SkipPredict: When to Invest in Predictions for Scheduling

考虑到最近有关基于预测作业大小的调度的研究，我们考虑预测成本在排队系统中的影响，消除了以前研究中预测是外部资源和/或免费的假设。特别地，我们引入了一种新颖的利用预测的方法——SkipPredict，旨在解决它们固有的成本。我们提出了一种定制化的方法，根据作业的预测需求对作业进行分类。为了实现这一点，我们使用一位“廉价预测”来将作业分类为短作业或长作业。SkipPredict优先处理预测为短作业的作业，对于预测为长作业的作业，SkipPredict会应用第二轮更详细的“昂贵预测”来近似这些作业的最短剩余处理时间。我们的分析考虑了预测成本。我们研究了两种不同模型的成本影响。在外部成本模型中，预测是由某些外部方法生成的，不影响作业的服务时间，但会产生成本。在服务器时间成本模型中，预测本身需要服务器处理时间，并在同一服务器上调度作业。

本论文旨在解决在排队系统中使用预测的成本问题，提出了一种新的方法SkipPredict来应对这个问题。

SkipPredict方法是一种基于预测需求分类的方法，通过使用一位“廉价预测”将作业分类为短作业或长作业，优先处理短作业，对于长作业再使用更详细的“昂贵预测”来近似最短剩余处理时间。同时，论文考虑了预测成本的影响，提出了两种成本模型：外部成本模型和服务器时间成本模型。

该方法在两种成本模型下的实验结果表明，SkipPredict方法比其他基于预测的方法具有更好的性能。此外，论文还提供了开源代码和数据集。

在排队系统中使用预测的研究已经有很多，例如“Predictive scheduling with a learned ARIMA model”和“Dynamic scheduling with prediction in a distributed system”。