Dynamic Cell Formation Problem (DCFP) seeks to cope with variation in part mix anddemands using machine relocation, replication, and removing; whilst from practical pointof view it is too hard to move machines between cells or invest on machine replication. Tocope with this deficiency, this paper addresses Reconfigurable Dynamic Cell FormationProblem (RDCFP) in which machine modification is conducted instead of their relocation orreplication in order to enhance machine capabilities to process wider range of productiontasks. In this regard, a mixed integer nonlinear mathematical model is proposed, which isNP-hard. To cope with the proposed model’s intractability, an Imperialist CompetitiveAlgorithm (ICA) is developed, whose obtained results are compared with those of GeneticAlgorithm’s (GA’s), showing superiority and outperformance of the developed ICA.

In this paper we study the main properties of the strongBerge equilibrium, then we prove a theorem of its existence based on the KyFan inequality and finally, we provide an algorithm for its determination.

This paper presents a unified approach forbottleneckcapacity expansion problems. In the bottleneck capacity expansion problem, BCEP, we are given a finite ground set E, a family Fof feasible subsets of E and a nonnegative real capacity ĉefor all e ∈ E. Moreover, we are given monotone increasing cost functions f e for increasing the capacity of the elements e ∈ E as well as a budget B. The task is to determine new capacities ce ≥ ĉe such that the objective function given by maxF∈F mine∈F ce is maximized under the sideconstraint that the overall expansion cost does not exceed the budget B.We introduce an algebraic model for defining the overall expansion cost and for formulating the budget constraint. This models allows to capturevarious types of budget constraints in one general model.Moreover, wediscuss solution approaches for the general bottleneck capacityexpansion problem. For an important subclass of bottleneck capacity expansion problems we propose algorithms which perform a strongly polynomial number ofsteps. In this manner we generalize and improve a recent result ofZhang et al. [15].

The VIKOR method was introduced as a Multi-Attribute Decision Making (MADM) method to solve discrete decision-making problems with incommensurable and conflicting criteria. This method focuses on ranking and selecting from a set of alternatives based on the particular measure of “closeness” to the “ideal” solution. The multi-criteria measure for compromise ranking is developed from the l–p metric used as an aggregating function in a compromise programming method. In this paper, the VIKOR method is extended to solve Multi-Objective Large-Scale Non-Linear Programming (MOLSNLP) problems with block angular structure. In the proposed approach, the Y-dimensional objective space is reduced into a one-dimensional space by applying the Dantzig-Wolfe decomposition algorithm as well as extending the concepts of VIKOR method for decision-making in continues environment. Finally, a numerical example is given to illustrate and clarify the main results developed in this paper.

Most systems are characterized by uncertainties that cause throughput to be highly variable, for example, many modern production processes and services are substantially affected by random yields. When yield is random, not only is the usable quantity uncertain, but the random yield reduces usable capacity and throughput in the system. For these reasons, strategies are needed that incorporate random yield. This paper presents the analysis of the newsvendor model with a general random yield distribution, including the derivation of the optimal order quantity. Results are shown to converge to the basic newsvendor model for the case of perfect yield, and are further demonstrated using the case of general multiplicative random yield. Results have significant impact on both manufacturing and service sectors since the newsvendor model applies to many real-world situations.

In general, traditional production-inventory systems are based on a number of simplifying– but somewhat unrealistic – assumptions, including constant demand rate, constant holdingcost, and instantaneous order replenishment. These assumptions have been individuallychallenged in numerous variations of production-inventory models. Finite production ratemodels, such as economic production quantity (EPQ) systems consider gradual orderreplenishment. Stock-dependent demand models assume the demand rate to be an elasticfunction of the inventory level. Variable holding cost models assume the holding cost perunit per time period to be a function of the time spent in storage. In this paper, thethree simplifying assumptions are simultaneously relaxed in a new production-inventorysystem with a finite production rate, stock-level dependent demand rate, and variableholding cost. Mathematical models and optimum solution procedures, including nonlinearprogramming, are presented for two functional forms of holding cost variability. The maincontribution of this paper is the formulation and solution of a new production-inventorymodel that more closely represents real-world situations. The realistic assumptions andefficient solution algorithms should make the model practical and useful for industrialapplications.

In this paper, we present a new linear time algorithm forscheduling UECT (Unit Execution and Communication Time) trees on twoidentical processors. The chosen criterion is the makespan. The used strategy is based on clustering of tasks. We show that this algorithm builds optimal schedules. Some extensions are discussed for non UECT tasks.

