Efficient algorithms for average completion time scheduling
Rene Sitters

We analyze the competitive ratio of online algorithms for minimizing
(weighted) average completion time on identical parallel machines and
prove that the well-known shortest remaining processing time algorithm
(SRPT) is $5/4$-competitive w.r.t. the average completion time
objective. The SRPT algorithm has a natural generalization to the case
where jobs have given weights. Unfortunately, our proof does not carry
over to this case. For weighted completion times, no algorithm is known
to have a competitive ratio less than 2. Remarkably, even for the
offline problem, the only ratio less than 2 results from the
approximation scheme given by Afrati et al. We give a deterministic
online algorithm with competitive ratio $1.791+o(m)$. This ratio holds
for preemptive and non-preemptive scheduling. The two algorithms show
that approximation ratios less than 2 can be obtained for parallel
machines by simple and efficient online algorithms. The known lower
bounds indicate that competitive ratios close to 1 are possible for
randomized algorithms, especially when preemption is allowed.

Here is the paper: http://dare.ubvu.vu.nl/handle/1871/15570