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 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2014},
     volume = {9},
     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
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
%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/

[1] Aygner M., Combinatory theory, World, M., 1982, 558 pp. | MR

[2] Gimadi E. Kh., Zalyubovskii V. V., Sevast'yanov S. V., “Polynomial Solvability of Project Scheduling Problems with Accumulative Resources and Directive Deadlines”, Diskretn. Anal. Issled. Oper. Ser. 2, 7:1 (2000), 9–34 | MR | Zbl

[3] Eremeev A. V., Kovalenko J. V., “Project Scheduling with Continuous Consumption of Raw Material in Production”, Book of Abstracts of Discrete Analysis and Oper. Res. Conf., Institute of Mathematics, Novosibirsk, 2010, 138

[4] Kovalenko J. V., “Solving of the Project Scheduling Problem with Continuous Consumption of Raw Material in Production”, Youth of the Third Millennium, The XXXIV Regional Scientific and Practical Student's Conference, Collected Articles of Section “Physical and Mathematical Sciences”, OmSU, Omsk, 2010, 21–24

[5] Kovalenko J. V., “On Project Scheduling Problem with Renewable Resource”, Automation and Remote control, 2012, no. 6, 140–153 | MR | Zbl

[6] Kormen T., Leyzerson H., Rivest R., Stein K., Algorithms: Construction and Analysis, Williams, M., 2005, 1296 pp.

[7] Kochetov Yu. A., Stolyar A. A., “New Greedy Heuristics for the Project Scheduling Problem with Limited Resources”, Diskretn. Anal. Issled. Oper. Ser. 2, 12:1 (2005), 12–36 | MR | Zbl

[8] Servakh V. V., “An Efficiently Solvable Case of the Project Scheduling Problem with renewable resources”, Diskretn. Anal. Issled. Oper. Ser. 2, 7:1 (2000), 75–82 | MR | Zbl

[9] C. E. Bell, J. Han, “A new heuristic solution method in resource constrained project scheduling”, Naval Res. Logistics, 38 (1991), 315–331 | 3.0.CO;2-7 class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[10] P. Brucker, S. Knust, A. Schoo, O. Thiele, “A branch and bound algorithm for the resource-constrained project scheduling problem”, Eur. J. Oper. Res., 107 (1998), 272–288 | DOI | Zbl

[11] P. Brucker, A. Krämer, “Polynomial algorithms for resource constrained and multiprocessor task scheduling problems”, Eur. J. Oper. Res., 90:2 (1996), 214–226 | DOI | Zbl

[12] N. Christofides, R. Alvarez-Valdes, J. M. Tamarit, “Project scheduling with resource constraints: a branch and bound approach”, European J. Oper. Res., 29 (1987), 262–273 | DOI | MR | Zbl

[13] J. Kallrath, A. Eremeev, P. Borisovsky, J. Kovalenko, Scheduling using continuous-time formulations, Technical report, BASF SE, Scientifc Computing, Ludwigshafen, 2010, 337 pp.

[14] A. A. B. Pritsker, L. J. Watters, P. M. Wolfe, “Multiproject scheduling with limited resources: a zero-one programming approach”, Management Sci., 16 (1969), 93–107 | DOI

[15] V. V. Servakh, T. A. Shcherbinina, “A fully polynomial time approximation scheme for two project scheduling problems”, Inform. Control Problems in Manufact., Proc. of 12th IFAC Intern. Symp., v. 3, eds. Dolgui A., Morel G., Pereira C. E., Elsevier Science, Saint-Etienne, 2006, 129–134

[16] Y. N. Sotskov, N. V. Shakhlevich, “NP-hardness of shop-scheduling problems with three jobs”, Discrete Appl. Math., 59:3 (1995), 237–266 | DOI | MR | Zbl