Tight bounds for the identical parallel machine-scheduling problem: Part II

A companion paper introduces new lower bounds and heuristics for the problem of minimizing makespan on identical parallel machines. The objective of this paper is threefold. First we describe further enhancements of previously described lower bounds. Second, we propose a new heuristic that requires solving a sequence of 0–1 knapsack problems. Finally, we show that embedding these newly derived bounds in a branch-and-bound procedure yields a very effective exact algorithm. Moreover, this algorithm features a new symmetry-breaking branching strategy. We present the results of computational experiments that were carried out on a large set of instances and that attest to the efficacy of the proposed algorithm. In particular, we report proven optimal solutions for some benchmark problems that have been open for some time.