Skip to content

Lesson 26: Model II: (M/M/1):(N/FCFS), the Finite-Capacity Queue

26.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. Derive \(P_n\) for a queue with a finite system capacity \(N\), including the case \(\rho=1\).
  2. Compute the blocking probability \(P_N\) and the effective arrival rate \(\lambda_{\text{eff}}\).
  3. Apply Little's law correctly in a system where customers are turned away.
  4. Explain why a finite queue is stable even when \(\lambda>\mu\).
  5. Choose the capacity \(N\) by marginal analysis of revenue against space cost.

26.2 The Model

Real systems have limits: a car park has bays, a telephone exchange has lines, a doctor's waiting room has chairs, a router has buffer memory. When the system holds \(N\) customers, further arrivals are turned away and lost forever.

Kendall notation. \((M/M/1):(N/\text{FCFS})\) — Poisson arrivals, exponential service, one server, system capacity \(N\) (including the one in service, so there are \(N-1\) waiting places).

The birth–death rates are

\[\lambda_n=\begin{cases}\lambda & 0\le n\le N-1\\ 0 & n\ge N\end{cases} \qquad\qquad \mu_n=\mu \ \ (1\le n\le N).\]

Setting \(\lambda_n=0\) for \(n\ge N\) is the whole of the modelling: an arrival that finds the system full simply does not join.

26.3 Deriving the State Distribution

The cut equations are unchanged for \(n<N\), so \(P_n=\rho^nP_0\) for \(0\le n\le N\) where \(\rho=\lambda/\mu\) as usual. The only difference is that the normalising sum is now finite:

\[P_0\sum_{n=0}^{N}\rho^n = 1.\]

Case ρ≠1

The finite geometric sum is \(\dfrac{1-\rho^{N+1}}{1-\rho}\), so

Result 1. $\(\boxed{\ P_0=\frac{1-\rho}{1-\rho^{\,N+1}},\qquad P_n=\frac{(1-\rho)\rho^{\,n}}{1-\rho^{\,N+1}},\ \ 0\le n\le N\ }\tag{2.1}\)$

Case ρ=1

The sum becomes \(\sum_{n=0}^{N}1 = N+1\), so

Result 2. $\(\boxed{\ P_n=\frac{1}{N+1}\ \text{ for all } n,\qquad L_s=\frac{N}{2}\ }\tag{2.2}\)$ a uniform distribution over the \(N+1\) states.

This case is not a curiosity. In the infinite model \(\rho=1\) was catastrophic — the queue grew without bound. Here it is perfectly well behaved. Truncation always restores stability.

Stability requires nothing

There is no stability condition. The sum \(\sum_{n=0}^{N}\rho^n\) is finite for every \(\rho\), including \(\rho>1\). Formula (2.1) is valid for an overloaded system; the excess demand simply appears as blocked customers rather than as an exploding queue.

26.4 The Performance Measures

Expected number in the system

Differentiating the finite geometric sum gives, for \(\rho\ne1\),

\[\boxed{\ L_s=\frac{\rho\left[1-(N+1)\rho^{\,N}+N\rho^{\,N+1}\right]}{(1-\rho)\left(1-\rho^{\,N+1}\right)}\ }\tag{3.1}\]

and \(L_s=N/2\) when \(\rho=1\).

The two arrival rates — the heart of this model

Blocking probability. \(P_N\) is the probability the system is full. An arrival at such a moment is lost.

\[\text{customers lost per unit time}=\lambda P_N,\qquad \boxed{\ \lambda_{\text{eff}}=\lambda(1-P_N)\ }\tag{3.2}\]

\(\lambda_{\text{eff}}\) is the rate at which customers actually enter the system, and it is the throughput. There are three equivalent expressions for it, and checking that they agree is the best possible verification of an answer:

\[\lambda_{\text{eff}}=\lambda(1-P_N)=\sum_{n=0}^{N-1}\lambda P_n=\mu(1-P_0). \tag{3.3}\]

The last form says: what goes in must come out. Output is \(\mu\) whenever the server is busy, which is a fraction \(1-P_0\) of the time.

Queue length and the waiting times

