Tight Bounds for the Identical Parallel Machine Scheduling Problem

Journal Article

Haouari, Mohamed . 2006

• رابط المنشور على الويب: Tight Bounds for the Identical Parallel Machine Scheduling Problem
• الوسوم: Scheduling, identical parallel machines, lower bounds, heuristics
• المجلة \ الصحيفة: International Transactions in Operational Research
• رقم العدد: 6
• رقم الإصدار السنوي: 13
• الصفحات: 529–548

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

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.