基于时间窗延迟的资源约束项目调度双层优化研究

doi:10.12005/orms.2021.0377

运筹与管理 ›› 2021, Vol. 30 ›› Issue (12): 6-12.DOI: 10.12005/orms.2021.0377

基于时间窗延迟的资源约束项目调度双层优化研究

刘国山¹, 王敏¹, 张转霞²

1.中国人民大学商学院,北京 100872;
2.北方工业大学信息学院,北京 100093

收稿日期:2020-05-24 出版日期:2021-12-25
作者简介:刘国山(1962-),男,吉林舒兰人,教授,博士,研究方向:项目管理、物流管理;王敏(1990-),女,山西永济人,博士研究生,研究方向:项目管理优化;张转霞(1990-),女,山西大同人,硕士研究生,研究方向:数据库。

ABi-level Programming Problem Based on Time-window Delay for Resource-Constrained Project Scheduling

LIU Guo-shan¹, WANG Min¹, ZHANG Zhuan-xia²

1. School of Business, Renmin University of China, Beijing 100872, China;
2. School of Information, North China University of Technology, Beijing 100093, China

Received:2020-05-24 Online:2021-12-25

摘要/Abstract

摘要： 本研究从业主—承包商交互的视角构建了一种RCPSP(resource-constrained project scheduling problem)双层优化模型,即在可更新资源约束条件下,项目双方如何进行交互决策达到双方NPV(Net present value)最大化的目标。首先对研究问题进行界定,构建资源约束下的max-NPV项目调度双层优化模型;然后利用延迟优先规则设计了一种基于时间窗延迟的嵌套式自适应遗传算法来求解该模型,以达到双方NPV最大化;最后用一个算例验证算法的有效性,同时通过PSPLIB数值实验说明算法的稳定性,并分析关键参数对项目双方收益的影响。研究结果为项目进程的安排以及奖励机制的设计提供依据,以提高双方利益。

关键词: 项目调度, 时间窗延迟, 自适应遗传算法, 双层优化, Max-NPV

Abstract: In this paper, a bi-level programming problem of RCPSP (resource-constrained project scheduling problem) is proposed from the perspective of owner-contractor interaction, that is, how to make interactive decision to maximize NPV (Net present value) under renewable resource constraints. Firstly, we establish the programming model for client and contractor as a leader-follower game that is enacted through bi-level hierarchical programming mechanism. The client is modeled as an upper-level problem for optimal selection of unit incentive ratio while the contractor is modeled as a lower-level problem which responds to decisions of upper level in order to schedule the activities. Secondly, in order to solve the problem, a nested adaptive genetic algorithm based on time window delay program is designed. Finally, a case study is implemented to illustrate the stability and efficiency of the algorithm, the proposed program has been tested on the PSPLIB dataset, and managerial insights are provided with respect to the impact of key parameters. The results can provide a basis for the arrangement of the project process and the formulation of the incentive mechanism between the two parties, so as to improve the interests of both parties.

Key words: project scheduling, time-window delay program, adaptive genetic algorithm, bi-level programming, max-NPV

中图分类号:

O224

刘国山, 王敏, 张转霞. 基于时间窗延迟的资源约束项目调度双层优化研究[J]. 运筹与管理, 2021, 30(12): 6-12.

LIU Guo-shan, WANG Min, ZHANG Zhuan-xia. ABi-level Programming Problem Based on Time-window Delay for Resource-Constrained Project Scheduling[J]. Operations Research and Management Science, 2021, 30(12): 6-12.

参考文献

