Passer à la navigation principale Passer à la recherche Passer au contenu principal

Competitive analysis of a better on-line algorithm to minimize total completion time on a single-machine

  • STMicroelectronics

Résultats de recherche: Contribution à un journal › Article publié dans une revue, révisé par les pairs › Revue par des pairs

6 Citations (Scopus)

Résumé

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-α, is √3-competitive, which beats the existing lower bound for non-clairvoyant online algorithms.

Langue originaleAnglais
Pages (de - à)97-103
Nombre de pages7
RevueJournal of Global Optimization
Volume27
Numéro de publication1
Les DOIs
ÉtatPublié - sept. 2003
Modification externeOui

Classification disciplinaire ASJC Scopus

  • Applications de l'informatique
  • Sciences de la gestion et recherche opérationnelle
  • Contrôle et optimisation
  • Mathématiques appliquées

Empreinte digitale

Voici les principaux termes ou expressions associés à « Competitive analysis of a better on-line algorithm to minimize total completion time on a single-machine ». Ces libellés thématiques sont générés à partir du titre et du résumé de la publication. Ensemble, ils forment une empreinte digitale unique.

Citer cette ressource