Lower Bounds for Scheduling on Identical Parallel Machines with Heads and Tails

Journal Article

Haouari, Mohamed . 2004

• Publication Online URL: Lower Bounds for Scheduling on Identical Parallel Machines with Heads and Tails
• Tags: Scheduling, identical parallel machines, release dates, delivery times, makespan, lower bound
• Magazine \ Newspaper: Annals of Operations Research
• Issue Number: 1-4
• Volume Number: 129
• Pages: 187-204

Publication Abstract

In this paper, we investigate new lower bounds for the P|rj,qj|Cmax scheduling problem. A new bin packing based lower bound, as well as several new lifting procedures are derived for this strongly NP -hard problem. Extensive numerical experiments show that the proposed lower bounds consistently outperform the best existing ones.