Graph-Based Imitation Learning for Real-Time Job Shop Dispatcher

We propose an advanced real-time dispatcher for minimizing the makespan of job shop scheduling problems (JSSPs), which are NP-hard combinatorial problems. The proposed dispatcher can be applied to large-sized unseen problems without additional learning. Several studies recently proposed a scalable dispatching agent using a graph neural network (GNN) and reinforcement learning (RL). However, we observe that they have not considered suitable Markov decision process (MDP) and GNN structure to solve JSSPs. Therefore, we incorporate scheduling theory and properties to define the state, action, and GNN model. We especially define the action set and state transition so that active schedules can be exclusively generated, define node features in a dynamic manner, and use a neighbor type-aware Graph Attention Network (GAT) model with length-agnostic neighbor sets. We also investigate the use of imitation learning (IL) to learn the dispatcher instead of the RL. We evaluate the effectiveness of our dispatcher on benchmark instances and dynamic environments. Note to Practitioners—This work aims to develop an advanced real-time dispatcher using GNN. It can handle dynamic scheduling environments. The focus is on JSSPs without constraints, commonly seen in real manufacturing systems. To improve the GNN-based dispatchers proposed by recent studies, we refine the dispatcher using a novel state, action, and a GNN structure. Our dispatcher demonstrates state-of-the-art performance compared to other real-time dispatchers on JSSP benchmark instances and several customized instances, which consist of up to 20 machines and 300 jobs. Additionally, we assess the dispatcher’s performance in dynamic JSSP environments, including dynamic job arrival, machine breakdown, and stochastic processing time. Note that, to apply the proposed dispatcher for real-world fields, you have to prepare only the information about predefined machine orders and currently remaining processing times for each job. Also, you do not need a simulator if you are going to utilize a trained dispatcher. In the future, extended study is needed to apply it to sequence-dependent setup constraints, due-related objectives, etc.