A stochastic greedy algorithm for the resource-constrained project scheduling problem

E. N. Goncharov

Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 3, pp. 11-24.

Résumé

We consider the resource constrained project scheduling problem (RCPSP) with precedence and resource constraints. All resources are renewable and the objective is to find a schedule that meets all resource and precedence constraints and minimizes the makespan. We propose a fast stochastic algorithm developed by the greedy algorithm based on deterministic solutions to this problem with the low-time complexity. Quality of this algorithm has been analyzed in a number of computational experiments with the standard sets J60 and J120 for the RCPSP from the PSPLIB [23]. The proposed algorithm takes some of the best positions among greedy algorithms and showed the best result on the set J60 from PSPLIB with the limit of schedules 50000. It is competitive among all the algorithms being second only to genetic algorithms and to combined ones based on them. Ill. 1, tab. 4, bibliogr. 33.

Détail

Keywords: resource constrained project scheduling problem, limited resource, renewable resource
Mots-clés : heuristic algorithm.

Bibliographie

[1] Gimadi E. Kh., “O nekotorykh matematicheskikh modelyakh i metodakh planirovaniya krupnomasshtabnykh proektov”, Modeli i metody optimizatsii, 10, Nauka, Novosibirsk, 1988, 89–115 | MR

[2] Gimadi E. Kh., Goncharov E. N., Zalyubovskii V. V., Plyaskina N. I., Kharitonova V. N., “O programmno-matematicheskom obespechenii dlya zadachi resursno-kalendarnogo planirovaniya Vostochno-Sibirskogo neftegazovogo kompleksa”, Vestn. NGU. Ser. Matematika, mekhanika, informatika, 10:4 (2010), 52–67

[3] Gimadi E. Kh., Zalyubovskii V. V., Sevastyanov S. V., “Polinomialnaya razreshimost zadach kalendarnogo planirovaniya so skladiruemymi resursami i direktivnymi srokami”, Diskret. analiz i issled. operatsii. Ser. 2, 7:1 (2000), 9–34 | MR | Zbl

[4] Gimadi E. X., Puzynina N. M., Sevastyanov S. V., “O nekotorykh ekstremalnykh zadachakh realizatsii krupnykh proektov tipa BAM”, Ekonomika i mat. metody, 15:5 (1979), 1017–1021

[5] Kochetov Yu. A., Stolyar A. A., “Ispolzovanie chereduyuschikhsya okrestnostei dlya priblizhënnogo resheniya zadachi kalendarnogo planirovaniya s ogranichennymi resursami”, Diskret. analiz i issled. operatsii. Ser. 2, 10:2 (2003), 29–55 | MR | Zbl

[6] Kochetov Yu. A., Stolyar A. A., “Novye zhadnye evristiki dlya zadachi kalendarnogo planirovaniya s ogranichennymi resursami”, Diskret. analiz i issled. operatsii. Ser. 2, 12:1 (2005), 12–36 | MR | Zbl

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

[8] Bouleimen K., Lecocq H. “A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version”, Eur. J. Oper. Res., 149:2 (2003), 268–281 | MR | Zbl

[9] 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 | Zbl

[10] Coelho J., Tavares L., Competitive analysis of metaheuristics for the resource constrained project scheduling problem, Tech. Report, Department of Civil Engineering, Instituto Superior Tecnico, Portugal, 2003

[11] Debels D., De Reyck Leus B. R., Vanhoucke M., “A hybrid scatter search/electromagnetism meta-heuristic for project scheduling”, Eur. J. Oper. Res., 169 (2006), 638–653 | DOI | MR | Zbl

[12] Debels D., Vanhoucke M., “Decomposition-based genetic algorithm for the resource-consrtained project scheduling problem”, Oper. Res., 55 (2007), 457–469 | DOI | Zbl

[13] Gimadi E. Kh., Sevastianov S. V., “On solvability of the project scheduling problem with accumulative resources of an arbitrary sign”, Proc. Oper. Res. 2002, Springer-Verl., Berlin–Heidelberg–New York, 2003, 241–246 | DOI | Zbl

[14] Goncharov E. N., “A greedy heuristic approach for the resource-constrained project scheduling problem”, Stud. Informatica Universalis, 9:3 (2012), 79–90

[15] Hartmann S., “A competitive genetic algorithm for resource-constrained project scheduling”, Naval Res. Logist., 45 (1998), 733–750 | 3.0.CO;2-C class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[16] Hartmann S., “A self-adapting genetic algorithm for project scheduling under resource constraints”, Naval Res. Logist., 49 (2002), 433–448 | DOI | MR | Zbl

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

[18] Kolisch R., “Efficient priority rules for the resource constrained project scheduling problem”, J. Oper. Manage., 14 (1996), 179–192 | DOI

[19] Kolisch R., “Serial and parallel resource-constrained project scheduling methods revisited: theory and computation”, Eur. J. Oper. Res., 90 (1996), 320–333 | DOI | Zbl

[20] Kolisch R., Drexl A., “Adaptive search for solving hard project scheduling problems”, Naval Res. Logist., 43:1 (1996), 23–40 | 3.0.CO;2-P class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | Zbl

[21] Kolisch R., Hartmann S., “Experimental investigation of heuristics for resource-constrained project scheduling: an update”, Eur. J. Oper. Res., 174 (2006), 23–37 | DOI | Zbl

[22] 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., Berlin, 1999, 147–178

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

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

[25] Nonobe K., Ibaraki T., “Formulation and tabu search algorithm for the resource constrained project scheduling problem”, Essays and surveys in metaheuristics, Kluwer Acad. Publ., Boston, 2002, 557–588 | DOI | MR | Zbl

[26] Ozdamar L., Ulusoy G., “A note on an iterative forward/backward scheduling technique with reference to a procedure by Li and Willis”, Eur. J. Oper. Res., 89 (1996), 400–407 | DOI | Zbl

[27] Proon S., Jin M., “A genetic algorithm with neighborhood search for the resource-constrained project scheduling problem”, Naval Res. Logist., 58 (2011), 73–82 | DOI | MR

[28] Schirmer A., “Case-based reasoning and improved adaptive search for project scheduling”, Naval Res. Logist., 47:3 (2000), 201–222 | 3.0.CO;2-L class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[29] Tormos P., Lova A., Integrating heuristics for resource-constrained project scheduling: One step forward, Tech. Report, Department of Statistics and Operations Research, Universidad Politecnica de Valencia, 2003

[30] Tormos P., Lova A., “An efficient multi-pass heuristic for project scheduling with constrained resources”, Int. J. Production Res., 41:5 (2003), 1071–1086 | DOI | Zbl

[31] Tormos P., Lova A., “A competitive heuristic solution techniques for resource-constrained project scheduling”, Ann. Oper. Res., 102 (2001), 65–81 | DOI | MR | Zbl

[32] Valls V., Ballestin F., Quintanilla S., “Justification and RCPSP: a technique that pays”, Eur. J. Oper. Res., 165:2 (2005), 375–386 | MR | Zbl

[33] Valls V., Ballestin F., Quintanilla S., “A hybrid genetic algorithm for the resource-constrained project scheduling problem”, Eur. J. Oper. Res., 185:2 (2008), 495–508 | DOI | Zbl