Models, algorithms and complexity for scheduling under uncertainty: On the tradeoffs between performance and adaptivity

绝大多数调度研究都假设有关问题实例的完整信息。然而，在大多数实际应用程序中，在调度执行过程中逐渐暴露出来的不确定输入是一个无处不在的问题。与确定性调度不同的是，从算法的角度来看，不确定条件下的调度问题并没有得到很好的理解。此外，目前的大多数算法设计方法都假设算法具有任意的灵活性，而忽略了实践驱动的适应性限制。在这个项目中，我们设计了算法和分析工具来解决输入不确定的重要调度问题，例如不可靠的机器、随机的作业处理时间或未知的作业到达时间。我们的主要目标是彻底研究算法的性能和它所需的自适应性之间的权衡。一方面，我们的目标是最好的可能的算法，潜在的高度动态化，即调度决策可以任意地适应实例化的问题数据。另一方面，我们对尊重实践驱动的适应性限制的好的但简单的算法感兴趣。我们分析了算法需要什么样的自适应性和多少量的自适应才能达到一定的性能保证。我们的主要工具来自近似算法、组合优化、数学规划和概率论，我们的研究融合了泛解和稳健解的概念。我们研究了随机调度、在线调度和实时调度问题的实际相关算法的基本理论问题。

The vast majority of scheduling research assumes complete information about the problem instance. In most real-world applications, however, uncertain input that is gradually revealed during schedule execution is an omnipresent issue. Unlike its deterministic counterpart, the diverse field of scheduling under uncertainty is not well understood from an algorithmic point of view. Moreover, most current approaches on algorithm’s design assume arbitrary algorithmic flexibility and neglect practice-driven limitations on adaptivity. In this project we design algorithmic and analytic tools for solving important scheduling problems with uncertain input, such as unreliable machines, stochastic job processing times, or unknown job arrival times. Our major goal is to study thoroughly the tradeoff between the performance of an algorithm and the amount of adaptivity it requires. On the one hand, we aim for best possible algorithms which are potentially highly dynamic, i.e., scheduling decisions may adapt arbitrarily to the instantiated problem data. On the other hand, we are interested in good but simple algorithms that respect practice-driven adaptivity restrictions. We analyze what kind and what amount of adaptivity an algorithm needs to achieve a certain performance guarantee. Our main tools come from approximation algorithms, combinatorial optimization, mathematical programming, and probability theory, and our investigations integrate the concepts of universal and robust solutions. We study fundamental theoretical questions on practically relevant algorithms for problems from stochastic, online, and real-time scheduling.