带有活动重叠的项目调度问题新算法: 分支定界法

doi:10.15960/j.cnki.issn.1007-6093.2023.01.008

运筹学学报 ›› 2023, Vol. 27 ›› Issue (1): 115-126.doi: 10.15960/j.cnki.issn.1007-6093.2023.01.008

带有活动重叠的项目调度问题新算法: 分支定界法

于静¹, 徐哲²^,*(), 谢芳³

1. 天津理工大学管理学院, 天津 300384
2. 北京航空航天大学经济管理学院, 北京 100191
3. 山东工商学院金融学院金融服务转型升级协同创新中心, 山东烟台 264005

收稿日期:2020-11-13 出版日期:2023-03-15 发布日期:2023-03-16
通讯作者: 徐哲 E-mail:xuzhebuaa@163.com
作者简介:徐哲, E-mail: xuzhebuaa@163.com
基金资助:
教育部人文社会科学青年基金(16YJC630159);教育部人文社会科学青年基金(17YJC630177);国家自然科学基金(71571005)

A branch and bound method for project scheduling problem with activities overlapping

Jing YU¹, Zhe XU²^,*(), Fang XIE³

1. School of Management, Tianjin University of Technology, Tianjin 300384, China
2. School of Economics and Management, Beihang University, Beijing 100191, China
3. Collaborative Innovation Center for Financial Service Transformation and Upgrading, College of Finance, Shandong Technology and Business University, Yantai 264005, Shandong, China

Received:2020-11-13 Online:2023-03-15 Published:2023-03-16
Contact: Zhe XU E-mail:xuzhebuaa@163.com

摘要/Abstract

摘要：

在复杂产品研发项目中, 通常采用活动重叠的方式来缩短工期, 带有活动重叠的资源受限项目调度问题的求解多以启发式算法为主, 该方法虽然具有收敛速度快、计算规模大等优点, 但无法得到最优解, 而精确算法是求解上述问题最优解的有效方法。基于此, 本文在深入分析活动重叠对项目调度影响的基础上, 设计了分支定界法以获得最优解。首先, 从理论上证明了算法的最优性, 一是对仅考虑最小延迟替代集即可得到最优解进行了证明; 二是对割集支配规则与左移支配规则在剪枝操作中的应用进行了证明。其次, 在算法设计上采用数据结构——栈对搜索树上的节点信息进行存储, 并针对活动重叠约束, 定义了新的决策时刻点和新的搜索树节点的表示方法。最后, 通过大量的算例实验分析验证了算法的可行性和有效性。综上, 本文提出的算法具备成熟的理论意义与精准的计算结果, 具有较高的研究价值。

关键词: 项目调度, 活动重叠, 分支定界法, 栈

Abstract:

In the complex product research and experimental development project, activities overlapping is usually used to shorten project duration. Currently, most methods for resource constrained project scheduling problem with activities overlapping are based on heuristic algorithm. This method has the advantages of fast-speed convergence and large-scale calculation, but cannot obtain the optimal solution. The accurate algorithm is an effective method to solve the optimal solution of the above problem. Therefore, a branch and bound method is designed to obtain the optimal solution according to examine the impact of overlapping activities on project scheduling. Firstly, the optimality of the algorithm is proved in theory. The optimal solution can be obtained only by considering the minimum delay substitution set, and cut set domination rule and left shift domination rule in pruning operation is proved. Secondly, in the algorithm design, the data structure-stack is used to store the node information on the search tree, and for the activities overlapping constraint, a new decision point and a new representation method of the search tree node are defined. Finally, the feasibility and effectiveness of the algorithm are verified by a large number of instances. In conclusion, the proposed algorithm has high research value with mature theoretical significance and accurate calculation results.

Key words: project scheduling, activity overlapping, branch and bound method, stack

中图分类号:

O224

于静, 徐哲, 谢芳. 带有活动重叠的项目调度问题新算法: 分支定界法[J]. 运筹学学报, 2023, 27(1): 115-126.

Jing YU, Zhe XU, Fang XIE. A branch and bound method for project scheduling problem with activities overlapping[J]. Operations Research Transactions, 2023, 27(1): 115-126.

图/表 4

图1

图2

表1

表2

参考文献 17

