基于自适应大邻域搜索的鲁棒多项目调度方法

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

中国管理科学 ›› 2022, Vol. 30 ›› Issue (9): 217-231.doi: 10.16381/j.cnki.issn1003-207x.2020.1096

基于自适应大邻域搜索的鲁棒多项目调度方法

单汩源¹, 王建江³, 别黎⁴

1.湖南大学工商管理学院,湖南长沙410082; 2.中南财经政法大学工商管理学院,湖北武汉430073;3.国防科技大学系统工程学院,湖南长沙410073;4.中南民族大学管理学院，湖北武汉430074

收稿日期:2020-06-09 修回日期:2020-09-29 出版日期:2022-09-20 发布日期:2022-09-01
通讯作者: 赵雁(1984- ),女(汉族),山东烟台人,中南财经政法大学工商管理学院，讲师,博士,研究方向:项目管理、鲁棒项目调度、组合优化,Email:zydxd@zuel.edu.cn. E-mail:zydxd@zuel.edu.cn
基金资助:
国家自然科学基金资助项目(72071075,71701067,71801218,71971094);湖南省自然科学基金资助项目(2019JJ50039,2020JJ4672);国防科技大学科研计划项目(ZK18-03-16)

An Adaptive Large Neighborhood Search Metaheuristic for Robust Multi-project Scheduling

HU Xue-jun¹, ZHAO Yan², SHAN Mi-yuan¹, WANG Jian-jiang³, BIE Li⁴

1. Business School, Hunan University, Changsha 410082, China;2. School of Business Administration, Zhongnan University of Economics and Law, Wuhan 430073, China;3. College of Systems Engineering, National University of Defense Technology, Changsha 410073, China;4. School of Management, South-Central University for Nationalities, Wuhan 430074, China

Received:2020-06-09 Revised:2020-09-29 Online:2022-09-20 Published:2022-09-01
Contact: 赵雁 E-mail:zydxd@zuel.edu.cn

摘要/Abstract

摘要： 多项目资源管理有时需要采用一种资源专享-转移策略，该策略下可更新资源在多项目之间不共享，但在当前项目完工之后其资源可以转移至其它还未开始的项目。针对这一实际问题的理论研究非常有限。考虑活动工期的不确定性，从时差效用函数视角评价项目调度计划的鲁棒性，在考虑拖期成本-鲁棒性的多目标问题框架下，构建了一个资源专享-转移视角下的多项目资源分配(战术层)与鲁棒调度(运作层)双层决策优化模型。针对模型的NP-hard性质和多目标组合优化特征，设计了一种新的自适应大邻域搜索(adaptive large neighborhood search，ALNS)算法求解模型。该算法采用“项目-缓冲-资源-活动”列表的混合编码表示问题可行解，提出基于四类列表的destroy-repair邻域结构，设计一种超体积指标进行自适应搜索以提高算法性能。最后，为了验证ALNS算法的适用性和有效性，设计一种NSGA-II算法作为比较基准，通过大规模仿真实验对算法性能进行了对比分析，并探索工期不确定水平对多项目调度方案鲁棒性的影响。

关键词: 多项目管理；资源专享；鲁棒性；时差效用函数；多目标优化；自适应大邻域搜索

Abstract: In multi-project management, it is critical to allocate limited resources among different projects and within each project, because it affects the resource utilization and the implementation of project plans. According to the execution environment of multiple projects or the characteristics of resources, there are two approaches to the management of renewable resources: resource sharing and resource dedication. The resource sharing policy has been studied a lot, but the research on the resource dedication problem is very limited. In this paper, a novel resource dedication-transferring policy for managing resources is proposed, in which renewable resources are dedicated to each individual project during execution but can be transferred to another one starting after the finish of the corresponding project.

Key words: multi-project management; resource dedication; robustness; slack-based utility function; multi-objective optimization; adaptive large neighborhood search

中图分类号:

F224

单汩源, 王建江, 别黎. 基于自适应大邻域搜索的鲁棒多项目调度方法[J]. 中国管理科学, 2022, 30(9): 217-231.

HU Xue-jun, ZHAO Yan, SHAN Mi-yuan, WANG Jian-jiang, BIE Li. An Adaptive Large Neighborhood Search Metaheuristic for Robust Multi-project Scheduling[J]. Chinese Journal of Management Science, 2022, 30(9): 217-231.

参考文献

