This paper presents a large deviation analysis of the steady-state sojourn time distribution in the GI/G/1 PS queue. Logarithmic estimates are obtained under the assumption of the service time distribution having a light tail, thus supplementing recent results for the heavy-tailed setting. Our proof gives insight in the way a large sojourn time occurs, enabling the construction of an (asymptotically efficient) importance sampling algorithm. Finally our results for PS are compared to a number of other service disciplines, such as FCFS, LCFS, and SRPT.

CWI. Probability, Networks and Algorithms [PNA]

Mandjes, M.R.H, & Zwart, A.P. (2004). Large deviations of sojourn times in processor sharing queues. CWI. Probability, Networks and Algorithms [PNA]. CWI.