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)).
|Title of host publication||Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04, New Orleans LA, USA, January 11-14, 2004)|
|Place of Publication||New York|
|Publisher||Association for Computing Machinery, Inc|
|Publication status||Published - 2004|