Next: MINIMUM WEIGHTED COMPLETION TIME Up: Multiprocessor Scheduling Previous: MINIMUM MULTIPROCESSOR SCHEDULING WITH Index

### MINIMUM PARALLEL PROCESSOR TOTAL FLOW TIME

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

- 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 total flow time for the schedule, i.e., .

- Good News: Approximable within where n=|T| [333].

- Bad News: Not approximable within for any [333].

- Comment: In the case m=1, it is approximable within and it is not approximable within for any [285]. In the preemptive case, that is, in the case a job that is running can be preempted and continue later on any machine, the problem is approximable within and it is not approximable within where [333]. Variation in which all speed factors are 1 and the load is measured using the Lp norm, i.e. , admits a PTAS for any [10].

Next: MINIMUM WEIGHTED COMPLETION TIME Up: Multiprocessor Scheduling Previous: MINIMUM MULTIPROCESSOR SCHEDULING WITH Index