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

Journal Article

Haouari, Mohamed . 2004

• رابط المنشور على الويب: Lower Bounds for Scheduling on Identical Parallel Machines with Heads and Tails
• الوسوم: Scheduling, identical parallel machines, release dates, delivery times, makespan, lower bound
• المجلة \ الصحيفة: Annals of Operations Research
• رقم العدد: 1-4
• رقم الإصدار السنوي: 129
• الصفحات: 187-204

مستخلص المنشور

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.