Metaheuristics for solving the multi-stage hybrid flow shop scheduling problem with dedicated machines

Abstract

This paper addresses the multi-stage hybrid flow shop scheduling problem with dedicated machines (HFSSP-DM), with more than three stages. The primary objective is to minimise the maximum completion time of jobs (makespan). We first formulate a mixed integer programming (MIP)-model for the problem and adapt three metaheuristic algorithms from the literature on two-stage hybrid flow shop with dedicated machines, simulated annealing (SA), Tabu search (TS), and genetic algorithm (GA). In addition, we introduce, for the first time in this context, a recent swarm-based algorithm, the reptile search algorithm (RSA), specifically tailored to tackle HFSSP-DM. To evaluate the effectiveness of these metaheuristics, we conduct a comprehensive set of computational experiments across various problem classes with different machine configurations and job sizes. The results show that RSA significantly outperforms GA, TS and SA, achieving near-optimal solutions with a very reasonable computational time. These findings underscore RSA's potential as a powerful tool for solving complex hybrid flow shop scheduling problems and offer valuable insights for optimising resource allocation and minimising production time in multi-stage manufacturing environments.