Collaborative Research: Bridging probabilistic and competitive analysis of scheduling policies

调度策略被显式地(或隐式地)用于需要分配资源的任何地方，因此调度理论有着漫长而多样的历史。在这一大堆工作中，出现了两个截然不同的研究社区，不幸的是，每个社区的研究人员往往不知道另一个社区的结果。来自理论计算机科学和优化社区的一组研究人员专注于在最糟糕的环境中为调度学科提供有竞争力的保证。来自性能建模和应用概率社区的一组不同的研究人员专注于在随机/概率环境中提供调度策略的准确性能分析。每种方法在单独实施时都有特定的优点和缺点。这个项目的目标是开发出能够实现“两全其美”的技术，即结合每个社区的想法，以达到任何一个社区都无法单独实现的结果。具体地说，该项目的目标是开发将最坏情况的结果和技术与用于分析随机模型的定性和定量技术相结合的方法，从而将可以应用最坏情况结果的模型的广度与随机分析的现实适用性结合起来。这是一个雄心勃勃的目标，但它将在一个重要的、成熟的领域开辟一条新的研究途径。如果成功，它可以将来自两个不同社区的想法结合在一起，这两个社区用非常不同的技术解决类似的问题，因此很可能确定将在实践中影响系统设计的新的调度规程。此外，该项目将通过开发一种新的统一的教学调度理论方法，对本科生和研究生的教育产生广泛的影响。

Scheduling policies are explicitly (or implicitly) used everywhere that resources need to be allocated, and resultantly the theory of scheduling has a long and varied history. Out of this large body of work, two distinct research communities have emerged and, unfortunately, researchers in each community are often not aware of results from the other community. One set of researchers from the theoretical computer science and optimization communities has focused on providing competitive guarantees for scheduling disciplines in the worst-case environment. A different set of researchers, from the performance modeling and applied probability communities, has focused on providing exact performance analyses of scheduling policies in stochastic/probabilistic environments. Each of these approaches have specific advantages and disadvantages when carried out on their own. The aim of this project is to develop techniques that can achieve the "best of both worlds", i.e., to combine ideas from each community to arrive at results neither has been able to achieve alone. Specifically, the goal of this project is to develop approaches that combine worst-case results and techniques with qualitative and quantitative techniques for analyzing stochastic models, thus combining the breadth of models where worst-case results can be applied with the real-world applicability of stochastic analysis. This is an ambitious goal, but one that will open up a new avenue of research in an important, well established field. If successful, it can bring together ideas from two distinct communities which attack similar problems with very different techniques, and thus is likely to identify new scheduling disciplines that will impact system design in practice. Additionally, the project will have a broad impact on the education of both undergraduate and graduate students through the development of a new unified approach to teaching scheduling theory.