A dual criteria preemptive scheduling problem for minimax error of imprecise computation tasks
We consider a hierarchical optimization problem for imprecise computation tasks, where each task is weighted with two weights, w and w'. The primary criterion is to minimize the total w-weighted error of all optional parts of tasks and the secondary criterion is to minimize the maximum w-weighted error. An algorithm is given with time complexity O(kn(3) log(2)n) for parallel and identical processors and O(kn(2)) for a single processor, where k is the number of distinct w-weights.
preemptive scheduling imprecise computation task parallel and identical processors single processor real-time system maximum weighted error total weighted error polynomial time algorithm