基于鲁棒性的离散时间—费用权衡项目调度

摘要/Abstract

摘要： 针对传统离散—时间费用权衡项目调度问题(DTCTP)中忽略活动工期波动的问题,从鲁棒优化角度考虑调整调度方案的灵活性。将DTCTP中的预算问题(DTCTP-P2)拓展为基于项目工期和鲁棒性的双目标模型DTCTP-Robustness,设计了专用的多目标精确枚举排序算法求解DTCTP-Robustness,算法逐个检查可行解,并采用基于双目标的Pareto解集合保存和更新策略。通过求解算例,分析在不同费用约束下,5种鲁棒性指标和工期组合下所对应的各个Pareto最优解集合;在相同的总费用约束下,比较DTCTP-Robustness和DTCTP-P2两种模型的最优解的差别。结果表明,项目经理在不确定环境下进行工期-费用权衡决策时,DTCTP-Robustness提供的信息比DTCTP-P2更客观。

关键词: 鲁棒性, 项目调度, 时间—费用权衡, Pareto精确算法

Abstract: Aiming at the problem that the duration fluctuations of activities were almost ignored in the classic Discrete Time/Cost Trade-off Project (DTCTP) scheduling,the flexibility of scheduling scheme was adjusted from the perspective of robust optimization.A new bi-objective model-DTCTP-Robustness based on project duration and robustness was presented by expanding the DTCTP-P2 (budget problem),and a special exact enumeration sorting algorithm was developed to solve the DTCTP-Robustness,in which all feasible solutions were checked one by one,and the strategy for the bi-objective model was executed to preserve and update the Pareto solutions set.Through the solving example,the Pareto optimal solution sets were analyzed according to five combinations of project duration and robust measures under the different cost constraints.The difference between the optimal solution of DTCTP-Robustness and DTCTP-P2 models were contrasted within the same budget constraint.The conclusion showed that the DTCTP-P2 could provide more objective information than the DTCTP-P2 when project managers made the duration/cost trade-off of projects under the uncertain environment.

Key words: robustness, project scheduling, time/cost trade-off, Pareto exact algorithm

中图分类号:

F224.3

张静文,刘金波,李若楠. 基于鲁棒性的离散时间—费用权衡项目调度[J]. .

ZHANG Jing-wen,LIU Jin-bo,LI Ruo-nan. Robustness-based discrete time/cost trade-off project scheduling[J]. .

参考文献

［1］HARTMANN S,BRISKON D.A survey of variants and extensions of the resource-constrained project scheduling problem［J］.European Journal of Operational Research,2010,207(1):1-14.
[2]PENG Wuliang,WANG Chengen.Resource-constrained DTCTP and its algorithm solution［J］.Computer Integrated Manufacturing Systems,2008,14(11):2155-2160(in Chinese).［彭武良,王成恩.资源受限的离散时间/成本平衡问题及其遗传算法求解［J］.计算机集成制造系统,2008,14(11):2155-2160.］
[3]DE P,DUNNE E J,GHOSH J B,et al.The discrete time/cost trade-off problem revisited［J］.European Journal of Operational Research,1995,81(2):225-238.
[4]BRUNI M E,BERALDI P,GUERRIERO F,et al.A heuristic approach for resource constrained project scheduling with uncertain activity durations［J］.Computer & Operations Research,2011,38(9);1305-1318.
[5]HERROELEN W,LEUS R.Project scheduling under uncertainty;survey and research potentials［J］.European Journal of Operational Research,2005,165(2);289-306.
[6]DEMEULEMEESTER E,HERROELEN W.Introduction to the special issue;project scheduling under uncertainty［J］.Journal of Scheduling,2007,10(3);151-152.
[7]ZHANG Jingwen,XU Yu,HE Zhengwen,et al.A review on the time/cost trade-offs problem in project scheduling［J］.Journal of Industrial Engineering and Engineering Management,2007,21(1):92-97(in Chinese).［张静文,徐渝,何正文,等.项目调度中的时间—费用权衡问题研究综述［J］.管理工程学报,2007,21(1):92-97.］
[8]VANHOUCKE M.The discrete time/cost trade-off problem;extensions and heuristic procedures［J］.Journal of Scheduling,2007,10(4):311-326.
[9]PENG Wuliang,WANG Chengen.A multi-mode resource-constrained discrete time-cost tradeoff problem and its genetic algorithm based on solution［J］.International Journal of Project Management,2009,27(6):600-609.
[10]ZHANG Jingwen,SHAN Huifang.Two categories of resource-constrained time/ cost trade-off project scheduling problem and its two-stage hybrid optimizing algorithm［J］.Computer Integrated Manufacturing Systems,2011,17(9);2035-2043 (in Chinese).［张静文,单绘芳.两类资源约束型工期-费用均衡及两阶段算法［J］.计算机集成制造系统,2011,17 (9);2035- 2043.］
[11]HAFIZOGLU A B,AZIZOGLU M.Linear programming based approaches for the discrete time/cost trade-off problem in project networks［J］.Journal of the Operational Research Society,2010,61(4):676-685.
[12]SONMEZ R,BETTEMIR O H.A hybrid genetic algorithm for the discrete time-cost trade-off problem［J］.Expert System with Applications,2012,39(13):11428-11434.
[13]TAREGHIAN H R,TAHERI S H.A solution procedure for the discrete time,cost and quality tradeoff problem using electromagnetic scatter search［J］.Applied Mathematics and Computation,2007,190(2):1136-1145.
[14]KIM J Y,KANG C W,HWANG I K.A practical approach to project scheduling;considering the potential quality loss cost in the time-cost trade-off problem［J］.International Journal of Project Management,2012,30(2):264-272.
[15]KLERIDES E,HADJICONSTANTINOU E.A decomposition-based stochastic programming approach for the project scheduling problem under time/cost trade-off settings and uncertain durations［J］.Computers and Operations Research,2010,37(12):2131-2140.
[16]KE Hua,MA Weimin,CHEN Xiaowei.Modeling stochastic project time-cost trade-offs with time-dependent activity durations［J］.Applied Mathematics and Computation,2012,218(18):9462-9469.
[17]ESHTEHARDIAN E,AFSHAR A,ABBASNIA R.Fuzzy-based MOGA approach to stochastic time-cost trade-off problem［J］.Automation in Construction,2009,18(5):692-701.
[18]CHEN S P,TSAI M J.Time-cost trade-off analysis of project networks in fuzzy environments［J］.European Journal of Operational Research,2011,212(2):386-397.
[19]DEBLAERE F,DEMEULEMEESTER E,HERROELEN W.Proactive policies for the stochastic resource-constrained project scheduling problem［J］.European Journal of Operational Research,2011,214(2):308-316.
[20]AL-FAWZAN M A,HAOUARI M.A bi-objective model for robust resource-constrained project scheduling［J］.International Journal of Production Economics,2005,96(2):175-187.
[21]VONDER S V,DEMEULEMEESTER E,HERROELEN W,et al.The use of buffers in project management;the trade-off between stability and makespan［J］.International Journal of Production Economics,2005,97(2):227-240.
[22]DEBLAERE F,DEMEULEMEESTER E,HERROELEN W.Reactive scheduling in the multi-mode RCPSP［J］.Computer & Operations Research,2011,38(1):63-74.
[23]HAZIR O,HAOUARI M,EREL E.Robust scheduling and robustness measures for the discrete time/cost trade-off problem［J］.European Journal of Operational Research,2010,207(2):633-643.
[24]VONDER S V,BALLESTIN F,DEMEULEMEESTER E,et al.Heuristic procedures for reactive project scheduling［J］.Computer & Industrial Engineering,2007,52(1):11-28.
[25]CHTOUROU H,HAOUARI M.A two-stage-priority-rule-based algorithm for robust resource-constrained project scheduling［J］.Computer & Industrial Engineering,2008,55(1);183-194.

