鉴于优先规则启发式算法求解多项目调度的优势, 基于带有全局资源转移时间的分布式多项目调度问题, 设计多种启发式算法及优先规则并针对不同优化目标评估其性能. 首先, 基于最小化多项目组合延迟百分比和最小化平均子项目延迟时间两种目标构建问题的混合整数规划模型. 其次, 设计改进的单项目、coupled和decoupled启发式三种类型的优先规则启发式算法求解问题; 针对每种启发式算法, 分别改进传统求解资源约束型项目调度的串行和并行机制以适应新问题的全局资源转移时间特征, 梳理现有用于求解单项目和多项目问题的优先规则, 并根据全局资源特性设计新的规则; 根据在调度机制中的不同作用, 每种启发式算法下的优先规则被分类和组合并应用于改进的调度机制中, 从而共获得4080种可求解新问题的启发式优先规则组合方案. 最后, 提出一种基于子项目位置分布的资源转移时间生成方法, 结合MPSPLIB算例库中的分布式多项目算例构造测试算例; 针对三种启发式算法及嵌入的4080种优先规则组合设计评估方案和指标并开展数值实验. 研究结果表明: 针对两种不同的优化目标, 单项目启发式和decoupled启发式各有优势, 但coupled启发式表现较差; 与现有优先规则相比, 提出的新优先规则可以更有效地优化两种目标; 全局资源转移时间对多项目的两种目标均有重要影响.
Abstract
In view of the advantages of the priority rule-based heuristics in solving multi-project scheduling, various heuristics and priority rules were designed for the decentralized multi-project scheduling problem with global resource transfer times and their performance on different objectives was evaluated. Firstly, a mixed integer programming model was constructed based on the two objectives portfolio percentage delay and average project delay. Secondly, three improved priority rule-based heuristics, single-project, coupled and decoupled heuristics, were designed to solve the problem. For each heuristic, the traditional serial and parallel schedule schemes for multi-project scheduling were improved to adapt to the global resource transfer time characteristics of the new problem; the existing priority rules for solving single project and multi-project problems were sorted out, and new rules were proposed according to the global resources characteristics. According to the different roles in the schedule schemes, the priority rules under each heuristic method were classified and combined and applied to the improved schedule schemes, so that a total of 4080 priority rule combinations that can solve the new problem were obtained. Finally, a resource transfer time generation mechanism based on project location distribution was proposed, and test instances were constructed based on the MPSPLIB dataset; the evaluation schemes and indicators were designed for three heuristics and the corresponding 4080 combination schemes, based on which numerical experiments were carried out. The results showed that the single-project heuristic and the decoupled heuristic had their own advantages for different objectives, but the coupled heuristic performed poorly; the new priority rules proposed in this paper performed better than the existing rules; global resource transfer time had a significant impact on both objectives of the multi-project.
关键词
全局资源转移时间 /
分布式多项目 /
decoupled启发式 /
优先规则性能 /
改进的调度生成机制
{{custom_keyword}} /
Key words
global resource transfer times /
decentralized multi-project /
decoupled heuristic /
priority rules performance /
improved schedule generation scheme
{{custom_keyword}} /
中图分类号:
C935
F224.33
{{custom_clc.code}}
({{custom_clc.text}})
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] Sá nchez M G, Lalla-Ruiz E, Gil A F, et al. Resource-constrained multi-project scheduling problem: A survey[J]. European Journal of Operational Research, 2023, 309(3): 958-976.
[2] Bredael D, Vanhoucke M. Multi-project scheduling: A benchmark analysis of metaheuristic algorithms on various optimisation criteria and due dates[J]. European Journal of Operational Research, 2023, 308(1): 54-75.
[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] Ma Z, Zheng W, He Z, et al. A genetic algorithm for proactive project scheduling with resource transfer times[J]. Computers & Industrial Engineering, 2022, 174: 108754.
[5] Liu Y, Zhou J, Lim A, et al. A tree search heuristic for the resource constrained project scheduling problem with transfer times[J]. European Journal of Operational Research, 2023, 304(3): 939-951.
[6] Homberger J. A (μ, λ)-coordination mechanism for agent-based multi-project scheduling[J]. OR Spectrum, 2012, 34(1): 107-132.
[7] 刘东宁, 徐哲, 李飞飞. 基于合作博弈协商机制的分布式资源受限多项目调度[J]. 系统工程理论与实践, 2019, 39(6): 1507-1516. Liu D N, Xu Z, Li F F. Distributed resource constrained multi-project scheduling problem with cooperative-game based negotiation mechanism[J]. Systems Engineering—Theory & Practice, 2019, 39(6): 1507-1516.
[8] 刘东宁, 徐哲. 基于多优先规则启发式的分布式多项目随机调度[J]. 系统工程理论与实践, 2021, 41(12): 3294-3303. Liu D N, Xu Z. A stochastic scheduling for distributed multi-project with multi-PR heuristic[J]. Systems Engineering—Theory & Practice, 2021, 41(12): 3294-3303.
[9] Kruger D, Scholl A. A heuristic solution framework for the resource constrained (multi) project scheduling problem with sequence-dependent transfer times[J]. European Journal of Operational Research, 2009, 197(2): 492-508.
[10] Kruger D, Scholl A. Managing and modelling general resource transfers in (multi-) project scheduling[J]. OR Spectrum, 2010, 32(2): 369-364.
[11] Mittal M L, Kanda A. Scheduling of multiple projects with resource transfers[J]. International Journal of Mathematics in Operational Research, 2009, 1(3): 303-325.
[12] Cai Z, Li X. A hybrid genetic algorithm for resource-constrained multi-project scheduling problem with resource transfer time[C]//Automation Science and Engineering (CASE), 2012 IEEE International Conference, 2012.
[13] Suresh M, Dutta P, Jain K. Resource constrained multi-project scheduling problem with resource transfer times[J]. Asia-Pacific Journal of Operational Research, 2015, 32(6): 1550048.
[14] Adhau S, Mittal M L, Mittal A. A multi-agent system for decentralized multi-project scheduling with resource transfers[J]. International Journal of Production Economics, 2013, 146(2): 646-661.
[15] 赵松, 徐哲, 刘东宁. 考虑全局资源闲置成本的分布式RCMPSPTT[J]. 系统工程理论与实践, 2020, 40(7): 1882- 1894. Zhao S, Xu Z, Liu D N. Decentralized RCMPSPTT with cost of idleness[J]. Systems Engineering—Theory & Practice, 2020, 40(7): 1882-1894.
[16] Zhang J, Liu W, Liu W. An effcient genetic algorithm for decentralized multi-project scheduling with resource transfers[J]. Journal of Industrial & Management Optimization, 2022, 18(1): 1-24.
[17] 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.
[18] Van Eynde R, Vanhoucke M. Resource-constrained multi-project scheduling: Benchmark datasets and decoupled scheduling[J]. Journal of Scheduling, 2020, 23(3): 301-325.
[19] Lova A, Tormos P. Analysis of scheduling schemes and heuristic rules performance in resource-constrained multi project scheduling[J]. Annals of Operations Research, 2001, 102(1-4): 263-286.
[20] Mittal M L, Kanda A. Two-phase heuristics for scheduling of multiple projects[J]. International Journal of Operational Research, 2009, 4(2): 159-177.
[21] Olaguí bel R A V, Goerlich J M T. Heuristic algorithms for resource constrained project scheduling: A review and an empirical analysis[M]//Elsevier, 1989: 113-134.
[22] Cooper D F. Heuristics for scheduling resource-constrained projects: An experimental investigation[J]. Management Science, 1976, 22(11): 1186-1194.
[23] Davis E W, Patterson J H. A comparison of heuristic and optimum solutions in resource-constrained project scheduling[J]. Management Science, 1975, 21(8): 944-955.
[24] Coelho J, Valadares L T. Comparative analysis on approximation algorithms for the resource constrained project scheduling problem[C]//Eighth International Workshop on Project Management and Scheduling, EURO Working Group on Project Management and Scheduling, 2002.
[25] Klein R. Bidirectional planning: Improving priority rule-based heuristics for scheduling resource-constrained projects[J]. European Journal of Operational Research, 2000, 127(3): 619-638.
[26] Slowinski R, Weglarz J. Advances in project scheduling[M]//Elsevier, 1989.
[27] Yang K K. A comparison of dispatching rules for executing a resource-constrained project with estimated activity durations[J]. Omega, 1998, 26(6): 729-738.
[28] Kurtulus I, Davis E W. Multi-project scheduling: Categorization of heuristic rules performance[J]. Management Science, 1982, 28(2): 161-172.
[29] Schirmer A, Riesenberg S. Parameterized heuristics for project scheduling: Biased random sampling methods [R]//Manuskripte aus den Instituten fü r Betriebswirtschaftslehre der Universität Kiel, 1997.
[30] Vá zquez E P, Calvo M P, Ordóñez P M. Learning process on priority rules to solve the RCMPSP[J]. Journal of Intelligent Manufacturing, 2015, 26(1): 123-138.
[31] 张亚宁, 白思俊, 陈志, 等. 基于深度学习的RCPSP调度优先规则实时动态选择算法[J]. 系统工程理论与实践, 2023, 43(7): 2142-2153. Zhang Y N, Bai S J, Chen Z, et al. Real-time dynamic selection algorithm of RCPSP scheduling priority rules based on deep learning[J]. Systems Engineering—Theory & Practice, 2023, 43(7): 2142-2153.
[32] 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(2): 1-21.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
国家自然科学基金(71971173,72201209);西北工业大学博士论文创新基金(CX2023069,SOMBC202203)
{{custom_fund}}