Chapter 9 · Reliability, Linear Programming and Queues

9.3 Queueing and Inventory Models

Queues as birth–death processes: Kendall notation, Little's law and PASTA; the steady states of M/M/1, M/M/1/K, M/M/c and M/M/c/K with the Erlang formulas; the Pollaczek–Khinchine formula for M/G/1; and the economic order quantity, with shortages and quantity discounts.

Patients wait in a clinic, calls wait at a help line, jobs wait at a printer, packets wait in a router buffer, aircraft wait for a runway. In each case customers arrive at random times, need a random amount of service, and wait when all servers are busy. Queueing theory predicts how long the queue is, how long a customer waits and what fraction is turned away, from just a few numbers: the arrival rate, the service rate, the number of servers and the room available. Its first and still most quoted result is A. K. Erlang's formula (1917) for the number of telephone lines a village needs. The other half of this section is the oldest piece of inventory theory, the economic order quantity (F. W. Harris, 1913), which balances the cost of ordering against the cost of holding stock.

For exponential inter-arrival and service times the number of customers in the system is a birth–death process, and its steady state comes straight from the cut equations $\lambda_n\pi_n=\mu_{n+1}\pi_{n+1}$ of the birth–death steady-state theorem in §3.3. Two general principles then turn state probabilities into waiting times: Little's law $L=\lambda W$ and PASTA (Poisson arrivals see time averages). For general service times the Pollaczek–Khinchine formula shows that the mean wait depends on the service-time variance as well as its mean. CSIR NET asks for $L$, $L_q$, $W$, $W_q$ and the idle probability of M/M/1 and M/M/c queues, for blocking probabilities in a finite waiting room, for P–K computations (often M/D/1 against M/M/1), and for the EOQ and its response to changes in demand or costs; Part C statements test the standard confusions collected in the ⚠️ box.

Queueing Systems: Kendall Notation and Little's Law

📘 Definition 9.13 — Queueing systems, Kendall notation and performance measures

A queueing system consists of customers arriving at times $A_1\le A_2\le\cdots$, one or more servers, a waiting room and a service discipline (FCFS = first come, first served, unless stated otherwise). Kendall's notation $A/B/c/K/N$ lists the inter-arrival distribution $A$, the service-time distribution $B$, the number of servers $c$, the capacity $K$ of the system (in service plus waiting; $\infty$ if omitted) and the size $N$ of the source population ($\infty$ if omitted). The symbols for $A$ and $B$ are: $M$ (Markovian: exponential, i.e. Poisson arrivals), $D$ (deterministic), $E_k$ (Erlang-$k$, the sum of $k$ iid exponentials), $G$ or $GI$ (general, independent). With arrival rate $\lambda$ and service rate $\mu$ per server (mean service time $1/\mu$), the offered load is $a=\lambda/\mu$ (in erlangs) and the traffic intensity or utilisation is $\rho=\lambda/(c\mu)$.

The standard performance measures in steady state are $P_n=\pi_n$ (probability of $n$ customers in the system), $L$ (mean number in the system), $L_q$ (mean number waiting), $W$ (mean time in the system, or sojourn time) and $W_q$ (mean waiting time before service). For a system that turns customers away, $\lambda_{\text{eff}}$ denotes the rate of customers actually admitted.

Little's law connects the time-average $L$ with the customer-average $W$. It is a statement about sample paths, needing no distributional assumptions at all. Let $N(t)$ be the number of customers present at time $t$, $A(t)=\#\{k:A_k\le t\}$ the number of arrivals by time $t$, $D_k\ge A_k$ the departure time and $W_k=D_k-A_k$ the time in the system of customer $k$.

📐 Theorem 9.28 — Little's law
Suppose that the limits $$\lambda=\lim_{t\to\infty}\frac{A(t)}{t}\in(0,\infty)\qquad\text{and}\qquad W=\lim_{n\to\infty}\frac1n\sum_{k=1}^nW_k\lt\infty$$ exist. Then $L=\lim_{t\to\infty}\frac1t\int_0^tN(s)\,ds$ exists and $$L=\lambda W .$$ Applied to the waiting room only, $L_q=\lambda W_q$; applied to the servers only, the mean number of busy servers is $\lambda\cdot E[S]$, where $E[S]$ is the mean service time. With blocking, $\lambda$ is replaced by $\lambda_{\text{eff}}$, the rate of admitted customers.

Proof. Customer $k$ contributes to $N(s)$ exactly for $s\in[A_k,D_k)$, so $\int_0^tN(s)\,ds=\sum_k\left|[A_k,D_k)\cap[0,t]\right|$. Each term is at most $W_k$ and is $0$ unless $A_k\le t$; it equals $W_k$ when $D_k\le t$. Hence, writing $n(t)=\max\{n:D_1,\dots,D_n\le t\}$, $$\sum_{k\le n(t)}W_k\ \le\ \int_0^tN(s)\,ds\ \le\ \sum_{k\le A(t)}W_k .$$ The right side divided by $t$ is $\frac{A(t)}t\cdot\frac1{A(t)}\sum_{k\le A(t)}W_k\to\lambda W$. For the left side we show $n(t)/t\to\lambda$. First, $\frac{W_n}n=\frac1n\sum_{k\le n}W_k$ $-\frac{n-1}{n}\cdot\frac1{n-1}\sum_{k\lt n}W_k$ $\to W-W=0$. Second, $A_n/n\to1/\lambda$, because $A(A_n)\ge n$ and $A(s)\lt n$ for $s\lt A_n$, so $n/A_n$ is squeezed between values of $A(s)/s$ at times tending to infinity. Hence $D_n/n=A_n/n+W_n/n\to1/\lambda$, and then also $\max_{k\le n}D_k/n\to1/\lambda$ (for $\varepsilon\gt0$, all but finitely many $k$ have $D_k\le k(1/\lambda+\varepsilon)$). Since $n(t)$ is the largest $n$ with $\max_{k\le n}D_k\le t$, this gives $n(t)/t\to\lambda$, and the left side divided by $t$ also tends to $\lambda W$. The two bounds squeeze $\frac1t\int_0^tN$ to $\lambda W$. The other statements apply the same argument to the waiting room ($W_k$ replaced by the waiting time) and to the servers ($W_k$ replaced by the service time). ∎

For the stable queues of this section, the limits exist with probability one and equal the steady-state means (an ergodic theorem for regenerative processes, which we accept), so $L=\sum n\pi_n$ and $W$ is the mean sojourn time of a customer in steady state.

📐 Theorem 9.29 — PASTA and the arrival–departure principle
  1. (PASTA: Poisson Arrivals See Time Averages) If customers arrive as a Poisson process and the arrival process after time $t$ is independent of the state of the system up to time $t$, then the long-run fraction of arrivals that find $n$ customers in the system equals the long-run fraction of time $\pi_n$ during which there are $n$ customers.
  2. If the number in the system changes by single arrivals and departures only, then the long-run fraction of arrivals that find $n$ customers (counting admitted arrivals) equals the long-run fraction of departures that leave $n$ customers behind.

Proof. (1) We give the argument for the Markovian queues of this section, where the state is a birth–death process with arrival rate $\lambda$ in every state (the general proof uses martingale arguments). Over a long time $t$ the system spends about $\pi_nt$ time units in state $n$. During that time arrivals occur at rate $\lambda$, independently of the state, so about $\lambda\pi_nt$ arrivals find state $n$, out of about $\lambda t$ arrivals in all: the fraction is $\pi_n$. (2) An arrival that finds $n$ moves the state from $n$ to $n+1$ (an up-crossing of the level $n+\tfrac12$), and a departure that leaves $n$ moves it from $n+1$ to $n$ (a down-crossing). Up- and down-crossings of the same level alternate, so their numbers differ by at most one at any time; dividing by the total numbers of arrivals and departures, which are asymptotically equal in a stable system, gives equal long-run fractions. ∎

PASTA is what lets us compute waiting-time distributions from $\pi$: an arriving customer in an M/M/1 queue finds $n$ others with probability $\pi_n$. Without Poisson arrivals it fails, as Example 1(b) shows, and it also fails for the admitted customers of a system with blocking (they find $n$ with probability $\pi_n/(1-\pi_K)$, $n\lt K$) and for finite-source models, where the arrival rate depends on the state.

✏️ Example 1 — A walk-in clinic, and a counterexample to "arrivals see averages"
(a) A walk-in clinic receives on average $12$ patients per hour. A patient spends on average $25$ minutes in the clinic, and on average $2$ patients are in the waiting room. Find $L$, $W_q$, the mean consultation time and the mean number of doctors busy; the clinic has $4$ doctors — what is their utilisation? (b) Prove or disprove: in every stable single-server queue, an arriving customer finds the server busy with probability equal to the long-run fraction of time the server is busy.
(a) System $\lambda=12$ per hour and $W=\tfrac{25}{60}$ hour, so $L=\lambda W=12\cdot\tfrac{25}{60}=5$ patients in the clinic on average.
Waiting room $L_q=2$ gives $W_q=L_q/\lambda=\tfrac2{12}$ hour $=10$ minutes. The mean consultation time is $W-W_q=15$ minutes.
Doctors Little's law on the consulting rooms: mean number of busy doctors $=\lambda\cdot E[S]=12\cdot\tfrac14=3=L-L_q$. With $4$ doctors the utilisation is $\rho=\tfrac34=75\%$. No distributional assumption was used anywhere.
(b) False Let customers arrive exactly every $2$ minutes (at times $0,2,4,\dots$) and need exactly $1.5$ minutes each: a D/D/1 queue. The server is busy $75\%$ of the time, yet every arrival finds it idle (the previous customer left $0.5$ minutes earlier). Little's law still holds: $\lambda=\tfrac12$ per minute, $W=1.5$, $L=0.75$. The statement becomes true for Poisson arrivals (Theorem 9.29(1)).

The M/M/1 and M/M/1/K Queues

In an M/M/1 queue, customers arrive as a Poisson process of rate $\lambda$ and are served one at a time by a single server with $\operatorname{Exp}(\mu)$ service times, independent of everything else. By the memoryless property the number in the system $N(t)$ is a birth–death process with $\lambda_n=\lambda$ ($n\ge0$) and $\mu_n=\mu$ ($n\ge1$), and the birth–death steady-state theorem of §3.3 applies with $\theta_n=\rho^n$, $\rho=\lambda/\mu$.

