Back

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.

, 28 pages

Research Axis

Research application