Optimal Scheduling of a Two-Stage Hybrid Flow Shop

Journal Article

Haouari, Mohamed . 2006

• رابط المنشور على الويب: Optimal Scheduling of a Two-Stage Hybrid Flow Shop
• الوسوم: Deterministic scheduling, Hybrid flow shop, Branch-and-bound method
• المجلة \ الصحيفة: Mathematical Methods of Operations Research
• رقم العدد: 1
• رقم الإصدار السنوي: 64
• الصفحات: 107-124

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

We present an exact branch-and-bound algorithm for the two-stage hybrid flow shop problem with multiple identical machines in each stage. The objective is to schedule a set of jobs so as to minimize the makespan. This is the first exact procedure which has been specifically designed for this strongly NP -hard problem. Among other features, our algorithm is based on the exact solution of identical parallel machine scheduling problems with heads and tails. We report the results of extensive computational experiments on instances which show that the proposed algorithm solves large-scale instances in moderate CPU time.