On-line scheduling of imprecise computations to minimize error
- 2 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 25 (5) , 1105-1121
- https://doi.org/10.1109/real.1992.242651
Abstract
[[abstract]]Three algorithms for scheduling preemptive, imprecise tasks on a processor to minimize the total error are described. Each imprecise task consists of a mandatory task followed by an optional task. Some of the tasks are online; they arrive after the processor begins execution. The algorithms assume that when each new online task arrives, its mandatory task and the portions of all the mandatory tasks yet to be completed at the time can be feasibly scheduled to be computed by 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 online and is ready upon its arrival; (2) when every task is online and is ready upon arrival but there are also offline tasks with arbitrary ready times; and (3) when online tasks have arbitrary ready times. Their running times are O(n log n), O(n log n), and O(n log2 n), respectively[[fileno]]2030218030023[[department]]資訊工程學Keywords
This publication has 8 references indexed in Scilit:
- Minimizing mean flow time with error constraintPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Fast algorithms for scheduling imprecise computationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Algorithms for scheduling periodic jobs to minimize average errorPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- On the competitiveness of on-line real-time task schedulingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Algorithms for scheduling imprecise computationsComputer, 1991
- Minimizing mean weighted execution time loss on identical and uniform processorsInformation Processing Letters, 1987
- A fault-tolerant scheduling problemIEEE Transactions on Software Engineering, 1986
- A Functional Equation and its Application to Resource Allocation and Sequencing ProblemsManagement Science, 1969