考虑转移时间的分布式资源受限多项目鲁棒调度优化

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

摘要/Abstract

摘要：

在分布式资源受限多项目调度问题中考虑资源转移时间，研究考虑活动工期不确定的鲁棒调度优化，以制定抵抗工期扰动能力强的多项目基线调度计划和资源转移计划。针对问题特点建立以单项目鲁棒性为优化目标的局部调度模型，并通过深度优化的分支定界算法生成插入时间缓冲的局部基线调度计划；考虑全局资源可用量约束，以多项目鲁棒性为优化目标建立全局协调决策模型，设计基于资源流网络构建的启发式资源分配算法有效协调全局资源的分配与转移。实验研究表明：多项目基线调度计划的鲁棒性会随着问题规模及工期不确定程度的增加而恶化；本文提出的两阶段算法与已有的分支定界算法及各类启发式算法相比，能够获得鲁棒性更强的基线调度计划；通过分析项目截止日期与按时完工概率之间的关系，为项目管理者确定合理的截止日期提供参考建议。

关键词: 分布式多项目调度, 资源转移时间, 不确定工期, 鲁棒调度, 两阶段算法

Abstract:

In the distributed management environment， multiple projects may be located in different regions， so the global resource transfer times cannot be neglected when making multi-project scheduling plans. Besides， activity durations may be affected by various uncertain factors （e.g.， breakdown of production equipment） in the actual scheduling， resulting in deterioration or even infeasibility of the pre-determined scheduling plans. A distributed multi-project scheduling problem considering resource transfer times and uncertain activity durations is studied. Robust project scheduling is employed to tackle uncertainty. It is named as the robust distributed resource-constrained multi-project scheduling problem with transfer times （robust DRCMPSP-TT）. In the robust DRCMPSP-TT， consider the parallel execution of multiple projects in a distributed decision-making environment. The duration of the activities is uncertain， and the execution of the activities requires both local and global resources. Obtain the multi-project baseline scheduling and global resource transfer plans through problem-solving.

To formulate this problem， a two-stage model containing local scheduling and global coordination decision-making is established based on the multi-agent system. In the local scheduling optimization model， each PA focuses on the robustness of the single-project baseline scheduling plan， while in the global coordination decision-making model， the CA is concerned with the robustness of the multi-project scheduling plan. Moreover， a two-stage algorithm integrating time buffer addition and resource flow network construction is designed to solve the problem. In the first stage， the local scheduling problem is solved by the deeply optimized branch-and-bound algorithm to generate local baseline schedules with insertion time buffers. In the second stage， based on the local baseline schedules， a heuristic resource allocation algorithm is developed to optimize additional resource arcs to coordinate global resource allocation and transfer effectively.

The experimental research is executed based on 24 instances generated by RanGen1 software. According to the number of projects and activities in each multi-project， these instances are divided into 4 problem subsets， denoted 2_10， 2_30， 5_10， and 5_30. Each problem subset contains 6 multi-project instances with different problem parameters. Experimental results show that variations in the problem size and the degree of duration uncertainty have an impact on the robustness of the baseline schedule. Compared with the existing branch-and-bound algorithms and various heuristic algorithms， the proposed two-stage algorithm can effectively improve the robustness of the baseline schedule and is more suitable for solving the studied problem. The experimental results further verified that the timely project completion probability increases with the increase of the deadline and approach 1 at different speeds under different duration variability levels. In addition， by analyzing the relationship between project deadlines and the timely project completion probability， quantitative reference opinions are provided for managers to determine reasonable deadlines.

It makes up for the vacancy of the DRCMPSP and opens the door to further study the DRCMPSP with resource transfer and uncertain activity durations in this study. It mainly adopts the proactive scheduling strategy to solve robust DRCMPSP-TT， while combining proactive scheduling with reactive scheduling to solve this problem can be a topic for future research. In addition， the global resource availability is often uncertain due to various unexpected and uncontrollable conditions such as equipment failure， and DRCMPSP-TT under uncertain global resource availability can be further investigated.

