Abstract
The flexible job shop scheduling problem (FJSP) is a complex, NP-hard challenge prevalent in modern manufacturing. This paper presents a Multi-Swarm Collaborative Genetic Algorithm (MSCGA) designed to address FJSP by decomposing it into two sub-problems: machine selection (MS) and operation sorting (OS). By utilizing a multi-population structure and specialized genetic operators, the MSCGA facilitates independent yet collaborative evolution. Evaluation against standard benchmarks demonstrates the algorithm's superiority in achieving minimized makespans compared to existing methods.
Introduction
In the competitive landscape of manufacturing, optimizing the Flexible Job Shop Scheduling Problem (FJSP) is vital for efficiency. Unlike traditional job shop scheduling, FJSP allows operations to be processed on any machine from a set of alternatives, significantly expanding the search space. The problem requires solving two intertwined tasks: Machine Selection (MS)—assigning operations to machines—and Operation Sorting (OS)—sequencing those operations to minimize the total completion time, or makespan.
The MSCGA Framework
The proposed Multi-Swarm Collaborative Genetic Algorithm (MSCGA) departs from traditional "unified coding" approaches. Instead, it treats MS and OS as distinct but interacting components of an ecosystem.
Multi-Population Structure and Collaborative Evolution
The MSCGA maintains $N$ swarms for Machine Selection (one per job) and a single central swarm for Operation Sorting. Fitness evaluation is achieved through "collaborative evolution," where individuals from different swarms are randomly paired to form complete scheduling solutions. This interaction ensures that machine assignments and operation sequences evolve in tandem, preventing the algorithm from converging on suboptimal local solutions.
Specialized Genetic Operators
To maintain diversity and explore the search space effectively, the algorithm employs:
- Precedence Operation Crossover (POX): Used for the OS swarm to preserve the relative order of operations.
- Two-Point Crossover: Applied to MS swarms to efficiently swap machine assignments.
- Neighborhood Mutation: A local search technique for the OS swarm that fine-tunes sequences without disrupting the overall schedule structure.
Experimental Evaluation
The effectiveness of MSCGA was tested against 48 standard benchmarks, including the MK (Brandimarte), Peres, and Fattahi datasets. These benchmarks represent varying scales of complexity and are widely used to compare scheduling algorithms.
Results and Discussion
The MSCGA consistently outperformed or matched state-of-the-art algorithms across the tested datasets. In the MK data, it achieved the best results in 9 out of 10 problems, with a lower average error than competing methods. Similar success was observed in the Peres and Fattahi datasets, where MSCGA secured the best results in the majority of instances.
As shown in the Gantt charts generated by the algorithm, the resulting schedules exhibit high machine utilization and minimal idle time. This density directly translates to a reduced makespan, fulfilling the primary objective of the optimization.
Conclusion
The Multi-Swarm Collaborative Genetic Algorithm offers a robust solution for the FJSP by leveraging the strengths of co-evolutionary strategies. By separating machine selection and operation sorting into distinct populations, the algorithm achieves a more efficient search of the solution space. Future work will explore multi-objective optimization to incorporate real-world constraints such as energy consumption and tardiness alongside makespan minimization.
Summary updated