Waiting Time Asymptotics in the Single Server Queue with Service in Random Order

We consider the single server queue with service in random order. For a large class of heavy-tailed service time distributions, we determine the asymptotic behavior of the waiting time distribution. For the special case of Poisson arrivals and regularly varying service time distribution with index ?ν, it is shown that the waiting time distribution is also regularly varying, with index 1?ν, and the pre-factor is determined explicitly. Another contribution of the paper is the heavy-traffic analysis of the waiting time distribution in the M/G/1 case. We consider not only the case of finite service time variance, but also the case of regularly varying service time distribution with infinite variance.