Computer Science Department
School of Computer Science, Carnegie Mellon University


Minimizing Weighted Flow Time

Nikhil Bansal, Kedar Dhamdhere

April 2002

Keywords: Weighted flow time, response time, online algorithms, job scheduling, single machine, preemption, non-clairvoyance, resource augmentation

We consider the problem of minimizing weighted flow time on a single machine in the preemptive setting. Our first result is an online algorithm which achieves a competitive ratio of k if there are k weight classes. Even for the special case of k=2 this gives the first O(1)-competitive algorithm. Our algorithm also directly gives an O(log{W}) competitive algorithm when the maximum to the minimum ratio of weights is W. Our second result deals with the non-clairvoyant setting where the job sizes are unknown (but the weight of the jobs are known). In this case, we give a resource augmented algorithm. In particular, if the non-clairvoyant online algorithm is allowed a (1+epsilon) speed-up, then it is (1+1/epsilon) competitive against an optimal offline, clairvoyant algorithm.

20 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by