Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learning
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Decision MakingGraph Neural NetworkGraph Representation LearningReinforcement Learning (RL)Representation LearningSchedulingSequential Decision MakingMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
ScheduleNet: Learn to solve multi-agent scheduling problems with reinforcement learning
We propose ScheduleNet, a RL-based real-time scheduler, that can solve various types of multi-agent scheduling problems. We formulate these problems as a semi-MDP with episodic reward (makespan) and learn ScheduleNet, a …
Decision MakingGraph AttentionJob Shop Schedulingreinforcement-learning+2Graph neural networks-based Scheduler for Production planning problems using Reinforcement Learning
Reinforcement learning (RL) is increasingly adopted in job shop scheduling problems (JSSP). But RL for JSSP is usually done using a vectorized representation of machine features as the state space. It has three major pro…
Distributed OptimizationGraph Neural NetworkJob Shop Schedulingreinforcement-learning+2Variational Approach for Job Shop Scheduling
This paper proposes a novel Variational Graph-to-Scheduler (VG2S) framework for solving the Job Shop Scheduling Problem (JSSP), a critical task in manufacturing that directly impacts operational efficiency and resource u…
Zero-shot GeneralizationRepresentation LearningReinforcement LearningUnraveling the Rainbow: can value-based methods schedule?
Recently, deep reinforcement learning has emerged as a promising approach for solving complex combinatorial optimization problems. Broadly, deep reinforcement learning methods fall into two categories: policy-based and v…
Atari GamesCombinatorial OptimizationDeep Reinforcement LearningJob Shop Scheduling+3HGT-Scheduler: Deep Reinforcement Learning for the Job Shop Scheduling Problem via Heterogeneous Graph Transformers
The Job Shop Scheduling Problem (JSSP) is commonly formulated as a disjunctive graph in which nodes represent operations and edges encode technological precedence constraints as well as machine-sharing conflicts. Most ex…
Reinforcement Learning