Branch and bound lower bounds for the hybrid flowshop

The Hybrid FlowShop HFS consists in the classical multistage flowshop, each stage being composed of identical parallel machines. Minimizing the makespan is NP-Hard in general. To schedule the HFS, Brah and Hunsucker (91), have designed a branch and bound algorithm. in order to solve larger instances, tight lower bounds are required to reduce the enumeration space and time. This paper introduces three improvements of Brah's algorithm and three new lower bounds. The latter are based upon the relaxation of the problem into a single stage sub-problem. Although large problems remain very hard, numerical tests have shown that the new algorithm has drastically reduced the number of the explored nodes as well as the running time needed to find an optimal solution.