Optimal Scheduling of a Two-Stage Hybrid Flow Shop

Journal Article

Haouari, Mohamed . 2006

• Publication Online URL: Optimal Scheduling of a Two-Stage Hybrid Flow Shop
• Tags: Deterministic scheduling, Hybrid flow shop, Branch-and-bound method
• Magazine \ Newspaper: Mathematical Methods of Operations Research
• Issue Number: 1
• Volume Number: 64
• Pages: 107-124

Publication Abstract

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.