基于两阶段资源分配协调机制的分布式多项目随机调度

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

中国管理科学 ›› 2022, Vol. 30 ›› Issue (12): 38-51.doi: 10.16381/j.cnki.issn1003-207x.2021.2641

• 论文 • 上一篇

基于两阶段资源分配协调机制的分布式多项目随机调度

李飞飞¹, 徐哲²

1.北京联合大学管理学院，北京100101； 2.北京航空航天大学经济管理学院，北京100191

收稿日期:2021-08-10 修回日期:2021-12-24 发布日期:2023-01-10
通讯作者: 徐哲(1964-),女(汉族),江苏无锡人,北京航空航天大学经济管理学院,教授,博导,研究方向:系统仿真、项目管理，Email:xuzhebuaa@163.com. E-mail:xuzhebuaa@163.com
基金资助:
北京市自然科学基金资助青年项目(9214024)，教育部人文社会科学研究青年基金资助项目(21YJCZH063)，北京市教委社科计划一般项目(SM202111417006)，国家自然科学基金资助项目(72271012,71571005)，北京联合大学教育科学研究课题(Jk202013)

Distributed Multi-project Stochastic Scheduling with Two-stage Coordination Mechanism of Resources Allocation

LI Fei-fei¹, XU Zhe²

1. School of Management, Beijing Union University, Beijing 100101, China；2. School of Economics and Management, Beihang University, Beijing 100191, China

Received:2021-08-10 Revised:2021-12-24 Published:2023-01-10
Contact: 徐哲 E-mail:xuzhebuaa@163.com

摘要/Abstract

摘要： 企业趋向于多项目共享全局资源的分布式协同管理。但在多项目实际执行时，全局资源可用量往往由于外部环境的动态变化而存在不确定性，活动中断、资源浪费等现象频发，项目管理变得愈加复杂。本文将不确定的全局资源可用量建模为随机变量，设计两阶段资源分配协调机制，在预分配阶段，考虑项目允许的最大活动中断次数约束，建立各项目调度的马尔可夫动态决策过程模型；预分配结束后，基于活动重要度依次对剩余全局资源进行协调再分配，以提高资源利用率并减少平均项目延期。设计基于全局资源协调分配的Rollout近似动态规划算法进行求解。开展问题库算例实验研究与案例分析，验证协调机制与求解算法的性能；同时，探讨并分析不确定参数对目标结果的影响。

关键词: 分布式多项目；随机调度；全局资源不确定；协调机制；动态规划

Abstract: Enterprises tend to manage multiple projects in a distributed manner where the global resources are shared among autonomous projects. In the actual process of multi-projects scheduling, however, the availability of global resources is often uncertain due to some unexpected situations or stochastic factors, resulting in disruption of activities, waste of resources and other consequences. A new level of complexity is therefore added to the traditional project management. The distributed resource-constrained multi-project scheduling problem (DRCMPSP) is studied under uncertain global resource availabilities.

Key words: distributed multi-project; stochastic scheduling; uncertain global resource availability; coordination mechanism; dynamic programming

中图分类号:

O223
N945

李飞飞, 徐哲. 基于两阶段资源分配协调机制的分布式多项目随机调度[J]. 中国管理科学, 2022, 30(12): 38-51.

LI Fei-fei, XU Zhe. Distributed Multi-project Stochastic Scheduling with Two-stage Coordination Mechanism of Resources Allocation[J]. Chinese Journal of Management Science, 2022, 30(12): 38-51.

参考文献

