Next: MINIMUM PRECEDENCE CONSTRAINED SEQUENCING Up: Sequencing on One Processor Previous: MAXIMUM CONSTRAINED SEQUENCING TO Index

### MINIMUM STORAGE-TIME SEQUENCING

- 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 w(t1,t2) measuring the storage required to save the intermediate results generated by task t1 until it is consumed by task t2.

- 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 [394].