Online Non-Preemptive Scheduling to Optimize Max Stretch on a Single Machine

Abstract : We consider in this work a classical online scheduling problem with release times on a single machine. The quality of service of a job is measured by its stretch, which is defined as the ratio of its response time over its processing time. Our objective is to schedule the jobs non-preemptively in order to optimize the maximum stretch. We present both positive and negative theoretical results. First, we provide an online algorithm based on a waiting strategy which is (1 + √ 5−1 2 ∆)-competitive where ∆ is the upper bound on the ratio of processing times of any two jobs. Then, we show that no online algorithm has a competitive ratio better than 1 + √ 5−1 2 ∆. The proposed algorithm is asymptotically the best algorithm for optimizing the maximum stretch on a single machine.
Type de document :
Communication dans un congrès
22nd International Computing and Combinatorics Conference (COCOON 2016), Aug 2016, Ho-Chi-Minh-Ville, Vietnam
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

http://hal.univ-grenoble-alpes.fr/hal-01309052
Contributeur : Abhinav Srivastav <>
Soumis le : lundi 16 mai 2016 - 16:53:39
Dernière modification le : jeudi 11 janvier 2018 - 06:27:41
Document(s) archivé(s) le : mercredi 16 novembre 2016 - 05:34:04

Fichier

full-proof-copy.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité - Pas d'utilisation commerciale - Pas de modification 4.0 International License

Identifiants

  • HAL Id : hal-01309052, version 2

Citation

Pierre-Francois Dutot, Erik Saule, Abhinav Srivastav, Denis Trystram. Online Non-Preemptive Scheduling to Optimize Max Stretch on a Single Machine. 22nd International Computing and Combinatorics Conference (COCOON 2016), Aug 2016, Ho-Chi-Minh-Ville, Vietnam. 〈hal-01309052v2〉

Partager

Métriques

Consultations de la notice

296

Téléchargements de fichiers

165