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

arXiv: https://arxiv.org/abs/2210.17178 · HTML: https://mlsanity.com/paper/2210.17178/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data.
- Builds on 20 of its 58 references that are in the map.
- First posted on arXiv 31 Oct 2022.

## Placed in

- Offline RL and imitation learning from data / [Offline RL algorithms](https://mlsanity.com/offlinerl/offline-rl-algorithms/)

## Builds on (most cited first, 20 of 20)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Learning to learn by gradient descent by gradient descent](https://mlsanity.com/paper/1606.04474/) (2016)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Behavioral Cloning from Observation](https://mlsanity.com/paper/1805.01954/) (2018)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Learning to Optimize](https://mlsanity.com/paper/1606.01885/) (2016)
- [Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances](https://mlsanity.com/paper/2012.10658/) (2020)
- [Recent Advances in Imitation Learning from Observation](https://mlsanity.com/paper/1905.13566/) (2019)
- [Deep Reinforcement Learning For Sequence to Sequence Models](https://mlsanity.com/paper/1805.09461/) (2018)
- [Revised Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks](https://mlsanity.com/paper/1706.07450/) (2017)
- [Augmented Behavioral Cloning from Observation](https://mlsanity.com/paper/2004.13529/) (2020)
- [Distributed Energy Trading and Scheduling among Microgrids via Multiagent Reinforcement Learning](https://mlsanity.com/paper/2007.04517/) (2020)
- [Learning to Accelerate Approximate Methods for Solving Integer Programming via Early Fixing](https://mlsanity.com/paper/2207.02087/) (2022)

## Built on by (most cited first, 10 of 10)

- [Unlearning Backdoor Threats: Enhancing Backdoor Defense in Multimodal Contrastive Learning via Local Token Unlearning](https://mlsanity.com/paper/2403.16257/) (2024)
- [Graph Neural Networks for Job Shop Scheduling Problems: A Survey](https://mlsanity.com/paper/2406.14096/) (2024)
- [Object Detectors in the Open Environment: Challenges, Solutions, and Outlook](https://mlsanity.com/paper/2403.16271/) (2024)
- [Deep reinforcement learning for machine scheduling: Methodology, the state-of-the-art, and future directions](https://mlsanity.com/paper/2310.03195/) (2023)
- [Leveraging Constraint Programming in a Deep Learning Approach for Dynamically Solving the Flexible Job-Shop Scheduling Problem](https://mlsanity.com/paper/2403.09249/) (2024)
- [Offline reinforcement learning for job-shop scheduling problems](https://mlsanity.com/paper/2410.15714/) (2024)
- [Continuous Vision-Language-Action Co-Learning with Semantic-Physical Alignment for Behavioral Cloning](https://mlsanity.com/paper/2511.14396/) (2025)
- [PersonaX: Multimodal Datasets with LLM-Inferred Behavior Traits](https://mlsanity.com/paper/2509.11362/) (2025)
- [Imitation Learning in the Deep Learning Era: A Novel Taxonomy and Recent Advances](https://mlsanity.com/paper/2511.03565/) (2025)
- [Transformer-Based Flow Shop Scheduling Using MILP-Generated Training Data](https://mlsanity.com/paper/2608.29690/) (2026)

## Abstract (arXiv)

The permutation flow shop scheduling (PFSS), aiming at finding the optimal permutation of jobs, is widely used in manufacturing systems. When solving 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 propose to train the model via expert-driven imitation learning, which accelerates 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. The code is available at: urlhttps://github.com/longkangli/PFSS-IL.