We consider the problem of finding near-optimal
solutions for a variety of \cal NP-hard scheduling
problems for which the objective is to minimize the
total weighted completion time. Recent work has led
to the development of several techniques that yield
constant worst-case bounds in a number of settings.
We continue this line of research by providing
improved performance guarantees for several of the
most basic scheduling models, and by giving the
first constant performance guarantee for a number of
more realistically constrained scheduling
problems. For example, we give an improved
performance guarantee for minimizing the total
weighted completion time subject to release dates on
a single machine, and subject to release dates
and/or precedence constraints on identical parallel
machines. We also give improved bounds on the power
of preemption in scheduling jobs with release dates
on parallel machines.
We give improved on-line algorithms for many more
realistic scheduling models, including environments
with parallelizable jobs, jobs contending for shared
resources, tree precedence-constrained jobs, as well
as shop scheduling models. In several of these
cases, we give the first constant performance
guarantee achieved on-line. Finally, one of the
consequences of our work is the surprising
structural property that there are schedules that
simultaneously approximate the optimal makespan and
the optimal weighted completion time to within small
constants. Not only do such schedules exist, but we
can find approximations to them with an on-line
algorithm.