Consider an M/M/1 retrial queue with collisions and working vacation interruption underN-policy. We use a quasi birth and death process to describe the considered system andderive a condition for the stability of the model. Using the matrix-analytic method, weobtain the stationary probability distribution and some performance measures. Furthermore,we prove the conditional stochastic decomposition for the queue length in the orbit.Finally, some numerical examples are presented.

Given a simple undirected weighted or unweighted graph, we try to cluster the vertex set into communities and also to quantify the robustness of these clusters. For that task, we propose a new method, called bootstrap clustering which consists in (i) defining a new clustering algorithm for graphs, (ii) building a set of graphs similar to the initial one, (iii) applying the clustering method to each of them, making a profile (set) of partitions, (iv) computing a consensus partition for this profile, which is the final graph partitioning. This allows to evaluate the robustness of a cluster as the average percentage of partitions in the profile joining its element pairs ; this notion can be extended to partitions. Doing so, the initial and consensus partitions can be compared. A simulation protocol, based on random graphs structured in communities is designed to evaluate the efficiency of the Bootstrap Clustering approach.

We introduce augmented Lagrangian methods for solving finite dimensional variational inequality problemswhose feasible sets are defined by convex inequalities, generalizing the proximal augmented Lagrangian methodfor constrained optimization. At each iteration, primal variables are updated by solvingan unconstrained variational inequality problem, and then dual variables are updated through a closed formula.A full convergence analysis is provided, allowing for inexact solution of the subproblems.

Tree decomposition introduced by Robertson and Seymour aims to decompose a problem into clusters constituting an acyclic graph. There are works exploiting tree decomposition for complete search methods. In this paper, we show how tree decomposition can be used to efficiently guide local search methods that use large neighborhoods like VNS. We propose DGVNS (Decomposition Guided VNS) which uses the graph of clusters in order to build neighborhood structures enabling better diversification and intensification. Second, we introduce tightness dependent tree decomposition which allows to take advantage of both the structure of the problem and the constraints tightness. Third, experiments performed on random instances (GRAPH) and real life instances (CELAR, SPOT5 and tagSNP) show the appropriateness and the efficiency of our approach. Moreover, we study and discuss the influence of the width of the tree decomposition on our approach and the relevance of removing clusters with very few proper variables from the tree decomposition.

This paper aims at developing efficient solving methods for an original service networkdesign problem imbued with sustainable issues. Indeed the network has to be designed forshort and local supply chain and for fresh food products. The original features of theproblem are the seasonality of supply, the limitation of transshipments for a product andno possibility of storage between consecutive periods. Decisions at strategic and tacticallevel are (1) decisions on a subset of hubs to open among a given set of potentiallocations, (2) transportation services to open between the actors and (3) flow quantitiesfor the fresh food products. We propose for this problem a Mixed Integer Programmingformulation and two solving techniques: Benders Decomposition and Dynamic Slope ScalingProcedure. These techniques are adapted to the problem and some experimental tests areconducted in order to compare the approaches on large-scale instances.


The Progressive Second Price mechanism (PSP), recently introduced byLazar and Semret to share aninfinitely-divisible resource among users through pricing, has been shown to verifyvery interesting properties. Indeed, the incentive compatibilityproperty of that scheme, and the convergence toan efficient resource allocation where established, using the frameworkof Game Theory.Therefore, that auction-based allocation and pricing scheme seemsparticularly well-suited to solve congestion problems intelecommunication networks, where the resource to share is theavailable bandwidth on a link.This paper aims atsupplementing the existing results by highlighting some properties of thedifferent equilibria that can be reached. We precisely characterize the possible outcomes of thePSP auction game in terms of players bid price: when the bid fee (cost of a bid update) tends to zero then the bid price of all users at equilibrium gets close to the so-called market clearing price of the resource. Therefore, observing an equilibrium of the PSP auction game gives some accurate information about the market clearing price of the resource.

The rising car usage deriving from growth in jobs and residential population causes airpollution, energy waste and consumption of people’s time. Public transport cannot be theonly answer to this increasing transport demand. Carpooling, which is based on the ideathat sets of car owners pick up colleagues while driving to or from the workplace, hasemerged to be a viable possibility for reducing private car usage in congested areas. Itsactual practice requires a suitable information system support and, the most important,the capability of effectively solving the underlying combinatorial optimization problem.This paper describes an ant colony algorithm based hybrid approach (HAC) for solving themulti-destination carpooling problem. Experiments have been performed to confirm theefficiency and the effectiveness of the approach.

