Online Scheduling of Unit Length Jobs with Commitment and Penalties

Abstract : We consider the online scheduling of unit length jobs with two models of commitment. In immediate notification, the acceptance of a job must be decided as soon as it is released. In immediate decision, the actual time slot allocated to the job must also be fixed at the job’s arrival as well. Failure to honour a commitment will result in a penalty. The non-commitment version has been extensively studied. In this paper we give algorithms and lower bounds for the two models of commitment. For immediate decision, we give an O(m(1 + ρ)1/m)-competitive algorithm where m is the number of machines and ρ is the penalty factor, and when m is large we give an O(log(1 + ρ)) upper bound. This is matched by a lower bound of Ω(logρ) on the competitive ratio. For immediate notification we give a lower bound of Ω(logρ/loglogρ). We also give some better bounds when m = 1 or when ρ is small. Finally we give considerations to the case of separate arrival and start times.
Type de document :
Communication dans un congrès
Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.54-65, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_5〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01402028
Contributeur : Hal Ifip <>
Soumis le : jeudi 24 novembre 2016 - 10:48:12
Dernière modification le : jeudi 24 novembre 2016 - 11:14:11
Document(s) archivé(s) le : mardi 21 mars 2017 - 12:31:08

Fichier

978-3-662-44602-7_5_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Stanley Fung. Online Scheduling of Unit Length Jobs with Commitment and Penalties. Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.54-65, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_5〉. 〈hal-01402028〉

Partager

Métriques

Consultations de la notice

16

Téléchargements de fichiers

9