The Queuing Theory Model is the study of waiting lines or queues and its objective is to design a system that allows the optimized organization depending on some criteria, our possible criteria are: expected attention level or maximum gain.
The analysis of a queue system requires an adequate understanding of the service measure, the possible service measures are The probability of an arriving customer needing to wait to be attended, average customer service time, average queue length.
So, what are the elements of a queue?
A queue has three elements:
- Who arrives: It is the customer that arrives at the queue according to an arriving pattern and wants a service.
- Who waits in the queue: It is the customer that arrived and needs to wait in one or more queues to get attended to.
- The service: At this point, the customer gets the service and exits the queue.
Arriving Process
We have two types of arrival:
- Deterministic arriving process: The customers follow a pattern to arrive at the queue, E.g. The system gets 5 customers every 10 seconds
- Radom arriving process: This is the most common process in a company, the customers don’t follow a pattern to arrive at the queue, but under three conditions a Poisson distribution can describe the random process.
Poisson distribution conditions
- Continuity: At least one customer needs to arrive at the queue in a timeframe.
- Stationary: For a timeframe given, the probability that a customer arrives is the same for all the timeframes of the same length.
- Independency: The arrival of a customer doesn’t influence the arrival of another customer.
Note: Those conditions don’t limit the problem and can be satisfied in multiple situations.
Arrival Poisson distribution
The mathematical formula for the arrival Poisson distribution is the next:
Arrival Poisson Distribution
Where:
- λ is the expectation of the arrival of a customer per unit of time.
- t is the time interval
- e is the base of the natural logarithm (2.7182818)
- k is the number of customers.
- k! = k (k-1) (k-2) (k-3) … (3) (2) (1)
Let’s see an example:
Imagine that we have a local where 6 customers arrive on average between 8:00 am to 9:00 am, and we want to know the probability that k= 0,1,2 customers arrive the local between 8:00 am to 8:30 am.
What do we know?
- λ = 6 customers per hour
- t = 0.5 hours
- λt = (6)(0.5) = 3
So, for k = 0 we have:
For k = 1, we have:
For k = 2, we have:
What does that’s mean?
Following the Poisson distribution results, we can say that the probability that zero customers arrive at the local between 8:00 am to 8:30 am is 0.049787, or the probability that 1 customer arrives at the local is 0.149361, or the probability that 2 customers arrive at the local is 0.224042.
The waiting queue
There are many factors that affect a queue:
- The queue configuration: A queue can be configured as
- A single server queue
- Multiple service queues with a single queue
- Multiple service queues with multiple queues
- Tandem queues: This a system with multiple stages and queues
- Cheaters: These are the customers that move in the queue without advancing criteria
- Contrariness: This occurs when the customers avoid arriving at the queue because it is too large
- Priorities
- Homogeneity
Queues Priorities
This aspect defines the queue discipline and determines the next customer to be selected.
The common selection criteria are:
- First Come First Serve (FCFS)
- Last Come First Serve (LCFS)
- Random customer service
- Estimated attention time
Queues Homogeneity
A homogeneous customer population is one in which customers require essentially the same service.
And a non-homogeneous customer population is where the customers can be grouped by:
- Arrival patters
- Service type required.
Service Processes
Some service systems need a fixed attention time, but, in many cases, the attention time varies according to the number of customers, when this happens the attention time is a treaty as a random variable.
An exponential distribution could be used in some cases to model the customer attention time.
Attention Time Exponential distribution
The mathematical formula used for this distribution is the next:
where μ is the number of customers that can be served by timeframes.
And if we want to know the probability that the attention time X is less than t , we use the next formula:
Queues systems performance measures
The performance of a queue could be measured concentrating on:
- Amount of customers in the queue.
- Amount of customers in the system.
The measurement in transitory and static periods complicates the analysis of attention time.
Transitory period
A transitory period occurs at the beginning of the operation, and it isn’t indicated for a long execution period.
Stationary periods
This period follows the transitory one, and the probability to have N clients in the system doesn’t change while the time elapses.
Based on the latest definitions, an arrival rate could be less than the sum of the effective attention rates:
- For a single server: λ < μ
- For k servers: λ < μ1 + μ2 + … + μk
- For k servers with services rate μ each one: λ < kμ
Performance measures in a stationary period
- P_0: Probability that there are no customers in the system
- P_n: Probability that there are n customers in the system.
- L: average number of customers in the system.
- L_q: average number of customers in the queue.
- W: Average time spent by a customer in the system.
- W_q: Average time spent by a customer in the queue.
- P_w: Probability that an arriving customer must wait to be served.
- ρ: Usage rate of each server (percentage of time each server is busy).
Queues Classifications
The queues systems can be classified by:
Note: Each classification criteria has at the end its position on the representation example
- Customer arrival process (1)
- Attention process (2)
- Amount of servers (3)
- Length (finite/infinite waiting queues) (4)
- Population amount. (5)
Notation
both the arrival process and the attention process can have the following notation:
- M (Markovian): Poisson arrival process or exponential arrival process
- D (Determinists): constant arrival or attention rate
- G (General): General probability of arrival or attention.
Conclusions
The queue theory models give us an understanding of how the queues systems are created and how to measure their performance, this theory is widely used from bank queue systems to internet systems like the ISP networking interaction for a package navigating over it.
Recommendations
If you are interested in this topic, I would like to recommend to you some lectures and books:
- General Systems Theory A focus on computer science engineering -Dougglas Hurtado Carmona
- Introduction to Operations Research -Frederick S. Hillier; Gerald J. Lieberman
- QUEUEING THEORY AND MODELING
Top comments (0)