Accéder directement au contenu Accéder directement à la navigation
Nouvelle interface
Communication dans un congrès

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

https://hal.univ-grenoble-alpes.fr/hal-01309052
Contributeur : Abhinav Srivastav Connectez-vous pour contacter le contributeur
Soumis le : jeudi 28 avril 2016 - 18:24:20
Dernière modification le : mardi 19 octobre 2021 - 11:28:36
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

777

Téléchargements de fichiers

374