• Improved competitive algorithm...

Treffer: Improved competitive algorithms for online scheduling with partial job values

Title:
Improved competitive algorithms for online scheduling with partial job values
Authors:
CHIN, Francis Y. L, FUNG, Stanley P. Y
Source:
COCOON 2003 : computing and combinatorics (Big Sky MT, 25-28 July 2003)Lecture notes in computer science. :425-434
Publisher Information:
Berlin: Springer, 2003.
Publication Year:
2003
Physical Description:
print, 14 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, 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, Logiciel, Software, Systèmes informatiques et systèmes répartis. Interface utilisateur, Computer systems and distributed systems. User interface, Algorithme compétitif, Competitive algorithms, Borne inférieure, Lower bound, Cota inferior, Borne supérieure, Upper bound, Cota superior, Charge travail, Workload, Carga trabajo, Compétitivité, Competitiveness, Competitividad, Gestion tâche, Task scheduling, Gestión labor, Multiprocesseur, Multiprocessor, Multiprocesador, Ordonnancement, Scheduling, Reglamento, Qualité service, Service quality, Calidad servicio, Temps traitement, Processing time, Tiempo proceso
Document Type:
Konferenz Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Department of Computer Science and Information Systems, The University of Hong Kong, Hong-Kong
ISSN:
0302-9743
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=15567739
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

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

Weitere Informationen

This paper considers an online scheduling problem arising from Quality-of-Service (QoS) applications. We are required to schedule a set of jobs, each with release time, deadline, processing time and weight. The objective is to maximize the total value obtained for scheduling the jobs. Unlike the traditional model of this scheduling problem, in our model unfinished jobs also get partial values proportional to their amounts processed. We give a new non-timesharing algorithm GAP for this problem for bounded m, where m is the number of concurrent jobs or the number of weight classes. The competitive ratio is improved from 2 to 1.618 (golden ratio) which is optimal for m = 2, and when applied to cases with m > 2 it still gives a competitive ratio better than 2, e.g. 1.755 when m = 3. We also give a new study of the problem in the multiprocessor setting, giving an upper bound of 2 and a lower bound of 1.25 for the competitiveness. Finally, we consider resource augmentation and show that O(log α) speedup or extra processors is sufficient to achieve optimality, where α is the importance ratio. We also give a tradeoff result between competitiveness and the amount of extra resources.