Next: MINIMUM SEQUENCING WITH RELEASE
Up: Sequencing on One Processor
Previous: MINIMUM STORAGE-TIME SEQUENCING
Set T of tasks, a directed acyclic graph
constraints for the tasks, a positive integer D, and for each task an
A one-processor schedule for T that obeys the precedence constraints and
the delays, i.e., an injective function
for each edge
The finish time for the schedule, i.e.,
- Good News:
Approximable within 2-1/(D+1) .
Approximable within 2-2/(D+1) if
for all tasks t.