A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion time

We study the problem of scheduling a single machine with the precedence relation on the set of jobs to minimize average weighted completion time. The problem is strongly NP-hard. The first combinatorial 2-approximation algorithm for this scheduling problem was developed by the author in 1992 (in fact, this algorithm solves a more general problem). Here we give an efficient implementation of this algorithm and show that its running time is O(nMF(n,m)), where n is the number of jobs, m is the number of arcs in the precedence relation graph, and MF(n,m) denotes the complexity of the maximal flow computation in a network with n nodes and m arcs. Thus, our algorithm is competitive to the best 2-approximation algorithms for this scheduling problem developed starting since 1997. (C) 2003 Published by Elsevier B.V.