1	Yassine A A , Mostafa O , Browning T R . Scheduling multiple, resource-constrained, iterative, product development projects with genetic algorithms[J]. Computers & Industrial Engineering, 2017, 107, 39- 56.
2	Gerk J E V , Qassim R Y . Project acceleration via activity crashing, overlapping, and substitution[J]. IEEE Transaction on Engineering Management, 2008, 55 (4): 590- 601. doi: 10.1109/TEM.2008.927786
3	Berthaut F , Pellerin R , Perrier N , et al. Time-cost trade-offs in resource constraint project scheduling problems with overlapping modes[J]. International Journal of Project Organization and Management, 2014, 6 (3): 215- 236. doi: 10.1504/IJPOM.2014.065259
4	Bozejko W , Hejducki Z , Uchronski M , et al. Solving resource-constrained construction scheduling problems with overlaps by meta-heuristic[J]. Journal of Civil Engineering and Management, 2014, 20 (5): 649- 659. doi: 10.3846/13923730.2014.906496
5	Koyuncu E , Erol R . PSO based approach for scheduling NPD projects including overlapping process[J]. Computers & Industrial Engineering, 2015, 85, 316- 327.
6	Dehghan R , Hazini K , Ruwanpura J . Optimization of overlapping activities in the design phase of construction projects[J]. Automation in Construction, 2015, 59, 81- 95. doi: 10.1016/j.autcon.2015.08.004
7	Greze L , Pellerin R , Leclaire P , et al. A heuristic method for resource-constrained project scheduling with activity overlapping[J]. Journal of Intelligent Manufacturing, 2014, 25 (4): 797- 811. doi: 10.1007/s10845-012-0719-5
8	于静, 徐哲, 李洪波. 带有活动重叠的资源受限项目调度问题建模与求解[J]. 系统工程理论与实践, 2015, 35 (5): 1236- 1245.
9	于静, 徐哲, 谢芳. 活动重叠模式与资源约束下的项目调度优化[J]. 管理科学学报, 2017, 20 (9): 36- 45.
10	Chu Z , Xu Z , Li H . New heuristics for the RCPSP with multiple overlapping modes[J]. Computers & Industrial Engineering, 2019, 131, 146- 156.
11	Chu Z , Xu Z , Xie F . Experimental Evaluation of Overlapping strategy for the multimode resource-constrained project scheduling problem[J]. Arabian Journal for Science and Engineering, 2019, 44 (3): 2503- 2517. doi: 10.1007/s13369-018-3211-5
12	初梓豪, 徐哲. 活动重叠对缩短资源受限项目工期有效性研究[J]. 系统工程理论与实践, 2019, 39 (9): 2388- 2397.
13	Christofides N , Alvarez-Valdes R , Tamarit M J . Project scheduling with resource constraints: A branch and bound approach[J]. European Journal of Operational Research, 1987, 29 (5): 262- 273.
14	Demeulemeester E , Herroelen W . A branch-and-bound procedure for the multiple resource-constrained project scheduling problem[J]. Management Science, 1992, 38 (20): 1803- 1818.
15	Sprecher A , Hartmann S , Drexl A . An exact algorithm for project scheduling with multiple modes[J]. OR Spektrum, 1997, 19 (3): 195- 203. doi: 10.1007/BF01545587
16	Mingozzi A , Maniezzo V , Ricciardelli S , et al. An exact algorithm for the resource-constrai-ned project scheduling based on a new mathematical for mulation[J]. Management Science, 1998, 44, 714- 729. doi: 10.1287/mnsc.44.5.714
17	Demeulemeester L E , Vanhoucke M , Herroelen S W . A random network generator for activity-on-the-node networks[J]. Journal of Scheduling, 2003, 6 (1): 17- 38. doi: 10.1023/A:1022283403119

参数	取值
活动个数$ N $	10; 20; 30; 40; 50
资源种类$ K $	4
次序强度$ OS $	0.3; 0.5; 0.7
资源系数$ RF $	0.3; 0.6
资源强度$ RS $	0.3; 0.5; 0.7
重叠参数$ \alpha $	从区间[0.3, 0.7] 之间随机选取
返工参数$ \mu $	从区间[0.3, 0.7] 之间随机选取
可重叠活动对占总的活动对百分比Percentage	30$ \% $

数据集	固定时间/s	均值AVE	标准差STD	百分比PER/%
Set(10)	10	0.029	0.036	100
Set(20)	10	0.087	0.102	100
Set(30)	10	0.515	0.693	97.0
Set(30)	60	0.930	2.418	100
Set(40)	10	0.721	1.280	80.8
	60	2.272	6.413	88.3
	300	10.253	23.645	100
Set(50)	10	0.915	1.373	67.5
	60	4.703	9.332	82.2
	300	18.983	43.681	100

带有活动重叠的项目调度问题新算法: 分支定界法

A branch and bound method for project scheduling problem with activities overlapping

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 4

参考文献 17

相关文章 1

编辑推荐

Metrics

本文评价