Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning

By Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, Chi Xu. Neural Information Processing Systems, 2020

463 citations recorded by the source corpus.

Priority dispatching rule (PDR) is widely used for solving real-world Job-shop scheduling problem (JSSP). However, the design of effective PDRs is a tedious task, requiring a myriad of specialized knowledge and often delivering limited performance. In this paper, we propose to automatically learn PDRs via an end-to-end deep reinforcement learning agent. We exploit the disjunctive graph representation of JSSP, and propose a Graph Neural Network based scheme to embed the states encountered during solving. The resulting policy network is size-agnostic, effectively enabling generalization on large-scale instances. Experiments show that the agent can learn high-quality PDRs from scratch with elementary raw features, and demonstrates strong performance against the best existing PDRs. The learned policies also perform well on much larger instances that are unseen in training.

Subfields: Computer Networks and Communications, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/d594764273c02b5a3bbdc4a8d49979a23ad1f125

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Industrial and Manufacturing Engineering

1. Wen Song
2. Qiqiang Li
3. Zhiguang Cao

Citations in the corpus

• Flexible Job-Shop Scheduling via Graph Neural Network and Deep Reinforcement Learning (2023, methodology): “This is because neural network inference is more costly than the simple rules employed by handcrafted PDRs, which is consistent with other works (see, e.g., [13] and [14]) and is reasonable considering the performance boost.”