Abstract
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 the deadline to produce 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 work 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 2 n).