Dynamic Job-Shop Scheduling Problems Using Graph Neural Network and Deep Reinforcement Learning

Chien Liang Liu*, Tzu Hsuan Huang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

23 Scopus citations

Abstract

The job-shop scheduling problem (JSSP) is one of the best-known combinatorial optimization problems and is also an essential task in various sectors. In most real-world environments, scheduling is complex, stochastic, and dynamic, with inevitable uncertainties. Therefore, this article proposes a novel framework based on graph neural networks (GNNs) and deep reinforcement learning (DRL) to deal with the dynamic JSSP (DJSSP) with stochastic job arrivals and random machine breakdowns by minimizing the makespan. In the proposed framework, JSSP is formulated as a Markov decision process (MDP) and is associated with a disjunctive graph to encode the information of jobs and machines as nodes and arcs. We propose a GNN architecture to perform representation learning by transforming graph states into node embeddings. Then, the agent takes actions using a parameterized policy in terms of policy learning. Operations are used as actions, and an effective reward is well designed to guide the agent. We train our proposed method using proximal policy optimization (PPO), which helps minimize the loss function while ensuring that the deviation is relatively small. Extensive experiments show that the proposed method can achieve excellent results considering different criteria: efficiency, effectiveness, robustness, and generalizability. Once the proposed method is trained, it can directly schedule new JSSPs of different sizes and distributions in static benchmark tests, showing its excellent generalizability and effectiveness compared to another DRL-based method. Furthermore, the proposed method simultaneously maintains the win rate (a quantitative metric) and the scheduling score (a qualitative metric) when scheduling in dynamic environments.

Original languageEnglish
Pages (from-to)6836-6848
Number of pages13
JournalIEEE Transactions on Systems, Man, and Cybernetics: Systems
Volume53
Issue number11
DOIs
StatePublished - 1 Nov 2023

Keywords

  • Deep reinforcement learning (DRL)
  • dynamic scheduling
  • graph neural network (GNN)
  • job-shop scheduling problem (JSSP)
  • real-time scheduling

Fingerprint

Dive into the research topics of 'Dynamic Job-Shop Scheduling Problems Using Graph Neural Network and Deep Reinforcement Learning'. Together they form a unique fingerprint.

Cite this