There has been recent success in using polyhedral
formulations of scheduling problems not only to obtain
good lower bounds in practice but also to develop
provably good approximation algorithms. Most of these
formulations rely on binary decision variables that are
a kind of assignment variables. We present quite simple
polynomial-time approximation algorithms that are
based on linear programming formulations with
completion time variables and give the best known
performance guarantees for minimizing the total
weighted completion time in several scheduling
environments. This amplifies the importance of
(appropriate) polyhedral formulations in the design of
approximation algorithms with good worst-case
performance guarantees. In particular, for the problem
of minimizing the total weighted completion time on a
single machine subject to precedence constraints we
present a polynomial-time approximation algorithm with
performance ratio better than 2. This outperforms a
(4 + ε)-approximation algorithm very recently
proposed by Hall, Shmoys, and Wein that is based on
time-indexed formulations. A slightly extended
formulation leads to a performance guarantee of 3 for
the same problem but with release dates. This improves
a factor of 5.83 for the same problem and even the
4-approximation algorithm for the problem with
release dates but without precedence constraints, both
also due to Hall, Shmoys, and Wein. By introducing new
linear inequalities, we also show how to extend our
technique to parallel machine problems. This leads, for
instance, to the best known approximation algorithm for
scheduling jobs with release dates on identical
parallel machines. Finally, for the flow shop problem
to minimize the total weighted completion time with
both precedence constraints and release dates we
present the first approximation algorithm that achieves
a worst-case performance guarantee that is linear in
the number of machines. We even extend this to
multiprocessor flow shop scheduling. The proofs of
these results also imply guarantees for the lower
bounds obtained by solving the proposed linear
programming relaxations. This emphasizes the strength
of linear programming formulations using completion
time variables.
