A special class of scheduling problems is studied in this paper, named Hybrid Flowshop, n jobs have to be performedin a shop and each of them has the same routing (so this is a flowshop). A job consists in k different operations. A set of machines are able to perform each operation and thisset is called a stage. So when a job consists in two operations,there are two stages in the shop. After introducing the scheduling generalities, we define our preocupations and we propose a notationin order to identify precisely and rapidly a problem. Then a state of the art is proposed and presented in two parts. The first one is dedicated to the 2-stage hybrid flowshops and the second to thegeneral case of the k-stage. Then a summary puts to the fore that many problems remain unsolved.

Fractional programming consists in optimizing a ratio oftwo functions subject to some constraints. Different versions of thismodel, linear or nonlinear, have applications in various fields likecombinatorial optimization, stochastic programming, data bases, andeconomy. Three resolution methods are presented: direct solution,parametric approach and solution of an equivalent problem.

An algebraic and combinatorial approach to the study ofthe Quadratic Assignment Problem produced theoretical results that canbe applied to (meta) heuristics to give them information about theproblem structure, allowing the construction of algorithms. In thispaper those results were applied to inform a Simulated Annealing-typeheuristic (which we called RedInv-SA). Some results from tests withknown literature instances are presented.

This paper presents a heuristic column generation method for solving vehicle routing problems with a heterogeneous fleet of vehicles. The method may also solve the fleet size and composition vehicle routing problem and new best known solutions are reported for a set of classical problems. Numerical results show that the method is robust and efficient, particularly for medium and large size problem instances.

The standard multiple criteria optimization starts with anassumption that the criteria are incomparable. However, there are manyapplications in which the criteria express ideas of allocation ofresources meant to achieve some equitable distribution. This paperfocuses on solving linear multiple criteria optimization problems withuniform criteria treated in an equitable way. An axiomatic definition ofequitable efficiency is introduced as an refinement ofPareto-optimality. Various generation techniques are examined and thestructure of the equitably efficient set is analyzed.

In previous papers, we used a Markovian model to determine the optimal functioning rules of a distributed system in various settings. Searchingoptimal functioning rules amounts to solve an optimization problemunder constraints. The hierarchy of solutions arising from the above problem is called the “first order hierarchy”, and may possibly yield equivalent solutions. The present paper emphasizes a specific technique for deciding between two equivalent solutions, which establishes the“second order hierarchy”.

We propose a temporal decomposition approach for the one-machine schedulingproblem with ready times and due dates. A set of feasible schedules ischaracterized by means of constraint-based analysis rules. They permit thedetermination of the feasible locations of each task in a sequence, representedby rank intervals. A decomposition procedure based on comparisons of rankintervals is developed in order to group tasks to be sequenced in theneighbourhood of each other in a feasible solution. Computational results are reported so that the capability of our approach to prepare the problem for a solution computation, achieved either by a human operator or by an automatic solving procedure, can be evaluated.

Given a graph with colored edges, a Hamiltonian cycle iscalled alternating if its successive edges differ in color. The problemof finding such a cycle, even for 2-edge-colored graphs, is triviallyNP-complete, while it is known to be polynomial for 2-edge-coloredcomplete graphs. In this paper we study the parallel complexity of finding such a cycle, if any, in 2-edge-colored complete graphs. We givea new characterization for such a graph admitting an alternatingHamiltonian cycle which allows us to derive a parallel algorithm forthe problem. Our parallel solution uses a perfect matching algorithmputting the alternating Hamiltonian cycle problem to the RNC class. Inaddition, a sequential version of our parallel algorithm improves thecomputation time of the fastest known sequential algorithm for thealternating Hamiltonian cycle problem by a factor of $O(\sqrt {n} )$ .

In this paper, a discrete-event simulation model iscoupled with a genetic algorithm to treat highly combinatorialscheduling problems encountered in a production campaign of a finechemistry plant. The main constraints and features of fine chemistryhave been taken into account in the development of the model, thusallowing a realistic evaluation of the objective function used in thestochastic optimization procedure. After a presentation of problemcombinatorics, the coupling strategy is then proposed and illustrated byan example of industrial size (24 equipment items, 140 products, 12different production recipes and 40 products to be recycled during thecampaign). This example serves as an incentive to show how the approachcan improve production performance. Three technical criteria have beenstudied: campaign completion time, average product cycle time, respectof due-dates. Two kinds of optimization variables have been considered:product input order and/or allocation of heuristics for conflittreatment. The results obtained are then analysed and some perspectivesof this work are presented.

This paper derives a good approach to approximating the expected inventory level per unit time for the continuousreview (Q, r) perishable inventory system. Three existing approximation approaches are examined and compared with the proposed approach. Three stockout cases, including the full backorder, the partial backorder, and the full lost sales cases, which customers or material users generally use to respond to a stockout condition are considered.This study reveals the fact that the proposed approximationis simple yet good and suitable for incorporation into the (Q, r)perishable inventory model to determine the best ordering policy.The results from numerical examples and a sensitivity analysisindicate that severe underestimation or overestimation of the expected inventory level per unit time due to the use of an inappropriate approximation approach would result in great distortion in the determination of the best ordering policy.

