Scheduling imprecise computation tasks on uniform processors

We consider the problem of preemptively scheduling n imprecise computation tasks on m?1 uniform processors, with each task Ti having two weights wi and . Three objectives are considered: (1) minimizing the maximum w^′-weighted error; (2) minimizing the total w-weighted error subject to the constraint that the maximum w^′-weighted error is minimized; (3) minimizing the maximum w^′-weighted error subject to the constraint that the total w-weighted error is minimized. For these objectives, we give polynomial time algorithms with time complexity O(mn⁴), O(mn⁴) and O(kmn⁴), respectively, where k is the number of distinct w-weights. We also present alternative algorithms for the three objectives, with time complexity O(cmn³), O(cmn³+mn⁴) and O(kcmn³), respectively, where c is a parameter-dependent number.