SCHEDULING IMPRECISE COMPUTATION TASKS WITH 0 1-CONSTRAINT/

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.