Iterated Tabu Search Enhanced Particle Swarm Optimization for the Multi-Stage Flexible Job Shop Scheduling Problem

In recent years, with the advancement of production technology in the manufacturing industry, the scheduling problems that rely on modeling in real-world scenarios have gradually evolved into complex process flows. Aiming at the limited problem modeling capabilities of existing scheduling problems, this study proposes Multi-Stage Flexible Job Shop Scheduling Problem (MS-FJSP). MS-FJSP alters the fixed operation processing sequence of jobs in conventional scheduling problems and introduces staged processing to incorporate flexible constraints on operation selection. Furthermore, MS-FJSP modifies the constraint of unique machine compatibility, enabling arbitrary adjustments to machine combinations according to processing requirements. To address the complex flexibility and large-scale solution space of MS-FJSP, we propose a particle swarm optimization algorithm based on double neighborhood tabu search (TS-PSO). Specifically, the PSO algorithm determines a superior neighborhood structure for this problem, while the TS algorithm improves and optimizes the solution quality within the neighborhood of this solution structure. We verify the algorithm’s performance using a dataset consisting of 12,000 MS-FJSP instances and an MS-FJSP instance modeled from a real-world scheduling scenario. Experimental results demonstrate that TS-PSO can achieve excellent solution quality within a reasonable time, and MS-FJSP possesses efficient modeling capability for real-world scheduling scenarios.