A Two-Individual Based Evolutionary Algorithm for the Flexible Job Shop Scheduling Problem

Junwen Ding, Zhipeng Lü, Chu-Min Li, Liji Shen, Liping Xu, Fred W. GloverAAAI 2019 · DOI

Abstract

The Flexible Job Shop Scheduling Problem (FJSP) is a notoriously difficult combinatorial optimization problem. Traditional Evolutionary Algorithms (EAs) often struggle with high computational overhead due to large population management. This paper presents the Master-Apprentice Evolutionary Algorithm (MAE), a lean framework that utilizes only two individuals to maintain genetic diversity and drive search efficiency. By combining a novel distance-based path relinking operator with tabu search, MAE significantly outperforms existing methods, establishing 10 new world records and improving best-known results for 47 benchmark instances.

Introduction

The Flexible Job Shop Scheduling Problem (FJSP) extends the classical job shop scheduling problem by allowing operations to be processed on any machine from a set of candidates, often with varying processing times. The objective is to minimize the makespan—the total time required to complete all jobs. Given its strongly NP-hard nature, FJSP presents a significant challenge for optimization algorithms. While population-based metaheuristics like EAs are commonly used, they often suffer from slow convergence and high complexity in managing large sets of potential solutions.

The Master-Apprentice Evolutionary Algorithm (MAE)

The core innovation of this work is the Master-Apprentice Evolutionary Algorithm (MAE), which simplifies the evolutionary process by maintaining only two solutions ($S_1$ and $S_2$). This "Master-Apprentice" duo reduces the overhead associated with large populations while focusing the search on high-quality regions of the solution space.

The Master-Apprentice Evolutionary Algorithm (MAE) framework showing the evolutionary cycle and generation steps.

Key Components

  1. Path Relinking: Instead of traditional crossover, MAE uses path relinking to generate intermediate solutions between $S_1$ and $S_2$. This operator explores the "path" connecting two solutions by making feasible changes, ensuring that offspring remain valid schedules without requiring complex repair mechanisms.
  2. Distance Metric: A unique distance definition was developed to unify machine assignment and operation sequencing, allowing the path relinking operator to navigate the FJSP search space effectively.
  3. Tabu Search: To intensify the search, a tabu search procedure is applied to the solutions generated by path relinking, exploring local neighborhoods for further improvements.
  4. Evolutionary Cycles: The process is organized into cycles of $p$ generations. At the end of each cycle, the "apprentice" solution is reset based on the "master" (the best-found solution), preventing search drift and incorporating historical bests into the ongoing evolution.

Experimental Evaluation

The MAE was evaluated on 313 public benchmark instances, including the DPdata, BCdata, BRdata, and HUdata sets. These benchmarks cover a wide range of problem sizes and flexibility levels.

Performance Results

MAE demonstrated exceptional performance compared to state-of-the-art metaheuristics and industrial solvers. It established 10 new world records for challenging instances and matched or improved best-known results for nearly all 313 test cases.

Comparison of makespan results between MAE and ITS across various benchmark instances.

Notably, MAE proved to be highly efficient, often finding superior solutions in a fraction of the time required by commercial solvers like the IBM ILOG CP Optimizer. For instance, MAE frequently outperformed the CP Optimizer's 8-hour results within just one hour of computation.

Conclusion

The Master-Apprentice Evolutionary Algorithm represents a paradigm shift in population-based optimization for FJSP. By demonstrating that a population of just two individuals can outperform much larger ensembles, this work highlights the importance of efficient search operators and structured memory over sheer population size. Future research will explore the application of the MAE framework to other complex combinatorial problems and further investigate the theoretical properties of two-individual evolution.

Summary updated

BibTeX
@inproceedings{ding2019two,
  author = {Junwen Ding and Zhipeng Lü and Chu-Min Li and Liji Shen and Liping Xu and Fred W. Glover},
  title = {{A Two-Individual Based Evolutionary Algorithm for the Flexible Job Shop Scheduling Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33012262},
}
Figure