Queueing theory is the engineering study of waiting lines, from customers at a checkout to packets in a router and jobs in a factory. It helps designers predict how long work waits, how busy servers become, and how many servers are needed. Small changes in arrival rate or service capacity can greatly affect delays, so queueing models are useful for planning reliable systems.
The central idea is to compare how fast work arrives with how fast the system can serve it.
Key Facts
- Arrival rate λ is the average number of jobs entering the system per unit time.
- Service rate μ is the average number of jobs one server can complete per unit time.
- Utilization for one server is ρ = λ/μ, and a stable single-server queue requires ρ < 1.
- For an M/M/1 queue, average number in the system is L = ρ/(1 - ρ).
- For an M/M/1 queue, average time in the system is W = 1/(μ - λ).
- Little's Law connects flow and delay: L = λW.
Vocabulary
- Queue
- A queue is a waiting line of jobs, customers, packets, or tasks that have arrived but have not yet finished service.
- Arrival rate
- Arrival rate is the average number of items entering a queueing system per unit time, usually written as λ.
- Service rate
- Service rate is the average number of items a server can complete per unit time, usually written as μ.
- Utilization
- Utilization is the fraction of service capacity being used, often written as ρ.
- Little's Law
- Little's Law states that the average number in a stable system equals the arrival rate times the average time in the system.
Common Mistakes to Avoid
- Using λ and μ with different time units is wrong because the ratio ρ = λ/μ only makes sense when both rates use the same time unit.
- Assuming 90 percent utilization means only a small wait is wrong because waiting time grows very quickly as ρ approaches 1.
- Confusing time in queue with time in system is wrong because time in system includes both waiting time and service time.
- Treating a queue as stable when λ ≥ μ is wrong because work arrives at least as fast as one server can finish it, so the line tends to grow without bound.
Practice Questions
- 1 A single-server help desk receives λ = 8 requests per hour and serves μ = 10 requests per hour. Find the utilization ρ and the average time in the system W for an M/M/1 model.
- 2 A router has an average arrival rate of 120 packets per second and an average time in the system of 0.025 s. Use Little's Law to find the average number of packets in the system.
- 3 A service counter is often run at 95 percent utilization to save labor cost. Explain why this may cause long and unreliable waiting times, even if the server is technically faster than the arrival rate.