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

A. V. Eremeev^a, J. V. Kovalenko<sup>b

a</sup> Omsk Branch of Sobolev Institute of Mathematics SB RAS, 13, Pevcov st., Omsk, 644099
^b Omsk Juridical Academy, 12, Korolenko Str., Omsk, 644010

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