Competitive Analysis of a Better On-line Algorithm to Minimize Total Completion Time on a Single-machine

Abstract : We consider the problem of scheduling jobs on-line on a single machine with the objective of minimizing total completion time. We assume that jobs arrive over time and that release dates are known in advance, but not the processing times. The most important result we are given in this paper is the competitive analysis of a new clairvoyant on-line algorithm for this scheduling problem. We are proving that this deterministic semi-online algorithm, called ST-Ö3 -competitive, which beats the existing lower bound for non-clairvoyant online algorithms.
Type de document :
Article dans une revue
Journal of Global Optimization, Springer Verlag, 2003, Volume 27 (Number 1), pp.Pages 97-103. 〈10.1023/A:1024693103802〉
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-00720883
Contributeur : Florent Breuil <>
Soumis le : jeudi 26 juillet 2012 - 09:18:14
Dernière modification le : mardi 23 octobre 2018 - 14:36:03

Lien texte intégral

Identifiants

Citation

Jairo R. Montoya-Torres. Competitive Analysis of a Better On-line Algorithm to Minimize Total Completion Time on a Single-machine. Journal of Global Optimization, Springer Verlag, 2003, Volume 27 (Number 1), pp.Pages 97-103. 〈10.1023/A:1024693103802〉. 〈emse-00720883〉

Partager

Métriques

Consultations de la notice

68