Knowledge Base & Community Wiki
Queuing Theory – Introduction
Queuing theory provides us tools to deal with problems which involve queuing or waiting. Typical examples might be:
- Banks or Supermarkets where customers wait to be serviced
- Web applications where users submit a query and are wait for a response
- Public transport where users wait in lines for the trains or busses to arrive
As we all agree queues are a common every-day experience. Queues form because resources on any given system are limited. In fact it makes economic sense to have queue built into a system. Queues help manage the traffic into and out of the system while optimizing how the system resources are allocated to user requests.
For example how many supermarket use till and queues in front of them to manage customer who need to be services. Have a think and work out how many customer tills you would need at your local supermarket to avoid queuing at peak times and if was feasible to maintain those tills throughout the year? How many buses or trains would be needed if queues were to be avoided/eliminated across all stations and bus depots?
In designing queuing systems we need to aim for a balance between service to customers (short queues implying many servers) and economic considerations (not too many servers). It’s not always possible to build and design queuing systems to deliver zero wait times. Queuing theory is the science of working out the appropriate balance between wait times and cost of the wait times for a particular service. All queuing systems can be broken down into individual sub-systems consisting of entities queuing for some activity:
Typically we can talk of the above system as dealing with customers queuing for service. To analyse this system we need information relating to:
- How customers arrive e.g. singly or in groups (batch or bulk arrivals)
- How the arrivals are distributed in time (e.g. what is the probability distribution of time between successive arrivals (the inter-arrival time distribution))
- Whether there is a finite population of customers or (effectively) an infinite number
The simplest arrival process is one where we have completely regular arrivals (i.e. the same constant time interval between successive arrivals). A Poisson (en.wikipedia.org/wiki/Poisson_distribution) stream of arrivals corresponds to arrivals at random. In a Poisson stream successive customers arrive after intervals which independently are exponentially distributed.
The Poisson stream is important as it is a convenient mathematical model of many real life queuing systems and is described by a single parameter – the average arrival rate. Other important arrival processes are scheduled arrivals; batch arrivals; and time dependent arrival rates (i.e. the arrival rate varies according to the time of day).
- Service center provides for a description of the resources needed to deliver the service i.e. number of customer service agents in a bank, number of cpu’s in a computer, etc.
- How long the service will take to complete including the service time distribution (i.e. exponential distribution, etc.)
- The number of servers available to provide the service
- Whether the servers are in series (i.e. each server has a separate queue) or in parallel (i.e. one queue for all servers)
- Whether pre-emption is allowed (i.e.a server can stop processing a customer to deal with another “emergency” customer)
Assuming that the service times for customers are independent and do not depend upon the arrival process is a common and important assumption. Another common assumption about service times is that they are exponentially distributed.
- The approach to serve customer requests i.e. how, from the set of customers waiting for service, do we choose the one to be served next (e.g. FIFO (first-in first-out) – also known as FCFS (first-come first served); LIFO (last-in first-out); randomly) (this is often called the queue discipline)
- Does the system include the following characteristics: Balking (customers deciding not to join the queue if it is too long), Reneging (customers leave the queue if they have waited too long for service), Jockeying (customers switch between queues if they think they will get served faster by so doing)
Changing the queue discipline (the rule by which we select the next customer to be served) can often reduce congestion. Often the queue discipline “choose the customer with the lowest service time” results in the smallest value for the time (on average) a customer spends queuing.
Probability of outcomes:
Note here that integral to queuing situations is the idea of uncertainty in, for example, inter-arrival times and service times. This means that probability and statistics are needed to analyse queuing situations. In terms of the analysis of queuing situations the types of questions in which we are interested are typically concerned with measures of system performance and might include:
- How long does a customer expect to wait in the queue before they are served?
- How long will they have to wait before the service is complete?
- What is the probability of a customer having to wait longer than a given time interval before they are served?
- What is the average length of the queue?
- What is the probability that the queue will exceed a certain length?
- What is the expected utilization of the server and the expected time period during which he will be fully occupied?
Remember servers cost us money so we need to keep them busy. In fact if we can assign costs to factors such as customer waiting time and server idle time then we can investigate how to design a system at minimum total cost. These are questions that need to be answered so that designers of the system can evaluate alternatives in an attempt to control/improve the situation. Some of the problems that are often investigated in practice are:
- What is the average length of the queue?
- Is it worthwhile to invest effort in reducing the service time?
- How many servers should be employed?
- Should priorities for certain types of customers be introduced?
- Is the waiting area for customers adequate?
In order to get answers to the above questions there are two basic approaches:
- Analytic methods or queuing theory (formula based); and
- Simulation (computer based).
The reason for there being two approaches (instead of just one) is that analytic methods are only available for relatively simple queuing systems. Complex queuing systems are almost always analyzed using simulation (more technically known as discrete-event simulation).
The simple queuing systems that can be tackled via queuing theory essentially:
- Mostly consist of just a single queue
- System which are linked where customers pass from one queue to another cannot be tackled via queuing theory
- Have distributions for the arrival and service processes that are well defined (e.g. standard statistical distributions such as Poisson or Normal)
- Systems where these distributions are derived from observed data, or are time dependent, are difficult to analyze via queuing theory
The first queuing theory problem was considered by Erlang in 1908 who looked at how large a telephone exchange needed to be in order to keep to a reasonable value the number of telephone calls not connected because the exchange was busy (lost calls). Within ten years he had developed a (complex) formula to solve the problem.
Modelling Solution: VisualizeIT offers access to a bunch of Analytical Models, Statistical Models and Simulation Models. Access to all the Analytical (Mathematical) models is free. We recommend you try out the Analytical models at VisualizeIT which are free to use and drop us a note with your suggestions, input and comments. You can access the VisualizeIT website here and the VisualizeIT modelling solution here –VisualizeIT.