Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18]


Journal of Information Science and Engineering, Vol. 25 No. 1, pp. 185-200 (January 2009)

Imprecise Computations with Deferred Optional Tasks*

Jia-Ming Chen, Wan-Chen Lu, Wei-Kuan Shih and Ming-Chung Tang+
Department of Computer Science
National Tsing Hua University
Hsinchu, 300 Taiwan
+Department of Electronics Engineering
Ming Chi University of Technology
Taishan, 243 Taiwan

The imprecise computation model is an extension of the traditional real-time processing model. In this model, each imprecise task is logically divided into two portions: a mandatory portion and an optional portion. Since the optional portions of imprecise tasks can be traded for their deadlines and/or the required quality of service (QoS), the resulting quality of executing tasks in this model can be controlled by different strategies of the scheduling algorithms. In this paper, we present two significant results pertaining to on-line scheduling problems in the model of imprecise computation obeying Deferred Optional Tasks (DOT) scheduling discipline. The first significant result presented is, to the best of our knowledge, the very first proof of NP-hardness property for the problem of on-line, imprecise DOT scheduling without preemption (DOTwoP). And the second one is that we propose an O(n log2 n) algorithm to solve the problem of on-line, imprecise DOT scheduling with preemption (DOTwP) when tasks are ready upon arrival.

Keywords: real-time system, imprecise computation model, on-line preemptive scheduling algorithm, deferred optional tasks, quality-of-service

Full Text () Retrieve PDF document (200901_10.pdf)

Received March 21, 2007; revised November 21, 2007; accepted April 24, 2008.
Communicated by Tei-Kei Kuo.
* A preliminary version of this paper has been presented at RTCSA'04.