E.Kh. Gimadi, E.N. Goncharov, A.A. Shtepa. A fast algorithm for finding a lower bound of the solution of the Resource-Constrained Project Scheduling Problem tested on PSPLIB instances ... P. 22-36

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).

Keywords: project management, Resource-Constrained Project Scheduling Problem, renewable resources, cumulative resources, PSPLIB, lower bound

Received September 25, 2020

Revised February 20, 2021

Accepted February 26, 2021

Funding Agency: This work was supported by the Program for Fundamental Research of the Siberian Branch of the Russian Academy of Sciences (project no. 0314-2019-0014) and by the Russian Foundation for Basic Research (project no. 20-31-90091).

Edward Khairutdinovich Gimadi, Dr. Phys.-Math. Sci., Prof., Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences, Novosibirsk, 630090 Russia, e-mail: gimadi@math.nsc.ru

Evgenii Nikolaevich Goncharov, Cand. Phys.-Math. Sci., Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences, Novosibirsk, 630090 Russia, e-mail: gon@math.nsc.ru

Alexandr Alexandrovich Shtepa, doctoral student, Novosibirsk State University (NSU), Novosibirsk, 630090 Russia, e-mail: shoomath@gmail.com

REFERENCES

1.   Baptiste P., Pape C. L. Constraint propagation and decomposition techniques for highly disjunctive and highly cumulative project scheduling problems. Constraints, 2000, vol. 5, pp. 119–139. doi: 10.1023/A:1009822502231 

2.   Blazewicz J., Lenstra J. K., Rinnoy Kan A. H. G. Scheduling subject to resource constraints: Classification and complexity. Discrete Applied Math., 1983, vol. 5, no. 1, pp. 11–24. doi: 10.1016/0166-218X(83)90012-4 

3.   Bottcher J., Drexl A., Salewski F. Project scheduling under partially renewable resource constraints. Management Sci., 1999, vol. 45, no. 4, pp. 543–559. doi: 10.1007/s10732-006-5224-6 

4.   Brucker P., Drexl A., M$\ddot{\mathrm{o}}$hring R., et al. Resource-Constrained Project Scheduling: Notation, classification, models, and methods. Eur. J. Oper. Res., 1999, vol. 112, no. 1, pp. 3–41.

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

6.   Hartmann S., Kolisch R. Experimental evaluation of state-of-the-art heuristics for the Resource-Constrained Project Scheduling Problem. Eur. J. Oper. Res., 2000, vol. 127, no. 2, pp. 394–407.

7.   Herroelen W., Demeulemeester E., De Reyck B. A. Classification scheme for project scheduling. In: Weglarz J. (Ed.), Project Scheduling-Recent Models, Algorithms and Applications, International, Series in Operations Research and Management Science, vol. 14, Dordrecht: Kluwer Acad. Publ., 1998, pp. 77–106. doi: 10.1007/978-1-4615-5533-9_1 

8.   Knust S. Lower bounds on the minimum project duration . In: C. Schwindt, J. Zimmermann (eds.), Handbook on project management and scheduling, Cham: Springer, 2015, vol. 1, chap. 3, pp. 43–56. doi: 10.1007/978-3-319-05443-8_3 

9.   Kolisch R., Sprecher A. PSPLIB — a Project Scheduling Problem Library. Eur. J. Oper. Res., 1996, vol. 96, pp. 205–216. doi: 10.1016/S0377-2217(96)00170-1 

10.   Kolisch R., Sprecher A., Drexl A. Characterization and generation of a general class of Resource-Constrained Project Scheduling Problems. Manage Science, 1995, vol. 41, 1995, pp. 1693–1703. doi: 10.1287/mnsc.41.10.1693 

11.   Neron E., Artigues C., Baptiste P., Carlier J., Damay J., Demassey S., Laborie P. Lower bounds for Resource Constrained Project Scheduling Problem. In: J. Jozefowska, J. Weglarz (Eds.), Perspectives in modern project scheduling, Chap. 7, Cham: Springer, 2006, pp. 167–204.
doi: 10.1007/978-0-387-33768-5_7 

12.   Neumann K., Schwindt C., Trautmann N. Scheduling of continuous and discontinuous material flows with intermediate storage restrictions. European J. Operational Research, 2005, vol. 165, no. 2, 2005, pp. 495–509.

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, Hindawi Publishing Corporation, 2014, vol. 2014. doi: 10.1155/2014/634649 

14.   Valls, V., Ballestin, F., Quintanilla, S. A hybrid genetic algorithm for the Resource-Consrtained Project Scheduling Problem. Eur. J. Oper. Res., 2008, vol. 185, no. 2, pp. 495–508.

15.   Weglarz, J. Project scheduling. Recent models, algorithms and applications, Boston: Kluwer Acad. Publ, 1999. 535 p. doi: 10.1007/978-1-4615-5533-9 

16.   Alekseev A.M., Gimadi E.Kh., Perepelitsa V.A. Mathematical models of scheduling and management of long-term projects (on the example of BAM). In: “Problems of highway construction and development of the construction base for the economic development of the BAM zone”, (II All-Union Conference on economic development of the BAM zone, Blagoveshchensk, 1977). Novosibirsk, 1977, pp. 118–126 (in Russian).

17.   Gimadi E.Kh., Puzynina N.M. Problem of the calendar planning of a large-scale design under the conditions of limited resources: experience in the construction of software. Upravliaemie systemy, 1983, no. 23, pp. 24–32 (in Russian).

18.   Gimadi E.Kh. Some mathematical models and methods for the planning of large-scale projects. In: “Modeli i metody optimizatsii” (Optimization models and methods), Novosibirsk: Nauka Publ., 1988 (Trudy Inst. Mat. Sib. Otd. AN SSSR, 1988, vol. 10), pp. 89–115 (in Russian).

19.   Gimadi E.Kh., Zalyubovskii V.V., Sevast’yanov S.V. Polynomial solvability of scheduling problems with storable resources and directive deadlines. Diskretn. Anal. Issled. Oper., Ser. 2, 2000, vol. 7, no. 1, pp. 9–34 (in Russian).

20.   Zukhovitsky S.I., Radchik I.A. Matematicheskie metody setevogo planirovaniya [Mathematical methods of network planning]. Moscow: Nauka Publ., 1965, 296 p.

21.   Kleinberg J., Tardos E. Algorithm design. Boston: Pearson/Addison-Wesley, 2006, 838 p. ISBN: 0321295358 . Translated to Russian under the title “Algoritmy: razrabotka i primenenie”. St. Petersburg: Piter Publ., 2016, 800 p.

22.   Kozlov M.K., Shafransky V.V. Scheduling of the execution of complexes of jobs for a given dynamics of the receipt of stored resources. Izv. AN SSSR, Tekhnicheskaya kibernetika, 1977, no. 4, pp. 75–81 (in Russian).

Cite this article as: E.Kh. Gimadi, E.N. Goncharov, A.A. Shtepa. A fast algorithm for finding a lower bound of the solution of the Resource-Constrained Project Scheduling Problem tested on PSPLIB instances, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2021, vol. 27, no. 1, pp. 22–36.