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.