Lesson 27: Model III: (M/M/c):(∞/FCFS), the Multi-Server Queue¶
27.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- Set up the birth–death rates for \(c\) parallel servers and derive \(P_0\).
- State and use the Erlang-C formula for the probability of waiting.
- Compute \(L_q, L_s, W_q, W_s\) for an \(M/M/c\) system and verify them.
- Distinguish the offered load \(r\) from the utilisation \(\rho\).
- Explain quantitatively why \(c\) servers of rate \(\mu\) differ from one server of rate \(c\mu\).
27.2 The Model¶
\(c\) identical servers work in parallel, fed by a single queue. A customer who finds a free server goes straight into service; otherwise all \(c\) are busy and the customer joins the common line.
Kendall notation. \((M/M/c):(\infty/\text{FCFS})\) — Poisson arrivals rate \(\lambda\), exponential service rate \(\mu\) per server, \(c\) servers, infinite capacity, one shared queue.
+--> (server 1)
arrivals --> [ Q ] --+--> (server 2)
lam +--> ...
+--> (server c) each at rate mu
The birth–death rates¶
Arrivals are unaffected by the state: \(\lambda_n=\lambda\) for all \(n\).
Service is state-dependent. With \(n\) customers present, the number of busy servers is \(\min(n,c)\), and each contributes \(\mu\) to the departure rate:
Two different ratios — do not confuse them¶
Offered load. \(\quad r=\dfrac{\lambda}{\mu}\quad\) — the expected number of busy servers, measured in erlangs. It may exceed 1.
Utilisation. \(\quad \rho=\dfrac{\lambda}{c\mu}=\dfrac{r}{c}\quad\) — the fraction of total capacity in use. Stability requires \(\rho<1\), i.e. \(\lambda<c\mu\).
Confusing \(r\) with \(\rho\) is the commonest source of wrong answers in this model. In Problem 1 below, \(r = 2.5\) (two and a half servers are busy on average) while \(\rho = 0.833\).
27.3 Deriving the Distribution¶
Apply the general birth–death result \(P_n=P_0\prod_{k=0}^{n-1}\lambda_k/\mu_{k+1}\).
For \(n\le c\) the denominators are \(\mu,2\mu,\dots,n\mu\):
For \(n>c\) the first \(c\) factors are as above and the rest each contribute \(\lambda/(c\mu)\):
Normalising. The tail is geometric with ratio \(\rho\), converging iff \(\rho<1\):
Result 1. $\(\boxed{\ P_0=\left[\ \sum_{n=0}^{c-1}\frac{r^{\,n}}{n!}\ +\ \frac{r^{\,c}}{c!}\cdot\frac{1}{1-\rho}\ \right]^{-1}}, \qquad r=\frac\lambda\mu,\ \ \rho=\frac{r}{c}<1 \tag{2.3}\)$
27.4 Erlang-C and the Performance Measures¶
The probability that a customer must wait¶
An arrival waits precisely when all \(c\) servers are busy, i.e. \(n\ge c\):
Result 2 (Erlang-C formula). $\(\boxed{\ C(c,r)=\Pr[\text{wait}]=\sum_{n\ge c}P_n=\frac{r^{\,c}}{c!\,(1-\rho)}P_0\ }\tag{3.1}\)$
This is the single most used formula in call-centre and telephony design. (Its cousin Erlang-B applies to loss systems with no queue and is the \(M/M/c/c\) model.)
Expected queue length¶
Only customers beyond the \(c\) in service are waiting:
Result 3. $\(\boxed{\ L_q=\frac{r^{\,c}\rho}{c!\,(1-\rho)^2}P_0 \;=\; C(c,r)\cdot\frac{\rho}{1-\rho}\ }\tag{3.2}\)$
The second form is memorable: the mean queue is the probability of waiting times the \(M/M/1\)-style congestion factor.
The rest, by two identities¶
The identity \(L_s-L_q=r\) generalises \(L_s-L_q=\rho\) from \(M/M/1\): the expected number in service equals the offered load. Since \(r\) is also \(c\rho\), it is the expected number of busy servers. Use this as the standard check.
The complete recipe¶
- Compute \(r=\lambda/\mu\) and \(\rho=r/c\); verify \(\rho<1\).
- Compute \(P_0\) from (2.3) — this is the only laborious step.
- Compute \(C(c,r)\) from (3.1) and \(L_q\) from (3.2).
- Get \(L_s=L_q+r\), then \(W_q=L_q/\lambda\) and \(W_s=W_q+1/\mu\).
- Check \(L_s-L_q=r\) and \(W_s-W_q=1/\mu\).
27.5 Solved Problems¶
Problem 1 — A three-server help desk¶
A help desk has \(c=3\) agents. Calls arrive at \(\lambda=10\) per hour and each agent handles calls at \(\mu=4\) per hour. Find \(P_0\), the probability of waiting, \(L_q\), \(L_s\), \(W_q\) and \(W_s\).
Solution.
Step 1 — the two ratios.
On average 2.5 of the 3 agents are busy.
Step 2 — \(P_0\).
Step 3 — Erlang-C.
Seven callers in ten must wait.
Step 4 — the measures.
Checks. \(L_s-L_q=2.5=r\) ✓. \(\lambda W_s=10(0.60112)=6.011=L_s\) ✓.
Interpretation. Each agent is busy \(83\,\%\) of the time — high but not extreme — yet a caller waits \(21\) minutes for a \(15\)-minute call. The \(1/(1-\rho)\) blow-up of Lesson 24 is at work here too.
Problem 2 — Is a fourth agent worth it?¶
Continue Problem 1. Evaluate adding a fourth agent.
Solution. Now \(c=4\), \(r=2.5\) unchanged, \(\rho=2.5/4=0.625\).
| \(c=3\) | \(c=4\) | change | |
|---|---|---|---|
| Utilisation \(\rho\) | 0.833 | 0.625 | \(-25\,\%\) |
| \(\Pr[\text{wait}]\) | 0.7022 | 0.3199 | \(-54\,\%\) |
| \(L_q\) | 3.511 | 0.533 | \(\mathbf{-85\,\%}\) |
| \(W_q\) | 21.07 min | 3.20 min | \(\mathbf{-85\,\%}\) |
Interpretation. A 33 % increase in staff cuts waiting by 85 %. Near-saturated systems respond dramatically to a small capacity addition, which is why the marginal fourth agent is very often worth hiring even at full salary. Lesson 29 turns this into a formal cost comparison.
Problem 3 — M/M/2 against M/M/1 of the same total capacity¶
A depot handles \(\lambda=18\) jobs per hour. Compare two counters at \(\mu=12\)/h each (\(M/M/2\)) with a single counter at \(\mu=24\)/h (\(M/M/1\)). Both have total capacity \(24\)/h.
Solution.
\(M/M/2\): \(r=18/12=1.5\), \(\rho=0.75\).
\(M/M/1\) with \(\mu=24\): \(\rho=0.75\).
| \(M/M/2\), \(\mu=12\) | \(M/M/1\), \(\mu=24\) | |
|---|---|---|
| \(\rho\) | 0.750 | 0.750 |
| \(P_0\) | 0.1429 | 0.2500 |
| \(L_s\) | 3.4286 | 3.0000 |
| \(W_s\) | 11.43 min | 10.00 min |
Interpretation. The single fast server wins, by \(14\,\%\) on waiting time. The reason is structural: in \(M/M/2\) a job can be stuck behind a long job at one counter while the other counter is free but already committed. Two half-speed servers can never match one full-speed one.
But — and this matters — the \(M/M/2\) system is more robust. If the single server fails, the system stops entirely; if one of two servers fails, capacity halves but service continues. Choosing between them is a trade-off between efficiency and resilience, not a pure optimisation.
Problem 4 — Designing to a service-level target¶
A clinic has \(\lambda=6\) patients per hour and each doctor serves at \(\mu=4\) per hour. Management requires that no more than 25 % of patients wait at all. How many doctors are needed?
Solution. \(r = 6/4 = 1.5\). Stability alone needs \(c\ge2\). Compute Erlang-C for successive \(c\):
| \(c\) | \(\rho=r/c\) | \(P_0\) | \(C(c,r)=\Pr[\text{wait}]\) | \(L_q\) | \(W_q\) |
|---|---|---|---|---|---|
| 2 | 0.7500 | 0.14286 | 0.64286 | 1.92857 | 19.29 min |
| 3 | 0.5000 | 0.21053 | 0.23684 | 0.23684 | 2.37 min |
| 4 | 0.3750 | 0.22099 | 0.07459 | 0.04475 | 0.45 min |
| 5 | 0.3000 | 0.22277 | 0.02014 | 0.00863 | 0.09 min |
With \(c=2\), \(64\,\%\) wait — far above target. With \(c=3\), only \(23.7\,\%\) wait.
Interpretation. Look at how fast the numbers improve. Going from \(2\) to \(3\) doctors cuts waiting time by a factor of eight; going from \(3\) to \(4\) cuts it by a further factor of five but from an already small base. The first server past the point of saturation delivers almost all of the benefit — a rule of thumb worth carrying into any staffing discussion.
Problem 5 — Reading a real system¶
A bank's three tellers each serve \(20\) customers per hour; arrivals average \(50\) per hour. The branch manager reports "utilisation is 83 %, and average queue length is under four people — we are running efficiently." Compute the figures and evaluate the claim.
Solution. \(r=50/20=2.5\), \(\rho=2.5/3=0.8333\). These are precisely Problem 1's numbers scaled in time, so \(P_0=0.044944\), \(C=0.70225\), \(L_q=3.511\).
Evaluating the claim. The manager's two facts are correct but the conclusion does not follow:
- \(L_q=3.51\) is under four — but \(70\,\%\) of customers wait, and a queue of four people is what a customer sees on arrival, which shapes their impression of the branch.
- Utilisation of \(83\,\%\) leaves the branch on the steep part of the \(1/(1-\rho)\) curve. A \(10\,\%\) rise in arrivals to \(55\)/h gives \(\rho=0.9167\), and \(L_q\) rises to \(\mathbf{9.31}\) — queue length nearly triples for a 10 % rise in demand.
- All the same, \(W_q=4.2\) minutes is genuinely acceptable for a bank branch.
Verdict. The system is performing acceptably today but has almost no margin. The right recommendation is not "add a teller now" but "monitor arrivals; at \(55\)/h the fourth teller becomes necessary." Report the sensitivity, not just the level — that is what distinguishes an OR analysis from a status report.
27.6 Practice Problems¶
- \(\lambda=8\)/h, \(\mu=5\)/h, \(c=2\). Find \(r\), \(\rho\), \(P_0\), \(\Pr[\text{wait}]\), \(L_q\), \(W_q\). (Answer: \(1.6\), \(0.8\), \(0.11111\), \(0.71111\), \(2.84444\), \(21.33\) min)
- Show that (2.3) and (3.2) reduce to the \(M/M/1\) formulas when \(c=1\).
- A workshop has \(\lambda=12\)/h and \(\mu=5\)/h per bench. What is the minimum number of benches for stability, and what is \(W_q\) at that number? (Answer: \(c=3\); \(\rho=0.8\), \(W_q=12.94\) min)
- For Problem 1's help desk, what happens to \(W_q\) if arrivals rise from \(10\) to \(11\) per hour with \(c=3\)? (Answer: \(\rho=0.9167\), \(L_q=9.314\), \(W_q=50.8\) min — a \(10\,\%\) demand rise more than doubles the wait)
- Explain in two sentences why \(L_s - L_q = r\) rather than \(\rho\) in this model.
27.7 Summary¶
- \(M/M/c\): \(c\) parallel servers, one shared queue. Service rate is \(\min(n,c)\mu\).
- Offered load \(r=\lambda/\mu\) (mean busy servers, may exceed 1) is not the same as utilisation \(\rho=r/c\) (must be \(<1\)).
- \(P_0=\left[\sum_{n=0}^{c-1}\dfrac{r^n}{n!}+\dfrac{r^c}{c!(1-\rho)}\right]^{-1}\) — the one laborious step.
- Erlang-C \(C(c,r)=\dfrac{r^c}{c!(1-\rho)}P_0\) is the probability of waiting; then \(L_q=C(c,r)\dfrac{\rho}{1-\rho}\).
- \(L_s=L_q+r\) and \(W_s=W_q+1/\mu\) are the standard checks.
- Adding one server to a near-saturated system produces an enormous improvement (85 % in Problem 2); further servers add little.
- One server of rate \(c\mu\) beats \(c\) servers of rate \(\mu\) — but is far less resilient to failure.
- Always report the sensitivity of the answer to \(\lambda\), because near \(\rho=1\) a small demand increase produces a large service collapse.
Next lesson: L28 — Models IV and V: \((M/M/c):(N/\text{FCFS})\) and finite-source (machine-repair) queues.
Practise now: unit3-queue-inventory-lab.html → Multi-Server Lab: set \(\lambda\), \(\mu\) and \(c\),
see the Erlang-C curve, and find the smallest \(c\) meeting a service-level target.