Abstract

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.