MINIMUM PRECEDENCE CONSTRAINED SEQUENCING WITH DELAYS

• INSTANCE: Set T of tasks, a directed acyclic graph $G=\left(T,E\right)$ defining precedence constraints for the tasks, a positive integer D, and for each task an integer delay $0\le d(t)\le D$.

• SOLUTION: A one-processor schedule for T that obeys the precedence constraints and the delays, i.e., an injective function $S: T\rightarrow Z^+$ such that, for each edge $\left<t_i,t_j\right>\in E$, $S(t_j)-S(t_i)>d(t_i)$.

• MEASURE: The finish time for the schedule, i.e., $\max\limits_{t\in T} S(t)$.

  
  

• Good News: Approximable within 2-1/(D+1) [79].

• Comment: Approximable within 2-2/(D+1) if $d(t)\in\{0,D\}$ for all tasks t.