Queuing Systems: Models, Metrics & Applications

What is a Queuing System?

A queuing system (or waiting-line system) is a mathematical model of real-world scenarios where entities (customers, tasks, data packets) arrive, wait in a queue, receive service, and depart. It consists of three key components:

1. Arrival process: How entities enter the system (e.g., customers at a bank, jobs in a CPU).
2. Queue discipline: Rules for ordering entities in the queue (FIFO, LIFO, priority).
3. Service mechanism: How entities are processed (e.g., single-server vs. multi-server).

Visual: Basic Queuing System Structure

flowchart LR
    A["Arrival Process\n(Poisson arrivals)"] --> B["Queue\n(Buffer)"]
    B --> C["Service Facility\n(Single/Multi-server)"]
    C --> D["Departure Process"]
    D -->|"Feedback"| A

Real-world analogy: A Khalti payment queue at a Daraz checkout.

• Arrival: Customers (orders) arrive randomly (Poisson process).
• Queue: Unpaid orders wait in a virtual queue.
• Service: Khalti’s servers process payments one by one (single-server, M/M/1).
• Departure: Paid orders leave the system.

Key Components of a Queuing System

1. Arrival Process

Describes how entities enter the system. The most common model is the Poisson process:

• Arrivals are independent (one customer’s arrival doesn’t affect another’s).
• Constant average arrival rate (λ = arrivals per unit time).
• Exponential inter-arrival times (time between arrivals follows an exponential distribution).

Example: Ncell customer calls arrive at an average rate of λ = 12 calls/hour.

• Probability of 0 calls in 5 minutes = $e^{-\lambda t}=e^{-12\times (5/60)}=e^{-1}\approx 0.368$ (36.8% chance).

2. Service Mechanism

Describes how entities are served. Common types:

Visual: M/M/1 vs. M/M/c

3. Queue Discipline

Rules for ordering entities in the queue:

• FIFO (First-In-First-Out): Oldest entity is served first (most common).
• LIFO (Last-In-First-Out): Latest entity is served first (rare in real systems).
• Priority: High-priority entities jump the queue (e.g., emergency patients).
• Random: Entities are served in random order (uncommon).

Example: NEPSE stock trading system uses priority queues for high-frequency traders.

Performance Metrics

Key metrics to evaluate queuing systems:

Little’s Law: Relates the three key metrics: $$L=\lambda W$$

• $L$: Average number of entities in the system.
• $\lambda$: Arrival rate.
• $W$: Average time an entity spends in the system.

Worked Example: Daraz Delivery Queue

• Arrival rate (λ): 20 orders/hour.
• Service rate (μ): 25 orders/hour (one delivery agent).
• Utilization (ρ): $\rho =\frac{20}{25}=0.8$.
• Average queue length (Lq): $L_q=\frac{0.8^2}{1-0.8}=3.2$ orders waiting.
• Average waiting time (Wq): $W_q=\frac{3.2}{20}=0.16$ hours = 9.6 minutes.

Visual: Daraz Delivery Queue Metrics

Common Queuing Models

1. M/M/1 Queue

• M: Markovian (Poisson arrivals, exponential service times).
• M: Markovian service.
• 1: Single server.

Steady-state probabilities: $$P_n=(1-\rho ){\rho }^n\text{for }n=0,1,2,\dots$$ where $\rho =\frac{\lambda }{\mu }$.

Example: eSewa Customer Support

• λ = 15 calls/hour, μ = 20 calls/hour.
• ρ = 0.75.
• Probability of 0 calls in the system: $P_0=1-\rho =0.25$ (25%).
• Probability of ≥3 calls waiting: $P_3+P_4+\cdots ={\rho }^3=0.4219$ (42.19%).

2. M/M/c Queue

• c: Multiple servers (e.g., NTC call center with 5 agents).

Utilization per server: $\rho =\frac{\lambda }{c\mu }$. Average queue length: $$L_q=\frac{P_0(\lambda /\mu {)}^c\rho }{c!(1-\rho {)}^2}$$ where $P_0$ is the probability of an empty system.

Example: NTC Call Center

• λ = 30 calls/hour, μ = 10 calls/hour/agent, c = 4 agents.
• ρ = 30 / (4 × 10) = 0.75.
• Lq ≈ 1.875 calls waiting on average.

3. M/M/1/K Queue (Finite Capacity)

• K: Maximum queue size (e.g., hospital with 10 beds).

Blocking probability: Probability a new arrival is rejected. $$P_{\text{block}}=P_K=\frac{(1-\rho ){\rho }^K}{1-{\rho }^{K+1}}$$

Example: Kathmandu Traffic Light System

• Assume a single "server" (green light) with:
  • λ = 20 cars/minute, μ = 25 cars/minute, K = 5 cars.
• ρ = 20/25 = 0.8.
• Probability of blocking (6th car arrives when 5 are waiting): $P_5=\frac{(1-0.8)\times 0.8^5}{1-0.8^6}\approx 0.262$ (26.2%).

Applications in Real World

1. E-Commerce: Daraz Order Fulfillment

• Queuing model: M/M/c (multiple warehouses = servers).
• How it works:
  • Orders arrive as Poisson processes (λ).
  • Warehouses process orders at rate μ per server.
  • Goal: Minimize $W_q$ (delivery delay) by optimizing $c$ (number of warehouses).
