Speed is as powerful as clairvoyance [scheduling problems]
- 19 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
We consider several well known nonclairvoyant scheduling problems, including the problem of minimizing the average response time, and best-effort firm real-time scheduling. It is known that there are no deterministic online algorithms for these problems with bounded (or even polylogarithmic in the number of jobs) competitive ratios. We show that moderately increasing the speed of the processor used by the non-clairvoyant scheduler effectively gives this scheduler the power of clairvoyence. Furthermore, we show that there exist online algorithms with bounded competitive ratios on all inputs that are not closely correlated with processor speed.Keywords
This publication has 12 references indexed in Scilit:
- On-line scheduling in the presence of overloadPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Beyond Competitive AnalysisSIAM Journal on Computing, 2000
- On-line scheduling of jobs with fixed start and end timesTheoretical Computer Science, 1994
- MOCA: a multiprocessor on-line competitive algorithm for real-time system schedulingTheoretical Computer Science, 1994
- Thek-server dual and loose competitiveness for pagingAlgorithmica, 1994
- A new measure for the study of on-line algorithmsAlgorithmica, 1994
- On the competitiveness of on-line real-time task schedulingReal-Time Systems, 1992
- A statistical adversary for on-line algorithmsPublished by American Mathematical Society (AMS) ,1992
- Competitive analysis of the Round Robin algorithmPublished by Springer Nature ,1992
- Amortized efficiency of list update and paging rulesCommunications of the ACM, 1985