\[L_q=L_s-(1-P_0) \tag{3.4}\]

because \(1-P_0\) is the expected number in service.

The one error everyone makes. Little's law must be applied with the effective rate: $\(\boxed{\ W_s=\frac{L_s}{\lambda_{\text{eff}}},\qquad W_q=\frac{L_q}{\lambda_{\text{eff}}}\ }\tag{3.5}\)$ Using the nominal \(\lambda\) here divides by too large a number and understates the waiting time. Customers who were turned away never waited, so they must not appear in the denominator.

26.5 Solved Problems

Problem 1 — The complete finite-capacity calculation

A single-chair barber's shop has room for \(5\) people in total (one in the chair, four waiting). Customers arrive at \(\lambda = 6\) per hour and haircuts take an exponential mean of \(7.5\) minutes (\(\mu = 8\) per hour). Find the state distribution, all four performance measures, the proportion of customers turned away, and compare with the infinite-capacity model.

Solution. \(\rho=6/8=0.75\), \(N=5\).

Step 1 — \(P_0\). \(\rho^{N+1}=0.75^{6}=0.177979\).

\[P_0=\frac{1-0.75}{1-0.177979}=\frac{0.25}{0.822021}=\mathbf{0.30413}\]

Step 2 — the distribution. \(P_n=P_0(0.75)^n\):

\(n\) 0 1 2 3 4 5
\(P_n\) 0.30413 0.22810 0.17107 0.12830 0.09623 0.07217

(Sum \(=1.00000\) ✓)

Step 3 — blocking and throughput.

\[P_5=\mathbf{0.07217}\ \Rightarrow\ \textbf{7.22 % of customers are turned away}\]
\[\text{lost} = 6(0.07217)=\mathbf{0.433\text{ customers per hour}}\]
\[\lambda_{\text{eff}}=6(1-0.07217)=\mathbf{5.567\text{ per hour}}\]

Check: \(\mu(1-P_0)=8(1-0.30413)=8(0.69587)=5.567\) ✓

Step 4 — the measures. From (3.1) with \(\rho=0.75\), \(N=5\):

\[L_s=\frac{0.75\left[1-6(0.75)^5+5(0.75)^6\right]}{(0.25)(0.822021)}=\mathbf{1.7009\text{ customers}}\]
\[L_q=L_s-(1-P_0)=1.7009-0.69587=\mathbf{1.0051\text{ customers}}\]
\[W_s=\frac{1.7009}{5.567}=0.30554\text{ h}=\mathbf{18.33\text{ minutes}}\]
\[W_q=\frac{1.0051}{5.567}=0.18054\text{ h}=\mathbf{10.83\text{ minutes}}\]

Check: \(W_s-W_q=0.075\) h \(=7.5\) min \(=1/\mu\) ✓

Step 5 — comparison with \(N=\infty\).

\(N=5\) \(N=\infty\)
\(P_0\) 0.3041 0.2500
\(L_s\) 1.701 3.000
\(L_q\) 1.005 2.250
\(W_s\) 18.33 min 30.00 min
Throughput 5.567/h 6.000/h
Customers lost 7.22 % 0 %

Interpretation. The finite room looks better on every congestion measure — shorter queue, shorter wait, more idle time. It is not better; it is hiding the demand it turned away. The four chairs are, in effect, rationing service. Any comparison of two systems with different capacities must put throughput and lost customers alongside the queue statistics, or it will reward the system that serves fewest people.

Problem 2 — The case ρ = 1

A single-server system has \(\lambda=\mu=8\) per hour and capacity \(N=4\). Find the distribution, \(L_s\), throughput and \(W_s\).

Solution. Since \(\rho=1\), use (2.2):

\[P_n=\frac{1}{N+1}=\frac{1}{5}=\mathbf{0.2}\quad\text{for } n=0,1,2,3,4\]

Every state is equally likely — a striking result: the system is as often empty as it is full.

