| Summary: | Resource-constrained project scheduling problem(RCPSP) is the most representative scheduling problem,which is an abstract representation of many practical scheduling problems.It belongs to the NP-hard problem and is difficult to obtain the global optimal solution for large-scale problems.In this paper,an integer programming model is proposed.By decomposing the model into a constrained master problem and some subproblems,a column generation method is designed for the solving of the linear relaxation model,and then the integer solution of the problem is found through branch & price.In the process of solving,relaxation variables are introduced to solve the pseudo infeasibility of the model.Furthermore,pruning strategy,branch strategy,and two methods for reducing the solution space according to different situations are designed.On the PSPLIB data set,for the problems with 30 processes,the current optimal solutions can be obtained in 10 minutes for 301 out of 480 instances.For the problems with 60 processes,the current optimal solutions can be obtained in 20 minutes for 269 out of 480 instances.For the problem with 90 processes,the current optimal solutions can be obtained in 30 minutes for 263 out of 480 instances.At the same time,by using the strategies of reducing the solution space,the number of timeout instances decreases significantly,and the performance of the optimized initial solution is significantly improved.Experimental results show that the proposed algorithm is effective.
|
|---|