基于分布式资源配置的现金流动态均衡多项目调度优化

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

摘要/Abstract

摘要：

现实中的承包商往往要同时实施多个项目，在此过程中如何保持现金流出与流入的动态平衡是其必须解决的核心问题之一。本文针对这一现实背景，研究了基于分布式资源配置的现金流动态均衡多项目调度问题，其中，各单项目在局部资源约束下自主地安排其进度计划，而企业总部通过分配全局资源对进度安排施加影响，目标是最小化承包商的最大现金流缺口。首先，基于对研究问题的定义，构建了由局部项目调度子模型和全局资源安排子模型构成的资源约束多项目调度优化模型。其次，根据问题特点及性质，设计了模型求解的模拟退火与禁忌搜索混合算法。最后，在随机生成的标准算例集合上对算法进行了计算测试，并就关键参数对目标函数的影响进行了敏感性分析，得到如下结论：本文所设计的改进算法是在求解该问题所有算法中最为满意的算法；资源强度、项目截止时间及支付条件等参数均会对以承包商最大现金流缺口测度的现金流动态均衡状态产生重要影响。

关键词: 分布式多项目调度, 现金流动态均衡, 优化模型, 模拟退火, 禁忌搜索

Abstract:

In reality， a contractor often implements several projects concurrently while during this course， how to maintain a dynamic balance between cash outflows and cash inflows is a key issue for the contractor to deal with. It should be noted that over the course of the project， the distribution of cash flows is closely related to the arrangement of the project schedule. As a result， through reasonable project scheduling， the contractor can effectively coordinate cash outflows and inflows and thus best achieve a positive cash flow balance. Based on the realistic background aforementioned， this paper studies the decentralized resource-constrained multi-project scheduling problem with the objective of cash flow dynamic balance. In the problem， the schedule of each project is arranged under its local resource constraints whereas the enterprise headquarter exerts its impact on project scheduling through the allocation of global resources among different projects.First， based on the discussion of realistic and theoretical backgrounds of the research problem， a multi-project scheduling optimization model is constructed under the objective of minimizing the maximum cash flow gap of the contractor. The model consists of two submodels， namely local project scheduling submodel and global resource allocation submodel. The former optimally arranges schedule for each single project under the constraint of its local resources and based on the results obtained， the latter optimally allocates and coordinates global resources among multiple projects so as to realize the best dynamic balance between the contractor’s cash outflows and inflows. Through the analysis of the constructed model， three basic properties of the studied problem are proposed， thus providing supports for the effective solution of the problem.Second， due to the characteristic of the problem， which is NP-hard and includes two interrelated subproblems， a simulated annealing - tabu search algorithm is developed. In the algorithm， the local project scheduling subproblem is solved by a simulated annealing - tabu search algorithm， where a tabu list is employed to prevent the algorithm from visiting identical feasible solutions repeatedly at high temperature stage， while the global resource allocation subproblem is tackled using a sequential game based algorithm， which deals with global resource conflicts effectively by postponing the relevant activities. To enhance the searching efficiency of the developed algorithm， an improvement measure is designed for the algorithm for the local project scheduling subproblem based on the properties of the studied problem.Finally， in order to evaluate the performance of the algorithm and the effect of its improvement measure， a large-scale computational experiment is conducted on a data set generated randomly. In the experiment， taking the multi-start iteration improvement algorithm as the comparison algorithm， the two versions of the developed algorithm， i.e.， the simulated annealing - tabu search algorithm equipped with and without the improvement measure， are tested and the results are also compared with those obtained by the simulated annealing， tabu search， and multistart iteration improvement algorithms. Based on the computational results， the advantage of the simulated annealing - tabu search algorithm including the improvement measure over other algorithms is verified and through the sensitivity analysis of the impact of key parameters on the objective function， the trends of the maximum cash flow gap of individual projects and multiple projects varying with the parameters are discussed.The conclusions of the research in this paper are as follows： The simulated annealing - tabu search algorithm with the improvement measure is the most promising algorithm for the studied problem. The advantage of this algorithm over other algorithms grows with the increase in the activity number of project， local resource strength， and project deadline or the decrease in the local resource factor. The maximal cash flow gap in individual projects descends as the local resource strength， advance payment proportion， milestone activity number， and project deadline go up， while ascends as the local resource factor and discount rate climb. When the global resource factor drops or the global resource strength and project deadline grow， the increment of the maximal cash flow gap in multi-project， which is caused by handling global resource conflicts， decreases.

Key words: Decentralized multi-project scheduling, Dynamic balance of cash flows, Optimization model, Simulated annealing, Tabu search

