EXACT AND APPROXIMATION ALGORITHMS FOR MAKESPAN MINIMIZATION ON UNRELATED PARALLEL MACHINES

The NP-hard problem addressed in this paper is well known in the sched uling literature as R parallel to C-max. We propose lower bounds based on Lagrangian relaxations and additive techniques. We then introduce new cuts which eliminate infeasible disjunctions on the cost function value, and prove that the bounds obtained through such cuts dominate t he previous bounds. These results are used to obtain exact and approxi mation algorithms. Computational experiments show that they outperform the most effective algorithms from the literature.