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

A branch and bound method for project scheduling problem with activities overlapping

在复杂产品研发项目中,通常采用活动重叠的方式来缩短工期,带有活动重叠的资源受限项目调度问题的求解多以启发式算法为主,该方法虽然具有收敛速度快、计算规模大等优点,但无法得到最优解,而精确算法是求解上述问题最优解的有效方法。基于此,本文在深入分析活动重叠对项目调度影响的基础上,设计了分支定界法以获得最优解。首先,从理论上证明了算法的最优性,一是对仅考虑最小延迟替代集即可得到最优解进行了证明;二是对割集支配规则与左移支配规则在剪枝操作中的应用进行了证明。其次,在算法设计上采用数据结构——栈对搜索树上的节点信息进行存储,并针对活动重叠约束,定义了新的决策时刻点和新的搜索树节点的表示方法。最后,通过大量的算例实验分析验证了算法的可行性和有效性。综上,本文提出的算法具备成熟的理论意义与精准的计算结果,具有较高的研究价值。

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.