On minimizing the total flow time on multiple machines

We consider the problem of minimizing the total flow time on multiple machines with preemption, where the flow time of a job is the time spent since it arrives until it finishes. Our main result is a quasi-polynomial time approximation scheme for a constant number of machines (m). The result also extends to total weighted flow time where either the job weights or the job sizes are polynomially bounded by the number of jobs (n). We also show that the dependence on m cannot be substantially improved. In particular, obtaining an O(1) approximation for the weighted case (even when all weights and sizes are polynomially bounded by n) by an algorithm with running time npolylog(n,m) would imply that NP ¿ DTIME(npolylog(n))