Queuing models
Queuing models: Poisson/exponential queues (M/M/1, M/M/c), finite-capacity and loss systems, M/G/1 (Pollaczek–Khinchine), Little’s law, steady-state measures (L, Lq, W, Wq), Erlang C and Erlang B, stability (ρ < 1), Kendall’s notation, and real-world effects (balking, reneging, priority).
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Queuing models help size servers, schedule manpower, and design buffers so customers, parts, or data don’t wait excessively or get lost. From bank counters and toll plazas to machine repair and call centers, they quantify the trade-off between service cost and delay, guiding quick, defensible decisions for exams and real plants.
Key ideas
- A queue is a system where random demands for service meet limited capacity. We study it under steady-state (long-run) behavior.
- Arrival process: Usually modeled as a Poisson process with rate λ (per second). Inter-arrival times are independent exponential random variables with mean 1/λ. Assumptions: stationarity, independent increments, memoryless inter-arrival times.
- Service process: Often exponential with rate μ (per second) per server. Service times are independent of arrivals and of each other.
- Queue discipline: Rule to select the next job (e.g., FIFO/FCFS, LIFO, priority). Unless stated, assume FIFO.
- Servers in parallel (c): Multiple identical servers share the queue; each server works on one job at a time.
- System capacity (K): Maximum number of jobs allowed in system (queue + in service). If full, arriving jobs are blocked (lost) or balk.
- Source population (N): If finite, the effective arrival rate decreases as more jobs enter the system (e.g., machine repairman problem). Unless stated, assume infinite population.
- Kendall’s notation A/S/c/K/N/D: A = inter-arrival distribution (M = Markov/Poisson), S = service-time distribution (M = exponential, G = general), c = number of servers, K = capacity, N = population size, D = discipline (e.g., FIFO). Default omitted parameters mean infinite capacity, infinite population, FIFO.
- Traffic intensity (utilization) ρ: Load on the server(s). For single server, ρ = λ/μ. For c servers, ρ = λ/(c μ). Stability requires ρ < 1 (for infinite-capacity systems with Poisson/exponential assumptions). Under ρ ≥ 1, queue length tends to grow without bound.
- Finite-capacity/loss systems: Systems like M/M/1/K and M/M/c/c are finite-state and always have a steady state (ergodic) for any λ, μ (no ρ < 1 requirement).
- State n: Number of jobs in system (waiting + in service). A birth–death process with birth rates λn and death rates μn describes transitions: n → n+1 at rate λn, n → n−1 at rate μn.
- Steady-state probabilities Pn: Long-run fraction of time the system has n jobs. For ergodic systems (ρ < 1 in standard infinite-capacity Poisson/exponential queues), Pn exists and sums to 1.
- Little’s law: L = λe W holds for any stable system and any subsystem with well-defined average effective arrival rate λe, average number in system L, and average time in system W. Applies regardless of distributions and discipline.
- Performance measures: L (mean number in system), Lq (mean number waiting), W (mean time in system), Wq (mean waiting time), P(wait) (probability an arrival must wait), blocking probability (probability of loss in finite capacity), P0 (probability of zero in system).
- M/M/1: Poisson arrivals, exponential service, single server, infinite capacity, FIFO. Key results: Pn = (1−ρ) ρ^n, L = ρ/(1−ρ), W = 1/(μ−λ), Lq = ρ^2/(1−ρ), Wq = λ/(μ(μ−λ)). Derivation outline: write birth–death steady-state balance λ Pn = μ Pn+1; solve recurrence Pn = ρ^n P0; normalize to find P0; then apply Little’s law.
- M/M/c: c identical exponential servers, infinite capacity. Define a = λ/μ and ρ = λ/(c μ). The normalizing constant P0 involves a finite sum up to c−1 and a tail geometric-like term. Probability of delay P(wait) is the Erlang C formula. Lq follows from P(wait) and ρ; then Wq = Lq/λ and W = Wq + 1/μ. Assumptions: FIFO, independent exponential services, Poisson arrivals, infinite capacity.
- M/M/c/c (loss system): c servers, no waiting space. Calls/jobs arriving when all c are busy are lost. Blocking probability is given by Erlang B; throughput equals λ (1 − B).
- M/M/1/K (finite capacity): Single server, capacity K. If system has K jobs, arrivals are blocked (lost). Steady-state remains geometric but truncated, with modified P0 and effective arrival rate λe = λ (1 − PK).
- M/G/1: Poisson arrivals with rate λ, general service time S with mean E[S] and second moment E[S^2]. Pollaczek–Khinchine result gives Wq and Lq; the service-time variance directly impacts waiting.
- Departures and PASTA: Burke’s theorem (M/M/1) states the departure process is Poisson with rate λ in steady state; PASTA (Poisson Arrivals See Time Averages) means arriving customers sample steady-state state probabilities.
- Limiting behavior: As ρ → 1−, queues blow up. For M/M/1, W = 1/(μ−λ), so delays become very large near saturation. Variability increases delay: in M/G/1, larger Var(S) increases Wq.
- Real systems differ: arrivals may be time-varying (non-stationary), services non-exponential (e.g., deterministic), customers may balk (refuse to join), renege (abandon), or jockey (switch lines), priorities and setups exist. These break ideal assumptions; use models M/D/1, G/G/1 approximations (e.g., Kingman’s formula) or simulation when needed.
Formulas
ρ = λ / μ — ρ: traffic intensity (dimensionless), λ: arrival rate (s⁻¹), μ: service rate of one server (s⁻¹); applies to single-server systems.
ρ = λ / (c·μ) — For c parallel identical servers; ρ must be < 1 for stability in infinite-capacity systems.
L = λe · W — Little’s law; L: average number in system (dimensionless), λe: effective arrival rate that enter the system (s⁻¹), W: average time in system (s). General stable systems.
Lq = λe · Wq — Queue version of Little’s law (excluding service). General stable systems.
M/M/1 (infinite capacity, FIFO):
P0 = 1 − ρ — Probability of empty system; requires ρ < 1.
Pn = (1 − ρ) · ρⁿ — Probability of n in system; n ≥ 0.
P(wait) = ρ — Probability an arrival must wait (server busy on arrival) by PASTA.
L = ρ / (1 − ρ) — Mean number in system.
Lq = ρ² / (1 − ρ) — Mean number waiting.
W = 1 / (μ − λ) — Mean time in system (s).
Wq = λ / [μ · (μ − λ)] — Mean waiting time (s).
U = ρ — Server utilization (fraction of time busy), dimensionless.
M/M/c (infinite capacity, FIFO): define a = λ / μ, ρ = λ / (c·μ)
P0 = [ Σ_{n=0}^{c−1} (aⁿ / n!) + (aᶜ / (c! · (1 − ρ))) ]⁻¹ — Empty-system probability; ρ < 1.
P(wait) = (aᶜ / (c! · (1 − ρ))) · P0 — Erlang C: probability an arrival must wait.
Lq = [P(wait) · ρ] / (1 − ρ) — Mean number waiting.
Wq = Lq / λ — Mean waiting time (s).
W = Wq + 1/μ — Mean time in system (s) for FIFO.
L = λ · W — Mean number in system.
U = ρ — Average utilization per server.
M/M/c/c (loss; no waiting):
B(c, a) = (aᶜ / c!) / [ Σ_{n=0}^{c} (aⁿ / n!) ] — Erlang B blocking probability; a = λ/μ. Steady state exists for any λ, μ.
B(c, a) = [ a · B(c−1, a) ] / [ c + a · B(c−1, a) ] with B(0, a) = 1 — Recursive computation.
Throughput = λ · (1 − B(c, a)) — Effective serviced rate (s⁻¹).
M/M/1/K (finite capacity K): define ρ = λ / μ
P0 = (1 − ρ) / (1 − ρ^{K+1}) for ρ ≠ 1 — Empty probability; for ρ = 1, use Pn = 1/(K+1). Steady state exists for any λ, μ.
Pn = [ (1 − ρ) · ρⁿ ] / (1 − ρ^{K+1}) — 0 ≤ n ≤ K.
PK = [ (1 − ρ) · ρ^K ] / (1 − ρ^{K+1}) — Probability system is full (blocking).
λe = λ · (1 − PK) — Effective admitted arrival rate (s⁻¹).
L = [ ρ · (1 − (K+1)·ρ^K + K·ρ^{K+1}) ] / [ (1 − ρ) · (1 − ρ^{K+1}) ] — Mean number in system.
W = L / λe — Mean time in system (s) for admitted jobs.
Wq = W − 1/μ — Mean waiting time (s) for admitted jobs.
M/G/1 (FIFO): let S be service time, E[S] = 1/μ (s), E[S²] (s²), ρ = λ · E[S]
Wq = [ λ · E[S²] ] / [ 2 · (1 − ρ) ] — Pollaczek–Khinchine mean waiting time (s).
Lq = λ · Wq = [ λ² · E[S²] ] / [ 2 · (1 − ρ) ] — Mean number waiting.
Lq = [ λ² · Var(S) + ρ² ] / [ 2 · (1 − ρ) ] — Equivalent form using Var(S) (s²); dimensionless.
W = Wq + E[S] — Mean time in system (s).
M/D/1 (deterministic service; special case of M/G/1): let ρ = λ/μ
Wq = ρ / [ 2 · μ · (1 − ρ) ] — Mean waiting time (s).
Lq = λ · Wq = ρ² / [ 2 · (1 − ρ) ] — Mean number waiting.
W = Wq + 1/μ — Mean time in system (s).
G/G/1 (Kingman’s approximation): let ca² = SCV of inter-arrival times, cs² = SCV of service times, E[S] = 1/μ, ρ = λ E[S]
Wq ≈ [ ρ / (1 − ρ) ] · [ (ca² + cs²) / 2 ] · E[S] — Approximate mean waiting time (s).
Lq ≈ λ · Wq, W ≈ Wq + E[S] — Derived approximations.
Other standard results:
PASTA: P{arrival sees n} = Pn — For Poisson arrivals in steady state.
Burke’s theorem (M/M/1): departures ~ Poisson(λ) — In steady state with ρ < 1.
Units note: Keep λ, μ in s⁻¹, times in s. If given per hour or per minute, convert to s⁻¹ before use. SCVs (ca², cs²) are dimensionless.
Worked examples
Example 1 — Direct M/M/1 performance Given: Poisson arrivals with rate λ = 0.20 s⁻¹, exponential service with rate μ = 0.25 s⁻¹, infinite capacity, FIFO.
- Check stability: ρ = λ/μ = 0.20/0.25 = 0.80 < 1 ⇒ stable.
- Mean time in system: formula W = 1/(μ − λ).
- Numbers: W = 1/(0.25 − 0.20) s = 1/0.05 s = 20 s.
- Mean waiting time: formula Wq = λ/[μ(μ − λ)].
- Numbers: Wq = 0.20 / [0.25 × 0.05] s = 0.20 / 0.0125 s = 16 s.
- Mean number in system: formula L = λ W.
- Numbers: L = 0.20 s⁻¹ × 20 s = 4.0 (dimensionless).
- Mean number waiting: formula Lq = λ Wq.
- Numbers: Lq = 0.20 s⁻¹ × 16 s = 3.2.
- Probability system empty: formula P0 = 1 − ρ.
- Numbers: P0 = 1 − 0.80 = 0.20.
- Probability of exactly 3 in system: formula Pn = (1 − ρ) ρⁿ.
- Numbers: P3 = 0.20 × 0.80³ = 0.20 × 0.512 = 0.1024.
Answer: W = 20 s, Wq = 16 s, L = 4.0, Lq = 3.2, P0 = 0.20, P3 = 0.1024. The final numeric answers are consistent via Little’s law.
Example 2 — M/M/2 with Erlang C (GATE-level combined measures) Given: Poisson arrivals with rate λ = 0.10 s⁻¹, two identical servers (c = 2), each server exponential with μ = 0.08 s⁻¹; infinite capacity, FIFO. Find P0, P(wait), Lq, Wq, W, L. Also comment on utilization.
- Compute a and ρ: a = λ/μ = 0.10/0.08 = 1.25 (dimensionless); ρ = λ/(c μ) = 0.10/(2 × 0.08) = 0.10/0.16 = 0.625.
- Stability holds since ρ < 1.
- Empty probability P0: use P0 = [ Σ_{n=0}^{c−1} (aⁿ/n!) + (aᶜ/(c! (1−ρ))) ]⁻¹.
- Σ_{n=0}^{1} (aⁿ/n!) = 1 + 1.25 = 2.25.
- Tail term = a²/(2! (1−ρ)) = 1.25² / (2 × (1 − 0.625)) = 1.5625 / (2 × 0.375) = 1.5625 / 0.75 = 2.0833333.
- Denominator sum = 2.25 + 2.0833333 = 4.3333333.
- P0 = 1 / 4.3333333 = 0.2307692.
- Probability of delay P(wait): Erlang C = (aᶜ/(c! (1−ρ))) × P0.
- P(wait) = 2.0833333 × 0.2307692 = 0.4807692.
- Mean number waiting Lq: Lq = [P(wait) × ρ]/(1 − ρ).
- Lq = 0.4807692 × 0.625 / 0.375 = 0.4807692 × 1.6666667 = 0.801282.
- Mean waiting time Wq: Wq = Lq/λ.
- Wq = 0.801282 / 0.10 s = 8.01282 s.
- Mean time in system W: W = Wq + 1/μ.
- 1/μ = 1 / 0.08 s⁻¹ = 12.5 s.
- W = 8.01282 s + 12.5 s = 20.51282 s.
- Mean number in system L: L = λ W.
- L = 0.10 s⁻¹ × 20.51282 s = 2.051282.
- Utilization: U = ρ = 0.625 (average fraction of time each server is busy).
Answers: P0 = 0.2307692, P(wait) = 0.4807692, Lq = 0.801282, Wq = 8.01282 s, W = 20.51282 s, L = 2.051282, utilization per server = 0.625. All measures are mutually consistent by Little’s law.
Common mistakes
- Mixing units (per hour vs per second). Always convert λ and μ to s⁻¹ and times to seconds.
- Using ρ = λ/(c μ) but then adding 1/μ to W for M/M/c incorrectly per server. Remember W = Wq + 1/μ for FIFO regardless of c (service time distribution per job is exponential with mean 1/μ at the server that serves it).
- Forgetting stability: applying M/M/1 formulas when λ ≥ μ, or M/M/c when ρ ≥ 1, leading to negative or infinite results.
- Confusing λ with λe in finite-capacity systems: use λe = λ (1 − PK) for Little’s law.
- Using M/M/1 formulas for M/M/1/K or M/M/c: each model has distinct P0, Lq, etc.
- Dropping P0 in M/M/c: P0 must be computed carefully; do not assume P0 = 1 − ρ (only true for M/M/1).
- Treating W = Lq/λ instead of Wq = Lq/λ: missing the queue vs system distinction.
- For M/G/1, plugging μ for E[S] in PK formula incorrectly; you need E[S²] (or Var(S) and E[S]).
- M/D/1 special case: using ρ² instead of ρ in Wq. Correct is
Wq = ρ / [2 μ (1 − ρ)]. - Kingman’s formula: forgetting that ca² and cs² are squared coefficients of variation (dimensionless), not variances.
For GATE ME
- Quick derivations and memory: M/M/1, M/M/c standard results; Erlang C and Erlang B; M/M/1/K expressions; Pollaczek–Khinchine for M/G/1.
- Compute P0, Pn, L, Lq, W, Wq, utilization, and blocking probabilities, with careful unit conversions.
- Stability checks and limiting behavior as ρ → 1; interpret qualitative changes.
- Applying Little’s law to sub-systems and to finite-capacity systems using λe.
- Selecting number of servers to meet a service level (e.g., limit P(wait), Wq), by trying c = 1, 2, 3 and checking Erlang C.
- Recognize when assumptions break (non-Poisson arrivals, general services), and use M/G/1 or mention need for simulation.
- Know M/D/1 formulas and Kingman’s G/G/1 approximation for quick estimates when service is low-variability or general.
Quick check
- In an M/M/1 with λ = 0.3 s⁻¹ and μ = 0.5 s⁻¹, what is W?
- In M/M/c with c = 3, λ = 0.6 s⁻¹, μ = 0.3 s⁻¹, what is ρ and is it stable?
- For M/G/1 with λ = 0.05 s⁻¹, E[S] = 10 s, Var(S) = 25 s², compute Wq.
Answers: 1) W = 1/(μ − λ) = 1/(0.5 − 0.3) = 5 s. 2) ρ = λ/(c μ) = 0.6/(3 × 0.3) = 0.6667 < 1, stable. 3) Wq = [λ E[S²]]/[2(1 − ρ)], E[S²] = Var + E[S]² = 25 + 100 = 125 s², ρ = λ E[S] = 0.05 × 10 = 0.5 ⇒ Wq = (0.05 × 125)/(2 × 0.5) = 6.25/1 = 6.25 s.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?