A Modified Iterated Greedy Algorithm for Flexible Job Shop Scheduling Problem

Ghiath Al Aqel, Xinyu Li, Liang GaoChinese 2019 · DOI

Abstract

The Flexible Job Shop Scheduling Problem (FJSP) is a critical challenge in modern manufacturing, requiring the simultaneous optimization of machine assignment (routing) and operation ordering (sequencing). This paper proposes a Modified Iterated Greedy (MIG) algorithm that simplifies the scheduling process by decomposing it into two distinct phases. By utilizing a diverse set of dispatching rules for solution reconstruction, the MIG algorithm achieves high-quality results with significantly lower computational overhead than traditional metaheuristics. Experimental evaluations on standard benchmarks demonstrate that MIG frequently identifies global optima and offers superior speed, making it a practical tool for real-world production environments.

Introduction

In modern manufacturing systems, the Flexible Job Shop Scheduling Problem (FJSP) is a vital optimization hurdle. Unlike the standard Job Shop Problem, FJSP allows operations to be processed on any machine from a given set, adding a layer of complexity: one must decide not only the order of tasks (sequencing) but also which machine performs each task (routing).

Because FJSP is NP-hard, finding an absolute best schedule to minimize the "makespan" (total completion time) is computationally intensive. Existing solutions often fall into two categories: exact algorithms that are too slow for large-scale problems, and complex metaheuristics like Genetic Algorithms (GA) that are computationally expensive and difficult to implement. The MIG algorithm addresses these issues by providing a simpler, faster, and more reproducible metaheuristic.

The Modified Iterated Greedy (MIG) Algorithm

The authors build upon the Iterated Greedy (IG) framework, which improves solutions by iteratively "destructing" and "reconstructing" parts of a schedule. The MIG algorithm introduces two key innovations to optimize this process for flexibility.

Two-Phase Decomposition

Rather than treating the schedule as a single complex puzzle, the MIG algorithm splits the optimization into two distinct phases. This decomposition allows the algorithm to focus on routing and sequencing independently within the iterative loop.

Figure 1: Flowchart of the MIG algorithm showing the two-phase destruction and construction process.
  • Phase One: Focuses on the routing sub-problem, destructing and reconstructing machine assignments.
  • Phase Two: Focuses on the sequencing sub-problem, optimizing the order of operations on the assigned machines.

Construction via Dispatching Rules

During the reconstruction phase, the MIG algorithm employs a suite of Dispatching Rules (DRs). Instead of a fixed heuristic, the algorithm randomly selects from a pool of 10 online and 4 offline rules, such as Shortest Processing Time (SPT) or Earliest Finish (EF). This variety allows the algorithm to intelligently rebuild schedules while maintaining a balance between exploring new solutions and refining the current best.

Figure 2: Illustration of the machine selection process during the construction phase.

Key Results and Performance

The algorithm was evaluated against 35 well-known benchmark problems (Kacem, Fattahi, and Brandimarte datasets). The results highlight several key advantages:

  • Unmatched Speed: MIG consistently consumed the lowest CPU time. For instance, in the Kacem 15x10 benchmark, MIG required only 0.07 seconds, while a Hybrid Genetic Algorithm (hGA) took over 112 seconds.
  • Global Optimality: The algorithm found the global optimum for all small-scale instances and most medium-scale problems. In instances like MFJS01 and MFJS03, MIG outperformed all other algorithms currently found in the literature.
  • Scalability: While highly effective for small-to-medium problems, the algorithm occasionally encountered local optima in very large-scale scenarios, suggesting potential for further global search enhancements.

Conclusion

The Modified Iterated Greedy algorithm provides an efficient and easy-to-implement solution for the FJSP. By intelligently applying simple dispatching rules within a two-phase framework, it matches or exceeds the performance of much heavier algorithms while requiring a fraction of the processing time. Future research will explore applying this framework to multi-objective problems, such as minimizing both time and energy consumption on the shop floor.

Summary updated

Abstract

The flexible job shop scheduling problem (FJSP) is considered as an important problem in the modern manufacturing system. It is known to be an NP-hard problem. Most of the algorithms used in solving FJSP problem are categorized as metaheuristic methods. Some of these methods normally consume more CPU time and some other methods are more complicated which make them difficult to code and not easy to reproduce. This paper proposes a modified iterated greedy (IG) algorithm to deal with FJSP problem in order to provide a simpler metaheuristic, which is easier to code and to reproduce than some other much more complex methods. This is done by separating the classical IG into two phases. Each phase is used to solve a sub-problem of the FJSP: sequencing and routing sub-problems. A set of dispatching rules are employed in the proposed algorithm for the sequencing and machine selection in the construction phase of the solution. To evaluate the performance of proposed algorithm, some experiments including some famous FJSP benchmarks have been conducted. By compared with other algorithms, the experimental results show that the presented algorithm is competitive and able to find global optimum for most instances. The simplicity of the proposed IG provides an effective method that is also easy to apply and consumes less CPU time in solving the FJSP problem.
BibTeX
@inproceedings{aqel2019modified,
  author = {Ghiath Al Aqel and Xinyu Li and Liang Gao},
  title = {{A Modified Iterated Greedy Algorithm for Flexible Job Shop Scheduling Problem}},
  booktitle = {Chinese},
  year = {2019},
  doi = {10.1186/s10033-019-0337-7},
}
Figure