|
Vestnik Novosibirskogo Gosudarstvennogo Universiteta. Seriya Matematika, Mekhanika, Informatika, 2008, Volume 8, Issue 3, Pages 105–112
(Mi vngu300)
|
|
|
|
This article is cited in 3 scientific papers (total 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.
Received: 21.12.2007
Citation:
V. V. Servakh, T. A. Shcherbinina, “Complexity of some project scheduling problem with nonrenewable resources”, Vestn. Novosib. Gos. Univ., Ser. Mat. Mekh. Inform., 8:3 (2008), 105–112
Linking options:
https://www.mathnet.ru/eng/vngu300 https://www.mathnet.ru/eng/vngu/v8/i3/p105
|
Statistics & downloads: |
Abstract page: | 172 | Full-text PDF : | 77 | References: | 29 | First page: | 1 |
|