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

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

中国管理科学 ›› 2022, Vol. 30 ›› Issue (9): 217-231.doi: 10.16381/j.cnki.issn1003-207x.2020.1096cstr: 32146.14.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

HU Xue-jun,ZHAO Yan,SHAN Mi-yuan, 等. 基于自适应大邻域搜索的鲁棒多项目调度方法[J]. 中国管理科学, 2022, 30(9): 217-231.

单汩源,王建江,别黎. 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]. 中国管理科学, 2025, 33(10): 293-303.
[2]	王莺潼, 计小宇, 孟庆春. 动态不确定环境下基于多层级备份策略的供应链网络性能研究[J]. 中国管理科学, 2025, 33(10): 316-326.
[3]	李梦祺, 李登峰, 南江霞. 考虑链间竞争与链内研发成本共担的绿色供应链决策——基于非合作-合作两型博弈方法[J]. 中国管理科学, 2025, 33(10): 339-349.
[4]	何爽, 赵亮, 张剑, 李琳. 替代竞争情境下关联需求固定产出比联产品加工决策研究[J]. 中国管理科学, 2025, 33(10): 76-85.
[5]	伏红勇, 雷一峰, 但斌, 掌曙光. 应对供应商减排不合规的碳审计策略：独立vs联合[J]. 中国管理科学, 2025, 33(9): 339-348.
[6]	陈威, 田永乐, 白春光, 马永开. 考虑极端天气的电力供应链可再生能源维护策略研究[J]. 中国管理科学, 2025, 33(9): 359-368.
[7]	吕希琛, 田银凤, 田世海, 刘佳缘, 孔庆伟. MRV机制下碳数据质量监管多主体行为决策研究[J]. 中国管理科学, 2025, 33(8): 355-368.
[8]	李志文, 徐贤浩, 关旭, 柏庆国, 陈程. 农产品市场双寡头区块链采纳决策的演化博弈分析[J]. 中国管理科学, 2025, 33(7): 324-336.
[9]	孙中苗, 徐琪. 区块链技术下政府对可再生能源电力消纳的动态激励补贴研究[J]. 中国管理科学, 2025, 33(7): 346-359.
[10]	扈衷权, 梁倩, 沈奥, 刘阳. 基于期权契约的应急物资生产能力储备模型研究[J]. 中国管理科学, 2025, 33(5): 247-258.
[11]	张文明, 杜玉禄. 相邻价格相关的在线单向交易问题的数据驱动型策略设计[J]. 中国管理科学, 2025, 33(5): 26-33.
[12]	何洪阳, 张彬, 田苏俊. 平台经济政企协同治理的演化博弈分析[J]. 中国管理科学, 2025, 33(5): 76-87.
[13]	周驰, 李赫, 于静. 委托代理关系下品牌商网络直播营销激励机制设计[J]. 中国管理科学, 2025, 33(4): 265-274.
[14]	白雨, 赵昕, 丁黎黎. 考虑企业时间偏好的碳配额存储与借贷机制研究[J]. 中国管理科学, 2025, 33(4): 357-368.
[15]	许书琴, 徐琪. 能源平台供应链可再生能源电力消纳激励契约研究[J]. 中国管理科学, 2025, 33(3): 326-338.

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

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

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0