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