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 条
  • [1] Brucker P., Drexl A., Mohring R., Et al., Resource-constrained project scheduling: Notation, classification, models, and methods, Eur. J. Oper. Res., 112, 1, pp. 3-41, (1999)
  • [2] Blauewicz J., Lenstra J.K., Rinnoy Kan A.H.G., Scheduling subject to resource constraints: Classification and complexity, Discr. Appl. Math., 5, 1, pp. 11-24, (1983)
  • [3] . Gimadi E.K., On some mathematical models and methods for planning large-scale projects. Models and optimization methods, Tr. Akad. Nauk SSSR. Sib. Otd. Inst. Mat. (Nauka, Novosibirsk), 10, pp. 89-115, (1988)
  • [4] Gimadi E.K., Zalyubovskii V.V., Sevast'yanov S.V., Polynomial solvability of scheduling problems with storable resources and deadlines, Diskr. Anal. Issled. Oper. Ser. 2, 7, 1, pp. 9-34, (2000)
  • [5] Pellerin R., Perrier N., Berthaut F., LSSPER: A survey of hybrid metaheuristics for the resource-constrained project scheduling problem, Eur. J. Oper. Res., 280, 2, pp. 395-416, (2020)
  • [6] Abdolshah M., A review of resource-constrained project scheduling problems (RCPSP) approaches and solutions, Int. Trans. J. Eng. Manage. Appl. Sci. Technol., 5, 4, pp. 253-286, (2014)
  • [7] Vanhoucke M., “Resource-constrained project scheduling,” in Project Management with Dynamic Scheduling, pp. 107-137, (2012)
  • [8] Hartmann S., riskorn D., A survey of variants and extensions of the resource-constrained project scheduling problem, Eur. J. Oper. Res., 207, pp. 1-14, (2010)
  • [9] Kolisch R., Hartmann S., Experimental investigation of heuristics for resource-constrained project scheduling: An update, Eur. J. Oper. Res., 174, pp. 23-37, (2006)
  • [10] Palpant M., Artigues C., Michelon P., Solving the resource-constrained project scheduling problem with large neighborhood search, Ann. Oper. Res., 131, pp. 237-257, (2004)
12345