This paper addresses the project scheduling problem. It provides an overview of various problem formulations under resource constraints, including those aimed at maximizing the Net Present Value of the entire project. Special attention is given to modeling scenarios typical of large-scale projects, where traditional resources can be substituted with their monetary equivalents. In such cases, the model is reduced to a single type of resource: financial resources. The standard problem formulation is described, and a novel modeling approach is proposed: instead of hard resource constraints, additional resource usage incurs a cost. This cost is modeled through borrowing at a fixed interest rate. Under this framework, any schedule consistent with the partial order of activities becomes feasible. A recursive procedure is proposed for calculating net profit given a fixed activity schedule. It is shown that determining a schedule that maximizes net profit is strongly NP-hard. A special case of the problem is identified as polynomially solvable when the total number of profitable, technologically independent activities is bounded by a constant. A model is also presented to estimate the potential of a project under full self-financing. The question of whether this problem is polynomially solvable remains open. To address it, an approximate integer linear programming model with a unimodular matrix is proposed. However, the complexity status of this formulation likewise remains unresolved.
- Title Investment project scheduling with lending
- Headline Investment project scheduling with lending
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 70
- Date:
- DOI 10.17223/20710410/70/7
Keywords
scheduling, investment project, Net Present Value, lendingAuthors
References
Fazar W. The origin of PERT // The Controller. 1962. No. 30. P.598-621.
Kelley J.E. Critical-path planning and scheduling: Mathematical basis // Oper. Res. 1961. V.9. No.3. P.296-320.
Alan A., Pritsker B., Watters L. J., and Wolfe P. M. Multiproject scheduling with limited resources: A zero-one programming approach // Management Science. 1969. V. 16. No. 1. P.93-108.
Blazewicz J., Lenstra J.K., and Rinnooy Kan A. H. G. Scheduling subject to resource constraints: classification and complexity // Discr. Appl. Math. 1983. V. 5. No. 1. P.11-24.
Russell A. H. Cash flows in networks // Management Science. 1970. V. 16. No. 5. P. 357-373.
Servakh V. V. A dynamic algorithm for some project management problems // Proc.Int. Workshop Discrete Optimization Methods in Scheduling and Computer-Aided Design (Minsk, September 5-6, 2000). Minsk: Inst. Eng. Cvbern. NAS Belarus, 2000. P.90-92.
Cepeax В. В., Щербинина T.A. О сложности одной задачи календарного планирования со складируемыми ресурсами j j Вести. НГУ. Сер. матем., мех., информ. 2008. Т. 8. УЗ. С.105-112.
Мартынова Е. А., Сервах В. В. О задаче календарного планирования проектов с использованием кредитов // Автоматика и телемеханика. 2012. УЗ. С. 107-116.
Казаковцева Е. А., Сервах В. В. Сложность задачи календарного планирования с кредитами // Дискреты, анализ и исслед. опер. 2015. Т. 22. У 4. С. 35-49.
Гимади Э.X., Залюбовский В. В., Севастьянов С. В. Полиномиальная разрешимость задач календарного планирования со складируемыми ресурсами и директивными сроками // Дискреты, анализ и исслед. опер. Сер. 2. 2000. Т. 7. У1. С. 9-34.
Гимади Э. Х., Гончаров Е. Н., Штепа А. А. Быстрый алгоритм вычисления нижней оценки для решения задачи ресурсно-календарного планирования с тестированием на примерах библиотеки PSPLIB // Тр. ІІММ УрО РАН. 2021. Т. 27. У 1. С. 22-36.
Гончаров Е. Н. Алгоритм локального поиска для задачи календарного планирования с ограниченными ресурсами // Дискреты, анализ и исслед. опер. 2022. Т. 29. У 4. С. 15-37.
Hazir 0., Haouari M., апа Erel Е. Robust optimization for the discrete time-cost tradeoff problem with cost uncertainty // C.Schwindt ав J. Zimmermann (eds.). Handbook оn Project Management and Scheduling. V.2. Cham: Springer, 2015. Р. 865-874.
Mdhring R. H. Minimizing costs of resource requirements in project networks subject to a fixed completion time // Oper. Res. 1984. V. 32. No. 1. P.89-120.
Романова А. А. Минимизация стоимости расписания проекта с возобновимыми ресурсами переменной стоимости // Материалы XII Междунар. школы-симпозиума АМУР. Симферополв, 2018. С. 392-396.
Rodrigues S. В. and Yamashita D. S. An exact algorithm for minimizing resource availability costs in project scheduling // Europ. J. Oper. Res. 2010. V. 206. No.3. P.562-568.
Fu F. Integrated scheduling and batch ordering for construction project // Appl. Math. Modelling. 2014. V.38. No.2. P.784-797.
Zoraghi N., Shahsavar A., and Niaki S. A hybrid project scheduling and material ordering problem: Modeling and solution algorithms // Appl. Soft Computing. 2017. V. 58. P. 700-713.
Kononov A. V. and Lin B. M. T. On relocation problems with multiple working crews // Discret. Optim. 2006. V.3. No.4. P.366-381.
Sevastyanov S. V., Lin В. M. T., and Fluang H.-L. Tight complexity analysis of the relocation problem with arbitrary release dates // Theor.Comput. Sci. 2011. V.412. No. 35. P.45364544.
Kaplan E. H. Relocation models for public housing redevelopment programs // Environment and Planning B: Urban Analytics and City Science. 1986. V. 13. No. 1. P. 5-19.
Kaplan E. H. and Amir A. A fast feasibility test for relocation problems // Europ. J. Oper. Res. 1988. V. 35. No. 2. P. 201-205.
Hanzdlek Z. and Sucha P. Time symmetry of resource constrained project scheduling with general temporal constraints and take-give resources // Ann. Oper. Res. 2017. V. 248. P. 209-237.
Okubo H., Miyamoto T., Yoshida S., et al. Project scheduling under partially renewable resources and resource consumption during setup operations // Computers k, Industrial Engineering. 2015. V.83. P.91-99.
Watermeyer K. and Zimmermann J. A branch-and-bound procedure for the resource-constrained project scheduling problem with partially renewable resources and general temporal constraints // OR Spectrum. 2020. Y. 12. P.427-460.
Hartmann S. and Briskorn D. An updated survey of variants and extensions of the resource-constrained project scheduling problem // Europ. J. Oper. Res. 2022. V. 297. No. 1. P. 1 11.
Handbook on Project Management and Scheduling. C. Schwindt and J. Zimmermann (eds). Cham: Springer, 2015. 1401 p.
Gu H., Schutt A., Stuckey P.J., et al. Exact and heuristic methods for the resource-constrained net present value problem // C. Schwindt and J. Zimmermann (eds). Handbook on Project Management and Scheduling. V. 1. Cham: Springer, 2015. P.299-318.
Leyman P. and Vanhoucke M. A new scheduling technique for the resource constrained project scheduling problem with discounted cash flows // Intern. J. Production Res. 2015. V. 53. No. 9. P.2771-2786.
Thiruvady D., Wallace M., Gu H., and Schutt A. A lagrangian relaxation and ACO hybrid for resource constrained project scheduling with discounted cash flows // J. Heuristics. 2014. V.20. P. 643-676.
Vanhoucke М. A scatter search heuristic for maximising the net present value of a resource-constrained project with fixed activity cash flows // Intern. J. Production Res. 2010. V. 48. No. 7. P. 1983-2001.
Fink A. and Homberger J. An ant-based coordination mechanism for resource-constrained project scheduling with multiple agents and cash flow objective // Flex. Serv. Manuf. J. 2013. V. 25. P. 94-121.
Legman P. and Vanhoucke M. Capital- and resource-constrained project scheduling with net present value optimization // Europ. J. Oper. Res. 2017. V.256. No.3. P.757-776.
Legman P., Van Driessche N., Vanhoucke M., and De Causmaecker P. The impact of solution representations on heuristic net present value optimization in discrete time/cost trade-off project scheduling with multiple cash flow and payment models // Computers k Oper. Res. 2019. V. 103. P. 184-197.
Legman P. and Vanhoucke M. Payment models and net present value optimization for resource constrained project scheduling // Computers k Industrial Engineering. 2016. V. 91. P. 139-153.
Shahsavar M., Niaki S.T.A., and Naja A.A. An efficient genetic algorithm to maximize net present value of project payments under inflation and bonus-penalty policy in resource investment problem // Adv. Engineering Software. 2010. V. 41. No. 7. P.1023-1030.
Waligora G. Discrete-continuous project scheduling with discounted cash inflows and various payment models - a review of recent results // Ann. Oper. Res. 2014. V. 213. P.319-340.
Tirkolaee E. B., Gobi A., Hematian M., et al. Multi-objective multi-mode resource constrained project scheduling problem using pare-to-based algorithms // Computing. 2019. V. 101. No. 11. P.547-570.
Khoshjahan Y., Najafi A. A., and Afshar-Nadjafi B. Resource constrained project scheduling problem with discounted earliness-tardiness penalties: Mathematical modeling and solving procedure // Computers k Industrial Engineering. 2013. V. 66. No. 2. P.293-300.
Malakh S. A. and Servakh V V. The problem of planning investment projects with lending // LNCS. 2024. V. 14766. P. 187-198.
Investment project scheduling with lending | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2025. № 70. DOI: 10.17223/20710410/70/7
Download full-text version
Counter downloads: 28