Next: MINIMUM PRECEDENCE CONSTRAINED SEQUENCING
Up: Sequencing on One Processor
Previous: MAXIMUM CONSTRAINED SEQUENCING TO
  Index
- INSTANCE:
Set T of tasks, a directed acyclic graph
defining precedence
constraints for the tasks, for each task a length
,
and for each
edge in the graph a weight
measuring the storage required
to save the intermediate results generated by task
until it is
consumed by task
.
- SOLUTION:
A one-processor schedule for T that obeys the precedence constraints, i.e.,
a permutation
such that, for each edge
,
.
- MEASURE:
The total storage-time product, i.e.,
- Good News:
Approximable within
[416].
Viggo Kann
2000-03-20