рус eng
«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

List of issues > Series «Mathematics». 2014. Vol. 9

Polynomially Solvable Cases of the Project Scheduling Problem with Changing Consumption and Supply Rates of Nonaccumulative Resources

Author(s)
A. V. Eremeev, J. V. Kovalenko
Abstract

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, pseudo-polynomial solvability
UDC
519.718
References

1. Aygner M. Сombinatory theory. M., World, 1982, 558 p.

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., 2000, vol. 7, no. 1, pp. 9-34.

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., Novosibirsk, Institute of Mathematics, 2010, p. 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: CollectedArticles of Section "Physical and Mathematical Sciences", Omsk, OmSU, 2010, pp. 21-24.

5. Kovalenko J.V. On Project Scheduling Problem with Renewable Resource. Automation and Remote control, 2012, no. 6, pp. 140-153.

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

7. Kochetov Yu.A., Stolyar A.A. New Greedy Heuristics for the Project Scheduling Problem with Limited Resources. Diskretn. Anal. Issled. Oper. Ser. 2., 2005, vol. 12, no. 1, pp. 12-36.

8. Servakh V.V. An Efficiently Solvable Case of the Project Scheduling Problem with renewable resources. Diskretn. Anal. Issled. Oper. Ser. 2., 2000, vol. 7, no. 1, pp. 75-82.

9. Bell C.E., Han J. A New Heuristic Solution Method in Resource Constrained Project Scheduling. Naval Res. Logistics, 1991, vol. 38, pp. 315-331.

10. Brucker P., Knust S., Schoo A., Thiele O. A Branch and Bound Algorithm for the Resource-Constrained Project Scheduling Problem. Eur. J. Oper. Res., 1998, vol. 107, pp. 272-288.

11. Brucker P., Kr¨amer A. Polynomial Algorithms for Resource Constrained and Multiprocessor Task Scheduling Problems. Eur. J. Oper. Res., 1996, vol. 90, no. 2, pp. 214-226.

12. Christofides N., Alvarez-Valdes R., Tamarit J. M. Project Scheduling with Resource Constraints: a Branch and Bound Approach. European J. Oper. Res., 1987, vol. 29, pp. 262-273.

13. Kallrath J., Eremeev A., Borisovsky P., Kovalenko J. Scheduling Using Continuous-Time Formulations: Technical Report. Ludwigshafen, BASF SE, Scientifc Computing, 2010, 337 p.

14. Pritsker A.A.B., Watters L.J., Wolfe P.M. Multiproject Scheduling with Limited Resources: a Zero-One Programming Approach. Management Sci., 1969, vol. 16, pp. 93-107.

15. Servakh V.V., Shcherbinina T.A. A Flly Polynomial Time Approximation Scheme for Two Project Scheduling Problems. Inform. Control Problems in Manufact.: A Proc. of 12th IFAC Intern. Symp., eds. By Dolgui A., Morel G., Pereira C.E.,Saint-Etienne, Elsevier Science, 2006, vol. 3, pp. 129-134.

16. Sotskov Y.N., Shakhlevich N.V. NP-hardness of Shop-Scheduling Problems with Three Jobs. Discrete Appl. Math., 1995, vol. 59, no. 3, pp. 237-266.


Full text (russian)