📐 Theorem 9.30 — Steady state of the M/M/1 queue
The M/M/1 queue has a steady state if and only if $\rho=\lambda/\mu\lt1$. Then:
  1. $\pi_n=(1-\rho)\rho^n$ ($n\ge0$), so $P(N\ge n)=\rho^n$, and the server is idle a fraction $\pi_0=1-\rho$ of the time.
  2. $L=\dfrac{\rho}{1-\rho}=\dfrac{\lambda}{\mu-\lambda}$, $\ L_q=\dfrac{\rho^2}{1-\rho}$, $\ W=\dfrac1{\mu-\lambda}$, $\ W_q=\dfrac{\rho}{\mu-\lambda}$, and $\operatorname{Var}(N)=\dfrac{\rho}{(1-\rho)^2}$.
  3. Under FCFS the sojourn time of a customer in steady state is $\operatorname{Exp}(\mu-\lambda)$, and the waiting time satisfies $P(W_q=0)=1-\rho$ and $P(W_q\gt t)=\rho\,e^{-(\mu-\lambda)t}$ for $t\ge0$.
  4. A busy period (from the arrival of a customer to an empty system until the system is next empty) has mean $\dfrac1{\mu-\lambda}$.
If $\rho\ge1$ there is no steady state: the queue is null recurrent for $\rho=1$ and transient for $\rho\gt1$.

Proof. (1) With $\theta_n=\rho^n$, $\sum_n\theta_n\lt\infty$ iff $\rho\lt1$, and the birth rates are bounded, so by the birth–death steady-state theorem (§3.3) a steady state exists iff $\rho\lt1$ and is $\pi_n=\theta_n/\sum\theta_k=(1-\rho)\rho^n$; for $\rho\ge1$ the same theorem gives null recurrence ($\rho=1$) or transience ($\rho\gt1$). Then $P(N\ge n)=\sum_{k\ge n}(1-\rho)\rho^k=\rho^n$.

(2) $N$ is geometric on $\{0,1,\dots\}$ with success probability $1-\rho$, with mean $\frac{\rho}{1-\rho}$ and variance $\frac{\rho}{(1-\rho)^2}$. Next, $L_q=\sum_{n\ge1}(n-1)\pi_n$ $=L-(1-\pi_0)$ $=\frac{\rho}{1-\rho}-\rho=\frac{\rho^2}{1-\rho}$. By Little's law $W=L/\lambda=\frac1{\mu-\lambda}$ and $W_q=L_q/\lambda=\frac{\rho}{\mu-\lambda}$.

(3) By PASTA an arrival finds $n$ customers with probability $(1-\rho)\rho^n$. The customer in service has a remaining service time $\operatorname{Exp}(\mu)$ (memoryless property), so under FCFS the newcomer's sojourn time is the sum of $n+1$ independent $\operatorname{Exp}(\mu)$ times. Its Laplace transform is $$E\left[e^{-sW}\right]=\sum_{n\ge0}(1-\rho)\rho^n\left(\frac{\mu}{\mu+s}\right)^{n+1}=\frac{(1-\rho)\mu}{\mu+s-\rho\mu}=\frac{\mu-\lambda}{\mu-\lambda+s},$$ the transform of $\operatorname{Exp}(\mu-\lambda)$; Laplace transforms determine distributions on $[0,\infty)$. The wait $W_q$ is $0$ if $n=0$ (probability $1-\rho$); given $N\ge1$, $N$ is again geometric on $\{1,2,\dots\}$ with the same parameter, and $W_q$ is a sum of $N$ independent $\operatorname{Exp}(\mu)$ times, which by the same computation is $\operatorname{Exp}(\mu-\lambda)$. Hence $P(W_q\gt t)=\rho e^{-(\mu-\lambda)t}$.

(4) Idle periods and busy periods alternate; an idle period lasts until the next arrival, an $\operatorname{Exp}(\lambda)$ time with mean $1/\lambda$. By the renewal-reward theorem the long-run idle fraction is $\frac{1/\lambda}{1/\lambda+E[B]}$, and it equals $\pi_0=1-\rho$. Solving, $E[B]=\frac{\rho}{\lambda(1-\rho)}=\frac1{\mu-\lambda}$. ∎

Two features deserve attention. First, $L=\frac{\rho}{1-\rho}$ blows up as $\rho\uparrow1$: raising the load from $80\%$ to $90\%$ more than doubles the mean queue ($4\to9$). A server cannot be run at full utilisation with random arrivals. Second, the quantiles of the sojourn time are explicit. In the upper-$\alpha$-point notation of §4.3, the time exceeded by a fraction $\alpha$ of the customers is $w_\alpha=\frac{\log(1/\alpha)}{\mu-\lambda}$, and the time exceeded in the queue is $\frac{\log(\rho/\alpha)}{\mu-\lambda}$ for $\alpha\lt\rho$ (and $0$ otherwise).

✏️ Example 2 — A ticket counter
Customers arrive at a ticket counter as a Poisson process of rate $8$ per hour, and service times are exponential with mean $6$ minutes. (a) Find $L$, $L_q$, $W$ and $W_q$. (b) Find the probability of at least $5$ customers at the counter, the probability that a customer spends more than an hour there, the probability of queueing for more than $30$ minutes, and the time $w_{0.1}$ exceeded by $10\%$ of customers. (c) How fast must the clerk serve to bring $W$ down to $15$ minutes?
(a) $\lambda=8$, $\mu=10$ per hour, $\rho=0.8$. $L=\frac{0.8}{0.2}=4$, $L_q=\frac{0.64}{0.2}=3.2$, $W=\frac1{10-8}=0.5$ h $=30$ min, $W_q=\frac{0.8}{2}=0.4$ h $=24$ min. Checks: $L=\lambda W=8\cdot0.5$ and $L-L_q=\rho$.
(b) $P(N\ge5)=0.8^5=0.328$. $P(W\gt1)=e^{-(10-8)\cdot1}=e^{-2}=0.135$. $P(W_q\gt\tfrac12)=0.8\,e^{-1}=0.294$. $w_{0.1}=\frac{\log10}{2}=1.151$ h $\approx69$ min: one customer in ten spends more than $69$ minutes at the counter, although the mean is $30$.
(c) $W=\frac1{\mu-8}\le\frac14$ iff $\mu\ge12$ per hour, i.e. a mean service time of at most $5$ minutes. A $20\%$ faster clerk (service time $17\%$ shorter) halves $W$: near saturation small changes in $\mu$ have large effects.

A real waiting room is finite. In the M/M/1/K queue at most $K$ customers can be present (one in service, $K-1$ waiting); a customer who arrives to find $K$ present is lost. The state space is $\{0,1,\dots,K\}$ with $\lambda_n=\lambda$ for $n\lt K$ and $\mu_n=\mu$.

📐 Theorem 9.31 — The M/M/1/K queue
For every $\rho=\lambda/\mu\gt0$ the M/M/1/K queue has the steady state $$\pi_n=\frac{(1-\rho)\rho^n}{1-\rho^{K+1}}\ \ (\rho\ne1),\qquad\pi_n=\frac1{K+1}\ \ (\rho=1),\qquad n=0,1,\dots,K .$$
  1. The fraction of arrivals that are lost (the blocking probability) is $\pi_K$, and $\lambda_{\text{eff}}=\lambda(1-\pi_K)=\mu(1-\pi_0)$.
  2. $L=\dfrac{\rho}{1-\rho}-\dfrac{(K+1)\rho^{K+1}}{1-\rho^{K+1}}$ for $\rho\ne1$ and $L=\dfrac K2$ for $\rho=1$; $L_q=L-(1-\pi_0)$; $W=L/\lambda_{\text{eff}}$ and $W_q=L_q/\lambda_{\text{eff}}$.
  3. The blocking probability $\pi_K=1\big/\sum_{j=0}^K\rho^{-j}$ decreases strictly in $K$, to $0$ if $\rho\le1$ and to $1-1/\rho$ if $\rho\gt1$.

Proof. The finite birth–death process is irreducible, so by §3.3 its unique stationary law is $\pi_n\propto\theta_n=\rho^n$, $0\le n\le K$; summing the geometric series gives the formula. (1) By PASTA a fraction $\pi_K$ of arrivals find the system full. Admitted customers arrive at rate $\lambda(1-\pi_K)$; in steady state they leave at the same rate, and departures occur at rate $\mu$ whenever the server is busy, i.e. at long-run rate $\mu(1-\pi_0)$. (2) For $\rho\ne1$, $\sum_{n=0}^Kn\rho^n=\rho\frac{d}{d\rho}\frac{1-\rho^{K+1}}{1-\rho}$, and simplifying $\frac{1-\rho}{1-\rho^{K+1}}\sum n\rho^n$ gives the stated $L$; for $\rho=1$, $L=\frac1{K+1}\sum_{n=0}^Kn=\frac K2$. Exactly one customer is in service whenever $N\ge1$, so $L_q=L-P(N\ge1)$. Little's law with the admitted rate gives $W$ and $W_q$. (3) Dividing numerator and denominator of $\pi_K=\rho^K/\sum_{n\le K}\rho^n$ by $\rho^K$ gives $1/\sum_{j=0}^K\rho^{-j}$, whose denominator increases strictly with $K$. As $K\to\infty$ the denominator tends to $\infty$ if $\rho\le1$ and to $\frac1{1-1/\rho}$ if $\rho\gt1$. ∎

✏️ Example 3 — A barber with three chairs
A barber works alone; besides the barber's chair there are $3$ chairs for waiting customers, and customers who find all chairs taken go elsewhere. Customers arrive as a Poisson process of rate $3$ per hour and haircuts are exponential with mean $15$ minutes. (a) Find the steady-state distribution, the fraction of customers lost, $L$, $L_q$, $W$ and $W_q$. (b) On market days customers arrive at rate $6$ per hour. Is there still a steady state, and what fraction is lost?
Model M/M/1/4 with $\lambda=3$, $\mu=4$, $\rho=0.75$. $\theta=(1,\ 0.75,\ 0.5625,\ 0.4219,\ 0.3164)$, sum $\frac{1-0.75^5}{0.25}=3.0508$.
(a) π $\pi=(0.3278,\ 0.2458,\ 0.1844,\ 0.1383,\ 0.1037)$. So $10.4\%$ of customers are lost and $\lambda_{\text{eff}}=3(1-0.1037)=2.689$ per hour; check: $\mu(1-\pi_0)=4\cdot0.6722=2.689$.
(a) Means $L=\frac{0.75}{0.25}-\frac{5\cdot0.75^5}{1-0.75^5}=3-1.5557=1.444$; $L_q=1.444-0.672=0.772$; $W=\frac{1.444}{2.689}=0.537$ h $\approx32.2$ min; $W_q=\frac{0.772}{2.689}=0.287$ h $\approx17.2$ min. (Dividing by $\lambda=3$ instead of $\lambda_{\text{eff}}$ would understate both times by $10\%$.)
(b) Yes — a finite system always has a steady state, even with $\rho=1.5\gt1$. Now $\theta=(1,\ 1.5,\ 2.25,\ 3.375,\ 5.0625)$ with sum $13.1875$, so $\pi_4=0.384$: $38\%$ of customers are lost, and the barber is idle only $\pi_0=7.6\%$ of the time. By Theorem 9.31(3), no number of chairs could push the loss below $1-\frac1{1.5}=\frac13$.
Interactive 1 — Markovian Queue Lab: Simulated Paths against the Steady State

