We consider the problem of preemptively scheduling a set of imprecise
computation tasks on a single processor, with the added constraint tha
t each optional subtask is either fully executed or entirely discarded
. Two performance metrics are considered: (1) the total error; (2) the
number of imprecisely scheduled tasks (i.e., tasks whose optional sub
tasks are entirely discarded). Since the problem of minimizing the tot
al error is NP-hard, we consider an O(n(2))-time heuristic for it, whe
re n is the number of tasks. It is shown that the total error of the s
chedule produced by the heuristic is at most three times that of an op
timal schedule and the bound is tight. For the problem of minimizing t
he number of imprecisely scheduled tasks, we show that it can be solve
d in O(n(5)) time. Since the time complexity is unacceptably high, we
consider an O(n(2))-time heuristic for it. It is shown that the number
of imprecisely scheduled tasks in the schedule produced by the heuris
tic is at most twice that in an optimal schedule and the bound is tigh
t. Interestingly, the number of precisely scheduled tasks (i.e., tasks
whose optional subtasks are fully executed) in an optimal schedule is
also at most twice that in the schedule produced by the heuristic and
the bound is tight.