［1］ Lova A, Maroto C, Tormos P. A multicriteria heuristic method to improve resource allocation in multiproject scheduling［J］. European Journal of Operational Research, 2000, 127(2): 408-424.
［2］ Laslo Z, Goldberg A I. Resource allocation under uncertainty in a multi-project matrix environment: Is organizational conflict inevitable?［J］. International Journal of Project Management, 2008, 26(8): 773-788.
［3］寿涌毅. 资源受限多项目调度的模型与方法［M］. 杭州: 浙江大学出版社, 2010.Shou Yongyi. Resource-constrained multi-project scheduling models and methods［M］. Hangzhou: Zhejiang University Press, 2010.
［4］ Asta S, Karapetyan D, Kheiri A, et al. Combining Monte-Carlo and hyper-heuristic methods for the multi-mode resource-constrained multi-project scheduling problem［J］. Information Sciences, 2016, 373:476-498.
［5］ Browning T R, Yassine A A. Resource-constrained multi-project scheduling: Priority rule performance revisited［J］. International Journal of Production Economics, 2010, 126(2): 212-228.
［6］徐赐军, 李爱平, 刘雪梅. 基于资源推拉技术的多项目调度算法［J］. 计算机集成制造系统, 2010, 16(6): 1246-1254.Xu Cijun, Li Aiping, Liu Xuemei. Multi-project scheduling algorithm based on resource push-pull technology［J］. Computer Integrated Manufacturing Systems, 2010, 16(6): 1246-1254.
［7］刘东宁, 徐哲, 李飞飞. 基于合作博弈协商机制的分布式资源受限多项目调度［J］. 系统工程理论与实践, 2019, 39(6): 1507-1516.Liu Dongning, Xu Zhe, Li Feifei. Distributed resource constrained multi-project scheduling problem with cooperative-game based negotiation mechanism［J］. Systems Engineering - Theory & Practice, 2019, 39(6): 1507-1516.
［8］ Be瘙塂ikci U, mit B, Ulusoy G. Resource dedication problem in a multi-project environment［J］. Flexible Services and Manufacturing Journal, 2013, 25(1): 206-229.
［9］ Be瘙塂ikci U, mit B, Ulusoy G. Multi-mode resource constrained multi-project scheduling and resource portfolio problem［J］. European Journal of Operational Research, 2015, 240(1): 22-31.
［10］ Liu Jing, Lu Ming. Robust dual-level optimization framework for resource-constrained multiproject scheduling for a prefabrication facility in construction［J］. Journal of Computing in Civil Engineering, 2019, 33(2): 04018067.
［11］胡雪君, 崔南方, 赵雁. 基于活动工期风险和资源约束风险的缓冲大小计算方法［J］. 控制与决策, 2016, 31(8): 1513-1518.Hu Xuejun, Cui Nanfang, Zhao Yan. Buffer sizing method based on activity duration risk and resource［J］. Control and Decision, 2016, 31(8): 1513-1518.
［12］田文迪, 胡慕海, 崔南方. 不确定性环境下鲁棒性项目调度研究综述［J］. 系统工程学报, 2014, 29(1): 135-144.Tian Wendi, Hu Muhai, Cui Nanfang. Review of studies on robust project scheduling under uncertainty［J］. Journal of Systems Engineering, 2014, 29(1): 135-144.
［13］ Wang J, Hu X, Demeulemeester E, et al. A bi-objective robust resource allocation model for the RCPSP considering resource transfer costs［J］. International Journal of Production Research, 2019, DOI: 10.1080/00207543.2019.1695168.
［14］马咏, 何正文, 郑维博. 基于柔性资源约束的前摄性项目调度优化研究［J］. 中国管理科学, 2020, 28(7): 220-230.Ma Yong, He Zhengwen, Zheng Weibo. Proactive project scheduling optimization based on flexible resource constraint［J］. Chinese Journal of Management Science, 2020, 28(7): 220-230.
［15］崔南方, 梁洋洋. 基于资源流网络与时间缓冲集成优化的鲁棒性项目调度［J］. 系统工程理论与实践, 2018, 38(1):102-112.Cui Nanfang, Liang Yangyang. Robust project scheduling based on the integrated optimization between resource flow network and time buffers［J］. Systems Engineering-Theory & Practice, 2018, 38(1):102-112.
［16］张静文, 周杉, 乔传卓. 基于时差效用的双目标资源约束型鲁棒性项目调度优化［J］. 系统管理学报, 2018, 27(2): 299-308.Zhang Jingwen, Zhou Shan, Qiao Chuanzhuo. A bi-objective robust resource-constrained project scheduling problem with utility functions of activity floats［J］. Journal of Systems &. Management, 2018, 27(2): 299-308.
［17］张立辉, 邹鑫, 黄元生, 等. 重复性项目调度模型的时差分析［J］. 中国管理科学, 2018, 26(6):95-103.Zhang Lihui, Zou Xin, Huang Yuansheng, el al. Float analysis in repetitive scheduling model［J］. Chinese Journal of Management Science, 2018, 26(6):95-103.
［18］ Lambrechts O, Demeulemeester E, Herroelen W. A tabu search procedure for developing robust predictive project schedules［J］. International Journal of Production Economics, 2008, 111(2): 493-508.
［19］ Palomo-Martínez P J, Salazar-Aguilar M A, Laporte G. Planning a selective delivery schedule through adaptive large neighborhood search［J］. Computers & Industrial Engineering, 2017, 112: 368-378.
［20］ Kiefer A, Hartl R F, Schnell A. Adaptive large neighborhood search for the curriculum-based course timetabling problem［J］. Annals of Operations Research, 2017, 252(2): 1-28.
［21］ Gomes H C, Neves F D A D, Souza M J F. Multi-objective metaheuristic algorithms for the resource-constrained project scheduling problem with precedence relations［J］. Computers & Operations Research, 2014, 44: 92-104.
［22］ 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.
［23］ Sun Jing, Miao Zhuang, Gong Dunwei, et al. Interval multiobjective optimization with memetic algorithms［J］. IEEE Transactions on Cybernetics, 2019, (99):1-14.
［24］ Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II［J］. IEEE Transactions on Evolutionary Computation, 2002, 6: 182-197.
［25］ Demeulemeester E, Vanhoucke M, Herroelen W. RanGen: A random network generator for activity-on-the-node networks［J］. Journal of Scheduling, 2003, 6(1):17-38.
［26］ Tabrizi B H, Ghaderi S F. A robust bi-objective model for concurrent planning of project scheduling and material procurement［J］. Computers & Industrial Engineering, 2016, 98: 11-29.

