Hybrid flow shop with multiple servers: a computational evaluation and efficient divide-and-conquer heuristics

Abstract This paper focuses on the minimisation of the makespan in a hybrid flow shop layout with multiple servers and identical machines. Servers are renewable secondary resources responsible of executing the setup times of the jobs. Although the use of human supervision is very extensive in real manufacturing scenarios, its study in academia is still very scarce. In fact, to the best of our knowledge, the hybrid flow shop with servers has not been addressed in the literature so far. Hence, we first analyse the problem and identify a number of problem properties. By using these properties, we design two constructive heuristics based on a divide-and-conquer mechanism and four composite heuristics based on memory-based procedures and local search that use an efficient representation of the solutions. In addition, in order to picture the state-of-the-art of the most efficient heuristics for this problem, we re-implement and adapt the most promising heuristics from related scheduling problems. All these heuristics, a total of 31, are compared in an extensive computational evaluation with 1,620 instances. The results show the excellent performance of the heuristics proposed.