• Tighter approximation bounds f...

Treffer: Tighter approximation bounds for LPT scheduling in two special cases

Title:
Tighter approximation bounds for LPT scheduling in two special cases
Authors:
KOVACS, Annamaria
Source:
Algorithms and complexity (6th Italian conference, CIAC 2006, Rome, Italy, May 29-31, 2006)0CIAC 2006. :187-198
Publisher Information:
Berlin: Springer, 2006.
Publication Year:
2006
Physical Description:
print, 15 ref 1
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Recherche operationnelle. Gestion, Operational research. Management science, Recherche opérationnelle et modèles formalisés de gestion, Operational research and scientific management, Ordonnancement, Scheduling, sequencing, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Algorithme, Algorithm, Algoritmo, Borne inférieure, Lower bound, Cota inferior, Borne supérieure, Upper bound, Cota superior, Charge travail, Workload, Carga trabajo, Complexité calcul, Computational complexity, Complejidad computación, Gestion tâche, Task scheduling, Gestión labor, Méthode cas pire, Worst case method, Método caso peor, Ordonnancement, Scheduling, Reglamento, Publication en série, Serial, Publicación en serie, Système information, Information system, Sistema información, Temps total achèvement, Makespan, Tiempo total acabamiento, Temps traitement, Processing time, Tiempo proceso, Traitement liste, List processing, Tratamiento lista
Document Type:
Konferenz Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Max-Planck Institut für Informatik, Stuhlsatzenhausweg 85, 66123 Saarbrücken, Germany
ISSN:
0302-9743
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=19150310
Rights:
Copyright 2007 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

Operational research. Management
Accession Number:
edscal.19150310
Database:
PASCAL Archive

Weitere Informationen

Q∥Cmax denotes the problem of scheduling n jobs on m machines of different speeds such that the makespan is minimized. In the paper two special cases of Q∥Cmax are considered: Case I, when m - 1 machine speeds are equal, and there is only one faster machine; and Case II, when machine speeds are all powers of 2. Case I has been widely studied in the literature, while Case II is significant in an approach to design so called monotone algorithms for the scheduling problem. We deal with the worst case approximation ratio of the classic list scheduling algorithm 'Longest Processing Time (LPT)'. We provide an analysis of this ratio Lpt/Opt for both special cases: For one fast machine, a tight bound of (√3 + 1)/2 ~ 1.366 is given. When machine speeds are powers of 2 (2-divisible machines), we show that in the worst case 41/30 < Lpt/Opt < 42/30 = 1.4. To our knowledge, the best previous lower bound for both problems was 4/3 - e, whereas the best known upper bounds were 3/2 -1/2m for Case I [6] resp. 3/2 for Case II [10]. For both the lower and the upper bound, the analysis of Case II is a refined version of that of Case I.