Online Non-Preemptive Scheduling to Optimize Max Stretch on a Single Machine - Université Grenoble Alpes
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
full-proof-copy.pdf (185.41 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Licence

Identifiants

  • HAL Id : hal-01309052 , version 2

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 (COCOON 2016), Aug 2016, Ho-Chi-Minh-Ville, Vietnam. ⟨hal-01309052v2⟩
819 Consultations
461 Téléchargements

Partager

More