Non-clairvoyant scheduling for minimizing mean slowdown

N. Bansal, K. Dhamdhere, J. Könemann, A. Sinha

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

23 Citaten (Scopus)


We consider the problem of scheduling dynamically arriving jobs in a non-clairvoyant setting, that is, when the size of a job in remains unknown until the job finishes execution. Our focus is on minimizing the mean slowdown, where the slowdown (also known as stretch) of a job is defined as the ratio of the 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 that the Shortest Elapsed Time First (SETF) algorithm, a close variant of which is used in the Windows NT and Unix operating system scheduling policies, is a (1+e)(1+\epsilon)-speed, O((1/e)5 log2 B)O((1/\epsilon)^5 \log^2 B)-competitive algorithm for minimizing mean slowdown non-clairvoyantly, when BB is the ratio between the largest and smallest job sizes. In a sense, this provides a theoretical justification of the effectiveness of an algorithm widely used in practice. On the other hand, we also show that any O(1)O(1)-speed algorithm, deterministic or randomized, is W(min(n,logB))\Omega(\min(n,\log B))-competitive. The motivation for resource augmentation is supported by an W(min(n,B))\Omega(\min(n,B)) lower bound on the competitive ratio without any speedup. For the static case, i.e., when all jobs arrive at time 0, we show that SETF is O(logB)O(\log{B}) competitive without any resource augmentation and also give a matching W(logB)\Omega(\log{B}) lower bound on the competitiveness.
Originele taal-2Engels
Pagina's (van-tot)305-318
Nummer van het tijdschrift4
StatusGepubliceerd - 2004
Extern gepubliceerdJa


Duik in de onderzoeksthema's van 'Non-clairvoyant scheduling for minimizing mean slowdown'. Samen vormen ze een unieke vingerafdruk.

Citeer dit