[1]	熊强,练帅,李治文,金帅. 双边道德风险下软件供应链信息安全责任协调契约设计[J]. 中国管理科学, 2024, 32(10): 265-274.
[2]	姜涛,高丽,刘露,柴旭东. 队列中的信息异构：基于口碑传播的等待制服务系统定价决策[J]. 中国管理科学, 2024, 32(10): 123-132.
[3]	黄苒,胡丽琴,李梦圆. 专有关系投资、议价力与企业违约风险[J]. 中国管理科学, 2024, 32(9): 11-23.
[4]	张艳芬,徐琪,孙中苗. 供应商竞争下考虑道德风险的平台供应链最优动态激励契约[J]. 中国管理科学, 2024, 32(9): 160-170.
[5]	李恒宇,柴俊武. 溢出效应下制造商的直播带货策略研究[J]. 中国管理科学, 2024, 32(9): 171-181.
[6]	王鹏,王要玉,王建才. 零售平台自有品牌与制造商渠道策略的竞合博弈分析[J]. 中国管理科学, 2024, 32(9): 214-224.
[7]	李进,刘格格,张海霞,张江华. 基于消费者绿色偏好和渠道竞争的制造商分散式入侵策略[J]. 中国管理科学, 2024, 32(7): 281-290.
[8]	冯颖,魏敏,何文豪,张炎治. 质量信息不对称下考虑参考价格效应的灰市供应链定价决策[J]. 中国管理科学, 2024, 32(6): 207-218.
[9]	李志鹏,周晓宇. 考虑消费者餍足效应的网络视频产业链最优决策研究[J]. 中国管理科学, 2024, 32(6): 229-239.
[10]	马德青,王晓晴,胡劲松. 多渠道零售下考虑消费者反展厅现象的平台型供应链销售模式选择[J]. 中国管理科学, 2024, 32(5): 133-146.
[11]	孙中苗,徐琪,张艳芬. 信息不对称下按需服务平台拥有不同类型代理人时的动态激励契约[J]. 中国管理科学, 2024, 32(5): 241-253.
[12]	熊一凡. 多重行动异质网络博弈[J]. 中国管理科学, 2024, 32(5): 265-274.
[13]	赵丹,严啸宸,汪和平,李艳. 双积分政策下汽车企业合作创新演化博弈分析[J]. 中国管理科学, 2024, 32(4): 279-292.
[14]	李波,张春燕,张俊飚. 食品企业质量安全意识提升的演化博弈逻辑[J]. 中国管理科学, 2024, 32(4): 315-324.
[15]	杨松,张言彩,王爱峰. 多主体参与下食品安全社会共治演化博弈稳定性[J]. 中国管理科学, 2024, 32(4): 325-334.

基于自适应大邻域搜索的鲁棒多项目调度方法

An Adaptive Large Neighborhood Search Metaheuristic for Robust Multi-project Scheduling

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0