Key words: distributed multi-project scheduling, resource transfer time, uncertain duration, robust scheduling, two-stage algorithm

中图分类号:

N945

徐哲,有维宝,赵松, 等. 考虑转移时间的分布式资源受限多项目鲁棒调度优化[J]. 中国管理科学, 2026, 34(2): 89-102.

Zhe Xu,Weibao You,Song Zhao, et al. Robust Scheduling Optimization for the Distributed Resource-constrained Multi-project Scheduling Problem with Transfer time[J]. Chinese Journal of Management Science, 2026, 34(2): 89-102.

图/表 13

图1

表1

符号及说明"

符号	说明
$N$	项目集合, $N = 1, 2, …, n, ∀ i ∈ N$
$Q$	全局资源集合, $Q = 1, 2, …, M, ∀ m ∈ Q$
$w i j$	活动 $a i j$ 的权重
$s i j B$	局部基线调度 $R B$ 中活动 $a i j$ 的计划开始时间
$S i j R$	局部实际调度 $R R$ 中活动 $a i j$ 的实际开始时间
$s i j B *$	多项目基线调度 $R B *$ 中活动 $a i j$ 计划开始时间
$S i j R *$	多项目实际调度 $R R *$ 中活动 $a i j$ 实际开始时间
$θ i j$	活动 $a i j$ 前添加的时间缓冲的大小
$d i j B$	活动 $a i j$ 的计划工期
$d i j R$	项目 $i$ 执行过程中活动 $a i j$ 的实际工期
$t$	时刻序号, $t = 0, 1, 2, …, T$ , $T$ 为项目计划期上限
$T T g x, i j m$	资源 $m$ 从活动 $a g x$ 转移到活动 $a i j$ 的转移时间
$α i j t$	二元决策变量,当活动 $a i j$ 在 $t$ 时刻完成时 $α i j t = 1$ ，否则 $α i j t = 0$
$y g x, i j m$	二元决策变量,当全局资源 $m$ 从活动 $a g x$ 转移到活动 $a i j$ 时 $y g x, i j m = 1$ ，否则 $y g x, i j m = 0$

表1

表2

表3

实验结果"

问题集	问题参数	$σ = 0.3$		$σ = 0.6$		$σ = 0.9$
问题集	问题参数	$S C$	$C P U (s)$	$S C$	$C P U (s)$	$S C$	$C P U (s)$
2_10	OS=0.3, RC=0.4	653.00	13.98	1440.36	14.56	4840.64	16.72
	OS=0.3, RC=0.8	914.69	12.82	2159.60	14.24	5082.13	15.13
	OS=0.5, RC=0.4	924.22	14.63	1008.00	15.33	3374.91	13.71
	OS=0.5, RC=0.8	993.33	19.96	1887.86	20.32	6110.53	20.63
	OS=0.7, RC=0.4	900.57	17.23	1446.96	16.62	4994.90	17.31
	OS=0.7, RC=0.8	1606.16	16.25	1735.56	16.97	3938.71	19.65
2_30	OS=0.3, RC=0.4	5462.57	51.06	7632.91	51.82	24149.06	50.77
	OS=0.3, RC=0.8	6841.72	33.32	9317.35	33.71	26727.48	33.43
	OS=0.5, RC=0.4	4360.00	30.61	7220.10	30.93	18927.03	33.24
	OS=0.5, RC=0.8	5170.92	50.40	8957.56	53.75	25033.98	57.41
	OS=0.7, RC=0.4	13889.35	45.32	15858.52	51.36	28189.86	50.74
	OS=0.7, RC=0.8	5351.67	50.43	8731.75	66.11	26019.41	61.54
