Queuing Theory: Models, Assumptions & Real-World Applications

TAKEAWAYS:

• Queuing theory analyzes waiting lines (queues) to minimize costs and improve efficiency using arrival rates (λ), service rates (μ), and queue discipline.
• The M/M/1 model (Markovian arrivals and service) is the simplest single-channel queue, where customers wait in a line for one server (e.g., a bank teller).
• Key metrics like average queue length (Lq), waiting time (Wq), and system time (Ws) are derived from Little’s Law: $L=\lambda W$.
• Assumptions (e.g., Poisson arrivals, exponential service times) simplify real-world problems but must be checked for validity.
• Applications range from call centers (Ncell) to e-commerce order processing (Daraz) and traffic management (Kathmandu’s ring road).
• Exam focus: Compare models, solve for metrics, and justify assumptions in real-world scenarios (e.g., a hospital’s emergency ward).

1. Introduction to Queuing Theory

Queuing theory is a branch of Operational Research (OR) that studies waiting lines (queues) to optimize service systems. It helps businesses and governments reduce costs, improve customer satisfaction, and allocate resources efficiently.

Why Study Queuing Theory?

• Real-world impact: Delays cost money (e.g., a customer waiting at a bank loses productivity).
• Decision-making: Helps design systems like call centers, hospitals, and traffic signals.
• Mathematical foundation: Uses probability, statistics, and stochastic processes.

Key Terms

2. Components of a Queuing System

Every queuing system has three essential components:

1. Input source: Where customers arrive (e.g., people entering a bank).
2. Service facility: Where customers are served (e.g., a teller’s counter).
3. Queue discipline: Rules governing the order of service (e.g., FCFS, LIFO, priority).

Visual: Queuing System Structure

flowchart LR
    A["Input Source\n(e.g., Customers)"] -->|"Arrive at rate λ"| B["Queue\n(Waiting Line)"]
    B -->|"Join queue"| C["Service Facility\n(e.g., Server/Teller)"]
    C -->|"Serve at rate μ"| D["Output\n(Served Customers)"]
    D --> A

3. Types of Queuing Models

Queuing models are classified based on:

• Arrival pattern (e.g., random, deterministic).
• Service mechanism (e.g., single-server, multi-server).
• Queue discipline (e.g., FIFO, priority).
• System capacity (e.g., finite or infinite).

Kendall’s Notation

Models are often described using Kendall’s notation: A/B/c/K/N/M

• A: Arrival process (e.g., M = Markovian/Poisson, D = Deterministic).
• B: Service time distribution (e.g., M = Markovian/exponential, G = General).
• c: Number of servers.
• K: Queue capacity (maximum number in the system).
• N: Population size (if finite).
• M: Service discipline (e.g., FCFS, LCFS).

Example: An M/M/1 model means:

• Arrivals: Poisson process (random).
• Service times: Exponentially distributed (random).
• Single server.

4. Single-Channel Queuing Model (M/M/1)

The M/M/1 model is the simplest queuing system:

• One server (e.g., a single bank teller).
• Poisson arrivals (λ customers/hour).
• Exponential service times (μ customers/hour).
• Infinite queue capacity (customers can wait indefinitely).

Assumptions of M/M/1 Model

1. Arrivals follow a Poisson process (probability of arrival is independent of past events).
2. Service times are exponentially distributed (memoryless property).
3. The system is stable (λ < μ, otherwise the queue grows infinitely).
4. First-Come-First-Served (FCFS) discipline.
5. Infinite queue capacity (no maximum limit on waiting customers).

Key Metrics for M/M/1

For an M/M/1 system in steady state (λ < μ), the following metrics are derived:

1. Probability of an empty system (P₀): $$P_0=1-\frac{\lambda }{\mu }$$

2. Average number of customers in the queue (Lq): $$L_q=\frac{{\lambda }^2}{\mu (\mu -\lambda )}$$

3. Average number of customers in the system (L): $$L=\frac{\lambda }{\mu -\lambda }$$

4. Average waiting time in the queue (Wq): $$W_q=\frac{L_q}{\lambda }=\frac{\lambda }{\mu (\mu -\lambda )}$$

