Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning

Longkang Li, Siyuan Liang, Zihao Zhu, Xiaochun Cao, Chris Ding, Hongyuan Zha, Baoyuan Wu

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.

Comparison between a feasible and an optimal permutation in PFSS, highlighting the impact on makespan.

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.

Architectural shift from sequence-based LSTM encoders to graph-based GGCN encoders.

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

Abstract

The permutation flow shop scheduling (PFSS), aiming at finding the optimal permutation of jobs, is widely used in manufacturing systems. When solving the large-scale PFSS problems, traditional optimization algorithms such as heuristics could hardly meet the demands of both solution accuracy and computational efficiency. Thus learning-based methods have recently garnered more attention. Some work attempts to solve the problems by reinforcement learning methods, which suffer from slow convergence issues during training and are still not accurate enough regarding the solutions. To that end, we train the model via expert-driven imitation learning, which accelerates the convergence more stably and accurately. Moreover, in order to extract better feature representations of input jobs, we incorporate the graph structure as the encoder. The extensive experiments reveal that our proposed model obtains significant promotion and presents excellent generalizability in large-scale problems with up to 1000 jobs. Compared to the state-of-the-art reinforcement learning method, our model's network parameters are reduced to only 37\% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8\% to 1.3\% on average.
BibTeX
@misc{li2022learning,
  author = {Longkang Li and Siyuan Liang and Zihao Zhu and Xiaochun Cao and Chris Ding and Hongyuan Zha and Baoyuan Wu},
  title = {{Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning}},
  year = {2022},
  eprint = {2210.17178},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2210.17178},
}
Figure