Geodesic
Complexity of some project scheduling problem with nonrenewable resources
Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 8 (2008) no. 3, pp. 105-112 
V. V. Servakh; T. A. Shcherbinina. Complexity of some project scheduling problem with nonrenewable resources. Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 8 (2008) no. 3, pp. 105-112. http://geodesic.mathdoc.fr/item/VNGU_2008_8_3_a6/
@article{VNGU_2008_8_3_a6,
     author = {V. V. Servakh and T. A. Shcherbinina},
     title = {Complexity of some project scheduling problem with nonrenewable resources},
     journal = {Sibirskij \v{z}urnal \v{c}istoj i prikladnoj matematiki},
     pages = {105--112},
     year = {2008},
     volume = {8},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VNGU_2008_8_3_a6/}
}
TY  - JOUR
AU  - V. V. Servakh
AU  - T. A. Shcherbinina
TI  - Complexity of some project scheduling problem with nonrenewable resources
JO  - Sibirskij žurnal čistoj i prikladnoj matematiki
PY  - 2008
SP  - 105
EP  - 112
VL  - 8
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VNGU_2008_8_3_a6/
LA  - ru
ID  - VNGU_2008_8_3_a6
ER  - 
%0 Journal Article
%A V. V. Servakh
%A T. A. Shcherbinina
%T Complexity of some project scheduling problem with nonrenewable resources
%J Sibirskij žurnal čistoj i prikladnoj matematiki
%D 2008
%P 105-112
%V 8
%N 3
%U http://geodesic.mathdoc.fr/item/VNGU_2008_8_3_a6/
%G ru
%F VNGU_2008_8_3_a6

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper the project scheduling problem with nonreneawble resources and criterion of Net Present Value is considered. We prove that this problem is strongly $NP$-hard. Special case of independent jobs was investigated. We propose the exact algorithm for this case of the problem which is based on dynamic programming scheme. We obtain the cases of the problem when the algorithm became pseudopolynomial.

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

[2] Servakh V. V., Scherbinina T. A., “O zadache kalendarnogo planirovaniya proekta s razlichnymi kriteriyami i skladiruemymi resursami”, Problemy optimizatsii i ekonomicheskie prilozheniya, III Vseros. konf. (Omsk, 2006), 125

[3] Brucker P., Drexl A., Mohring R. et al., “Resource-constrained Project Scheduling: Notation, Classification, Models, and Methods”, European Journal of Operational Research, 112 (1999), 3–41 | DOI | Zbl

[4] Brucker P., Lenstra J. K., Rinnooy Kan A. H. G., Complexity of Machine Scheduling Problems, BW 43, Math. Cent. Afd. Math. Beslisk., Amsterdam, 1975

[5] Doersch R. H., Patterson J. H., “Scheduling a Project to Maximaze its Present Value: A Zero-one Programming Approach”, Management Science, 23:8 (1977), 882–889 | DOI | Zbl

[6] Garey M. R., Johnson D. S., “Complexity Result for Multiprocessor Scheduling Under Resource Constraints”, SIAM J. Comput., 4:4 (1975), 397–411 | DOI | MR | Zbl

[7] Gimadi E., Sevastianov S., “On Solvability of the Project Scheduling Problem with Accumulative Resources of an Arbitrary Sign”, Operations Research Proceedings, Springer, 2002, 241–246

[8] Icmeli O., Erenguc S. S., “A Branch and Bound Procedure for the Resource Constrained Project Scheduling Problem with Discounted Cash Flows”, Management Science, 42:10 (1996), 1395–1408 | DOI | Zbl

[9] Herroelen W. S., Van Dommelen P., Demeulemeester E. L., “Project Network Models with Discounted Cash Flows a Quided Tour through Recent Revelopments”, European Journal of Operational Research, 100 (1997), 97–121 | DOI | Zbl

[10] Karp R. M., “Reducibility among Combinatorial Problems”, Complexity of Computer Computations, eds. R. E. Miller, J. W. Thatcher (eds.), Plenum Press, N.Y., 1972, 85–103 | DOI | MR

[11] Kolish R., Padman R., “An Integrated Survey of Deterministic Project Scheduling”, OMEGA — The International Journal of Management Science, 29 (2001), 249–272 | DOI