.png){kind=icon}
.png){kind=icon}
Return
Evolution strategies-based optimized graph reinforcement learning for solving dynamic job shop scheduling problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.asoc.2023.110596.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The job shop scheduling problem (JSSP) with dynamic events and uncertainty is a strongly NP-hard combinatorial optimization problem (COP) with extensive applications in the manufacturing system. Recently, growing interest has been aroused in utilizing machine learning techniques to solve the JSSP. However, most prior arts cannot handle dynamic events and barely consider uncertainties. To close this gap, this paper proposes a framework to solve a dynamic JSSP (DJSP) with machine breakdown and stochastic processing time based on Graph Neural Network (GNN) and deep reinforcement learning (DRL). To this end, we first formulate the DJSP as a Markov Decision Process (MDP), where disjunctive graph represent the states. Secondly, we propose a GNN-based model to effectively extract the embeddings of the state by considering the features of the dynamic events and the stochasticity of the problem, e.g., the machine breakdown and stochastic processing time. Then, the model constructs solutions by dispatching optimal operations to machines based on the learned embeddings. Notably, we propose to use the evolution strategies (ES) to find optimal policies that are more stable and robust than conventional DRL algorithms. The extensive experiments show that our method substantially outperforms existing reinforcement learning-based and traditional methods on multiple classic benchmarks.& COPY; 2023 Elsevier B.V. All rights reserved.
Keywords:
Evolution strategies
Graph neural network
Graph reinforcement learning
Job shop scheduling
Reinforcement learning
Journal
IF:
6.6
Papers:
1.4W
Citations:
4.8W
Organization
View more organizations