带有活动重叠的项目调度问题新算法: 分支定界法

In the complex product research and experimental development project, activities overlapping is usually used to shorten project duration. Currently, most methods for resource constrained project scheduling problem with activities overlapping are based on heuristic algorithm. This method has the advantages of fast-speed convergence and large-scale calculation, but cannot obtain the optimal solution. The accurate algorithm is an effective method to solve the optimal solution of the above problem. Therefore, a branch and bound method is designed to obtain the optimal solution according to examine the impact of overlapping activities on project scheduling. Firstly, the optimality of the algorithm is proved in theory. The optimal solution can be obtained only by considering the minimum delay substitution set, and cut set domination rule and left shift domination rule in pruning operation is proved. Secondly, in the algorithm design, the data structure–stack is used to store the node information on the search tree, and for the activities overlapping constraint, a new decision point and a new representation method of the search tree node are defined. Finally, the feasibility and effectiveness of the algorithm are verified by a large number of instances. In conclusion, the proposed algorithm has high research value with mature theoretical significance and accurate calculation results.