双重资源约束下的净现值最大化多项目调度优化

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

Abstract

Abstract:

In reality， the implementation of multiple projects often involves two types of resources， namely， renewable and non-renewable resources. Renewable resources include labor， machinery， and facilities that are not depleted and can be reused during project execution. Therefore， these resources have a defined availability on a per-unit time. On the other hand， non-renewable resources typically consist of raw materials， components， and funding， which are consumed once they are invested in a single-project and cannot be reused for other projects. Hence， the availability of non-reusable resources is defined for the entire duration of the project. In a multi-project environment， if a renewable resource for a specific project is idle during a certain period， it can be shared with other projects， making it a global resource. Conversely， for non-renewable resources， temporary surpluses in a single project are generally not shared with others， treating them as local resources.It is noteworthy that during the project implementation process， activities generally have multiple execution modes based on the type and quantity of resources invested， leading to different durations and costs. Overall， the choice of activity modes is constrained by the project budget. Project budgets fall under the category of non-renewable resources， with availability defined over the entire project cycle， once invested in the project， they cannot be reused. Therefore， in terms of non-renewable resources， managers need to allocate them reasonably to individual projects to ensure the smooth completion of projects and the ultimate achievement of expected goals.This research delves into the multi-project resource-constraint scheduling problem， specifically tackling the challenge of optimizing net present value （NPV） under dual resource constraints-renewable and non-renewable resources. The objective revolves around allocating non-renewable resources to individual projects， determining activity modes based on the availability of these resources， and subsequently scheduling activity starting times within the confines of shared renewable resource availability. Therefore， managers are tasked with manipulating three sets of decision variables-non-renewable allocation for individual projects， activity modes， and starting times of activities for a single project-to maximize the NPV of multiple projects.In the subsequent sections， a literature review is conducted to demonstrate the theoretical significance of this research. Next， an optimization model for maximizing net present value in multi-project scheduling under dual resource constraints is constructed， and the basic properties of the model are analyzed. Subsequently， a three-tier nested tabu search heuristic algorithm for solving the model is designed， and improvement measures for the algorithm are proposed based on proposed properties. Finally， extensive computational experiments are conducted to validate the model and the algorithm. Results have shown that the three-tier nested tabu search algorithm with improvement measures proves to be the most effective algorithm for solving the problem of maximizing net present value in multi-project scheduling under dual resource constraints. Additionally， sensitivity analysis reveals： the renewable resource factor （RF） has a negative impact on NPV， while RS positively affects NPV. As project deadlines， the number of milestones， intermediate payment ratios， and advance payment ratios increase， project net present value also increases. However， the discount rate negatively influences net present value. An increase in non-renewable resources contributes to the improvement of NPV in multi-projects.

Key words: multi-project scheduling, Max-NPV, optimization model, tabu search algorithm, dual resource constraint

CLC Number:

C935

Hua He,Zhengwen He,Fangfang Cao, et al. Max-NPV Multi-project Scheduling Optimization under Dual Resource Constraints[J]. Chinese Journal of Management Science, 2025, 33(12): 146-159.

Figures/Tables 10

