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

# An Exact Algorithm for Makespan Minimization on Unrelated Parallel Machines

## Silvano Martello, François Soumis et P Toth

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