中图分类号:

C935

何羽康,贾涛,郑维博. 基于分布式资源配置的现金流动态均衡多项目调度优化[J]. 中国管理科学, 2026, 34(2): 144-155.

Yukang He,Tao Jia,Weibo Zheng. Decentralized Resource Allocation Based Multi-project Scheduling Optimization to Dynamically Balance Cash Flows[J]. Chinese Journal of Management Science, 2026, 34(2): 144-155.

图/表 7

图1

表1

算例参数设置"

参数	设置	参数	设置
项目数 $H$	3	全局资源强度 $G R F$	0.5，0.75，1
项目非虚活动数 $n h$	10，20，40，60	全局资源因子 $G R F$	0.5，0.75，1
项目的开始和结束活动数	从2、3、4中按等概率随机选取	活动工期 $d i h$	从 $U [1,10]$ 中随机选取
项目的最大紧前紧后活动数	4	活动成本 $c i h$	从 $U [1,10]$ 中随机选取
局部资源种类数 $K$	4	项目预付款比例 $γ h$	0.05，0.1，0.15
局部资源因子 $L R F$	0.5，0.75，1	项目支付比例 $θ h$	0.8，0.85，0.9
局部资源强度 $L R S$	0.5，0.75，1	项目开始时间 $B T h$	从 $U [0,5]$ 中随机选取
全局资源种类数 $Q$	2	单位时期折现率 $α$	0.006，0.008，0.01
活动挣值 $v i h$	$ρ v ∙ c i h$ 。其中， $ρ v$ 是生成 $v i h$ 的专用参数，该参数的取值从 $U [1.3,1.5]$ 中随机其选取	项目里程碑活动	里程碑活动数 $M h$ 被设置为3、4、5，里程碑活动从项目的非虚活动中随机选取
活动对局部资源的需求量 $l r i h k$	从 $U [1,10]$ 中随机选取	项目截止时间 $D T h$	$A T h$ + $ρ D ∙ C P L$ 。其中， $ρ D$ 是生成 $D T h$ 的专用参数，该参数被设置为1.2、1.4、1.6； $C P L$ 为不考虑资源约束下的项目关键路径长度
活动对全局资源的需求量 $g r i h q$	从 $U [1,10]$ 中随机选取	项目截止时间 $D T h$

表1

表2

算法的计算结果"

参数	取值	SA-TS-IM			SA-TS			SA			TS			MSII			$∆ A R D 1$	$∆ A R D 2$	$∆ A R D 3$
参数	取值	$N B S$	$A R D$	$M R D$	$N B S$	$A R D$	$M R D$	$N B S$	$A R D$	$M R D$	$N B S$	$A R D$	$M R D$	$N B S$	$A R D$	$M R D$	$∆ A R D 1$	$∆ A R D 2$	$∆ A R D 3$
$n h$	10	5,334	1.66	2.81	3,063	5.10	9.65	2,979	6.44	9.92	3,561	6.26	12.09	1,854	13.37	26.20	3.44	4.78	4.60
	20	5,766	1.27	2.86	3,519	5.69	8.87	3,288	7.58	12.20	3,111	7.35	12.14	1,089	22.56	32.20	4.42	6.31	6.08
	40	6,174	1.15	2.34	3,900	6.72	10.73	3,207	8.36	14.26	2,697	9.26	17.64	258	37.18	52.07	5.57	7.21	8.11
	60	6,495	0.53	1.00	3,429	7.84	13.22	3,369	9.70	18.55	2,763	10.07	17.73	0	46.60	69.88	7.31	9.17	9.54
$L R F$	0.5	8,331	0.92	2.01	4,914	7.16	13.17	4,566	9.12	18.55	3,903	9.59	17.73	810	32.67	65.07	6.24	8.20	8.67
	0.75	7,995	1.16	2.27	4,722	6.75	13.22	4,182	8.26	13.50	3,933	7.85	12.59	1,137	29.60	69.88	5.59	7.10	6.69
	1	7,443	1.38	2.86	4,275	5.12	9.61	4,095	6.68	10.05	4,296	7.28	15.10	1,254	27.54	53.14	3.74	5.30	5.90
$L R S$	0.5	7,266	1.41	2.86	4,143	5.09	10.32	3,993	6.31	9.52	4,362	5.64	9.87	1,437	26.76	45.40	3.68	4.90	4.23
	0.75	8,055	1.22	2.26	4,755	6.55	13.22	4,215	8.38	15.18	3,978	8.54	15,72	1,113	28.78	56.95	5.33	7.16	7.32
	1	8,448	0.80	1.60	5,013	7.38	12.74	4,635	9.36	18.55	3,792	10.55	17.73	651	34.25	69.88	6.58	8.56	9.75
