Approximability and Nonapproximability Results for Minimizing Total Flow Time ona Single Machine

摘要

The authors consider the problem of scheduling n jobs that are released over timeon 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 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, the authors 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 of n). This algorithm is based on resolving the preemptions of the corresponding optimum preemptive schedule. The performance guarantee of the authors' approximation is not far from best possible as their second, negative, result demonstrates: Unless P = NP, no polynomial time approximation algorithm for minimum total flow time can have a worst-case performance guarantee of O(n to the 1/2 power minus Epsilon) for any Epsilon greater than 0.