5. Average time in the system (Ws): $$W_s=\frac{L}{\lambda }=\frac{1}{\mu -\lambda }$$

Worked Example 1: Bank Teller Queue

Scenario: A bank has one teller serving customers. Customers arrive at a rate of λ = 12 per hour, and the teller serves customers at a rate of μ = 15 per hour. Assume Poisson arrivals and exponential service times.

Questions:

1. What is the probability that the bank is empty?
2. What is the average number of customers waiting in the queue?
3. What is the average waiting time for a customer?

Solution:

1. Probability of an empty system (P₀): $$P_0=1-\frac{\lambda }{\mu }=1-\frac{12}{15}=1-0.8=0.2(20\%)$$

2. Average queue length (Lq): $$L_q=\frac{{\lambda }^2}{\mu (\mu -\lambda )}=\frac{12^2}{15(15-12)}=\frac{144}{15\times 3}=\frac{144}{45}=3.2\text{ customers}$$

3. Average waiting time (Wq): $$W_q=\frac{L_q}{\lambda }=\frac{3.2}{12}=0.2667\text{ hours}=16\text{ minutes}$$

Visual: Queue Length Distribution This graph shows the probability of having n customers in the system. The probability decreases as n increases.

5. Real-World Applications of Queuing Theory

Queuing theory is used in Nepal and globally to optimize systems where waiting occurs. Here’s how:

Example 1: Ncell Customer Service Center (M/M/c Model)

• Problem: Ncell receives λ = 200 calls/hour, but their 3 customer service agents handle μ = 80 calls/hour each.
• Issue: Long wait times frustrate customers.
• Solution: Queuing theory helps determine:
  • How many agents are needed to keep wait times under 2 minutes.
  • Whether adding a 4th agent reduces costs more than it increases wages.
• Key Metric: Use Erlang C formula (for multi-server queues) to calculate: $$W_q=\frac{P_0{\left(\frac{\lambda }{\mu }\right)}^c\lambda }{\mu c!(1-\rho {)}^2}\text{(where }\rho =\frac{\lambda }{c\mu }\text{)}$$ Here, $\rho =\frac{200}{3\times 80}=0.833$. If $W_q>2$ minutes, more agents are needed.

Example 2: Daraz Order Fulfillment (M/G/1 Model)

• Problem: Daraz’s warehouse processes λ = 500 orders/day, but order processing times vary (some take 5 minutes, others 30 minutes).
• Issue: Customers complain about delayed deliveries.
• Solution: Queuing theory helps:
  • Model variable service times (G) to predict delays.
  • Optimize warehouse staffing during peak hours (e.g., Dashain sales).
• Key Metric: Use Pollaczek-Khinchine formula for M/G/1: $$W_q=\frac{\lambda E[S^2]}{2(1-\rho )}\text{(where }E[S]=\text{mean service time, }E[S^2]=\text{variance)}$$ If $E[S]=15$ minutes and variance is high, Daraz may prioritize faster orders or hire temporary staff.

Example 3: Kathmandu Traffic Management (M/M/∞ Model)

• Problem: Traffic jams at Kathmandu’s Ring Road cause λ = 1000 vehicles/hour to enter a single lane, but the lane can only handle μ = 600 vehicles/hour.
• Issue: Long queues and accidents.
• Solution: Queuing theory helps:
  • Model traffic flow as M/M/1 to predict congestion.
  • Design smart traffic lights to dynamically adjust green/red times.
• Key Metric: Calculate probability of delay using: $$P(\text{delay})=\frac{\lambda }{\mu }=\frac{1000}{600}=1.67\text{(Unstable!)}$$ Solution: Add more lanes or restrict entry during peak hours.

6. Multi-Channel Queuing Models

When a system has multiple servers, the model becomes M/M/c (e.g., a bank with 3 tellers).

Key Differences: M/M/1 vs. M/M/c

Worked Example 2: Hospital Emergency Ward (M/M/c)

Scenario: A hospital’s emergency ward has:

• λ = 20 patients/hour.
• 3 doctors, each serving at μ = 8 patients/hour.
• FCFS discipline.

Questions:

1. What is the probability that all doctors are busy?
2. What is the average number of patients waiting?

Solution:

