Queueing models

Why it matters

Queues are everywhere: patients in an emergency department, calls waiting for an agent, trucks at a loading dock, jobs waiting for a server. Customers feel waiting long before they notice anything else, and managers always ask the same questions: how long will people wait, and how many servers do we need? Queueing theory answers them with a handful of formulas, and it explains a surprising fact: waits explode as a system gets close to full.

Describing a queue

Kendall notation writes a queue as A/S/c:

• A is the arrival pattern. M (for Markovian, or memoryless) means a Poisson process: arrivals are random and independent, with an average rate lambda per unit time, and the gaps between them are exponential.
• S is the service time distribution. M again means exponential with average rate mu (average service time 1/mu).
• c is the number of identical servers.

So M/M/1 is random arrivals, random service and one server, served first come, first served, with unlimited waiting room. It is the simplest useful model and the baseline for everything else.

The key number is the utilization (traffic intensity):

rho = lambda / mu     (fraction of time the server is busy)

If rho >= 1, work arrives faster than it can be done and the queue grows without limit. The system is unstable. A stable queue needs lambda < mu.

The M/M/1 formulas

For a stable M/M/1 queue:

Little's law ties them together and holds for almost any stable queue, not just M/M/1:

L = lambda * W        Lq = lambda * Wq        W = Wq + 1/mu

It is a powerful sanity check: if 10 customers arrive per hour and each spends half an hour in the system, there are 5 in the system on average.

Worked example: a pharmacy counter

Customers arrive at 10 per hour. One pharmacist serves 12 per hour (5 minutes each on average).

rho = 10 / 12 = 0.833
L   = 0.833 / 0.167 = 5 customers
Lq  = 0.833^2 / 0.167 = 4.17 customers
W   = 1 / (12 - 10) = 0.5 hours = 30 minutes
Wq  = 0.833 / 2 = 0.417 hours = 25 minutes

A 5-minute service turns into a 25-minute wait. Watch what happens as arrivals rise, with service fixed at 12 per hour:

Going from 92% to 96% busy doubles the wait. This non-linear blow-up is the most important practical lesson of queueing theory: running people or machines at "100% efficiency" means very long queues.

More servers: M/M/c and Erlang C

With c servers, each serving at rate mu, the system is stable when lambda < c * mu. Let a = lambda / mu (the load in "erlangs") and rho = a / c. The Erlang C formula gives the chance an arrival must wait:

P(wait) = [a^c / c! / (1 - rho)] / [ sum_{k=0}^{c-1} a^k / k!  +  a^c / c! / (1 - rho) ]
Wq      = P(wait) / (c * mu - lambda)

Adding a second pharmacist at the same counter: P(wait) = 0.245 and Wq is about 1.05 minutes, down from 25. Pooling servers in one shared line is far better than separate lines.

Call centres use Erlang C to staff every half hour. With 100 calls per hour and 12 calls per agent per hour, 9 agents is the minimum for stability; 10 agents give an average wait of about 1.5 minutes and 11 agents about 0.6 minutes. If the target is "average wait under 1 minute", the answer is 11.

When the formulas do not fit

The formulas assume a steady state, Poisson arrivals and exponential service. Real systems have rush hours, scheduled appointments, customers who give up (abandonment), priorities and service times that are far from exponential. Use the formulas for quick estimates and staffing rules of thumb, and switch to simulation (next lesson) when the details matter.

Common mistakes

• Mixing time units. lambda and mu must use the same unit (per hour, or per minute).
• Applying formulas to an unstable queue. If lambda >= mu, the "answer" is negative or infinite.
• Planning for 100% utilization. Waits grow without limit as rho approaches 1.
• Confusing W and Wq. Time in system includes service; time in queue does not.

Quick recap

• M/M/1: Poisson arrivals at lambda, exponential service at mu, one server; stable only if lambda < mu.
• Wq = rho / (mu - lambda), and Little's law L = lambda * W links the rest.
• Waits explode as utilization nears 100%.
• Erlang C sizes multi-server systems such as call centres.

Try it

In the Do tab, code the M/M/1 metrics and Erlang C, then size a call centre.