符号	定义	符号	定义
q	项目序号，q=1, 2, …, Q，Q为项目总数	Ω	多项目进度计划安排，Ω=(Ω¹, Ω²,…, Ω^Q )
N^q	项目q网络节点集合，由项目活动构成	NPV^q	项目q的净现值，NPV^q =NPV⁺^q ‒NPV^‒^q
A^q	项目q网络箭线集合，由活动优先关系构成	NPV	所有Q个项目的净现值总和
n^q	项目q中的实活动总数	CPL^q	项目q活动网络关键路径的长度
BT^q	项目q规定的开始时间	$L B_R w v q$	项目q对不可重复使用本地资源w的需求量下界
DT^q	项目q规定的截止时间	$U B_R w v q$	项目q对不可重复使用本地资源w的需求量上界
i, j	项目活动序号，i, j∈N^q	ζ^q	项目q对承包商收益的贡献度
o	项目活动执行模式序号，o=1, 2, …, O_i	init_R^v	算法上层模块的问题初始解
k	可重复使用全局资源序号，k=1, 2, …, K	curr_R^v	算法上层模块的问题当前解
w	不可重复使用本地资源序号，w=1, 2, …, W	neig_R^v	算法上层模块的问题邻点解
$r i o k ρ$	活动i以模式o执行时对可重复使用全局资源k的需求量	TLL^upp	算法上层模块的禁忌列表长度
$r i o w v$	活动i以模式o执行时对不可重复使用本地资源w的需求量	$N u m s t o p u p p$	算法上层模块需探测可行R^v 的总数
d_io	活动i以模式o执行时的工期	init_Π^q	算法中层模块的问题初始解
c_io	活动i以模式o执行时的成本	curr_Π^q	算法中层模块的问题当前解
v_i	活动i的挣值	neig_Π^q	算法中层模块的问题邻点解
TCP^q	项目q的合同总价格	TLL^mid	算法中层模块的禁忌列表长度
$γ q$	项目q的预付款比例	$N u m s t o p m i d$	算法中层模块需探测可行Π^q 的总数
θ^q	项目q的中间支付比例	init_S^q	算法下层模块的问题初始解
M^q	项目q的里程碑活动数	curr_S^q	算法下层模块的问题当前解
$R k ρ$	可重复使用全局资源k的总可用量	neig_S^q	算法下层模块的问题邻点解
$R w v$	不可重复使用本地资源w的总可用量	TLL^low	算法下层模块的禁忌列表长度
$R w v q$	分配给项目q的不可重复使用资源w的可用量	$N u m s t o p l o w$	算法下层模块需探测可行S^q 的总数
R^v	不可重复使用本地资源分配结果向量	NBS	算法得到与已知最好解相同的满意解的数量
o_i	决策变量，活动i的执行模式	ARD	算法得到的满意解与已知最好解的平均相对偏差
Π^q	项目q的活动执行模式向量，Π^q = $(o 0, o 1, …, o n q + 1)$	MRD	算法得到的满意解与已知最好解的最大相对偏差
s_i	决策变量，活动i的开始时间	ACT	算法得到的满意解的平均计算时间
S^q	项目q的活动开始时间向量，S^q = $(s 0, s 1, …, s n q + 1)$	MCT	算法得到的满意解的最大计算时间

算例参数	取值设置
项目数Q	3
单项目中的非虚活动数n^q	10，20，30
单项目中的开始和结束活动数	从2、3和4中按等概率随机选取
单项目中的最大紧前紧后活动数	4
可重复使用全局资源种类数K	2
不可重复使用本地资源种类数W	2
活动执行模式数O_i	2
执行模式1下的d_i₁，c_i₁， $r i 1 k ρ$ ， $r i 1 w v$	从U[1, 10]中随机选取
执行模式2下的活动工期d_i₂	λ_d ·d_i₁，其中，λ_d 为生成d_i₂的专用参数，取值从U[0.7, 0.9]中随机选取
执行模式2下的活动成本c_i₂	λ_c ·c_i₁，其中，λ_c 为生成c_i₂的专用参数，取值从U[1.1, 1.3]中随机选取
执行模式2下的可重复使用全局资源需求量 $r i 2 k ρ$	$λ r ρ$ · $r i 1 k ρ$ ，其中， $λ r ρ$ 为生成 $r i 2 k ρ$ 的专用参数，取值从U[1.1, 1.3]中随机选取
执行模式2下的不可重复使用本地资源需求量 $r i 2 w v$	$λ r v$ · $r i 1 w v$ ，其中， $λ r v$ 为生成 $r i 2 w v$ 的专用参数，取值从U[1.1, 1.3]中随机选取
活动挣值v_i	λ_v ·(c_i₁+c_i₂)/2，其中，ρ_v 为生成v_i 的专用参数，取值从U[1.5, 1.8]中随机选取
资源因子RF	0.5，0.75，1
资源强度RS	0.5，0.75，1，基于两种执行模式下的资源需求的平均值计算
不可重复使用本地资源总量 $R w v$	$λ R v ⋅ [∑ i ∈ N q (r i 1 w v + r i 2 w v) / 2]$ ，其中 $λ R v$ 为生成 $R w v$ 的参数， $λ R v$ ={0.9,1.1,1.3}
单项目里程碑活动数M^q	3，4，5，里程碑活动从项目的非虚活动中按等概率随机选取
单项目预付款比例γ^q	0.05，0.1，0.15
单项目中间支付比例θ^q	0.8，0.85，0.9
单项目开始时间BT^q	从U[0, 5]中随机选取
折现率α	0.006，0.008，0.010
单项目截止时间DT^q	BT^q +ρ_D ·( $C P L 1 q$ + $C P L 2 q$ )。ρ_D= {1.2,1.4,1.6}； $C P L 1 q$ 和 $C P L 2 q$ 为在不考虑资源约束下，所有活动均采用执行模式1和执行模式2的关键路径的长度

