Precedence constrained scheduling to minimize sum of weighted completion times on a single machine

We consider the problem of scheduling a set of jobs on a single machine with the objective of minimizing sum of weighted completion times. The problem is NP-hard when there are precedence constraints between jobs {[}15]. We provide an efficient combinatorial 2-approximation algorithm for this problem. In contrast to our work, earlier approximation algorithms {[}11] achieving constant factor approximations are based on solving a linear programming relaxation of the problem. We also show that the linear ordering relaxation of Potts {[}19] has an integrality gap of 2. (C) 1999 Elsevier Science B.V. All rights reserved.