Minimizing flow time on a constant number of machines with preemption

Abstract

We consider offline algorithms for minimizing the total flow time on O(1) machines where jobs can be preempted arbitrarily but migrations are disallowed. Our main result is a quasi-polynomial time approximation scheme for minimizing the total flow time. We also consider more general settings and give some hardness results. © 2004 Elsevier B.V. All rights reserved.