Volume 2, numéro 1, summer 2007

EN :

We consider the job shop scheduling problem unit–Jm, where each job is processed once on each of m given machines. Every job consists of a permutation of tasks for all machines. The execution of any task on its corresponding machine takes exactly one time unit. The objective is to minimize the overall completion time, called makespan. The contribution of this paper are the following results: (i) For any input instance of unit–Jm with d jobs, the makespan of an optimum schedule is at most m + o(m), for d = o(m1/2). This improves on the upper bound O(m + d) given in [5] where O hides a constant equal to two as shown in [7]. For d = 2 the upper bound is improved to m + ⌈ √m ⌉. (ii) There exist input instances of unit–Jm with d = 2 such that the makespan of an optimum schedule is at least m + ⌈ √m ⌉, i.e., our upper bound for d = 2, see result (i), cannot be improved. (iii) We present a randomized on-line approximation algorithm for unit–Jm with the best known approximation ratio for d = o(m1/2). (iv) There is no deterministic on-line algorithm with a competitive ratio better than 4/3 for unit–Jm with two jobs, and for three or more jobs, there is no deterministic on-line algorithm which is better than 1.5 competitive. Compared with the expected competitive ratio of (iii) which tends to 1, this shows that for unit–Jm randomization is very powerful compared with determinism. For two and three jobs, deterministic on-line algorithms with competitive ratios tending to 4/3 and 1.5 respectively are presented. (v) A deterministic approximation algorithm for unit–Jm is described that works in quadratic time for constant d and has an approximation ratio of 1 + 2d/⌊√m ⌋ for d ≤ 2 log2 m.

EN :

The 3-COLORABILITY problem is NP-complete in the class of claw-free graphs. In this paper we study the computational complexity of the problem in subclasses of claw-free graphs defined by forbidding finitely many additional subgraphs (line graphs and claw-free graphs of bounded vertex degree being examples of such classes). We prove a necessary condition for the polynomial-time solvability of the problem in such classes and propose a linear-time solution for an infinitely increasing hierarchy of classes that meet the condition. To develop such a solution for the basis of this hierarchy, we generalize the notion of locally connected graphs that has been recently studied in the context of the 3-COLORABILITY

EN :

One of the most celebrated polynomially solvable cases of the TSP is the Gilmore-Gomory TSP. The patching scheme for the problem developed by Gilmore and Gomory has several interesting features. Its generalization, called the GG-scheme, has been studied by several researchers and polynomially testable sufficiency conditions for its validity have been given, leading to polynomial schemes for large subclasses of the TSP. A good characterization of the subclass of the TSP for which the GG-scheme produces an optimal solution, is an outstanding open problem of both theoretical and practical significance. We give some necessary conditions and a new, polynomially testable sufficiency condition for the validity of the GG-scheme that properly includes all previously known such conditions.

EN :

We corrected proofs of two results on the greedy algorithm for the Symmetric TSP and answered a question in Gutin and Yeo, Oper. Res. Lett. 30 (2002), 97–99.

EN :

We consider mixed-integer linear programs with arbitrary bounded integer variables. We first describe a cutting plane approach based on the reformulation of integer variables into binary variables and describe a practical algorithm to compute these cuts for the original problem. We use the term “Binarize and Project” to highlight the similarity to the back onto the original space. Indeed, the interest of this approach lies in taking advantage of cutting plane approaches efficient for mixed-binary problems while keeping the problem in its non-binary form for improving the efficiency of the branch-and-bound procedure.

We then propose a new strengthened reformulation into binary variables that answers some concerns and limitations raised in [9], by ensuring that only one application of the lift-and-project convexification procedure to the binary reformulation of the problem is required to obtain a strengthening of the original problem.

Finally, the method is implemented inside the COIN optimization library and a preliminary experimentation is performed on problems from the MIPLIB library. The computational results confirm that the use of the proposed binary reformulation and cutting plane generation procedure leads to an improved integrality gap reduction albeit with an increased computing time.

EN :

Ant colony algorithms are a class of metaheuristics which are inspired from the behaviour of real ants. The original idea consisted in simulating the stigmergic communication, therefore these algorithms are considered as a form of adaptive memory programming. A new formalization was proposed for the design of ant colony algorithms, introducing the biological notions of heterarchy and communication channels. We are interested in the way ant colonies handle the information. According to these issues, a heterarchical algorithm called “Continuous Interacting Ant Colony” (CIAC) was previously designed for the optimization of multiminima continuous functions. We propose in that paper an improvement of CIAC, by the way of a hybridization with the local search Nelder-Mead algorithm. The new algorithm called “Hybrid Continuous Interacting Ant Colony” (HCIAC) compares favorably with some competing algorithms on a large set of standard test functions.

EN :

We consider on-line network synthesis problems. Let N = {1, , n} be a set of n sites. Traffic flow requirements between pairs of sites are revealed one by one. Whenever a new request rij = rji (i < j) between sites i and j is revealed, an on-line algorithm must install the additional necessary capacity without decreasing the existing network capacity such that all the traffic requirements are met. The objective is to minimize the total capacity installed by the algorithm. The performance of an on-line algorithm is measured by the competitive ratio, defined to be the worst-case ratio between the total capacity by the on-line algorithm and the total optimal (off-line) capacity assuming we have priori information on all the requirements initially. We distinguish between two on-line versions of the problem depending on whether the entire set of sites is known a prior or not. For the first version where the entire set of site is unknown, we present a best possible algorithm along with a matching lower bound. For the second version where the entire set of sites is known a priori, we present a best possible algorithm for n ≤ 6.