复杂不确定环境下活动可拆分的项目资源鲁棒性调度优化

doi:10.16381/j.cnki.issn1003-207x.2020.2176

摘要/Abstract

摘要： 复杂不确定环境下，制定一个具有较强抗干扰能力的基准进度计划非常必要。本文研究了活动工期不确定环境下考虑活动可拆分的项目资源鲁棒性调度优化问题，旨在考虑活动可拆分，探究在活动优先关系约束、项目截止日期约束、活动拆分约束、资源流约束等条件下如何进行活动拆分决策并合理地安排各个项目活动/活动分段间的资源调配方案和时间缓冲添加策略，以制定鲁棒性最大化的基准进度计划。本文创新点如下：1)在项目资源鲁棒性调度优化问题中考虑活动可拆分，定义了资源流网络下活动自由时差的计算方法，提出了一种新的活动可拆分情形下进度计划鲁棒性的衡量方式，进而构建得到了考虑活动可拆分的项目资源鲁棒性调度优化模型；2)分析证明了问题模型的强NP-hard属性以及非线性属性，并在此基础上开发了一种内嵌资源调度安排的遗传算法进行问题求解；3)选取一个典型的实际案例对研究问题进行说明，直观展示了活动拆分执行对进度计划鲁棒性提升的重要价值，揭示了鲁棒性调度计划中资源调度方案的重要性，得到了活动拆分执行会增加项目内部资源转移次数的结论。

关键词: 鲁棒性调度；优化模型；遗传算法；活动可拆分；活动工期不确定

Abstract: In practice, faced with the complex and uncertain environment, it is really necessary for project managers to construct a robust resource allocation schedule with a strong anti-interference ability. At the stage of schedule generation, activities may be not divided into the smallest units, so project managers can choose to further split activities into subactivities under specific constraints. When taking activity splitting into account, on the one hand, it will be more flexible for activity scheduling; on the other hand, it will be more complex for resource allocation between the subactivities.

Key words: robust scheduling; optimization model; genetic algorithm; activity splitting; stochastic activity durations

中图分类号:

C935
F224.33

马志强, 徐小峰, 何正文, 王能民. 复杂不确定环境下活动可拆分的项目资源鲁棒性调度优化[J]. 中国管理科学, 2022, 30(3): 117-130.

MA Zhi-qiang, XU Xiao-feng, HE Zheng-wen, WANG Neng-min. Robust Scheduling Optimization of Project Resources with Activity Splitting under Complex and Uncertain Environments[J]. Chinese Journal of Management Science, 2022, 30(3): 117-130.

参考文献

