A hierarchical approach to schedule the two-machine flow shop problem with flexible periodic synchronized maintenance

Abstract

This paper tackles the makespan minimisation for the well-known two-machine flow shop problem with flexible periodic maintenance activities on both machines. The maintenance starting dates are to be decided along with the job's sequence. We adopt a hierarchical approach in which we first decide the job's sequence and then the maintenance starting dates. We identify a dominance rule and a polynomial case, and construct an enhancement procedure. We develop and test several variants of Tabu search and simulated annealing metaheuristics. We also propose an adaptation of the well-known NEH heuristic. The experimental study shows the superiority of one of the variants of simulated annealing and the efficiency of the dominance rule. [Received: 15 July 2022; Accepted: 8 May 2023]