[1] Herroelen W, Dommelen V, Demeulemeester E. Project network models with discounted cash flows: a guided tour through recentdevelopments[J]. European Journal of Operational Research, 1997, 100(1): 97-121.
[2] 陈建华,马士华.基于工期协调的项目公司与承包商收益激励模型[J].中国管理科学,2007,15(3):114-122.
[3] Kerkhove L P, Vanhoucke M. Incentive contract design for projects: the owner's perspective[J]. Omega, 2016, 62: 93-114.
[4] Joseph G S. The impact of contractor behavior on the client's payment-scheduling problem[J]. Management Science, 2005, 51(4): 629-640.
[5] He Z, Wang N, Li P. Simulated annealing for financing cost distribution based project payment scheduling from a joint perspective[J]. Annals of Operations Research, 2014, 213: 203-220.
[6] Xianhai M, Gallagher B. The impact of incentive mechanisms on project performance[J]. International Journal of Project Management, 2012, 30: 352-362.
[7] Suprapto M, Bakker H L M, Herman G M, et al. How do contract types and incentives matter toproject performance?[J]. International Journal of Project Management, 2016, 34: 1071-1087.
[8] Leyman P, Vanhoucke M. Payment models and net present value optimization for resource-constrained project scheduling[J]. European Journal of Operational Research, 2016, 91: 139-153.
[9] Leyman P, Vanhoucke M. A new scheduling technique for the resource-constrainedproject scheduling problem with discounted cash flows[J]. International Journal of Production Research, 2015, 53(9): 2771-2786.
[10] Vanhoucke M, Demeulemeester E, Herroelen W. On maximizing the net present value of a project under renewable resource constraints[J]. ManagementScience, 2001, 47(8): 1113-1121.
[11] Shr J F, Chen W T. A method to determine minimum contract bids for incentive highway projects[J]. International Journal of Project Management, 2003, 21(8): 601-615.
[12] Christiansen S, Patriksson M, Wynter L. Stochastic bi-level programming instructural optimization[J]. Structural and Multidisciplinary Optimization, 2001, 21(5): 361-371.
[13] Hansen P, Jaumard B, Savard G. New branch-and-bound rules for linear bi-level programming[J]. SIAM Journal on Scientific and Statistical Computing,1992, 13(5): 1194-1217.
[14] Candler W, Townsley R. A linear two-level programming problem[J]. Computers & Operations Research, 1982, 9(1): 59-76.
[15] Bard J F, Falk J. An explicit solution to the multi-level programming problem[J]. Computers & Operations Research, 1982, 9(1): 77-100.
[16] Srinivas M, Patnaik L M. Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE Transactions on Systems Man and Cybernetics, 1994, 24(4): 656-667.

基于时间窗延迟的资源约束项目调度双层优化研究

ABi-level Programming Problem Based on Time-window Delay for Resource-Constrained Project Scheduling

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	马咏, 何正文, 江波, 王能民. 一种求解柔性资源约束前摄性项目调度问题的启发式算法[J]. 运筹与管理, 2021, 30(8): 14-20.
[2]	刘万琳, 张静文, 刘婉君. 带有资源柔性约束的max-NPV分布式多项目调度问题[J]. 运筹与管理, 2021, 30(8): 37-43.
[3]	张静文, 刘婉君, 李琦. 基于关键链改进搜索的遗传算法求解分布式多项目调度[J]. 运筹与管理, 2021, 30(3): 123-129.
[4]	宁敏静, 郑小强, 何正文. 基于随机活动工期的现金流动态均衡前摄性与反应性项目调度优化[J]. 运筹与管理, 2021, 30(2): 117-123.
[5]	胡雪君, 王建江, 谭跃进, 徐培德, 崔南方. 带有资源转移时间的RCPSP资源流模型及算法[J]. 运筹与管理, 2021, 30(12): 42-50.
[6]	陈俊杰, 同淑荣, 王曜, 聂亚菲, 张静文. 人力资源约束下的项目群调度问题建模与求解[J]. 运筹与管理, 2020, 29(3): 107-116.
[7]	宁敏静, 何正文, 刘人境. 基于随机活动工期的多模式现金流均衡项目调度优化[J]. 运筹与管理, 2019, 28(9): 91-98.
[8]	刘寅斌,胡子怡,李洪波,余咪咪. 可抢占条件下的项目调度研究综述[J]. 运筹与管理, 2019, 28(4): 191-195.
[9]	刘建胜, 张有功, 熊峰, 胡颖聪. Flying-V型仓储布局货位分配优化方法研究[J]. 运筹与管理, 2019, 28(11): 27-33.
[10]	李雪, 何正文, 王能民. 不确定环境下基于时间、费用及鲁棒性权衡的多目标项目调度优化[J]. 运筹与管理, 2019, 28(1): 6-16.
[11]	付芳, 张涛. 考虑返修的建设项目时间-成本-质量问题[J]. 运筹与管理, 2018, 27(7): 193-199.
[12]	陆坚毅, 杨超, 揭婉晨. 考虑绕行特征的电动汽车快速充电站选址问题及自适应遗传算法[J]. 运筹与管理, 2017, 26(1): 8-17.
[13]	刘洋, 陈志, 白思俊. 广义优先关系约束下Max-npv项目调度问题及其遗传算法[J]. 运筹与管理, 2016, 25(6): 91-98.
[14]	郑维博, 何正文, 刘人境. 基于融资能力约束的多模式Max-npv项目调度优化: 双重视角[J]. 运筹与管理, 2016, 25(1): 25-34.
[15]	李佳媛, 何正文. 基于资源随机中断的反应性多模式项目调度优化[J]. 运筹与管理, 2015, 24(6): 44-50.