［1］ Herroelen W,Leus R. Project scheduling under uncertainty: Survey and research potentials［J］. European Journal of Operational Research,2005,165:289-306.
［2］徐小峰, 郝俊, 邓忆瑞. 考虑多因素扰动的项目关键链缓冲区间设置及控制模型［J］. 系统工程理论与实践, 2017, 37(6): 1593-1601.Xu Xiaofeng, Hao Jun, Deng Yirui. Project critical chain buffer setting and control model considered multiple factors disturbance［J］. Systems Engineering-Theory & Practice, 2017, 37(6): 1593-1601.
［3］ Artigues C, Michelon P, Reusser S. Insertion techniques for static and dynamic resource-constrained project scheduling［J］. European Journal of Operational Research, 2003, 149(2): 249-267.
［4］ Herroelen W, Leus R. The construction of stable project baseline schedules［J］. European Journal of Operational Research, 2004, 156(3): 550-565.
［5］ Deblaere F, Demeulemeester E, Herroelen W, et al. Robust resource allocation decisions in resource-constrained projects［J］. Decision Sciences, 2007, 38(1): 5-37.
［6］ Van de Vonder S, 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.
［7］ Van de Vonder S, Demeulemeester E, Herroelen W, et al. The trade-off between stability and makespan in resource-constrained project scheduling［J］. International Journal of Production Research, 2006, 44(2): 215-236.
［8］ Van de Vonder S, Demeulemeester E, Herroelen W. Proactive heuristic procedures for robust project scheduling: An experimental analysis［J］. European Journal of Operational Research, 2008, 189(3): 723-733.
［9］ Elshaer R, Yamamoto H. New proactive time buffer heuristics for robust project scheduling［J］. Journal of Advanced Mechanical Design Systems & Manufacturing, 2012, 6(5): 559-571.
［10］ Potgieter I J, Rooyen G C V. Maximizing slack in resource-constrained schedules: A heuristic approach［J］. Journal of Computing in Civil Engineering, 2016, 30(6): 04016018-1- 04016018-11.
［11］庞南生,白立晨.鲁棒性项目调度中资源流网络优化算法研究［J］.项目管理技术,2018,16(10):70-74.Pang Nansheng, Bai Lichen. Optimization algorithm on resource flow network for robust project scheduling［J］. Project Management Techonology, 2018, 16(10): 70-74.
［12］梁洋洋,王田,崔南方.基于资源流网络优化的Max-npv项目调度［J］.中国管理科学,2020,DOI: 10.16381/j.cnki.issn1003-207x.2019.1431.Liang Yangyang, Wang Tian, Cui Nanfang. Max-NPV project scheduling based on optimizing the resource flow network［J］. Chinese Journal of Management Science, 2020, DOI: 10.16381/j.cnki.issn1003-207x.2019.1431.
［13］ Wang Jianjiang, Hu Xuejun, Demeulemeester E, et al. A bi-objective robust resource allocation model for the RCPSP considering resource transfer costs［J］. International Journal of Production Research, 2021, 59(2): 367-387.
［14］刘寅斌,胡子怡,李洪波,等.可抢占条件下的项目调度研究综述［J］.运筹与管理,2019,28(4):191-199.Liu Yinbin, Hu Ziyi, Li Hongbo, et al. Preemptive project scheduling: Aliterature review［J］. Operations Research and Management Science, 2019, 28(4): 191-199.
［15］陆志强,石婷.作业可拆分的资源投入问题的建模与优化［J］.计算机集成制造系统,2018,24(3):602-611.Lu Zhiqiang, Shi Ting. Modeling and optimization of resource investment problem with activity splitting［J］. Computer Integrated Manufacturing Systems, 2018, 24(3): 602-611.
［16］ Afshar-Nadjafi B, Khalaj Z, Mehdizadeh E. A branch and bound approach to solve the preemptive resource leveling problem［J］. International Journal of Manufacturing Engineering, 2013: 1-7.
［17］ Ma Zhiqiang, He Zhengwen, Wang Nengmin, et al. A genetic algorithm for the proactive resource-constrained project scheduling problem with activity splitting［J］. IEEE Transactions on Engineering Management, 2019, 66(3): 459-474.
［18］ Tavana M, Abtahi A R, Khalili-Damghani K. A new multi-objective multi-mode model for solving preemptive time-cost-quality trade-off project scheduling problems［J］. Expert Systems with Applications, 2014, 41(4): 1830-1846.
［19］刘振元,袁慧涛,周成,等.多技能资源时间窗约束下可中断项目调度的分支定界算法［J］.系统工程理论与实践,2019,39(1):183-199.Liu Zhenyuan, Yuan Huitao, Zhou Cheng, et al. Branch-and-bound based approach for preemptive project scheduling with time-window constraints on multi-skilled resources［J］. Systems Engineering-Theory & Practice, 2019, 39(1): 183-199.
［20］ Ballestín F, Valls V, Quintanilla S. Pre-emption in resource-constrained project scheduling［J］. European Journal of Operational Research, 2008, 189(3): 1136-1152.
［21］ Ballestín F, Valls V, Quintanilla S. Scheduling projects with limited number of preemptions［J］. Computers & Operations Research, 2009, 36(11): 2913-2925.
［22］ Haouari M, Kooli A, Néron E, et al. A preemptive bound for the resource constrained project scheduling problem［J］. Journal of Scheduling, 2014, 17(3): 237-248.
［23］ Demeulemeester E, Herroelen W. An efficient optimal solution procedure for the preemptive resource-constrained project scheduling problem［J］. European Journal of Operational Research, 1996, 90(2): 334-348.
［24］ Moukrim A, Quilliot A, Toussaint H. An effective branch-and-price algorithm for the preemptive resource constrained project scheduling problem based on minimal interval order enumeration［J］. European Journal of Operational Research, 2015, 244(2): 360-368.
［25］丁雪枫,尤建新.多模式资源受限项目调度问题的混合优化算法研究［J］.中国管理科学,2012,20(S1):154-159.Ding Xuefeng, You Jianxin. Studies on a hybrid optimal algorithm for multi-mode resource-constrained project scheduling problem［J］. Chinese Journal of Management Science, 2012, 20(S1): 154-159.
［26］寿涌毅,彭晓峰,李菲,等.抢占式资源受限项目调度问题的遗传算法［J］.浙江大学学报(工学版),2014,48(8):1473-1480.Shou Yongyi, Peng Xiaofeng, Li Fei, et al. Genetic algorithms for the preemptive resource-constrained project scheduling problem［J］. Journal of Zhejiang University (Engineering Science), 2014, 48(8): 1473-1480.
［27］ Vanhoucke M, Coelho J. Resource-constrained project scheduling with activity splitting and setup times［J］. Computers & Operations Research, 2019, 109: 230-249.
［28］ Zhang Hong, Li Heng, Tam C M. Particle swarm optimization for preemptive scheduling under break and resource-constraints［J］. Journal of Construction Engineering and Management, 2006, 132(3): 259-267.
［29］ Afshar-Nadjafi B. A solution procedure for preemptive multi-mode project scheduling problem with mode changeability to resumption［J］. Applied Computing and Informatics, 2018, 14(2): 192-201.
［30］ Chtourou H, Haouari M. A two-stage-priority-rule-based algorithm for robust resource-constrained project scheduling［J］. Computers & Industrial Engineering, 2008, 55(1): 183-194.
［31］ Ma Zhiqiang, Demeulemeester E, He Zhengwen, et al. A computational experiment to explore better robustness measures for project scheduling under two types of uncertain environments［J］. Computers & Industrial Engineering, 2019, 131: 382-390.
［32］ Artigues C, Leus R, Nobibon F T. Robust optimization for resource-constrained project scheduling with uncertain activity durations［J］. Flexible Services & Manufacturing Journal, 2013, 25: 175-205.
［33］ Holland J H. Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence［M］. London: The MIT Press, 1992.

