Journal
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH
Volume 59, Issue 11, Pages 3360-3377Publisher
TAYLOR & FRANCIS LTD
DOI: 10.1080/00207543.2020.1870013
Keywords
Scheduling; job shop scheduling problem; JSSP; graph neural network; reinforcement learning
Ask authors/readers for more resources
The proposed framework utilizes GNN and RL to learn a solution for JSSP scheduling problem, demonstrating its superiority over traditional dispatching rules and RL schedulers. The learned policy from the framework exhibits strong generalization capabilities, performing well on new JSSP instances.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available