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

This note deals with the scheduling problem of minimizing the sum of job co mpletion 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 imm ediately 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 fun ction f(n) there exists an O(f(n))-competitive on-line algorithm for minimi zing the total completion time if and only if the infinite sum Sigma(n=1)(i nfinity) 1/(nf(n)) converges.