参数	取值	NPV	参数	取值	NPV	参数	取值	NPV	参数	取值	NPV
RF	0.5	115.98	RS	0.5	102.10	ρ_D	1	103.57	$λ R v$	0.9	100.98
	0.75	106.26		0.75	106.18		1.2	112.84		1.1	109.72
	1	103.55		1	107.52		1.4	115.27		1.3	115.34
M^q	3	102.10	γ^q	0.05	99.44	θ^q	0.8	100.67	α	0.006	109.41
	4	106.89		0.1	105.89		0.85	104.12		0.008	105.95
	5	110.27		0.15	110.23		0.90	106.31		0.010	103.48

参数	平方和	自由度	均方	F	p	参数	平方和	自由度	均方	F	p
RF	6240.54	2	3120.27	525.47	0.00^**	M^q	7374.42	2	3687.21	620.94	0.00^**
RS	4416.65	2	2208.33	371.89	0.00^**	γ^q	2216.88	2	1108.44	186.67	0.00^**
ρ_D	4396.85	2	2198.43	1370.22	0.00^**	θ^q	2881.08	2	11440.54	5242.59	0.00^**
$λ R v$	6448.90	2	3224.45	543.01	0.00^**	α	92667.09	2	46333.54	7802.75	0.00^**
^**p<0.01

References 33

[1]	Kolisch R， Padman R. An integrated survey of deterministic project scheduling［J］. Omega， 2001， 29（3）： 249-272.
[2]	Amirian H， Sahraeian R. Solving a grey project selection scheduling using a simulated shuffled frog leaping algorithm［J］. Computers & Industrial Engineering， 2017， 107： 141-149.
[3]	Fu F， Zhou H. A combined multi-agent system for distributed multi-project scheduling problems［J］. Applied Soft Computing， 2021， 107： 107402.
[4]	Ahmeti A， Musliu N. Hybridizing constraint programming and meta-heuristics for multi-mode resource-constrained multiple projects scheduling Problem［J］. Journal of Heuristics， 2025， 31（1）： 1-37.
[5]	Wauters T， Kinable J， Smet P， et al. The multi-mode resource-constrained multi-project scheduling problem［J］. Journal of Scheduling， 2016， 19（3）： 271-283.
[6]	Geiger M J. A multi-threaded local search algorithm and computer implementation for the multi-mode， resource-constrained multi-project scheduling problem［J］. European Journal of Operational Research， 2017， 256（3）： 729-741.
[7]	于懿宁，徐哲，刘东宁. 考虑多技能人力资源的分布式多项目调度问题［J］. 系统工程理论与实践， 2020， 40（11）： 2921-2933.
	Yu Y N， Xu Z， Liu D N. Distributed multi-project scheduling problem with multi-skilled staff［J］. Systems Engineering-Theory & Practice， 2020，40（11）： 2921-2933.
