- INSTANCE:
Set
*T*of tasks, a directed acyclic graph defining precedence constraints for the tasks, a positive integer*D*, and for each task an integer delay . - SOLUTION:
A one-processor schedule for
*T*that obeys the precedence constraints and the delays, i.e., an injective function such that, for each edge , . - MEASURE:
The finish time for the schedule, i.e.,
.

*Good News:*Approximable within*2-1/(D+1)*[79].*Comment:*Approximable within*2-2/(D+1)*if for all tasks*t*.