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

作者:于静; 徐哲; 谢芳
更新时间:

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