On the approximability of average completion time scheduling under precedence constraints

Woeginger, Gerhard J. (2003) On the approximability of average completion time scheduling under precedence constraints. Discrete Applied Mathematics, 131 (1). pp. 237-252. ISSN 0166-218X

PDF
Restricted to UT campus only: Request a copy
205Kb

Abstract:	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 [..].
Item Type:	Article
Copyright:	© 2003 Elsevier
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/74975
Official URL:	http://dx.doi.org/10.1016/S0166-218X(02)00427-4
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 213306