Solving flexible job shop scheduling problem by a multi-swarm collaborative genetic algorithm

Cuiyu Wang, Yang Li, Xinyu LiJournal of Systems Engineering and Electronics 2021 · DOI

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.

Flowchart of the Multi-Swarm Collaborative Genetic Algorithm (MSCGA) process.

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.

Gantt chart representation of an optimized schedule for a benchmark problem, showing minimized makespan and high machine utilization.

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

Abstract

The flexible job shop scheduling problem (FJSP), which is NP-hard, widely exists in many manufacturing industries. It is very hard to be solved. A multi-swarm collaborative genetic algorithm (MSCGA) based on the collaborative optimization algorithm is proposed for the FJSP. Multi-population structure is used to independently evolve two sub-problems of the FJSP in the MSCGA. Good operators are adopted and designed to ensure this algorithm to achieve a good performance. Some famous FJSP benchmarks are chosen to evaluate the effectiveness of the MSCGA. The adaptability and superiority of the proposed method are demonstrated by comparing with other reported algorithms.
BibTeX
@article{wang2021solving,
  author = {Cuiyu Wang and Yang Li and Xinyu Li},
  title = {{Solving flexible job shop scheduling problem by a multi-swarm collaborative genetic algorithm}},
  journal = {Journal of Systems Engineering and Electronics},
  year = {2021},
  doi = {10.23919/jsee.2021.000023},
}
Figure