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.

Featured Image

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.

Perspectives