工业工程2024，Vol.27Issue(1)：45-53,9.DOI:10.3969/j.issn.1007-7375.230006
基于CPM的多模式资源约束项目调度建模与复杂度分析
Mathematical Modeling and Complexity Analysis for Multi-mode Resource-constrained Project Scheduling Based on CPM
摘要
Abstract
To effectively reduce the complexity and solution space of the multi-mode resource-constrained project scheduling model,three mixed-integer linear programming models are established in this paper.The upper bound of time series T is reduced by using the tight upper bound TTUB,while the upper and lower bounds of the completion time of each activity are reduced by using the critical path method.Thereby,complexity and solution space of the model are reduced.1106 instances with different scales are selected from the MRCPSP benchmark library to verify the effectiveness of the improved model.Results show that the CPM-based multi-mode resource-constrained project scheduling model has smaller solution space;the number of decision variables is reduced by 3～65 times,and the number of constraints is reduced by 1～4 times;the average computation time is decreased by 53%～112%,resulting in that the performance of the proposed model is significantly better than that of others.Moreover,the results of the 1106 instances also indicate that the closer α is to 1,the lower the complexity and the smaller the solution space of the model,which verifies the performance of parameter α.But the difficulty of exploring feasible solutions increases with the increase of instance scales.Therefore,the value of α should be appropriately relaxed for large-scale instances.关键词
多模式资源约束项目调度/模型复杂度/解空间/上界/混合整数线性规划模型Key words
multi-mode resource-constrained project scheduling/model complexity/solution space/upper bound/mixed-integer linear programming model分类
管理科学引用本文复制引用
张利平,高拯,陈志敏,唐秋华,夏源..基于CPM的多模式资源约束项目调度建模与复杂度分析[J].工业工程,2024,27(1):45-53,9.基金项目
国家自然科学基金资助项目(51875420) （51875420）
