Queueing Theory: Systems, Disciplines, Measures & Real-World Applications

Core Concepts

1. What is a Queueing System?

A queueing system (or waiting-line system) is a mathematical model of a real-world scenario where customers (entities needing service) arrive, wait in a queue, and receive service from one or more servers. Key components:

graph TD
    A["Arrival Process"] --> B["Queue"]
    B --> C["Service Discipline"]
    C --> D["Server(s)"]
    D --> E["Departure Process"]
    E -->|"Feedback"| A

• Customers: Jobs, people, data packets, or any entity requiring service (e.g., users on eSewa, orders on Daraz).
• Servers: Resources providing service (e.g., bank tellers, Pathao drivers, NTC call centers).
• Queue: Waiting line (FIFO, LIFO, or priority-based).
• Arrival Process: How customers enter the system (e.g., Poisson arrivals in Ncell calls).
• Service Process: Time taken to serve a customer (e.g., Khalti payment processing time).

2. Queueing Disciplines (Service Rules)

How customers are selected for service:

Worked Example: eSewa Transaction Queue

• Scenario: 100 users submit eSewa payments in 1 hour. Average service time = 2 minutes.
• Discipline: FIFO (first payment processed first).
• Question: How many users are waiting after 10 minutes? Solution:
  • Served in 10 mins: $\frac{10}{2}=5$ users.
  • Remaining queue: $100-5=95$ users.

3. Kendall’s Notation for Queueing Systems

Standard notation to describe a queueing system: A/S/c/K/N

• A: Arrival process (e.g., M = Markovian/Poisson, D = Deterministic).
• S: Service time distribution (e.g., M = Exponential, D = Constant).
• c: Number of servers.
• K: Queue capacity (∞ = unlimited).
• N: Population size (∞ = infinite).

Examples:

1. M/M/1: Single-server system with Poisson arrivals and exponential service (e.g., Ncell customer support).
2. M/M/c: Multiple servers (e.g., bank with 3 tellers: M/M/3).
3. M/D/1: Poisson arrivals but fixed service time (e.g., automated Khalti transactions).

4. Performance Measures

Key metrics to evaluate queueing systems:

Worked Example: NTC Call Center

• Arrival rate (λ): 12 calls/hour.
• Service rate (μ): 15 calls/hour.
• Utilization (ρ): $\rho =\frac{12}{15}=0.8$ (80% busy).
• Average waiting time (Wq): $W_q=\frac{{\rho }^2}{1-\rho }\times \frac{1}{\lambda }=\frac{0.64}{0.2}\times \frac{1}{12}=0.267$ hours ≈ 16 minutes.

Why Stability Matters: If $\rho \ge 1$, the queue grows infinitely (e.g., Pathao drivers during peak hours if demand > supply).

5. Single-Server Queueing System (M/M/1)

Key Equations (Derived from Markov Chains)

1. Utilization: $\rho =\frac{\lambda }{\mu }$.
2. Probability of Empty System (P₀): $P_0=1-\rho$.
3. Average Queue Length: $L_q=\frac{{\rho }^2}{1-\rho }$.
4. Average Waiting Time: $W_q=\frac{\rho }{\mu -\lambda }$.

Worked Example: Coffee Shop Barista

• Arrival rate (λ): 1 customer every 3 minutes → $\lambda =\frac{20}{3}$ customers/hour.
• Service rate (μ): 1 customer every 2.5 minutes → $\mu =24$ customers/hour.
• Utilization (ρ): $\frac{20/3}{24}=\frac{20}{72}=0.278$.
• Average waiting time (Wq): $W_q=\frac{0.278}{24-(20/3)}=\frac{0.278}{17.33}\approx 0.016$ hours ≈ 1 minute.

Visualization of State Transitions:

stateDiagram-v2
    [*] --> State0: P₀ = 1 - ρ
    State0 --> State1: λ
    State1 --> State0: μ
    State1 --> State2: λ
    State2 --> State1: μ
    State2 --> State3: λ
    etc.

Note: This is a birth-death process (Markov chain).

6. Multi-Server Queueing System (M/M/c)

For c servers, the equations change:

• Utilization per server: $\rho =\frac{\lambda }{c\mu }$.
• Probability of Empty System (P₀): $P_0={\left[{\sum }_{n=0}^{c-1}\frac{(c\rho {)}^n}{n!}+\frac{(c\rho {)}^c}{c!}\cdot \frac{1}{1-\rho }\right]}^{-1}$.
• Average Queue Length (Lq): $L_q=\frac{P_0(c\rho {)}^c\rho }{c!(1-\rho {)}^2}$.

Worked Example: Bank with 3 Tellers

• λ: 18 customers/hour.
• μ: 6 customers/hour per teller.
• ρ: $\frac{18}{3\times 6}=1$ → Unstable! (Queue grows infinitely.)
• Solution: Add a 4th teller ($c=4$): $\rho =\frac{18}{24}=0.75$. Now stable.

7. Feedback Systems

