In this article, we will learn about Queueing Theory and its practical applications. We all have experienced the annoyance of having to wait in a queue. We wait in line at supermarkets to check out, we wait in line in banks and post offices and we wait in line at fast food restaurants. But we as customers do not like waiting. And the managers of these establishments also don’t like their customers to wait as it may cost them business.
So the first question that arises is that “Why is there waiting?”
To which the answer is that there is more demand for service that there is an available facility for that service.
And “Why is this so?”
For which there could be a number of reasons such as, shortage of available servers, limitation of space, economic limitations etc.
These limitations can be removed with the expenditure of capital. And to know how much service should then be made available, one needs to know:
- How many people will form the queue?
- How long must a customer wait?
Queuing theory attempts to answer these questions through detailed mathematical analysis. The ultimate goal is to achieve an economic balance between cost of service and the cost associated with the waiting for that service.
Basic Structure Of A Queuing System
A Queuing system can be described as one in which customers are arriving for service, waiting for their service if it is not immediately available and if having waited for service leaving the system after being served.
The term ‘customer’ is used in general sense and does not imply necessarily a human customer. For example, a customer can be a computer program waiting to be run or an airplane waiting in line to take off.
Queuing Theory was developed to provide models to predict the behavior of systems that attempt to provide service for randomly arising demands.
Characteristics Of Queuing System
For defining the characteristics we’ll first explain the following terms:
- Input Source: Also called as calling population. One of the main characteristics is its size, that is the total numbers of customers which may be finite or infinite (which is the default case).
- Queue: A queue is where customers wait before being served. It is characterized by the maximum permissible number of customers it can retain. The queue may be finite or infinite.
- Service Mechanism: Consists of one or more service facilities, each of which contains one or more parallel service channels, called servers. At a given facility, the customers enter one of the parallel service channels and are served by that customer.
In the context of above, there are six basic characteristics of a queuing process that provide an adequate description of a queuing system
1. Arrival Pattern: In general situations, the process of arrivals is random (stochastic). It is, therefore, necessary to know the probability distribution of the times between successive customer arrivals (inter-arrival times). Also, the customers can arrive simultaneously (batch or bulk arrival) and if so, the probability distribution describing the size of the batch.
The reaction of the customer upon entering the system.
- Balking: If the queue is too long and the customer decides not to enter the queue upon arrival, the customer is said to have balked.
- Reneged: A customer may enter a queue, but after a time loses patience and decides to leave, in this case, the customer is said to have reneged.
- Jockey: If there are two or more parallel waiting for lines customers may switch from one another that is the jockey for position.
2. Service Patterns: We need to describe a probability distribution for the sequence of customer service time. Service may be single or in batch, there are many situations where customers may be served simultaneously by the same server, such as people boarding a train, sightseers on a guided tour. The situation in which service depends on the number of customers waiting is referred to as State-Dependent service.
3. Queue Discipline: It refers to the manner in which the customers are selected for service when a queue has formed. Most common disciplines are:
- FCFS (FIFO): First come, first served/ First in, first out.
- LCFS (LIFO): Last come, first served/ Last in, first out.
- RSS: Random Selection of Service independent of the time of arrival to the queue
- Preemptive Priority: The customer with the highest priority is allowed to enter service immediately even if a low priority is already in service.
- Non-Preemptive Priority: The highest priority customer goes to the head of the queue but cannot get into service until the customer presently in service is completed.
4. System Capacity: In some queuing process there is a physical limitation to the amount of waiting room so that when the line reaches a certain length, no further customers are allowed to enter until space becomes available as a result of service completion. This situation is referred to as finite queuing situation.
5. The number of Service Channels: By this, we are typically referring to the number of parallel service stations which can serve customers simultaneously. It is assumed that service mechanisms of parallel channels operate independently of each other.
6. Stages of Service: A queuing system may have only a single stage of service, or it may have several stages. An example of a multistage the queuing system would be a physical examination procedure, where each patient must proceed through several stages, such as medical history, blood tests etc.
A Queueing process is described by a series of symbols and dashes such as A/B/X/Y/Z where
- A: Interarrival time distribution
- B: Probability distribution of service times
- X: Number of parallel service channels
- Y: Restriction on system capacity
- Z: Queue discipline
Some standard symbols for the characteristic distributions are as follows
- M: Exponential/Markovian
- Ek: Erlang type
- D: Deterministic
- Hk: Mixture of k exponential
- G: General distribution
These notations are referred to as Kendall’s Notation.
Generally, there are three types of system response of interest:
- Some measures of waiting time.
- An indication of the manner in which the customers may accumulate.
- A measure of the idle time of servers.
Since most queuing systems are stochastic, these measures are often random variables and their probability distribution is desired.
There are two types of customer waiting times:
- Time a customer spends in the queue.
- Total time a customer spends in the system (queue and service).
The task of a Queuing Analyst if generally one of the two things:
- To determine the values of appropriate measures of effectiveness.
- To design an optimal system (Tradeoff between customer service versus the expense of providing more service capability)
- State of the system: Number of customers in the queuing system
- Queue length: Number of customers waiting for service to begin
- N (t) = Number of customers in the queuing system at time t.
= Ns (t) + Nq (t)
- Pn (t) = Probability of exactly n customers in system at time t
= P [N (t) =n]
- C = Number of parallel service channels in the queuing system
- λn = Mean arrival rate, of new customers when n customers are in the system, the expected number of arrivals per unit time. When λn is constant for all n, it is denoted by λ.
(1/ λ) is the expected inter arrival time.
- µn = Mean service rate when n customers are in the system, the expected number of customers completing service per unit time. µn represents the combined rate at which all busy servers achieve service completions. When mean service rate per busy server is a constant for all n ≥ 1, this constant is denoted by µ.
µn = cµ when n ≥ 1 (all servers are busy). 1/µ is the expected service time.
- Transient condition: When a queuing system has recently begun, the state of the system will be greatly affected by the initial state and by the time that has since elapsed.
- Steady State condition: After a sufficient time has elapsed the state of the system becomes essentially independent of the initial state and elapsed time. This condition is called as ‘Steady-State’. Queuing theory has tended to focus largely on the steady-state condition.
- pn = P[N=n]
= Probability of exactly ‘n’ customers in the queuing system.
Where, N is the random variable giving the number of customers in the system.
- L = Expected number of customers in the queuing system.
- Lq = Expected number of customers in queue or
= Expected queue length
- Wq = Mean waiting time in the queue.
= E (Tq) where Tq is a random variable denoting the time spent by the customer in the queue.
Also T = Tq + S, where S is the random variable denoting service time of a customer.
- ρ = (λ/cµ)
= A measure of ‘traffic intensity’ for the C-server queuing system. Also known as ‘Utilization factor’ for the service facility that is the expected fraction of time the individual servers are busy.
One of the most powerful relations in queuing given by John D.C. Little. This formula relates the steady-state mean system size to steady state average customer waiting times.
Little’s formula is:
- L = λW
- Lq = λWq
Also, since E (T) = E (Tq + S) = E (Tq) + E (S) or
W = Wq + (1/µ)
Hence it is necessary to find only one of the four expected values.