Efficiency of the solution representations for the hybrid flow shop scheduling problem with makespan objective

• Published in: Computers & operations research 2019-09, Vol.109, p.77-88
• Main Authors: Fernandez-Viagas, Victor, Perez-Gonzalez, Paz, Framinan, Jose M.
• Format: Article
• Language: English
• Subjects: Algorithms; Complete enumeration; Enumeration; Flowshop; Hybrid flow shop; Job shop scheduling; Job shops; Makespan; MILP; Operations research; Production scheduling; Reduction; Representations; Review; Schedules; Scheduling; Solution representation; Solution space; Tradeoffs
• ISSN: 0305-0548; 1873-765X; 0305-0548
• DOI: 10.1016/j.cor.2019.05.002

•We consider and review different representations, sequencing rules, and assignment rules.•We analyse the structure of the solution space by using complete enumeration.•We present 4 MILPs to model the different solution representations.•We compare 22 different approaches in two extensive sets of instances. In this paper we address the classical hybrid flow shop scheduling problem with makespan objective. As this problem is known to be NP-hard and a very common layout in real-life manufacturing scenarios, many studies have been proposed in the literature to solve it. These contributions use different solution representations of the feasible schedules, each one with its own advantages and disadvantages. Some of them do not guarantee that all feasible semiactive schedules are represented in the space of solutions –thus limiting in principle their effectiveness– but, on the other hand, these simpler solution representations possess clear advantages in terms of having consistent neighbourhoods with well-defined neighbourhood moves. Therefore, there is a trade-off between the solution space reduction and the ability to conduct an efficient search in this reduced solution space. This trade-off is determined by two aspects, i.e. the extent of the solution space reduction, and the quality of the schedules left aside by this solution space reduction. In this paper, we analyse the efficiency of the different solution representations employed in the literature for the problem. More specifically, we first establish the size of the space of semiactive schedules achieved by the different solution representations and, secondly, we address the issue of the quality of the schedules that can be achieved by these representations using the optimal solutions given by several MILP models and complete enumeration. The results obtained may contribute to design more efficient algorithms for the hybrid flow shop scheduling problem.