A Branch-and-Bound Algorithm for the Permutation Flow Shop Scheduling Problem Subject to Release Dates and Delivery Times

We consider the problem of minimising the makespan in an m-machine flow shop subject to release dates and delivery times which requires scheduling n jobs through m machines which are placed in series. This problem is known to be NP-hard. We propose a new branch-and-bound algorithm which encompasses several features including a procedure for adjusting heads and tails, heuristics, and a lower bounding procedure which is based on the exact solution of the two-machine flow shop problem with time lags, ready times, and delivery times. We present extensive computational experiments on two sets of problems, with up to 6000 operations, which show that the proposed algorithm solves large-scale instances in moderate CPU time