Minimizing weighted flow time

Abstract

We consider the problem of minimizing the total weighted flow time on a single machine with preemptions. We give an online algorithm that is O(k)-competitive for k weight classes. This implies an O(log W)-competitive algorithm, where W is the maximum to minimum ratio of weights. This algorithm also implies an O(log n + log P)-approximation ratio for the problem, where P is the ratio of the maximum to minimum job size and n is the number of jobs. We also consider the nonclairvoyant setting where the size of a job is unknown upon its arrival and becomes known to the scheduler only when the job meets its service requirement. We consider the resource augmentation model, and give a (1 + ε)-speed, (1 +1/ε)-competitive online algorithm.