Minimizing Maximum Weighted Error for Imprecise Computation Tasks

We consider the problem of preemptively scheduling a set of imprecise computation tasks on m ≥ 1 identical processors, with each task T_i having two weights, w_i and w′_i. Two performance metrics are considered: (1) the maximum w′-weighted error; (2) the total w-weighted error subject to the constraint that the maximum w′-weighted error is minimized. For the problem of minimizing the maximum w′-weighted error, we give an algorithm which runs in O(n³ log²n) time for multiprocessors and O(n²) time for a single processor. For the problem of minimizing the total w-weighted error subject to the constraint that the maximum w′-weighted error is minimized, we give an algorithm which also has the same time complexity.