5_10	OS=0.3, RC=0.4	6363.55	26.47	10079.09	27.08	29379.95	24.74
	OS=0.3, RC=0.8	6280.04	28.71	8533.55	42.24	24489.11	29.54
	OS=0.5, RC=0.4	4829.47	29.26	8200.71	29.04	27972.72	34.02
	OS=0.5, RC=0.8	7585.40	31.29	11120.37	28.14	33133.82	28.60
	OS=0.7, RC=0.4	5167.40	30.85	9431.60	26.85	30092.46	29.08
	OS=0.7, RC=0.8	7168.58	30.16	10168.20	28.35	29979.77	27.90
5_30	OS=0.3, RC=0.4	27337.84	80.02	43311.83	83.22	135420.83	82.26
	OS=0.3, RC=0.8	30292.21	83.35	46858.55	84.35	136848.00	83.13
	OS=0.5, RC=0.4	84342.90	84.59	91761.90	83.45	147660.73	83.83
	OS=0.5, RC=0.8	33219.79	87.68	50037.00	85.96	159252.25	86.03
	OS=0.7, RC=0.4	26948.85	80.06	44546.88	82.70	135142.40	79.32
	OS=0.7, RC=0.8	32146.23	137.73	51808.83	144.99	165523.50	145.95

表3

图2

图3

表4

不同算法的求解结果（进度稳定性成本）对比"

算法	$σ = 0.3$	$σ = 0.6$	$σ = 0.9$
两阶段算法	813.00	1373.30	3860.06
分支定界算法	4628.43	4786.11	5743.93
MINSLK	3144.56	3370.62	4704.70
EFT	2145.94	2206.82	2998.54
LFT	1481.89	1697.29	3259.04
LST	2417.22	2735.42	4525.36
EST	1614.98	1794.95	3096.05
SPT	2272.67	2352.04	3285.29
LPT	4510.92	4643.24	5681.31

表4

图4

图5

图6

图7

图8

图9

参考文献 33

[1]	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.
[2]	Demeulemeester E L， Herroelen W S. Project scheduling： a research handbook［M］.New York： Springer Science & Business Media， 2006.
[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]	Zhao S， Xu Z. A sealed bid auction-based two-stage approach for a decentralized multiproject scheduling problem with resource transfers［J］. Applied Intelligence， 2022， 52（15）： 18081-18100.
[5]	刘婉君，张静文，刘万琳. 基于拍卖机制的资源转移时间型动态分布式多项目调度［J］. 中国管理科学， 2022， 30（8）： 117-129.
	Liu W J， Zhang J W， Liu W L. Dynamic decentralized resource-constrained multi-project scheduling problem with transfer times based on auction mechanism［J］. Chinese Journal of Management Science， 2022， 30（8）： 117-129.
[6]	赵松，徐哲，刘东宁. 考虑全局资源闲置成本的分布式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.
[7]	赵松，徐哲，刘东宁. 地域分散型多项目时间/成本权衡问题［J］. 中国管理科学， 2023， 31（9）： 62-72.
	Zhao S， Xu Z， Liu D N. Time/cost trade-off problem in decentralized multi-project scheduling［J］. Chinese Journal of Management Science， 2023， 31（9）： 62-72.