Choose a model and the arrival rate $\lambda$ (each server works at rate $\mu=1$). The queue is simulated customer by customer with a seeded generator, FCFS. Left: the number in the system $N(t)$ over the last $60$ time units, with the exact $L$ dashed. Right: the fraction of time spent in each state (blue bars) against the exact steady state $\pi_n$ (purple marks). The readouts compare the simulated $L$, $W$ and admitted rate with the theory, and check Little's law $L=\lambda_{\text{eff}}W$ on the simulated data alone. Push $\rho$ towards $1$ in M/M/1 and watch the convergence slow down; push past $1$ and the path drifts away, while the finite models settle for every $\lambda$.

—
L: simulated (exact)—
W: simulated (exact)—
λ_eff: simulated (exact)—
Little check: λ_eff·W vs L—

Multi-server Queues: M/M/c and M/M/c/K

With $c$ identical exponential servers, $n$ customers keep $\min(n,c)$ servers busy, and each busy server completes service at rate $\mu$. So the state is a birth–death process with $\lambda_n=\lambda$ and $\mu_n=\min(n,c)\,\mu$. Write $a=\lambda/\mu$ for the offered load and $\rho=a/c$ for the utilisation per server.

📐 Theorem 9.32 — The M/M/c queue and the Erlang C formula
The M/M/c queue has a steady state if and only if $\rho=\lambda/(c\mu)\lt1$. Then $$\pi_n=\pi_0\frac{a^n}{n!}\ (n\le c),\qquad\pi_n=\pi_0\frac{a^c}{c!}\rho^{\,n-c}\ (n\ge c),$$ $$\pi_0=\left[\sum_{n=0}^{c-1}\frac{a^n}{n!}+\frac{a^c}{c!\,(1-\rho)}\right]^{-1}.$$
  1. The probability that an arrival has to wait (the Erlang C formula) is $C(c,a)=P(N\ge c)=\pi_0\dfrac{a^c}{c!\,(1-\rho)}$.
  2. $L_q=C(c,a)\dfrac{\rho}{1-\rho}$, $\ W_q=\dfrac{C(c,a)}{c\mu-\lambda}$, $\ W=W_q+\dfrac1\mu$, $\ L=L_q+a$; the mean number of busy servers is $a$.
  3. Under FCFS, $P(W_q\gt t)=C(c,a)\,e^{-(c\mu-\lambda)t}$.

Proof. Here $\theta_n=\frac{\lambda^n}{\mu\cdot2\mu\cdots n\mu}=\frac{a^n}{n!}$ for $n\le c$, and for $n\ge c$ each further factor is $\frac{\lambda}{c\mu}=\rho$, so $\theta_n=\frac{a^c}{c!}\rho^{n-c}$. The tail $\sum_{n\ge c}\theta_n=\frac{a^c}{c!}\cdot\frac1{1-\rho}$ is finite iff $\rho\lt1$, and the birth rates are bounded, so the birth–death steady-state theorem (§3.3) gives existence iff $\rho\lt1$ and the formulas for $\pi_n$ and $\pi_0$. (1) By PASTA an arrival waits iff it finds $N\ge c$; summing the tail gives $C(c,a)$. (2) $L_q=\sum_{n\ge c}(n-c)\pi_n=\pi_c\sum_{k\ge0}k\rho^k=\pi_c\frac{\rho}{(1-\rho)^2}$, and $\pi_c=C(c,a)(1-\rho)$, which gives $L_q$. Little's law gives $W_q=L_q/\lambda=\frac{C\rho}{\lambda(1-\rho)}=\frac{C}{c\mu-\lambda}$; then $W=W_q+\frac1\mu$ and $L=\lambda W=L_q+a$. (3) Given that an arrival finds $n\ge c$, the number $n-c$ ahead of it in the queue is geometric: $P(n-c=k\mid N\ge c)=(1-\rho)\rho^k$. While all servers are busy, departures occur at rate $c\mu$ (the minimum of $c$ independent exponential clocks), so the newcomer waits for $n-c+1$ independent $\operatorname{Exp}(c\mu)$ times. As in Theorem 9.30(3), a geometric number (on $\{1,2,\dots\}$, parameter $1-\rho$) of iid $\operatorname{Exp}(c\mu)$ times is $\operatorname{Exp}(c\mu(1-\rho))=\operatorname{Exp}(c\mu-\lambda)$. ∎

For $c=2$ the formulas collapse to closed forms worth remembering: $\pi_0=\frac{1-\rho}{1+\rho}$, $C=\frac{2\rho^2}{1+\rho}$, $L_q=\frac{2\rho^3}{1-\rho^2}$, $L=\frac{2\rho}{1-\rho^2}$ (Exercise III.2).

✏️ Example 4 — Two clerks: separate queues, one queue, or one fast clerk?
A post office has two clerks, each serving at rate $\mu=5$ customers per hour (exponential), and customers arrive at rate $8$ per hour in total. Compare: (i) two separate M/M/1 queues, each receiving half the customers; (ii) a single queue feeding both clerks (M/M/2); (iii) one clerk working twice as fast ($\mu=10$). (a) Find $W_q$ and $W$ in each case. (b) Prove that for every $\rho\lt1$ the single queue (ii) has a smaller $W_q$ than the separate queues (i), by the factor $\frac{\rho}{1+\rho}$.
(i) Separate Each clerk is an M/M/1 queue with $\lambda=4$, $\mu=5$, $\rho=0.8$ (independent thinning of a Poisson process gives Poisson streams, §3.3): $W_q=\frac{0.8}{5-4}=0.8$ h $=48$ min, $W=1$ h.
(ii) Pooled M/M/2 with $a=1.6$, $\rho=0.8$: $\pi_0=\left[1+1.6+\frac{1.6^2}{2\cdot0.2}\right]^{-1}=\frac19$, $C=\frac19\cdot\frac{1.28}{0.2}=0.711$, $L_q=0.711\cdot4=2.844$, $W_q=\frac{2.844}8=0.356$ h $\approx21.3$ min, $W=W_q+0.2$ h $\approx33.3$ min.
(iii) Fast M/M/1 with $\lambda=8$, $\mu=10$ (Example 2): $W_q=24$ min, $W=30$ min.
Comparison Pooling cuts the queueing time from $48$ to $21$ minutes: with separate queues one clerk may sit idle while the other has a queue. The fast clerk gives the smallest time in the system ($30$ against $33$ min), because each service is half as long, but a larger wait before service ($24$ against $21$ min). Which design is "best" depends on whether waiting or total time matters.
(b) Proof For $c=2$, $\pi_0=\frac{1-\rho}{1+\rho}$ and $L_q=\frac{2\rho^3}{1-\rho^2}$ (Exercise III.2), so with $\lambda=2\rho\mu$, $W_q^{\text{(ii)}}=\frac{L_q}{\lambda}=\frac{\rho^2}{\mu(1-\rho^2)}$. Each separate queue has arrival rate $\rho\mu$ and $W_q^{\text{(i)}}=\frac{\rho}{\mu(1-\rho)}$. The ratio is $\frac{\rho^2(1-\rho)}{\rho(1-\rho^2)}=\frac{\rho}{1+\rho}\lt\frac12$. At $\rho=0.8$ it is $\frac49$, matching $21.3/48$.

With a finite waiting room, at most $K\ge c$ customers can be present: the M/M/c/K queue. The extreme case $K=c$, with no waiting room at all, is the Erlang loss system M/M/c/c — telephone lines, hospital beds, parking spaces.

📐 Theorem 9.33 — M/M/c/K and the Erlang B formula
  1. For every $\lambda,\mu\gt0$ the M/M/c/K queue ($c\le K$) has the steady state given by the formulas of Theorem 9.32 restricted to $0\le n\le K$ and renormalised: $$\pi_0=\left[\sum_{n=0}^{c-1}\frac{a^n}{n!}+\frac{a^c}{c!}\sum_{j=0}^{K-c}\rho^j\right]^{-1}.$$ The blocking probability is $\pi_K$, $\lambda_{\text{eff}}=\lambda(1-\pi_K)$, the mean number of busy servers is $\lambda_{\text{eff}}/\mu$, $L_q=\sum_{n=c}^K(n-c)\pi_n$, $L=L_q+\lambda_{\text{eff}}/\mu$, $W=L/\lambda_{\text{eff}}$.
  2. (Erlang B formula) For M/M/c/c the steady state is the Poisson law truncated to $\{0,\dots,c\}$, $\pi_n=\dfrac{a^n/n!}{\sum_{k=0}^ca^k/k!}$, and the fraction of arrivals lost is $$B(c,a)=\frac{a^c/c!}{\sum_{k=0}^ca^k/k!},\qquad B(0,a)=1,\quad B(c,a)=\frac{aB(c-1,a)}{c+aB(c-1,a)} .$$
  3. The two Erlang formulas are related by $C(c,a)=\dfrac{B(c,a)}{1-\rho\,(1-B(c,a))}$ for $\rho\lt1$.

Proof. (1) A finite irreducible birth–death process always has a unique stationary law (§3.3), with the same $\theta_n$ as before, now for $n\le K$. The blocking probability is $\pi_K$ by PASTA; Little's law applied to the servers, which every admitted customer passes through for a mean time $1/\mu$, gives the mean number of busy servers $\lambda_{\text{eff}}/\mu$, and then $L=L_q+\lambda_{\text{eff}}/\mu$. (2) For $K=c$ the geometric part is absent. For the recursion let $S_c=\sum_{k\le c}a^k/k!$. Then $$\frac1{B(c,a)}=\frac{c!\,S_c}{a^c}=\frac{c!\,(S_{c-1}+a^c/c!)}{a^c}=1+\frac ca\cdot\frac{(c-1)!\,S_{c-1}}{a^{c-1}}=1+\frac{c}{aB(c-1,a)} ,$$ which rearranges to the stated recursion. (3) Put $T=\sum_{n\lt c}a^n/n!=S_c-a^c/c!$ and $x=a^c/c!$. Then $B=x/(T+x)$ and $C=\frac{x/(1-\rho)}{T+x/(1-\rho)}=\frac{x}{(1-\rho)T+x}$. Substituting $T=x(1-B)/B$ gives $C=\frac{B}{(1-\rho)(1-B)+B}=\frac{B}{1-\rho(1-B)}$. ∎

A remarkable fact, which we state without proof, is the insensitivity of the Erlang B formula: for the loss system M/G/c/c with any service distribution of mean $1/\mu$ the blocking probability is still $B(c,a)$. The Erlang C formula has no such property.

