G-92-45
An Exact Algorithm for Makespan Minimization on Unrelated Parallel Machines
, , and BibTeX reference
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.
Published December 1992 , 28 pages