Lesson 28: Models IV and V: (M/M/c):(N/FCFS) and Finite-Source Queues¶
28.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- Combine multiple servers with finite capacity to analyse \((M/M/c):(N/\text{FCFS})\).
- Analyse the machine-repair (finite-source) model with one or several repairmen.
- Use the Erlang-B loss formula for systems with no waiting room.
- Recognise when the calling population must be treated as finite.
- Explain why service discipline (FCFS, LIFO, SIRO) does not change the mean measures.
28.2 Model IV — (M/M/c):(N/FCFS)¶
This model simply combines Lessons 26 and 27: \(c\) servers and a limit \(N\) on the number in the system (\(N\ge c\), leaving \(N-c\) waiting places).
The birth–death machinery gives, with \(r=\lambda/\mu\) and \(\rho=r/c\):
Result 1. $\(P_n=\begin{cases}\dfrac{r^{\,n}}{n!}P_0 & 0\le n\le c\\[8pt] \dfrac{r^{\,n}}{c!\,c^{\,n-c}}P_0=\dfrac{r^{\,c}}{c!}\rho^{\,n-c}P_0 & c\le n\le N\end{cases}\tag{1.1}\)$ $\(P_0=\left[\sum_{n=0}^{c-1}\frac{r^{\,n}}{n!}+\frac{r^{\,c}}{c!}\sum_{n=c}^{N}\rho^{\,n-c}\right]^{-1} =\left[\sum_{n=0}^{c-1}\frac{r^{\,n}}{n!}+\frac{r^{\,c}}{c!}\cdot\frac{1-\rho^{\,N-c+1}}{1-\rho}\right]^{-1}\tag{1.2}\)$ (the last factor becomes \(N-c+1\) when \(\rho=1\)).
No stability condition is required — the sum is finite, so \(\rho>1\) is permitted, exactly as in Lesson 26. The measures are
Careful. In the finite-capacity case the identity \(L_s = L_q + r\) fails, because the mean number busy is not \(r\) but \(\lambda_{\text{eff}}/\mu\). Use $\(L_s = L_q + \frac{\lambda_{\text{eff}}}{\mu}\)$ or simply compute \(L_s=\sum nP_n\) directly. This is the trap in Model IV.
28.3 Model V — Finite-Source (Machine-Repair) Queues¶
Why the calling population matters¶
Every model so far assumed an infinite calling population, so that \(\lambda\) did not depend on how many customers were already in the system. That fails whenever the population is small.
The machine-interference problem. \(M\) machines are each liable to break down. A broken machine cannot break down again, so the more machines are already waiting for repair, the lower the rate at which new breakdowns occur.
where \(\lambda\) is the failure rate of one running machine. With \(c\) repairmen, \(\mu_n = \min(n,c)\mu\).
The solution¶
Result 2. With \(c\) repairmen and \(M\) machines, $\(P_n = \begin{cases}\dbinom{M}{n}\left(\dfrac\lambda\mu\right)^{n}P_0 & 0\le n\le c\\[10pt] \dfrac{M!}{(M-n)!\,c!\,c^{\,n-c}}\left(\dfrac\lambda\mu\right)^{n}P_0 & c\le n\le M\end{cases}\tag{2.1}\)$ with \(P_0\) from normalisation. There is never a stability condition: the population regulates itself.
The key quantities:
Two derived measures that managers actually ask for:
- Machine availability \(=\dfrac{M-L_s}{M}\) — the fraction of the fleet productive at any moment.
- Repairman utilisation \(=\dfrac{\text{mean number busy}}{c}=\dfrac{1}{c}\sum_n\min(n,c)P_n\).
28.4 Erlang-B: Loss Systems with No Queue¶
When \(N=c\) there is no waiting room at all: an arrival finding every server busy is lost. This is the classic telephone-trunk model.
Erlang-B (loss) formula. $\(B(c,r)=P_c=\frac{r^{\,c}/c!}{\displaystyle\sum_{n=0}^{c}r^{\,n}/n!} \tag{3.1}\)$
A recursion that is trivial to evaluate by hand, and numerically stable:
Remarkable fact (insensitivity). Erlang-B depends on the service-time distribution only through its mean. Whether calls are exponential, constant or wildly variable, the blocking probability is the same. This is why (3.1) has been trusted in telecommunications for a century.
28.5 On Service Discipline¶
\(M/M/c\) has been analysed under FCFS throughout. What if service is LIFO, or SIRO (service in random order), or by priority?
Theorem. For any work-conserving, non-anticipating discipline that does not use service-time information, the distribution of the number in the system — and hence \(L_s\), \(L_q\), \(W_s\), \(W_q\) — is unchanged.
The reason is that the number present changes only when someone arrives or someone departs, and neither rate depends on which customer is chosen for service.
What does change is the variance of the waiting time. FCFS is the fairest: everyone waits about the same. LIFO and SIRO have the same mean wait but a much longer tail — some unlucky customer waits a very long time. Priority disciplines lower the mean wait for urgent classes at the direct expense of the rest, which is exactly what a hospital triage system is designed to do.
28.6 Solved Problems¶
Problem 1 — Two servers with limited waiting room¶
A clinic has \(c=2\) doctors and room for \(N=5\) patients in total. Patients arrive at \(\lambda=6\) per hour; each doctor serves at \(\mu=4\) per hour. Analyse the system.
Solution. \(r=6/4=1.5\), \(\rho=1.5/2=0.75\), \(c=2\), \(N=5\).
Step 1 — the coefficients \(C_n=P_n/P_0\).
| \(n\) | formula | \(C_n\) |
|---|---|---|
| 0 | \(1\) | 1.00000 |
| 1 | \(r\) | 1.50000 |
| 2 | \(r^2/2!\) | 1.12500 |
| 3 | \(C_2\rho\) | 0.84375 |
| 4 | \(C_3\rho\) | 0.63281 |
| 5 | \(C_4\rho\) | 0.47461 |
| \(\sum C_n\) | 5.57617 |
| \(n\) | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| \(P_n\) | 0.17933 | 0.26900 | 0.20175 | 0.15131 | 0.11349 | 0.08511 |
Step 2 — blocking and throughput.
Step 3 — the measures.
Check. \(L_s-L_q=1.3723\), and \(\lambda_{\text{eff}}/\mu=5.4893/4=1.3723\) ✓ — note this is not \(r=1.5\), exactly as warned in §1.
Interpretation. Only \(6.93\) minutes of waiting looks excellent, but \(8.5\,\%\) of patients are sent away. In a clinic those patients do not vanish — they return later, sicker. A loss model must always be paired with a statement of where the lost demand goes.
Problem 2 — Machine repair with one repairman¶
A factory has \(M=6\) machines. Each running machine fails at \(\lambda=0.1\) per hour; one repairman repairs at \(\mu=0.4\) per hour. Find the distribution of broken machines, the average number running, the repairman's utilisation and the average downtime.
Solution. \(\lambda/\mu=0.25\), \(c=1\), so \(C_n=\dfrac{M!}{(M-n)!}(0.25)^n\).
| \(n\) | \(C_n\) | \(P_n\) |
|---|---|---|
| 0 | 1.00000 | 0.11716 |
| 1 | \(6(0.25)=1.5\) | 0.17574 |
| 2 | \(6\cdot5(0.0625)=1.875\) | 0.21968 |
| 3 | \(6\cdot5\cdot4(0.015625)=1.875\) | 0.21968 |
| 4 | \(360(0.00390625)=1.40625\) | 0.16476 |
| 5 | \(720(0.0009766)=0.703125\) | 0.08238 |
| 6 | \(720(0.000244)=0.17578\) | 0.02059 |
| \(\sum=8.53516\) | 1.00000 |
Interpretation. Repair itself takes only \(2.5\) hours; the other \(4.49\) hours are waiting for the repairman. The fleet is producing at only \(59\,\%\) of capacity while the repairman is busy \(88\,\%\) of the time — a system in visible distress, and precisely the situation the finite-source model was invented to expose.
Problem 3 — Would a second repairman pay?¶
Continue Problem 2. A repairman costs \(₹150\) per hour; each machine down costs \(₹500\) per hour in lost output. Evaluate hiring a second repairman.
Solution. With \(c=2\), \(C_n=\dfrac{M!}{(M-n)!\,2!\,2^{\,n-2}}(0.25)^n\) for \(n\ge2\):
| \(n\) | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| \(P_n\) | 0.24204 | 0.36307 | 0.22692 | 0.11346 | 0.04255 | 0.01064 | 0.00133 |
The economics.
| \(c=1\) | \(c=2\) | |
|---|---|---|
| Machines down \(L_s\) | 2.4687 | 1.3886 |
| Availability | 58.9 % | 76.9 % |
| Downtime cost \(500L_s\) | ₹1234.32 | ₹694.31 |
| Labour cost \(150c\) | ₹150.00 | ₹300.00 |
| Total per hour | ₹1384.32 | ₹994.31 |
Hire the second repairman: it saves \(₹390\) per hour, about \(₹31\) lakh a year on a single shift.
Interpretation. Note the second repairman is idle \(42\,\%\) of the time and is still worth hiring. Judging staffing by "are they busy enough?" is exactly backwards when the cost of the thing waiting dwarfs the cost of the server. The right question is never "is the server busy?" but "what does the queue cost?"
Problem 4 — A loss system: how many trunk lines?¶
A small exchange offers \(r=3\) erlangs of traffic. Calls finding all lines busy are lost (no queue). How many lines are needed to keep blocking below \(5\,\%\)?
Solution. Use the recursion \(B(c,r)=\dfrac{rB(c-1,r)}{c+rB(c-1,r)}\) with \(B(0,3)=1\):
| \(c\) | working | \(B(c,3)\) |
|---|---|---|
| 1 | \(3(1)/(1+3)\) | 0.75000 |
| 2 | \(3(0.75)/(2+2.25)\) | 0.52941 |
| 3 | \(3(0.52941)/(3+1.58824)\) | 0.34615 |
| 4 | \(3(0.34615)/(4+1.03846)\) | 0.20611 |
| 5 | \(3(0.20611)/(5+0.61832)\) | 0.11005 |
| 6 | \(3(0.11005)/(6+0.33016)\) | 0.05216 |
| 7 | \(3(0.05216)/(7+0.15647)\) | 0.02186 |
\(c=6\) gives \(5.22\,\%\) — just above target; \(c=7\) gives \(2.19\,\%\).
Interpretation. Seven lines to carry three erlangs — an "efficiency" of only \(43\,\%\). That over-provisioning is unavoidable: blocking falls roughly geometrically in \(c\), so each extra line buys less than the last. This is also why trunking works: a single exchange carrying \(30\) erlangs needs about \(37\) lines (\(123\,\%\) of load) whereas ten separate exchanges of \(3\) erlangs need \(70\). Consolidation of demand is the whole business case for shared infrastructure.
Problem 5 — Choosing between models¶
For each situation, state which model applies and why.
| Situation | Model | Reason |
|---|---|---|
| (a) 5 machines, 2 mechanics, plant floor | Finite source, \(c=2\) | The population is small and a broken machine cannot break again |
| (b) Call centre, 40 agents, callers hang up if all busy | Erlang-B, \(M/M/c/c\) | No waiting facility; blocked calls are lost |
| (c) Call centre, 40 agents, callers hold in a queue | \(M/M/c\), Erlang-C | Unlimited holding, infinite caller population |
| (d) Clinic, 3 doctors, waiting room seats 8 | \((M/M/c):(N)\) with \(c=3, N=11\) | Both multiple servers and finite capacity |
| (e) Petrol pump, 2 nozzles, forecourt holds 6 cars | \((M/M/c):(N)\) with \(c=2, N=6\) | As above; the forecourt is the capacity |
| (f) Website, thousands of users, 20 threads | \(M/M/c\) | Population effectively infinite relative to servers |
The decision rule. Use a finite-source model whenever the population is less than about \(10\) times the number of servers; otherwise the infinite-source approximation is safe. Use a finite capacity model whenever customers are physically turned away rather than allowed to wait.
Why it matters. Applying \(M/M/1\) to situation (a) with \(\lambda = 5(0.1) = 0.5\) and \(\mu = 0.4\) gives \(\rho = 1.25 > 1\) — the model reports an unstable system that in reality runs perfectly well. Choosing the wrong model does not give a slightly wrong answer; it gives a meaningless one.
28.7 Practice Problems¶
- \((M/M/2):(4)\) with \(\lambda=4\)/h, \(\mu=3\)/h. Find \(P_0\), \(P_4\) and \(\lambda_{\text{eff}}\). (Answer: \(0.23754\), \(0.09384\), \(3.6246\)/h)
- Four machines, \(\lambda=0.2\)/h each, one repairman at \(\mu=1\)/h. Find the availability. (Answer: \(L_s=0.99171\), availability \(75.2\,\%\))
- Use the Erlang-B recursion to find \(B(5, 2)\). (Answer: \(0.03670\))
- Repeat Problem 3 with the downtime cost reduced to \(₹200\) per machine-hour. Is the second repairman still justified? (Answer: \(c=1\) costs \(₹643.74\), \(c=2\) costs \(₹577.72\) — yes, but only just; the break-even downtime cost is \(₹138.9\) per hour)
- Explain in three sentences why LIFO and FCFS give the same \(L_q\) but very different waiting-time variances.
28.8 Summary¶
- Model IV \((M/M/c):(N)\) combines multiple servers with finite capacity. No stability condition; \(\lambda_{\text{eff}}=\lambda(1-P_N)\); and \(L_s = L_q + \lambda_{\text{eff}}/\mu\), not \(L_q+r\).
- Model V (finite source) has \(\lambda_n=(M-n)\lambda\): the population regulates itself, so the system is always stable. Report availability \((M-L_s)/M\), not just \(L_s\).
- Downtime in a repair system is dominated by waiting for the repairman, not by repair itself.
- Erlang-B \(B(c,r)\) handles loss systems with no queue and is computed by the recursion \(B(c,r)=rB(c-1,r)/[c+rB(c-1,r)]\). It is insensitive to the service distribution beyond its mean.
- Loss systems need heavy over-provisioning at low load, but pooling demand makes them far more efficient — the argument for shared infrastructure.
- Service discipline does not change the mean measures — only the variance of the waiting time and the fairness of the outcome.
- Choosing the wrong model class (finite vs infinite source) is not a small error: it can report an unstable system that in fact works perfectly.
Next lesson: L29 — Applications and the economic analysis of queues.
Practise now: unit3-queue-inventory-lab.html → Model Selector: describe a system in words and
the lab identifies the right model, then solves it.