地域分散型多项目时间/成本权衡问题

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

摘要/Abstract

摘要：

实践中多项目可能分散在不同的地域，制订多项目计划时全局资源在项目间的转移时间不能忽略；项目活动有不同的执行模式，投入的预算越多，活动工期越短。地域分散型多项目时间/成本权衡问题涉及总预算在项目间的合理分配、全局资源在项目间的转移以及预算约束下的项目工期优化问题。针对该问题特点设计一种遗传算法，对带有预算约束的局部项目调度问题进行求解，采用序贯博弈谈判机制协调总预算在多项目间的分配并制订全局资源转移计划。基于多项目标准算例集MPSPLIB开展实验研究，一方面，探究求解该问题的序贯博弈谈判机制的协调效果；另一方面，分析并讨论问题规模、资源冲突强度和总预算对全局目标值的影响。

关键词: 地域分散型多项目调度, 资源转移, 预算分配, 时间/成本权衡, 序贯博弈谈判机制

Abstract:

In practice， multiple projects may be located in different locations， therefore， the global resource transfer times cannot be neglected when making multi-project scheduling plans. Besides， project activities have different execution modes， activity durations can be shortened by increasing the budget. Both global resource transfer times and budget constraints are considered and the time/cost trade-off problem in decentralized multi-project scheduling is proposed.Based on a multi-agent system， a two-stage model including local scheduling model and global coordination model is constructed， each project agent （PA） independently schedules the corresponding single project under the allocated budget constraints to minimize the project makespan， and the coordination agent （CA） uses a coordination mechanism to eliminate budget competition conflicts to minimize average project delay （APD）. The local scheduling is the discrete time/cost trade-off problem under budget constraints （DTCTP-B）， a new genetic algorithm is designed to solve it. The sequential game negotiation mechanism is employed to coordinate the allocation of the total budget among multiple projects and make the global resource transfer plans.To evaluate the performance of the proposed algorithm， 45 instances are selected from MPSPLIB and converted into the problems studied in this paper. Experimental results show that compared with the heuristic method， the method proposed in this paper is more effective and can further reduce APD. The results of parameter analysis show that both problem size and global resource conflict degree have influences on the APD， and the influence of the global resource conflict degree is greater. Taking instance 2 of problem subset MP30_5 as an example， the influence of total budget input on APD is analyzed and discussed.

Key words: decentralized multi-project scheduling, resource transfers, budget allocation, time/cost trade-off, sequential game-based negotiation mechanism

中图分类号:

N945

赵松,徐哲,刘东宁. 地域分散型多项目时间/成本权衡问题[J]. 中国管理科学, 2023, 31(9): 62-72.

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.

图/表 16

表1

符号说明"

符号	说明
$s i j$	活动 $a i j$ 的开始时间
$P i$	项目 $i$ 中的活动优先关系集合
$B i$	分配给项目 $i$ 的预算
$L i$	项目 $i$ 的延期
$G$	全局资源种类
$t$	时刻
$A t$	时刻 $t$ 正在进行的活动集合
$r h l, i j g$	全局资源 $g$ 从活动 $a h l$ 转移到活动 $a i j$ 的数量
$Δ h l, i j, g$	全局资源 $g$ 从活动 $a h l$ 转移到活动 $a i j$ 消耗的时间
$D i$	项目 $i$ 的截止日期

表1

图1

图2

图3

图4

图5

图6

表2

表3

表4

图7

图8

图9

表5

图10

表6

参考文献 23

1	Kruger D， Scholl A. Managing and modeling general resource transfers in （multi） project scheduling［J］. OR Spectrum， 2010， 32（2）： 369-394.
2	Kadri R L， Boctor F F. An efficient genetic algorithm to solve the resource-constrained project scheduling problem with transfer times： the single mode case［J］. European Journal of Operational Research， 2018， 265（2）： 454-462.
3	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.
4	刘婉君，张静文，刘万琳．基于拍卖机制的资源转移时间型动态分布式多项目调度［J］．中国管理科学，2022，30（8）：117-129.
	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， 2022， 30（8）：117-129.
5	赵松，徐哲，刘东宁. 考虑全局资源闲置成本的分布式RCMPSPTT［J］. 系统工程理论与实践， 2020， 40（7）： 1882-1894.
	Zhao Song， Xu Zhe， Liu Dongning. Decentralized RCMPSPTT with cost of idleness［J］. Systems Engineering-Theory & Practice. 2020， 40（7）： 1882-1894.
6	Li Feifei， Xu Zhe， Li Haitao. A multi-agent based cooperative approach to decentralized multi-project scheduling and resource allocation［J］. Computers & Industrial Engineering， 2021， 151： 106916.
7	Choi B， Park M. A continuous time-cost tradeoff problem with multiple milestones and completely ordered jobs［J］. European Journal of Operational Research， 2015， 244 （3）： 748-752.
8	Hochbaum D S. A polynomial time repeated cuts algorithm for the time cost tradeoff problem： the linear and convex crashing cost deadline problem［J］. Computers & Industrial Engineering， 2016， 95：64-71.
9	Zhang Qian， Zou Xin. A heuristic procedure for solving discrete time-cost tradeoff problems in repetitive projects［J］. Journal of Physics： Conference Series， 2019， 1168： 032099.
10	Ghoddousi P， Eshtehardian E， Jooybanpour S， et al. Multi-mode resource-constrained discrete time–cost-resource optimization in project scheduling using non-dominated sorting genetic algorithm［J］. Automation in Construction， 2013， 30（MAR.）： 216-227.
11	Ballesteros-Pérez P， Elamrousy K M， González-Cruz M C. Non-linear time-cost trade-off models of activity crashing： application to construction scheduling and project compression with fast-tracking［J］. Automation in Construction， 2019， 97（January）： 229-240.
12	Mahmoudi A， Javed S A. Project scheduling by incorporating potential quality loss cost in time-cost tradeoff problems： the revised KKH model［J］. Journal of Modelling in Management， 2020， 15（3）： 1187-1204.
13	张维迎. 博弈论与信息经济学［M］. 上海：上海人民出版社， 2004.
	Zhang Weiying. Game theory and information economics［M］. Shanghai： Shanghai People’s Publishing House， 2004.
