Queuing Models: M/M/1, M/M/c, Limited Waiting Space and M/G/1
CSIR NET queuing theory: birth-death steady state, Little's law, M/M/1, M/M/1/K, M/M/c, M/M/c/K, Erlang formulas and the Pollaczek-Khinchine M/G/1 result.
- 18 min
On this page · 15 sections
Prerequisites
- Markov Chains and Classification of States: a Markovian queue is a continuous-time Markov chain on \( \{0, 1, 2, \dots\} \); stationary distributions, irreducibility and positive recurrence carry over.
- Hazard Function, Failure Rates, Censoring and Life Testing: the memoryless exponential distribution, which is what makes the “M” in M/M/1 work.
- Sequences and Series: every steady-state formula below is a geometric or exponential series summed in closed form.
The Hook: One Fast Counter or Two Slow Ones?
Notation and the Language of Queues
Kendall’s notation \( A/B/c/K \): arrival process / service-time distribution / number of servers / system capacity (in service plus waiting). M means Markovian (Poisson arrivals, exponential service), D deterministic, G general, \( E_k \) Erlang. Capacity \( K = \infty \) is omitted. The discipline is FCFS unless stated.
| Symbol | Meaning |
|---|---|
| \( \lambda \) | arrival rate (customers per unit time) |
| \( \mu \) | service rate of one server; mean service time \( \frac{1}{\mu} \) |
| \( \rho \) | traffic intensity (utilisation): \( \frac{\lambda}{\mu} \) for one server, \( \frac{\lambda}{c\mu} \) for \( c \) servers |
| \( a = \frac{\lambda}{\mu} \) | offered load in erlangs |
| \( p_n \) | steady-state probability of \( n \) customers in the system |
| \( L, L_q \) | mean number in the system, in the queue |
| \( W, W_q \) | mean time in the system, in the queue |
Poisson arrivals and exponential inter-arrival times are the same thing: arrivals form a Poisson process of rate \( \lambda \) if and only if the inter-arrival times are independent exponentials with mean \( \frac{1}{\lambda} \).
Little’s law
For any queue in steady state (very general conditions, any distributions, any discipline),
$$\boxed{L = \lambda W, \qquad L_q = \lambda W_q, \qquad W = W_q + \frac{1}{\mu}.}$$With a finite waiting room, replace \( \lambda \) by the effective arrival rate \( \lambda_{\text{eff}} \), the rate of customers who actually join. Little’s law turns any one of \( L, L_q, W, W_q \) into the other three.
Birth-death steady state
In a Markovian queue the number in system \( N(t) \) is a birth-death process: from state \( n \), up at rate \( \lambda_n \), down at rate \( \mu_n \). The steady-state balance equations (rate out = rate in) reduce to the cut equations \( \lambda_{n-1} p_{n-1} = \mu_n p_n \), so
$$p_n = p_0 \prod_{i=1}^{n} \frac{\lambda_{i-1}}{\mu_i}, \qquad p_0 = \left[1 + \sum_{n \ge 1}\prod_{i=1}^{n}\frac{\lambda_{i-1}}{\mu_i}\right]^{-1}.$$A steady state exists if and only if the sum is finite. Every model below is this formula with a particular choice of \( \lambda_n, \mu_n \).
graph LR
S0((0)) -- "λ0" --> S1((1))
S1 -- "μ1" --> S0
S1 -- "λ1" --> S2((2))
S2 -- "μ2" --> S1
S2 -- "λ2" --> S3((3))
S3 -- "μ3" --> S2
S3 -.-> S4((...))M/M/1
\( \lambda_n = \lambda \), \( \mu_n = \mu \). Steady state iff \( \rho = \frac{\lambda}{\mu} < 1 \).
| Quantity | Formula |
|---|---|
| \( p_n \) | \( (1 - \rho)\rho^n \) (geometric); \( p_0 = 1 - \rho \) |
| \( P(N \ge n) \) | \( \rho^n \) |
| \( L \) | \( \frac{\rho}{1 - \rho} = \frac{\lambda}{\mu - \lambda} \) |
| \( L_q \) | \( \frac{\rho^2}{1 - \rho} = \frac{\lambda^2}{\mu(\mu - \lambda)} \) |
| \( W \) | \( \frac{1}{\mu - \lambda} \) |
| \( W_q \) | \( \frac{\rho}{\mu - \lambda} = \frac{\lambda}{\mu(\mu - \lambda)} \) |
| Time in system (FCFS) | exponential with rate \( \mu - \lambda \): \( P(\text{time} > t) = e^{-(\mu - \lambda)t} \) |
| Wait in queue | \( P(W_q = 0) = 1 - \rho \); \( P(W_q > t) = \rho\,e^{-(\mu - \lambda)t} \) |
| Mean queue length when the queue is non-empty | \( \frac{1}{1 - \rho} \) |
| Mean busy period | \( \frac{1}{\mu - \lambda} \) |
Note \( L - L_q = \rho \), the mean number in service: true for every stable single-server queue with unlimited waiting room (with finite capacity it is \( 1 - p_0 \)).
The blow-up. \( L = \frac{\rho}{1 - \rho} \) is 1 at \( \rho = 0.5 \), 9 at \( \rho = 0.9 \), 99 at \( \rho = 0.99 \). Running a server close to full utilisation is expensive in waiting.
M/M/1/K: Limited Waiting Space
At most \( K \) customers in the system (1 in service, \( K - 1 \) waiting); arrivals finding \( K \) present are lost. \( \lambda_n = \lambda \) for \( n < K \), 0 at \( K \). A steady state exists for every \( \rho \) (finite state space).
$$p_n = \frac{(1 - \rho)\rho^n}{1 - \rho^{K+1}} \ (\rho \ne 1), \qquad p_n = \frac{1}{K + 1} \ (\rho = 1), \qquad n = 0, 1, \dots, K.$$| Quantity | Formula |
|---|---|
| Blocking (loss) probability | \( p_K \) |
| Effective arrival rate | \( \lambda_{\text{eff}} = \lambda(1 - p_K) = \mu(1 - p_0) \) |
| \( L \) | \( \frac{\rho}{1 - \rho} - \frac{(K + 1)\rho^{K+1}}{1 - \rho^{K+1}} \) (\( \rho \ne 1 \)); \( \frac{K}{2} \) (\( \rho = 1 \)) |
| \( L_q \) | \( L - (1 - p_0) \) |
| \( W, W_q \) | \( \frac{L}{\lambda_{\text{eff}}} \), \( \frac{L_q}{\lambda_{\text{eff}}} \) |
The identity \( \lambda(1 - p_K) = \mu(1 - p_0) \) is “rate in = rate out”: customers join at rate \( \lambda_{\text{eff}} \) and leave at rate \( \mu \) whenever the server is busy.
M/M/c
\( c \) identical servers, one queue. \( \lambda_n = \lambda \); \( \mu_n = n\mu \) for \( n \le c \), \( c\mu \) for \( n \ge c \). With \( a = \frac{\lambda}{\mu} \) and \( \rho = \frac{a}{c} \), a steady state exists iff \( \rho < 1 \), i.e. \( \lambda < c\mu \).
$$p_n = \begin{cases} \dfrac{a^n}{n!}\,p_0, & 0 \le n \le c, \\[2mm] \dfrac{a^n}{c!\,c^{n-c}}\,p_0, & n \ge c, \end{cases} \qquad p_0 = \left[\sum_{n=0}^{c-1}\frac{a^n}{n!} + \frac{a^c}{c!\,(1 - \rho)}\right]^{-1}.$$| Quantity | Formula |
|---|---|
| Probability an arrival must wait (Erlang C) | \( C(c, a) = P(N \ge c) = \dfrac{a^c}{c!\,(1 - \rho)}\,p_0 \) |
| \( L_q \) | \( \dfrac{a^c \rho}{c!\,(1 - \rho)^2}\,p_0 = C(c, a)\,\dfrac{\rho}{1 - \rho} \) |
| \( L \) | \( L_q + a \) (mean number of busy servers is \( a \)) |
| \( W_q, W \) | \( \frac{L_q}{\lambda} \), \( W_q + \frac{1}{\mu} \) |
For \( c = 1 \) these reduce to M/M/1. With infinitely many servers (M/M/\( \infty \)) nobody waits and \( N \sim \text{Poisson}(a) \).
M/M/c/K and the Erlang Loss Formula
Now at most \( K \ge c \) in the system. The \( p_n \) are the M/M/c expressions for \( n \le K \), with
$$p_0 = \left[\sum_{n=0}^{c}\frac{a^n}{n!} + \frac{a^c}{c!}\sum_{n=c+1}^{K}\rho^{\,n-c}\right]^{-1},$$and a steady state for every \( \rho \). For \( \rho \ne 1 \),
$$L_q = \frac{p_0\,a^c\rho}{c!\,(1 - \rho)^2}\left[1 - \rho^{K-c+1} - (K - c + 1)(1 - \rho)\rho^{K-c}\right],$$\( \lambda_{\text{eff}} = \lambda(1 - p_K) \), \( W_q = \frac{L_q}{\lambda_{\text{eff}}} \), \( W = W_q + \frac{1}{\mu} \), \( L = \lambda_{\text{eff}} W \).
For \( \lambda = 6 \), \( \mu = 4 \), \( c = 2 \), \( K = 4 \): \( p_0 = \frac{128}{653} \approx 0.196 \), \( p_4 = \frac{81}{653} \approx 0.124 \), \( L_q = \frac{270}{653} \approx 0.413 \). Two waiting places cut the queue from 1.93 to 0.41, at the price of losing 12.4% of customers.
No waiting room (\( K = c \)): M/M/c/c, the Erlang loss system. Arrivals finding all servers busy are lost:
$$p_n = \frac{a^n / n!}{\sum_{j=0}^{c} a^j / j!}, \qquad B(c, a) = p_c = \frac{a^c / c!}{\sum_{j=0}^{c} a^j / j!} \quad \text{(Erlang B)}.$$For \( c = 2 \), \( a = 1.5 \): \( B = \frac{1.125}{1 + 1.5 + 1.125} = \frac{9}{29} \approx 0.310 \).
M/G/1: General Service Times
Poisson arrivals at rate \( \lambda \), one server, service time \( S \) with any distribution, mean \( E[S] = \frac{1}{\mu} \), variance \( \sigma^2 \). With \( \rho = \lambda E[S] < 1 \), the Pollaczek-Khinchine (P-K) mean-value formula is
$$\boxed{L_q = \frac{\lambda^2\sigma^2 + \rho^2}{2(1 - \rho)}, \qquad W_q = \frac{\lambda E[S^2]}{2(1 - \rho)},}$$with \( L = L_q + \rho \), \( W = W_q + E[S] \), and \( p_0 = 1 - \rho \) still.
| Service distribution | \( \sigma^2 \) | \( L_q \) |
|---|---|---|
| Exponential (M/M/1) | \( \frac{1}{\mu^2} \) | \( \frac{\rho^2}{1 - \rho} \) |
| Deterministic (M/D/1) | 0 | \( \frac{\rho^2}{2(1 - \rho)} \): half of M/M/1 |
| Erlang-\( k \) (\( M/E_k/1 \)) | \( \frac{1}{k\mu^2} \) | \( \frac{k + 1}{2k}\cdot\frac{\rho^2}{1 - \rho} \) |
Variability costs waiting. For fixed mean service time, \( L_q \) increases linearly with the variance. Removing all variability halves the queue relative to exponential service.
M/G/1 is not a birth-death chain (the remaining service time is not memoryless); it is analysed through the embedded Markov chain at departure instants, which is where the full P-K transform formula for the distribution of \( N \) comes from.
Memory Tricks
Don’t Confuse
| This | vs | That |
|---|---|---|
| M/M/c: \( \rho = \frac{\lambda}{c\mu} \), stable iff \( \lambda < c\mu \) | offered load \( a = \frac{\lambda}{\mu} \) (can exceed 1) | |
| Erlang C: probability of waiting (infinite queue) | Erlang B: probability of being lost (no queue) | |
| \( K \) = capacity of the whole system | number of waiting places \( K - c \) | |
| \( \lambda \) in Little’s law for infinite capacity | \( \lambda_{\text{eff}} = \lambda(1 - p_K) \) with finite capacity | |
| One fast server: smaller \( L \), \( W \) | \( c \) slow servers: smaller \( L_q \), \( W_q \) (same total capacity) | |
| \( p_0 = 1 - \rho \) in M/G/1 | the rest of the distribution of \( N \) is not geometric unless service is exponential |
Common Mistakes
Practice
All questions below are original practice questions written for this page. They are not from any CSIR NET paper. In Level 3, as in Part C, one or more options may be correct.
Level 1: Foundation
- State Little’s law for the queue (waiting line only).
- In M/M/1 with \( \rho = 0.6 \), what fraction of time is the server idle?
- By what factor does deterministic service reduce \( L_q \) compared with exponential service of the same mean?
Answers
- \( L_q = \lambda W_q \) (with \( \lambda_{\text{eff}} \) if customers can be lost).
- \( p_0 = 1 - \rho = 0.4 \).
- By half: \( \frac{\rho^2}{2(1 - \rho)} \) against \( \frac{\rho^2}{1 - \rho} \).
Level 2: Part B Style
Practice Q1. Customers arrive at a single counter as a Poisson process with rate 6 per hour; service is exponential with mean 7.5 minutes. The mean waiting time in the queue (minutes) is
(a) 7.5 (b) 22.5 (c) 30 (d) 45
Answer: (b)
\( \mu = 8 \) per hour, \( \rho = 0.75 \), \( W_q = \frac{\rho}{\mu - \lambda} = \frac{0.75}{2} = 0.375 \) h = 22.5 min. (c) is \( W \), the time in the system.
Practice Q2. In an M/M/1/3 queue with \( \lambda = \mu \), the proportion of arriving customers who are turned away is
(a) \( \frac{1}{8} \) (b) \( \frac{1}{4} \) (c) \( \frac{1}{3} \) (d) \( \frac{1}{2} \)
Answer: (b)
At \( \rho = 1 \), \( p_n = \frac{1}{K + 1} = \frac{1}{4} \) for \( n = 0, 1, 2, 3 \). Poisson arrivals see time averages, so the loss proportion is \( p_3 = \frac{1}{4} \).
Practice Q3. In an M/G/1 queue, \( \lambda = 3 \) per hour and service times have mean 15 minutes and standard deviation 10 minutes. The mean number in the queue is
(a) 1.125 (b) 1.625 (c) 2.25 (d) 2.375
Answer: (b)
P-K: \( \rho = 0.75 \), \( \lambda^2\sigma^2 = 9 \times \frac{1}{36} = 0.25 \); \( L_q = \frac{0.25 + 0.5625}{0.5} = 1.625 \). (a) is M/D/1, (c) M/M/1, (d) is \( L \).
Practice Q4. For an M/M/2 queue with \( \lambda = 6 \) and \( \mu = 4 \) per hour, the probability that an arriving customer has to wait is
(a) \( \frac{1}{7} \) (b) \( \frac{9}{28} \) (c) \( \frac{9}{14} \) (d) \( \frac{3}{4} \)
Answer: (c)
\( a = 1.5 \), \( \rho = 0.75 \), \( p_0 = \frac{1}{7} \). Erlang C \( = \frac{a^2}{2!(1 - \rho)}p_0 = \frac{2.25}{0.5}\cdot\frac{1}{7} = \frac{9}{14} \). (a) is \( p_0 \); (b) is \( W_q \) in hours; (d) is \( \rho \).
Level 3: Part C Style
Practice Q5. Customers arrive as a Poisson process with rate \( \lambda = 6 \) per hour. System A is one exponential server with rate 8 per hour; system B is two exponential servers each with rate 4 per hour and a single queue. Which statements are true?
(a) Both systems are stable. (b) The mean number in the queue is smaller in B. (c) The mean time in the system is smaller in B. (d) The mean number in the system is smaller in A.
Answer: (a), (b) and (d)
- (a) True. A: \( \lambda < \mu = 8 \). B: \( \lambda < 2 \times 4 = 8 \).
- (b) True. \( L_q^A = 2.25 \), \( L_q^B = \frac{27}{14} \approx 1.93 \).
- (c) False. \( W^A = 0.5 \) h, \( W^B = \frac{4}{7} \approx 0.571 \) h.
- (d) True. \( L^A = 3 \), \( L^B = \frac{24}{7} \approx 3.43 \) (consistent with Little: \( L = 6W \)).
Practice Q6. An M/M/1/2 queue has \( \lambda = 3 \) and \( \mu = 2 \) per hour. Which statements are true?
(a) A steady state exists even though \( \lambda > \mu \). (b) The probability that an arrival is lost is \( \frac{9}{19} \). (c) The effective arrival rate is \( \frac{30}{19} \) per hour. (d) The mean time in the system of a customer who joins is \( \frac{L}{\lambda} = \frac{8}{19} \) hours.
Answer: (a), (b) and (c)
- (a) True. Finite state space \( \{0, 1, 2\} \), irreducible: a unique stationary distribution for any \( \rho \).
- (b) True. Weights \( 1, \frac{3}{2}, \frac{9}{4} \) sum to \( \frac{19}{4} \); \( p_2 = \frac{9/4}{19/4} = \frac{9}{19} \).
- (c) True. \( 3\left(1 - \frac{9}{19}\right) = \frac{30}{19} \), which equals \( \mu(1 - p_0) = 2 \cdot \frac{15}{19} \).
- (d) False. \( L = \frac{24}{19} \), and Little’s law needs \( \lambda_{\text{eff}} \): \( W = \frac{24/19}{30/19} = 0.8 \) h. \( \frac{L}{\lambda} = \frac{8}{19} \) uses the wrong rate.
Practice Q7. A help desk receives Poisson calls at 10 per hour; each call takes an exponential time with mean 15 minutes; calls wait in a single queue for \( c \) identical agents. Which statements are true?
(a) The system is unstable with \( c = 2 \) agents. (b) With \( c = 3 \), \( p_0 = \frac{4}{89} \). (c) With \( c = 3 \), the mean number of calls waiting is about 3.51. (d) With \( c = 3 \), the mean waiting time before an agent answers is about 35 minutes.
Answer: (a), (b) and (c)
\( \lambda = 10 \), \( \mu = 4 \), \( a = 2.5 \).
- (a) True. \( c\mu = 8 < 10 \): with two agents the queue grows without bound.
- (b) True. \( c = 3 \), \( \rho = \frac{5}{6} \). \( \sum_{n=0}^{2}\frac{a^n}{n!} = 1 + 2.5 + 3.125 = 6.625 \); \( \frac{a^3}{3!(1 - \rho)} = \frac{15.625}{6 \cdot \frac{1}{6}} = 15.625 \). \( p_0 = \frac{1}{22.25} = \frac{4}{89} \).
- (c) True. \( L_q = \frac{a^3\rho}{3!(1 - \rho)^2}p_0 = \frac{15.625 \times \frac{5}{6}}{6 \times \frac{1}{36}} \cdot \frac{4}{89} = \frac{625}{178} \approx 3.51 \).
- (d) False. \( W_q = \frac{L_q}{\lambda} = \frac{125}{356} \) h \( \approx 0.351 \) h \( \approx 21.1 \) min. The figure “35 minutes” comes from misreading 0.351 hours as 35 minutes, a units slip. (The mean time in the system is \( W = W_q + 0.25 \) h \( \approx 36.1 \) min.)
Quick Revision Table
| Model | Key results |
|---|---|
| Little | \( L = \lambda W \), \( L_q = \lambda W_q \), \( W = W_q + \frac{1}{\mu} \) |
| Birth-death | \( p_n = p_0\prod_{i \le n}\frac{\lambda_{i-1}}{\mu_i} \) |
| M/M/1 | \( p_n = (1 - \rho)\rho^n \); \( L = \frac{\rho}{1 - \rho} \); \( W = \frac{1}{\mu - \lambda} \); \( L_q = \frac{\rho^2}{1 - \rho} \) |
| M/M/1/K | \( p_n \propto \rho^n \), \( n \le K \); \( \lambda_{\text{eff}} = \lambda(1 - p_K) = \mu(1 - p_0) \); always stable |
| M/M/c | \( p_0^{-1} = \sum_{n |
| Erlang C | \( P(\text{wait}) = \frac{a^c}{c!(1 - \rho)}p_0 \) |
| Erlang B | \( \frac{a^c/c!}{\sum_{j \le c} a^j/j!} \) |
| M/G/1 (P-K) | \( L_q = \frac{\lambda^2\sigma^2 + \rho^2}{2(1 - \rho)} \); M/D/1 half of M/M/1 |
Key Takeaways
What’s Next
- Inventory Models: the other half of the elementary OR syllabus, where stock rather than customers piles up.
- Markov Chains and Classification of States: the stationary-distribution theory behind every \( p_n \) here.
- Reliability and Operations Research: Quick Revision.