John R. Kender, Rick Kjeldsen
IEEE Transactions on Pattern Analysis and Machine Intelligence
Paper
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.