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.