Online weighted flow time and deadline scheduling

In this paper we study some aspects of weighted flow time. We first show that the online algorithm Highest Density First is an O(1)-speed O(1)-approximation algorithm for P | ri, pmtn | ∑ wi Fi. We then consider a related Deadline Scheduling Problem that involves minimizing the weight of the jobs unfinished by some unknown deadline D on a uniprocessor. We show that any c-competitive online algorithm for weighted flow time must also be c-competitive for deadline scheduling. We then give an O(1)-competitive algorithm for deadline scheduling. © 2005 Elsevier B.V. All rights reserved