CMU-CS-03-103
Computer Science Department
School of Computer Science, Carnegie Mellon University



CMU-CS-03-103

Approximation Schemes for Flow Time on Multiple Machines

Nikhil Bansal

January 2003

CMU-CS-03-103.ps
CMU-CS-03-103.pdf


Keywords: Flow time, multiple machines, approximation schemes, preemption, unrelated machines, approximation algorithms


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