Minimizing Makespan on Parallel Machines Subject to Release Dates and Delivery Times

Journal Article

Gharbi, Anis . 2002

• رابط المنشور على الويب: Minimizing Makespan on Parallel Machines Subject to Release Dates and Delivery Times
• الوسوم: scheduling, identical parallel machines, makespan, release dates, delivery times, branch-and-bound
• المجلة \ الصحيفة: Journal of Scheduling
• رقم العدد: 4
• رقم الإصدار السنوي: 5
• الصفحات: 329–355

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

We consider the problem of minimizing the makespan on identical parallel machines subject to release dates and delivery times. The objective of this paper is to develop exact branch-and-bound algorithms to solve this strongly NP-hard problem. A preprocessing algorithm is devised to speed up the convergence of the proposed algorithms, and a new tight bounding scheme is introduced. The search tree is also reduced using a polynomial selection algorithm. Extensive computational experiments show that instances with up to 300 jobs can be solved exactly in a moderate CPU time.