Geodesic
A greedy algorithm for the resource-constrained project scheduling problem
Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 4, pp. 27-39 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The resource-constrained project scheduling problem (briefly RCPSP) is a general scheduling problem that includes precedence and resource constraints. Activities preemptions are not allowed. Resources are renewable and there is a unique way to perform the activities. The problem with renewable resources is NP-hard in the strong sense. We propose a new deterministic greedy algorithm. It is based on heuristics that use information obtained from a relaxing problem. The algorithm is tested with standard data sets given by Kolisch library PSPLIB for j60, j90, and j120 and found to be performing well. Tab. 2, bibliogr. 17.
Keywords: resource-constrained project scheduling problem, project management, renewable resources, greedy algorithm
Mots-clés : PSPLIB. 
@article{DA_2024_31_4_a1,
     author = {E. N. Goncharov},
     title = {A greedy algorithm for the resource-constrained project scheduling problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {27--39},
     year = {2024},
     volume = {31},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2024_31_4_a1/}
}
TY  - JOUR
AU  - E. N. Goncharov
TI  - A greedy algorithm for the resource-constrained project scheduling problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2024
SP  - 27
EP  - 39
VL  - 31
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DA_2024_31_4_a1/
LA  - ru
ID  - DA_2024_31_4_a1
ER  - 
%0 Journal Article
%A E. N. Goncharov
%T A greedy algorithm for the resource-constrained project scheduling problem
%J Diskretnyj analiz i issledovanie operacij
%D 2024
%P 27-39
%V 31
%N 4
%U http://geodesic.mathdoc.fr/item/DA_2024_31_4_a1/
%G ru
%F DA_2024_31_4_a1
E. N. Goncharov. A greedy algorithm for the resource-constrained project scheduling problem. Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 4, pp. 27-39. http://geodesic.mathdoc.fr/item/DA_2024_31_4_a1/

[1] Brucker P., Drexl A., Möhring R., Neumann K., Pesch E., “Resource-constrained project scheduling: Notation, classification, models, and methods”, Eur. J. Oper. Res., 112:1 (1999), 3–41 | DOI | MR

[2] Herroelen W., Demeulemeester E., De Reyck B., “A classification scheme for project scheduling”, Project scheduling: Recent models, algorithms and applications, Kluwer Acad. Publ., Dordrecht, 1999, 1–26

[3] Blażewicz J., Lenstra J. K., Rinnooy Kan A. H. G., “Scheduling subject to resource constraints: Classification and complexity”, Discrete Appl. Math., 5:1 (1983), 11–24 | DOI | MR

[4] Kolisch R., Hartmann S., “Heuristic algorithms for solving the resource-constrained project scheduling problem: Classification and computational analysis”, Project scheduling: Recent models, algorithms and applications, Kluwer Acad. Publ., Dordrecht, 1999, 147–178 | MR

[5] Pellerin R., Perrier N., Berthaut F., “A survey of hybrid metaheuristics for the resource-constrained project scheduling problem”, Eur. J. Oper. Res., 280:2 (2020), 395–416 | DOI | MR

[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 (2014), 253–286

[7] Vanhoucke M., “Resource-constrained project scheduling”, Project management with dynamic scheduling, Springer, Heidelberg, 2012, 107–137 | DOI | MR

[8] Hartmann S., Briskorn D., “A survey of variants and extensions of the resource-constrained project scheduling problem”, Eur. J. Oper. Res., 207:1 (2010), 1–14 | DOI | MR

[9] Yu. A. Kochetov and A. A. Stolyar, “New greedy heuristics for the scheduling problem with constrained resources”, Diskretn. Anal. Issled. Oper., Ser. 2, 12:1 (2005), 12–36 (In Russian) | MR

[10] E. N. Goncharov, “A stochastic greedy algorithm for the resource-constrained project scheduling problem”, Diskretn. Anal. Issled. Oper., 21:3 (2014), 10–23 (In Russian) | MR

[11] Kolisch R., Sprecher A., “PSPLIB — A project scheduling problem library”, Eur. J. Oper. Res., 96:1 (1996), 205–216 | DOI | MR

[12] Eh. Kh. Gimadi, V. V. Zalyubovskii, and S. V. Sevastianov, “Polynomial solvability of scheduling problems with storable resources and directive deadlines”, Diskretn. Anal. Issled. Oper., Ser. 2, 7:1 (2000), 9–34 (In Russian) | MR

[13] Eh. Kh. Gimadi, “Some mathematical models and methods for scheduling large-scale projects”, Models and Methods of Optimization, Trudy AN SSSR, Sib. Otd., Inst. Mat., 10, Nauka, Novosibirsk, 1988, 89–115 (In Russian)

[14] Gimadi Eh. Kh., Sevastianov S. V., “On solvability of the project scheduling problem with accumulative resources of an arbitrary sign”, Operations research proceedings 2002, Sel. Pap. Int. Conf. Operations Research (Klagenfurt, Austria, Sept. 2–5, 2002), Springer, Heidelberg, 2003, 241–246 | DOI

[15] Li K. Y., Willis R. J., “An iterative scheduling technique for resource-constrained project scheduling”, Eur. J. Oper. Res., 56:3 (1992), 370–379 | DOI | MR

[16] Kolisch R., Sprecher A., Drexl A., “Characterization and generation of a general class of resource-constrained project scheduling problems”, INFORMS Manage. Sci., 41 (1995), 1693–1703 | MR

[17] Project scheduling: Recent models, algorithms and applications, Kluwer Acad. Publ., Dordrecht, 1999, 546 pp.