Lesson 21: Characteristics of Queuing Systems¶
21.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- Identify the six components of a queuing system.
- Read and write Kendall–Lee notation.
- Define the standard performance measures \(L_s, L_q, W_s, W_q\).
- State and apply Little's Law.
- Explain why utilisation below 1 is essential and why congestion grows non-linearly.
21.2 What Is a Queuing System?¶
Definition. A queuing (waiting-line) system consists of customers arriving at a service facility, possibly waiting, receiving service, and departing.
Why we study it. Waiting is expensive — in customer goodwill, in idle machines, in lost sales — but so is capacity. Queuing theory quantifies the trade-off.
The universal structure.
Arrivals Queue Service Departures
-----------> [ o o o o o ] -----> [ Server 1 ] ----------->
(rate λ) (waiting line) [ Server 2 ] (rate μ each)
[ ... ]
[ Server c ]
Examples across domains.
| Setting | Customers | Servers |
|---|---|---|
| Bank | people | tellers |
| Hospital A&E | patients | doctors |
| Factory | jobs | machines |
| Computer network | data packets | routers |
| Call centre | calls | agents |
| Airport | aircraft | runways |
| Repair shop | broken machines | technicians |
21.3 The Six Components¶
The input (arrival) process¶
| Aspect | Options |
|---|---|
| Size of source | infinite (a bank's customers) or finite (10 machines needing repair) |
| Pattern | random (Poisson) or scheduled (appointments) |
| Behaviour | patient; or balking (refusing to join a long queue), reneging (leaving after waiting), jockeying (switching lines) |
| Batch or single | one at a time, or in groups (a bus arriving at a restaurant) |
Definition (Arrival rate \(\lambda\)). The mean number of arrivals per unit time. Mean inter-arrival time \(= 1/\lambda\).
The queue (waiting line)¶
| Aspect | Options |
|---|---|
| Capacity | infinite or finite (\(N\) — a car park, a phone system's hold slots) |
| Number of lines | single line, or one per server |
A single line feeding all servers is provably better than separate lines: it eliminates the risk of being stuck behind one slow customer while another server idles. This is why banks and airports adopted the snake queue.
The queue discipline¶
| Discipline | Meaning |
|---|---|
| FCFS / FIFO | first come, first served — the default and the fairest |
| LCFS / LIFO | last come, first served — a stack; e.g. items on a pallet |
| SIRO | service in random order |
| Priority | urgent cases first — pre-emptive (interrupt current service) or non-pre-emptive |
| SPT | shortest processing time first — minimises average waiting |
Important fact. For the standard measures, the discipline does not affect \(L_s\) or \(W_s\) as long as it is non-pre-emptive and independent of service times. It changes who waits, not the average. Priority disciplines change the distribution of waiting, not its mean.
The service mechanism¶
| Aspect | Options |
|---|---|
| Number of servers \(c\) | 1, several, or infinite (self-service) |
| Arrangement | parallel (independent servers) or series (stages in sequence) |
| Service-time distribution | exponential (M), deterministic (D), Erlang (\(E_k\)), general (G) |
Definition (Service rate \(\mu\)). The mean number of customers one busy server can serve per unit time. Mean service time \(= 1/\mu\).
System capacity and 2.6 population¶
Covered above under queue capacity and source size.
21.4 Kendall–Lee Notation¶
| Position | Meaning | Common symbols |
|---|---|---|
| \(a\) | arrival distribution | M (Markovian/Poisson), D (deterministic), \(E_k\) (Erlang), G (general) |
| \(b\) | service distribution | same symbols |
| \(c\) | number of servers | \(1, 2, \ldots, \infty\) |
| \(d\) | system capacity | \(\infty\) or \(N\) |
| \(e\) | population size | \(\infty\) or \(M\) |
| \(f\) | queue discipline | FCFS, LCFS, SIRO, PRI |
"M" stands for Markovian or memoryless — Poisson arrivals and exponential service times.
Common shorthand. \(M/M/1\) alone means \((M/M/1):(\infty/\infty/\text{FCFS})\).
The five models of the course¶
| Model | Kendall notation | Name | Lesson |
|---|---|---|---|
| I | \((M/M/1):(\infty/\infty/\text{FCFS})\) | single server, infinite queue | L24–L25 |
| II | \((M/M/1):(N/\infty/\text{FCFS})\) | single server, finite capacity | L26 |
| III | \((M/M/c):(\infty/\infty/\text{FCFS})\) | multi-server, infinite queue | L27 |
| IV | \((M/M/c):(N/\infty/\text{FCFS})\) | multi-server, finite capacity | L28 |
| V | \((M/M/1):(\infty/\infty/\text{SIRO})\) | single server, random order | L28 |
21.5 Performance Measures¶
| Symbol | Meaning |
|---|---|
| \(\lambda\) | mean arrival rate |
| \(\mu\) | mean service rate per busy server |
| \(c\) | number of servers |
| \(\rho\) | utilisation (traffic intensity) \(= \lambda/(c\mu)\) |
| \(P_n\) | steady-state probability of exactly \(n\) customers in the system |
| \(P_0\) | probability the system is empty |
| \(L_s\) | expected number in the system (waiting + being served) |
| \(L_q\) | expected number in the queue (waiting only) |
| \(W_s\) | expected time in the system |
| \(W_q\) | expected waiting time in the queue |
The stability condition¶
If \(\rho \ge 1\), arrivals outpace service and the queue grows without bound — no steady state exists. Every formula in Unit III assumes \(\rho < 1\).
The relationships¶
In words: system = queue + service. The term \(\lambda/\mu\) is the expected number in service (which equals \(c\rho\)).
21.6 Little's Law¶
Theorem (Little, 1961). For any queuing system in steady state, whatever the distributions, discipline or number of servers:
The intuition. A customer spends \(W_s\) in the system. During that time, \(\lambda W_s\) new customers arrive. By the time they leave, on average \(\lambda W_s\) are present. Hence \(L_s = \lambda W_s\).
Why it is remarkable. Little's Law requires no assumptions about arrival or service distributions, the number of servers, or the queue discipline. It holds for \(M/M/1\), \(G/G/c\), priority queues, networks of queues — everything in steady state.
Practical uses.
- Compute any one of \(L, W, \lambda\) from the other two.
- Validate a model — if simulated \(L \ne \lambda W\), there is a bug.
- Measure a real system without timing individual customers: count the average number present and divide by the arrival rate.
With finite capacity, use the effective arrival rate \(\lambda_{\text{eff}} = \lambda(1-P_N)\), since blocked customers never enter (L26).
21.7 Why Congestion Grows Non-Linearly¶
For \(M/M/1\) (derived in L24):
| \(\rho\) | \(L_q\) | Interpretation |
|---|---|---|
| 0.50 | 0.50 | comfortable |
| 0.70 | 1.63 | busy |
| 0.80 | 3.20 | congested |
| 0.90 | 8.10 | severe |
| 0.95 | 18.05 | critical |
| 0.99 | 98.01 | collapse |
The \(\frac{1}{1-\rho}\) term explodes as \(\rho\to1\). This single fact explains:
- why hospitals cannot run at 100 % bed occupancy;
- why motorways jam suddenly rather than gradually;
- why "improving utilisation" from 85 % to 95 % is usually a false economy;
- why manufacturing bottlenecks (L15) should be kept below ~85 %.
The design rule.
21.8 Solved Problems¶
Problem 1 — Reading and writing Kendall notation¶
Interpret each notation, and write the notation for the described systems.
(a) \((M/M/3):(\infty/\infty/\text{FCFS})\) (b) \((M/D/1):(10/\infty/\text{FCFS})\) (c) \((M/M/2):(\infty/8/\text{FCFS})\) (d) A bank with 4 tellers, random arrivals, exponential service, unlimited waiting room, served in order. (e) An automated car wash: appointments every 5 minutes exactly, wash takes exactly 4 minutes, one bay, 3 waiting spaces.
Solution.
(a) \((M/M/3):(\infty/\infty/\text{FCFS})\)
- Poisson arrivals, exponential service, 3 parallel servers
- Unlimited queue, unlimited population, first come first served.
- Example: a bank with 3 tellers and a single snake queue.
(b) \((M/D/1):(10/\infty/\text{FCFS})\)
- Poisson arrivals, deterministic (constant) service, 1 server
- System capacity 10 — an 11th arrival is turned away.
- Example: an automated machine with a fixed cycle time and a 10-place buffer.
(c) \((M/M/2):(\infty/8/\text{FCFS})\)
- Poisson arrivals, exponential service, 2 servers, unlimited queue
- Finite population of 8 — e.g. 8 machines that can break down, with 2 repair technicians.
- Note: with a finite source, the arrival rate falls as more customers are already in the system (fewer machines left to break).
(d) The bank.
(e) The car wash.
- Arrivals every 5 minutes exactly ⟹ D
- Service exactly 4 minutes ⟹ D
- 1 bay ⟹ \(c = 1\)
- 3 waiting spaces + 1 in service ⟹ capacity 4
A note on (e). With both arrivals and service deterministic and \(\mu = 15/\text{hr} > \lambda = 12/\text{hr}\), no queue ever forms — each car finishes 1 minute before the next arrives.
If arrivals were Poisson at the same mean rate (\(M/D/1\) with \(\rho = 0.8\)), a substantial queue would form. Removing variability is often cheaper than adding capacity — the insight behind appointment systems, scheduled deliveries and level production.
Problem 2 — Little's Law in practice¶
A hospital emergency department sees 60 patients per day. On average 9 patients are present at any time. (a) What is the average length of stay? (b) If a new triage process cuts the average stay to 2.5 hours, how many patients will be present? (c) A consultant claims the department can handle 90 patients/day with 12 present — is this consistent?
Solution.
Given. \(\lambda = 60\)/day \(= 2.5\)/hour, \(L_s = 9\) patients.
(a) Average length of stay. By Little's Law:
(b) After the improvement. \(W_s = 2.5\) hours, \(\lambda\) unchanged:
(c) Checking the consultant's claim. \(\lambda = 90\)/day \(= 3.75\)/hour, \(L_s = 12\):
Is this consistent? Little's Law is satisfied arithmetically — but it says nothing about whether the system can achieve those numbers.
The real question is capacity. Raising throughput by 50 % (60 → 90) while reducing stay from 3.6 to 3.2 hours means the department must become substantially faster and more heavily loaded. From §6, if utilisation rises from, say, 0.80 to 0.95, waiting time would rise steeply, not fall.
What to ask the consultant. "What is the current utilisation, and what will it be at 90 patients/day? If it exceeds 0.9, the queuing formulas predict waiting times will rise sharply, not fall — what capacity is being added to prevent that?"
The general lesson. Little's Law is a constraint, not a prediction. It tells you that \(L\), \(\lambda\) and \(W\) must be mutually consistent; it does not tell you which combinations are achievable.
Problem 3 — The non-linearity of congestion¶
A machine shop has \(\lambda = 8\) jobs/hour and \(\mu = 10\) jobs/hour. (a) Compute \(L_q\) and \(W_q\). (b) Demand rises 12.5 % to 9 jobs/hour — recompute. (c) Comment.
Solution.
(a) At \(\lambda = 8\).
(b) At \(\lambda = 9\).
(c) The comparison.
| Measure | \(\lambda = 8\) | \(\lambda = 9\) | Change |
|---|---|---|---|
| Arrival rate | 8 | 9 | +12.5 % |
| Utilisation \(\rho\) | 0.80 | 0.90 | +12.5 % |
| Queue length \(L_q\) | 3.2 | 8.1 | +153 % |
| Waiting time \(W_q\) | 24 min | 54 min | +125 % |
Why. The factor \(\frac{1}{1-\rho}\) went from \(\frac{1}{0.2} = 5\) to \(\frac{1}{0.1} = 10\) — it doubled — while \(\rho^2\) rose only from 0.64 to 0.81.
Push further to \(\lambda = 9.5\):
A further 5.6 % rise in demand more than doubles the queue again.
Management implications.
- Capacity planning must be non-linear. Sizing for average demand at high utilisation guarantees poor service.
- Small demand increases can be catastrophic near capacity. A shop comfortable at 8 jobs/hour is in crisis at 9.5.
- Conversely, small capacity increases pay enormous dividends. Raising \(\mu\) from 10 to 11 at \(\lambda = 9\) gives \(\rho = 0.818\), \(L_q = \frac{0.669}{0.182} = 3.68\) — a 55 % reduction in queue for a 10 % capacity increase.
Problem 4 — Choosing the queue discipline¶
A repair shop serves jobs with these processing times: 2, 8, 3, 12, 5 hours (all present at time 0). Compare FCFS (in the order given) and SPT (shortest processing time first) on total and average waiting time.
Solution.
FCFS — order \(2, 8, 3, 12, 5\).
| Job | Duration | Start | Finish | Wait |
|---|---|---|---|---|
| 1 | 2 | 0 | 2 | 0 |
| 2 | 8 | 2 | 10 | 2 |
| 3 | 3 | 10 | 13 | 10 |
| 4 | 12 | 13 | 25 | 13 |
| 5 | 5 | 25 | 30 | 25 |
| Total | 50 |
SPT — order \(2, 3, 5, 8, 12\).
| Job | Duration | Start | Finish | Wait |
|---|---|---|---|---|
| 1 | 2 | 0 | 2 | 0 |
| 3 | 3 | 2 | 5 | 2 |
| 5 | 5 | 5 | 10 | 5 |
| 2 | 8 | 10 | 18 | 10 |
| 4 | 12 | 18 | 30 | 18 |
| Total | 35 |
Comparison.
| Discipline | Total wait | Mean wait | Makespan |
|---|---|---|---|
| FCFS | 50 h | 10 h | 30 h |
| SPT | 35 h | 7 h | 30 h |
Theorem (SPT optimality). On a single machine with all jobs available at time 0, SPT minimises the mean flow time (and hence mean waiting time). Proof by adjacent pairwise interchange, exactly as for Johnson's rule (L14).
Why the makespan is unchanged. The total work is \(2+8+3+12+5 = 30\) hours regardless of order, and the single machine never idles. Sequencing redistributes waiting; it does not create capacity.
The trade-off SPT hides.
| Job | FCFS wait | SPT wait | Change |
|---|---|---|---|
| 2 (8 h) | 2 | 10 | +8 |
| 4 (12 h) | 13 | 18 | +5 |
| 3 (3 h) | 10 | 2 | −8 |
| 5 (5 h) | 25 | 5 | −20 |
Practical consequences.
- SPT can starve long jobs if new short jobs keep arriving. The standard fix is ageing — increase a job's priority the longer it waits.
- Fairness versus efficiency. FCFS is perceived as fair; SPT is more efficient. Many systems use a hybrid (priority classes with FCFS inside each).
- This is why hospital triage is not FCFS, and why operating systems use multi-level feedback queues rather than pure SPT.
Connecting to §2.3's claim. The discipline does not change \(L_s\) or \(W_s\) when service times are independent of the discipline — SPT violates this by using the service times to order the queue, which is exactly why it can improve the average.
Problem 5 — A complete system-design study¶
A bank branch is being designed. Customers arrive Poisson at 30/hour. A teller serves exponentially at 12/hour. Staff cost ₹200/hour; customer waiting is valued at ₹150/hour. How many tellers should be employed?
Solution.
Step 1 — the stability requirement.
With 2 tellers the queue would grow without bound. Any analysis must start at \(c = 3\).
Step 2 — compute the measures for each \(c\) (using the \(M/M/c\) formulas of L27; \(r = \lambda/\mu = 2.5\)).
| \(c\) | \(\rho\) | \(L_q\) | \(W_q\) (min) | \(L_s\) |
|---|---|---|---|---|
| 3 | 0.833 | 3.511 | 7.02 | 6.011 |
| 4 | 0.625 | 0.533 | 1.07 | 3.033 |
| 5 | 0.500 | 0.130 | 0.26 | 2.630 |
| 6 | 0.417 | 0.030 | 0.06 | 2.530 |
Step 3 — the cost analysis.
(Using \(L_s\) — the number in the system — values the customer's whole time in the branch. Using \(L_q\) would value only queueing time; either is defensible, but state which you used.)
| \(c\) | Staff cost | Waiting cost \(150L_s\) | Total |
|---|---|---|---|
| 3 | 600 | \(150(6.011) = 902\) | ₹1 502 |
| 4 | 800 | \(150(3.033) = 455\) | ₹1 255 ← |
| 5 | 1000 | \(150(2.630) = 395\) | ₹1 395 |
| 6 | 1200 | \(150(2.530) = 380\) | ₹1 580 |
Step 4 — sensitivity.
If waiting were valued at only ₹80/hour:
| \(c\) | Staff | Waiting | Total |
|---|---|---|---|
| 3 | 600 | \(80(6.011) = 481\) | ₹1 081 ← |
| 4 | 800 | 243 | ₹1 043 |
| 5 | 1000 | 210 | ₹1 210 |
At ₹80/hour, \(c = 4\) still wins (₹1 043 versus ₹1 081) — but only just.
If waiting were valued at ₹50/hour:
Now \(c=3\) wins. The switch point is around ₹65/hour.
Step 5 — service-level checks.
| \(c\) | \(W_q\) | Meets "under 2 minutes"? |
|---|---|---|
| 3 | 7.0 min | ✗ |
| 4 | 1.07 min | ✓ |
| 5 | 0.26 min | ✓ (over-provisioned) |
If the bank has a published service standard of "under 2 minutes' wait", \(c = 4\) is required regardless of the cost analysis — and conveniently it is also the cost optimum.
Step 6 — the recommendation.
"Employ 4 tellers. This minimises total cost at ₹1 255/hour and meets a 2-minute service standard with \(W_q = 1.07\) minutes. Three tellers would run at 83 % utilisation with a 7-minute average wait — technically stable but poor service and, at our assumed waiting valuation, more expensive overall. Note the recommendation is sensitive to the value placed on customer waiting time: below about ₹65/hour, three tellers becomes cheaper."
Caveats to state.
- Poisson arrivals assume a constant rate. Real banks have lunchtime peaks. Recommend analysing peak-hour \(\lambda\) separately — at \(\lambda = 45\)/hour, \(c=4\) gives \(\rho = 0.94\) and an unacceptable wait.
- Exponential service times assume high variability. If teller times are more regular (\(M/D/c\)), actual queues would be roughly half those predicted — so this analysis is conservative.
- Staffing is not continuous. Consider 3 tellers off-peak and 5 at peak, rather than a fixed 4.
21.9 Practice Problems¶
- Write the Kendall notation for: Poisson arrivals, exponential service, 5 servers, capacity 20, infinite population, FCFS. [Ans: \((M/M/5):(20/\infty/\text{FCFS})\)]
- \(\lambda = 15\)/hr, \(L_s = 6\). Find \(W_s\). [Ans: 0.4 h = 24 min]
- \(\lambda = 20\)/hr, \(\mu = 25\)/hr, \(c=1\). Find \(\rho\) and \(L_q\). [Ans: 0.8, 3.2]
- Why does the queue explode as \(\rho\to1\)?
- State Little's Law and one assumption it does NOT require.
- \(L_q = 4\), \(\lambda = 10\)/hr. Find \(W_q\) in minutes. [Ans: 24 min]
- For \(\lambda=12\), \(\mu=5\), what is the minimum number of servers? [Ans: 3]
21.10 Summary¶
- A queuing system has six components: input process, queue, discipline, service mechanism, system capacity, population.
- Kendall–Lee notation \((a/b/c):(d/e/f)\) — arrival dist. / service dist. / servers : capacity / population / discipline. M = Markovian (Poisson arrivals, exponential service).
- Measures: \(L_s, L_q\) (numbers) and \(W_s, W_q\) (times), with \(L_s = L_q + \lambda/\mu\) and \(W_s = W_q + 1/\mu\).
- Stability requires \(\rho = \lambda/(c\mu) < 1\); otherwise no steady state exists.
- Little's Law \(L = \lambda W\) holds for any steady-state system regardless of distributions, servers or discipline — the most useful result in the subject, and a powerful model-validation check.
- Congestion grows non-linearly: \(L_q = \rho^2/(1-\rho)\) explodes as \(\rho\to1\). Going from 90 % to 95 % utilisation more than doubles the queue. Target \(\rho\le0.85\).
- Queues are caused by VARIABILITY, not just high utilisation — a \(D/D/1\) system with \(\rho = 0.8\) has no queue at all. Reducing variability is often cheaper than adding capacity.
- SPT minimises mean waiting but at the cost of starving long jobs; FCFS is fairer. The discipline redistributes waiting, it does not create capacity.
Next lesson: L22 — The Poisson process and the exponential distribution.
Practise now: unit3-queue-inventory-lab.html → Queue Explorer: set \(\lambda\), \(\mu\) and \(c\),
and watch \(L_q\), \(W_q\) and the utilisation curve update live, with the \(\rho\to1\) explosion plotted.