Classifying Policies that Prioritize Small Jobs
Adam Wierman
Department of Computer Science
Carnegie Mellon University
Monday, May 8, 2006
4:30 - 5:45 PM
Packard 101
Abstract:
Recently, there have been a number of "scheduling success stories" where computer applications have provided improved performance by simply adjusting the way requests are scheduled. In applications such as web servers and routers, the heuristic of biasing towards small jobs has led to many of these successes. However, the policies that are implemented by practitioners do not match the idealized policies studied in theory. My goal in this talk is to illustrate that it is possible to bridge this gap by analyzing classes of scheduling policies instead of individual policies. I will present one example of such a class: the SMART class, which includes a wide range of policies that prioritize jobs with small sizes. We will show that the SMART class is 2-competitive with respect to mean response time. Further, we will discuss stochastic bounds on the response times under SMART policies and the tail behavior of response times under SMART policies.
Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html