Single Machine Scheduling with Series-Parallel Precedence Constraints

R. N. Burns and Gerald Steiner
Additional contact information
R. N. Burns: University of Waterloo, Waterloo, Ontario

Operations Research, 1981, vol. 29, issue 6, 1195-1207

Abstract: This paper considers a set of tasks to be sequenced for processing on a single machine. The possible sequences may be restricted by given precedence constraints. For each feasible sequence we have an additive cost function (e.g., tardiness or weighted tardiness) and the objective is to find a feasible sequence with minimal total cost. An efficient algorithm is presented for the case when the set of precedence constraints can be represented by a series-parallel graph. The algorithm is based on the earlier known dynamic programming approach, its main new achievement is the use of a compact labeling scheme for series-parallel graphs which is the best possible in a certain sense.

Keywords: 112 single machine scheduling; 584 series-parallel precedence (search for similar items in EconPapers)
Date: 1981
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.29.6.1195 (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:29:y:1981:i:6:p:1195-1207

Access Statistics for this article

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