Treffer: Optimal on-line algorithms to minimize makespan on two machines with resource augmentation
Title:
Optimal on-line algorithms to minimize makespan on two machines with resource augmentation
Authors:
Source:
Approximation and online algorithms (Budapest, 16-18 September 2003, revised papers)Lecture notes in computer science. :109-122
Publisher Information:
Berlin: Springer, 2004.
Publication Year:
2004
Physical Description:
print, 33 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, Logiciel, Software, Généralités, General, Algorithme compétitif, Competitive algorithms, Algorithme optimal, Optimal algorithm, Algoritmo óptimo, Ordonnancement, Scheduling, Reglamento, Temps total achèvement, Makespan, Tiempo total acabamiento
Document Type:
Konferenz
Conference Paper
File Description:
text
Language:
English
Author Affiliations:
School of Computer Science, The Interdisciplinary Center, Herzliya, Israel
School of Computer Science, Tel-Aviv University, Ramat-Aviv, Tel-Aviv, Israel
School of Computer Science, Tel-Aviv University, Ramat-Aviv, Tel-Aviv, Israel
ISSN:
0302-9743
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
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.15671393
Database:
PASCAL Archive
Weitere Informationen
We study the problem of on-line scheduling on two uniformly related machines where the on-line algorithm has resources different from those of the off-line algorithm. We consider three versions of this problem: preemptive semi-online, non-preemptive on-line and preemptive on-line scheduling. For all these cases we design algorithms with best possible competitive ratios as a function of the machine speeds.