14	邹宗保，王建军，邓贵仕. 再制造外包对供应链成员决策的影响［J］. 系统工程学报， 2017， 32（6）： 783-793.
	Zou Zongbao， Wang Jianjun， Deng Guishi. Influence of outsourcing remanufacturing on supply chain members' decisions［J］. Journal of Systems Engineering， 2017， 32（6）： 783-793.
15	Li Feifei， Xu Zhe. A multi-agent system for distributed multi-project scheduling with two-stage decomposition［J］. PLoS One， 2018， 13（10）： e0205445.
16	Choi B， Chung J. Complexity results for the linear time-cost tradeoff problem with multiple milestones and completely ordered jobs［J］. European Journal of Operational Research， 2014， 236 （1）： 61-68.
17	Ma Guofeng， Zhang Lingzhi. Exact overlap rate analysis and the combination with 4D BIM of time-cost tradeoff problem in project scheduling［J］. Advances in Civil Engineering， 2019， 2019（91）： 1-12.
18	Heravi G， Moridi S. Resource-constrained time-cost tradeoff for repetitive construction projects［J］. KSCE Journal of Civil Engineering， 2019， 23（8）： 3265-3274.
19	Goncharov E N， Leonov V V. Genetic algorithm for the resource-constrained project scheduling problem［J］. Automation and Remote Control， 2017， 78（6）： 1101-1114.
20	Ren Yifei， Lu Zhiqiang， Liu Xinyi. A branch-and-bound embedded genetic algorithm for resource-constrained project scheduling problem with resource transfer time of aircraft moving assembly line［J］. Optimization Letters， 2020， 14： 2161-2195.
21	谢芳，徐哲，于静. 柔性资源约束下的项目调度问题双目标优化［J］. 系统工程理论与实践， 2016， 36（3）： 674-683.
	Xie Fang， Xu Zhe， Yu Jing. Bi-objective optimization for the project scheduling problem with variable resource availability［J］. Systems Engineering-Theory & Practice， 2016， 36（3）： 674-683.
22	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.
23	刘东宁，徐哲，李飞飞. 基于合作博弈协商机制的分布式资源受限多项目调度［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.

MP30_5	序贯博弈谈判机制		启发式方法
MP30_5	预算分配顺序（项目号）	平均项目延期（天）	预算分配顺序（项目号）	平均项目延期（天）
算例1	(3,2,5,4,1)	67.3	(1,2,3,4,5)	71.7
算例2	(3,1,4,5,2)	54.5	(1,2,4,3,5)	50.7
算例3	(1,4,5,3,2)	86.3	(2,1,4,3,5)	95.1
算例4	(3,2,1,5,4)	13.5	(5,2,4,1,3)	15.9
算例5	(1,5,4,2,3)	87.2	(3,1,5,2,4)	93.8

问题集	APD¹（天）	APD⁰（天）	GAP(%)
MP30_2	35.9	42.1	-14.73
MP30_5	61.76	65.44	-5.62
MP30_10	245.91	266.51	-7.73
MP90_2	32	35.7	-10.36
MP90_5	35.06	39.14	-10.42
MP90_10	151.54	165.5	-8.44
MP120_2	140.75	146.15	-3.69
MP120_5	158.92	177.36	-10.40
MP120_10	367.95	395.75	-7.02

问题集	AUF
MP30_2	0.84
MP30_5	0.82
MP30_10	2.38
MP90_2	0.57
MP90_5	0.61
MP90_10	1.14
MP120_2	1.31
MP120_5	1.32
MP120_10	1.91

项目	到达时间	截止日期	活动	活动执行的工期模式（月）	活动执行模式对应的成本（万元）
项目1	0	7.5	1	[0,0,0,0,0]	[0,0,0,0,0]
			2	[2-6]	[45,40,35,30,25]
			3	[1-5]	[50,45,40,35,30]
			4	[3-7]	[40,35,30,25,20]
			5	[0,0,0,0,0]	[0,0,0,0,0]
项目2	5	11	1	[0,0,0,0,0]	[0,0,0,0,0]
			2	[3-7]	[40,35,30,25,20]
			3	[3-7]	[40,35,30,25,20]
			4	[1-5]	[50,45,40,35,30]
			5	[0,0,0,0,0]	[0,0,0,0,0]
项目3	10	13	1	[0,0,0,0,0]	[0,0,0,0,0]
			2	[2-6]	[45,40,35,30,25]
			3	[1-5]	[50,45,40,35,30]
			4	[1-5]	[50,45,40,35,30]
			5	[0,0,0,0,0]	[0,0,0,0,0]

参与博弈的项目顺序	平均项目延期（月）
（项目1，项目2，项目3）	4.5
（项目1，项目3，项目2）	7.83
（项目2，项目1，项目3）	10.5
（项目2，项目3，项目1）	11.17
（项目3，项目1，项目2）	7.17
（项目3，项目2，项目1）	12.17