We consider the problem of scheduling jobs on multiple machines with preemption with the goal of minimizing the total flow time and the maximum flow time.

For minimizing total flow time, we give an algorithm which produces a 1 + epsilon approximate solution in time $n^O(m\log{n}\epsilon^2). n is the number of jobs and m is the number of machines. More generally, even if we have unrelated machines and consider weighted flow time, our algorithm has running time $n^{O(m \log^2{n} /\epsilon^3)}$, provided either P or W is poly-bounded in n. Here W(resp. $P$) is the ratio between the maximum to minimum job weight (resp. size).

For minimizing the maximum flow time, we give a PTAS for a constant number of unrelated machines.

10 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu