基于CPM的多模式资源约束项目调度建模与复杂度分析

摘要

为有效降低多模式资源约束项目调度模型的复杂度和解空间，构建3类混合整数线性规划模型。运用紧上界T_TUB缩减时间序列T的上界和关键路径法缩减各项活动结束时间的上下界，以降低模型复杂度和解空间。为验证改进模型的有效性，从MRCPSP标杆案例库中选取1 106组规模不等的算例进行求解。结果表明，基于CPM的多模式资源约束项目调度模型解空间更小；决策变量同比缩小3～65倍，约束数同比缩小1～4倍；平均求解时间同比减少53%～112%，求解性能显著优于其他模型。为验证紧上界T_TUB的参数α性能，1106组算例结果表明，α越接近1，模型的复杂度越低，解空间越小。但随着算例规模增加，算例可行解探寻难度增加。因此，对大规模算例，α值应适当放宽。

关键词

多模式资源约束项目调度 / 模型复杂度 / 解空间 / 上界 / 混合整数线性规划模型

基金资助

国家自然科学基金资助项目(51875420)