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

Authors: Asma Ouled Bedhief; Amira Brahmi; Najla Aissaoui; Safa Bhar Layeb

Addresses: LR-OASIS, Department of Industrial Engineering, National Engineering School of Tunis, University of Tunis El Manar, Tunis, Tunisia; Department of Industrial Engineering, National Engineering School of Bizerte, University of Carthage, Tunis, Tunisia ' LR-OASIS, Department of Industrial Engineering, National Engineering School of Tunis, University of Tunis El Manar, Tunis, Tunisia ' LR-OASIS, Department of Industrial Engineering, National Engineering School of Tunis, University of Tunis El Manar, Tunis, Tunisia; Department of Industrial Engineering, National Engineering School of Carthage, University of Carthage, Tunis, Tunisia ' LR-OASIS, Department of Industrial Engineering, National Engineering School of Tunis, University of Tunis El Manar, Tunis, Tunisia; Centre Génie Industriel, Université Toulouse, IMT Mines Albi, Albi, France

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.

Keywords: scheduling; hybrid flow shop; multiple stages; multiple dedicated machines; MIP-model; reptile search algorithm; RSA; genetic algorithm; Tabu search; simulated annealing.

DOI: 10.1504/IJAOM.2025.150034

International Journal of Advanced Operations Management, 2025 Vol.16 No.4, pp.373 - 415

Received: 03 Dec 2024
Accepted: 18 Jun 2025
Published online: 21 Nov 2025 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article