1. Utilization per doctor (ρ): $$\rho =\frac{\lambda }{c\mu }=\frac{20}{3\times 8}=0.833$$ The probability that all doctors are busy is calculated using the Erlang C formula, but for simplicity, we can approximate using: $$P(\text{all busy})\approx \frac{(c\rho {)}^c}{c!(1-\rho )}{P}_0$$ (Full calculation requires solving for $P_0$, but this gives an idea.)

2. Average queue length (Lq): Using the Erlang C formula: $$L_q=\frac{P_0(c\rho {)}^c\rho }{c!(1-\rho {)}^2}$$ (Numerical solution required; typically solved using software or tables.)

7. Economic Considerations in Queuing Systems

Queuing theory isn’t just about math—it’s about cost vs. service level. Businesses must balance:

• Cost of waiting (e.g., customer dissatisfaction, lost sales).
• Cost of service (e.g., hiring more staff, buying equipment).

Cost Components

Optimal Number of Servers

Businesses use queuing theory to find the cost-minimizing number of servers. For example:

• A call center may calculate that adding a 4th agent reduces wait times from 5 minutes to 2 minutes, saving Rs. 50,000/day in lost sales, even if it costs Rs. 30,000/day in wages.

8. Limitations of Queuing Models

While powerful, queuing models have limitations:

1. Assumptions may not hold:
   • Real arrivals aren’t always Poisson (e.g., rush hour traffic spikes).
   • Service times may not be exponential (e.g., some orders take much longer than others).
2. Complexity increases with realism:
   • Adding priority queues, balking (customers leaving if the queue is too long), or reneging (customers leaving while waiting) makes models harder to solve.
3. Human behavior is unpredictable:
   • Customers may change their minds or complain, affecting the system.

9. Advanced Topics (Exam Relevance)

While the syllabus focuses on basic models, exams may test:

• Priority Queues: Customers with higher priority get served first (e.g., VIPs at a hospital).
• Bulk Service: A server handles multiple customers at once (e.g., a bus picking up passengers).
• Finite Population Models: Limited number of customers (e.g., machines in a factory needing repair).

Exam Tip

1. Understand the assumptions: Always state whether arrivals are Poisson, service times exponential, etc.
2. Know the formulas: Memorize Little’s Law, M/M/1 metrics, and Erlang C for multi-server systems.
3. Relate to real-world examples:
   • Ncell: Use M/M/c to optimize call center staffing.
   • Daraz: Use M/G/1 for variable order processing times.
   • Banks: Use M/M/1 for single-teller queues.
4. Draw diagrams: Sketch the queuing system (input → queue → server → output) in exams.
5. Calculate cost trade-offs: If asked about "optimal servers," show both waiting cost and service cost.

Summary Table: Queuing Models

Practice Questions (Exam Style)

1. A hospital has one doctor serving patients at a rate of μ = 10 patients/hour. Patients arrive at λ = 8 patients/hour. Calculate:

   • Probability the doctor is idle.
   • Average number of patients in the queue.
   • Average waiting time.

2. A fast-food restaurant has 2 counters. Customers arrive at λ = 15/hour, and each counter serves at μ = 10/hour. What is the average time a customer spends in the system?

3. Discuss how queuing theory can improve efficiency at:

   • Nepal’s NTC bus stands.
   • Khalti’s customer support.
   • Pathao’s driver dispatch system.

Final Answer Structure for Exams

When answering questions on queuing theory:

1. Define the model (e.g., "This is an M/M/1 queuing system...").
2. State assumptions (Poisson arrivals, exponential service, etc.).
3. Calculate key metrics (Lq, Wq, L, Ws).
4. Interpret results (e.g., "The average wait time is 5 minutes, which may require adding a second server").
5. Relate to real-world (e.g., "This applies to Ncell’s call center...").

A single teller serving customers in a bank queue (M/M/1 model) (Image: Cristian Bortes from Cluj-Napoca, Romania, CC BY 2.0, via Wikimedia Commons) Multiple agents handling calls (M/M/c model) (Image: FiveOne51, CC BY-SA 3.0, via Wikimedia Commons) Vehicles waiting at a signal (M/M/1 with finite capacity) (Image: Kiran891, CC BY-SA 4.0, via Wikimedia Commons)