Queuing theory is a mathematical study that delves into the analysis of waiting lines or queues. This field of study helps in understanding and modelling how queues form, how long they last, and how they can be managed effectively. The importance of queuing theory is evident in various real-life scenarios, such as managing customer service lines, traffic flow, and even telecommunications.
The foundation of queuing theory was laid by A.K. Erlang, who worked with the Copenhagen Telephone Company in the early 20th century.
He developed the first models to determine the optimal number of telephone circuits required to minimize customer wait times while balancing the cost of service. This work highlighted the broader applicability of queuing theory across different industries and systems.
Table of contents
What is Queueing Theory?
Queueing theory was pioneered by A.K. Erlang in 1909, specifically in the context of analyzing telephone traffic. The fundamental purpose of this theory is to determine an optimal level of service that minimizes both the cost of idle service capacity (e.g., employees or machines that are not in use) and the cost of waiting (e.g., customer dissatisfaction or lost business).
For example, if a hospital’s emergency room frequently has long queues, it might indicate insufficient service capacity, leading to potentially severe consequences for waiting patients.
Basic Concepts of Queuing Theory
- Queuing Model: A queuing model mathematically represents a queuing system. It typically includes components such as the arrival process, which describes how customers arrive. The model also covers the service mechanism, detailing how customers are served, and the queue discipline, which determines the order in which customers are served. These models are crucial for analyzing different types of queuing systems and predicting their behaviour.
- Key Components:
- Input Source: This refers to the origin of customers in the system. The input source can either be finite or infinite, depending on the number of potential customers.
- Queue Discipline: This defines the rule by which customers are selected for service. Common disciplines include First In First Out (FIFO), Last In First Out (LIFO), and priority-based selection.
- Service Mechanism: This describes the process of serving customers, including the number of service channels and the nature of the service provided.
- Probabilistic Background: Queuing theory relies heavily on probability theory, particularly the Poisson and exponential distributions. People commonly use the Poisson distribution to model the arrival of customers. The exponential distribution models service times.
Random Variables and Probability Distributions
A random variable is a numerical outcome of a random process or experiment, such as the number rolled on a die. The probability distribution of a random variable describes the likelihood of each possible outcome. For example, the Poisson distribution is often used to model the number of arrivals at a service point in a given time period.
Stochastic Processes
A stochastic process is a sequence of random variables indexed by time. These can be discrete like the outcome of a die roll repeated over time, or continuous, like the temperature at a particular location over time. We typically model queueing systems as stochastic processes. In these models, customer arrivals and service provisions are random events.
The Poisson Process
The Poisson process is a particular type of stochastic process that is fundamental to queueing theory. It describes situations where events occur independently and at a constant average rate over time. Examples include the arrival of telephone calls at a switchboard or patients at a clinic.
In a Poisson process:
- The number of events occurring in disjoint time intervals is independent.
- The probability of more than one event occurring in a very short time interval is negligible.
- The probability of exactly one event occurring in a small time interval is proportional to the length of the interval.
These properties make the Poisson process a useful model for many queueing situations, where arrivals are random and the time between arrivals follows an exponential distribution.
The Exponential Distribution
The exponential distribution closely relates to the Poisson process. It models the time between successive events in a Poisson process. If the number of arrivals follows a Poisson distribution, then the time between consecutive arrivals follows an exponential distribution.
This distribution is important because it simplifies the analysis of queueing systems, particularly when determining the average waiting time and the probability of a certain number of customers in the system.
The Markov Process and Birth-Death Processes
A Markov process is a type of stochastic process where the future state of the system depends only on the current state, not on the sequence of events that preceded it. The memoryless property simplifies the analysis of Markov processes, leading to their common use in queueing theory.
A special case of the Markov process is the birth-death process, which models systems where the only possible transitions are to adjacent states. In queueing terms, a new customer might arrive, representing a “birth.” A “death” represents when a customer departs after being served.
This process is particularly useful for modelling simple queueing systems where arrivals and departures occur one at a time.
Assumptions in Queueing Models
When formulating a queueing model, it is important to specify the assumed probability distributions of both the inter-arrival times (time between successive arrivals) and service times (time taken to serve a customer). Common assumptions include:
- Poisson arrivals: The number of arrivals in any time period follows a Poisson distribution.
- Exponential service times: The time taken to serve a customer follows an exponential distribution.
These assumptions enable us to develop simple yet powerful models that we can analyze using tools from probability theory.
Types of Queueing Models
There are various types of queueing models, each suited to different scenarios. Some common models include:
1. M/M/1 Queue
- M: Stands for “Markovian” and indicates that both the inter-arrival times and service times are exponentially distributed.
- 1: Indicates there is a single server.
- This model simplifies queueing by assuming that both arrivals and service times are random, following Poisson and exponential distributions, respectively.
2. M/M/c Queue
- Similar to the M/M/1 queue, but with multiple servers (c servers).
- This model is useful for systems like bank tellers or hospital emergency rooms where multiple servers (e.g., tellers, doctors) are available.
3. M/D/1 Queue
- Here, the service times are deterministic (fixed) rather than random, while arrivals are still Poisson distributed.
- This model applies in situations where the service time is predictable, such as a car wash or an automated machine.
Key Performance Measures
Queueing theory provides several key performance measures to evaluate the effectiveness of a queueing system, including:
- Average Queue Length: This represents the average number of customers waiting in line.
- Average Waiting Time: Measures how long a customer waits before being served.
- Probability of n Customers in the System: Indicates the likelihood that exactly n customers are either in the queue or being served at a given time.
- Traffic Intensity (ρ): Calculated as the ratio of the arrival rate (λ) to the service rate (μ), showing how busy the system is. If ρ exceeds 1, the system becomes overloaded, leading to increased waiting times.
- Utilization (Us): Reflects the proportion of time the server is busy. For a single-server system, you calculate utilization as ρ. In a multi-server system, you find utilization by dividing ρ by the number of servers (m).
- Throughput: Measures the average number of customers served per time unit. In a multi-server system, you determine throughput by multiplying m, ρ, and μ.
- Average Waiting Time (Wq): Captures how long, on average, a customer waits in the queue before being served.
- Average Number of Customers in the System (L): Includes both those waiting in the queue and those being served.
- Idle Time: Indicates the proportion of time when the server is not busy, and no customers are in the system.
Applications of Queueing Theory
Queueing theory has a wide range of applications across various industries:
- Healthcare: Managing patient flow in hospitals and optimizing the allocation of resources like doctors and nurses.
- Telecommunications: Designing efficient call centres and data networks to minimize delays and dropped calls.
- Transportation: Managing traffic at intersections, optimizing the scheduling of public transport, and reducing congestion at airports.
- Manufacturing: Streamlining production processes by reducing bottlenecks and minimizing downtime.
Case Study: Queuing System at a Bank
To illustrate the application of queuing theory, consider a bank that wants to optimize its customer service operations. The bank’s management is concerned about long wait times during peak hours, leading to customer dissatisfaction.
Using a basic M/M/1 queuing model, the bank can analyze its current system:
- Arrival Rate (λ): The average number of customers arriving at the bank per hour.
- Service Rate (μ): The average number of customers that can be served per hour by a teller.
By calculating the traffic intensity (ρ) and utilization (Us), the bank can determine whether its current system is adequate. If ρ is close to or greater than 1, it indicates that the system is overloaded, and additional tellers may be needed.
The bank can also calculate the average waiting time (Wq) and average number of customers in the system (L) to assess the impact of any changes, such as adding more tellers or extending operating hours.
Final Words
Queueing theory powerfully analyzes and optimizes systems involving waiting. By understanding the probabilistic nature of arrivals and service times, and by using models like the M/M/1 or M/D/1 queue, organizations can make informed decisions to improve efficiency and reduce costs.
The principles of queueing theory are widely applicable, making it an essential area of study for anyone involved in operations management, logistics, or any field where service provision and customer satisfaction are critical.
About Six Sigma Development Solutions, Inc.
Six Sigma Development Solutions, Inc. offers onsite, public, and virtual Lean Six Sigma certification training. We are an Accredited Training Organization by the IASSC (International Association of Six Sigma Certification). We offer Lean Six Sigma Green Belt, Black Belt, and Yellow Belt, as well as LEAN certifications.
Book a Call and Let us know how we can help meet your training needs.