L'opérateur de moyenne pondérée est très souvent utilisé pour définir une valeur v(a) à des entités a à partir de performances xj(a), j=1,...,n. Cet opérateur fait intervenir des poids spécifiquesw j comme multiplicateurs de la performance relative à la je composante. Ceci induit des possibilités de compensation des mauvaises performances par les meilleures qui peuvent être jugées inacceptables dans certains contextes concrets. En vue d'atténuer ces possibilités de compensation, on peut faire intervenir une seconde pondération à l'aide de poids de rangq r qui affectent le rôle que joue, dans la définition de v(a), la performance xj(a) en fonction du rang r qu'elle occupe dans un rangement des meilleures valeurs aux moins bonnes.Je commencerai par décrire trois exemples issus de contextes réels dans lesquels cette double pondération est nécessaire. Ensuite, je présenterai successivement un premier opérateur que j'ai introduit en 1996 sous le nom de moyenne ordonnée doublement pondérée (MO2P) et un second, proposé en 1997 par Torra [Int. J. Intell. Syst.12 (1997) 153–166.] “weighted ordered weighted average” (WOWA). Ces deux opérateurs n'étant signifiants que si les performances xj(a) se situent sur une même échelle d'intervalle E, je terminerai en proposant un autre type d'opérateur pouvant convenir lorsque E est une échelle purement ordinale.



The present paper addresses the class of two-stage robust optimization problems which canbe formulated as mathematical programs with uncertainty on the right-hand sidecoefficients (RHS uncertainty). The wide variety of applications and the fact that manyproblems in the class have been shown to be NP-hard, motivates the search for efficientlysolvable special cases. Accordingly, the first objective of the paper is to provide anoverview of the most important applications and of various polynomial or pseudo-polynomialspecial cases identified so far. The second objective is to introduce a new subclass ofpolynomially solvable robust optimization problems with RHS uncertainty based on theconcept of state-space representable uncertainty sets. A typicalapplication to a multi period energy production problem under uncertain customer loadrequirements is described into details, and computational results including a comparisonbetween optimal two-stage solutions and exact optimal multistage strategies arediscussed.

The Algorithm in this paper is designed to find theshortest path in a network given time-dependent cost functions. It hasthe following features: it is recursive; it takes place bath in abackward dynamic programming phase and in a forward evaluation phase; itdoes not need a time-grid such as in Cook and Halsey and Kostreva andWiecek's "Algorithm One”; it requires only boundedness (above andbelow) of the cost functions; it reduces to backward multi-objectivedynamic programming if there are constant costs. This algorithm has beensuccessfully applied to multi-stage decision problems where the costsare a function of the time when the decision is made. There are examplesof further applications to tactical delay in production scheduling andto production control.

In this paper, we develop a divide-and-conquer approach, called block decomposition, tosolve the minimum geodetic set problem. This provides us with a unified approach for allgraphs admitting blocks for which the problem of finding a minimum geodetic set containinga given set of vertices (g-extension problem) can be efficiently solved. Ourmethod allows us to derive linear time algorithms for the minimum geodetic set problem in(a proper superclass of) block-cacti and monopolar chordal graphs. Also, we show that hullsets and geodetic sets of block-cacti are the same, and the minimum geodetic set problemis NP-hard in cobipartite graphs. We conclude by pointing out several interesting researchdirections.

In this paper, we study the Steiner 2-edge connected subgraph polytope.We introduce a large class of valid inequalities for this polytope calledthe generalized Steiner F-partition inequalities, that generalizesthe so-called Steiner F-partition inequalities. We show that theseinequalities together with the trivial and the Steiner cutinequalities completely describe the polytope on a class of graphsthat generalizes the wheels. We also describe necessary conditions forthese inequalities to be facet defining, and as a consequence, weobtain that the separation problem over the Steiner 2-edge connectedsubgraph polytope for that class of graphs can be solved in polynomialtime. Moreover, we discuss that polytope in the graphs that decomposeby 3-edge cutsets. And we show that the generalized SteinerF-partition inequalities together with the trivial and the Steinercut inequalities suffice to describe the polytope in a class of graphsthat generalizes the class of Halin graphs when the terminals have aparticular disposition. This generalizes a result of Barahona andMahjoub [4] for Halin graphs. This also yields apolynomial time cutting plane algorithm for the Steiner 2-edgeconnected subgraph problem in that class of graphs.

This paper considers large shift scheduling problems with different shiftstart times and lengths, fractionable breaks and work stretch durationrestrictions. Two solution approaches are proposed to solve the problemsover a multiple-day planning horizon. The first approach is based on alocal branching strategy and the second one is based on a temporaldecomposition of the problem. Local branching is veryefficient in finding good feasible solutions when compared to a classicalbranch-and-bound procedure. However, the decomposition approach has theadvantage of yielding feasible solutions in short computing times, even for difficult instances.