Minimizing flow time nonclairvoyantly

We consider the problem of scheduling a collection of dynamically arriving jobs with unknown execution times so as to minimize the average response/flow time. This is the classic CPU scheduling problem faced by time sharing operating systems. In the standard 3-field scheduling notation this is the nonclairvoyant version of 1|pmtn, r_j|ΣF_j. Its easy to see that every algorithm that doesn´t unnecessarily idle the processor is at worst n-competitive, where n is the number of jobs. Yet there is no known nonclairvoyant algorithm, deterministic or randomized, with a competitive ratio provably o(n). We present a randomized nonclairvoyant algorithm, RMLF, that has competitive ratio θ(lognloglogn) against an adaptive adversary. RMLF is a slight variation of the multi level feedback (MLF) algorithm used by the Unix operating system, further justifying the adoption of this algorithm. R. Motwani et al. (1994) showed that every randomized nonclairvoyant algorithm is Ω2(log n)competitive, and that every deterministic nonclairvoyant algorithm is Ω2(n^1/3 )-competitive