OR-Notes are a series of introductory notes on topics that fall under the broad heading of the field of operations research (OR). They were originally used by me in an introductory OR course I give at Imperial College. They are now available for use by any students and teachers interested in OR subject to the following conditions.
A full list of the topics available in OR-Notes can be found here.
Queuing theory deals with problems which involve queuing (or waiting). Typical examples might be:
In essence all queuing systems can be broken down into individual sub-systems consisting of entities queuing for some activity (as shown below).
Typically we can talk of this individual sub-system as dealing with customers queuing for service. To analyse this sub-system we need information relating to:
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:
These are questions that need to be answered so that management can evaluate alternatives in an attempt to control the situation. Some of the problems that are often investigated in practice are:
In order to get answers to the above questions there are two basic approaches:
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 analysed using simulation.
Other queueing theory information can be found here.
In this section we present brief notes highlighting the key points from the queuing theory presentation.
Queues are a common every-day experience.
Queues form because resources are limited.
It makes economic sense to have queues (c.f. how many supermarket tills you would need to avoid queuing).
Aim for a balance between service to customers (short queues implying many servers) and economic considerations (not too many servers).
System size = numbers of customers being served + number of customers in the queue
= total number of arrivals - total number of departures.
The system size represents the backlog of customers who are being served or who are waiting for service.
Let
then Qn+1 = Qn + Sn - In (assuming FIFO queue discipline)
Traffic intensity = (arrival rate)/(departure rate)
where
Traffic intensity is a measure of the congestion of the system. If it is near zero there is very little queuing and in general as the traffic intensity increases (to near 1 or even greater than 1) the amount of queuing increases.
Arrival process/service mechanism/queue discipline are the three important factors relating to the structure of queues. We consider these three factors in turn.
A Poisson stream of arrivals corresponds to arrivals at random. 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).
A common assumption about service times is that they are exponentially distributed.
Consider the example consisting of:
Hence arrival rate = number of arrivals per unit time = 1 customer per minute
Hence on average three (= number of servers) customers leave the system every 2 minutes and so the departure rate (= number of departures per unit time) = (3/2) customers per minute.
Hence the traffic intensity = (arrival rate)/(departure rate) = 1/(3/2) = (2/3)
Little's formula is: mean queue size = (arrival rate) x (mean queuing time)
One interesting result is that, for our above example, less queuing occurs with three servers than with one server working three times as fast.
Erlang in 1908 tackled the first queuing theory problem by looking 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.
Machines awaiting repair are like customers in a queue waiting for service. Queuing theory can be used to show that it is better for the repairmen to share the responsibility for all the machines as opposed to each man being responsible for just a few particular machines.
Simulation models can be used as a powerful technique for analysing (usually via the computer) complex queuing situations.
Entity-cycle diagrams can be used to help construct simulation models.