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