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.,
.
defining precedence
constraints for the tasks, a positive integer D, and for each task an
integer delay
.
such that,
for each edge
,
.
.
for all tasks t.