Reinforcement-learning Based Optimization Algorithms For The Flexible Job Shop Scheduling Problem

The job shop scheduling problem(Job Shop Scheduling Problem,FJSP)is one of the most classical combinatorial optimization problems and is proved to be NP-hardness.In today’s industrial manufacturing environment,in order to be more in line with the actual production environment,the problem is extended to the flexible job shop scheduling problem(Flexible Job Shop Scheduling Problem,FJSP)which allows an operation to be completed on several machines.At present,the algorithms for solving FJSP are mainly based on intelligent algorithms such as genetic algorithm.With successful application of reinforcement learning(RL)in artificial intelligence,it has become a research hotspot recently.In this paper,We tries to use RL to solve FJSP.By description of scheduling state,designing scheduling rules and rewards,composite dispatching stragety is constructed to improve the efficiency and performance of solving FJSP.The main work of this paper includes the following four aspects:(1)After deep research of machine learning,we propose an overall RL-based framework of constructing composite strategy for FJSP in this paper.(2)Combining with the framework,we propose a round-updating algorithm based on soft policy for solving FJSP and defined the state,action and reward used in the algorithm.Moreover,we analysize the time complexity of the algorithm.(3)The round-updating algorithm based on soft policy for solving FJSP relies on state-action list.If there are too many states,the scale of list will be very large,thus having a serious effect on the efficiency of this algorithm.The neural network is introduced to solve this problem.Seven features are extracted as the input of network to deal with more complicated states,policy gradient is used to train the network parameter,thus imporving the strategy.(4)In this paper,we implement the proposed algorithms and compare them with other algorithms in classical FJSP instances.We compare the time complexity and peformance of sloving FJSP.The experiment results verfy the feasibility of RL in solving FJSP.