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

✍ Scribed by N.N. Pisaruk

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 217 KB
• Volume: 131
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(03)00334-2

✦ Synopsis

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 ÿrst 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 e cient implementation of this algorithm and show that its running time is O(n MF(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 ow 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.