We consider the problem of preemptively scheduling a set of imprecise computation tasks on a single processor, with the added constraint that each optional subtask is either fully executed or entirely discarded. Two p...
详细信息
We consider the problem of preemptively scheduling a set of imprecise computation tasks on a single processor, with the added constraint that each optional subtask is either fully executed or entirely discarded. Two performance metrics are considered: (1) the total error;(2) the number of imprecisely scheduled tasks (i.e., tasks whose optional subtasks are entirely discarded). Since the problem of minimizing the total error is NP-hard, we consider an O(n(2))-time heuristic for it, where n is the number of tasks. It is shown that the total error of the schedule produced by the heuristic is at most three times that of an optimal schedule and the bound is tight. For the problem of minimizing the number of imprecisely scheduled tasks, we show that it can be solved in O(n(5)) time. Since the time complexity is unacceptably high, we consider an O(n(2))-time heuristic for it. It is shown that the number of imprecisely scheduled tasks in the schedule produced by the heuristic is at most twice that in an optimal schedule and the bound is tight. Interestingly, the number of precisely scheduled tasks (i.e., tasks whose optional subtasks are fully executed) in an optimal schedule is also at most twice that in the schedule produced by the heuristic and the bound is tight.
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) minimizi...
详细信息
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. (c) 2007 Elsevier B.V. All rights reserved.
We consider a hierarchical optimization problem for imprecise computation tasks, where each task is weighted with two weights, w and w'. The primary criterion is to minimize the total w-weighted error of all optio...
详细信息
We consider a hierarchical optimization problem for imprecise computation tasks, where each task is weighted with two weights, w and w'. The primary criterion is to minimize the total w-weighted error of all optional parts of tasks and the secondary criterion is to minimize the maximum w-weighted error. An algorithm is given with time complexity O(kn(3) log(2)n) for parallel and identical processors and O(kn(2)) for a single processor, where k is the number of distinct w-weights.
We consider the problem of preemptively scheduling a set of imprecise computation tasks on a single processor. with the Oil-constraint. In the imprecisecomputation model, each task consists of two parts, mandatory an...
详细信息
We consider the problem of preemptively scheduling a set of imprecise computation tasks on a single processor. with the Oil-constraint. In the imprecisecomputation model, each task consists of two parts, mandatory and optional, with the mandatory part required to be completed while the optional part can be left uncompleted, If a task has an optional part that is unfinished, then it incurs an error equal to the processing rime of its unfinished potion. In the 0/1 constraint environment, each optional subtask is either fully scheduled or entirely discarded. Two performance metrics are considered: (1) the number of imprecisely scheduled tasks;(2) the total error. For the problem of minimizing the number of imprecisely scheduled tasks, it has been shown that it can be solved in O(n(3))-time. Since the time complexity is relatively high. We propose two O(n(2))-time algorithms for two special cases. On the other hand, it is known that the problem of minimizing the total error is NP-hard. We present an O(n(2)) rime algorithm to solve the problem when tasks have optional parts of the same length.
暂无评论