工业工程

工业工程 ›› 2024, Vol. 27 ›› Issue (1): 45-53.doi: 10.3969/j.issn.1007-7375.230006

• 系统建模与优化 • 上一篇    下一篇

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

张利平1,2, 高拯1,2, 陈志敏3, 唐秋华1,2, 夏源3   

  1. 1. 武汉科技大学 冶金装备及其控制教育部重点实验室，湖北 武汉 430081;
    2. 武汉科技大学 机械传动与制造工程湖北省重点实验室，湖北 武汉 430081;
    3. 中国舰船研究设计中心，湖北 武汉 430064
  • 收稿日期:2023-01-03 发布日期:2024-03-05
  • 通讯作者: 高拯 (2000—)，男，湖北省人，硕士研究生，主要研究方向为项目管理。Email：2640460132@qq.com E-mail:2640460132@qq.com
  • 作者简介:张利平 (1983—)，女，湖北省人，教授，博士，主要研究方向为智能制造、生产调度、项目管理等
  • 基金资助:
    国家自然科学基金资助项目 (51875420)

Mathematical Modeling and Complexity Analysis for Multi-mode Resource-constrained Project Scheduling Based on CPM

ZHANG Liping1,2, GAO Zheng1,2, CHEN Zhimin3, TANG Qiuhua1,2, XIA Yuan3   

  1. 1. Key Laboratory of Metallurgical Equipment and Control Technology, Wuhan University of Science and Technology, Wuhan 430081, China;
    2. Hubei Key Laboratory of Mechanical Transmission and Manufacturing Engineering, Wuhan University of Science and Technology, Wuhan 430081, China;
    3. China Ship Development and Design Center, Wuhan 430064, China
  • Received:2023-01-03 Published:2024-03-05

RichHTML

436

PDF

361

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

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

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

中图分类号: