Learning to schedule job-shop problems: representation and policy learning using graph neural network and reinforcement learning

Abstract

We propose a framework to learn to schedule a job-shop problem (JSSP) using a graph neural network (GNN) and reinforcement learning (RL). We formulate the scheduling process of JSSP as a sequential decision-making problem with graph representation of the state to consider the structure of JSSP. In solving the formulated problem, the proposed framework employs a GNN to learn that node features that embed the spatial structure of the JSSP represented as a graph (representation learning) and derive the optimum scheduling policy that maps the embedded node features to the best scheduling action (policy learning). We employ Proximal Policy Optimization (PPO) based RL strategy to train these two modules in an end-to-end fashion. We empirically demonstrate that the GNN scheduler, due to its superb generalization capability, outperforms practically favoured dispatching rules and RL-based schedulers on various benchmark JSSP. We also confirmed that the proposed framework learns a transferable scheduling policy that can be employed to schedule a completely new JSSP (in terms of size and parameters) without further training.

Keywords:

• Scheduling
• job shop scheduling problem
• JSSP
• graph neural network
• reinforcement learning

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 When multiple machines are available at tth transition, we randomly sample the machine such that a transition always loads an operation to a machine and we increment transition index t

2 We overload the notation of action $a_{\tau }$ as $a_{\tau }^v$ to clearly show that the action is ‘selecting the node v’.

3 Refer the webpage https://pypi.org/project/pyjssp

4 ReLU network is a standard building block for complex neural networks. Choosing $2^n$ numbered hidden layers is also standard practice in the deep learning community. Similarly, we set the dimension of hidden node embedding as $2^3$. We tested deeper and thicker ReLU networks while finding the best hyperparameters. The deep and thick ReLU networks than the specified hyperparameter setup did not improve scheduling performance.

Additional information

Funding

This work was supported by Samsung [G01190084].

Notes on contributors

Junyoung Park

Junyoung Park received the B.S degree in Industrial and Systems engineering (ISysE), and Business and Technology Management from the Korea Advanced Institute of Science and Technology (KAIST), Daejeon, South Korea, in 2016. Since 2017, he has been working towards the mater's and Ph.D. degree in ISysE from KAIST. His research interests include modelling and analysing of large-scale engineering systems with machine learning technics and their application to controls.

Jaehyeong Chun

Jaehyeong Chun received the B.S. degree in industrial systems and engineering from the Korea Advanced Institute of Science and Technology, Daejeon, South Korea, in 2018, the M.S. degree in industrial systems and engineering from the Korea Advanced Institute Science and Technology, Daejeon, South Korea, in 2020. Since 2020, He is attending Gachon university college of medicine, Incheon, South Korea. His research interests include systematic modelling for medical systems and application of machine learning technique to medical fields.

Sang Hun Kim

Sang Hun Kim received the B.S. degree in chemical engineering from Kyungpook National University, Daegu, South Korea, in 2004, the M.S. and Ph.D. degrees in chemical and biomolecular engineering from Korea Advanced Institute of Science and Technology, Daejeon, South Korea, in 2010. He is currently a Principal Engineer of Samsung Electronics, Hwaseong, South Korea. His research interests include modelling and simulation of manufacturing scheduling system by using mathematical optimization, and machine learning technologies.

Youngkook Kim

Youngkook Kim received the B.S. degree in semiconductor engineering from Samsung Institute of Technology, Hwaseong, South Korea, in 2013. He is currently a Principal Engineer of Samsung Electronics, Hwaseong, South Korea. His research interests include operation and management of scheduling system for semiconductor manufacturing.

Jinkyoo Park

Jinkyoo Park is currently an assistant professor of Industrial and Systems Engineering at Korea Advanced Institute of Science and Technology (KAIST), Republic of Korea. He received his B.S. degree in Civil and Architectural Engineering from Seoul National University in 2009, an M.S. degree in Civil, Architectural and Environmental Engineering from the University of Texas Austin in 2011, a M.S. degree in Electrical Engineering from Stanford University in 2015, and a Ph.D. degree in Civil and Environmental Engineering from Stanford University in 2016. He develops various AI-based decision-making algorithms for multi-agent systems and employs these algorithms for monitoring and controlling the smart factory, smart city, and smart grid systems.