Queueing Equations · Will Vass

Tools · Queueing Theory · Equations

What every formula here assumes

Poisson arrivals: Jobs arrive independently at a constant average rate λ, with exponentially distributed gaps between them. Scheduled or batched arrivals break this.
Exponential service: Service times average 1/μ and are highly variable — mostly short, occasionally very long. This is the assumption that fails most often.
First come, first served: One shared line, no priorities, no jumping. Averages hold under other disciplines, but the distribution of waits does not.
Infinite queue and population: Nobody is turned away, nobody gives up, and the pool of potential arrivals is effectively unlimited.
Steady state: Every number here is a long-run average. It is not the first ten minutes after opening, and it is not the lunchtime peak.
Stability: ρ < 1: Arrivals must be slower than the servers can clear them. At ρ ≥ 1 the queue grows without bound and none of these quantities exist.

The exponential-service assumption is the one to check first. If your service times are near-constant — a machine cycle, an automated test, a fixed-length inspection — these formulas will roughly double the queue you will actually see. Constant service time (M/D/1) halves L_q at the same utilization. Use M/M/c on a process like that and you will buy capacity you did not need.

Symbols

$\lambda$: Arrival rate — jobs arriving per unit of time.
$\mu$: Service rate of one server — jobs it completes per unit of time while busy. Mean service time is 1/μ.
$c$: Number of identical servers sharing a single queue.
$a$: Offered load, in Erlangs: how many servers' worth of work arrives. Also the average number of busy servers.
$\rho$: Utilization — the fraction of time any one server is busy. Must be below 1 or nothing below has a finite value.
$L$: Average number of jobs in the system: waiting plus in service.
$L_q$: Average number of jobs waiting in the queue.
$W$: Average time a job spends in the system: wait plus service.
$W_q$: Average time a job spends waiting before service starts.
$P_0$: Probability the system is completely empty — no job waiting, none in service.
$P(\text{wait})$: Probability an arrival finds every server busy and has to wait at all (Erlang C).

λ and μ must share a time unit. Whichever you use, W and W_q come out in it; L and L_q are counts of jobs and carry no unit at all.

Fundamentals

True of any queue, not just this model.

Little's Law

L = \lambda W \qquad\qquad L_q = \lambda W_q

The average number of jobs in a system is the rate they arrive multiplied by the average time each one stays. It assumes nothing about how arrivals or service times are distributed — it holds for any stable system in steady state, which is why it outlives the M/M/c model the rest of this page depends on. The second form applies the same identity to the waiting line alone.

Reach for it when You can see 12 parcels sitting in the induct area and you know 30 arrive an hour: each is waiting 24 minutes, and you never had to time one.

Utilization and offered load

\rho = \frac{\lambda}{c\mu} \qquad\qquad a = \frac{\lambda}{\mu}

Offered load a counts how many servers' worth of work is arriving; ρ is that load spread across the c servers you actually have. Every other result on this page is really a function of ρ, and it has to stay below 1 — at ρ = 1 the work arriving exactly equals the capacity to do it, so any random clump of arrivals is never worked back off.

Reach for it when Deciding whether a third picker is worth hiring: compute ρ at c = 2 and again at c = 3 and see which side of the cliff each one lands on.

M/M/1 — one server

The c = 1 case, reduced to closed form.

Probability the system is empty

P_0 = 1 - \rho

With one server, the fraction of time the system is completely empty is exactly the fraction of time that server is idle. Note how weak a guarantee that is: a server at 80% utilization is doing nothing one hour in five, and still has a queue almost all the rest of the time. Idle time and short queues are not the same property.

Reach for it when Sanity-checking a time study — if the idle fraction you observed is nowhere near 1 − ρ, your estimate of λ or μ is wrong.

Average number waiting

L_q = \frac{\rho^2}{1-\rho}

The jobs in the line, not counting the one being served. That (1 − ρ) denominator is the single most important intuition in queueing: the line does not grow in proportion to load, it grows towards a vertical asymptote. Going from 80% to 90% utilization roughly doubles the queue, and 90% to 95% doubles it again — the last few percent of capacity cost more than all the rest put together.

