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

摘要

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 approximation algorithm with a sublinear worst-case performance guarantee of O( square root 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 identical with N P, no polynomial-time approximation algorithm for minimum total flow time can have a worst-case performance guarantee of O(n super( one half - epsilon )) for any epsilon > 0.