• On-line scheduling with tight...

Treffer: On-line scheduling with tight deadlines

Title:
On-line scheduling with tight deadlines
Authors:
KOO, Chiu-Yuen, LAM, Tak-Wah, NGAN, Tsuen-Wan, SADAKANE, Kunihiko, TO, Kar-Keung
Source:
Mathematical foundations of computer science (MFCS 2001)Theoretical computer science. 295(1-3):251-261
Publisher Information:
Amsterdam: Elsevier, 2003.
Publication Year:
2003
Physical Description:
print, 16 ref
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, Logiciel, Software, Performances des systèmes informatiques. Fiabilité, Computer systems performance. Reliability, Algorithme compétitif, Competitive algorithms, Algorithme optimal, Optimal algorithm, Algoritmo óptimo, Algorithme, Algorithm, Algoritmo, Constante, Constant, Ordonnancement, Scheduling, Ordonamiento, Problème, Problem, Problema, Processeur, Processor, Procesador, Système, System, Sistema, Temps, Time, Tiempo, Traitement en ligne, On line processing, Tratamiento en línea, Analyse compétitive, Competitive analysis
Time:
2000, 2001
Document Type:
Konferenz Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Department of Computer Science, University of Maryland, College Park, MD 20742, United States
Department of Computer Science, University of Hong Kong, Pokfulam Road, Hong-Kong
Graduate School of Information Sciences, Tohoku University, Sendai 980-8579, Japan
ISSN:
0304-3975
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=14570846
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

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

Weitere Informationen

This paper is concerned with the on-line problem of scheduling jobs with tight deadlines in a uni-processor system. It has been known for long that in such a setting, no on-line algorithm is 1-competitive (i.e., optimal) in the sense of matching the optimal off-line algorithm on the total value of jobs that meet the deadlines; indeed, no algorithm can be better than k-competitive, where k is the importance ratio of the jobs. Recent work, however, reveals that the competitive ratio can be improved to a constant if the on-line scheduler is equipped with a processor O(1) times faster (J. ACM 47(4) (2000) 617), and further to one when using a processor O(logk) times faster (Proc. 12th Ann. ACM-SIAM Symp. on Discrete Algorithms, 2001, p. 755). This paper presents a new on-line algorithm for scheduling jobs with tight deadlines and shows that it is 1-competitive when using a processor that is only O(1) times faster.