Scheduling tasks with ready times and deadlines to minimize average error
Authors: Shih W. , Liu J. S. W. , Chung J. , Gillies D. W. 
Published: October 2004

We consider here the problem of scheduling tasks each of which is
logically decomposed into a mandatory subtask and an optional
subtask. The mandatory subtask must be executed to completion in
order to produce an acceptable result. The optional subtask begins
after the mandatory subtask is completed and refines the result in
order to reduce the error in the result. If the available processor
time is insufficient, the optional subtask can be left incompleted.
The error in the result of a task is equal to the processing time
of the unexecuted portion of the optional subtask. We describe a
preemptive algorithm for scheduling <i>n</i> dependent
tasks with rational ready times, deadlines, and processing times on
uniprocessor systems. This algorithm is optimal in the sense that
it finds feasible schedules meeting ready-time and deadline
constraints of all tasks and minimizing the average error of all
tasks, whenever feasible schedules exist. The complexity of this
algorithm is
<i>O</i>(<i>n</i><sup>2</sup>log<sup>2</sup><i>n</i>).
This algorithm can also be used to schedule optimally independent
tasks with rational ready times, deadlines and processing times on
identical multiprocessor systems. R<1>@Liu, J. W. S., K. J.
Lin, and S. Natarajan, "Scheduling real-time, periodic jobs using
imprecise results," <i>Proceedings of the IEEE 8th Real-Time
Systems Symposium</i>, San Jose, California, December 1987.
R<2>Chung, J. Y. and J. W. S. Liu, "Performance of algorithms
for scheduling periodic jobs to minimize average error,"
<i>Proceedings of the IEEE 9th Real-Time Systems
Symposium</i>, Huntsville, Alabama, December 1988.
R<3>Chung, J. Y. and J. W. S. Liu, "Performance of algorithms
for scheduling periodic jobs to avoid timing faults," to appear in
the <i>Proceedings of 22nd Hawaii International Conference on
System Sciences</i>, Hawaii, 1989. R<4>Lin, K. J., S.
Natarajan, J. W. -S. Liu, and T. Krauskopf, "Concord: a system of
imprecise computations," <i>Proceedings of the 1987 IEEE
Compsac</i>, Japan, October, 1987. R<5>Blazewicz, J.
and G. Finke, "Minimizing mean weighted execution time loss on
identical and uniform processors", <i>Information Processing
Letters</i>, Vol. 24, pp. 259--263, March 1987.
R<6>Chong, E. K. P. and W. Zhao, <i>Performance
evaluation of scheduling algorithms for imprecise computer
systems</i>, Technical Report, Department of Computer
Science, University of Adelaide, SA 5001, Australia, September
1988. R<7>Chong, E. K. P. and W. Zhao, <i>User
controlled optimization in task scheduling for imprecise computer
systems</i>, Technical Report, Department of Computer
Science, University of Adelaide, SA 5001, Australia, October 1988.
R<8>Lawler, E. L. and J. M. Moore, "A functional equation and
its application to resource allocation and scheduling problem,"
<i>Management Science</i>, Vol. 16, pp. 77--84, 1969.
R<9>McNaughton, R., "Scheduling with deadlines and loss
functions," <i>Management Science</i>, Vol. 12, pp.
1--12, 1959. R<10>Tarjan, R. E., <i>Data Structures and
Network Algorithms</i>, Society for Industrial and Applied
Mathematics, Pennsylvania, 1983. R<11>Shih, W. K., J. W. S.
Liu, J. Y. Chung, and D. W. Gillies, <i>Scheduling tasks with
ready times and deadlines to minimize average error</i>,
Technical Report, Department of Computer Science, University of
Illinois, January 1989.