Next: MINIMUM 3-DEDICATED PROCESSOR SCHEDULING Up: Multiprocessor Scheduling Previous: MINIMUM PARALLEL PROCESSOR TOTAL Index

### MINIMUM WEIGHTED COMPLETION TIME SCHEDULING

- INSTANCE: Set T of tasks, number m of identical processors, for each task a release time , a length , and a weight .

- SOLUTION: An m-processor schedule for T that obeys the resource constraints and the release times, i.e., a function such that, for all and for each processor i, if S(u,i) is the set of tasks t for which and f(t)2=i, then |S(u,i)| = 1 and for each task t, .

- MEASURE: The weighted sum of completion times, i.e. .

- Good News: Approximable within 2 [409].

- Comment: The preemptive case is also approximable within 2 [379]. Generalization to unrelated processors (where the length of a task also depends in the processor) is approximable within 2 for any for both nonpreemptive and preemptive scheduling [409]. Restriction (of the nonpreemptive case) where r(t)=0 for all t is approximable within 3/2 [410]. Generalization where there are precedence constraints on T that must be obeyed in the solution is approximable within 5.33 [88].

- Garey and Johnson: SS13

Next: MINIMUM 3-DEDICATED PROCESSOR SCHEDULING Up: Multiprocessor Scheduling Previous: MINIMUM PARALLEL PROCESSOR TOTAL Index