论文标题
与预测的合同日程安排
Contract Scheduling With Predictions
论文作者
论文摘要
合同调度是一种通用技术，允许设计具有可中断功能的系统，并且给定不一定会中断的算法。关于该主题的先前工作在很大程度上假定中断是调度程序未知的最糟糕的截止日期。在这项工作中，我们研究了有关中断的潜在错误预测的设置。具体而言，我们考虑预测描述中断发生的时间的设置，以及作为对单个或多个二进制查询的响应获得预测的设置。对于这两种设置，我们都会研究鲁棒性（即假定对抗性预测的最坏情况）与一致性（即假定预测是无错误的绩效）之间的权衡。
Contract scheduling is a general technique that allows to design a system with interruptible capabilities, given an algorithm that is not necessarily interruptible. Previous work on this topic has largely assumed that the interruption is a worst-case deadline that is unknown to the scheduler. In this work, we study the setting in which there is a potentially erroneous prediction concerning the interruption. Specifically, we consider the setting in which the prediction describes the time that the interruption occurs, as well as the setting in which the prediction is obtained as a response to a single or multiple binary queries. For both settings, we investigate tradeoffs between the robustness (i.e., the worst-case performance assuming adversarial prediction) and the consistency (i.e, the performance assuming that the prediction is error-free), both from the side of positive and negative results.
