论文标题
与速度预测的日程安排
Scheduling with Speed Predictions
论文作者
论文摘要
具有预测的算法是一个最近的框架，用于在不完整的信息设置中克服悲观的最坏情况。在调度的背景下，最近的工作利用了机器学习的预测来设计算法，这些算法在最初未知的工作时间的设置中提高了近似值。在本文中，我们研究了速度快速调度问题，在这些问题中，机器的速度而不是工作的处理时间是未知的，并且可以通过预测来增加这个问题。 我们的主要结果是达到$ \ min \ {η^2（1 +α），（2 + 2/α）\} $近似的算法，对于任何$α\ in（0,1）$，其中$η\ geq 1 $是预测错误。当预测准确时，这种近似值超过了最著名的速度近似速度调度，而没有预测$ 2-1/m $，其中$ m $是机器的数量，同时保持最差的$ 2 + 2 + 2/α$，即使预测预测是任意错误的。此外，我们在三种特殊情况下获得了改进的近似值：相等的工作规模，无限的工作规模和二进制机器速度。我们还通过下界补充了算法结果。最后，我们对现有的算法进行验证评估算法，以进行快速调度。
Algorithms with predictions is a recent framework that has been used to overcome pessimistic worst-case bounds in incomplete information settings. In the context of scheduling, very recent work has leveraged machine-learned predictions to design algorithms that achieve improved approximation ratios in settings where the processing times of the jobs are initially unknown. In this paper, we study the speed-robust scheduling problem where the speeds of the machines, instead of the processing times of the jobs, are unknown and augment this problem with predictions. Our main result is an algorithm that achieves a $\min\{η^2(1+α), (2 + 2/α)\}$ approximation, for any $α\in (0,1)$, where $η\geq 1$ is the prediction error. When the predictions are accurate, this approximation outperforms the best known approximation for speed-robust scheduling without predictions of $2-1/m$, where $m$ is the number of machines, while simultaneously maintaining a worst-case approximation of $2 + 2/α$ even when the predictions are arbitrarily wrong. In addition, we obtain improved approximations for three special cases: equal job sizes, infinitesimal job sizes, and binary machine speeds. We also complement our algorithmic results with lower bounds. Finally, we empirically evaluate our algorithm against existing algorithms for speed-robust scheduling.
