Online Non-Preemptive Scheduling to Optimize Max Stretch on a Single Machine - Université Grenoble Alpes Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

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

Résumé

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.
Fichier principal
Vignette du fichier
max-stretch.pdf (343.11 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01309052 , version 1 (28-04-2016)
hal-01309052 , version 2 (16-05-2016)

Licence

Identifiants

  • HAL Id : hal-01309052 , version 1

Citer

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⟩
805 Consultations
431 Téléchargements

Partager

Gmail Mastodon Facebook X LinkedIn More