A feedback system sends customers back to the queue after service (e.g., retries, rework). Example: Ncell customer calls back if issue isn’t resolved. Modeling:

• Use Markov chains with transition probabilities.
• Steady-state probabilities solve for long-term behavior.

Worked Example: Daraz Order Retry

• Scenario: 20% of orders fail and retry.
• Arrival rate (λ): 100 orders/hour.
• Service rate (μ): 120 orders/hour.
• Effective λ: ${\lambda }_{eff}=\lambda (1+p)=100\times 1.2=120$ orders/hour.
• Utilization (ρ): $\frac{120}{120}=1$ → Unstable!
• Fix: Increase server capacity to 150 orders/hour.

8. GPSS Basics (Simulation Tool)

GPSS (General Purpose Simulation System) models queueing systems using blocks:

Example GPSS Code for Coffee Shop:

GENERATE 3, 1      // Arrive every 3 minutes, ±1 min variance
QUEUE            // Join queue
SEIZE 1           // Take barista (server 1)
DELAY 2.5         // Service time = 2.5 minutes
RELEASE 1         // Free barista
TERMINATE         // End transaction

Output: GPSS simulates average waiting time, queue length, and utilization.

9. Real-World Applications

In the Real World

1. eSewa/Khalti Transactions

   • Idea: M/M/c queueing (multiple servers = payment gateways).
   • How: Transactions arrive as Poisson processes; servers process payments exponentially. High $\rho$ during festivals → system crashes if not scaled.

2. Daraz Order Fulfillment

   • Idea: Priority queueing (express orders jump ahead of standard).
   • How: Orders are prioritized by delivery time (SJF-like for urgent orders).

3. NTC Call Center

   • Idea: M/M/c with feedback (customers call back if unresolved).
   • How: Agents handle calls; unresolved calls re-enter the queue.

4. Pathao Driver Dispatch

   • Idea: Multi-server queue with dynamic arrivals (drivers = servers, riders = customers).
   • How: Algorithm assigns riders to nearest available driver (minimizes $W_q$).

5. Bank Loan Processing

   • Idea: M/G/1 queue (service times vary by loan complexity).
   • How: Simple loans (D) have faster service; complex loans (G) increase $W_q$.

10. Worked Example: Kathmandu Traffic Lights

Scenario:

• Cars arrive at a traffic light every 10 seconds (λ = 6 cars/minute).
• Light stays green for 30 seconds (μ = 2 cars/minute during green).
• Question: What’s the average waiting time for cars?

Solution:

1. Utilization (ρ): $\rho =\frac{\lambda }{\mu }=\frac{6}{2}=3$ → Unstable! (Queue grows infinitely.)
2. Fix: Extend green time to 15 seconds (μ = 4 cars/minute). $\rho =\frac{6}{4}=1.5$ → Still unstable.
3. Final Fix: Increase μ to 6 cars/minute (green time = 10 seconds). $\rho =1$ → Stable but infinite queue. Conclusion: Need multiple lanes (increase c) or adaptive timing.

Visualization:

graph LR
    A["Cars Arrive"] --> B["Queue"]
    B --> C["Green Light\nμ=6 cars/min"]
    C --> D["Red Light\nμ=0"]
    D --> B

Real Picture:

11. Advantages and Limitations of Queueing Theory

Exam Tip

How to Score Full Marks

1. Definitions:

   • Always define queueing system, utilization (ρ), and Kendall’s notation clearly.
   • Example: "A queueing system is a model where entities (customers) arrive, wait, and receive service from servers."

2. Kendall’s Notation:

   • Must include all 5 parameters (A/S/c/K/N) with units.
   • Example: "An M/M/3 queue has Poisson arrivals, exponential service, and 3 servers."

3. Performance Measures:

   • Memorize formulas for $L_q$, $W_q$, and $\rho$.
   • Stability condition: Always state $\rho <1$ for stability.

4. Worked Examples:

   • Show every step (e.g., calculate λ, μ, then ρ).
   • Relate to real-world (e.g., "This is like Pathao’s driver allocation system").

5. GPSS:

   • Describe blocks in order (GENERATE → QUEUE → SEIZE → DELAY → RELEASE).
   • Link to output (e.g., "TABULATE records average queue length").

6. Graphs and Diagrams:

   • Draw state transitions for Markov chains.
   • Label axes in performance graphs (e.g., "Queue Length vs. Arrival Rate").

7. Common Pitfalls:

   • Don’t assume $\rho <1$ without checking.
   • Distinguish M/M/1 vs. M/M/c equations.
   • For feedback systems, show how ${\lambda }_{eff}$ changes.

Past Exam Questions Covered

Final Checklist Before Exam

• Can you derive $L_q$ and $W_q$ for M/M/1?
• Can you map a real system (e.g., Daraz) to Kendall’s notation?
• Do you know when a system is unstable ($\rho \ge 1$)?
• Can you write a GPSS snippet for a given scenario?
• Can you explain feedback systems with an example?