Next: MINIMUM SEQUENCING WITH RELEASE Up: Sequencing on One Processor Previous: MINIMUM STORAGE-TIME SEQUENCING Index

### MINIMUM PRECEDENCE CONSTRAINED SEQUENCING WITH DELAYS

- 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 , S(tj)-S(ti)>d(ti).

- MEASURE: The finish time for the schedule, i.e., .

- Good News: Approximable within 2-1/(D+1) [73].

- Comment: Approximable within 2-2/(D+1) if for all tasks t.