MINIMIZING MEAN FLOW TIME WITH ERROR CONSTRAINT

We consider the problem df minimizing mean flow time for the Imprecise Computation Model introduced by Lin et al. A task system TS = ({Ti}, {r(T-i)}, {d(T-i)}, {m(T-i)}, {o(T-i)}) consists of a set of n indepen dent tasks, where r(T-i), d(T-i), m(T-i), and o(T-i) denote the ready time, deadline, execution time of the mandatory part, and execution ti me of the optional part of T-i, respectively. Given a task system TS a nd an error threshold K, our goal is to find a preemptive schedule on one processor such that the average error is no more than K and the me an flow time of the schedule is minimized. Such a schedule is called a n optimal schedule. In this article we show that the problem of findin g an optimal schedule is NP-hard, even if all tasks have identical rea dy times and deadlines. A pseudopolynomial-time algorithm is given for a set of tasks with identical ready times and deadlines, and opposite ly ordered mandatory execution times and total execution times (i.e., there is a labeling of tasks such that m(T-i) less than or equal to m( Ti+1) and m(T-i) + o(T-i) greater than or equal to m(Ti+1) + o(Ti+1) f or each 1 less than or equal to i < n). Finally, polynomial-time algor ithms are given for (1) a set of tasks with identical ready rimes, and similarly ordered mandatory execution times and total execution times and (2) a set of tasks with similarly ordered ready times, deadlines, mandatory execution times, and total execution times.