We consider the scheduling problem of minimizing the average
weighted completion time of n jobs with release dates on a single
machine. We first study two linear programming relaxations of the
problem, one based on a time-indexed formulation, the other on a
completion-time formulation. We show their equivalence by proving
that a bigO(nlog n) greedy algorithm leads to optimal solutions
to both relaxations. The proof relies on the notion of mean busy
times of jobs, a concept which enhances our understanding of these
LP relaxations. Based on the greedy solution, we describe two simple
randomized approximation algorithms, which are guaranteed to deliver
feasible schedules with expected objective function value within
factors of 1.7451 and 1.6853, respectively, of the optimum. They
are based on the concept of common and independent α-points,
respectively. The analysis implies in particular that the
worst-case relative error of the LP relaxations is at most 1.6853,
and we provide instances showing that it is at least `e/(e-1)
approx 1.5819`. Both algorithms may be derandomized;
their deterministic versions run in
bigO(n2) time. The randomized algorithms also apply to the
on-line setting, in which jobs arrive dynamically over time and one
must decide which job to process without knowledge of jobs that will
be released afterwards.