[8]	Chen H， Ding G， Zhang J， et al. A filtering genetic programming framework for stochastic resource constrained multi-project scheduling problem under new project insertions［J］. Expert Systems with Applications， 2022， 198： 116911.
[9]	Chen Z， Demeulemeester E， Bai S， et al. Efficient priority rules for the stochastic resource-constrained project scheduling problem［J］. European Journal of Operational Research， 2018， 270（3）： 957-967.
[10]	Zhou T， Long Q， Law K M Y， et al. Multi-objective stochastic project scheduling with alternative execution methods： An improved quantum-behaved particle swarm optimization approach［J］. Expert Systems with Applications， 2022， 203： 117029.
[11]	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.
[12]	Xie F， Li H， Xu Z. An approximate dynamic programming approach to project scheduling with uncertain resource availabilities［J］. Applied Mathematical Modelling， 2021， 97： 226-243.
[13]	Zhao S， Xu Z. 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.
[14]	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.
[15]	Deblaere F， Demeulemeester E， Herroelen W， et al. Robust resource allocation decisions in resource-constrained projects［J］. Decision Sciences， 2007， 38（1）： 5-37.
[16]	Pang N， Meng Q. Resource allocation in robust scheduling［J］. Journal of the Operational Research Society， 2023， 74（1）： 125-142.
[17]	Liang Y， Cui N， Hu X， et al. The integration of resource allocation and time buffering for bi-objective robust project scheduling［J］. International Journal of Production Research， 2020， 58（13）： 3839-3854.
[18]	Shi Y， Su H， Pang N. Resource flow network generation algorithm in robust project scheduling［J］. Journal of the Operational Research Society， 2021， 72（6）： 1294-1308.
[19]	胡振涛，崔南方，胡雪君，等. 集成时间缓冲与资源流的多技能项目鲁棒调度方法［J］. 系统管理学报， 2023， 32（5）： 916-926.
	Hu Z T， Cui N F， Hu X J， et al. Integrated time-and resource-based robust scheduling algorithm for multi-skilled projects［J］. Journal of Systems & Management， 2023， 32（5）： 916-926.
[20]	Van De Vonder S， Demeulemeester E， Herroelen W， et al. The trade-off between stability and makespan in resource-constrained project scheduling［J］. International Journal of Production Research， 2006， 44（2）： 215-236.
[21]	Van de Vonder S， Demeulemeester E， Herroelen W. Proactive heuristic procedures for robust project scheduling： An experimental analysis［J］. European Journal of Operational Research， 2008， 189（3）： 723-733.
[22]	Ma Y， He Z， Wang N， et al. Tabu search for proactive project scheduling problem with flexible resources［J］. Computers & Operations Research， 2023， 153： 106185.
[23]	Zhang J， Song X， Díaz E. Critical chain project buffer sizing based on resource constraints［J］. International Journal of Production Research， 2017， 55（3）： 671-683.
[24]	Tian W， Zhao Y， Demeulemeester E. Generating a robust baseline schedule for the robust discrete time/resource trade-off problem under work content uncertainty［J］. Computers & Operations Research， 2022， 143： 105795.
[25]	Zhang H， Ma R， He Z. Project scheduling cost optimization based on resource transfer costs and robustness［J］. Computers & Operations Research， 2024， 161： 106445.
[26]	You W， Xu Z， Yu Y， et al. A two-layer approach for solving robust decentralized multiproject scheduling problem with multi-skilled staff［J］. International Transactions in Operational Research， 2024， 31（3）： 1631-1670.
[27]	崔南方，梁洋洋. 基于资源流网络与时间缓冲集成优化的鲁棒性项目调度［J］. 系统工程理论与实践， 2018， 38（1）： 102-112.
	Cui N F， Liang Y Y. 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.
[28]	Van De Vonder S. Proactive-reactive procedures for robust project scheduling［M］.Norwell： Now Foundations and Trends， 2006.
[29]	Kerzner H. Project Management： A Systems Approach to Planning， Scheduling， and Controlling［M］. New York： Van Nostrand Reinhold， 1979.
[30]	梁洋洋，崔南方. 基于资源流网络优化的鲁棒性项目调度［J］. 系统管理学报， 2020， 29（2）： 335-345.
	Liang Y Y， Cui N F. Robust project scheduling based on optimization of resource flow network［J］. Journal of Systems & Management， 2020， 29（2）： 335-345.
[31]	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.
[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， 2021， 59（2）： 367-387.
[33]	Deblaere F， Demeulemeester E， Herroelen W. RESCON： Educational project scheduling software［J］. Computer Applications in Engineering Education， 2011， 19（2）： 327-336.

参数	取值
项目数	2，5
活动数	10，30
共享资源种类	2
资源因子（RF）	1
次序强度（OS）	0.3，0.5，0.7
资源受限程度（RC）	0.4，0.8
共享资源可用量	10