Study On Deep Reinforcement Learning Algorithms Solving Open Shop Scheduling Problem

Open Shop Scheduling Problem is a typical combinatorial optimization problem,which has been widely studied in manufacturing,transportation,logistics and other fields.This kind of problem has complex constraints and huge solution space.Consequently,it is very difficult to acquire the optimal solutions.At present,most of the traditional algorithms obtain the suboptimal solutions based on specific rules or local search,which have great limitations and are only suitable for problems with specific distributions.In recent years,Deep Reinforcement Learning has shown strong applicability and scalability in solving all kinds of complex decision-making problems.Therefore,this paper solves Open Shop Scheduling Problem based on Deep Reinforcement Learning.The main work of this paper is as follows:A Deep Reinforcement Learning algorithm based on actor-critic network is designed and implemented to solve Open Shop Scheduling Problem.Firstly,the strategy of constructing graph is used to simplify the input and output scheduling scheme of Open Shop Scheduling Problem.The input graph can accurately describe the characteristics of the problem and the relationship between the operations,and the output graph can directly reflect the constraints and temporal relation of the problem.In order to realize modeling graph structure via Deep Reinforcement Learning,the construction process of the output graph is serialized,and the dynamic programming algorithm is designed to calculate the makespan of the scheduling scheme.Then,the state,action and reward of Open Shop Scheduling Problem are analyzed from the perspective of Reinforcement Learning,and a Deep Reinforcement Learning framework of model based on actor-critic network is proposed.In order to better explore the deep information and representation problem model,two neural networks based on attention mechanism are optimized: Pointer Attention Network and Graph Attention Network.The proposed model is compared with traditional algorithms,and experiments are carried out on randomly generated Open Shop Scheduling Problem of different scales.The experimental results verify the effectiveness of the proposed models.In order to further optimize the algorithm,this paper proposes an attention model based on Discount Memory.By analyzing the characteristics of Open Shop Scheduling Problem and the principle of Graph Attention Network,it is found that attention mechanism pays too much attention to the previous output or fixed historical decisions.However,in complex Open Shop Scheduling Problem,some historical decisions with special significance are quite critical.Discount Memory focuses on both time and relevance,which can assist attention mechanism to explicitly model the relationship between historical decisions and current decision.The ablation experiments and baseline comparison experiments,which are evaluated from solution quality and calculation cost,are carried out to verify the effectiveness of Discount Memory.The experimental results show that the model is significantly improved after the increase of Discount Memory.And the model also shows practical value in solving real-time scheduling problems.