Operations Research Transactions >
2023 , Vol. 27 >Issue 1: 115 - 126
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2023.01.008
A branch and bound method for project scheduling problem with activities overlapping
Received date: 2020-11-13
Online published: 2023-03-16
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
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 . DOI: 10.15960/j.cnki.issn.1007-6093.2023.01.008
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
/
| 〈 |
|
〉 |