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 problems with release dates and tails. Several heuristics art: used to compute upper bounds. Lower bounds are based upon the single-stage subproblem relaxation. Several upper and lower bounding strategies are considered. Numerical tests show that, in a few minutes of running time, and even for the hardest (i.e. without a bottleneck stage) and mid-size problems, the algorithm has reduced the initial gap between upper and lower bounds by 50% on average. (C) 2000 Published by Elsevier Science B.V. All rights reserved.