A Local Search Algorithm for the Resource-Constrained Project Scheduling Problem

被引：0
作者：
Goncharov E.N. [1 ,2 ]
机构：
[1] Sobolev Institute of Mathematics, Siberian Branch, Russian Academy ofSciences, Novosibirsk
[2] Novosibirsk State University, Novosibirsk
来源：
Journal of Applied and Industrial Mathematics | 2022年 / 16卷 / 04期
关键词：
PSPLIB; renewable resources; resource-constrained project scheduling problem; Tabu search; variable neighborhood search;
D O I：
10.1134/S1990478922040081
中图分类号：
学科分类号：
摘要：
Abstract: We consider the resource-constrained project scheduling problem (RCPSP). The problemaccounts for technological constraints of activities precedence together with resource constraints.All resources are renewable. Activities interruptions are not allowed. This problem is NP-hard inthe strong sense. We present a new local search algorithm that uses a Tabu-list and two types ofneighborhoods. The algorithm is evaluated using three data bases of instances of the problem: 480instances of 60 activities, 480 of 90, and 600 of 120 activities, respectively, taken from the PSPLIBlibrary available online. Numerical experiments demonstrate that the proposed algorithm producesbetter results than existing algorithms described in the literature for large-sized instances. Forsome instances from the dataset j120, the best known heuristic solutions were improved. © 2022, Pleiades Publishing, Ltd.
引用
收藏
页码：672 / 683
页数：11
相关论文
共 47 条
[41]  
Carlier J., Moukrim A., Xu H., “A memetic algorithm for the resource constrained project scheduling problem, ” Proc. Int. Conf. Ind. Eng. Syst, (2009)
[42]  
Debels D., De Reyck Leus B.R., Vanhoucke M., A hybrid scatter search electromagnetism meta-heuristic for project scheduling, Eur. J. Oper. Res., 169, pp. 638-653, (2006)
[43]  
Ranjbar M., Kianfar F., A hybrid scatter search for the RCPSP, Sci. Iran., 16, 1, pp. 11-18, (2009)
[44]  
Jedrzejowicz P., Ratajczak E., “Population learning algorithm for the resource-constrained project scheduling,” in Perspectives in Modern Project Scheduling, pp. 275-296, (2006)
[45]  
Ying K.C., Lin S.W., Lee Z.J., Hybrid-directional planning: improving improvement heuristics for scheduling resource-constrained projects, Int. J. Adv. Manuf. Technol., 41, 3-4, pp. 358-366, (2009)
[46]  
Alcaraz J., Maroto C., “A hybrid genetic algorithm based on intelligent encoding for project scheduling,” in Perspectives in Modern Project Scheduling, pp. 249-274, (2006)
[47]  
Valls V., Ballestin F., uintanilla M.S., Justification and RCPSP: A technique that pays, Eur. J. Oper. Res., 165, pp. 375-386, (2005)
12345