Collaborative Research: Bridging probabilistic and competitive analysis of scheduling policies

协作研究：桥接调度策略的概率分析和竞争分析

• 批准号: 0830511
• 负责人: Adam Wierman
• 金额: $ 15万
• 依托单位: California Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-10-01 至 2011-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830511&HistoricalAwards=false
• 关键词: Collaborative; Research; Bridging; probabilistic; competitive

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.

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