Online Scheduling via Learned Weights
Online Scheduling via Learned Weights
复制标题
DOI：
10.1137/1.9781611975994.114
复制
发表时间：
2020-01
期刊：
影响因子：
--
通讯作者：
Silvio Lattanzi;Thomas Lavastida;Benjamin Moseley;Sergei Vassilvitskii
中科院分区：
文献类型：
--
作者：
Silvio Lattanzi;Thomas Lavastida;Benjamin Moseley;Sergei Vassilvitskii
在线算法是不确定性下最坏情况优化的标志。另一方面，在实践中，输入往往远离最坏情况，并具有一些可预测的特性。最近的一系列工作已经展示了如何使用机器学习预测来规避经典在线问题（如滑雪租赁和缓存）中竞争比率的强下限。我们研究如何预测技术可以用来突破最坏情况下的障碍，在线调度。带约束任务的最小完工时间问题是在线调度理论中的经典问题。这个问题的最坏情况下的分析给出了在在线设置的竞争比的最小（log m）的下限。我们确定了一个强大的数量，可以预测，然后用来指导在线算法，以实现更好的性能。我们的预测是紧凑的大小，具有尺寸线性的机器的数量，并可以使用标准的货架方法学习。我们的算法的性能保证取决于预测的准确性，给定误差为η的预测，我们展示了如何构造O（log η）的竞争分数分配。然后，我们给出了一个在线算法，四舍五入任何分数分配到一个完整的时间表。我们的算法是O（（log log m）3）-竞争力，我们给了一个几乎匹配的最小值（log log m）的在线舍入算法的下界。1总之，我们给出的算法，配备了误差η的预测，实现O（log η（log log m）3）的竞争比，甚至对于中等准确的预测也打破了log（log m）的下限。
Online algorithms are a hallmark of worst case optimization under uncertainty. On the other hand, in practice, the input is often far from worst case, and has some predictable characteristics. A recent line of work has shown how to use machine learned predictions to circumvent strong lower bounds on competitive ratios in classic online problems such as ski rental and caching. We study how predictive techniques can be used to break through worst case barriers in online scheduling. The makespan minimization problem with restricted assignments is a classic problem in online scheduling theory. Worst case analysis of this problem gives Ω(log m ) lower bounds on the competitive ratio in the online setting. We identify a robust quantity that can be predicted and then used to guide online algorithms to achieve better performance. Our predictions are compact in size, having dimension linear in the number of machines, and can be learned using standard off the shelf methods. The performance guarantees of our algorithms depend on the accuracy of the predictions, given predictions with error η , we show how to construct O (log η ) competitive fractional assignments. We then give an online algorithm that rounds any fractional assignment into an integral schedule. Our algorithm is O ((log log m ) 3 )-competitive and we give a nearly matching ˜Ω(log log m ) lower bound for online rounding algorithms. 1 Altogether, we give algorithms that, equipped with predictions with error η , achieve O (log η (log log m ) 3 ) competitive ratios, breaking the Ω(log m ) lower bound even for moderately accurate predictions.