We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
On-line scheduling on a single machine: minimizing the total completion time.
- Authors
Fiat, Amos; Woeginger, Gerhard J.
- Abstract
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 SIGMA[sup Infinity, sub n=1] 1/ (nf (n)) converges.
- Subjects
PRODUCTION scheduling; ALGORITHMS
- Publication
Acta Informatica, 1999, Vol 36, Issue 4, p287
- ISSN
0001-5903
- Publication type
Article
- DOI
10.1007/s002360050162