Report Number: CS-TN-97-58
Institution: Stanford University, Department of Computer Science
Title: Precedence Constrained Scheduling to Minimize Weighted
Completion Time on a Single Machine.
Author: Chekuri, Chandra
Author: Motwani, Rajeev
Date: August 1997
Abstract: We consider the problem of scheduling a set of jobs on
a single machine with the
objective of mimizing weighted (average) completion time.
The problem is NP-hard
when there are precedence constraints between jobs, [12]
and we provide a simple and efficient combinatorial
2-approximation algorithm. In contrast to our work,
earlier approximation altorithms [9] achieving the same
ratio are based on solving a linear programming relaxation
of the problem.
http://i.stanford.edu/pub/cstr/reports/cs/tn/97/58/CS-TN-97-58.pdf