Heuristics for Minimizing Total Flow Time with Error Constraint

Abstract

We consider the problem of minimizing total flow time for the imprecise computation model introduced by Lin et al. Leung et al. have shown that the problem of finding a minimum total flow time schedule subject to the constraint that the total error is no more than a given threshold $K$ is NP-hard, even for a single processor. In this paper we give a fast heuristic for a set of tasks with a large deadline. We show that the heuristic produces schedules with total flow time no more than $3/2$ times the optimum solution. Examples are given showing that the ratio can asymptotically approach $3/2$ for a single processor and $5/4$ for multiprocessors. A second heuristic is given for a single processor and a set of tasks with different deadlines. It is shown that the worst-case performance bound of the heuristic is $2$ and the bound is tight.