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

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

(1, 2) , (3) , (1, 2) , (2, 1)
1
2
3

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

Paternité - Pas d'utilisation commerciale - Pas de modification - CC BY 4.0

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⟩
777 Consultations
374 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More