I
NSTANCE
:
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
.
S
OLUTION
:
A one-processor schedule for
T
that obeys the precedence constraints and
the delays, i.e., an injective function
such that,
for each edge
,
.
M
EASURE
:
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
.