［1］ Hartmann S, Briskorn 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］ Gonalves J F, Mendes J J, Resende M G. A genetic algorithm for the resource constrained multi-project scheduling problem［J］. European Journal of Operational Research, 2008, 189(3): 1171-1190.
［3］ Confessore G, Giordani S, Rismondo S. A market-based multi-agent system model for decentralized multi-project scheduling［J］. Annals of Operations Research, 2007, 150(1): 115-135.
［4］ Homberger J. A multiagent system for the decentralized resource-constrained multiproject scheduling problem［J］. International Transactions in Operational Research, 2007, 14(6): 565-589.
［5］彭武良, 陈良威, 马雪丽. 分散式项目群调度的双目标优化方法研究［J］.管理工程学报, 2021, DOI: 10.13587/j.cnki.jieem.2021.05.012.Peng Wuliang, Chen Liangwei, Ma Xueli. Research on the double-objective optimization for decentralized project group scheduling［J］. Journal of Industrial Engineering and Engineering Management, 2021, DOI: 10.13587/j.cnki.jieem.2021.05.012.
［6］ Chan H K, Chung S H. Optimisation approaches for distributed scheduling problems［J］. International Journal of Production Research, 2013, 51(9): 2571-2577.
［7］ Araúzo J A, Pajares J, Lopez-Paredes A. Simulating the dynamic scheduling of project portfolios［J］. Simulation Modelling Practice and Theory, 2010, 18(10): 1428-1441.
［8］应瑛, 寿涌毅. 基于组合拍卖方法的资源受限多项目调度［J］. 计算机集成制造系统, 2009, 15(11): 2160-2165.Ying Ying, Shou Yongyi. Resource-constrained multi-project scheduling based on combinatorial auction method［J］. Computer Integrated Manufacturing Systems, 2009, 15(11): 2160-2165.
［9］王磊, 战德臣, 聂兰顺. 基于市场机制的多项目分散式调度问题［J］. 计算机集成制造系统, 2014, 20(8): 1969-1979.Wang Lei, Zhan Dechen, Nie Lanshun. Multi-project decentralized scheduling problem solving by market mechanism［J］. Computer Integrated Manufacturing Systems, 2014, 20(8): 1969-1979.
［10］ Adhau S, Mittal M L, Mittal A. A multi-agent system for distributed multi-project scheduling: An auction-based negotiation approach［J］. Engineering Applications of Artificial Intelligence, 2012, 25(8): 1738-1751.
［11］ Song Wen, Kang Donghun, Zhang Jie, et al. A multi-unit combinatorial auction based approach for decentralized multi-project scheduling［J］. Autonomous Agents and Multi-Agent Systems, 2017, 31(6): 1548-1577.
［12］ Homberger J. A (μ, λ)-coordination mechanism for agent-based multi-project scheduling［J］. OR spectrum, 2012, 34(1): 107-132.
［13］ Homberger J, Fink A. Generic negotiation mechanisms with side payments - design, analysis and application for decentralized resource-constrained multi-project scheduling problems［J］. European Journal of Operational Research, 2017, 261(3): 1001-1012.
［14］ Wauters T, Verbeeck K, De Causmaecker P, et al. A learning-based optimization approach to multi-project scheduling［J］. Journal of Scheduling, 2015, 18(1): 61-74.
［15］李飞飞, 徐哲, 于静. 基于序贯博弈谈判机制的分布式多项目调度［J］. 系统工程理论与实践, 2018, 38(3): 696-709.Li Feifei, Xu Zhe, Yu Jing. A sequential game-based negotiation approach to distributed multi-project scheduling problem［J］. Systems Engineering-Theory & Practice, 2018, 38(3): 696-709.
［16］刘东宁, 徐哲, 李飞飞. 基于合作博弈协商机制的分布式资源受限多项目调度［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.
［17］ Tosselli L, Bogado V, Martínez E. A repeated-negotiation game approach to distributed (re)scheduling of multiple projects using decoupled learning［J］. Simulation Modelling Practice and Theory, 2020, 98: 101980.
［18］刘婉君, 张静文, 刘万琳. 基于拍卖机制的资源转移时间型动态分布式多项目调度［J］.中国管理科学, 2021, DOI: 10.16381/j.cnki.issn1003-207x.2020.0687.Liu Wanjun, Zhang Jingwen, Liu Wanlin. Dynamic decentralized resource-constrained multi-project scheduling problem with transfer times based on auction mechanism［J］. Chinese Journal of Management Science, 2021, DOI: 10.16381/j.cnki.issn1003-207x.2020.0687.
［19］ Song Wen, Xi Hui, Kang Donghun, et al. An agent-based simulation system for multi-project scheduling under uncertainty［J］. Simulation Modelling Practice and Theory, 2018, 86: 187-203.
［20］胡雪君, 赵燕, 单汨源, 等. 基于自适应大邻域搜索的鲁棒多项目调度方法［J］. 中国管理科学, 2020, DOI: 10.16381/j.cnki.issn1003-207x.2020.1096.Hu Xuejun, Zhao Yan, Shan Miyuan, et al. An adaptive large neighborhood search metaheuristic for robust multi-project scheduling［J］. Chinese Journal of Management Science, 2020, DOI: 10.16381/j.cnki.issn1003-207x.2020.1096.
［21］刘东宁, 徐哲. 基于多优先规则启发式的分布式多项目随机调度［J］.系统工程理论与实践, 2021, DOI: 10.12011/SETP2020-2982.Liu Dongning, Xu Zhe. A stochastic scheduling for distributed multi-project with multi-PR heuristic［J］. Systems Engineering-Theory & Practice, 2021, DOI: 10.12011/SETP2020-2982.
［22］ Zhao Song, Xu Zhe. New closed-loop approximate dynamic programming for solving stochastic decentralized multi-project scheduling problem with resource transfers［J］. Expert Systems with Applications, 2021, 185: 115593.
［23］ Liu Dongning, Xu Zhe, Li Feifei. A three-stage decomposition algorithm for decentralized multi-project scheduling under uncertainty［J］. Computers & Industrial Engineering, 2021, 160: 107553.
［24］刘万琳, 张静文, 刘婉君. 带有资源柔性约束的max-NPV分布式多项目调度问题［J］. 运筹与管理, 2021, 30(8): 37-43.Liu Wanlin, Zhang Jingwen, Liu Wanjun. Max-NPV of distributed multi-project scheduling problem with resource flexibility constraints［J］. Operations Research and Management Science, 2021, 30(8): 37-43.
［25］谢芳, 李洪波, 柏庆国. 随机多模式资源受限项目调度［J］.中国管理科学, 2021, DOI:10.16381/j.cnki.issn1003-207x.2020.1250.Xie Fang, Li Hongbo, Bai Qingguo. Stochastic multi-mode resource-constrained project scheduling［J］. Chinese Journal of Management Science, 2021, DOI:10.16381/j.cnki.issn1003-207x.2020.1250.
［26］ Li H, Womer N K. Solving stochastic resource-constrained project scheduling problems by closed-loop approximate dynamic programming［J］. European Journal of Operational Research, 2015, 246(1): 20-33.

基于两阶段资源分配协调机制的分布式多项目随机调度

Distributed Multi-project Stochastic Scheduling with Two-stage Coordination Mechanism of Resources Allocation

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

Metrics

本文评价

推荐阅读 0