Algorithms for flow time scheduling
Nikhil Bansal, Avrim L. Blum · 2003
In this thesis proposal we address problems in scheduling related to minimizing ow time. The ow time of a job is the time it spends until its service requirement is met. We study three fundamental problems: First, we consider the problem of minimizing weighted ow time on a single machine. We give the rst truly online algorithm with a non-trivial competitive ratio. Second, we study online algorithms for minimizing the L p norms of ow time and stretch (stretch of job is its ow time divided by its size). Both these problems are also studied in the non-clairvoyant setting where the size of a job is not known upon its arrival. We give a general technique to reduce a non-clairvoyant problem to a (usually simpler) clairvoyant problem. Third, is the oine problem of minimizing the total ow time on multiple machines. We give a Quasi-polynomial time approximation scheme (a 1 + approximation algorithm with a running time n O(log n) ) for a constant number of machines. The previous best known approximation result for the problem was an O(log n) approximation, where n is the number of jobs [30, 3].