ALCOMFT-TR-01-42

Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela and Kirk Pruhs
Online Weighted Flow Time and Deadline Scheduling
Rome. Work package 4. April 2001.

Abstract: Optimizing the weighted flow time of a set of jobs released over time is a difficult and challenging scheduling problem. Weighted flow time is also intimately related to scheduling broadcasts to minimize average user perceived latency in a client-server system where the server communicates to the clients via broadcast. In this paper we show that the algorithm Highest Density First is an O(1)-speed O(1)-approximation algorithm for the scheduling problem P | r_i, pmtn | \sum w_i F_i, minimizing weighted flow time with preemption on a multiprocessor. We also consider a second related problem that we call the Deadline Scheduling Problem (DSP), which involves minimizing the weight of the jobs unfinished by some unknown deadline D on a uniprocessor. We show that every c-competitive online algorithm for 1 | r_i, pmtn | \sum w_i F_i, must also be c-completive for DSP. We then give an O(1)-competitive algorithm for DSP. We then draw conclusions about to develop and analyze algorithms for broadcast scheduling.

Postscript file: ALCOMFT-TR-01-42.ps.gz (182 kb).