JISE


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


Journal of Information Science and Engineering, Vol. 17 No. 1, pp. 73-83


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

  Retrieve PDF document (JISE_200101_05.pdf)