Journal
DISCRETE APPLIED MATHEMATICS
Volume 131, Issue 1, Pages 237-252Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/S0166-218X(02)00427-4
Keywords
scheduling; precedence constraints; interval order; bipartite order; approximation algorithms; approximability threshold
Categories
Ask authors/readers for more resources
We consider the scheduling problem of minimizing the average weighted job completion time on a single machine under precedence constraints. We show that this problem with arbitrary job weights, the special case of the problem where all job weights are one, and several other special cases of the problem all have the same approximability threshold with respect to polynomial time approximation algorithms. Moreover, for the special case of interval order precedence constraints and for the special case of convex bipartite precedence constraints, we give a polynomial time approximation algorithm with worst case performance guarantee arbitrarily close to the golden ratio 1/2 (1 + root5) approximate to 1.61803. (C) 2003 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available