$ρ D$	1.2	7,383	1.33	2.86	4,278	5.64	11.13	4,080	6.80	12.58	4,419	6.33	11.66	1,368	25.74	48.14	4.31	5.47	5.00
	1.4	7,995	1.18	2.34	4,557	6.16	11.59	4,248	8.22	14.38	4,134	8.45	16.82	1,044	28.80	69.88	4.98	7.04	7.27
	1.6	8,391	0.95	1.92	5,076	7.25	13.22	4,515	9.08	18.55	3,579	9.96	17.73	789	35.25	66.03	6.30	8.13	9.01
全部算例		23,769	1.15	2.86	13,911	6.35	13.22	12,843	8.03	18.55	12,132	8.25	17.73	3,201	29.93	69.88	5.20	6.88	7.10

表2

图2

表3

参数LRF、LRS、γh、Mh、θh、ρD和α不同取值下的Gmaxh"

参数取值	$G m a x h$	参数取值	$G m a x h$	参数取值	$G m a x h$	参数取值	$G m a x h$	参数取值	$G m a x h$	参数取值	$G m a x h$	参数取值	$G m a x h$
$L R F$ =0.5	13.96	$L R S$ =0.5	18.59	$γ h$ =0.05	27.48	$M h$ =3	26.34	$θ h$ =0.8	26.02	$α$ =0.006	13.67	$ρ D$ =1.2	19.23
$L R F$ =0.75	14.93	$L R S$ =0.75	14.73	$γ h$ =0.1	13.62	$M h$ =4	14.70	$θ h$ =0.85	16.16	$α$ =0.008	15.43	$ρ D$ =1.4	14.72
$L R F$ =0.75	17.11	$L R S$ =1	12.70	$γ h$ =0.15	4.88	$M h$ =5	4.98	$θ h$ =0.9	3.80	$α$ =0.01	16.90	$ρ D$ =1.6	12.01

表3

表4

参数GRF、GRS和ρD不同取值下的∆Gmax"

参数取值	$∆ G m a x$	参数取值	$∆ G m a x$	参数取值	$∆ G m a x$
$G R F$ =0.5	1.75	$G R S$ =0.5	6.26	$ρ D$ =1.2	4.58
$G R F$ =0.75	3.61	$G R S$ =0.75	3.23	$ρ D$ =1.4	3.16
$G R F$ =0.75	4.81	$G R S$ =1	0.67	$ρ D$ =1.6	2.42

表4

图3

参考文献 29

[1]	Payne J H. Management of multiple simultaneous projects： A state-of-the-art review［J］. International Journal of Project Management，1995， 13（3）： 163-168.
[2]	李飞飞，徐哲，刘东宁，等. 分布式资源受限多项目调度问题研究综述［J］. 工业工程与管理， 2023， 28（5）： 199-210.
	Li F F， Xu Z， Liu D N， et al. A literature review of distributed resource-constrained multi-project scheduling problem［J］. Industrial Engineering and Management， 2023， 28（5）： 199-210.
[3]	Russell A H. Cash flows in networks［J］. Management Science， 1970， 16（5）： 357-373.
[4]	Smith-Daniels D E， Padman R， Smith-Daniels V L. Heuristic scheduling of capital constrained projects［J］. Journal of Operations Management， 1996，14（3）： 241-254.
[5]	何正文，刘人境，胡信布. 基于合同双方交互作用的项目调度优化［J］. 管理科学学报， 2014， 17（8）： 48-59.
	He Z W， Liu R J， Hu X B. Project scheduling optimization based on interaction between two parties of contracts［J］. Journal of Management Sciences in China， 2014， 17（8）： 48-59.
[6]	Leyman P， Vanhoucke M. Capital- and resource-constrained project scheduling with net present value optimization［J］. European Journal of Operational Research， 2017， 256（3）： 757-776.
[7]	梁洋洋，王田，崔南方. 基于资源流网络优化的Max-npv项目调度［J］.中国管理科学，2022，30（7）： 241-251.
	Liang Y Y， Wang T， Cui N F. Max—NPV project scheduling based on optimizing the resource flow network［J］. Chinese Journal of Management Science， 2022， 30（7）： 241-251.
[8]	何一丹，何正文，王能民，等. 共享经济环境下的资源约束Max-NPV多项目调度优化［J］. 中国管理科学， 2024， 32（9）： 260-270.
	He Y D， He Z W， Wang N M， et al. Resource-constrained max-NPV multi-project scheduling optimization under sharing economy environment［J］. Chinese Journal of Management Science，2024，32（9）： 260-270.
