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

Journal of Inforamtion Science and Engineering, Vol.17 No.1, pp.73-83 (January 2001)

Algorithms for Imprecise Tasks With 0/1-Constraints*

Kun-Ming Yu
Department of Computer Science and Information Engineering
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

Full Text () 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.