Introduction to queuing system
1.1 Description of the Queueing Problem
Queueing problems are encountered when the demand for a service exceeds its immediate availability. Real-life examples include:
- Supermarkets: Customers waiting in line to check out.
- Call Centers: Callers put on hold during high traffic periods.
- Airports: Aircrafts waiting in line for take-off clearance.
In each case, the cost of providing enough capacity to prevent waiting may be economically infeasible. Queueing theory provides a mathematical approach to evaluate the performance of such systems. It helps decision-makers design, analyze, and optimize systems to achieve a trade-off between service quality and cost.
Historical Note: A.K. Erlang, working for the Copenhagen Telephone Exchange, pioneered this field in the early 1900s. His work laid the foundation for modern-day telecommunication network design and many service systems.
1.2 Characteristics of Queueing Processes
A queueing process can be described by six key characteristics:
Arrival Pattern: Describes the nature of customer arrivals, typically modeled as a stochastic process. The Poisson process is the most common.
- Real-life: Patients arriving at a hospital emergency room.
- Can be stationary (time-independent) or non-stationary (time-dependent).
Service Pattern: Time taken to serve customers; usually modeled using exponential, deterministic, or general distributions.
- Real-life: Varying time taken by bank tellers depending on the transaction.
- Can include batch service or service that depends on the current state of the system.
Queue Discipline: The rule by which customers are selected for service.
- Examples include FCFS, LCFS, Priority-based, Random Selection.
- Preemptive vs. Non-preemptive priorities affect how interruptions are handled.
System Capacity: Maximum number of customers allowed in the system (in service + in queue).
- Finite: Elevators, small waiting rooms.
- Infinite: Theoretical models often assume infinite capacity for mathematical tractability.
Number of Servers:
- Single-server: One service channel (e.g., a single ATM machine).
- Multi-server: Multiple parallel channels (e.g., multiple checkout counters).
Number of Service Stages:
- Single-stage: Fast food pickup.
- Multi-stage: Vehicle inspection, where each station represents a different stage (brakes, emission, etc.).
- Can include feedback or re-routing based on intermediate outcomes.
1.3 Notation
Kendall notation: A/B/C/D/E
- A: Arrival time distribution (M = Markov/Exponential, D = Deterministic, G = General)
- B: Service time distribution
- C: Number of servers
- D: System capacity
- E: Queue discipline
Example: M/M/1/∞/FCFS = Exponential interarrival and service time, 1 server, infinite capacity, first-come-first-served.
In practice, only the first three parameters (A/B/C) are often used unless the system has a special capacity or discipline. The notation helps in standardizing models and simplifies the communication of complex queue configurations.
1.4 Measuring System Performance
Performance is typically measured using:
- L: Average number of customers in the system (queue + service)
- Lq: Average number of customers in the queue
- W: Average time a customer spends in the system
- Wq: Average time a customer waits in the queue
These values are generally considered in the steady-state (long-run) scenario. Other metrics include server utilization, probability that a customer has to wait, and probability that the system is empty.
Example: In an amusement park, reducing Wq improves customer satisfaction, even if the total service time W remains constant.
1.5 Some General Results
Traffic Intensity (ρ) = λ / (c * μ)
- Where λ = arrival rate, μ = service rate, c = number of servers
- If ρ ≥ 1, the queue grows indefinitely in the long run (unstable system)
Little's Law:
- L = λ * W
- Lq = λ * Wq
These laws are surprisingly general and do not require specific distributional assumptions. They are essential tools in queueing analysis.
Other key results include:
- Server Utilization: The fraction of time a server is busy.
- Probability of n customers in the system (Pn): Derived using steady-state balance equations.
- Busy Period: Time from when the system becomes busy until it becomes empty again.
1.6 Simple Data Bookkeeping for Queues
Track each customer:
- Arrival time
- Service start time
- Departure time
- Waiting time in queue
- Total time in system
Example Table:
| Customer | Arrival | Service Start | Departure | Wait Time | Service Time |
|---|---|---|---|---|---|
| A | 0 | 0 | 3 | 0 | 3 |
| B | 2 | 3 | 6 | 1 | 3 |
Using event-driven simulations, queueing systems are modeled and evaluated in real-time. This approach helps simulate complex systems without closed-form analytical solutions.
1.7 Poisson Process and Exponential Distribution
The Poisson process models random arrivals over time:
- Probability of k arrivals in time t: P(k) = (λt)^k * e^(-λt) / k!
The Exponential Distribution models the time between arrivals:
- Probability density function: f(t) = λ * e^(-λt)
Properties:
- Memorylessness
- Mean = 1/λ
- Variance = 1/λ^2
Example: The number of cars arriving at a toll booth every minute follows a Poisson process, while the time between two successive arrivals is exponentially distributed.
1.8 Markovian Property of the Exponential Distribution
The exponential distribution has the memoryless property:
- P(T > s + t | T > s) = P(T > t)
This implies that the remaining time until the next event does not depend on how much time has already passed. Only the exponential (continuous) and geometric (discrete) distributions have this property.
This property simplifies the mathematical treatment of queueing systems and is the foundation for continuous-time Markov chains.
1.9 Stochastic Processes and Markov Chains
- Stochastic Process: A collection of random variables indexed by time.
- Markov Process: A stochastic process where the future state depends only on the current state (memoryless property).
Types:
- Discrete-time Markov Chains (DTMC): Transitions happen at fixed intervals.
- Continuous-time Markov Chains (CTMC): Transitions occur at any continuous point in time.
Markov chains are used to model a wide variety of queueing systems. They can represent transitions among queue sizes, service completions, and arrivals.
1.10 Introduction to QtsPlus Software
QtsPlus is an educational and analytical software tool designed for modeling and analyzing queueing systems.
Features:
- Solves classical queueing models like M/M/1, M/M/c, M/M/c/K, etc.
- Computes steady-state probabilities, average waiting times, queue lengths, and server utilizations.
- Allows users to visualize and experiment with different input parameters.
Usage:
- Ideal for students and researchers to verify theoretical calculations
- Simulates the effect of changing service rate or number of servers
Real-Life Applications Summary:
| Scenario | Queue Model | Type |
|---|---|---|
| Supermarket | M/M/c | Multi-server |
| Customer Support Hotline | M/M/1 | Single-server |
| Hospital Emergency Room | M/M/c + Priority | Priority Queue |
| Fast Food Pickup | M/D/1 | Deterministic |
| Airport Runway Scheduling | M/M/1 with balking/reneging | State-dependent |
End of Notes for Chapter 1.