[1]	王田, 郑重. 产能不确定供应商的风险厌恶行为对供应链的影响[J]. 中国管理科学, 2022, 30(1): 165-174.
[2]	朱立龙, 荣俊美, 张思意. 政府奖惩机制下药品安全质量监管三方演化博弈及仿真分析[J]. 中国管理科学, 2021, 29(11): 55-67.
[3]	马咏, 何正文, 郑维博. 基于柔性资源约束的前摄性项目调度优化研究[J]. 中国管理科学, 2020, 28(7): 220-230.
[4]	朱立龙, 荣俊美. “互联网+医疗健康”背景下考虑患者反馈机制的药品质量监管策略研究[J]. 中国管理科学, 2020, 28(5): 122-135.
[5]	刘明, 李颖祖, 曹杰, 章定. 突发疫情环境下基于服务水平的应急物流网络优化设计[J]. 中国管理科学, 2020, 28(3): 11-20.
[6]	官子力, 张旭梅, 但斌. 需求不确定下制造商服务投入影响销售的供应链信息共享与激励[J]. 中国管理科学, 2019, 27(10): 56-65.
[7]	李迁, 陶莎, 周晓园, 盛昭瀚. 考虑作业空间干涉的工程项目时间-成本均衡优化研究[J]. 中国管理科学, 2019, 27(10): 170-178.
[8]	龚媛媛, 肖勇波. 新鲜产品跨季销售中的动态库存管理策略研究[J]. 中国管理科学, 2019, 27(7): 83-93.
[9]	李鹏飞, 马航. 基于病毒协同遗传算法的自动化立体仓库货位优化模型[J]. 中国管理科学, 2017, 25(5): 70-77.
[10]	耿瑞, 朱建军, 王翯华, 刘小弟. 基于z标记的灰色GERT多任务项目费用优化研究[J]. 中国管理科学, 2017, 25(4): 133-142.
[11]	郭传好, 陈芳, 单而芳. 短生命周期乳制品供应链网络成本与收益优化研究[J]. 中国管理科学, 2017, 25(2): 87-97.
[12]	熊峰, 彭健, 金鹏, 张向阳, 邱妘. 生鲜农产品供应链关系契约稳定性影响研究——以冷链设施补贴模式为视角[J]. 中国管理科学, 2015, 23(8): 102-111.
[13]	曹晓刚, 郑本荣, 闻卉. 考虑顾客偏好的双渠道闭环供应链定价与协调决策[J]. 中国管理科学, 2015, 23(6): 107-117.
[14]	张延禄, 杨乃定. 基于组织-任务网络的研发项目工期风险分析——以组织失效为风险因素[J]. 中国管理科学, 2015, 23(2): 99-107.
[15]	曹晓刚, 闻卉, 郑本荣, 黎继子. 混合需求下考虑专利保护因素的闭环供应链定价与协调[J]. 中国管理科学, 2014, 22(10): 106-112.