On Solvability of the Project Scheduling Problem with Accumulative Resources of an Arbitrary Sign

A project scheduling problem (PSP) with precedence constraints, deadlines and resource constraints is considered. It was known before that PSP is polynomially solvable if all resource constraints are of so called accumulative type (please, don’t mix the notion with completely different notions cumulative and cumulatives lately introduced in the literature and being nothing but a kind of renewable resource constraints!), provided that both resource availabilities and resource requirements are non-negative. Now we show that PSP with accumulative resource constraints remains polynomially solvable if we allow resource availabilities of an arbitrary sign, while all resource requirements remain non-negative. On the other hand, it is shown that in the case of resource requirements of an arbitrary sign the problem becomes NP-hard in strong sense.