Scheduling to Minimize Maximum Cumulative Cost Subject to Series-Parallel Precedence Constraints

Abstract

Consider a set of events that are constrained by a certain precedence relation. Associated with each event is a cost (an integer), which may be interpreted as an additional number of resource units necessary for the event to occur (units are released if the cost is negative). It is desired to order the events into a single sequence in such a way that the maximum cumulative cost encountered (largest number of resource units used at one time) is minimized. It is known that this problem is in general NP-complete. For the special case where the precedence constraints can be represented by a series-parallel graph, we present an algorithm for finding an optimal schedule whose running time does not grow faster than the square of the number of events.