Previous | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] | [10] |

Algorithms for Imprecise Tasks With 0/1-Constraints

**Kun-Ming Yu**

Chung-Hua University

Hsinchu, Taiwan 300, R.O.C.

We consider the problem of preemptively scheduling a set of imprecise computation tasks on a single processor, with the 0/1-constraint. In the imprecise computation 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 time 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(n3)-time. Since the time complexity is relatively high. We propose two O(n2)-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(n2) time algorithm to solve the problem when tasks have optional parts of the same length.

Keywords: real-time system, imprecise computation task, preemptive scheduling, mandatory subtask, optional subtask, total error, imprecisely scheduled tasks, NP-hard

Retrieve PDF document (**200101_05.pdf** : 3,563,874 bytes)

Received August 29, 1998; revised September 30 & December 2, 1999; accepted January 18, 2000.

Communicated by Shing-Tsaan Huang.
^{*}Research supported in part by the NSC Grant NSC 82-0408-E-216-003.