Reach for it when Explaining why a station that is only 10% busier than last month now has a line four times as long.

Average number in the system

L = \frac{\rho}{1-\rho}

Everyone present: the jobs waiting plus the one in service. It is Lq + ρ, because a single server is occupied a ρ fraction of the time and so holds ρ jobs on average. Same explosive denominator, for the same reason.

Reach for it when Sizing a buffer or a floor footprint, where the job currently being worked on still occupies a slot.

Average wait before service

W_q = \frac{\rho}{\mu\,(1-\rho)} \qquad=\qquad \frac{L_q}{\lambda}

How long a new arrival waits before anyone starts on it. It is Lq divided by λ — the same statement as the queue length, converted to time by Little's Law. The 1/μ out front is worth noticing: speeding up service shortens the wait twice over, once directly and once by dragging ρ away from the cliff.

Reach for it when Quoting a realistic queue time against a service-level target, and working out what service rate would actually be needed to hit it.

Average time in the system

W = \frac{1}{\mu - \lambda}

Total time from arriving to leaving, wait and service together. The form is worth memorising, because it says the answer is set by the slack between capacity and demand rather than by the size of either. A machine serving 10 an hour against 9 arriving gives the same one-hour answer as one serving 1000 against 999.

Reach for it when A back-of-the-envelope turnaround time when the only two numbers you have are the two rates.

M/M/c — c servers, one queue

The general case. Work down it in order; each result feeds the next.

Probability the system is empty

P_0 = \left[\;\sum_{n=0}^{c-1} \frac{a^n}{n!} \;+\; \frac{a^c}{c!\,(1-\rho)}\;\right]^{-1}

The normalising constant that forces every state probability to sum to one. The sum covers the states where fewer than c servers are busy and nobody is queueing; the second term collapses the whole infinite tail of states where all c are busy and a line has formed. There is no tidier closed form, which is why the calculator computes it term by term instead of the page quoting a shortcut.

Reach for it when Rarely read on its own — it is the input to Erlang C below, and to every quantity after it.

Erlang C — probability of having to wait

P(\text{wait}) = \frac{a^c}{c!\,(1-\rho)}\,P_0

The chance an arriving job finds all c servers busy, and so joins a queue rather than going straight into service. This, not the average wait, is the number service operations are usually managed against: "80% of calls answered immediately" is a promise about 1 − P(wait). It drops sharply as servers are added even when ρ is held constant, which is the whole argument for pooling several small queues into one big one.

Reach for it when Setting a staffing level against a promise of the form "x% of arrivals are served without waiting".

Average number waiting

L_q = P(\text{wait}) \cdot \frac{\rho}{1-\rho}

The same ρ/(1 − ρ) blow-up as M/M/1, but applied only to the share of arrivals that actually have to queue. The cliff near ρ = 1 is still there and still dominates everything; Erlang C just discounts it by how often a free server was waiting. At c = 1, P(wait) = ρ and this collapses back to ρ²/(1 − ρ).

Reach for it when Comparing 2 servers at 90% utilization against 3 at 90% — identical ρ, materially different queue.

Average number in the system

L = L_q + a

Add the jobs currently in service to the jobs waiting. Offered load a is exactly the average number of busy servers in a stable system, so it is also the average number of jobs being worked on — no extra derivation needed.

Reach for it when Counting total work-in-progress, e.g. how many units are physically on the floor at any moment.

Average wait before service

W_q = \frac{L_q}{\lambda}

Little's Law, pointed at the waiting line. Turn an average queue length into the average time each arrival spends in it.

Reach for it when Converting a queue length you can count on a shop floor into a wait time you can quote to a customer.

Average time in the system

W = W_q + \frac{1}{\mu}

Time in the system is the wait plus one average service time, and nothing subtler than that. Note it is 1/μ and not 1/(cμ): extra servers shorten the queue, they do not make any individual job get processed faster.

Reach for it when Total dwell time — the number you promise as a turnaround, as opposed to the queue time alone.