A fast algorithm for scheduling imprecise computations with timing constraints to minimize weighted error
Wei‐Kuan Shih, Che–Rung Lee, Ching‐Hui Tang · 2002
Scheduling tasks with different weights in the imprecise computation model is rather difficult. Each task in the imprecise computation model is logically decomposed into a mandatory subtask and an optional subtask. The mandatory subtask must be completely executed before a deadline to produce an acceptable result; the optional subtask begins after the mandatory subtask to refine the result. The error in the results of a task is measured by the processing time of the unexecuted portion of the optional subtask. This paper proposes a fast algorithm for scheduling imprecise computation with timing constraints on uniprocessor systems. The proposed algorithm can obtain the optimal schedule for different weighted tasks with time complexity O(n log/sup 2/n).