Volume 22, No 4, 2015, P. 35-49
UDC 519.85
Kazakovtseva E. A., Servakh V. V.
The complexity of the project scheduling problem with credits
Abstract:
We consider the profit maximization problem in calendar planning of investment projects taking into account reinvesting of the obtained revenue and possible credit financing.We construct corresponding models and study characteristics of these models. Strong NP-hardness of the profit maximization problem is proved when the amount of the used credits is not limited.
Bibliogr. 11.
Keywords: project scheduling, investment project, NPV criterion, credit.
DOI: 10.17377/daio.2015.22.478
Evgeniya A. Kazakovtseva 2
Vladimir V. Servakh 1,2
1. Omsk Branch of Sobolev Institute of Mathematics of SB RAS,
13 Pevtsov St., 644099 Omsk, Russia
2. Omsk State University,
55-a Mir Ave., 644077 Omsk, Russia
e-mail: martynova87@mail.ru, svv_usa@rambler.ru
Received 20 February 2015
Revised 6 April 2015
References
[1] E. Kh. Gimadi, V. V. Zalyubovskiy, and S. V. Sevastyanov, Polynomial solvability of scheduling problems with storable resources and directive deadlines, Diskretn. Anal. Issled. Oper., Ser. 2, 7, No. 1, 9–34, 2000. Translated in J. Appl. Ind. Math., 1, No. 4, 442–452, 2007.
[2] E. A. Kazakovtseva and V. V. Servakh, Financing and reliability analysis for schedules in the project calendar planning problem Avtom. Telemekh., No. 7, 87–98, 2014. Translated in Autom. Remote Control, 75, No. 7, 1231–1240, 2014.
[3] E. A. Kazakovtseva and V. V. Servakh, NP-hardness of the project scheduling problem with credits in Tezisy dokladov XVI Baikal’skoi mezhdunarodnoi shkoly-seminara “Metody optimizatsii i ikh prilozheniya” (Abstr. XVI Baikal Int. School-Seminar “Optimization Methods and Their Applications”), Olkhon, Irkutsk Reg., Russia, June 30 – July 6, 2014, p. 56, Inst. Sist. Energ. SO RAN, Irkutsk, 2014.
[4] E. A. Martynova and V. V. Servakh, On scheduling credited projects, Avtom. Telemekh., No. 3, 107–116, 2012. Translated in Autom. Remote Control, 73, No. 3, 508–516, 2012.
[5] E. A. Martynova and V. V. Servakh, Optimizing the use of credits in the project scheduling problem, in Materialy Rossiiskoi konferentsii “Diskretnaya optimizatsiya i issledovanie operatsii” (Proc. Russian Conf. “Discrete Optimization and Operation Research”), Novosibirsk, Russia, June 24–28, 2013, p. 96, Izd. Inst. Mat., Novosibirsk, 2013.
[6] V. V. Servakh and T. A. Shcherbinina, Complexity of some project scheduling problem with nonrenewable resources, Vestn. NGU, Ser. Mat., Mekh., Inform., 8, No. 3, 105–112, 2008.
[7] P. Brucker, A. Drexl, R. M¨ohring, K. Neumann, and E. Pesch, Resource-constrained project scheduling: Notation, classification, models, and methods Eur. J. Oper. Res., 112, No. 1, 3–41, 1999.
[8] E. Kh. Gimadi and S. V. Sevast’yanov, On solvability of the project scheduling problem with accumulative resources of an arbitrary sign, in Oper. Res. Proc. 2002 (Sel. Pap. Int. Conf. Oper. Res., Klagenfurt, Sept. 2–5, 2002), pp. 241–246, Springer-Verl., Berlin, 2002.
[9] R. H. Möhring, Minimizing costs of resource requirements in project networks subject to a fixed completion time, Oper. Res., 32, No. 1, 89–120, 1984.
[10] J. We²glarz, ed., Project Scheduling: Recent Models, Algorithms, and Applications, Kluwer Acad. Publ., New York, 1999 (Int. Ser. Oper. Res. Manag. Sci., Vol. 14).
[11] A. H. Russell, Cash flows in networks, Manag. Sci., 16, No. 5, 357–373, 1970.
