A New Hybrid Social Spider Optimization and Tabu Search for the Permutation Flow Shop Scheduling Problem

The permutation flow shop scheduling problem (PFSP) is an NP‐complete problem that represents a significant challenge in manufacturing and production environments. Memetic algorithms (MAs) that hybridize global search strategies with local refinement techniques are widely regarded as among the most powerful metaheuristic approaches for addressing complex combinatorial challenges. This paper presents a new hybrid social spider optimization and tabu search (SSO‐TS) approach for minimizing the makespan in PFSP. SSO‐TS combines the strengths of SSO and TS by unifying the global diversification capability of SSO with the local intensification capability of TS, yielding a hybrid strategy that achieves a balance between diversification and intensification. The performance of SSO‐TS is evaluated on the established Taillard benchmark suite. To assess the impact of hybridization, SSO‐TS is first compared with the original SSO algorithm. The results demonstrate that hybridizing SSO with TS significantly improves performance, achieving a 77% reduction in the average percentage error of the best‐obtained solution. SSO‐TS is then evaluated against four leading algorithms from previous research. The experimental results indicate that SSO‐TS outperforms three of the four with respect to solution quality. These findings validate the effectiveness of the proposed approach and establish SSO‐TS as an effective and competitive approach for solving the PFSP.