[8]	于懿宁，徐哲，赵松，等. 考虑员工请假情形的多技能分布式资源受限多项目反应型调度优化［J］. 中国管理科学， 2025， 33（8）： 131-143.
	Yu Y N， Xu Z， Zhao S， et al. Research on the distributed resource-constrained multi-project reactive scheduling problem considering multi-skilled staff leave［J］. Chinese Journal of Management Science， 2025， 33（8）： 131-143.
[9]	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.
[10]	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.
[11]	张静文，刘婉君，李琦. 基于关键链改进搜索的遗传算法求解分布式多项目调度［J］. 运筹与管理， 2021， 30（3）： 123-129.
	Zhang J W， Liu W J， Li Q. An adapted genetic algorithm based on the critical chain with improving search to solve the decentralized resource-constrained multi-project scheduling problem［J］. Operations Research and Management Science， 2021， 30（3）： 123-129.
[12]	刘婉君，张静文，刘万琳. 基于拍卖机制的资源转移时间型动态分布式多项目调度［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.
[13]	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.
[14]	Chakrabortty R K， Sarker R A， Essam D L. Resource constrained multi-project scheduling： A priority rule based evolutionary local search approach［C］//Proceedings of Intelligent and Evolutionary Systems： The 20th Asia Pacific Symposium， IES 2016， Canberra， Australia， November， Cham： Springer International Publishing， 2016.
[15]	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.
[16]	Chiu H N， Tsai D M. An efficient search procedure for the resource-constrained multi-project scheduling problem with discounted cash flows［J］. Construction Management and Economics， 2002， 20（1）： 55-66.
[17]	Węglarz J， Józefowska J， Mika M， et al. Project scheduling with finite or infinite number of activity processing modes–A survey［J］. European Journal of Operational Research， 2011， 208（3）： 177-205.
[18]	Hartmann S， Briskorn D. An updated survey of variants and extensions of the resource-constrained project scheduling problem［J］. European Journal of Operational Research， 2022， 297（1）： 1-14.
[19]	Schwindt C， Zimmermann J. Handbook on project management and scheduling Vol.1［M］. Cham： Springer International Publishing， 2015.
[20]	Can A， Ulusoy G. Multi-project scheduling with two-stage decomposition［J］. Annals of Operations Research， 2014， 217（1）： 95-116.
[21]	Cui L， Liu X， Lu S， et al. A variable neighborhood search approach for the resource-constrained multi-project collaborative scheduling problem［J］. Applied Soft Computing， 2021， 107： 107480.
[22]	Beşikci U， Bilge Ü， Ulusoy G. Multi-mode resource constrained multi-project scheduling and resource portfolio problem［J］. European Journal of Operational Research， 2015， 240（1）： 22-31.
[23]	赵松，徐哲，刘东宁，等. 地域分散型多项目时间/成本权衡问题［J］.中国管理科学，2023， 31（9）： 62-72.
	Zhao S， Xu Z， Liu D N， et al. Time/cost trade-off problem in decentralized multi-project scheduling［J］. Chinese Journal of Management Science， 2023， 31（9）： 62-72.
