Next: MINIMUM SEQUENCING WITH RELEASE
Up: Sequencing on One Processor
Previous: MINIMUM STORAGE-TIME SEQUENCING
  Index
- 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.
Viggo Kann
2000-03-20