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 T_i having two weights w_i and w_i^′. 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 (m n⁴), O (m n⁴) and O (k m n⁴), respectively, where k is the number of distinct w-weights. We also present alternative algorithms for the three objectives, with time complexity O (c m n³), O (c m n³ + m n⁴) and O (k c m n³), respectively, where c is a parameter-dependent number.