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 favored 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.

arXiv comment16 pages, 8 figures

References in corpus (11)

• Adam: A Method for Stochastic Optimization
• Playing Atari with Deep Reinforcement Learning
• Trust Region Policy Optimization
• Learning Combinatorial Optimization Algorithms over Graphs
• How Powerful are Graph Neural Networks?
• Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
• Graph networks as learnable physics engines for inference and control
• Learning Heuristics over Large Graphs via Deep Reinforcement Learning
• Learning the Multiple Traveling Salesmen Problem with Permutation Invariant Pooling Networks
• Differentiable Physics-informed Graph Networks
• GLoMo: Unsupervisedly Learned Relational Graphs as Transferable Representations

Cited by in corpus (6)

• Deep reinforcement learning for machine scheduling: Methodology, the state-of-the-art, and future directions
• Introducing PetriRL: An Innovative Framework for JSSP Resolution Integrating Petri nets and Event-based Reinforcement Learning
• ScheduleNet: Learn to solve multi-agent scheduling problems with reinforcement learning
• Learning to Control Local Search for Combinatorial Optimization
• Optimal Solving of Constrained Path-Planning Problems with Graph Convolutional Networks and Optimized Tree Search
• Scalable Verification of GNN-based Job Schedulers