Groupe d’études et de recherche en analyse des décisions


An Exact Algorithm for Makespan Minimization on Unrelated Parallel Machines

, et

The NP-hard problem addressed in this paper is well known in the scheduling literature as R|Cmax. We introduce lower bounds based on Lagrangian relaxations and additive techniques. These are used to obtain exact and approximation algorithms. Computational experiments show that they outperform the most effective algorithms from the literature.

, 28 pages