A large-deviations analysis of the GI/GI/1 SRPT queue

with Bert Zwart

Journal version   PDF   PDF-save-the-forest-version

Abstract: We consider a GI/GI/1 queue with the shortest remaining processing time discipline (SRPT) and light-tailed service times. Our interest is focused on the tail behavior of the sojourn-time distribution. We obtain a general expression for its large-deviations decay rate. The value of this decay rate critically depends on whether there is mass in the endpoint of the service-time distribution or not. An auxiliary priority queue, for which we obtain some new results, plays an important role in our analysis. We apply the results for SRPT to compare SRPT with FIFO from a large deviations point of view.

Queueing Systems 54(2):85-97 (2006)