Volume 1, numéro 2, summer 2006

EN :

Given a weighted graph G = (V, E, w), we investigate the problem of constructing a sequence of n = |V | subsets of vertices M1, . . . , Mn (called groups) with small diameters, where the diameter of a group is calculated using distances in G. The constraint on these n groups is that they must be incremental: M1 ⊂ M2 ⊂ ⊂ Mn = V . The cost

of a sequence is the maximum ratio between the diameter of each group Mi and the diameter of a group N i with i vertices and minimum diameter: max2 i n nD(Mi) D(N∗ i ) o. This quantity captures the impact of the incremental constraint on the diameters of the groups in a sequence. We give general bounds on the value of this ratio and we prove that the problem of constructing an optimal incremental sequence cannot be solved approximately in polynomial time with an approximation ratio less than 2 unless P = NP . Finally, we give a 4-approximation algorithm and we show that the analysis of our algorithm is tight.

EN :

We study the on-line bin packing problem (BPP). In BPP, we are given a sequence B of items a1, a2, . . . , an and a sequence of their sizes (s1, s2, . . . , sn) (each size si ∈ (0, 1]) and are required to pack the items into a minimum number of unit-capacity bins. Let R1{ , } be the minimal asymptotic competitive ratio of an on-line algorithm in the case when all items are only of two different sizes α and β. We prove that max{R1{ , } : α, β ∈ (0, 1]} = 4/3. We also obtain an exact formula for R1{ , } when max{α, β} > 12 . This result extends the result of Faigle, Kern and Turan (1989) that R1{ , } = 43 for β = 12 − ǫ and α = 12 + ǫ for any fixed nonnegative ǫ < 16 .

EN :

This paper is devoted to basic scheduling problems in which the scheduling cost of a job is not a function of its completion time. Instead, the cost is derived from the integration of a cost function over the time intervals on which the job is processed. This criterion is specially meaningful when job preemption is allowed. Polynomial algorithms are presented to solve some special cases including a one-machine problem with a common due date and a two-machine problem with linear nondecreasing cost functions.

EN :

Given a network with known link capacities and traffic demands, one can compute the paths to be used and the amount of traffic to be send through each path by solving a classical multi-flow problem. However, more quality of service constraints such as delay constraints, may be imposed and the routing problem becomes difficult to solve. We assume that the delay on each link depends on both its capacity and the total flow on it. We show that satisfying the delay constraints and the capacity constraints is an NP-complete problem. We give a convex relaxation of the delay constrained routing problem and present some ways to get upper and lower bounds on the problem.

EN :

The Vehicle Routing Problem with Time Windows (VRPTW) is an important problem in logistics, which is an extension of well known Vehicle Routing Problem (VRP), with a central depot. The Objective is to design an optimal set of routes for serving a number of customers without violating the customer’s time window constraints and vehicle capacity constraint. It has received considerable attention in recent years. This paper reviews the research on Evolutionary Algorithms for VRPTW. The main types of evolutionary algorithms for the VRPTW are Genetic Algorithms and Evolutionary Strategies which may also be described as Evolutionary metaheuristics to distinguish them from other metaheuristics. Along with these evolutionary metaheuristics, this paper reviews heuristic search methods that hybridize ideas of evolutionary algorithms with some other search technique, such as tabu search, guided local search, route construction heuristics, ejection chain approach, adaptive large neighborhood search, variable neighborhood search and hierarchal tournament selection. In addition to the basic features of each method, experimental results for the 56 benchmark problem with 100 customers of Solomon (1987) and Gehring and Homberger (1999) are presented and analyzed.