TY - JOUR
T1 - Graph neural networks for job shop scheduling problems
T2 - A survey
AU - Smit, Igor G.
AU - Zhou, Jianan
AU - Reijnen, Robbert
AU - Wu, Yaoxin
AU - Chen, Jian
AU - Zhang, Cong
AU - Bukhsh, Zaharah
AU - Zhang, Yingqian
AU - Nuijten, Wim P.M.
N1 - Publisher Copyright:
© 2024 The Author(s)
PY - 2025/4
Y1 - 2025/4
N2 - 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.
AB - 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.
KW - Combinatorial optimization
KW - Deep reinforcement learning
KW - Flow-shop scheduling
KW - Graph neural network
KW - Job shop scheduling
UR - http://www.scopus.com/inward/record.url?scp=85211045949&partnerID=8YFLogxK
U2 - 10.1016/j.cor.2024.106914
DO - 10.1016/j.cor.2024.106914
M3 - Review article
AN - SCOPUS:85211045949
SN - 0305-0548
VL - 176
JO - Computers and Operations Research
JF - Computers and Operations Research
M1 - 106914
ER -