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 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