  We present a unified framework for minimizing average completion time for
many seemingly disparate online scheduling problems, such as the traveling
repairperson problems (TRP), dial-a-ride problems (DARP), and scheduling on
unrelated machines.
  We construct a simple algorithm that handles all these scheduling problems,
by computing and later executing auxiliary schedules, each optimizing a certain
function on already seen prefix of the input. The optimized function resembles
a prize-collecting variant of the original scheduling problem. By a careful
analysis of the interplay between these auxiliary schedules, and later
employing the resulting inequalities in a factor-revealing linear program, we
obtain improved bounds on the competitive ratio for all these scheduling
problems.
  In particular, our techniques yield a $4$-competitive deterministic algorithm
for all previously studied variants of online TRP and DARP, and a
$3$-competitive one for the scheduling on unrelated machines (also with
precedence constraints). This improves over currently best ratios for these
problems that are $5.14$ and $4$, respectively. We also show how to use
randomization to further reduce the competitive ratios to $1+2/\ln 3 < 2.821$
and $1+1/\ln 2 < 2.443$, respectively. The randomized bounds also substantially
improve the current state of the art. Our upper bound for DARP contradicts the
lower bound of 3 given by Fink et al. (Inf. Process. Lett. 2009); we pinpoint a
flaw in their proof.
