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.
본 논문은 그래프 심층 신경망과 강화학습을 활용해 잡샵 스케쥴링 문제를 푸는 그래프 심층 신경망 스케쥴러를 제안한다. 먼저, 잡샵 스케쥴링 문제를 그래프 형태의 상태로 표현하고 순차적 의사결정 문제로 변환한다. 이후 그래프로 표현된 잡샵 스케쥴링 문제의 공간적 구조를 그래프 심층 신경망을 통해 학습하고 스케쥴링 정책을 도출해낸다. 이 때 강화학습을 통해 신경망의 학습을 진행함으로써 스케쥴링 문제의 시간적 구조를 반영한다. 제안한 그래프 심층 신경망 스케쥴러는 일반화 능력을 가지고 있어 추가적인 학습 없이도 새로운 잡샵 스케쥴링 문제 적용했을 때 일반적으로 사용하는 우선 순위 스케쥴링 규칙과 기존의 강화학습 기반의 스케쥴러를 능가함을 확인하였다.