# 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:

• People arriving at a check-out till to be served in a supermarket.
• Patients waiting for admission, transfer or discharge in a hospital.
• Servers receiveing data requests from clients.
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:

• How long can the queue get? If it gets too long people could abandon the queue and revenue is lost, or there could be issues fitting the number of people in the space available.
• How long will it take from entering the queue to start to get served? Again, if this is too long people may abandon the queue.
• How long will it take to serve all the custemers expected to arrive in the hour? Does the checkout have to stay open longer than necessary?
• How hard will the server be working? Will the staff be over or under utilised?
There are three events to capture in this system:

• A customer enters the queue for checkout.
• A customer in the queue starts getting served.
• A customer in the queue finishes getting served and leaves.
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 initial queue length is zero.
• The mean customer arrival rate is 1 per minute.
• The mean customer service rate is 1.2 per minute.
• The simulation will server 60 customers.
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:

• How long can the queue get?
• How long will it take from entering the queue to start to get served?
• How long will it take to serve all the custemers expected to arrive in the hour?
• How hard will the server be working?
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:

• 25% - 75%, the interquartile range. This is the range of values experienced by the middle 50% of customers.
• 5% - 95%. This is the range of values experienced by the middle 90% of customers.
• 2.5% - 97.2%. This is the range of values experienced by the middle 95% of customers.

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:
• A little over 22% of the time a customer is served immediately upon arrival.
• 50% of customers will see a queue of 2 or fewer poeple in front of them, which is lower than the mean value of 2.6.
• 75% of customers will see a queue of 4 or fewer, and 95% will see a queue of 8 or fewer.
• The maximum queue length experienced over 50,000 cases was 28.
###### Time in the queue as a customer arrives to checkout:
• About 47% of customers are served within 1 minute of arriving at the checkout.
• 50% of customers will wait 1.3 minutes or less, which is lower than the mean value of 2 minutes.
• 75% of customers will 3 minutes or less, and 95% will wait 7 minutes or less.
• The maximum wait experienced over 50,000 cases was 26.6 minutes.
###### 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.

• The mean time to serve 60 customers is 64 minutes, which is close to the naive estimate.
• 50% of the time it will take less than 63 minutes to serve 60 customers.
• 75% of the time it will take less than about 68 minutes, and 95% of the time it will take less than 75 minutes.
• The maximum time experienced over 50,000 cases to serve 60 customers was 99 minutes.
###### Server utilisation:
• The mean and median server utilisation value is 80%.
• The interquartile range is from about 73% to about 86% utilisation, i.e. this is the range experienced 50% of the time.
• 5% of the time the server will be utilised about 64% or less, or 95% or more.
• 95% of all server utilisation falls within a range of 60% to 97%.
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.