The power of restarts in online scheduling

不确定条件下的优化问题是一个有着广泛应用的研究领域。在在线调度中，我们假设输入的作业一个接一个地到达(或随着时间推移)，并且需要在不知道剩余输入的情况下被分配到机器上。目标是最小化竞争比，对于成本最小化问题，竞争比是给定输入的算法成本与相同输入的最优成本之间对所有输入的最高可能比率。我们对作业随时间到达的在线调度问题很感兴趣。本项目将侧重于几个常见的目标函数，特别是总完成时间、总流程时间、吞吐量和这些函数的加权版本。我们将研究如何在实际相关但很少研究的重启模型中优化这些目标函数。在此模型中，可以在更紧急的作业(较小的作业或较重的作业)到达时中断正在运行的作业，但在这种情况下，正在运行的作业必须从头开始重新启动：对其所做的工作将丢失。该模型也称为带重启的抢占模型，不同于通常研究较多的带恢复的抢占模型，在该模型中，任何中断的作业都可以从中断点恢复。重启模型动机良好，因为并不是在所有情况下都可以在不丢失已完成工作的情况下中断正在运行的作业。因此，重要的是要了解多少重新启动可以帮助提高在线调度算法的性能。我们的工作将提供更好的结果，在某些情况下是第一个结果，对于这在很大程度上忽略了研究方向。

Optimiztion under uncertainty is a widely studied field with many different applications. In online scheduling, we make the assumption that the input jobs arrive one by one (or over time) and need to be assigned to machines without knowledge of the remaining input. The goal is to minimize the competitive ratio, which for cost minimization problems is the highest possible ratio over all inputs between the cost of an algorithm for a given input and the optimal cost for the same input. We are interested in online scheduling problems where jobs arrive over time. This project will focus on several common objective functions, in particular on total completion time, total flow time, throughput and the weighted versions of these functions. We will study how to optimize these objective functions in the practically relevant but very rarely studied model with restarts. In this model, it is possible to interrupt a running job in case a more urgent job arrives (a smaller one, or a heavier one), but in this case the job that was running must be restarted from the beginning: the work done on it is lost. This model is also called preemption with restarts and is different from the more commonly studied preemption with resume model, in which any interrupted job can simply be resumed from the point of interruption.The restarts model is well-motivated, as it is not in all situations possible to interrupt running jobs without losing the work done so far. It is therefore important to understand how much restarts can help to improve the performance of online algorithms for scheduling. Our work will provide better results, and in some cases the first results, for this to a large extent neglected research direction.