
CMUCS02128
Computer Science Department
School of Computer Science, Carnegie Mellon University
CMUCS02128
Minimizing Weighted Flow Time
Nikhil Bansal, Kedar Dhamdhere
April 2002
CMUCS02128.ps
CMUCS02128.pdf
Keywords: Weighted flow time, response time, online
algorithms, job scheduling, single machine, preemption,
nonclairvoyance, 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 nonclairvoyant 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 nonclairvoyant online algorithm is
allowed a (1+epsilon) speedup, then it is (1+1/epsilon) competitive
against an optimal offline, clairvoyant algorithm.
20 pages
