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
Liste complète des métadonnées

http://hal.univ-grenoble-alpes.fr/hal-01309052
Contributeur : Abhinav Srivastav <>
Soumis le : jeudi 28 avril 2016 - 18:24:20
Dernière modification le : jeudi 24 octobre 2019 - 10:35:58
Archivage à long terme le : mardi 15 novembre 2016 - 17:25:40

Fichier

max-stretch.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 1

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, Aug 2016, Ho Chi Minh City, Vietnam. ⟨hal-01309052v1⟩

Partager

Métriques

Consultations de la notice

24

Téléchargements de fichiers

20