\[L_s=\frac{N}{2}=\mathbf{2\text{ customers}},\qquad L_q=L_s-(1-P_0)=2-0.8=\mathbf{1.2}\]
\[\lambda_{\text{eff}}=\lambda(1-P_4)=8(0.8)=\mathbf{6.4\text{ per hour}}\]
\[W_s=\frac{2}{6.4}=0.3125\text{ h}=\mathbf{18.75\text{ min}},\qquad W_q=\frac{1.2}{6.4}=\mathbf{11.25\text{ min}}\]

Interpretation. With unlimited waiting room, \(\rho=1\) would make \(L_s\to\infty\). Here the answer is a comfortable \(2\) customers — but \(20\,\%\) of demand is destroyed to achieve it. Truncation buys stability with lost business, and the price is exactly \(\lambda P_N\).

Problem 3 — An overloaded system (ρ > 1)

A petrol pump with one nozzle has space for \(3\) vehicles. Cars arrive at \(10\) per hour; service takes an exponential mean of \(10\) minutes (\(\mu = 6\) per hour). Analyse the system.

Solution. \(\rho = 10/6 = 1.6667 > 1\) — an infinite queue would be unstable. The finite model applies without difficulty.

\[\rho^{N+1}=(1.6667)^4=7.7160,\qquad P_0=\frac{1-1.6667}{1-7.7160}=\frac{-0.6667}{-6.7160}=\mathbf{0.09926}\]
\(n\) 0 1 2 3
\(P_n\) 0.09926 0.16544 0.27574 0.45956
\[P_3=\mathbf{0.45956}\ \Rightarrow\ \textbf{46 % of arriving cars are turned away!}\]
\[\lambda_{\text{eff}}=10(1-0.45956)=\mathbf{5.404\text{ per hour}}\qquad \text{(check: } \mu(1-P_0)=6(0.90074)=5.404\ \checkmark)\]
\[L_s=2.0956,\quad L_q=L_s-(1-P_0)=2.0956-0.90074=1.1949\]
\[W_s=\frac{2.0956}{5.404}=0.38776\text{ h}=\mathbf{23.27\text{ min}},\qquad W_q=\mathbf{13.27\text{ min}}\]

Interpretation. The pump is busy \(90\,\%\) of the time and the average queue is barely two cars — figures a manager might call satisfactory. They are not. Nearly half of all customers drive away, costing \(4.6\) sales per hour. In an overloaded finite system the queue statistics look good precisely because the system is failing. The number that matters is \(\lambda P_N\), and it should be the first quantity reported.

Problem 4 — Choosing the capacity to meet a blocking target

For the barber's shop of Problem 1 (\(\lambda=6\), \(\mu=8\)), management wants no more than \(5\,\%\) of customers turned away. What is the smallest capacity \(N\)?

Solution. Compute \(P_N=\dfrac{(1-\rho)\rho^N}{1-\rho^{N+1}}\) for successive \(N\):

\(N\) \(P_N\) Lost per hour \(L_s\) \(W_s\)
3 0.15429 0.926 1.149 13.58 min
4 0.10371 0.622 1.444 16.11 min
5 0.07217 0.433 1.701 18.33 min
6 0.05135 0.308 1.922 20.26 min
7 0.03708 0.223 2.110 21.91 min

\(N=6\) still blocks \(5.14\,\%\); \(N=7\) blocks \(3.71\,\%\).

\[\boxed{N=7\ \text{(one chair in use plus 6 waiting places)}}\]

Interpretation. Note the trade-off in the last two columns: every chair added reduces blocking but lengthens the wait for those already inside. Going from \(N=3\) to \(N=7\) cuts blocking from \(15.4\,\%\) to \(3.7\,\%\) but raises the average visit from \(13.6\) to \(21.9\) minutes. There is no capacity that is best on both counts; the choice depends on whether a lost customer or an annoyed one costs more. Note too the diminishing returns: the first extra chair saves \(0.30\) customers per hour, the fourth saves only \(0.09\).

Problem 5 — The economically optimal capacity

Each customer actually served yields a contribution of \(₹40\). Each waiting place costs \(₹8\) per hour in rent and furniture. With \(\lambda=6\), \(\mu=8\) as before, find the profit-maximising \(N\).

