摘要
This paper presents an end-to-end deep reinforcement framework to automatically learn a policy for solving a flexible Job-shop scheduling problem (FJSP) using a graph neural network. In the FJSP environment, the reinforcement agent needs to schedule an operation belonging to a job on an eligible machine among a set of compatible machines at each timestep. This means that an agent needs to control multiple actions simultaneously. Such a problem with multi-actions is formulated as a multiple Markov decision process (MMDP). For solving the MMDPs, we propose a multi-pointer graph networks (MPGN) architecture and a training algorithm called multi-Proximal Policy Optimization (multi-PPO) to learn two sub-policies, including a job operation action policy and a machine action policy to assign a job operation to a machine. The MPGN architecture consists of two encoder-decoder components, which define the job operation action policy and the machine action policy for predicting probability distributions over different operations and machines, respectively. We introduce a disjunctive graph representation of FJSP and use a graph neural network to embed the local state encountered during scheduling. The computational experiment results show that the agent can learn a high-quality dispatching policy and outperforms handcrafted heuristic dispatching rules in solution quality and meta-heuristic algorithm in running time. Moreover, the results achieved on random and benchmark instances demonstrate that the learned policies have a good generalization performance on real-world instances and significantly larger scale instances with up to 2000 operations.
学科与关键词
- An end-to-end deep reinforcement learning method based on graph neural network for distributed job-shop scheduling problemHuang, Jiang-Ping; Gao, Liang; Li, Xin-Yu*EXPERT SYSTEMS WITH APPLICATIONS, 2024, 238: 121756.被引 13
- Solving flexible job shop scheduling problems via deep reinforcement learningYuan, Erdong; Wang, Liejun*; Cheng, Shuli; Song, Shiji; Fan, Wei; Li, YongmingEXPERT SYSTEMS WITH APPLICATIONS, 2024, 245: 123019.被引 11
- Multi-policy deep reinforcement learning for multi-objective multiplicity flexible job shop schedulingDing, Linshan; Guan, Zailin; Rauf, Mudassar; Yue, Lei*Swarm and Evolutionary Computation, 2024, 87: 101550.被引 9
