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.
Original language | English |
---|---|
Pages (from-to) | 267-273 |
Journal | Operations Research Letters |
Volume | 33 |
Issue number | 3 |
DOIs | |
Publication status | Published - 2005 |