MINIMUM STORAGE-TIME SEQUENCING

• INSTANCE: Set T of tasks, a directed acyclic graph $G=\left(T,E\right)$ defining precedence constraints for the tasks, for each task a length $l(t)\in Z^+$, and for each edge in the graph a weight $w(t_1,t_2)$ measuring the storage required to save the intermediate results generated by task $t_1$ until it is consumed by task $t_2$.

• SOLUTION: A one-processor schedule for T that obeys the precedence constraints, i.e., a permutation $\pi: [1..\vert T\vert ]\rightarrow[1..\vert T\vert ]$ such that, for each edge $\left<t_i,t_j\right>\in E$, $\pi^{-1}(i)<\pi^{-1}(j)$.

• MEASURE: The total storage-time product, i.e.,
  
  $$\displaystyle\sum\limits_{ \left<t_{\pi(i)},t_{\pi(j)}\right>... ...isplaystyle\sum\limits_{k=\min(i,j)}^{\max(i,j)} l(t_{\pi(k)}).$$
  
  

  
  

• Good News: Approximable within $O(\log\vert T\vert)$ [416].