Queuing theory: single-server models

Why it matters

Jobs waiting for a CNC machine, trucks waiting at a loading bay and operators queuing at a tool crib all cost money: idle people and machines on one side, extra servers on the other. Single-server queuing models predict queue length and waiting time from just two rates, so you can size a facility before building it.

Key ideas

• Elements of a queuing system. An arrival process (calling population and arrival pattern), a queue (with a capacity, possibly infinite), a queue discipline (FCFS/FIFO, LIFO, SIRO or priority) and a service mechanism (number of servers and service-time distribution).
• Kendall notation (a/b/c):(d/e/f). a = arrival distribution, b = service-time distribution, c = number of servers, d = queue discipline, e = system capacity, f = size of the calling population. M = Markovian (Poisson arrivals, exponential times), D = deterministic, G = general. The basic model is (M/M/1):(FCFS/∞/∞).
• Poisson arrivals and exponential service. If arrivals are Poisson at mean rate λ, the times between arrivals are exponential with mean 1/λ. Service times exponential with mean 1/μ means a service rate μ. The exponential distribution is memoryless: the remaining service time does not depend on how long service has already taken.
• Stability. Utilisation (traffic intensity) ρ = λ/μ is the fraction of time the server is busy. Steady state exists only if ρ < 1. As ρ → 1, queue length and waiting time grow without limit — not linearly, but as 1/(1 − ρ). A server at 95% utilisation has a mean number in system almost five times that of one at 80% (L = 19 against 4).
• Performance measures.
  • L — mean number in the system (waiting + being served); Lq — mean number waiting in the queue.
  • W — mean time in the system; Wq — mean waiting time in the queue.
  • P₀ — probability the system is empty (server idle) = 1 − ρ; Pₙ — probability of exactly n in the system.
• Little's law. L = λW and Lq = λWq hold for almost any stable queue regardless of distributions. Also W = Wq + 1/μ and L = Lq + ρ for a single server.
• Deterministic service (M/D/1). With constant service time, Lq is exactly half the M/M/1 value at the same ρ — variability itself creates waiting.
• Economic design. Total cost per hour = server cost + waiting cost (customers' or machines' idle time × cost rate). Increasing μ reduces waiting cost but raises server cost; the best μ minimises the sum.
• Assumptions to state. Steady state, infinite queue and population, FCFS, independent arrivals, single server. Finite-capacity and multi-server models (M/M/1/N, M/M/s) use different formulas.

Formulas

All for (M/M/1):(FCFS/∞/∞) with ρ < 1.

• Utilisation: ρ = λ / μ
  • λ = mean arrival rate (customers per hour); μ = mean service rate (customers per hour); both in the same time unit.
• Idle probability: P₀ = 1 − ρ
• Probability of n in system: Pₙ = (1 − ρ)·ρⁿ
• Probability of n or more in system: P(N ≥ n) = ρⁿ
• Mean number in system: L = λ / (μ − λ) = ρ / (1 − ρ)
• Mean number in queue: Lq = λ² / (μ(μ − λ)) = ρ² / (1 − ρ)
• Mean time in system: W = 1 / (μ − λ)
• Mean time in queue: Wq = λ / (μ(μ − λ)) = ρ / (μ − λ)
• Little's law: L = λ·W, Lq = λ·Wq; W = Wq + 1/μ
• Mean queue length when the queue is non-empty: Lₙ = μ / (μ − λ)
• Time in system is exponential: P(T > t) = e^(−(μ − λ)·t)
• M/D/1 (constant service time): Lq = ρ² / (2(1 − ρ))

Worked examples

Example 1 (standard): inspection station Parts arrive at a single inspection station at random (Poisson) at 12 per hour; inspection times are exponential with mean 4 minutes.

1. Rates: λ = 12 /h; μ = 60/4 = 15 /h. ρ = 12/15 = 0.8 (< 1, stable).
2. L = ρ/(1 − ρ) = 0.8/0.2 = 4 parts.
3. Lq = ρ²/(1 − ρ) = 0.64/0.2 = 3.2 parts.
4. W = 1/(μ − λ) = 1/3 h = 20 min.
5. Wq = λ/(μ(μ − λ)) = 12/(15 × 3) = 0.2667 h = 16 min. Check: W = Wq + 1/μ = 16 + 4 = 20 min ✓; Little: L = λW = 12 × (1/3) = 4 ✓.
6. P₀ = 1 − 0.8 = 0.2, so the inspector is idle 20% of the time. P(4 or more parts present) = ρ⁴ = 0.4096. Answer: L = 4 parts, Lq = 3.2 parts, W = 20 min, Wq = 16 min, inspector idle 20% of the time.

Example 2 (GATE level): tool crib redesign Mechanics arrive at a tool crib at 10 per hour (Poisson); the attendant serves 12 per hour (exponential).

1. ρ = 10/12 = 0.833. L = 0.833/0.167 = 5 mechanics; Lq = 0.833²/0.167 = 4.17 mechanics.
2. W = 1/(12 − 10) = 0.5 h = 30 min; Wq = 10/(12 × 2) = 0.4167 h = 25 min.
3. Probability that 3 or more mechanics are at the crib: ρ³ = 0.833³ = 0.579.
4. Management wants Wq ≤ 10 min = 1/6 h. Required μ: λ/(μ(μ − λ)) ≤ 1/6 → μ(μ − 10) ≥ 60 → μ² − 10μ − 60 ≥ 0 → μ ≥ (10 + √(100 + 240))/2 = (10 + 18.44)/2 = 14.22 /h.
5. If the service time were made constant at 5 min (μ = 12 /h, M/D/1): Lq = ρ²/(2(1 − ρ)) = 0.694/0.333 = 2.08 mechanics — half the M/M/1 value. Answer: Wq = 25 min now; the attendant must serve at least about 14.2 mechanics per hour to cut Wq to 10 min.

Common mistakes

• Mixing time units: λ per hour with μ per minute, or a mean service time used directly as μ (μ = 1/mean service time).
• Using the formulas when ρ ≥ 1 — the system has no steady state; the queue grows indefinitely.
• Confusing L with Lq and W with Wq; remember L − Lq = ρ (the mean number in service), not 1.
• Writing P(N ≥ n) = ρⁿ⁺¹ or Pₙ = ρⁿ without the (1 − ρ) factor.
• Thinking waiting time grows in proportion to utilisation; it grows as 1/(1 − ρ).
• Applying M/M/1 results to constant service times.

For GATE ME

Expect direct M/M/1 numericals: given λ and μ (often one as a mean time), find ρ, L, Lq, W, Wq or P₀; probability of finding n or more customers; the service rate needed to meet a waiting-time target; and Little's law. Watch for unit conversions and for options that swap L and Lq. Practise deriving every measure from ρ and checking with Little's law.

Quick check

1. λ = 6 /h, μ = 8 /h. Find ρ and L.
2. Mean service time is 5 min. What is μ in customers per hour?
3. A stable queue has λ = 20 /h and W = 0.25 h. What is L?
4. What happens to an M/M/1 queue if λ = μ?
5. For the same ρ, how does Lq for M/D/1 compare with M/M/1?

Answers: 1. ρ = 0.75, L = 3. 2. 12 per hour. 3. L = λW = 5. 4. No steady state; the queue grows without bound. 5. It is half.