Geodesic
Polynomially Solvable Cases of the Project Scheduling Problem with~Changing Consumption and Supply Rates of Nonaccumulative Resources
The Bulletin of Irkutsk State University. Series Mathematics, Tome 9 (2014), pp. 26-38

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

We consider a strongly NP-hard project scheduling problem with nonaccumulative resources and sequence constraints. A distinctive feature of the formulation is that the rate of resource consumption by a task may change in duration of the task, and the resource availability depends on time. The problem is proved to be pseudo-polynomially solvable if the width of the partial order is bounded by a constant, being NP-hard. New polynomially solvable case of the problem is found.
Keywords: project scheduling, nonaccumulative resources, dynamic programming, polynomial solvability
Mots-clés : pseudo-polynomial solvability. 
@article{IIGUM_2014_9_a2,
     author = {A. V. Eremeev and J. V. Kovalenko},
     title = {Polynomially {Solvable} {Cases} of the {Project} {Scheduling} {Problem} {with~Changing} {Consumption} and {Supply} {Rates} of {Nonaccumulative} {Resources}},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {26--38},
     publisher = {mathdoc},
     volume = {9},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2014_9_a2/}
}
TY  - JOUR
AU  - A. V. Eremeev
AU  - J. V. Kovalenko
TI  - Polynomially Solvable Cases of the Project Scheduling Problem with~Changing Consumption and Supply Rates of Nonaccumulative Resources
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2014
SP  - 26
EP  - 38
VL  - 9
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2014_9_a2/
LA  - ru
ID  - IIGUM_2014_9_a2
ER  - 
%0 Journal Article
%A A. V. Eremeev
%A J. V. Kovalenko
%T Polynomially Solvable Cases of the Project Scheduling Problem with~Changing Consumption and Supply Rates of Nonaccumulative Resources
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2014
%P 26-38
%V 9
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IIGUM_2014_9_a2/
%G ru
%F IIGUM_2014_9_a2
A. V. Eremeev; J. V. Kovalenko. Polynomially Solvable Cases of the Project Scheduling Problem with~Changing Consumption and Supply Rates of Nonaccumulative Resources. The Bulletin of Irkutsk State University. Series Mathematics, Tome 9 (2014), pp. 26-38. http://geodesic.mathdoc.fr/item/IIGUM_2014_9_a2/