[1]	陈志远,伍章俊,童珊珊,刘晓. 基于改进双归档进化算法的多目标动态软件项目调度[J]. 计算机集成制造系统, 2021, 27(9): 2565-2574.
[2]	杨丽丽,李文龙,孔祥龙,许浩. 混合不确定性鲁棒协同优化设计方法[J]. 计算机集成制造系统, 2021, 27(11): 3282-3290.
[3]	刘辉,张超勇,戴稳. 基于堆叠稀疏去噪自动编码网络与多隐层反向传播神经网络的铣刀磨损预测模型[J]. 计算机集成制造系统, 2021, 27(10): 2801-2812.
[4]	韩笑乐,许可,陆志强. 集装箱码头泊位—堆场资源的鲁棒性模板决策[J]. 计算机集成制造系统, 2020, 26(第3): 784-794.
[5]	王小明,陈庆新,毛宁. 基于近似动态规划的模具项目调度[J]. 计算机集成制造系统, 2020, 26(6): 1691-1701.
[6]	巴智勇,袁逸萍,戴毅,李晓娟,阿地兰木·斯塔洪,刘金朵. 考虑机器故障的作业车间调度方案鲁棒测度方法[J]. 计算机集成制造系统, 2020, 26(12): 3341-3349.
[7]	王治,刘检华,刘少丽,任杰轩,吴天一. 基于双目视觉的管路位姿测量[J]. 计算机集成制造系统, 2019, 25(第5): 1047-1054.
[8]	朱宏伟,陆志强. 考虑资源转移时间的项目可拆分资源受限多项目调度问题[J]. 计算机集成制造系统, 2019, 25(第3): 586-597.
[9]	钱美容,蒋近. CD播放器机械臂轨迹跟踪的鲁棒自适应迭代学习控制[J]. 计算机集成制造系统, 2019, 25(第3): 682-691.
[10]	廖怡娜,陆志强. 考虑作业返工的资源受限项目调度问题[J]. 计算机集成制造系统, 2019, 25(第11): 2762-2774.
[11]	杨超,陆志强. 项目拆分和多项目调度集成决策模型与算法[J]. 计算机集成制造系统, 2018, 24(第3): 550-557.
[12]	初梓豪,徐哲,于静. 带有活动重叠的多模式资源受限项目调度问题[J]. 计算机集成制造系统, 2017, 23(第3期): 557-566.
[13]	顾泽平,杨建军,周勇. 不确定因素扰动下多目标柔性作业车间鲁棒调度方法[J]. 计算机集成制造系统, 2017, 23(第1期): 66-74.
[14]	张晓冬,周宏丽,胡杨. 大规模协同环境下知识协作网络的动态鲁棒性[J]. 计算机集成制造系统, 2017, 23(第11): 2353-2360.
[15]	张猛,陆志强. 多技能资源约束项目调度问题的改进算法[J]. 计算机集成制造系统, 2016, 22(第3期): 782-792.