Optimal Scheduling of a Two-stage Hybrid Flow Shop

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 -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.