This site uses cookies. To see our cookie policy and how to control cookies click hereCookies

Back to Modelling & Simulation

Time to queue

Using discrete event simulation

There are many systems where continuous monitoring in time is not an important concern but instead what does matter is when an event occurs that changes the state of the system. One such example is a queue, which could represent, amongst other things:

The following considers the first case and simplifies things down to a single server working on a till for approximately a one hour period from when the shop first opens. When the shop first opens there is obviously nobody waiting to be served. As time passes people will enter the shop and arrive at random times to check out. Each shopper will buy a diffent number of items so the time taken to serve each customer will also follow some random distribution. What is required is an analysis of this system to understand:

There are three events to capture in this system:

If a customer arrives at the checkout and there is no queue they get served immediately then leave. If a second customer arrives after service has finished for the first customer, they too get served immediately then leave. If, then, a third customer arrives before the second customer has finished they must wait and queue of length 1 is created. This continues throughout the service period. An example set of events for six customers is shown below. While the background time in this diagram is continuous it is only the events marked by the vertical dotted lines that matter for analysing the system. A simulation therefore jumps along from one discrete event to another. This diagram also shows when the server is occupied and not occupied, from which a server utilisation value (the percentage of the time the server is serving) can be calculated.

The mathematics in this problem is largely based around statistical distributions. One useful distribution is the Erlang distribution, which is characterised by a shape parameter, \(k\) and a rate parameter, \(\lambda\). When \(k = 1\), the distribution is an exponential distribution, while with larger values the distribution tends towards a normal distribution. The rate parameter determines how fast the distribution drops to zero and the location of the maximum when \(k \geqslant 2\). The larger the value of \(\lambda\), the quicker the distribution drops to zero, and the further to the left the peak value occurs. $$ f(x;k,\lambda )={\lambda ^{k}x^{k-1}e^{-\lambda x} \over (k-1)!}\quad {\mbox{for }}x,\lambda \geq 0$$

The mean of an Erlang distribution is given by $$Mean \left( f(x;k,\lambda \right) = \frac{k}{\lambda}. $$ The Erlang distribution is very useful in queuing problems. The Erlang distribution with \(k=1\) models the inter-arrival time between customers (which are assumed to be indepedndent events). In this case the mean time between arrivals is \(\frac{1}{\lambda}\), so \(\lambda\) represents the mean number of arrivals per unit time. The probability that exactly \(n\) customers arrive in the unit time is given by the Poisson distribution: $$ f (n;\lambda)= \frac{\lambda ^n e^{-\lambda}}{n!}. $$ As an aside, this distribution also models the number of count events measured by a Geiger counter when detecting ionising radiation from radioactive decay.

An Erlang distribution may also be used to model the time it takes to serve a customer. The distribution with \(k=1\) could be used but this allows for very short service times with reasonably high probabilty. In a customer-service situation this may not be realistic as time will be taken to unload at the checkout and for payment to be taken. To allow for this values of \(k \geqslant 2\) may be used. Recall the mean service time is given by \(\frac{k}{\lambda}\), so \(\frac{\lambda}{k}\) is the mean number of customers served per unit time. In the simulation below, \(k=2\), so to serve an average of \(s\) customers per unit time the Erlang distribution with \(\lambda = 2s\) should be used.

To construct a simulation a method of drawing time intervals from the Erlang distribution is required. For the \(k=1\) case the distribution reduces to the exponential distribution $$ f(x;\lambda ) = \lambda e^{-\lambda x} $$ Integrating this between \(x=0\) and \(x=t\) gives the probability that an event will happen within time t. $$P(event) = \int_{0}^{t} \lambda e^{-\lambda x} dx = 1-e^{-\lambda t}.$$ Rearranging, $$ t = -\frac{1}{\lambda} \ln \left(1 - P(event)\right)$$ If the event occurs at random then \(1-P(event)\) can be replaced by a random uniform deviate, U, on the interval (0,1]. This gives a method for generating random exponentially-spaced times between events as $$ t = -\frac{1}{\lambda} \ln U .$$ For the case where \(k \geqslant 2\) the above is generalised using \(k\) uniform deviates as $$ t = -\frac{1}{\lambda} \ln \prod_{i=1}^{k} U_i .$$

The interactive below uses the results from a discrete event simulation of the checkout queue (coded in Python). The simulation assumptions are

The mean service rate is 20% higher than the mean arrival rate so on average there should be capacity in the system to provide adequate service. Estimates are provided for the four key items of interest:

Note, because there is random variation in customer arrival time and service time, the above are not single values but rather form a distribution of results. The distributions are constructed by running the simulation a number of times and agregating the results. As the number of simulations increases the shapes of the distributions settles into their final forms. Note, the simulations are not carried out in real time in the browser as they typically take longer than the refresh rate between display frames. However, for this simple simulation run times are of the order of several tens of seconds for multi-thousand simulation cases.

For each of the measurements of interest, the range, mean and median values are displayed. It is also possible to show a set of quantile ranges:

The results would typically be reviewed to determine whether the possible ranges and the frequenecy with which they occur are acceptable. For example, it may be possible to build an very long queue, but this only occurs in one of the 50,000 cases. Such an event could be reasonably classified as an exceptional event. The fillowing points are made based on 50,000 simulation cases.

People in the queue as a customer arrives to checkout:
Time in the queue as a customer arrives to checkout:
Time to serve 60 customers:
The average customer arrival rate is 1 per minute, while the average service rate is 1.2 per minute. Naively, as the average service rate is higher than the average arrival rate, one could expect the mean time to server 60 customers is 60 minutes plus a minute or two to account for the fact that the first customer does not arrive at \(t-0\) and takes a finite time to serve.

Server utilisation:
The above is the most simple version of a queue model. It can, of course, be expanded to consider further options such as considering mutliple parallel servers and sequential servers etc.