Queuing models: M/M/1 and M/M/c

Why it matters

Jobs waiting at a bottleneck machine, operators queuing at a tool crib, trucks at a loading dock and breakdowns waiting for a maintenance crew are all queues. Too few servers means idle people and late orders; too many means idle servers. Queuing models put numbers on this trade-off from just two rates, so you can decide how many servers to provide before buying anything.

Key ideas

Elements of a queue. Arrival process (rate λ), service process (rate μ per server), number of servers c, queue discipline (usually first-come-first-served), system capacity and calling population (usually infinite).

Kendall notation A/B/c. A = inter-arrival distribution, B = service-time distribution, c = number of servers. M (Markovian) means Poisson arrivals, i.e. exponential inter-arrival times, or exponential service times. M/M/1 is one server; M/M/c is c parallel identical servers fed by one common queue. Extended forms add capacity and population (M/M/1/N/∞/FCFS).

Assumptions of M/M/1 and M/M/c. Poisson arrivals at a constant mean rate λ; exponential service times with mean 1/μ; infinite queue capacity and population; FCFS; no balking or reneging; steady state, which exists only if the traffic intensity ρ < 1. The exponential distribution is memoryless: the remaining service time does not depend on how long service has already taken.

Traffic intensity (utilisation).

• M/M/1: ρ = λ/μ — the fraction of time the server is busy; 1 − ρ is the probability the system is empty.
• M/M/c: ρ = λ/(cμ) — the average utilisation of each server; stability requires λ < cμ. As ρ → 1 queues and waits grow without bound — the curve is very steep above about ρ = 0.8, which is why bottleneck machines are not loaded to 100 %.

Little's law. In any stable system, L = λW and L_q = λW_q, and W = W_q + 1/μ. Once one measure is known, the others follow.

M/M/c logic. First find P₀ from the sum over states, then the probability an arrival must wait (the Erlang C probability), then L_q, then the rest by Little's law. One fast server of rate cμ gives a shorter time in system than c slow servers of rate μ, but c servers give a shorter wait in queue and are more robust to a breakdown.

Formulas

M/M/1 (ρ = λ/μ < 1):

• P₀ = 1 − ρ, Pₙ = (1 − ρ)·ρⁿ, P(n > k) = ρ^(k+1)
• L = λ / (μ − λ), L_q = λ² / [μ(μ − λ)]
• W = 1 / (μ − λ), W_q = λ / [μ(μ − λ)]

M/M/c (r = λ/μ, ρ = λ/(cμ) < 1):

• P₀ = [ Σ (n = 0 to c − 1) rⁿ/n! + r^c / (c!·(1 − ρ)) ]⁻¹
• P(wait) = r^c · P₀ / (c!·(1 − ρ))
• L_q = P₀ · r^c · ρ / (c!·(1 − ρ)²)
• W_q = L_q / λ, W = W_q + 1/μ, L = λW = L_q + r

Symbols: λ = mean arrival rate (customers/h); μ = mean service rate per server (customers/h); c = number of servers; ρ = utilisation (dimensionless); Pₙ = probability of n in system; L, L_q = mean number in system and in queue; W, W_q = mean time in system and in queue (h). Valid in steady state only.

Worked examples

Example 1 (M/M/1). Jobs arrive at a CNC machine at λ = 12 per hour (Poisson); machining times are exponential with mean 4 min, so μ = 15 per hour.

1. ρ = λ/μ = 12/15 = 0.8; P₀ = 0.2 (idle 20 % of the time).
2. L = λ/(μ − λ) = 12/3 = 4 jobs; L_q = λ²/[μ(μ − λ)] = 144/45 = 3.2 jobs.
3. W = 1/(μ − λ) = 1/3 h = 20 min; W_q = λ/[μ(μ − λ)] = 12/45 h = 16 min.
4. Check by Little: L = λW = 12 × (1/3) = 4 ✓; W − W_q = 4 min = 1/μ ✓.
5. P(more than 3 jobs) = ρ⁴ = 0.8⁴ = 0.410.
6. L = 4 jobs, W = 20 min, W_q = 16 min.

Example 2 (GATE-type, M/M/2 vs a faster single server). Operators arrive at a tool crib at λ = 10 per hour. Option 1: two attendants, each μ = 6 per hour. Option 2: one attendant with μ = 12 per hour. Compare W_q and W.

1. Option 1: r = 10/6 = 1.667, ρ = 10/12 = 0.833.
2. P₀ = [1 + 1.667 + 1.667²/(2 × (1 − 0.833))]⁻¹ = [2.667 + 2.778/0.333]⁻¹ = [2.667 + 8.333]⁻¹ = 1/11 = 0.0909.
3. L_q = P₀ · r² · ρ / (2!·(1 − ρ)²) = 0.0909 × 2.778 × 0.833 / (2 × 0.02778) = 3.79 operators.
4. W_q = 3.79/10 = 0.379 h = 22.7 min; W = 22.7 + 10 = 32.7 min.
5. Option 2 (M/M/1, μ = 12): W_q = 10/[12 × 2] = 0.417 h = 25.0 min; W = 1/(12 − 10) = 0.5 h = 30.0 min.
6. Two attendants: W_q ≈ 22.7 min, W ≈ 32.7 min. One fast attendant: W_q = 25 min, W = 30 min. The fast single server gets operators back to work sooner; the two-server crib has the shorter queue and a backup.

Common mistakes

• Using M/M/1 formulas when λ ≥ μ — no steady state exists.
• Mixing units: arrival rate per hour with service time in minutes. Convert a mean service time to a rate first (4 min → 15/h).
• Using ρ = λ/μ for M/M/c instead of λ/(cμ).
• Confusing W (in system, includes service) with W_q (in queue only).
• Applying Little's law with the wrong λ (in finite-capacity systems use the effective arrival rate).
• Treating c servers as one queue per server — M/M/c assumes one common queue.

For GATE PI

• M/M/1 calculations: ρ, L, L_q, W, W_q, P₀, Pₙ (very frequent NAT).
• Effect of changing λ or μ, and the minimum μ to meet a target waiting time.
• Simple M/M/2 problems and Little's law consistency checks.
• Practise converting service times to rates and keeping hours versus minutes straight.

Quick check

1. λ = 8/h, μ = 10/h (M/M/1). Find L and W.
2. In an M/M/3 system λ = 24/h and μ = 10/h. What is ρ?
3. L = 6 and λ = 3 per minute. What is W?
4. What happens to W in M/M/1 as λ approaches μ?

Answers: 1. L = 8/2 = 4; W = 1/2 h = 30 min. 2. 24/30 = 0.8. 3. 2 min. 4. It grows without limit.