• Non-clairvoyant scheduling for...

Treffer: Non-clairvoyant scheduling for minimizing mean slowdown

Title:
Non-clairvoyant scheduling for minimizing mean slowdown
Authors:
BANSAL, N, DHAMDHERE, K, KÖNEMANN, J, SINHA, A
Source:
STACS 2003 : 20th annual symposium on theoretical aspects of computer science (Berlin, 27 February - 1 March 2003)Lecture notes in computer science. :260-270
Publisher Information:
Berlin: Springer, 2003.
Publication Year:
2003
Physical Description:
print, 15 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Algorithme compétitif, Competitive algorithms, Algorithme déterministe, Deterministic algorithms, Charge travail, Workload, Carga trabajo, Compétitivité, Competitiveness, Competitividad, Gestion tâche, Task scheduling, Gestión labor, Ordonnancement, Scheduling, Ordonamiento, Plan randomisé, Randomized design, Plan aleatorizado
Document Type:
Konferenz Conference Paper
File Description:
text
Language:
English
Author Affiliations:
School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, United States
Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PA 15213, United States
ISSN:
0302-9743
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=14724922
Rights:
Copyright 2003 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.14724922
Database:
PASCAL Archive

Weitere Informationen

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(log2 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 Q(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.