22 March - 26 March 2010
Isaac Newton Institute for Mathematical Sciences, Cambridge, UK
Workshop Organisers: Takis Konstantopoulos (Heriot-Watt) and Kavita Ramanan (Brown University).
Bruce Hajek (University of Illinois), Frank Kelly (Cambridge), P.R. Kumar (University of Illinois), Tom Kurtz (University of Wisconsin-Madison), Jean Mairesse (LIAFA), Philippe Robert (INRIA), John Tsitsiklis (MIT) and Ruth Williams (University of California, San Diego)
in association with the Newton Institute programmeStochastic Processes in Communication Sciences (11 January to 2 July 2010) Participants | Application | Accommodation and Cost
Title: Scheduling and large deviations
We investigate the impact of a scheduling discipline in preventing large response times in a queueing setting. In particular, for a GI/GI/1 queue it is well known that, in a large deviations setting, FIFO is optimal for light-tailed service times, and service disciplines such as PS (Processor Sharing) and SRPT (Shortest Remaining Processing Time) are optimal for heavy-tailed service times. It is also known that PS and SRPT do not perform well for light-tailed service times, while FIFO does not perform well for heavy-tailed service times. In this talk, we review these results, and answer the natural question whether it is possible to construct a single scheduling discipline that is competitive with FIFO for light-tailed service times and competitive with SRPT for heavy tailed service times. We also investigate how more robust scheduling disciplines can be designed by exploiting partial information on the distributions, such as the system load.