A Novel Hybrid Recruit Simulated Annealing and Rat Swarm Optimization Algorithm for Permutation Flow Shop Scheduling

Abstract

ABSTRACT The permutation flow shop scheduling problem (PFSSP) is a classical NP‐hard problem that aims to determine an optimal job sequence across machines to minimize makespan. Existing swarm intelligence and evolutionary algorithms often suffer from premature convergence, parameter sensitivity, and limited adaptability in dynamic environments. This study proposes a Hybrid Recruit Simulated Annealing and Rat Swarm Optimization (HRSA‐RSO) algorithm that integrates the exploration capability of Rat Swarm Optimization with the probabilistic local refinement of Simulated Annealing. The hybrid design incorporates adaptive parameter control, a swap insertion neighborhood structure, and a modified Nawaz Enscore Ham (NEH) initialization strategy. An adaptive temperature mechanism guided by Hamming‐based diversity enhances robustness while reducing the need for manual tuning. Experiments on 15 Taillard benchmark instances show that HRSA‐RSO achieves an average Percentage Relative Deviation (PRD) of 0.46%–2.25%, outperforming 10 state‐of‐the‐art metaheuristics while using 20%–30% less computational time. Statistical analyses (ANOVA, Wilcoxon, and Friedman tests, p < 0.05) confirm the superiority and consistency of the proposed approach. Owing to its low computational overhead and strong scalability, HRSA‐RSO represents an effective and practical solution for large‐scale PFSSP and real‐world manufacturing environments.