Menu
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.