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.