On-line scheduling on a single machine: minimizing the total completion time

A. Fiat, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

10 Citations (Scopus)

Abstract

This note deals with the scheduling problem of minimizing the sum of job completion times in a system with n jobs and a single machine. We investigate the on-line version of the problem where every job has to be scheduled immediately and irrevocably as soon as it arrives, without any information on the later arriving jobs. We prove that for any sufficiently smooth, non-negative, non-decreasing function f(n) there exists an O(f(n))-competitive on-line algorithm for minimizing the total completion time if and only if the infinite sum ∑ ∞ n=1 1/\ab(nf(n))
∑n=1∞1/\ab(nf(n))
converges.
Original languageEnglish
Pages (from-to)287-293
JournalActa Informatica
Volume36
Issue number4
DOIs
Publication statusPublished - 1999
Externally publishedYes

Fingerprint

Dive into the research topics of 'On-line scheduling on a single machine: minimizing the total completion time'. Together they form a unique fingerprint.

Cite this