The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 25 NO.5 / (1996))
On-Line Scheducling of Imprecise Computations to Minimize Error
Wei-Kuan Shih, Jane W. S. Liu,
Pages. 1105-1121
Abstract This paper describes three algorithms for scheduling preemptive,imprecise tasks on a processor to minimize the total error. Each imprecise task consists of a mandatory task followed by an optional task. Some of the tasks are on-line; they arrive after the processor begins execution. The algorithms assume that when each new on-line task arrives, its mandatory task and the portions of all the mandatory tasks yet to be completed at the time can be feasibly schedules whose total errors are as their deadlines. The algorithms produce for such tasks feasible schedules whose total errors are as small as possible. The three algorithms are designed for three types of task systems: (1) when every task is on-line and is ready upon its arrival, (2) when every on-line task is ready upon arrival but there are also off-line tasks with arbitrary ready
times, and (3) when on-line tasks have arbitrary ready times. Their running times are $O(nlog n), O(nlog n)$, and $O(nlog^2 n)$, respectively.
Contents 1. Introduction
2. On-line-sceduling problem
3. On-line tasks ready upon arrival in the absence of off-line tasks
3.1. Reserving time for mandatory tasks
3.2. Scheduling decisions
3.3. Updating the reservation list
3.4. Optimality of the NORA algorithm
4. On-line tasks with arbitrary ready times together with off-line tasks
4.1. Reservation array
4.2. Speed-up method
5. On-line tasks ready upon arrival in the presence of off-line tasks
6. Summary
Key words real-time systems, scheduling to meet deadlines, deterministic scheduling, on-line scheduling.
Mathmatical Subject Classification 68Q25