A branch-and-bound algorithm for the hybrid flowshop

This paper introduces a branch-and-bound algorithm for the hybrid flowshop scheduling problem to minimize makespan. The algorithm can also cope with p roblems with release dates and tails. Several heuristics art: used to compu te upper bounds. Lower bounds are based upon the single-stage subproblem re laxation. Several upper and lower bounding strategies are considered. Numer ical tests show that, in a few minutes of running time, and even for the ha rdest (i.e. without a bottleneck stage) and mid-size problems, the algorith m has reduced the initial gap between upper and lower bounds by 50% on aver age. (C) 2000 Published by Elsevier Science B.V. All rights reserved.