Research On Branch&Price And Reinforcement Learning Algorithm For Resource-Constrained Project Scheduling Problem

Resource-constrained project scheduling problem(RCPSP)is one of the most representative project scheduling problems.It is an abstract representation of many practical scheduling problems,such as workshop processing,construction scheduling,and so on.How to shorten the solution time and improve the solution quality has become a long-term demand of the industry.At present,although the method based on column generation has high solving ability,it cannot guarantee to obtain the accurate optimal solution due to the use of heuristic algorithm in solving the subproblem;Although the traditional heuristic method can quickly obtain a feasible solution,the solution ability needs to be further improved.Aiming at the goal of finding the exact optimal solution,an algorithm based on branch pricing is proposed in this paper;For high-speed scenarios,this paper proposes a solution algorithm based on deep reinforcement learning.The details are as follows:(1)An algorithm based on branch pricing is proposed to find the exact optimal solution.The main and subproblem models of the column generation algorithm are established for the RCPSP problem.In the main problem,the pseudo unsolvable problem is solved by introducing relaxation variables;In addition,a static and dynamic strategy to reduce the solution space is proposed,which removes some variables that must not be in the optimal solution and reduces the search range of the algorithm;Finally,the branch tree is constructed by the branch and bound algorithm,and the decimal solution obtained by the column generation algorithm is transformed into an integer solution.The experimental results on self-made data set and public data set PSPLIB show that the introduction of relaxation variables into the main problem ensures the correctness and optimality of the algorithm,and the two strategies to reduce the solution space significantly improve the solution ability of the algorithm;The proposed algorithm can find the optimal solution to most problems with no more than 90 processes.(2)For the first time,an algorithm based on deep reinforcement learning is proposed to quickly solve the feasible solution.By analyzing the infeasibility of serial schedule generation scheme(SSGS)combined with Actor-Critic(AC)network and the feasibility of parallel schedule generation scheme(PSGS)combined with AC network,the solution mode of PSGS combined with AC network is designed: The solving process is transformed into a Markov process,and the AC network is used to replace the priority rule to select the process,in which the actor selects a process step by step to construct the scheduling scheme,and the critical evaluates the scheduling scheme;To represent the process more comprehensively,the sequential relationship network is regarded as a graph,the subsequent processes of the process are regarded as their neighbors,and the neighbor information is aggregated combined with the graph neural network;The network adopts the encoder-decoder framework,considers the information such as resources and processes in the current state,and introduces the attention mechanism into critical to better represent the example information.The experimental results on the public data set PSPLIB show that the proposed algorithm can surpass the solution performance of the compared heuristic algorithm with the time complexity of the heuristic algorithm on all scale examples,which verifies the superiority of the proposed solution mode.