[24]	Wauters T， Kinable J， Smet P， et al. The multi-mode resource-constrained multi-project scheduling problem［J］. Journal of Scheduling， 2016， 19（3）： 271-283.
[25]	Voß S， Witt A. Hybrid flow shop scheduling as a multi-mode multi-project scheduling problem with batching requirements： A real-world application［J］. International Journal of Production Economics， 2007， 105（2）： 445-458.
[26]	Sprecher A， Drexl A. Multi-mode resource-constrained project scheduling by a simple， general and powerful sequencing algorithm 1［J］. European Journal of Operational Research， 1998， 107（2）： 431-450.
[27]	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.
[28]	Schwindt C， Zimmermann J. Handbook on project management and scheduling Vol.1［M］. Cham： Springer International Publishing， 2015.
[29]	Movahedian A O， Esmaelian M， Mohammadi Z D. Multi-mode resource constrained multi-project selecting and scheduling problem to maximize net present value［J］. Journal of Industrial Management Perspective， 2016， 20（5）： 79-100.
[30]	Mika M， Waligóra G， Węglarz J. Tabu search for multi-mode resource-constrained project scheduling with schedule-dependent setup times［J］. European Journal of Operational Research， 2008， 187（3）： 1238-1250.
[31]	Waligóra G. Discrete-continuous project scheduling with discounted cash flows—a tabu search approach［J］. Computers & Operations Research， 2008， 35（7）： 2141-2153.
[32]	Kolisch R， Sprecher A， Drexl A. Characterization and generation of a general class of resource-constrained project scheduling problems［J］. Management Science， 1995， 41（10）： 1693-1703.
[33]	Kolisch R， Sprecher A. PSPLIB - A project scheduling problem library［J］. European Journal of Operational Research， 1997， 96（1）： 205-216.

文献	目标函数				资源约束			活动执行模式
文献	工期	成本	净现值	其他	可重复使用资源 (全局共享)约束	不可重复使用资源 (局部非共享)约束	双重资源约束	单模式	多模式
Amirian和Sahraeian(2017)^[2]		√		√	√			√
Fu和Zhou(2021)^[3]		√				√		√
Ahmeti和Musliu(2021)^[4]	√						√		√
Wauters等(2015)^[5]	√						√		√
Geiger(2017)^[6]	√						√		√
于懿宁等(2020)^[7]	√				√			√
于懿宁等(2023)^[8]		√			√			√
Adhau等(2012)^[9]	√	√					√	√
Adhau等(2013)^[10]	√						√	√
张静文等(2017)^[11]	√						√	√
刘婉君等(2017)^[12]	√						√	√
Browning和Yassine(2010)^[13]	√				√			√
Chakrabortty等(2017)^[14]	√				√			√
Vázquez等(2015)^[15]	√				√			√
Chiu和Tsai(2002)^[16]			√		√			√
Can和Ulusoy(2014)^[20]	√						√		√
Cui等(2021)^[21]	√				√			√
Beşikci等(2017)^[22]	√						√		√
赵松等(2021)^[23]	√	√					√		√
Wauters等(2016)^[24]	√						√	√
Voß和Witt(2007)^[25]	√						√		√
Sprecher和Drexl^[26]	√				√				√
Asta等(2016)^[27]	√						√		√
本文			√				√		√

n^q	TS-IM					TS-NIM
n^q	NBS	ARD	MRD	ACT	MCT	NBS	ARD	MRD	ACT	MCT
10	4439	0.08	0.50	4077.37	6874.8	2075	0.12	0.66	3488.54	5277.42
20	5291	0.05	0.64	8199.18	10061.44	1254	0.17	0.87	7910.32	9378.36
30	5982	0.01	0.51	13776.4	14088.52	579	0.25	0.91	12743.17	13982.13
所有算例	15712	0.05	0.64	8684.32	14088.52	3908	0.18	0.91	8047.34	13982.13
n^q	MSII					RS
n^q	NBS	ARD	MRD	ACT	MCT	NBS	ARD	MRD	ACT	MCT
10	47	0.19	0.92	3033.03	4488.84	0	0.28	0.99	2555.32	3932.79
20	16	0.26	0.99	5377.24	6318.75	0	0.31	0.99	4655.11	6076.11
30	0	0.37	1	10010.01	10382.97	0	0.44	1	9432.43	9642.74
所有算例	63	0.27	1	6140.09	10382.97	0	0.34	1	5547.62	9642.74

Max-NPV Multi-project Scheduling Optimization under Dual Resource Constraints

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 33

Related Articles 15

Metrics

Comments

Recommended 0

