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.
- 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.
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