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

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.