Discrete state transfer algorithm based on deep reinforcement learning for solving flexible job shop scheduling problem

Abstract

Flexible Job Shop Scheduling (FJSP) is a scheduling problem widely used in real life. The research on its intelligent algorithm has important academic significance and application value. In order to solve FJSP, this paper proposes a discrete state transfer algorithm based on proximal policy optimization (DSTA-PPO) with the optimization goal of minimizing the maximum completion time. DSTA-PPO has the following three characteristics: (1) Considering that FJSP requires simultaneous scheduling of process sorting and machine allocation, a state feature that can fully express the current scheduling problem is designed by combining process coding and machine coding. (2) A variety of critical path-based search operations are designed for process sorting and machine allocation. (3) Through reinforcement learning training, it can effectively guide the agent to select the correct search operation to optimize the current scheduling sequence. Through simulation experiments based on different data sets, the effectiveness of each link of the algorithm was verified. At the same time, it was compared with the existing algorithms on the same example with minimizing the maximum completion time. The comparison results show that the proposed algorithm can solve the examples in most examples with a shorter completion time, and effectively solve the flexible job shop scheduling problem.