Skip to main navigation Skip to search Skip to main content

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

  • STMicroelectronics

Research output: Contribution to journal › Journal Article › peer-review

6 Citations (Scopus)

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

Original languageEnglish
Pages (from-to)97-103
Number of pages7
JournalJournal of Global Optimization
Volume27
Issue number1
DOIs
Publication statusPublished - Sept 2003
Externally publishedYes

Keywords

  • Competitive analysis
  • Completion time
  • On-line scheduling
  • Single-machine

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research
  • Control and Optimization
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Competitive analysis of a better on-line algorithm to minimize total completion time on a single-machine'. These topics are generated from the title and abstract of the publication. Together, they form a unique fingerprint.

Cite this