Speed is as powerful as clairvoyance [scheduling problems]
Speed is as powerful as clairvoyance [scheduling problems]
复制标题
速度就像千里眼一样强大【调度问题】
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
K. Pruhs
中科院分区：
文献类型：
--
作者：
B. Kalyanasundaram;K. Pruhs
我们考虑了几个众所周知的非千里眼调度问题，包括平均响应时间最小化问题和尽力而为的公司实时调度问题。众所周知，这些问题不存在竞争比率有界（甚至是作业数量的多对数）的确定性在线算法。我们的研究表明，适度提高非千里眼调度器所使用处理器的速度，能有效地让该调度器拥有千里眼的能力。此外，我们还证明了在所有输入上都存在竞争比率有界的在线算法，而这些算法与处理器速度并不密切相关。
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.