Scheduling imprecise computation tasks on uniform processors

作者：Wan, Guohua; Leung, Joseph Y T^*; Pinedo, Michael L

来源：Information Processing Letters, 2007, 104(2): 45-52.

DOI：10.1016/j.ipl.2007.05.004

• preemptive scheduling
• uniform processors
• imprecise computation task
• polynomial time algorithms
• algorithms
• analysis of algorithms
• combinatorial problems

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(mn(4)), O(mn(4)) and O(kmn(4)), respectively, where k is the number of distinct w-weights. We also present alternative algorithms for the three objectives, with time complexity O(cmn(3)), O(cmn(3) mn(4)) and O(kcmn(3)), respectively, where c is a parameter-dependent number.

• 出版日期2007-10-16
• 单位深圳大学