|
In the real-time system, each task is with the time-critical
restrictions, especially deadline. If any task cannot be
fini- shed by its deadline, it will incur time fault and make
the re- sult meaningless. Unfortunately, it is hard to make
all tasks meeting their time-critical restrictions. An
Imprecise Computa- tion Model was proposed to cope with
this situation. In this thesis, we study the problem of
minimizing total weighted error of an Imprecise Computation
task system. In the Imprecise Computation Model, each task is
logically decomposed into two subtasks: mandatory and optional.
The manda- tory subtask of each each task must be completely
executed to generate an acceptable result, while its optional
subtask begi- nning after the mandatory subtask is completed
can be left unfi- nished. The optional part is used to refine
the result generated by its associated mandatory one. If the
optional subtask is unfinished, it will occur an error, where
error is simply equal to the processing time of the unfinished
portion of the optional subtask. We consider the problem of
preemptively scheduling n inde- pendent tasks on m > 1
identical processor system so as to mini- mize total weighted
error. For this problem, we give an polyno- mial-time
algorithm, Algorithm MINTWE, which runs in O(kn square㏒ square
n), where k is the number of different weights.
|