Queuing Theory

Understanding Kendall's Notation (A/S/c/K/N/Disc)

Notation Structure: Queue models use standardized Kendall notation describing six characteristics:

• A (Arrival Process): M = Markovian (Poisson), D = Deterministic, G = General
• S (Service Distribution): M = Exponential, D = Constant, G = General, Ek = Erlang-k
• c (Server Count): Number of parallel service channels (1, 2, ...)
• K (System Capacity): Maximum customers allowed (default ∞)
• N (Population): Calling population size (default ∞)
• Disc (Discipline): FIFO, LIFO, Priority, SIRO (default FIFO)

Markovian vs General Distributions: Markovian (M) assumes exponential distributions with memoryless property—future arrivals don't depend on past. This simplifies analytical solutions through Markov chain mathematics. General distributions (G) require more complex analysis but better represent real-world service variability.

Exponential Service Advantage: Exponential service distributions enable closed-form mathematical solutions because the memoryless property (remaining service time independent of elapsed time) creates tractable differential equations. Non-exponential service requires embedded Markov chains or approximation methods.

Model Selection Decision Framework

M/M/1 vs M/M/c Selection:

• Use M/M/1 for single-server systems (one ATM, one security checkpoint, single-machine work centers)
• Use M/M/c when multiple identical servers work in parallel (bank tellers, call center agents, multi-server retail checkout)
• General guideline: If utilization (ρ) exceeds 0.8 in M/M/1, consider adding servers (M/M/c) to prevent excessive queue growth

When to Use M/G/1: Select M/G/1 when service times follow non-exponential patterns—constant service (automated systems), lognormal (human tasks with learning curves), or empirical distributions. M/G/1 uses Pollaczek-Khinchine formula requiring only mean and variance, not full distribution specification.

Finite Capacity (M/M/1/K): Apply when physical constraints limit queue length (parking lots, call center trunk lines, buffer inventories). When K is reached, arriving customers are lost (blocked) or redirected.

Formula Interpretation & Little's Law

Utilization (ρ) as Congestion Risk: Utilization represents the proportion of time servers are busy, but more importantly serves as a congestion risk indicator. As ρ approaches 1, system stability degrades and queues grow without bound.

Stability Condition: The system becomes unstable (queues infinite) when ρ ≥ 1. For steady-state solutions, arrival rate must be strictly less than service rate (λ < μ or ρ < 1). This is the fundamental capacity constraint.

Steady-State Expectations: L, Lq, W, Wq represent long-run average (expected) values, not deterministic outcomes. Actual queue lengths and waiting times vary probabilistically around these means. High variance means customers experience waits significantly longer than average.

Little's Law Relationship: The fundamental theorem L = λW (and Lq = λWq) connects system metrics. It states that average number in system equals arrival rate multiplied by average time in system. This holds for all stable queue systems regardless of distribution assumptions.

Nonlinear Queue Growth: Queue length increases nonlinearly as utilization approaches 1. At ρ = 0.5, Lq = 0.5 customers. At ρ = 0.8, Lq = 4 customers. At ρ = 0.95, Lq = 19 customers. Small utilization increases cause exponential waiting growth—a 5% increase from 85% to 90% utilization more than doubles expected queue length.

Analytical Requirements for Valid Models

• Poisson Arrivals: Arrival processes assumed Poisson distributed (Markovian), meaning arrivals are random, independent, and occur at constant average rate. Inter-arrival times follow exponential distribution.
• Exponential Service (M/M): Service times assumed exponentially distributed for M/M models. This implies high service time variability—some customers take much longer than others. Constant service times (D) or general distributions (G) require different models.
• Steady-State Conditions: System must reach equilibrium where performance metrics stabilize. Transient analysis (startup periods, sudden demand spikes) requires simulation or time-dependent equations.
• Independent Arrivals: Customers assumed independent—one customer's arrival doesn't influence another's. Balking (customer sees long queue and leaves) and reneging (customer abandons queue) violate this assumption.
• FIFO Discipline: Service discipline typically First-In-First-Out (FIFO). Priority queues, processor sharing, or last-in-first-out require different analytical approaches.
• Infinite Population: Standard models assume infinite calling population. Finite population models (limited potential customers) apply when arrival rate depends on how many are already in service.