Non-clairvoyant scheduling for minimizing mean slowdown

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

23 Citaten (Scopus)

Samenvatting

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
TijdschriftAlgorithmica
Volume40
Nummer van het tijdschrift4
DOI's
StatusGepubliceerd - 2004
Extern gepubliceerdJa

Vingerafdruk

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

Citeer dit