Perfect simulation of M/G/c queues

Stephen B. Connor, Wilfrid S. Kendall
  • Advances in Applied Probability, December 2015, Cambridge University Press
  • DOI: 10.1239/aap/1449859799

Getting exact draws from multi-server queues in equilibrium

What is it about?

The multiserver queue is a fundamental element of many kinds of business service, from airport immigration to post-office service lines. Exact analytical results are few (albeit beautiful and very valuable), expect for the important but over-simplified case in which service times are random with exponential distribution. (Why is this unrealistic? because someone who has been in service for t units of time has exactly the same prognosis for the time of service completion as someone who has only just commenced service). So simulation methods must be used. However if one wishes to get an accurate picture of the behaviour of the queue in statistical equilibrium then one has to discard the initial "burn-in" period. Or at least that is what one used to have to do. With the advent of this paper (building on previous work of Sigman, and now joined by a number of other papers developing this iead), we now know how to draw exactly from equilibrium using a rather remarkable idea of exact or perfect simulation due originally to Propp and Wilson in 1996.

Why is it important?

Multiserver queues are central to all sorts of operation research applications. This paper describes and proves a practical way to simulate them which does not need to worry about "burn-in" times.


Wilfrid Kendall (Author)
University of Warwick

I've been interested in perfect simulation methods for about twenty years now. I like this paper because it shows how to apply them in a very practical and down-to-earth context.

The following have contributed to this page: Wilfrid Kendall

In partnership with: