Scheduling algorithms for imprecise computation in real-time systems
Chin S. Wong · 1990
In this dissertation we consider the complexity of minimizing the mean flow time and the number of late tasks in the imprecise computation model. In this model, each task is regarded as logically composed of two subtasks, mandatory and optional. It is required that the mandatory part of each task be completely executed, while its optional part can be partially executed by its deadline. An error is said to occur if a task has its optimal part unfinished, and the error is simply the execution time of the unfinished portion. We consider the problem of preemptively scheduling imprecise computational task systems on $p \geq$ 1 identical processors so as to minimize the mean flow time. Given a task system TS and an error threshold K, our goal is to find a preemptive schedule such that each task is executed in the interval of its release time and deadline, the total error is no more than K, and the mean flow-time of the schedule is minimized. Such a schedule is called an optimal schedule. We show that the problem of finding an optimal schedule is NP-hard for each fixed $p \geq$ 1, even if all tasks have the same ready time and the same deadline. For a single processor, a pseudo-polynomial time algorithm and polynomial time algorithms for various special cases of the problem are given. We also give fast heuristics for two special cases of the problem. The worst-ease performance ratios of the heuristics are shown to be 3/2 and 2, respectively. We also consider the problem of preemptively scheduling imprecise computational task systems on $p \geq$ 1 processors so as to minimize the number of last tasks. Given a task system TS and an error threshold K, our goal is to find a preemptive schedule such that the total error is no more than K, and the number of late tasks is minimized. Such a schedule is called an optimal schedule. We show that the problem of finding an optimal schedule is NP-hard for each fixed $p \geq$ 1, even if all tasks have the same ready time and the same deadline. For a single processor, a pseudo-polynomial time algorithm, a polynomial time algorithm and a fast heuristic for various special cases of the problem are also given.