During my Data Structures class we are soon to look at the FIFO: a queue. So I thought it might be fun to look at some queuing theory, not the data structures but how queues are modeled.

The sorts of parameters we need to set up a queue are:

• How quickly do customers arrive?
• How quickly do customers get served?
• How many servers are there?
• How many customers can the queue hold?
• How does the queue operate?

Here, “customer” could also be a “job” or a “process” and “served could mean “start” (a job) or “execute” (a process).

a/b/c/d/e queues

These parameters are usually captured as five numbers or letters.

The standard queue is usually denoted

M/M/1  

where the two Ms represent that the distribution of the arrival and service rates is Markovian, and there is only a single server. The d part (capacity) is assumed infinite, and the e part is first-in, first-out (FIFO).

For simplicity, I’m going to assume that the queue operates as I said above: FIFO. Another option is last in first out (LIFO).

The details

The labels that are often given for each of these parameters are:

• $\lambda$ - the average number of arrivals per unit time.
• $\mu$ - the average number served per unit time.
• $c$ - the number of servers able to work in parallel.
• $K$ - the capacity of the queue (how many customers can the queue hold)

In addition to the averages $\lambda$ and $\mu$, we also need to know the distributions of the arrivals and services.

These are often chosen to be a Poisson process (Markovian), so the distribution is an exponential distribution.

The probability of having $n$ arrivals in a time interval $t$ is given by

and the time between arrivals is then

Similarly, the service times follow similar Poisson distributions when the Markovian option is taken.

Upshot

One quick metric we can look at on how well an M/M/1 queue performs is the average number of customers in the system, $L$.

where $\rho = \frac{\lambda}{c \mu}$.

So, for an M/M/1 queue where $c = 1$ we get

This means that if the arrival rate and the service rate are the same, the average number of customers in the system is $\infty$.

Below is a re-publication of an article I wrote for the Australian Financial review.

“Lies and Statistics” Column, Weekend Australian Financial Review, 01-02/11/2003

Several supermarkets recently made the “eight items or less” lanes “basket only” to reduce queue rage [Ian Royall, 14/08/03 Herald-Sun]. Queue-hogs with nine items in their baskets caused pointless arguments. Other queue-hogs insist on paying with the exact change in five cent pieces; they forget the PIN number on their EFTPOS card; their baby suddenly grabs hold of their wallet and empties the contents onto the floor.

Supermarkets do their best to reduce the effects of queue-hogs, because customers hate waiting to pay for their groceries.

The number of items in the basket is not the problem. That’s just so the customers are easy to move in one large queue. The value of express lanes at Coles comes from use of multiple check-out operators serving one queue, not from the small number of items.

One Coles manager tackles the queue rage problem by knowing the average checkout operator work rate. She’s measured it. She measures it because managing the queues and, therefore, the queue-hogs is an important part of keeping customers happy. As Peter Drucker, a leader in modern management research, says “if you can’t measure it, you can’t control it”.

Queueing theory is a branch of statistics that allows relatively complex systems like queues to be analysed quantitatively. It enables the Coles manager to make sense of her measurements.

One measure of queue performance is the utilisation factor. This is average customer arrival rate as a percentage of the operator’s average serving rate. A utilisation factor of 100% means that customers arrive as fast as they are served. Queueing theory says that while the utilisation factor is 100% then the queue will keep growing.

However, the average serving rate and the average arrival rate do not tell the whole story.

No operator will serve every customer the same way, even if the customers behave the same way. No two customers shop the same way. These variations mean that a queue with a 100% utilisation factor will always have some customers arriving faster than the operator can serve them.

Even when the queue utilisation is less than 100%, there are still times when customers arrive faster than the operator can handle. Queue-hogs mean the checkout operator serves fewer people than normal. People then have to wait, even when they arrive more slowly than the operator can normally serve them.

If more customers arrive after a queue-hog than normal, then the effect is multiplied and the check-out operator and customers will have a longer wait.

The best way to deal with the queue-hogs is to use multiple checkout operators to serve one queue. Now no single queue-hog will stop the whole queue.

Otherwise, if each operator served a different queue, one queue-hog could still keep other customers waiting.

That’s why supermarkets use multiple checkout operators on their express lanes: it’s the most efficient use of their operators and it helps most of the rest of us avoid the queue-hogs!