Queueing and Capacity

Queueing and Capacity

Queueing Models, Little's Law and Service-Level Staffing

Kendall notation

A queue is written A/S/c/K/N: A the arrival process, S the service-time distribution, c the number of parallel servers, K the capacity of the system (queue plus service, infinite when omitted) and N the size of the calling population (infinite when omitted). M stands for Markovian (memoryless): Poisson arrivals, exponential service times. G is a general service distribution known only by its mean and variance, D a deterministic one. All models here serve first come first served and are in steady state: long-run averages after the start-up transient has died out, with constant rates.

Birth–death balance

For the Markovian models the number in the system n changes one unit at a time: up at the arrival rate λ_n, down at the service rate μ_n. In steady state the flow between neighbouring states balances, λ_n−1 P_n−1 = μ_n P_n, so P_n = P₀ Π λ_k−1/μ_k and P₀ normalizes the sum to one. Every M/M model is one choice of λ_n and μ_n:

• M/M/c: λ_n = λ, μ_n = min(n, c) μ. With A = λ/μ (the offered load in erlangs) and ρ = A/c: P_n = P₀ Aⁿ/n! for n ≤ c and P₀ (A^c/c!) ρ^n−c beyond; the sum converges only when ρ < 1, the stability condition. M/M/1 is c = 1 (P_n = (1 − ρ) ρⁿ, L = ρ/(1 − ρ), W = 1/(μ − λ)).
• M/M/c/K: the same ratios truncated at n = K; always stable. The fraction of arrivals turned away is P_K and the admitted rate is λ_eff = λ (1 − P_K).
• M/M/c//N: λ_n = (N − n) λ, the sources still outside the system; always stable. P_n = P₀ C(N, n) Aⁿ for n ≤ c and P₀ N!/((N − n)! c! c^n−c) Aⁿ beyond; λ_eff = λ (N − L). This is the machine-repair model.
• M/M/∞: μ_n = n μ, giving the Poisson distribution with mean A and no waiting.
• M/M/c/c (Erlang B): no queue; the truncated Poisson distribution, with P_c the blocking probability.

Erlang B and Erlang C

Erlang's loss formula B(c, A) = (A^c/c!) / Σ_k≤c A^k/k! is the probability that all c lines are busy when there is no queue; the carried load is A(1 − B). It is evaluated by the recursion B(k) = A B(k−1) / (k + A B(k−1)) from B(0) = 1, which never forms a factorial and is exact for any c. Erlang's delay formula C(c, A) = c B / (c − A + A B) is the probability that an arrival to the M/M/c queue finds every server busy and waits. From it, L_q = C ρ/(1 − ρ), W_q = C/(c μ − λ), and because the waiting customers are cleared at rate c μ the wait of those who wait is exponential: P(W_q > t) = C e^{−(cμ − λ) t}. The service level within t is one minus that. B is a telephone-trunk (loss) measure, C a call-centre (delay) measure; for the same c and A, C is always the larger.

Waiting-time distribution of the finite models

An admitted arrival that finds n ≥ c in the system waits for n − c + 1 departures at rate c μ, an Erlang (gamma) time, so P(W_q > t) = Σ_n≥c q_n Σ_j≤n−c e^−cμt (c μ t)^j/j!. The arriving customer does not always see the time-average distribution P_n: with Poisson arrivals and finite capacity it sees P_n/(1 − P_K) over the admitted states, and with a finite population the arrival rate falls with n, so it sees q_n proportional to (N − n) P_n. For M/M/c the sum closes to the exponential form above.

M/G/1 and the Pollaczek–Khinchine formula

When service times have a general distribution with mean 1/μ and coefficient of variation c_s (standard deviation over mean), the mean queue is L_q = ρ² (1 + c_s²) / (2 (1 − ρ)), the Pollaczek–Khinchine formula. The other means follow from Little's law. With c_s = 1 it reproduces M/M/1 exactly; with c_s = 0 (deterministic service, M/D/1) the queue is half as long. The state probabilities P_n and the waiting-time distribution depend on the whole service distribution and are not given by the mean and variance alone, so the tool reports only the means for this model.

Little's law

L = λ W holds for any stationary queue regardless of the distributions and the discipline: the mean number present equals the arrival rate times the mean time each one spends. Applied to the queue alone, L_q = λ W_q; to the servers alone, the mean number busy is λ/μ. For the finite models the rate in the law is the admitted rate λ_eff. The results page restates the law with the computed numbers as a consistency check.

Finite capacity and finite population

Both change the arrival process the servers see. A capacity limit discards the arrivals that would have made the queue long, so the carried rate is below the offered one and the system is stable at any load; the price is the blocked fraction. A finite population makes the arrival rate fall as more sources are inside the system (a broken machine does not break again), which is why a repair shop with five machines and one mechanic never diverges even when each machine fails faster than it is repaired. In both cases the effective rate is what enters Little's law.

Service-level staffing and the economics of pooling

Call centres state their target as a service level such as 80 % of calls answered within 20 s. For each candidate c the tool solves the model and reads the service level at the target time; the staffing is the smallest c that reaches it, and the table shows the trade-off around it. The minimum stable number is the first integer above A. Above that the wait falls steeply with the first few extra servers and slowly afterwards, so a service-level target rather than a utilization target is the right way to set staff. The same formulas show the value of pooling: one queue of 2c agents handling 2λ has a far shorter wait than two separate queues of c, because an idle agent in one group can serve the other's queue. Splitting the load by skill or site forfeits that advantage.

Reading the results page

The offered load A and the utilization ρ come first with the stability check; then the measures P₀, L, L_q, W, W_q, the probability of waiting, the mean number busy and, for the finite models, the blocking probability and λ_eff; Little's law with the numbers; the waiting-time distribution at the entered times; the staffing table with the entered row and the target row marked; the distribution of the number in the system; and three charts: the wait (or blocking) against the number of servers, P_n, and P(W_q > t) against t. Rates are entered per minute, hour or day and the service time, target times and reported waits are in the time unit chosen, so a 180 s handle time with calls per hour needs no conversion by hand.

Limits

Steady state only: no time-varying arrival rates (a day of a call centre is treated as a sequence of intervals, each at its own rate), no transient start-up. First come first served with a single class: no priorities, no abandonment (an Erlang A model), no retrials, no networks of queues. The Markovian models assume Poisson arrivals and exponential service; the M/G/1 model relaxes the service distribution for one server only, and with c_s = 1 it reproduces M/M/1. Service levels of the finite models are those of admitted customers. The Erlang formulas are exact; the P_n tables of the infinite models are listed to 99.9 % of the probability.