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

  • 2021-06-02 11:40:22
  • Junyoung Park, Jaehyeong Chun, Sang Hun Kim, Youngkook Kim, Jinkyoo Park
  • 0


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


Quick Read (beta)

loading the full paper ...