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

H. M. Abdel-Wahab and T. Kameda
Additional contact information
H. M. Abdel-Wahab: University of Waterloo, Waterloo, Ontario
T. Kameda: University of Waterloo, Waterloo, Ontario

Operations Research, 1978, vol. 26, issue 1, 141-158

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.

Date: 1978
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.26.1.141 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:26:y:1978:i:1:p:141-158

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().