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
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$.
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.
- (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.
- 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.
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$.
- $\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.
- $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}$.
- 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$.
- A busy period (from the arrival of a customer to an empty system until the system is next empty) has mean $\dfrac1{\mu-\lambda}$.
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).
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$.
- 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)$.
- $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}}$.
- 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$. ∎
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.
- 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)}$.
- $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$.
- 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).
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.
- 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}}$.
- (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)} .$$
- 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.
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]$.
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}$ |
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. ∎
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.
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\%$.
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:
- 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).
- For each candidate compute the total cost $TC(Q)=c_jD+\frac{KD}{Q}+\frac{ic_jQ}{2}$.
- Choose the candidate with the smallest total cost.
- "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$.
- 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.
- $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.
- 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.
- 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.
- 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$.
- 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.
- 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.
- 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$.
- 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.
- 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
- 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 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\%$.
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.
- 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 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.
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$.
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$.
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.
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$.
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)$.
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$.
Suggested plan — 3 lectures × 60 min.
- 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$.
- 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.
- 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 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.
- 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).
- 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.
- 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.
- 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.
🧪 Self-check quiz
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