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.