Solving the Flexible Flow Shop Problem via Deep Reinforcement Learning

Wang Jiening

Abstract

.The classic Flow Shop Scheduling Problem (FSP) and the Flexible Flow Shop Scheduling Problem (FFSP) are significant topics in the field of production scheduling, widely applied in manufacturing and logistics. However, traditional methods face challenges such as high computational complexity and difficulty in finding optimal solutions when dealing with large-scale and high-dimensional problems. To address these issues, this paper proposes an innovative solution based on Deep Reinforcement Learning (DRL) using the Deep Q-Network (DQN) algorithm, which effectively combines the powerful feature extraction capabilities of deep learning with the decision-making advantages of reinforcement learning.

This paper designs an efficient training framework that enhances the stability and convergence speed of the algorithm through prioritized experience replay and a dual-network structure. For the varying complexities of FSP and FFSP, corresponding network structures are constructed. Based on the FSP framework, Noisy Linear Layer and batch normalization techniques are introduced, and a Dueling DQN structure is adopted to better solve FFSP problems. For the classic flow shop scheduling problem, this paper uses the Gurobi solver as an exact lower bound to verify the accuracy of the DQN algorithm on medium and small-scale problems. For largescale problems, this paper has developed a two-stage lower bound estimation method based on machine slack and critical path, theoretically verifying the scalability of the DQN algorithm. For the flexible flow shop problem, this paper proposes a flexible encoding mechanism for the action space and designs a composite reward function that takes into account makespan, equipment utilization, and load balancing. Through this mechanism and reward function, the DQN algorithm can better adapt to the complexity of FFSP and optimize the scheduling plan. Experimental results show that the DQN algorithm demonstrates significant computational efficiency and scalability advantages in both small and large-scale problems of the classic and flexible flow shop models. These findings not only provide a new solution approach to the flow shop scheduling problem but also validate the effectiveness of the proposed method through experiments, providing important theoretical support for the wide application of deep reinforcement learning in industrial automation and intelligent manufacturing fields.