✏️ Example 5 — How many intensive-care beds?
A hospital's intensive-care unit admits emergency patients as a Poisson process of rate $1.5$ per day; stays are exponential with mean $2$ days. A patient who finds all beds occupied is transferred elsewhere. (a) With $4$ beds, what fraction of patients is transferred, and how many beds are occupied on average? (b) How many beds are needed to transfer fewer than $5\%$ of patients? (c) Suppose instead that, with $4$ beds, up to $2$ patients can be held in a recovery area until a bed frees up (M/M/4/6). Find the fraction transferred, the fraction of admitted patients who must wait, and their mean wait.
(a) $a=\lambda/\mu=1.5\cdot2=3$ erlangs. With the recursion: $B(1,3)=\frac34$, $B(2,3)=\frac{2.25}{4.25}=0.5294$, $B(3,3)=\frac{1.588}{4.588}=0.3462$, $B(4,3)=\frac{1.0385}{5.0385}=0.2061$. So $20.6\%$ of patients are transferred. Mean occupied beds $=a(1-B)=3\cdot0.794=2.38$ (Little's law on the beds).
(b) Continue: $B(5,3)=0.1101$, $B(6,3)=0.0522$, $B(7,3)=0.0219$. Six beds still lose $5.2\%$; seven beds are needed ($2.2\%$). Note how slowly the loss falls: going from $4$ to $7$ beds raises capacity by $75\%$ but the mean occupancy only from $2.38$ to $2.93$ beds.
(c) M/M/4/6: $\theta_n=\frac{3^n}{n!}$ for $n\le4$ and then $\times\frac34$ per step: $\theta=(1,3,4.5,4.5,3.375,2.531,1.898)$, sum $20.80$, so $\pi=(0.048,\ 0.144,\ 0.216,\ 0.216,$ $0.162,\ 0.122,\ 0.091)$. Transferred: $\pi_6=9.1\%$ (down from $20.6\%$). Admitted patients who wait: they find $4$ or $5$ present, probability $\frac{\pi_4+\pi_5}{1-\pi_6}=0.312$. $L_q=\pi_5+2\pi_6=0.304$, $\lambda_{\text{eff}}=1.5(1-0.091)=1.363$ per day, so $W_q=\frac{0.304}{1.363}=0.223$ day $\approx5.4$ hours averaged over all admitted patients.

The M/G/1 Queue and the Pollaczek–Khinchine Formula

When service times are not exponential, the number in the system is no longer a Markov process in continuous time: the future depends on how long the current service has already run. Two ideas rescue the analysis: look at the system only at departure epochs, where it is Markov, and use PASTA and Theorem 9.29(2) to transfer the answer to arbitrary times. Let customers arrive as a Poisson process of rate $\lambda$, and let service times $S_1,S_2,\dots$ be iid with mean $E[S]=1/\mu$, variance $\sigma^2$ and $E[S^2]=\sigma^2+1/\mu^2\lt\infty$, independent of the arrivals. Put $\rho=\lambda E[S]$.

📐 Theorem 9.34 — Pollaczek–Khinchine mean-value formula (M/G/1)
If $\rho=\lambda E[S]\lt1$, the M/G/1 queue has a steady state in which the server is busy a fraction $\rho$ of the time and $$W_q=\frac{\lambda E[S^2]}{2(1-\rho)},\qquad L_q=\frac{\lambda^2E[S^2]}{2(1-\rho)}=\frac{\lambda^2\sigma^2+\rho^2}{2(1-\rho)},$$ $$W=W_q+E[S],\qquad L=L_q+\rho .$$ In terms of the squared coefficient of variation $c_s^2=\sigma^2\mu^2$ of the service time, $W_q=\dfrac{1+c_s^2}{2}\cdot\dfrac{\rho}{\mu(1-\rho)}$: the M/M/1 value multiplied by $\frac{1+c_s^2}2$.

Proof. Let $X_n$ be the number of customers left behind by the $n$-th departure, and $A_{n+1}$ the number of arrivals during the $(n+1)$-th service. If $X_n\ge1$, the next service starts at once and $X_{n+1}=X_n-1+A_{n+1}$; if $X_n=0$, the server waits for the next arrival, serves it, and $X_{n+1}=A_{n+1}$. With $U_n=\mathbf 1\{X_n\gt0\}$, $$X_{n+1}=X_n-U_n+A_{n+1}.$$ The $A_n$ are iid and $A_{n+1}$ is independent of $X_n$ (Poisson arrivals during a service that has not yet started). Given $S=s$, $A\sim\operatorname{Poi}(\lambda s)$, so by the laws of total expectation and variance (§1.4), $E[A]=\lambda E[S]=\rho$ and $\operatorname{Var}(A)=\lambda E[S]+\lambda^2\operatorname{Var}(S)$, hence $E[A^2]=\rho+\lambda^2E[S^2]$.

The departure chain $(X_n)$ is an irreducible aperiodic Markov chain on $\{0,1,\dots\}$; we accept that for $\rho\lt1$ it is positive recurrent with stationary law $\pi^{d}$ having a finite mean (this needs $E[S^2]\lt\infty$). Let $X\sim\pi^{d}$, $U=\mathbf 1\{X\gt0\}$ and $A$ independent of $X$; then $X-U+A$ has the same law as $X$. Taking expectations, $E[U]=E[A]=\rho$: the probability that a departure leaves the system empty is $1-\rho$. Squaring, and using $U^2=U$, $XU=X$, $E[XA]=\rho E[X]$, $E[UA]=\rho^2$: $$0=E[U]+E[A^2]-2E[X]+2\rho E[X]-2\rho^2 ,$$ so $2(1-\rho)E[X]=2\rho-2\rho^2+\lambda^2E[S^2]$, that is $$E[X]=\rho+\frac{\lambda^2E[S^2]}{2(1-\rho)} .$$ By Theorem 9.29(2) departures leave behind the same distribution that arrivals find, and by PASTA arrivals find the time-average distribution; so $L=E[X]$. Little's law on the server gives the mean number in service $\lambda E[S]=\rho$, the busy fraction; hence $L_q=L-\rho$, $W_q=L_q/\lambda$ and $W=W_q+E[S]$. Finally $\lambda^2E[S^2]=\lambda^2\sigma^2+\rho^2$ and $\lambda E[S^2]=\frac{\rho}{\mu}(1+c_s^2)$. ∎

Why the variance matters. An arriving customer must wait for the customers in the queue ($L_q$ of them by PASTA, each needing $E[S]$ on average) and for the residual service of the customer being served, if any. The residual has mean $\frac{E[S^2]}{2E[S]}$, not $\frac{E[S]}2$: a random time is more likely to fall in a long service than in a short one (the inspection paradox of §3.3). So $W_q=L_qE[S]+\rho\frac{E[S^2]}{2E[S]}=\rho W_q+\frac{\lambda E[S^2]}2$, which is the P–K formula again. Two queues with the same $\lambda$ and the same mean service time can therefore have very different waits.

service time$c_s^2$$W_q$ (with $\rho=\lambda/\mu$)$L_q$
exponential (M/M/1)$1$$\dfrac{\rho}{\mu(1-\rho)}$$\dfrac{\rho^2}{1-\rho}$
deterministic (M/D/1)$0$$\dfrac{\rho}{2\mu(1-\rho)}$$\dfrac{\rho^2}{2(1-\rho)}$
Erlang-$k$ (M/$E_k$/1)$\frac1k$$\dfrac{k+1}{2k}\cdot\dfrac{\rho}{\mu(1-\rho)}$$\dfrac{k+1}{2k}\cdot\dfrac{\rho^2}{1-\rho}$
uniform on $(0,2/\mu)$$\frac13$$\dfrac23\cdot\dfrac{\rho}{\mu(1-\rho)}$$\dfrac23\cdot\dfrac{\rho^2}{1-\rho}$
📐 Theorem 9.35 — Pollaczek–Khinchine transform formula (stated)
Let $S^*(s)=E[e^{-sS}]$ be the Laplace transform of the service time. If $\rho\lt1$, the steady-state number $N$ in an M/G/1 system has probability generating function $$E\left[z^N\right]=\frac{(1-\rho)(1-z)\,S^*(\lambda(1-z))}{S^*(\lambda(1-z))-z},\qquad |z|\le1 .$$

Sketch. In the recursion $X'=X-U+A$, $z^{X'}=z^{X-U}z^{A}$ with $A$ independent of $X$, and $E[z^A]=E[e^{-\lambda S(1-z)}]=S^*(\lambda(1-z))=:K(z)$ (the pgf of $\operatorname{Poi}(\lambda s)$ is $e^{-\lambda s(1-z)}$). Writing $\Pi(z)=E[z^X]$ and splitting on $X=0$: $\Pi(z)=K(z)\left[\pi^d_0+\frac{\Pi(z)-\pi^d_0}{z}\right]$. Solving for $\Pi$ with $\pi_0^d=1-\rho$ gives the formula, and $N$ has the same law as $X$ by Theorem 9.29. For exponential service $S^*(s)=\frac{\mu}{\mu+s}$, $K(z)=\frac{1}{1+\rho-\rho z}$, and the formula reduces to $\frac{1-\rho}{1-\rho z}$: the geometric law of Theorem 9.30. Differentiating at $z=1$ recovers Theorem 9.34. ∎

✏️ Example 6 — One printer, four kinds of jobs
Print jobs arrive at a shared printer as a Poisson process of rate $20$ per hour, and the mean printing time is $2.4$ minutes. Find $W_q$, $L_q$ and $W$ if printing times are (a) exponential; (b) constant; (c) Erlang-2; (d) hyperexponential with squared coefficient of variation $4$ (mostly short jobs with occasional very long ones). Comment.
Set-up $\lambda=20$ per hour, $E[S]=0.04$ h, $\rho=0.8$, $E[S^2]=(1+c_s^2)\,E[S]^2=(1+c_s^2)\cdot0.0016$ h². P–K: $W_q=\frac{20\,E[S^2]}{2\cdot0.2}=50\,E[S^2]$ hours.
(a) M/M/1 $E[S^2]=0.0032$: $W_q=0.16$ h $=9.6$ min, $L_q=\lambda W_q=3.2$, $W=12$ min.
(b) M/D/1 $E[S^2]=0.0016$: $W_q=4.8$ min, $L_q=1.6$, $W=7.2$ min. Exactly half the M/M/1 queue, but $W$ is not halved, because the $2.4$ minutes of printing are unchanged.
(c) M/E₂/1 $c_s^2=\frac12$, $E[S^2]=0.0024$: $W_q=7.2$ min, $L_q=2.4$, $W=9.6$ min.
(d) Hyperexponential $c_s^2=4$, $E[S^2]=0.008$: $W_q=24$ min, $L_q=8$, $W=26.4$ min.
Comment Same arrivals, same mean job, same utilisation — and mean waits from $4.8$ to $24$ minutes, in proportion to $1+c_s^2$. A policy that splits off the rare huge jobs (to another printer, or to the night) reduces $c_s^2$ and can cut the waiting dramatically without buying capacity.
Interactive 2 — M/G/1: The Pollaczek–Khinchine Curves and the Workload

