Abstract
We consider the problem of scheduling tasks each of which is logically decomposed into a mandatory part and an optional part. The mandatory part must be executed to completion in order to produce an acceptable result. The optional part refines the result in order to reduce the error in the result. If the available processor time is insufficient, the optional part can be left unfinished. The error in the result produced by an aperiodic task is equal to the processing time of the unexecuted portion of the optional part. Our objective is to schedule the tasks so that the total error over all tasks is minimized. A preemptive algorithm for scheduling n aperiodic dependent tasks with rational ready times, deadlines, and processing times on a uniprocessor system is described. This algorithm is optimal in the sense that it finds feasible schedules meeting the time constraints and minimizing the total error of all tasks, whenever feasible schedules exist. The complexity of this algorithm is O(n 2 log 2 n). We also consider the problem of scheduling periodic tasks. For these tasks the error in the result of each task is measured in terms of the average error in the results produced over several consecutive periods. A class of preemptive, priority-driven algorithms can be used to find feasible schedules with a small average error. These algorithms are described and evaluated. © 1989.