[1]	Baofeng Tian, Jingwen Zhang, Lubo Li, Junjie Chen. Integrated Resource-constrained Project Scheduling and Material Ordering Problem with Limited Storage Space [J]. Chinese Journal of Management Science, 2025, 33(8): 144-155.
[2]	Xiao Cui, Zhengwen He, Nengmin Wang. Optimization of Reactive Project Scheduling with Stochastic Resource Requirements Considering Information Handling Input [J]. Chinese Journal of Management Science, 2025, 33(8): 218-229.
[3]	Song Xue, Xu Chen, Chao Li, Jingchun Feng. Research on Miniature Multi-Project Scheduling of Service Project Enterprises Considering the Evolution of Human Resources Skills [J]. Chinese Journal of Management Science, 2025, 33(6): 96-104.
[4]	Yanting Wang, Weibo Zheng, Zhiqiang Ma, Zhengwen He. Robustness Threshold-based Max-NPV Project Scheduling Optimization on Different Clients’ Payment Modes [J]. Chinese Journal of Management Science, 2025, 33(4): 185-196.
[5]	Lei Zhu, Yaofeng Cui, Jiarui Wang, Jiahao Wu. Dynamic Optimization Model for Renewable Resource Development: An Example of Onshore Wind [J]. Chinese Journal of Management Science, 2025, 33(11): 336-344.
[6]	Yidan He,Zhengwen He,Nengmin Wang,Zhiqiang Ma. Resource-constrained Max-NPV Multi-project Scheduling Optimization under Sharing Economy Environment [J]. Chinese Journal of Management Science, 2024, 32(9): 260-270.
[7]	Jingchun Feng,Yaqi Yan,Ke Zhang,Daisong Hu. Robust Optimization Model of Water Environment Treatment Portfolio of Big Rivers for Maximizing Enterprise Income——Taking Yangtze River Protection as an Example [J]. Chinese Journal of Management Science, 2024, 32(6): 323-334.
[8]	Song ZHAO, Zhe XU, Dong-ning LIU. Time/Cost Trade-off Problem in Decentralized Multi-project Scheduling [J]. Chinese Journal of Management Science, 2023, 31(9): 62-72.
[9]	Wu-liang PENG,Liang-wei CHEN. A Program Cascade Optimization Scheduling Method [J]. Chinese Journal of Management Science, 2023, 31(10): 146-152.
[10]	GE Xian-long, WEN Peng-zhe, XUE Gui-qin. Two-echelon Dynamic Vehicle Routing Problem with Request Forecasting [J]. Chinese Journal of Management Science, 2022, 30(8): 210-220.
[11]	MA Zhi-qiang, XU Xiao-feng, HE Zheng-wen, WANG Neng-min. Robust Scheduling Optimization of Project Resources with Activity Splitting under Complex and Uncertain Environments [J]. Chinese Journal of Management Science, 2022, 30(3): 117-130.
[12]	ZHEN Lu, TAN Zhe-yi, XIAO Li-yang, MA Cheng-le. Research on Parcel Sorting Optimization Model and Algorithm for Double-layer Automatic Sorting Systems [J]. Chinese Journal of Management Science, 2021, 29(7): 171-180.
[13]	ZHANG Meng-ling, WANG Jing, HUANG Jun. Research on Robust Optimization of Emergency Resource Allocation Based on Supplier Participation Mechanism under Uncertain Demand [J]. Chinese Journal of Management Science, 2020, 28(7): 102-111.
[14]	MA Yong, HE Zheng-wen, ZHENG Wei-bo. Proactive Project Scheduling Optimization Based on Flexible Resource Constraint [J]. Chinese Journal of Management Science, 2020, 28(7): 220-230.
[15]	CUI Yu-quan, LIU Bing-jie, LIU Cong, QU Jing-jing. Optimization Model Analysis of New Order Agricultural Cooperation Model [J]. Chinese Journal of Management Science, 2020, 28(12): 140-150.