• Real impact: Daraz uses priority queues for high-value orders (e.g., electronics) to reduce $W_q$.

2. Telecom: Ncell Network Traffic

• Queuing model: M/M/1 (base station tower as a single server).
• How it works:
  • Calls arrive at rate λ (e.g., 50 calls/hour/tower).
  • Tower processes calls at rate μ (e.g., 60 calls/hour).
  • Problem: If ρ > 1, calls are dropped (network congestion).
• Real impact: Ncell uses dynamic ρ monitoring to reroute calls during peak hours (e.g., 6–9 PM).

3. Banking: Khalti Transaction Processing

• Queuing model: M/M/c (multiple Khalti servers).
• How it works:
  • Transactions arrive as Poisson (λ = 1000 transactions/hour).
  • Servers process at μ = 500 transactions/hour/server.
  • Optimization: Khalti scales $c$ (servers) during Diwali sales to keep $W_q$ < 2 seconds.

4. Healthcare: Patan Hospital Emergency Room

• Queuing model: M/M/1/K (finite beds, K = 20).
• How it works:
  • Patients arrive at λ = 15/hour.
  • Doctors serve at μ = 10/hour.
  • Critical metric: $P_{\text{block}}$ (patients turned away due to full beds).
• Real impact: Hospital uses priority queues (triage system) to reduce $W_q$ for critical cases.

Worked Example: Pathao Driver Assignment

Scenario: Pathao has 10 drivers (servers) in Kathmandu. Riders request rides at an average rate of λ = 12 rides/hour. Each driver can accept μ = 2 rides/hour.

1. Calculate utilization per driver (ρ): $$\rho =\frac{\lambda }{c\mu }=\frac{12}{10\times 2}=0.6$$ (Each driver is busy 60% of the time.)

2. Average number of riders waiting (Lq): For M/M/c, use the formula: $$L_q=\frac{P_0(\lambda /\mu {)}^c\rho }{c!(1-\rho {)}^2}$$ First, compute $P_0$: $$P_0={\left[\sum _{n=0}^{c-1}\frac{(c\rho {)}^n}{n!}+\frac{(c\rho {)}^c}{c!(1-\rho )}\right]}^{-1}$$ Plugging in values: $$P_0\approx 0.0036$$ Now, $L_q$: $$L_q=\frac{0.0036\times (12/2{)}^{10}\times 0.6}{10!(1-0.6{)}^2}\approx 0.32\text{ riders waiting}$$

3. Average waiting time (Wq): $$W_q=\frac{L_q}{\lambda }=\frac{0.32}{12}\approx 0.027\text{ hours}=1.6\text{ minutes}$$

Conclusion: Pathao’s system is efficient, with riders waiting only 1.6 minutes on average. To reduce wait times further, Pathao could:

• Increase $c$ (hire more drivers).
• Optimize $\mu$ (train drivers to accept rides faster).

Advantages and Disadvantages of Queuing Systems

Exam Tip

What Examiners Look For

1. Correct notation: Always define $\lambda$, $\mu$, $\rho$, $L_q$, and $W_q$ clearly.
2. Model selection: Identify whether the system is M/M/1, M/M/c, or M/M/1/K and justify your choice.
3. Little’s Law: Use it to relate $L$, $\lambda$, and $W$. Many questions test this directly.
4. Numerical accuracy: Show all steps in calculations (e.g., computing $P_0$ for M/M/c).
5. Real-world tie-ins: Relate queuing theory to Nepalese examples (e.g., NTC, Khalti, Daraz) to earn extra marks.

Common Pitfalls

• Ignoring stability: If $\rho \ge 1$, the queue grows infinitely—always check $\rho <1$.
• Wrong formula: Mixing up $L_q$ and $L$, or $W_q$ and $W_s$.
• Unit mismatches: Ensure $\lambda$ and $\mu$ are in the same time units (e.g., per hour, per minute).

Sample Exam Question

*"A bank has a single teller (M/M/1) with arrival rate λ = 10 customers/hour and service rate μ = 12 customers/hour. Calculate:

1. The utilization factor (ρ).
2. The average number of customers in the queue (Lq).
3. The average waiting time (Wq). Assume the bank opens at 9 AM. If 5 customers arrive by 9:05 AM, what is the probability that all are served by 9:10 AM?"*

Solution Outline:

1. $\rho =\frac{10}{12}=0.833$.
2. $L_q=\frac{{\rho }^2}{1-\rho }=\frac{0.833^2}{0.167}\approx 4.17$.
3. $W_q=\frac{L_q}{\lambda }=0.417$ hours = 25 minutes.
4. Probability all 5 are served by 9:10 AM:
   • Time available: 5 minutes.
   • Service time per customer: $\frac{1}{\mu }=5$ minutes.
   • Probability all 5 finish in 5 minutes: 0 (since 5 × 5 = 25 minutes > 5 minutes).
   • Correction: Use exponential service times. Probability a customer is served in ≤5 minutes: $1-e^{-\mu t}=1-e^{-12\times (5/60)}\approx 0.918$. For 5 independent customers: $0.918^5\approx 0.63$ (63%).