# Graph Neural Networks for Job Shop Scheduling Problems: A Survey

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 47 of its 132 references that are in the map.
- First posted on arXiv 20 Jun 2024.

## Builds on (most cited first, 30 of 47)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Dueling Network Architectures for Deep Reinforcement Learning](https://mlsanity.com/paper/1511.06581/) (2015)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [Explainability in Graph Neural Networks: A Taxonomic Survey](https://mlsanity.com/paper/2012.15445/) (2020)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Reinforcement learning](https://mlsanity.com/paper/2405.10369/) (2024)
- [An Introduction to Deep Reinforcement Learning](https://mlsanity.com/paper/1811.12560/) (2018)
- [Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning](https://mlsanity.com/paper/2010.12367/) (2020)
- [Explainable AI (XAI): A Systematic Meta-Survey of Current Challenges and Future Opportunities](https://mlsanity.com/paper/2111.06420/) (2021)
- [A Survey of Deep Meta-Learning](https://mlsanity.com/paper/2010.03522/) (2020)
- [Unsupervised Attributed Multiplex Network Embedding](https://mlsanity.com/paper/1911.06750/) (2019)
- [Matrix Encoding Networks for Neural Combinatorial Optimization](https://mlsanity.com/paper/2106.11113/) (2021)
- [Simulation-guided Beam Search for Neural Combinatorial Optimization](https://mlsanity.com/paper/2207.06190/) (2022)
- [MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts](https://mlsanity.com/paper/2405.01029/) (2024)
- [Towards Omni-generalizable Neural Methods for Vehicle Routing Problems](https://mlsanity.com/paper/2305.19587/) (2023)
- [Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learning](https://mlsanity.com/paper/2106.01086/) (2021)
- [Multi-Task Learning for Routing Problem with Cross-Problem Zero-Shot Generalization](https://mlsanity.com/paper/2402.16891/) (2024)
- [Combinatorial Optimization with Policy Adaptation using Latent Space Search](https://mlsanity.com/paper/2311.13569/) (2023)
- [ScheduleNet: Learn to solve multi-agent scheduling problems with reinforcement learning](https://mlsanity.com/paper/2106.03051/) (2021)

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

- [Rethinking Light Decoder-based Solvers for Vehicle Routing Problems](https://mlsanity.com/paper/2503.00753/) (2025)
- [Collaboration! Towards Robust Neural Methods for Routing Problems](https://mlsanity.com/paper/2410.04968/) (2024)
- [Offline Reinforcement Learning for Learning to Dispatch for Job Shop Scheduling](https://mlsanity.com/paper/2409.10589/) (2024)
- [Learning to Optimize Job Shop Scheduling Under Structural Uncertainty](https://mlsanity.com/paper/2601.21389/) (2026)
- [Neural Combinatorial Optimization for Stochastic Flexible Job Shop Scheduling Problems](https://mlsanity.com/paper/2412.14052/) (2024)
- [Generalizing Beyond Suboptimality: Offline Reinforcement Learning Learns Effective Scheduling through Random Solutions](https://mlsanity.com/paper/2509.10303/) (2025)
- [Mamba Meets Scheduling: Learning to Solve Flexible Job Shop Scheduling with Efficient Sequence Modeling](https://mlsanity.com/paper/2602.21546/) (2026)
- [Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Scheduling](https://mlsanity.com/paper/2603.02846/) (2026)
- [HGT-Scheduler: Deep Reinforcement Learning for the Job Shop Scheduling Problem via Heterogeneous Graph Transformers](https://mlsanity.com/paper/2603.06777/) (2026)
- [Towards Solving Polynomial-Objective Integer Programming with Hypergraph Neural Networks](https://mlsanity.com/paper/2603.19318/) (2026)
- [Bridging the Sim-to-Real Gap in Reinforcement Learning-Based Industrial Dispatching through Execution Semantics](https://mlsanity.com/paper/2605.29078/) (2026)
- [Neural Certificate Pricing for Combinatorial Optimization Problems](https://mlsanity.com/paper/2607.01185/) (2026)
- [Schedulable Job-Level Dependencies for Cause-Effect Chains via Graph Neural Networks](https://mlsanity.com/paper/2607.02624/) (2026)
- [Time-Lag-Aware Deep Reinforcement Learning for Flexible Job-Shop Scheduling in PPVC Module Factories](https://mlsanity.com/paper/2607.11725/) (2026)
- [Curriculum Learning with GNN-based Reinforcement Learning for Job Shop Scheduling](https://mlsanity.com/paper/2609.28085/) (2026)

## Abstract (arXiv)

Job shop scheduling problems (JSSPs) represent a critical and challenging class of combinatorial optimization problems. Recent years have witnessed a rapid increase in the application of graph neural networks (GNNs) to solve JSSPs, albeit lacking a systematic survey of the relevant literature. This paper aims to thoroughly review prevailing GNN methods for different types of JSSPs and the closely related flow-shop scheduling problems (FSPs), especially those leveraging deep reinforcement learning (DRL). We begin by presenting the graph representations of various JSSPs, followed by an introduction to the most commonly used GNN architectures. We then review current GNN-based methods for each problem type, highlighting key technical elements such as graph representations, GNN architectures, GNN tasks, and training algorithms. Finally, we summarize and analyze the advantages and limitations of GNNs in solving JSSPs and provide potential future research opportunities. We hope this survey can motivate and inspire innovative approaches for more powerful GNN-based approaches in tackling JSSPs and other scheduling problems.