Reproduce “Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learning” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Junyoung Park, Jaehyeong Chun, Sang Hun Kim, Youngkook Kim, Jinkyoo Park

The paper presents a graph neural network reinforcement-learning scheduler for job-shop problems. It represents operations through job-order and shared-machine relationships, then uses a learned policy to select feasible operations. Trained on random small instances, it usually beat priority rules on unseen benchmarks, with errors of 12.6% to 20.9%, but required more computation and optimized composite rules were not compared.

Key insights

  • Representing JSSP states as dynamic disjunctive graphs allows the GNN to learn and embed complex structural and temporal relationships, leading to more robust and generalizable state representations.
  • The end-to-end GNN-RL framework can learn a transferable scheduling policy that effectively generalizes to diverse, unseen JSSP instances (varying in size and characteristics) without requiring specific retraining.
  • An efficient MDP formulation that focuses on 'non-trivial states' and a reward function based on the number of waiting jobs provides frequent and meaningful signals, contributing to stable and effective RL training for makespan minimization.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.