MINIMIZING MAXIMUM WEIGHTED ERROR FOR IMPRECISE COMPUTATION TASKS

We consider the problem of preemptively scheduling a set of imprecise computation tasks on m greater-than-or-equal-to 1 identical processors , with each task T(i) having two weights, w(i) and w'(i). Two performa nce 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(n3 log2 n) ti me for multiprocessors and O(n2) time for a single processor. For the problem of minimizing the total w-weighted error subject to the constr aint that the maximum w'-weighted error is minimized, we give an algor ithm which also has the same time complexity. (C) 1994 Academic Press, Inc.