We address the 3-Machine Assembly-Type Flowshop Scheduling Problem (3MAF). This problem is known to be NP-complete in the strongsense. We propose an exact branch and bound method based on a recursiveenumeration of potential inputs and outputs of the machines. Using this algorithm,several large size instances have been solved to optimality.

Constructive heuristics for shop scheduling problems are often based onpriority (or dispatching) rules. However, recent work has demonstratedthat insertion algorithms that step by step insert operations or jobs into partial schedules usually clearly outperform priority rules.In this paper, we consider various job shop scheduling problems withsetup times. For each job a specific technological route and a releasedate are given. Moreover, the jobs are partitioned into groups. Asequence independent setup time S rj is required on machine j when a job of the r-th group is processed after a job of another group. We consider different types of job availability, namely item and batch availability. As objective function we use both regular and nonregular criteria. For such problems we apply insertion techniquescombined with beam search. Especially we consider different insertion orders of the operations or jobs. A refined variant of the insertion algorithmis presented, where several operations are inserted in parallel. The proposed variants have been tested on a large collection of test problems and compared with other constructive algorithms based onpriority rules.

Comparing q-ary relations on a set ${\cal O}$ ofelementary objects is one of the most fundamental problems ofclassification and combinatorial data analysis. In this paper thespecific comparison task that involvesclassification tree structures (binary or not) is considered in thiscontext. Two mathematical representationsare proposed. One is defined in terms of a weighted binary relation; the second uses a 4-ary relation.The most classical approaches to tree comparison are discussed in thecontext of a set theoretic representation of these relations. Formalandcombinatorial computing aspects of a construction method for a verygeneralfamily of association coefficients between relations are presented. The main purpose of this article is to specify the componentsof this construction, based on a permutational procedure, when thestructuresto be compared are classification trees.

This paper presents results about the optimal order interval in a contextof fuzzy information about inventory management. The classical inventory model is based on well known cost and demand rate. In practice, this accurate estimation is very difficult to obtain, even impossible. Consequently, we propose a solution, not optimal in a classical sense,but allowing to choose an action which is not far from the optimal policywhatever the economic parameters may be. These parameters belong to a fieldwhich represents the error of estimation, this field is important to choose the solution.

We consider a generalized proximal point method (GPPA) forsolving the nonlinear complementarity problem with monotone operators inRn . It differs from the classical proximal point method discussedby Rockafellar for the problem of finding zeroes of monotone operatorsin the use of generalized distances, called φ-divergences,instead of the Euclidean one. These distances play not only aregularization role but also a penalization one, forcing the sequencegenerated by the method to remain in the interior of the feasible set,so that the method behaves like an interior point one. Under appropriateassumptions on the φ-divergence and the monotone operator weprove that the sequence converges if and only if the problem hassolutions, in which case the limit is a solution. If the problem doesnot have solutions, then the sequence is unbounded. We extend previousresults for the proximal point method concerning convex optimizationproblems.

We show that the problem of deciding if there is a scheduleof length three for the multiprocessor scheduling problem on identicalmachines and unit execution time tasks in -complete even for bipartitegraphs, i.e. for precedence graphs of depth one. This complexity resultextends a classical result of Lenstra and Rinnoy Kan [5].

We first motivate and define a notion of asymptoticdifferential approximation ratio. For this, we introduce a new class ofproblems called radial problems including in particular the hereditaryones. Next, we validate the definition of the asymptotic differentialapproximation ratio by proving positive, conditional and negativeapproximation results for some combinatorial problems. We first derive adifferential approximation analysis of a classical greedy algorithm forbin packing, the “first fit decreasing”. Next we deal with minimumvertex-covering-by-cliques of a graph and the minimumedge-covering-by-complete-bipartite-subgraphs of a bipartite graph anddevise a differential-approximation preserving reduction from the formerto the latter. Finally, we prove two negative differential approximationresults about the ability of minimum vertex-coloring to be approximatedby a polynomial time approximation schema.

We consider two parallel M/M/1 queues. The server at one of the queuesis subject to intermittent breakdowns. By the theory of dynamic programming, we determine a threshold optimal policy which consists to transfer, when it is necessary, the customers that arrive at the first queue towards the second queue in order to minimize an instantaneous costdepending of the two queue lengths.

We give a new formulation for the problem of task scheduling intounrelated processors under precedence constraints. This formulation has a polynomial number of variables and does not require that theprocessing times be integer valued.

Single server queues with repeated attempts are useful inthe modeling of computer and telecommunication systems. In addition, weconsider in this paper the possibility of disasters. When a disasteroccurs, all the customers present in the system are destroyedimmediately. Using a regenerative approach, we derive a numericallystable recursion scheme for the state probabilities. This model can beemployed to analyze the behaviour of a buffer in computers with virusinfections.