RUS  ENG
Full version
JOURNALS // Siberian Journal of Pure and Applied Mathematics // Archive

Vestn. Novosib. Gos. Univ., Ser. Mat. Mekh. Inform., 2008 Volume 8, Issue 3, Pages 105–112 (Mi vngu300)

This article is cited in 3 papers

Complexity of some project scheduling problem with nonrenewable resources

V. V. Servakha, T. A. Shcherbininab

a Omsk Branch of Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
b Omsk State University

Abstract: 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.

UDC: 519.8

Received: 21.12.2007



© Steklov Math. Inst. of RAS, 2024