Online weighted flow time and deadline scheduling

In this paper we study some aspects of weighted flow time on parallel machines. We first show that the online algorithm Highest Density First is an O(1)-speed O(1)-approximation algorithm for Pr(i), pmtn Sigma w(i)F(i). 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 finally give an O(1)-competitive algorithm for Deadline Scheduling