Heuristics and Reinforcement Learning for Solving the Job Shop Scheduling Problem

Li Yanwen

Abstract

The purpose of this study is to solve the flexible job shop scheduling problem (FJSP): improve the scheduling efficiency of the flexible job shop, find a Markov decision process with the constraints of the flexible job shop scheduling problem, and propose a reinforcement learning method to solve the problem of simultaneous selection of workpiece and machine. In this paper, a solution method based on Q-learning is proposed. First, by modeling the FJSP problem, the processes are considered as states, and the coupling number is used to represent the state space, as well as to define the action space and reward function. Then, a specific application process of the Q-learning algorithm in FJSP is proposed, and the corresponding state transfer, action selection, and reward update strategies are designed. Subsequently, based on the proposed algorithm, the solution program for FJSP is implemented, and the effectiveness and performance of the algorithm are verified through simulation experiments. The algorithm solution results are demonstrated by visualization means such as drawing Gantt charts, which proves the potential and superiority of the method in solving the FJSP problem. Finally, the validity of the algorithm is verified in terms of multifaceted comparative experiments. The research results of this paper provide new ideas and methods for solving scheduling optimization problems in actual production and have certain theoretical and practical application value.