Non-clairvoyant Scheduling for Minimizing Mean Slowdown

摘要

We consider the problem of scheduling jobs online non-clairvoyantly, that is, when job sizes are not known. Our focus is on minimizing mean slowdown, defined as the ratio of flow time to the size of the job. We use resource augmentation in terms of allowing a faster processor to the online algorithm to make up for its lack of knowledge of job sizes. Our main result is an O(1)-speed O(log~2 B)-competitive algorithm for minimizing mean slowdown non-clairvoyantly, when B is the ratio between the largest and smallest job sizes. On the other hand, we show that any O(1)-speed algorithm, deterministic or randomized, is at least Ω(log B) competitive. The motivation for bounded job sizes is supported by an Ω(n) lower bound for arbitrary job sizes, where n is the number of jobs. Furthermore, a lower bound of Ω(B) justifies the need for resource augmentation even with bounded job sizes. For the static case, i.e. when all jobs arrive at time 0, we give an O(log B) competitive algorithm which does not use resource augmentation and a matching Ω(log B) lower bound on the competitiveness.