Result: Scheduling to minimize average completion time revisited: Deterministic on-line algorithms

Title:
Scheduling to minimize average completion time revisited: Deterministic on-line algorithms
Authors:
MEGOW, Nicole, SCHULZ, Andreas S
Source:
Approximation and online algorithms (Budapest, 16-18 September 2003, revised papers)Lecture notes in computer science. :227-234
Publisher Information:
Berlin: Springer, 2004.
Publication Year:
2004
Physical Description:
print, 18 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Mathematics, Mathématiques, 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 approximation, Approximation algorithm, Algoritmo aproximación, Algorithme compétitif, Competitive algorithms, Algorithme déterministe, Deterministic algorithms, Algorithme randomisé, Randomized algorithm, Algoritmo aleatorizado, Complétude, Completeness, Completitud, En ligne, On line, En línea, Machine parallèle, Parallel machines, Moyenne temporelle, Time average, Promedio temporal, Ordonnancement, Scheduling, Reglamento, Plan randomisé, Randomized design, Plan aleatorizado, Temps traitement, Processing time, Tiempo proceso, Moyenne pondérée, Weighted average
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Institut für Mathematik, Technische Universität Berlin, Sekr., MA 6-1, Strasse des 17. Juni 136, 10623 Berlin, Germany
Sloan School of Management, Massachusetts Institute of Technology, Office E53-361, 77 Massachusetts Avenue, Cambridge, MA 02139-4307, United States
ISSN:
0302-9743
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=15735224
Rights:
Copyright 2004 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.15735224
Database:
PASCAL Archive

Further Information

We consider the scheduling problem of minimizing the average weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith's ratio rule yield smaller competitive ratios compared to the previously best-known deterministic on-line algorithms, which are (4 + ε)-competitive in either case. Our preemptive algorithm is 2-competitive, which actually meets the competitive ratio of the currently best randomized on-line algorithm for this scenario. Our nonpreemptive algorithm has a competitive ratio of 3.28. Both results are characterized by a surprisingly simple analysis; moreover, the preemptive algorithm also works in the less clairvoyant environment in which only the ratio of weight to processing time of a job becomes known at its release date, but neither its actual weight nor its processing time. In the corresponding nonpreemptive situation, every on-line algorithm has an unbounded competitive ratio.