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.