Tight Bounds for the Identical Parallel Machine Scheduling Problem

Journal Article

Haouari, Mohamed . 2006

• Publication Online URL: Tight Bounds for the Identical Parallel Machine Scheduling Problem
• Tags: Scheduling, identical parallel machines, lower bounds, heuristics
• Magazine \ Newspaper: International Transactions in Operational Research
• Issue Number: 6
• Volume Number: 13
• Pages: 529–548

Publication Abstract

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.