# OR-Notes

## J E Beasley

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

Queuing theory deals with problems which involve queuing (or waiting). Typical examples might be:

• banks/supermarkets - waiting for service
• computers - waiting for a response
• failure situations - waiting for a failure to occur e.g. in a piece of machinery.

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:

• arrival process:
• how customers arrive e.g. singly or in groups (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)).
• service mechanism:
• a description of the resources needed for service to begin
• how long the service will take (the service time distribution)
• the number of servers available
• whether the servers are in series (each server has a separate queue) or in parallel (one queue for all servers).
• queue discipline:
• 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); LIFO (last-in first-out); randomly).

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, and 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 utilisation 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).

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:

• 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 analysed using simulation.

Other queueing theory information can be found here.

#### Queuing theory - presentation

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

• Qn be the queuing time for customer n (time spent waiting for service)
• Sn be the service time for customer n (time spent being served)
• In be the time between the arrival of customer n and the arrival of customer (n+1)

then Qn+1 = Qn + Sn - In (assuming FIFO queue discipline)

Traffic intensity = (arrival rate)/(departure rate)

where

• arrival rate = number of arrivals per unit time
• departure rate = number of departures per unit time.

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.

• arrival process - the simplest arrival process is one where we have completely regular arrivals (i.e. the same time interval between successive arrivals).

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).

• service mechanism - the service time is the time taken to serve a customer. Assuming that the service times for customers are independent and do not depend upon the arrival process is common.

A common assumption about service times is that they are exponentially distributed.

• queue discipline - 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.

Consider the example consisting of:

• Poisson arrival stream, mean inter-arrival time of one minute.

Hence arrival rate = number of arrivals per unit time = 1 customer per minute

• service mechanism consisting of three servers where the service time for each customer is exponentially distributed with a mean service time of 2 minutes.

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.