On-line scheduling to maximize task completions
- 1 January 1994
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 15, 228-236
- https://doi.org/10.1109/real.1994.342713
Abstract
The problem of uniprocessor scheduling under conditions of overload is investigated. The system objective is to maximize the number of tasks that complete by their deadlines. For this performance metric it is shown that, in general, any on-line algorithm may perform arbitrarily poorly as compared to a clairvoyant scheduler. Restricted instances of the general problem for which on-line schedulers ran provide a guaranteed level of performance are identified, and on-line algorithms presented for these special cases.Keywords
This publication has 9 references indexed in Scilit:
- D/sup over/; an optimal on-line scheduling algorithm for overloaded real-time systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Earliest deadline scheduling for real-time database systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On-line scheduling in the presence of overloadPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- ROBUSTPublished by Association for Computing Machinery (ACM) ,1993
- On the competitiveness of on-line real-time task schedulingReal-Time Systems, 1992
- On being optimistic about real-time constraintsPublished by Association for Computing Machinery (ACM) ,1990
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973
- An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late JobsManagement Science, 1968
- Letter to the Editor—A Proof of the Optimality of the Shortest Remaining Processing Time DisciplineOperations Research, 1968