All five service distributions have mean $E[S]=1$; arrivals are Poisson with rate $\lambda=\rho$. Left: the P–K curves $W_q=\rho E[S^2]/(2(1-\rho))$ for the five distributions (the selected one is thick), with the simulated mean wait at the current $\rho$ (red dot, from Lindley's recursion $W_{n+1}=\max(0,W_n+S_n-A_{n+1})$) converging to the theory (purple dot). Right: the unfinished work $V(t)$ in the system, which jumps by a service time at each arrival and drains at slope $-1$; by PASTA an arrival sees its time average, which equals $W_q$ (dashed). Compare the smooth sawtooth of deterministic service with the rare tall spikes of the hyperexponential.

—
E[S²]—
P–K W_q—
simulated W_q (customers)—
ratio to M/M/1—

Inventory Models: the Economic Order Quantity

A shop, a pharmacy or a factory store sells an item at a steady rate and reorders it from a supplier. Ordering often costs money each time (paperwork, transport, set-up), so large rare orders are cheap to place; but stock on the shelf ties up capital and space, so small frequent orders are cheap to hold. The EOQ model finds the balance.

📘 Definition 9.14 — The basic EOQ model
Demand occurs continuously at a known constant rate $D$ units per unit time. An order of $Q$ units costs a fixed ordering (set-up) cost $K$ plus $cQ$, and arrives instantly (or after a known constant lead time $\ell$). Holding stock costs $h$ per unit per unit time (often $h=ic$, with $i$ an annual carrying rate). In the basic model shortages are not allowed. The inventory level then falls linearly from $Q$ to $0$ over a cycle of length $T=Q/D$, when the next order arrives. In the model with planned shortages, unmet demand is backlogged at a cost $p$ per unit short per unit time and filled when the next order arrives; the stock then rises to a level $S\le Q$ at each delivery.
📐 Theorem 9.36 — The economic order quantity (Harris–Wilson formula)
In the basic EOQ model the long-run average cost per unit time of ordering $Q$ units each time is $$C(Q)=\frac{KD}{Q}+\frac{hQ}{2}+cD .$$ It is minimised by $$Q^*=\sqrt{\frac{2KD}{h}},\qquad\text{with}\qquad C(Q^*)-cD=\sqrt{2KDh},$$ cycle length $T^*=Q^*/D=\sqrt{2K/(Dh)}$ and $D/Q^*$ orders per unit time. At $Q^*$ the ordering and holding costs are equal, and for every $Q\gt0$ $$\frac{C(Q)-cD}{C(Q^*)-cD}=\frac12\left(\frac{Q}{Q^*}+\frac{Q^*}{Q}\right).$$ With lead time $\ell\lt T^*$, the order is placed when the stock falls to the reorder point $R=D\ell$.

Proof. Each cycle of length $T=Q/D$ costs $K+cQ$ for the order plus holding cost $h\int_0^T(Q-Dt)\,dt=h\frac{QT}{2}$ (the area of a triangle of height $Q$ and base $T$). Dividing by $T$ (the renewal-reward principle, or simply the periodicity of the inventory pattern) gives $\frac{KD}{Q}+cD+\frac{hQ}{2}$. By the AM–GM inequality, $\frac{KD}Q+\frac{hQ}2\ge2\sqrt{\frac{KD}{Q}\cdot\frac{hQ}{2}}=\sqrt{2KDh}$, with equality iff $\frac{KD}{Q}=\frac{hQ}2$, i.e. $Q=Q^*$. At $Q^*$ each of the two terms equals $\frac12\sqrt{2KDh}=\frac12C^*$, where $C^*=\sqrt{2KDh}$; so $\frac{KD}{Q}=\frac{C^*}2\cdot\frac{Q^*}{Q}$ and $\frac{hQ}{2}=\frac{C^*}{2}\cdot\frac{Q}{Q^*}$, which gives the ratio formula. Finally, demand during the lead time is $D\ell$, so an order placed when $D\ell$ units remain arrives exactly as the stock runs out. ∎

The ratio formula explains the popularity of the EOQ: the cost curve is very flat near its minimum. Ordering $25\%$ too much costs only $\frac12(1.25+0.8)-1=2.5\%$ extra, and an error of a factor $2$ in $K$ or $D$ changes $Q^*$ by a factor $\sqrt2$ and the cost by only $6\%$.

📐 Theorem 9.37 — EOQ with planned shortages
With backlogging at cost $p$ per unit per unit time, ordering $Q$ and raising the stock to $S$ at each delivery costs, per unit time (excluding $cD$), $$C(Q,S)=\frac{KD}{Q}+\frac{hS^2}{2Q}+\frac{p(Q-S)^2}{2Q} .$$ The optimum is $$Q^*=\sqrt{\frac{2KD}{h}}\sqrt{\frac{h+p}{p}},\qquad S^*=\sqrt{\frac{2KD}{h}}\sqrt{\frac{p}{h+p}},\qquad C^*=\sqrt{2KDh}\sqrt{\frac{p}{h+p}},$$ with maximum backlog $Q^*-S^*$. As $p\to\infty$ these tend to the basic EOQ.

Proof. In a cycle of length $Q/D$ the stock falls from $S$ to $0$ in time $S/D$ (holding area $\frac{S^2}{2D}$) and then the backlog grows to $Q-S$ in time $(Q-S)/D$ (shortage area $\frac{(Q-S)^2}{2D}$). Multiplying the areas by $h$ and $p$, adding $K$ and dividing by $Q/D$ gives $C(Q,S)$. For fixed $Q$, $C$ is a convex quadratic in $S$ with derivative $\frac{hS-p(Q-S)}{Q}$, which vanishes at $S=\frac{p}{h+p}Q$. There $hS^2+p(Q-S)^2=\frac{hp^2+ph^2}{(h+p)^2}Q^2=\frac{hp}{h+p}Q^2$, so $$C(Q)=\frac{KD}{Q}+\frac{h'Q}{2},\qquad h'=\frac{hp}{h+p} .$$ This is the basic model with $h$ replaced by $h'$: Theorem 9.36 gives $Q^*=\sqrt{2KD/h'}$, $C^*=\sqrt{2KDh'}$, and $S^*=\frac{p}{h+p}Q^*$, which are the stated formulas. ∎

Two more variants are common. If the order is produced at a finite rate $P\gt D$ instead of arriving at once (the economic production quantity), the stock peaks at $Q(1-D/P)$ and $Q^*=\sqrt{2KD/(h(1-D/P))}$ (Exercise IV.7). If the supplier offers quantity discounts, the purchase cost $cD$ is no longer a constant and must be included in the comparison:

🧭 Problem-solving strategy — all-units quantity discounts
The unit price is $c_1$ for $Q\lt q_1$, $c_2\lt c_1$ for $q_1\le Q\lt q_2$, and so on, with $h=ic_j$ at price $c_j$.
  1. For each price $c_j$ compute $Q_j=\sqrt{2KD/(ic_j)}$. If $Q_j$ lies in the range where $c_j$ applies, it is a candidate. If $Q_j$ is below that range, the best quantity at price $c_j$ is the lower break point $q_{j-1}$ (the cost is increasing beyond $Q_j$). If it is above the range, price $c_j$ can be ignored (a cheaper price does better).
  2. For each candidate compute the total cost $TC(Q)=c_jD+\frac{KD}{Q}+\frac{ic_jQ}{2}$.
  3. Choose the candidate with the smallest total cost.
✏️ Example 7 — A pharmacy's order policy
A pharmacy sells $2400$ boxes of a medicine a year at a steady rate. Each order costs $150$ rupees to place, a box costs $10$ rupees, and the annual carrying rate is $20\%$ of the price. (a) Find the EOQ, the number of orders per year, the cycle length, the annual ordering-plus-holding cost, and the reorder point for a lead time of $2$ weeks. (b) If shortages are allowed with backorders at $6$ rupees per box per year, find the optimal policy and its cost. (c) The supplier offers a price of $9.80$ rupees per box on orders of at least $1000$ boxes. Should the pharmacy accept (no shortages)?
(a) $D=2400$, $K=150$, $h=0.2\cdot10=2$ rupees per box per year. $Q^*=\sqrt{\frac{2\cdot150\cdot2400}{2}}=\sqrt{360000}=600$ boxes; $4$ orders a year, every $3$ months. Ordering cost $4\cdot150=600$ and holding cost $2\cdot\frac{600}2=600$ rupees: equal, as Theorem 9.36 says, with total $\sqrt{2KDh}=1200$ rupees a year. Reorder point $R=2400\cdot\frac2{52}\approx92$ boxes.
(b) $p=6$: $\sqrt{\frac{h+p}{p}}=\sqrt{\frac86}=1.1547$. $Q^*=600\cdot1.1547=693$ boxes, $S^*=600/1.1547=520$ boxes, maximum backlog $173$ boxes, and $C^*=1200/1.1547=1039$ rupees a year: allowing backorders saves about $161$ rupees a year.
(c) At $9.80$: $h=1.96$ and $Q_2=\sqrt{\frac{2\cdot150\cdot2400}{1.96}}=606$, below the break point $1000$; so the best order at that price is $Q=1000$. Total costs: at $10$ with $Q=600$: $24000+1200=25200$; at $9.80$ with $Q=1000$: $23520+\frac{150\cdot2400}{1000}+1.96\cdot\frac{1000}2$ $=23520+360+980=24860$.
Answer (c) Accept the discount and order $1000$ boxes ($2.4$ orders a year): the saving of $480$ on purchases outweighs the extra $140$ of ordering-plus-holding cost, for a net saving of $340$ rupees a year.
⚠️ Counterexamples and pitfalls
  1. "Stable" means $\rho\lt1$ strictly, with $\rho=\lambda/(c\mu)$. At $\rho=1$ the M/M/1 queue is null recurrent: no steady state although the server is "exactly loaded". For M/M/c the condition is $\lambda\lt c\mu$, not $\lambda\lt\mu$. Finite-capacity systems (M/M/1/K, M/M/c/K) have a steady state for every $\lambda$.
  2. Use $\lambda_{\text{eff}}$ in Little's law when customers are turned away. In Example 3, $W=L/\lambda$ would give $28.9$ instead of $32.2$ minutes.
  3. $L-L_q$ is the mean number in service, not $1$. It is $\rho$ for one server ($L_q\ne L-1$, because the server is sometimes idle), $a$ for M/M/c, $1-\pi_0$ for M/M/1/K and $\lambda_{\text{eff}}/\mu$ in general.
  4. The M/M/1 waiting time is not exponential. $W_q$ has an atom $1-\rho$ at $0$; only the sojourn time $W$ is $\operatorname{Exp}(\mu-\lambda)$. Conditionally on waiting, $W_q$ is $\operatorname{Exp}(\mu-\lambda)$ again.
  5. PASTA needs Poisson arrivals that do not anticipate the state. It fails for D/D/1 (Example 1(b)), for admitted customers of a loss system (they see $\pi_n/(1-\pi_K)$, $n\lt K$) and for finite-source models: in the machine-repair model of §3.3 a breaking machine never finds itself already broken, so arrivals see the distribution of the system with one machine fewer.
  6. Doubling both rates halves the times but not the numbers. $(\lambda,\mu)\to(2\lambda,2\mu)$ leaves $\rho$, $\pi$, $L$, $L_q$ unchanged and halves $W$, $W_q$.
  7. Queues grow nonlinearly in the load. $L=\rho/(1-\rho)$: going from $\rho=0.9$ to $0.95$ more than doubles $L$, from $9$ to $19$. Averaging the load over a day hides the peaks; the queue is driven by the peak load.
  8. No design is best for every measure. One fast server beats $c$ slow ones on $W$ but loses on $W_q$ (Example 4); a shared queue beats separate queues on both.
  9. The P–K formula depends on the second moment. M/D/1 halves $L_q$ and $W_q$ of M/M/1, not $L$ and $W$. A distribution with infinite variance (e.g. a Pareto law with shape $\alpha\in(1,2]$) gives $W_q=\infty$ even at $\rho=0.1$.
  10. Erlang B is insensitive, Erlang C is not. The loss probability of M/G/c/c depends on the service law only through its mean; the waiting probability of M/G/c does not obey the M/M/c formula.
  11. EOQ scales like a square root. Doubling demand multiplies $Q^*$ and the minimum cost by $\sqrt2$, not by $2$; the number of orders also grows by $\sqrt2$. With quantity discounts, compare total costs including the purchase cost $cD$, which the EOQ formula ignores.

Exercises

I
Kendall notation, Little's law and PASTA.
  • 1 Describe in words the systems M/D/2/10, $E_3$/M/1, M/M/$c$/$c$ and M/M/1/3/3, and say which of them can have a steady state for every arrival rate.
  • 2 A bank branch receives $30$ customers an hour and on average $4$ customers are inside. Find the mean time a customer spends in the branch. If service takes $3$ minutes on average, find $W_q$, $L_q$ and the mean number of busy tellers.
  • 3 Prove that in any stable single-server queue (G/G/1) with arrival rate $\lambda$ and mean service time $E[S]$, the long-run fraction of time the server is busy is $\lambda E[S]$.
  • 4 A car-wash with a small waiting area loses $10\%$ of its potential customers, who arrive at rate $6$ per hour; on average $1.8$ cars are on the premises. How long does an admitted car stay?
  • 5 In a D/D/1 queue customers arrive every $4$ minutes and need $3$ minutes each. Find the time-average distribution of the number in the system, the distribution seen by arrivals, and check Little's law.
  • 6 Show that in a stable M/M/1 queue the number of customers left behind by a departing customer has the distribution $(1-\rho)\rho^n$.
  • 7 A hospital has on average $450$ in-patients and admits $90$ patients a day. Find the mean length of stay. What assumptions does the computation need?
1 M/D/2/10: Poisson arrivals, constant service times, $2$ servers, at most $10$ customers in the system (others are lost). $E_3$/M/1: Erlang-3 inter-arrival times (more regular than Poisson), exponential service, one server, unlimited room. M/M/$c$/$c$: Poisson arrivals, exponential service, $c$ servers and no waiting room (Erlang's loss system). M/M/1/3/3: three machines that break down (each after an exponential time) and one repairman — the finite-source machine-repair model of §3.3. The finite-capacity systems (M/D/2/10, M/M/$c$/$c$, M/M/1/3/3) have a steady state for every arrival rate; $E_3$/M/1 needs $\lambda\lt\mu$.
2 $W=L/\lambda=\frac4{30}$ h $=8$ min. $W_q=8-3=5$ min, $L_q=30\cdot\frac5{60}=2.5$, and the mean number of busy tellers is $L-L_q=1.5=\lambda E[S]=30\cdot\frac1{20}$.
3 Apply Little's law (Theorem 9.28) to the "system" consisting of the server alone: customers enter it at rate $\lambda$ (in a stable queue every customer is eventually served) and stay for their service time, of mean $E[S]$. The number in this system is $1$ when the server is busy and $0$ otherwise, so its time average — the busy fraction — is $\lambda E[S]$.
4 $\lambda_{\text{eff}}=0.9\cdot6=5.4$ per hour and $W=L/\lambda_{\text{eff}}=\frac{1.8}{5.4}$ h $=20$ min (not $18$ min, which uses $\lambda=6$).
5 Each customer is alone for $3$ minutes of every $4$: the time-average distribution is $\pi_1=\frac34$, $\pi_0=\frac14$. Every arrival finds the system empty: the arrival distribution is $\delta_0$. Little: $\lambda=\frac14$ per minute, $W=3$, $L=\frac34=\lambda W$. Little's law holds; PASTA fails.
6 By Theorem 9.29(2) departures leave behind the distribution that arrivals find, and by PASTA arrivals find $\pi_n=(1-\rho)\rho^n$. (Directly: up-crossings of the level $n+\frac12$ occur at long-run rate $\lambda\pi_n$, down-crossings at rate $\mu\pi_{n+1}$, and these are equal — the cut equations.)
7 $W=L/\lambda=\frac{450}{90}=5$ days. Little's law needs only that the long-run averages exist (a stationary regime: no long-term trend in admissions or stays); no Poisson or exponential assumption is needed.
II
M/M/1 and M/M/1/K.
  • 1 An M/M/1 queue has $\lambda=12$ and $\mu=16$ per hour. Find $\rho$, $\pi_0$, $L$, $L_q$, $W$, $W_q$ and $P(N\gt3)$.
  • 2 For the queue of Exercise 1, find $P(W\gt30\text{ min})$, the time $w_{0.05}$ exceeded by $5\%$ of the customers, and $P(W_q\gt0)$.
  • 3 Show that $\operatorname{Var}(N)=\rho/(1-\rho)^2$ in M/M/1 and that $E[W_q\mid W_q\gt0]=W$. Evaluate $\operatorname{SD}(N)$ for the queue of Exercise 1.
  • 4 Prove that the mean busy period of an M/M/1 queue is $1/(\mu-\lambda)$, and find the mean number of customers served in a busy period.
  • 5 Customers arrive at rate $\lambda=10$ per hour. Serving at rate $\mu$ costs $10\mu$ rupees per hour, and each customer-hour in the system costs $40$ rupees. Find the service rate that minimises the total hourly cost.
  • 6 Find the steady state, the blocking probability, $L$ and $W$ of the M/M/1/3 queue with $\lambda=\mu=1$.
  • 7 Derive the formula for $L$ in Theorem 9.31(2) and check it against Example 3.
  • 8 Prove or disprove: for an M/M/1/K queue with $\rho=1.2$, enough waiting room can make the loss probability smaller than $10\%$.
Check lab: M/M/c/K calculator

Enter $\lambda$, $\mu$, the number of servers $c$ and the capacity $K$ (leave $K$ empty for an infinite waiting room). The lab computes the steady state from the cut equations and the measures of Theorems 9.30–9.33. It starts with Exercise II.1; try Example 3 ($3,4,1,4$), Example 5(c) ($1.5, 0.5, 4, 6$) or Exercise III.6.

π₀, P(wait or blocked)—
L, L_q—
W, W_q—
λ_eff, busy servers—
1 $\rho=0.75$, $\pi_0=0.25$, $L=3$, $L_q=2.25$, $W=\frac1{4}$ h $=15$ min, $W_q=0.1875$ h $=11.25$ min, $P(N\gt3)=P(N\ge4)=0.75^4=0.316$.
2 $P(W\gt\tfrac12)=e^{-4\cdot0.5}=e^{-2}=0.135$. $w_{0.05}=\frac{\log20}{4}=0.749$ h $\approx44.9$ min. $P(W_q\gt0)=\rho=0.75$.
3 $N$ is geometric on $\{0,1,\dots\}$ with success probability $1-\rho$, whose variance is $\frac{\rho}{(1-\rho)^2}$. By Theorem 9.30(3), $P(W_q\gt t\mid W_q\gt0)=\frac{\rho e^{-(\mu-\lambda)t}}{\rho}$, an $\operatorname{Exp}(\mu-\lambda)$ law with mean $\frac1{\mu-\lambda}=W$. For Exercise 1, $\operatorname{Var}(N)=12$ and $\operatorname{SD}(N)=3.46$, larger than the mean $3$.
4 Theorem 9.30(4): idle periods are $\operatorname{Exp}(\lambda)$, and the idle fraction $\frac{1/\lambda}{1/\lambda+E[B]}=1-\rho$ gives $E[B]=\frac1{\mu-\lambda}$. During a busy period the server works all the time, so the mean number served is $\mu E[B]=\frac{\mu}{\mu-\lambda}=\frac1{1-\rho}$ (Wald's identity makes this precise).
5 $f(\mu)=10\mu+40L=10\mu+\frac{400}{\mu-10}$ for $\mu\gt10$. $f'(\mu)=10-\frac{400}{(\mu-10)^2}=0$ gives $\mu-10=\sqrt{40}$, $\mu^*=16.32$ per hour, with $f(\mu^*)=163.2+63.2=226.5$ rupees per hour; $f''\gt0$, so it is the minimum. In general $\mu^*=\lambda+\sqrt{c_w\lambda/c_s}$.
6 $\rho=1$: $\pi_n=\frac14$ for $n=0,1,2,3$. Blocking $\frac14$, $\lambda_{\text{eff}}=0.75$, $L=\frac32$, $W=\frac{1.5}{0.75}=2$; check: $\mu(1-\pi_0)=0.75$.
7 $\sum_{n=0}^Kn\rho^n=\rho\frac{d}{d\rho}\frac{1-\rho^{K+1}}{1-\rho}=\frac{\rho\left[1-(K+1)\rho^K+K\rho^{K+1}\right]}{(1-\rho)^2}$. Multiplying by $\frac{1-\rho}{1-\rho^{K+1}}$ and writing $1-(K+1)\rho^K+K\rho^{K+1}$ $=(1-\rho^{K+1})-(K+1)\rho^K(1-\rho)$ gives $L=\frac{\rho}{1-\rho}-\frac{(K+1)\rho^{K+1}}{1-\rho^{K+1}}$. For $\rho=0.75$, $K=4$: $3-\frac{5\cdot0.2373}{0.7627}=1.444$, as in Example 3.
8 False. By Theorem 9.31(3) the loss probability decreases to $1-\frac1{1.2}=\frac16\approx16.7\%$ and stays above it for every $K$: when arrivals outpace the server, at least the excess $\lambda-\mu$ must be lost, a fraction $1-\frac1\rho$.
III
M/M/c, M/M/c/K and the Erlang formulas.
  • 1 An M/M/3 queue has $\lambda=6$ and $\mu=3$ per hour. Find $\pi_0$, the probability of waiting, $L_q$, $W_q$, $L$ and $W$.
  • 2 For M/M/2 with $\rho=\lambda/(2\mu)\lt1$, prove $\pi_0=\frac{1-\rho}{1+\rho}$, $C=\frac{2\rho^2}{1+\rho}$, $L_q=\frac{2\rho^3}{1-\rho^2}$ and $L=\frac{2\rho}{1-\rho^2}$.
  • 3 Compute $B(c,2)$ for $c=1,\dots,5$ with the recursion. How many lines does an office offering $2$ erlangs of traffic need to lose fewer than $5\%$ of calls?
  • 4 A help line has $4$ agents; calls arrive at $24$ per hour and last $8$ minutes on average (exponential). Find the probability that a caller waits, the mean wait, and the mean number of callers on hold.
  • 5 At $\rho=\frac12$, compare one server of rate $2\mu$ with an M/M/2 queue of rate $\mu$ per server, for both $W_q$ and $W$.
  • 6 Find the steady state, blocking probability, $L$, $L_q$, $W$ and $W_q$ of the M/M/2/4 queue with $\lambda=3$, $\mu=2$, and check that $L-L_q=\lambda_{\text{eff}}/\mu$.
  • 7 Show that in the Erlang loss system the mean number of busy servers is $a(1-B(c,a))$, and deduce that $B(c,a)\ge1-c/a$.
  • 8 Prove that for fixed $\rho\in(0,1)$ the Erlang C probability $C(c,c\rho)$ tends to $0$ as $c\to\infty$ (large systems are efficient).
1 $a=2$, $\rho=\frac23$. $\pi_0=\left[1+2+2+\frac{8/6}{1/3}\right]^{-1}=\frac19$; $C=\frac19\cdot\frac43\cdot3=\frac49=0.444$; $L_q=\frac49\cdot2=\frac89=0.889$; $W_q=\frac{0.889}6=0.148$ h $\approx8.9$ min; $L=\frac89+2=2.889$; $W=W_q+\frac13=0.481$ h $\approx28.9$ min.
2 $a=2\rho$: $\pi_0^{-1}=1+2\rho+\frac{4\rho^2}{2(1-\rho)}=\frac{(1+2\rho)(1-\rho)+2\rho^2}{1-\rho}=\frac{1+\rho}{1-\rho}$. $C=\pi_0\frac{a^2}{2(1-\rho)}=\frac{1-\rho}{1+\rho}\cdot\frac{2\rho^2}{1-\rho}=\frac{2\rho^2}{1+\rho}$. $L_q=C\frac{\rho}{1-\rho}=\frac{2\rho^3}{(1+\rho)(1-\rho)}$ and $L=L_q+2\rho=\frac{2\rho^3+2\rho(1-\rho^2)}{1-\rho^2}=\frac{2\rho}{1-\rho^2}$.
3 $B(1,2)=\frac23$, $B(2,2)=\frac{4/3}{2+4/3}=0.4$, $B(3,2)=\frac{0.8}{3.8}=0.2105$, $B(4,2)=\frac{0.421}{4.421}=0.0952$, $B(5,2)=\frac{0.1905}{5.1905}=0.0367$. Five lines are needed.
4 $\mu=7.5$ per hour, $a=3.2$, $\rho=0.8$. Erlang C: $C(4,3.2)=0.596$ (from $B(4,3.2)=0.2282$ and Theorem 9.33(3)). $L_q=0.596\cdot4=2.39$ callers on hold, $W_q=\frac{2.39}{24}=0.0994$ h $\approx6.0$ min, $W\approx14.0$ min.
5 Here $\lambda=\mu$. Fast server: M/M/1 with rates $\mu$ and $2\mu$: $W=\frac1{2\mu-\mu}=\frac1\mu$, $W_q=W-\frac1{2\mu}=\frac1{2\mu}$. M/M/2: by Exercise 2 (and Example 4), $W_q=\frac{\rho^2}{\mu(1-\rho^2)}=\frac{1}{3\mu}$ and $W=\frac1{3\mu}+\frac1\mu=\frac4{3\mu}$. The fast server wins on $W$, the pair on $W_q$.
6 $a=1.5$, $\rho=0.75$: $\theta=(1,\ 1.5,\ 1.125,\ 0.844,\ 0.633)$, sum $5.102$, $\pi=(0.196,\ 0.294,\ 0.221,\ 0.165,\ 0.124)$. Blocking $12.4\%$, $\lambda_{\text{eff}}=2.628$. $L=1.727$, $L_q=\pi_3+2\pi_4=0.413$, $W=\frac{1.727}{2.628}=0.657$, $W_q=0.157$. Check: $L-L_q=1.314=\frac{2.628}{2}$.
7 Admitted calls arrive at rate $\lambda(1-B)$ and occupy a server for a mean time $1/\mu$; Little's law on the servers gives a mean of $a(1-B)$ busy servers. Since at most $c$ servers are busy, $a(1-B)\le c$, i.e. $B\ge1-\frac ca$ — a useful lower bound when $a\gt c$.
8 With $a=c\rho$ and $x=a^c/c!$, $C=\frac{x/(1-\rho)}{T+x/(1-\rho)}\le\frac{x}{(1-\rho)T}$, where $T=\sum_{n\lt c}a^n/n!$. Now $\frac{x}{T}=\frac{P(Y=c)}{P(Y\lt c)}$ for $Y\sim\operatorname{Poi}(c\rho)$. By the weak law of large numbers (a $\operatorname{Poi}(c\rho)$ variable is a sum of $c$ iid $\operatorname{Poi}(\rho)$), $P(Y\lt c)\to1$ because $\rho\lt1$; and $P(Y=c)\le P(Y\ge c)\to0$. Hence $C(c,c\rho)\to0$: at the same utilisation, a large pool almost never makes anyone wait.
IV
M/G/1 and inventory.
  • 1 Jobs arrive at a machine at rate $4$ per hour; processing times are uniform on $(0,20)$ minutes. Find $\rho$, $W_q$, $L_q$, $L$ and $W$.
  • 2 Show that the P–K formula gives the M/M/1 values for exponential service, and that for M/D/1 $L_q=\frac{\rho^2}{2(1-\rho)}$.
  • 3 Prove that among all service distributions with a given mean, constant service minimises $W_q$ in M/G/1.
  • 4 A counter serves two kinds of customers: $80\%$ need $1$ minute, $20\%$ need $11$ minutes. Customers arrive as a Poisson process of rate $0.2$ per minute. Find $W_q$ and compare it with an exponential service time of the same mean.
  • 5 Annual demand is $12000$ units, ordering cost $500$ rupees, holding cost $3$ rupees per unit per year. Find the EOQ, the number of orders per year and the minimum annual cost.
  • 6 In Exercise 5 the supplier ships only in lots of $2500$. By what percentage does the annual ordering-plus-holding cost rise?
  • 7 In Exercise 5 the item is produced in-house at a rate of $48000$ units a year instead of being delivered all at once. Derive the cost function and find the optimal production lot.
  • 8 In Exercise 5 the unit price is $15$ rupees (so $h=0.2\times$ price), with a price of $14.50$ for orders of at least $2500$ units. Find the best order quantity.
1 $E[S]=10$ min $=\frac16$ h, $E[S^2]=\frac{(1/3)^2}{3}=\frac1{27}$ h², $\rho=\frac46=\frac23$. $W_q=\frac{4\cdot\frac1{27}}{2\cdot\frac13}=\frac29$ h $\approx13.3$ min, $L_q=4\cdot\frac29=\frac89$, $L=\frac89+\frac23=\frac{14}9\approx1.56$, $W=\frac29+\frac16=\frac7{18}$ h $\approx23.3$ min.
2 Exponential: $E[S^2]=\frac2{\mu^2}$, so $W_q=\frac{2\lambda/\mu^2}{2(1-\rho)}=\frac{\rho}{\mu(1-\rho)}$ and $L_q=\lambda W_q=\frac{\rho^2}{1-\rho}$, as in Theorem 9.30. Deterministic: $E[S^2]=\frac1{\mu^2}$ and $L_q=\frac{\lambda^2/\mu^2}{2(1-\rho)}=\frac{\rho^2}{2(1-\rho)}$.
3 $W_q=\frac{\lambda E[S^2]}{2(1-\rho)}$ with $\lambda$ and $\rho=\lambda E[S]$ fixed is increasing in $E[S^2]=\operatorname{Var}(S)+E[S]^2\ge E[S]^2$, with equality iff $\operatorname{Var}(S)=0$, i.e. $S$ is constant.
4 $E[S]=0.8+2.2=3$ min, $E[S^2]=0.8\cdot1+0.2\cdot121=25$, $\rho=0.6$. $W_q=\frac{0.2\cdot25}{2\cdot0.4}=6.25$ min. Exponential with mean $3$: $E[S^2]=18$ and $W_q=4.5$ min. The mixture has $c_s^2=\frac{25-9}{9}=\frac{16}9\gt1$, so it waits longer.
5 $Q^*=\sqrt{\frac{2\cdot500\cdot12000}{3}}=2000$ units; $6$ orders a year; minimum cost $\sqrt{2\cdot500\cdot12000\cdot3}=6000$ rupees a year.
6 $\frac12\left(\frac{2500}{2000}+\frac{2000}{2500}\right)=\frac12(1.25+0.8)=1.025$: $2.5\%$ more, i.e. $6150$ rupees.
7 During production (time $Q/P$) the stock rises at rate $P-D$, reaching $Q(1-D/P)$, then falls at rate $D$: the average stock is $\frac Q2(1-D/P)$, and $C(Q)=\frac{KD}{Q}+\frac{h(1-D/P)Q}{2}$. This is the EOQ with $h$ replaced by $h(1-D/P)=3\cdot0.75=2.25$: $Q^*=\sqrt{\frac{2\cdot500\cdot12000}{2.25}}=2309$ units, cost $\sqrt{2\cdot500\cdot12000\cdot2.25}=5196$ rupees a year.
8 At $15$: $h=3$, $Q=2000$ is in range, total $180000+6000=186000$. At $14.50$: $h=2.9$, $\sqrt{2KD/h}=2034\lt2500$, so take $Q=2500$: total $174000+\frac{500\cdot12000}{2500}+2.9\cdot1250$ $=174000+2400+3625=180025$. Order $2500$ units, saving $5975$ rupees a year.
🎯 Exam corner CSIR Part BCSIR Part CGATE ST

E1. CSIR Part B GATE ST In an M/M/1 queue customers arrive at rate $5$ per hour and are served at rate $6$ per hour. The expected number of customers waiting in the queue (not in service) in steady state is (A) $5$; (B) $\frac{25}6$; (C) $\frac56$; (D) $1$.

Idea $L_q=\frac{\rho^2}{1-\rho}$ with $\rho=\frac56$.
Compute $L_q=\frac{25/36}{1/6}=\frac{25}6\approx4.17$. Option (A) is $L=\frac{\rho}{1-\rho}=5$; (C) is $\rho$, the mean number in service; (D) is the mean sojourn time $W=1$ hour.
Answer (B).

E2. CSIR Part B A single-server system has room for one customer in service and one waiting; arrivals finding both places taken are lost. Arrivals are Poisson and service times exponential, with the same rate $\lambda=\mu$. The long-run fraction of arriving customers that are lost is (A) $\frac14$; (B) $\frac13$; (C) $\frac12$; (D) $\frac23$.

Idea M/M/1/2 with $\rho=1$; the steady state is uniform on $\{0,1,2\}$ (Theorem 9.31), and by PASTA the lost fraction is $\pi_2$.
Compute $\pi_2=\frac13$. (Option (D), $1-\pi_0$, is the fraction of time the server is busy.)
Answer (B).

E3. CSIR Part B In the basic EOQ model, if the annual demand becomes four times as large while all costs stay the same, the economic order quantity (A) is unchanged; (B) doubles; (C) becomes four times as large; (D) is halved.

Idea $Q^*=\sqrt{2KD/h}$ is proportional to $\sqrt D$.
Compute $\sqrt{4}=2$: the EOQ doubles, and so do the number of orders per year ($D/Q^*\propto\sqrt D$) and the minimum cost $\sqrt{2KDh}$.
Answer (B).

E4. CSIR Part C Consider a stable M/M/1 queue with arrival rate $\lambda$, service rate $\mu$ and FCFS discipline, and let $\rho=\lambda/\mu$. Which of the following are true? (One or more options may be correct.) (A) The steady-state number in the system is geometric with $P(N=n)=(1-\rho)\rho^n$. (B) The sojourn time of a customer is exponential with rate $\mu-\lambda$. (C) The waiting time before service is exponential with rate $\mu-\lambda$. (D) $L=\lambda W_q$.

(A) True Theorem 9.30(1).
(B) True Theorem 9.30(3): a geometric number of $\operatorname{Exp}(\mu)$ phases.
(C) False $P(W_q=0)=1-\rho\gt0$: the law has an atom at $0$, so it is not exponential (only its conditional law given $W_q\gt0$ is).
(D) False Little's law gives $L=\lambda W$ and $L_q=\lambda W_q$; $\lambda W_q=\frac{\rho^2}{1-\rho}\ne\frac{\rho}{1-\rho}=L$.
Answer (A) and (B).

E5. CSIR Part C Which of the following statements about Markovian queues are true? (A) Little's law $L=\lambda W$ holds for an M/M/1 queue under any service discipline that serves one customer at a time and never idles when customers are present (FCFS, LCFS, random order). (B) The M/M/$c$ queue has a steady state if and only if $\lambda\lt c\mu$. (C) The M/M/$c$/$K$ queue has a steady state only if $\lambda\lt c\mu$. (D) In the M/M/1/K queue the rate at which customers enter the system is $\lambda(1-\pi_0)$.

(A) True Little's law needs no assumption on the order of service (Theorem 9.28). Moreover the number in the system, hence $L$, is the same birth–death process for every such discipline, so even $W=L/\lambda$ is the same; only the distribution of the sojourn time changes.
(B) True Theorem 9.32: the tail $\sum\theta_n$ converges iff $\rho=\lambda/(c\mu)\lt1$.
(C) False A finite irreducible chain always has a steady state (Theorem 9.33(1)); Example 3(b) has $\rho=1.5$.
(D) False Customers enter at rate $\lambda(1-\pi_K)$ (those not blocked), which also equals $\mu(1-\pi_0)$; $\lambda(1-\pi_0)$ is neither in general.
Answer (A) and (B).

E6. CSIR Part C GATE ST In an M/G/1 queue with arrival rate $\lambda$, service time $S$ with $E[S^2]\lt\infty$ and $\rho=\lambda E[S]\lt1$, which of the following are true? (A) $W_q=\frac{\lambda E[S^2]}{2(1-\rho)}$. (B) For the same $\lambda$ and the same mean service time, the mean queue length $L_q$ of M/D/1 is half that of M/M/1. (C) Increasing the variance of $S$ while keeping its mean fixed increases $L$. (D) The long-run fraction of time the server is idle depends on the variance of $S$.

(A) True The Pollaczek–Khinchine formula (Theorem 9.34).
(B) True $E[S^2]$ is $\frac1{\mu^2}$ for constant and $\frac2{\mu^2}$ for exponential service, and $L_q$ is proportional to $E[S^2]$.
(C) True $L=\rho+\frac{\lambda^2(\sigma^2+E[S]^2)}{2(1-\rho)}$ increases strictly in $\sigma^2$ when $\lambda$ and $E[S]$ are fixed.
(D) False The idle fraction is $1-\rho=1-\lambda E[S]$ (Little's law on the server), which involves only the mean.
Answer (A), (B) and (C).
🧑‍🏫 For the teacher

Suggested plan — 3 lectures × 60 min.

  1. Principles and M/M/1. Start with a queue students know (a canteen, a bank) and ask which numbers would describe it. Definition 9.13 and Kendall notation; Little's law (Theorem 9.28) with the picture of the area under $N(t)$, then the full proof; Example 1, including the D/D/1 counterexample as a class puzzle. PASTA (Theorem 9.29). Recall the birth–death steady state from §3.3 and derive Theorem 9.30 on the board, with the Laplace-transform proof of (3). Example 2. Project Interactive 1 (M/M/1) at $\lambda=0.5$, $0.8$, $0.95$ and $1.1$.
  2. Finite rooms and many servers. Theorem 9.31 and Example 3 (stress $\lambda_{\text{eff}}$ and the $\rho\gt1$ case). Theorem 9.32 with the derivation of $L_q$ and the waiting-time law; Example 4 as a debate ("which design would you choose?") before the computation. Theorem 9.33, the Erlang B recursion, Example 5. Interactive 1 with M/M/3 and M/M/2/6.
  3. M/G/1 and inventory. The residual-service heuristic first, then the embedded-chain proof of Theorem 9.34; the table of special cases; Example 6 and Interactive 2 (deterministic against hyperexponential at $\rho=0.8$). The EOQ (Theorem 9.36) with the AM–GM proof and the flatness formula; Theorem 9.37; the quantity-discount strategy and Example 7. Finish with E4–E6.

Discussion questions. (1) Why does a supermarket with one long snake queue feeding many tills serve customers faster than one queue per till, even with the same staff? (2) The P–K formula says variance hurts. Give two practical ways in which a hospital or a print shop could reduce the variance of its service times. (3) The EOQ assumes constant demand. Which of its conclusions survive when demand is random, and what new quantity (safety stock) must be added?

Misconceptions to watch for. Taking $\rho=\lambda/\mu$ in M/M/c; using $\lambda$ instead of $\lambda_{\text{eff}}$ with blocking; writing $L_q=L-1$; believing that $W_q$ is exponential in M/M/1; applying PASTA to deterministic or finite-source arrivals; thinking that M/D/1 halves the sojourn time; forgetting the purchase cost when comparing quantity discounts; expecting EOQ to scale linearly with demand.

Suggested homework. I(2, 3, 5, 7), II(1, 2, 4, 6, 8), III(1, 3, 4, 6, 8), IV(1, 3, 4, 5, 8); Exam corner E2, E4, E6.

🔬 Research–Teaching NexusResearch-tutored · optional, about 60 minutes

Research question. How many servers does a large call centre, emergency department or cloud-computing cluster need? Should staffing grow in proportion to the load, or more slowly?

Why it matters. Staffing is the largest cost of call centres and hospitals. Exercise III.8 shows that at a fixed utilisation the probability of waiting vanishes as the system grows, so large systems can be run hotter. The "square-root staffing rule" $c\approx a+\beta\sqrt a$ (Halfin and Whitt, 1981) captures exactly how much spare capacity is needed: the excess over the offered load grows only like $\sqrt a$. It is used to plan nurse rosters, call-centre shifts and server farms around the world.

What to do.

  1. Implement the Erlang B recursion and the conversion $C=B/(1-\rho(1-B))$ of Theorem 9.33; check $C(4,3.2)\approx0.596$ (Exercise III.4).
  2. For offered loads $a=10,50,100,500$ erlangs, compute $C(c,a)$ with (i) $c=\lceil a/0.8\rceil$ (fixed $80\%$ utilisation) and (ii) $c=\lceil a+\sqrt a\rceil$ (square-root staffing with $\beta=1$). Tabulate both.
  3. Compare the values in (ii) with the Halfin–Whitt limit $\left[1+\beta\Phi(\beta)/\varphi(\beta)\right]^{-1}$, where $\varphi$ is the standard normal density.
  4. Find, for each $a$, the smallest $c$ with $C(c,a)\le0.2$, and plot $(c-a)/\sqrt a$ against $a$. What do you observe?

Tools: Python (scipy.stats.norm for $\Phi$ and $\varphi$) or a spreadsheet.

Hand in: The table of $C(c,a)$ for both rules, the plot, and a paragraph explaining why fixed-utilisation staffing becomes wasteful for large $a$ while square-root staffing keeps the service level roughly constant.

Going further. Read about the "quality and efficiency driven" (QED) regime and about abandonment (Erlang A), in which impatient callers hang up; and about why emergency departments, whose arrivals vary through the day, need time-varying staffing.

Instructor note: with fixed utilisation $0.8$ the waiting probabilities are about $0.285$, $0.051$, $0.0099$ and $4\times10^{-8}$ for $a=10,50,100,500$ ($c=13,63,125,625$) — the large systems are heavily overstaffed. With $c=\lceil a+\sqrt a\rceil$ ($c=14,58,110,523$) they are about $0.174$, $0.194$, $0.237$ and $0.218$, close to the Halfin–Whitt value $\left[1+\Phi(1)/\varphi(1)\right]^{-1}\approx0.223$ (the rounding up of $c$ causes the scatter). Students will find $(c-a)/\sqrt a$ settling near $1$ in step 4, which is the point of the exercise.

🧪 Self-check quiz

0/5 correct

Q1. Customers arrive at a system at rate $10$ per hour and spend on average $18$ minutes in it. The mean number in the system is

Q2. In a stable M/M/1 queue with traffic intensity $\rho$, the mean number in the system is

Q3. Which queue has a steady state for every arrival rate $\lambda\gt0$?

Q4. With the same arrival rate and the same mean service time, the mean number waiting in an M/D/1 queue compared with M/M/1 is

Q5. In the basic EOQ model with demand rate $D$, ordering cost $K$ and holding cost $h$, the optimal order quantity is