Next: MINIMUM TIME-COST TRADEOFF Up: Sequencing on One Processor Previous: MINIMUM PRECEDENCE CONSTRAINED SEQUENCING Index

### MINIMUM SEQUENCING WITH RELEASE TIMES

- INSTANCE: Set T of tasks, for each task a release time , a length , and a weight .
- SOLUTION: A one-processor schedule for T that obeys the release times, i.e. a function such that, for all , if S(u) is the set of tasks t for which , then |S(u)| = 1 and for each task t, .
- MEASURE: The weighted sum of completion times, i.e. .

- Good News: Approximable within 1.6853 [184].

- Comment: Approximable within if all weights w(t)=1 [93]. Variation in which there are precedence constraints on T instead of release times is approximable within 2 [203]. The preemptive case is approximable within 4/3 [408]. Variation in which there are precedence constraints and release times is approximable within e [410]. If all weights w(t)=1 and the objective is to minimize the max-stretch the nonpreemptive problem is not approximable within for any , but the preemptive problem admits a PTAS [65].

Next: MINIMUM TIME-COST TRADEOFF Up: Sequencing on One Processor Previous: MINIMUM PRECEDENCE CONSTRAINED SEQUENCING Index