Scheduling imprecise computation tasks with 01-constraint

AbstractWe consider the problem of preemptively scheduling a set of imprecise computation tasks on a single processor, with the added constraint that each optional subtask is either fully executed or entirely discarded. Two performance metrics are considered: 1.(1) the total error;2.(2) the number of imprecisely scheduled tasks (i.e., tasks whose optional subtasks are entirely discarded). Since the problem of minimizing the total error is NP-hard, we consider an O(n2)-time heuristic for it, where n is the number of tasks. It is shown that the total error of the schedule produced by the heuristic is at most three times that of an optimal schedule and the bound is tight. For the problem of minimizing the number of imprecisely scheduled tasks, we show that it can be solved in O(n5) time. Since the time complexity is unacceptably high, we consider an O(n2)-time heuristic for it. It is shown that the number of imprecisely scheduled tasks in the schedule produced by the heuristic is at most twice that in an optimal schedule and the bound is tight. 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