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

Chien Liang Liu*, Tzu Hsuan Huang

*此作品的通信作者

研究成果: Article同行評審

5 引文 斯高帕斯(Scopus)

摘要

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.

原文English
頁(從 - 到)6836-6848
頁數13
期刊IEEE Transactions on Systems, Man, and Cybernetics: Systems
53
發行號11
DOIs
出版狀態Published - 1 11月 2023

指紋

深入研究「Dynamic Job-Shop Scheduling Problems Using Graph Neural Network and Deep Reinforcement Learning」主題。共同形成了獨特的指紋。

引用此