Solution. Net profit per hour \(=40\lambda_{\text{eff}}-8(N-1)\), since a capacity of \(N\) requires \(N-1\) waiting places.

\(N\) \(\lambda_{\text{eff}}\) Revenue \(40\lambda_{\text{eff}}\) Space cost \(8(N-1)\) Net
2 4.5405 ₹181.62 ₹8 ₹173.62
3 5.0743 ₹202.97 ₹16 ₹186.97
4 5.3777 ₹215.11 ₹24 ₹191.11
5 5.5670 ₹222.68 ₹32 ₹190.68
6 5.6919 ₹227.68 ₹40 ₹187.68
7 5.7775 ₹231.10 ₹48 ₹183.10
\[\boxed{N^{*}=4:\ \text{one chair in use and 3 waiting places, net }₹191.11\text{ per hour}}\]

Marginal analysis — the professional way to present this.

Extra place Marginal revenue Marginal cost Add it?
2 → 3 ₹21.35 ₹8 yes
3 → 4 ₹12.14 ₹8 yes
4 → 5 ₹7.57 ₹8 no — stop here
5 → 6 ₹5.00 ₹8 no

Marginal revenue falls monotonically (each extra chair rescues fewer customers than the one before) while marginal cost is constant. Expand while MR > MC and stop the moment it is not. The answer is robust: the net-profit column is nearly flat between \(N=4\) and \(N=5\), so a manager who picks either loses less than fifty paise an hour.

26.6 Practice Problems

  1. \(\lambda=4\)/h, \(\mu=6\)/h, \(N=3\). Find \(P_0\), \(P_3\), \(L_s\) and \(\lambda_{\text{eff}}\). (Answer: \(0.41538\), \(0.12308\), \(1.01538\), \(3.5077\)/h)
  2. Show algebraically that (2.1) tends to \((1-\rho)\rho^n\) as \(N\to\infty\) when \(\rho<1\), and explain why the limit fails for \(\rho>1\).
  3. A car park holds \(4\) cars; arrivals \(8\)/h, mean parking time \(30\) min. What fraction of drivers find it full? (Answer: \(\rho=4\), \(P_4=0.75073\) — three drivers in four)
  4. For Problem 3's pump, how large must \(N\) be to bring blocking below \(20\,\%\)? Compute \(P_N\) for \(N=4,6,8,10\) first. (Answer: impossible: \(P_N\to1-1/\rho=0.40\) as \(N\to\infty\), so blocking can never fall below \(40\,\%\). Throughput is capped at \(\mu=6\)/h against demand of \(10\)/h; no amount of waiting space serves customers a single server has no time for. When \(\rho>1\) you must add CAPACITY, not SPACE.)
  5. Verify the three expressions for \(\lambda_{\text{eff}}\) in (3.3) numerically for Problem 1.

26.7 Summary

  • Finite capacity means \(\lambda_n=0\) for \(n\ge N\); everything else is unchanged.
  • \(P_n=\dfrac{(1-\rho)\rho^n}{1-\rho^{N+1}}\) for \(\rho\ne1\), and \(P_n=\dfrac{1}{N+1}\) for \(\rho=1\).
  • No stability condition is needed. The model is valid for any \(\rho\), including \(\rho>1\).
  • \(P_N\) is the blocking probability; \(\lambda P_N\) customers are lost per unit time; the throughput is \(\lambda_{\text{eff}}=\lambda(1-P_N)=\mu(1-P_0)\).
  • Always use \(\lambda_{\text{eff}}\) in Little's law. This is the single most common error in the topic.
  • Truncation makes congestion statistics look good by discarding demand. Report lost customers alongside \(L_q\) and \(W_q\), always.
  • Capacity should be set by marginal analysis: add a place while its marginal revenue exceeds its marginal cost. Marginal revenue falls fast, so the optimum is usually small.

Next lesson: L27 — Model III, \((M/M/c):(\infty/\text{FCFS})\), the multi-server queue and the Erlang-C formula.

Practise now: unit3-queue-inventory-lab.html → Finite Capacity Lab: set \(N\) with a slider and watch \(P_N\), throughput and \(W_s\) trade off against one another.