2002 · 74 citations · 11 references
ComputingComputer ScienceMathematicsAlgorithmsReal-time SystemsSchedulingJob SchedulingMachine SchedulingOnline AlgorithmsOnline SchedulingReal-time SchedulingScheduling TheoryAverage Response Time AnalysisCompetitive RatioDeterministic Online AlgorithmsOnline Job SchedulingOnline Real-time SchedulingResponse TimeScheduler DesignScheduling Problems
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.
11
Silberschatz · 1991 · 1.6K citations
Thek-server dual and loose competitiveness for paging
Neal E. Young · Algorithmica · 1994 · 248 citations · Full text
Christos H. Papadimitriou · SIAM Journal on Computing · 2000 · 179 citations
On the competitiveness of on-line real-time task scheduling
Sanjoy Baruah, G. Koren, Dacheng Mao et al. · Real-Time Systems · 1992 · 172 citations