Abstract
Permutation Flow Shop Scheduling (PFSS) is a fundamental NP-hard problem in manufacturing that involves determining the optimal sequence of jobs across multiple machines to minimize the total completion time, or makespan. While Reinforcement Learning (RL) has been applied to this domain, it often suffers from slow convergence and inadequate feature representation. This paper introduces PFSS-IL, a framework that combines Gated Graph ConvNets (GGCN) with expert-driven imitation learning. By treating jobs as nodes in a graph and training the model to mimic the well-established NEH heuristic, the authors developed a model that is 63% smaller than state-of-the-art RL baselines and reduces the solution gap from 6.8% to just 1.3%.
The Permutation Flow Shop Scheduling Problem
In a typical PFSS scenario, a set of jobs must be processed through a series of machines in the same order. The primary objective is to find a permutation of these jobs that minimizes the makespan—the time elapsed from the start of the first job on the first machine to the completion of the last job on the final machine.
Finding the optimal permutation is computationally intensive because the search space grows factorially with the number of jobs ($n!$). Traditional heuristics, such as the NEH algorithm, provide reasonable solutions but can become computationally expensive at scale.
As shown in the figure above, different job sequences result in varying amounts of machine idle time, directly impacting the final makespan. An optimal schedule minimizes these gaps, ensuring maximum machine utilization.
Methodology: Graph-based Imitation Learning
The proposed PFSS-IL model addresses the limitations of previous deep learning approaches through two key innovations:
1. Graph-based Feature Representation
Most existing neural schedulers use sequence models like LSTMs to encode job information. However, LSTMs treat jobs as an ordered list, failing to explicitly capture the relative differences in processing times between jobs—a critical factor in scheduling efficiency.
PFSS-IL employs Gated Graph ConvNets (GGCN) to embed job features. In this graph representation, each job is a node, and edges represent the differences in processing times between jobs. This allows the model to learn a richer representation of how swapping specific jobs affects machine idle time.
2. Behavioral Cloning from Expert Heuristics
Instead of using Reinforcement Learning, which requires an agent to learn from scratch through trial and error, the authors utilize Imitation Learning (IL). Specifically, they use Behavioral Cloning to train the network to mimic the decisions of the NEH heuristic. This approach provides a stable and high-quality training signal, leading to significantly faster convergence—reaching peak performance in 10–20 epochs compared to the 40–50 epochs typically required by RL methods.
Experimental Results
The model was rigorously tested on standard benchmarks (Taillard and VRF) and large-scale generated datasets. The results demonstrate substantial improvements over RL-based pointer networks:
- Model Efficiency: The PFSS-IL architecture is highly compact, requiring only 37% of the parameters used by leading RL models.
- Solution Quality: The gap between the model's output and the expert solution was reduced from 6.8% (RL) to 1.3% (IL).
- Inference Speed: While the NEH heuristic can take nearly an hour to solve problems with 1,000 jobs, the neural network generates high-quality solutions in a matter of seconds.
- Generalization: A model trained on small instances (e.g., 20 jobs) generalizes effectively to much larger problems (up to 1,000 jobs), proving that the learned scheduling logic is scale-invariant.
Conclusion and Future Work
PFSS-IL demonstrates that for combinatorial optimization problems where strong heuristics already exist, imitation learning combined with graph-based encoders is superior to traditional RL. By focusing on the relationships between jobs rather than absolute processing times, the model achieves state-of-the-art performance with a fraction of the computational overhead.
However, the current approach is limited by the "expert ceiling," as behavioral cloning prevents the model from significantly outperforming the NEH heuristic it mimics. Future research will explore advanced imitation learning techniques, such as Learning from Observations, to potentially surpass the performance of existing expert heuristics. Additionally, extending the model to handle varying numbers of machines remains an open challenge for future development.
Summary updated