Approximability and nonapproximability results for minimizing total flow time on a single machine

H. Kellerer, T. Tautenhahn, G.J. Woeginger

Research output: Book/ReportReportAcademic

125 Downloads (Pure)


We consider the problem of scheduling n jobs that are released over time on a single machine in order to minimize the total ??flow time??. This problem is well-??known to be NP??-complete, and the best polynomial time approximation algorithms constructed so far had (more or less trivial)?? worst-??case performance guarantees of O??(n).???? In this paper, we present one positive and one negative result on polynomial time approximations for the minimum total ??flow time problem??. The positive result is the first approxima??tion algorithm with a sublinear worst-??case performance guarantee of O(\sqrt{n}). This algorithm is based on resolving the preemptions of the corresponding optimum preemptive schedule??. The performance guarantee of our approximation algorithm is not far from best possible as our second, negative result demonstrates.?? Unless P=NP, no polynomial time approxima??tion algorithm for minimum total ??flow time can have a worst-??case performance guarantee of O(n^{1/2 - \epsilon}) for any \epsilon > 0. ?? ?? ???? Keywords:?? scheduling, approximation algorithm, worst-??case analysis, total flow time, release time, single machine??.
Original languageEnglish
Place of PublicationEindhoven
PublisherTechnische Universiteit Eindhoven
Number of pages13
Publication statusPublished - 1995

Publication series

NameMemorandum COSOR
ISSN (Print)0926-4493

Fingerprint Dive into the research topics of 'Approximability and nonapproximability results for minimizing total flow time on a single machine'. Together they form a unique fingerprint.

Cite this