Tight bounds for the identical parallel machine scheduling problem

We address the problem of minimizing makespan on identical parallel machines. We propose new lower bounding strategies and heuristics for this fundamental scheduling problem. The lower bounds are based on the so-called lifting procedure. In addition, two optimization-based heuristics are proposed. These heuristics require iteratively solving a subset-sum problem. We present the results of computational experiments that provide strong evidence that the new proposed lower and upper bounds consistently outperform the best bounds from the literature. © 2006 Wiley Periodicals, Inc.