How unit 5 is examined
This unit covers queue characteristics, birth-death models, Kendall-Lee notation and the M/M/1 and M/M/C formulas; no topic was asked in the supplied papers, so learn the M/M/1 numerical first, then the notation and characteristics.
Queuing: Introduction to queuing theory, Queuing systems and their characteristics
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. <mark>Queuing theory is the mathematical study of waiting lines, used to find the level of service that balances the cost of providing service against the cost of making customers wait.</mark>
Key points.
- A queue forms whenever the demand for a service (arrivals) exceeds the capacity to serve at that moment, as at a bank counter, a petrol pump, a hospital or a computer print server.
- The input source (calling population) may be finite or infinite; an infinite source means one arrival does not change the chance of the next.
- The arrival pattern is described by the distribution of inter-arrival times; the usual assumption is Poisson arrivals with mean arrival rate $\lambda$ per unit time, so the inter-arrival time is exponential with mean $1/\lambda$.
- The service pattern is described by the distribution of service times; the usual assumption is exponential service with mean service rate $\mu$ per unit time, so the mean service time is $1/\mu$.
- The number of servers (channels) may be one or many, arranged in parallel (customers pick any free server) or in series (customers pass through stages one after another).
- The queue discipline is the rule for choosing the next customer: FIFO (first in first out), LIFO (last in first out), SIRO (service in random order) or priority service.
- The system capacity may be finite (customers are turned away when the waiting room is full) or infinite.
- Customer behaviour includes balking (refusing to join a long queue), reneging (leaving after waiting) and jockeying (switching to a shorter queue).
- The system is in steady state when its behaviour no longer depends on time; this needs the traffic intensity $\rho=\lambda/\mu<1$ for one server, otherwise the queue grows without bound.
Diagram.
<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-01" viewBox="0 0 492.8 80" width="492.8" height="80" role="img" aria-label="Single-channel queue. Src = calling population, Q = waiting line (queue), S = server (service facility), Out = departure. Arrival rate lambda, service rate mu."><style>#dsfig-u5-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-01 .t{fill:#16181D;font-weight:500}#dsfig-u5-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-01 .dot{fill:#16181D}#dsfig-u5-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-01 .ah{fill:#454C5A}#dsfig-u5-01 .ah.hi{fill:#2340B8}#dsfig-u5-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-01 .e{stroke:#B1B7C3}html.dark #dsfig-u5-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-01 .t{fill:#E6E8ED}html.dark #dsfig-u5-01 .t.inv{fill:#0F1115}html.dark #dsfig-u5-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-01 .dot{fill:#E6E8ED}html.dark #dsfig-u5-01 .ann{fill:#8FA3FF}html.dark #dsfig-u5-01 .lbl{fill:#858D9C}html.dark #dsfig-u5-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-01 .ah{fill:#B1B7C3}html.dark #dsfig-u5-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L156.6,40" marker-end="url(#ah3)"/><path class="e" d="M196.6,40 L294.2,40" marker-end="url(#ah3)"/><path class="e" d="M334.2,40 L431.8,40" marker-end="url(#ah3)"/><g class="wl"><rect x="81.6" y="31" width="54.3" height="18" rx="9"/><text class="t" x="108.8" y="40" dy=".35em" text-anchor="middle">lambda</text></g><g class="wl"><rect x="370.8" y="31" width="26.4" height="18" rx="9"/><text class="t" x="384" y="40" dy=".35em" text-anchor="middle">mu</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">Src</text><circle class="n" cx="177.6" cy="40" r="18"/><text class="t" x="177.6" y="40" dy=".35em" text-anchor="middle">Q</text><circle class="n" cx="315.2" cy="40" r="18"/><text class="t" x="315.2" y="40" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="452.8" cy="40" r="18"/><text class="t" x="452.8" y="40" dy=".35em" text-anchor="middle">Out</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Single-channel queue. Src = calling population, Q = waiting line (queue), S = server (service facility), Out = departure. Arrival rate lambda, service rate mu.</figcaption></figure>
Measures of performance. $L_s$ = expected number in the system, $L_q$ = expected number in the queue, $W_s$ = expected time in the system, $W_q$ = expected waiting time in the queue, $\rho$ = traffic intensity (server utilisation). Little's law connects them: $L_s=\lambda W_s$ and $L_q=\lambda W_q$.
Answer frame. Open with the definition of queuing theory; draw the single-channel diagram; then list the six components (source, arrival pattern, service pattern, servers, discipline, capacity) with one sentence each; add balking, reneging and jockeying; close with the steady-state condition $\rho<1$.
Pure-birth and Pure-death models
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. <mark>A pure-birth model is a queue in which only arrivals occur (no departures), and a pure-death model is a queue in which only departures occur (no arrivals); both are special cases of the birth-death process.</mark>
Key points.
- In the birth-death process "birth" means an arrival and "death" means a departure; the state $n$ is the number of customers in the system.
- In a pure-birth model the arrival rate is constant $\lambda$ and the number of arrivals in time $t$ follows the Poisson law.
- Pure-birth probability of exactly $n$ arrivals in time $t$: $P_n(t)=\dfrac{(\lambda t)^n e^{-\lambda t}}{n!}$, $n=0,1,2,\dots$, with mean $\lambda t$.
- The time between two successive arrivals in a pure-birth model is exponential with mean $1/\lambda$, and it is memoryless.
- In a pure-death model the system starts with $N$ customers and service completes at rate $\mu$; there are no new arrivals, so the count only falls.
- Pure-death probability: $P_n(t)=\dfrac{(\mu t)^{N-n}e^{-\mu t}}{(N-n)!}$ for $n=1,2,\dots,N$, and $P_0(t)=1-\sum_{n=1}^{N}P_n(t)$.
- Example (pure birth): if $\lambda=3$ per hour, the probability of no arrival in 30 minutes is $P_0(0.5)=e^{-1.5}=0.2231$.
- Example (pure death): $N=3$, $\mu=2$ per hour, then $P_3(t)=e^{-2t}$, so after 1 hour $P_3=e^{-2}=0.1353$ (nobody served yet).
Answer frame. Open with the definition and the meaning of birth and death; state the pure-birth Poisson formula and the exponential inter-arrival time; state the pure-death formula with the initial $N$; work one small numerical from points 7-8; close by noting that combining both gives the M/M/1 birth-death model.
Kendall & Lee's notation of Queuing
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. <mark>Kendall-Lee notation describes a queue by six symbols $(a/b/c):(d/e/f)$, where a is the arrival distribution, b the service-time distribution, c the number of parallel servers, d the queue discipline, e the maximum number allowed in the system and f the size of the calling population.</mark>
Key points.
- Kendall's original notation had three symbols a/b/c; Lee extended it with d, e and f to include discipline, capacity and source size.
- Symbol M means Markovian, that is Poisson arrivals or exponential service, D means deterministic (constant) and $E_k$ means Erlang with $k$ phases.
- Symbol G means a general distribution, and GI means general independent inter-arrival times.
- Symbol c is the number of servers, so M/M/1 has one server and M/M/C has C parallel servers.
- Symbol d takes values FIFO, LIFO, SIRO, PR (priority) or GD (general discipline).
- Symbols e and f default to infinity, so $(M/M/1):(GD/\infty/\infty)$ is normally written just M/M/1.
- Example: $(M/M/3):(FIFO/10/\infty)$ means Poisson arrivals, exponential service, 3 servers, first-in-first-out, at most 10 customers in the system, infinite source.
- Example: M/D/1 means Poisson arrivals, constant service time and one server.
| Position | Symbol | Meaning | Typical values |
|---|---|---|---|
| a | arrival | inter-arrival distribution | M, D, G |
| b | service | service-time distribution | M, D, $E_k$, G |
| c | servers | number of parallel servers | 1, 2, C |
| d | discipline | order of service | FIFO, LIFO, SIRO |
| e | capacity | maximum in the system | N or $\infty$ |
| f | source | calling population size | finite or $\infty$ |
Answer frame. Open with the six-symbol form $(a/b/c):(d/e/f)$; give the table of what each position means; explain M, D, G; close with the M/M/1 and $(M/M/3):(FIFO/10/\infty)$ examples.
Empirical queuing models: Numerical on M/M/1 and M/M/C
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. ==The M/M/1 model has Poisson arrivals at rate $\lambda$, exponential service at rate $\mu$, one server, FIFO discipline and infinite capacity and source; it reaches steady state only if $\rho=\lambda/\mu<1$.==
Key points.
- The M/M/1 model is a birth-death process with constant arrival rate $\lambda$ and constant service rate $\mu$ in every state $n\ge 1$.
- The M/M/C model is the same with C identical parallel servers sharing one queue; the service rate in state $n$ is $n\mu$ for $n<C$ and $C\mu$ for $n\ge C$.
- Traffic intensity is $\rho=\lambda/\mu$ for M/M/1 and $\rho=\lambda/(C\mu)$ for M/M/C; steady state needs $\rho<1$.
- Always convert $\lambda$ and $\mu$ to the same time unit (per hour or per minute) before substituting.
- Find $L_s$ first, then get $L_q=L_s-\rho$ (M/M/1), and get the times by dividing by $\lambda$ (Little's law).
Formula (M/M/1).
$$P_0=1-\rho,\qquad P_n=\rho^n(1-\rho)$$
$$L_s=\frac{\lambda}{\mu-\lambda},\quad L_q=\frac{\lambda^2}{\mu(\mu-\lambda)},\quad W_s=\frac{1}{\mu-\lambda},\quad W_q=\frac{\lambda}{\mu(\mu-\lambda)}$$
Also $P(n\ge k)=\rho^k$, the mean waiting time of those who actually wait is $1/(\mu-\lambda)$, and the mean queue length of non-empty queues is $1/(1-\rho)$.
Formula (M/M/C). With $r=\lambda/\mu$ and $\rho=r/C<1$:
$$P_0=\left[\sum_{n=0}^{C-1}\frac{r^n}{n!}+\frac{r^C}{C!\,(1-\rho)}\right]^{-1}$$
$$L_q=\frac{r^C\,\rho}{C!\,(1-\rho)^2}\,P_0,\quad W_q=\frac{L_q}{\lambda},\quad W_s=W_q+\frac{1}{\mu},\quad L_s=L_q+r$$
Example 1 (M/M/1). Given: patients arrive at $\lambda=6$ per hour and the doctor serves $\mu=8$ per hour.
| Quantity | Working | Value |
|---|---|---|
| $\rho$ | 6/8 | 0.75 |
| $L_s$ | 6/(8-6) | 3 patients |
| $L_q$ | 36/(8 x 2) | 2.25 patients |
| $W_s$ | 1/(8-6) | 0.5 hr = 30 min |
| $W_q$ | 6/(8 x 2) | 0.375 hr = 22.5 min |
| $P_0$ | 1-0.75 | 0.25 |
Answer: $L_s=3$, $L_q=2.25$, $W_s=30$ min, $W_q=22.5$ min.
Example 2 (M/M/1). Given: $\lambda=8$/hr, $\mu=10$/hr. Then $\rho=0.8$, $L_s=8/2=4$, $L_q=64/20=3.2$, $W_s=1/2=0.5$ hr, $W_q=8/20=0.4$ hr, $P_0=0.2$, and $P(n\ge 3)=0.8^3=0.512$. Server idle 20% of the time; 51.2% of the time 3 or more are present.
Example 3 (M/M/C). Given: $\lambda=12$/hr, $\mu=5$/hr, $C=3$ servers. Then $r=2.4$, $\rho=0.8$.
- $P_0=\left[1+2.4+\dfrac{2.4^2}{2}+\dfrac{2.4^3}{6\times 0.2}\right]^{-1}=[1+2.4+2.88+11.52]^{-1}=\dfrac{1}{17.8}=0.0562$.
- $L_q=\dfrac{2.4^3\times 0.8}{6\times 0.04}\times 0.0562=46.08\times 0.0562=2.589$.
- $W_q=2.589/12=0.2157$ hr $=12.9$ min; $W_s=0.2157+0.2=0.4157$ hr; $L_s=2.589+2.4=4.989$.
Answer: $P_0=0.0562$, $L_q\approx 2.59$, $W_q\approx 12.9$ min, $W_s\approx 0.416$ hr, $L_s\approx 4.99$.
Answer frame. Open by writing the model (M/M/1 or M/M/C) and checking $\rho<1$; write "Given" with $\lambda$ and $\mu$ in the same unit; write the formulas, then substitute in the order $\rho$, $L_s$, $L_q$, $W_s$, $W_q$; for M/M/C compute $P_0$ first, then $L_q$, then the rest; close with a boxed answer and a one-line interpretation (for example, "the server is busy 75% of the time").
Pitfall: Mixing units (arrivals per hour with service per minute) and using $\rho\ge 1$ in the formulas both give wrong or meaningless answers; check units and $\rho<1$ first.
Last-minute revision
- Queuing theory balances the cost of service against the cost of waiting.
- Six components: source, arrival pattern, service pattern, servers, discipline, capacity.
- Balking = refuse to join, reneging = leave after joining, jockeying = switch queue.
- Arrivals are Poisson at rate $\lambda$; service is exponential at rate $\mu$; both are memoryless.
- Kendall-Lee notation is $(a/b/c):(d/e/f)$; M = Markovian, D = deterministic, G = general.
- Pure birth: $P_n(t)=(\lambda t)^n e^{-\lambda t}/n!$; pure death: $P_n(t)=(\mu t)^{N-n}e^{-\mu t}/(N-n)!$.
- M/M/1 needs $\rho=\lambda/\mu<1$; $P_0=1-\rho$; $P_n=\rho^n(1-\rho)$.
- $L_s=\lambda/(\mu-\lambda)$; $L_q=\lambda^2/[\mu(\mu-\lambda)]$.
- $W_s=1/(\mu-\lambda)$; $W_q=\lambda/[\mu(\mu-\lambda)]$.
- Little's law: $L=\lambda W$; and $W_s=W_q+1/\mu$, $L_s=L_q+\lambda/\mu$.
- M/M/C needs $\rho=\lambda/(C\mu)<1$; find $P_0$ then $L_q=\dfrac{r^C\rho}{C!(1-\rho)^2}P_0$.
- Check for M/M/1 with $\lambda=6,\mu=8$: $L_s=3$, $W_s=30$ min.
Memory hooks
- "Rho below one" keeps the queue from running away.
- M = Markov = memoryless, so exponential gaps and Poisson counts.
- "L over lambda gives W": every time is its length divided by the arrival rate.
- Ls minus Lq equals rho (one server); Ws minus Wq equals 1/mu.
- Kendall reads "arrive / serve / servers", Lee adds "discipline / capacity / source".
Coverage checklist
- Queuing: Introduction to queuing theory, Queuing systems and their characteristics: definition, components, behaviours, steady state, diagram; no past questions.
- Pure-birth and Pure-death models: both formulas with worked values; no past questions.
- Kendall & Lee’s notation of Queuing: six-symbol notation, table, examples; no past questions.
- empirical queuing models – Numerical on M/M/1 and M/M/C Queuing models: formulas, two M/M/1 and one M/M/C numericals; no past questions.