On-line scheduling of imprecise computations to minimize error

Abstract

Three algorithms for scheduling preemptive, imprecise tasks on a processor to minimize the total error are described. Each imprecise task consists of a mandatory task followed by an optional task. Some of the tasks are online; they arrive after the processor begins execution. The algorithms assume that when each new online task arrives, its mandatory task and the portions of all the mandatory tasks yet to be completed at the time can be feasibly scheduled to be computed by their deadlines. The algorithms produce for such tasks feasible schedules whose total errors are as small as possible. The three algorithms are designed for three types of task systems: (1) when every task is online and is ready upon its arrival; (2) when every task is online and is ready upon arrival but there are also offline tasks with arbitrary ready times; and (3) when online tasks have arbitrary ready times. Their running times are O(n log n), O(n log n), and O(n log/sup 2/ n), respectively.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>