[9]	Rostami S， Creemers S， Leus R. Maximizing the net present value of a project under uncertainty： Activity delays and dynamic policies［J］. European Journal of Operational Research， 2024， 317（1）： 16-24.
[10]	Yazdani M， Aouam T， Vanhoucke M. An exact decomposition technique for the deadline-constrained discrete time/cost trade-off problem with discounted cash flows［J］. Computers & Operations Research， 2024， 163： 106491.
[11]	何华，曹芳芳，何正文，等. 双重资源约束下的净现值最大化多项目调度优化［J］. 中国管理科学， 2025，33（12）：146-159.
	He H， Cao FF， He ZW， et al. Max-NPV multi-project scheduling optimization under dual resource constraints［J］. Chinese Journal of Management Science， 2025，33（12）：146-159.
[12]	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.
[13]	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.
[14]	彭武良，陈良威，马雪丽. 分散式项目群调度的双目标优化方法研究［J］. 管理工程学报， 2021， 35（5）： 131-140.
	Peng W L， Chen L W， Ma X L. Research on the double-objective optimization for decentralized project group scheduling［J］. Journal of Industrial Engineering and Engineering Management，2021， 35（5）： 131-140.
[15]	刘婉君，张静文，刘万琳. 基于拍卖机制的资源转移时间型动态分布式多项目调度［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.
[16]	胡雪君，赵雁，单汩源，等. 基于自适应大邻域搜索的鲁棒多项目调度方法［J］. 中国管理科学， 2022， 30（9）： 217-231.
	Hu X J， Zhao Y， Shan G Y， et al. An adaptive large neighborhood search metaheuristic for robust multi-project scheduling［J］. Chinese Journal of Management Science， 2022， 30（9）： 217-231.
[17]	He Y， Jia T， Zheng W. Tabu search for dedicated resource-constrained multiproject scheduling to minimise the maximal cash flow gap under uncertainty［J］. European Journal of Operational Research， 2023， 310（1）： 34-52.
[18]	有维宝，徐哲，刘东宁. 基于拍卖谈判机制的分布式多技能多项目调度［J］. 运筹与管理， 2024， 33（1）： 1-8.
	You W B， Xu Z， Liu D N. An auction-based negotiation mechanism to distributed multi-skilled multi-project scheduling problem［J］. Operations Research and Management Science， 2024， 33（1）： 1-8.
[19]	Satic U， Jacko P， Kirkbride C. A simulation-based approximate dynamic programming approach to dynamic and stochastic resource-constrained multi-project scheduling problem［J］. European Journal of Operational Research， 2024， 315（2）： 454-469.
[20]	He Y， Jia T， Zheng W. Simulated annealing for centralised resource-constrained multiproject scheduling to minimise the maximal cash flow gap under different payment patterns［J］. Annals of Operations Research， 2024， 338（1）： 115-149.
[21]	Brucker P， Drexl A， Möhring R， et al. Resource-constrained project scheduling： Notation， classification， models， and methods［J］. European Journal of Operational Research， 1999， 112（1）： 3-41.
[22]	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.
[23]	Gómez Sánchez M， Lalla-Ruiz E， Fernández Gil A， et al. Resource-constrained multi-project scheduling problem： A survey［J］. European Journal of Operational Research， 2023， 309（3）： 958-976.
[24]	李飞飞，徐哲，于静. 基于序贯博弈谈判机制的分布式多项目调度［J］. 系统工程理论与实践， 2018（3）： 696-709.
	Li F F， Xu Z， Yu J. A sequential game-based negotiation approach to distributed multi-project scheduling problem［J］. Systems Engineering-Theory & Practice， 2018（3）： 696-709.
[25]	Blazewicz J， Lenstra J K， Kan A H G R. Scheduling subject to resource constraints： Classification and complexity［J］. Discrete Applied Mathematics， 1983， 5（1）： 11-24.
[26]	Pellerin R， Perrier N， Berthaut F. A survey of hybrid metaheuristics for the resource-constrained project scheduling problem［J］. European Journal of Operational Research， 2020， 280（2）： 395-416.
[27]	Kolisch R， Sprecher A. PSPLIB - A project scheduling problem library［J］. European Journal of Operational Research， 1997， 96（1）： 205-216.
[28]	Browning T R， Yassine A A. A random generator of resource-constrained multi-project network problems［J］. Journal of Scheduling， 2010， 13（2）： 143-161.
[29]	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.