Towards Optimal Scheduling for Multiserver Systems

Doug Down
Department of Computing and Software
McMaster University


Thursday, June 9, 2005
4:30 - 5:45 PM
Terman Engineering Center, Room 453


Abstract:

While it is well known that Shortest Remaining Processing Time (SRPT) is the optimal scheduling policy for a single server system, there are no results on how to route arrivals in a system of parallel servers, each using SRPT scheduling. We propose a routing policy that involves multiple layers of round robin routing. When the processing time distribution is discrete, we show that the combination of the proposed routing policy and SRPT scheduling at each server has a heavy traffic limit identical to that of the optimal policy (an extension of SRPT) for a multiple server system with a single queue. We then use the insight from these results to develop effective policies for the case when the processing time distribution is continuous. While these policies are not necessarily optimal, they do have heavy traffic limits that suggest superior performance to several schemes suggested in the literature.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html