Queueing theory equations

A blog post about queueing theory that I wrote back in 2008 continues to be popular. The post shows that when a system is close to capacity, adding another server dramatically reduces the wait time. In that example, going from one teller to two tellers doesn't make service twice as fast but 93 times as fast.

That post starts out at a very high level and then goes into some details. This post goes into much more detail.

For a quick introduction to queueing theory, see this page.

Queueing theory notation

In Kendall's notation, we're talking about M/M/1 and M/M/2 queues. The first letter denotes the assumed distribution on times between customer arrivals, the second denotes the distribution on service times, and the number at the end gives the number of servers.

The simplest and most common models in queueing theory are M/M models. The Ms stand for Markov" but they really mean exponential. (Sorry. I didn't invent the notation.) The time between arrivals is exponentially distributed, which means the arrival is a Poisson process. The time it takes to serve each customer is also exponentially distributed.

Let be the number of who arrive per unit time, and let be the number of customers served per unit time, on average. For the system to approach a steady state we must have / < 1. Otherwise the number of customers in the queue grows over time without bound. In the example I mentioned above, = 5.8 customers per hour, and = 6 customers per hour. Customers are coming in nearly as fast as they can be served, and so a long line develops.

M/M/1 equations

For a M/M/1 queue, the expected wait time, once the system reaches steady state, is

and the expected number of customers waiting at any time is

M/M/2 equations

The equations for M/M/k systems in general are significantly more complicated, but they're not bad when k = 2. For an M/M/2 system at steady state, the expected wait time is

and the expected number of customers waiting is

You may have noticed that for both M/M/1 and M/M/2 the expected number of customers waiting in line is times the expected wait time, i.e. L = W. This is true in general and is known as Little's law.

More queueing theory

• The science of waiting in line
• Computer servers and human servers
• Queueing theory and regular expressions

The post Queueing theory equations first appeared on John D. Cook.