On Waiting Times for Nonlinear Accumulating Priority Queues

David A. Stanford, Dept. of Statistical & Actuarial Sciences, University of Western Ontario


In 1964, Kleinrock proposed a queueing discipline for a single-server queue in which customers from different classes accumulate priority as linear functions of their waiting time, at a rate dependent upon their class. As the server becomes available, it selects the waiting customer with the highest amount of priority, whenever the queue is non-empty. For such a queue, Kleinrock derived a recursion for calculating the expected waiting time of customers from each class. More recently, Stanford, Taylor and Ziedins took another look at this queue, which they termed the Accumulating Priority Queue (APQ), and derived the waiting time distributions for each class.

With his co-author Finkelstein, Kleinrock also studied an accumulating priority system in which customers' priorities increase as a power-law function of their time in the queue. They established that it is possible to associate with such a power-law accumulating priority queue a particular linear accumulating priority queue, in such a way that the expected waiting times of customers from the different classes are preserved. In this paper, we extend this analysis to characterise the class of nonlinear accumulating priority queues that are equivalent to linear APQs in the sense that the waiting time distributions for all classes are identical.

Joint work with:

  • Na Li (Dept. of Statistical & Actuarial Sciences, University of Western Ontario),
  • Peter Taylor (School of Mathematics & Statistics, University of Melbourne) and
  • Ilze Ziedins (Dept. of Statistics, University of Auckland)