We consider the problem of scheduling jobs online non-clairvoyantly, that is, when the job sizes are not known. Our focus is on minimizing mean slowdown, defined as the ratio of response time to the size of the job. We first show that no (deterministic or randomized) algorithm can achieve a competitive ratio of Omega(n), where n is the number of jobs.

Resource augmentation is the concept of allowing the online algorithm a speed-up to make up for its non-clairvoyance, since the competitive ratio is obtained by comparing against an optimal offline, clairvoyant algorithm. We show that our lower bound continues to hold even with resource augmentation.

Finally, we consider the case when the ratio of job sizes (denoted B) is bounded. In this case, we show that any non-clairvoyant algorithm needs at least Omega(logB) speed up to be constant competitive. We provide an algorithm which is O(log² B) competitive when the speed up is O(logB). In the special case when all the jobs arrive at the same time we provide an algorithm which is constant competitive and uses a O(logB) speed up.

20 pages

*Graduate School of Industrial Administration, Carnegie Mellon University

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by [email protected]