论文标题
小排队有小建议
Queues with Small Advice
论文作者
论文摘要
由于最新的工作和预测的工作规模的工作的激励，我们考虑了按照最少建议的调度算法的性能，即一点点。除了展示非常有限的建议的力量外，此类计划也很自然。在预测设置中，可以使用一点点建议来对工作是“大”还是“小”的简单预测；也就是说，工作是高于给定阈值还是低于给定的阈值。此外，一位建议方案可以对应于确定在队列的前还是后面的工作的机制，这是在许多实施设置中可能有用的限制。最后，带有一点点建议的队列具有足够简单的状态，可以在限制两个选择的功能的限制平均场分析框架中进行分析。我们的工作遵循了最近工作的道路，即使少量甚至可能不准确的信息也可以大大提高调度绩效。
Motivated by recent work on scheduling with predicted job sizes, we consider the performance of scheduling algorithms with minimal advice, namely a single bit. Besides demonstrating the power of very limited advice, such schemes are quite natural. In the prediction setting, one bit of advice can be used to model a simple prediction as to whether a job is "large" or "small"; that is, whether a job is above or below a given threshold. Further, one-bit advice schemes can correspond to mechanisms that tell whether to put a job at the front or the back for the queue, a limitation which may be useful in many implementation settings. Finally, queues with a single bit of advice have a simple enough state that they can be analyzed in the limiting mean-field analysis framework for the power of two choices. Our work follows in the path of recent work by showing that even small amounts of even possibly inaccurate information can greatly improve scheduling performance.
