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