This paper presents a state-of-the-art survey on multicriteria scheduling and introduces a definition of a multicriteria scheduling problem. It provides a framework that allows to tackle multicriteria scheduling problems, according to Decision Aid concepts. This problem is decomposed into three different problems. The first problem is about obtaining a model. The second one is how to take criteria into account and the third one is about solving a scheduling problem. An extension to an existing notation for scheduling problems is proposed for multicriteria scheduling problems. Then, basic results from the literature on multicriteria optimization are presented. These results are used to build the final scheduling problem to solve. Finally a survey is presented for one-machine, parallel machines and flowshop multicriteria scheduling problems.

Assume that n tasks must be processed by one machine in a fixed sequence. The processing time, the preferred starting time and the earliness and tardiness costs per time unit are known for each task. The problem is to allocate each task a starting time such that the total cost incurred by the early and tardy tasks is minimum. Garey et al. have proposed a nice O(nlogn) algorithm for the special case of symmetric and task-independent costs. In this paper we first extend that algorithm to the case of asymmetric and task-independent cost without increasing its worst-case complexity. For the general case of asymmetric and task-dependent costs, we propose an O(n3 logn) algorithm based on a strong dominance property that yields to model the scheduling problem as a minimum cost path in a valued directed acyclic graph.

To cope with its development, a French operator of mobile telephone networkmust periodically plan the purchase and the installation of new hardware,in such a way that a hierarchy of constraints (required and preferred)is satisfied.This paper presents the “constructive repair” method we used to solvethis problem within the allowed computing time (1 min). This method repairsthe planning during its construction. A sequence of repair procedures is defined: if a given repair cannot be achieved on a partial solution,a stronger repair (possibly relaxing more important constraints) is called upon.We tested our method on ten (both hand-made and real) problems. All our solutions were at least as good as thoses computed by hand by the engineer in charge with the planning.

In this paper we will describe a new class of coloring problems, arising from military frequency assignment, where we want tominimize the number of distinct n-uples of colors used to color a givenset of n-complete-subgraphs of a graph. We will propose two relaxations based onSemi-Definite Programming models for graph and hypergraphcoloring, to approximate those (generally) NP-hard problems, as well asa generalization of the works of Karger et al. for hypergraph coloring,to find good feasible solutions with a probabilisticapproach.

In this paper we present a method to perform fast simulation oflarge Markovian systems. This method is based on the use of threeconcepts: Markov chain uniformization, event-driven dynamics,and modularity. An application of urban trafficsimulation is presented to illustrate the performance of our approach.

The Reverse Elimination Method (REM) is a dynamic strategy for managing the tabu list. It is based on logical interdependencies between the solutions encountered during recent iterations of the search. REM provides both a necessary and sufficient condition to prevent cycling. The purpose of this paper is first to incorporate in REM a chronological order rule when cycling is unavoidable, thereby assuring the finite convergence of Tabu Search. Secondly, we correct a generalization of REM, the so-called REM-t method proposed by Glover (1990) where t is an integer parameter which controls the number of tabu attributes. A suitable adjustment of this parameter t can be designed in order to create a balance between diversification and intensification. In this paper, new dynamic rules for controlling the adjustment of the parameter t, are proposed. Finally, to illustrate the differences between the variants proposed for managing the tabu list, we test some of them on the 0–1 multidimensional knapsack problem.

We study a continuous version of the capacity and flow assignment problem(CFA) where the design cost is combined with an average delay measureto yield a non convex objective function coupled with multicommodity flowconstraints. A separable convexification of each arc cost function is proposedto obtain approximate feasible solutions within easily computable gaps fromoptimality. On the other hand, DC (difference of convex functions) programming can be usedto compute accurate upper bounds and reduce the gap.The technique is shown to be effective when topology is assumedfixed and capacity expansion on some arcs is considered.

A method to infer X-trees (valued trees having X as set of leaves) from incomplete distance arrays (where some entries are uncertain or unknown) is described. It allows us to build an unrooted tree using only 2n-3 distance values between the n elements of X, if they fulfill some explicit conditions. This construction is based on the mapping between X-tree and a weighted generalized 2-tree spanning X.