A fast algorithm for finding a lower bound of the solution of the Resource-Constrained Project Scheduling Problem tested on PSPLIB instances

E. Kh. Gimadi ; E. N. Goncharov ; A. A. Shtepa

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 27 (2021) no. 1, pp. 22-36

Résumé

We consider the intractable Resource-Constrained Project Scheduling Problem (RCPSP). It is assumed that the intensity functions of resource allocation and consumption are constant on specified time intervals and there are no deadlines. The procedure for calculating the lower bound for the RCPSP is constructed on the basis of the relaxation of the problem by replacing renewable resources with cumulative ones. The time complexity of this procedure depends on the number of activities $n$ as a function of $\mathcal O(n\log{n})$. From the analysis of numerical experiments (which are carried out on examples of problems from the electronic library PSPLIB), it follows that the proposed procedure is highly competitive, and in some series of instances gives results close to the best lower bounds published in the PSPLIB with dramatically small CPU time (milliseconds).

Détail

Keywords: project management, Resource-Constrained Project Scheduling Problem, renewable resources, cumulative resources, lower bound.
Mots-clés : PSPLIB

Bibliographie

[1] Baptiste P., Pape C.L., “Constraint propagation and decomposition techniques for highly disjunctive and highly cumulative project scheduling problems”, Constraints, 5 (2000), 119–139 | DOI | MR | Zbl

[2] Blazewicz J., Lenstra J.K., Rinnoy Kan A. H. G., “Scheduling subject to resource constraints: Classification and complexity”, Discrete Applied Math., 5:1 (1983), 11–24 | DOI | MR | Zbl

[3] Bottcher J., Drexl A., Salewski F., “Project scheduling under partially renewable resource constraints”, Management Science, 45:4 (1999), 543–559 | DOI | Zbl

[4] Brucker P., Drexl A., Mohring R., et al., “Resource-Constrained Project Scheduling: Notation, classification, models, and methods”, Eur. J. Oper. Res., 112:1 (1999), 3–41 | DOI | MR | Zbl

[5] Gafarov E., Lazarev A., Werner F., On lower and upper bounds for the Resource-Constrained Project Scheduling Problem, Technical report, Otto-von-Guericke Universitaet, Magdeburg, 2010, 27 pp.

[6] Hartmann S., Kolisch R., “Experimental evaluation of state-of-the-art heuristics for the Resource-Constrained Project Scheduling Problem”, Eur. J. Oper. Res., 127:2 (2000), 394–407 | DOI | Zbl

[7] Herroelen W., Demeulemeester E., De Reyck B.A., “Classification scheme for project scheduling”, Project Scheduling-Recent Models, Algorithms and Applications, International Ser. Oper. Research and Management Sci., 14, Kluwer Acad. Pub., Dordrecht, 1998, 77–106 | DOI

[8] Knust S., “Lower bounds on the minimum project duration”, Handbook on project management and scheduling, chap. 3, v. 1, Springer, Cham, 2015, 43–56 | DOI

[9] Kolisch R., Sprecher A., “PSPLIB - a Project Scheduling Problem Library”, Eur. J. Oper. Res., 96 (1996), 205–216 | DOI

[10] Kolisch R., Sprecher A., Drexl A., “Characterization and generation of a general class of Resource-Constrained Project Scheduling Problems”, Manage Science, 41 (1995), 1693–1703 | DOI | MR | Zbl

[11] Neron E., Artigues C., Baptiste P., Carlier J., Damay J., Demassey S., Laborie P., “Lower bounds for Resource Constrained Project Scheduling Problem”, Perspectives in modern project scheduling, Chap. 7, Springer, Cham, 2006, 167–204 | DOI | MR | Zbl

[12] Neumann K., Schwindt C., Trautmann N., “Scheduling of continuous and discontinuous material flows with intermediate storage restrictions”, European J. Oper. Research, 165:2 (2005), 495–509 | DOI | Zbl

[13] Shirzadeh Chaleshtarti A., Shadrokh S., Fathi Y., “Branch and bound algorithms for Resource Constrained Project Scheduling Problem subject to nonrenewable resources with prescheduled procurement”, Mathematical Problems in Engineering, 2014 (2014), Hindawi Publishing Corporation | DOI | MR

[14] Valls, V., Ballestin, F., Quintanilla, S., “A hybrid genetic algorithm for the Resource-Consrtained Project Scheduling Problem”, Eur. J. Oper. Res., 185:2 (2008), 495–508 | DOI | MR | Zbl

[15] Weglarz, J., Project scheduling. Recent models, algorithms and applications, Kluwer Acad. Publ., Boston, 1999, 535 pp. | DOI

[16] Alekseev A.M., Gimadi E.Kh., Perepelitsa V.A., “Matematicheskie modeli kalendarnogo planirovaniya i upravleniya dolgosrochnymi proektami (na primere BAM)”, Problemy stroitelstva magistrali i razvitiya stroitelnoi bazy dlya khozyaistvennogo osvoeniya zony BAM, Tr. II Vsesoyuznoi konferentsii po problemam khozyaistvennogo osvoeniya zony BAM (Novosibirsk, 1977), Blagoveschensk, 1977, 118–126

[17] Gimadi E.Kh., Puzynina N.M., “Zadacha kalendarnogo planirovaniya krupnomasshtabnogo proekta v usloviyakh ogranichennykh resursov: opyt postroeniya matematicheskogo obespecheniya”, Upravlyaemye sistemy, 1983, no. 23, 24–32, Novosibirsk | MR | Zbl

[18] Gimadi E.Kh., “O nekotorykh matematicheskikh modelyakh i metodakh planirovaniya krupnomasshtabnykh proektov”, Modeli i metody optimizatsii, Tr. AN SSSR. Sib. Otd-nie. In-t matematiki, 10, Nauka, Novosibirsk, 1988, 89–115

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

[20] Zukhovitskii S.I., Radchik I.A., Matematicheskie metody setevogo planirovaniya, Nauka, M., 1965, 296 pp.

[21] Kleinberg Dzh., Tardos E., Algoritmy: razrabotka i primenenie. Klassika Computers Science, per. s angl. E. Matveeva, Piter, SPb., 2016, 800 pp.

[22] Kozlov M.K., Shafranskii V.V., “Kalendarnoe planirovanie vypolneniya kompleksov rabot pri zadannoi dinamike postupleniya skladiruemykh resursov”, Izv. AN SSSR. Tekhnicheskaya kibernetika, 1977, no. 4, 75–81 | Zbl