On the approximability of average completion time scheduling under precedence constraints

Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

32 Citations (Scopus)
57 Downloads (Pure)

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 [..].
Original languageEnglish
Pages (from-to)237-252
Number of pages16
JournalDiscrete applied mathematics
Volume131
Issue number1
DOIs
Publication statusPublished - 2003

Keywords

  • Approximation algorithms
  • Approximability threshold
  • Interval order
  • Bipartite order
  • Precedence constraints
  • Scheduling

Fingerprint Dive into the research topics of 'On the approximability of average completion time scheduling under precedence constraints'. Together they form a unique fingerprint.

Cite this