Queueing Theory Slides

Queueing Theory
SIE 321 Probabilistic Models in Operations Research
Prof. Krokhmal
SIE 321 Queueing Theory Prof. Krokhmal 1 / 57

About Queueing Theory
Waiting lines are a part of everyday life
People wait in line to:

Buy a basketball game ticket
Make a bank deposit
Get a sandwich
...
Waiting lines occur in industrial settings when:

Airplanes wait to take off
Machines wait to be repaired
Patients wait to assigned into wards or to doctors
...
Americans spend an estimated 37,000,000,000 hours per year waiting in queues.
Queueing theory is the study of waiting in all these various guises.

Origins of Queueing Theory
Queueing theory originates at the beginning of the 20th century.
Seminal contributions were made by Agner Krarup Erlang (then as an employee of

Copenhagen Telephone Company).
First application to telephone engineering:

While working for CTC, Erlang was presented with the problem of determining how many
circuits were needed to provide an acceptable telephone service.
He also studied how many telephone operators were needed to handle a given volume of
calls. Most telephones exchanges then used human operators and cord boards to switch
telephone calls by means of jack plugs.

Goals and Methods of Queueing Theory
Queueing theory seeks to answer question such as:

How much time does a customer spend in line?
What proportion of time is a server (e.g., a call center staff) idle?
What is the average number of people/items waiting?
What is the probability distribution of the number of customers in the system?
What is the probability distribution of waiting time?
...
Queueing theory:
relies on queueing models to represent queueing systems.
studies these various models to derive formulas and insights for the corresponding queueing
systems.
helps to determine how to operate queueing systems in an efficient way.

More Examples of Queueing Systems
Commercial service systems:

Person-to-person: bank teller, checkout stands at grocery store, cafeteria line, ...
Other: home appliance install/repairs, vending machines, gas stations, ...
Transportation service systems:

Toll booth, traffic lights, airplanes waiting to take off, trucks waiting to be unloaded, parking
lots, ...
Interval service systems:

Material handling systems, maintenance crews, computer labs, ...
Social service systems:

Judicial systems, emergency rooms, low income housing, ...

Basic structure of queueing models
Queueing theory considers operations when people, materials, equipment,

etc., form waiting lines in order to receive service
public lines at cafeterias, check-out counters, etc
equipment to be repaired produces waiting line at service facilities
vehicles form waiting lines at toll gates, traffic signals

Input source (calling population)
The demand for service is the primary stimulus on the waiting-line system
There exists a population of individuals, units, etc., requiring service from time to time
The calling population can be thought as a group of items, some of which depart and join
the waiting line
computer customers: depending on time of day, etc., customers will call 1-800 support desk
machines/equipment: wear-out, usage rates will determine the mechanism for putting the
machines in waiting line for repair
The calling population, although limited, can be considered infinite under certain
conditions

Input source (calling population)
For arrival population to be considered infinite, the departure rate must be relatively small
comparing to the size of the population
In some cases, the proportion of the population requiring service may be fairly large
comparing to population itself
Then the population is seriously depleted by the departure of its members for service
Hence, the departure rate will not remain stable
Such cases are classified as finite waiting-line operations

The queue
The term queue refers to the customers that departed the population and are waiting for
service, but have note yet been serviced
The departure mechanism governs the rate at which individuals leave the population and
join the queue
A model of queueing system must describe the statistical pattern according to which
customers join the queue

The queue
The common assumptions are that the number of customers joining the queue is
described by Poisson distribution, or constant over time, etc.
This departure mechanism is responsible for the formation of the waiting line and the
need to provide service
Balking: sometimes, the customers needing service may refuse joining the queue (the
queue may be too long, etc)

Queue discipline
Usually, the waiting line is a discrete array of individuals (items)

Individuals or items joining the waiting line take a position in queue in accordance with a
certain waiting-line discipline
first come, first served (FCFS, or FIFO - first in, first out)
last come, first served (LIFO - last in first out)
random selection process
individual may remain in the queue for a period of time and then rejoin the population
(reneging)
The service mechanism
Service is the process of providing the activities required by the units in the waiting line
collecting a toll
filling an order
providing a necessary repair, etc.
The act of providing the service causes the waiting line to decrease by one unit
The rate at which units in line are serviced is assumed to be a parameter directly under
control of the decision maker
The service facility may consists of a single channel (server), or several servers in parallel
If it consists of only single channel, all arrivals must eventually pass through this channel
If several channels are provided, items may move from the waiting line into the first
channel that becomes empty
Time elapsed from service commencement to completion is called service time
Modeling of a queueing system requires that the service time must be specified: either
random with a particular distribution (e.g., exponential, gamma (Erlang)), or constant

Queueing theory goals
When a unit joins the waiting line, waiting cost is incurred
Increasing the service capacity (# number of servers) will lead to a reduction of both the
length of the line and waiting time for each service
Hence, waiting costs are reduced
On the other hand, increase in the service cost will occur
Thus, it is of interest to determine the minimum total cost (waiting cost and service cost)
for a waiting-line service system
Queueing theory enables one to determine the average number of customers in line,
average waiting time, etc and use these values for optimizing the design of service
enterprize

Queueing theory notation (Kendall-Lee notation)
Type of queueing system can be denoted as, for example, M=M=s

Number of servers
Distribution of service times
Distribution of interarrival times

where
M D exponential distribution (Markovian)
G D general distribution
D D deterministic, or degenerate distribution (constant times)
Ek D Erlang distribution with parameter k
Example: M=G=s is a queueing system with exponential interarrival times, general

service times, and s servers

Queueing theory notation
The following general notations will be used:
Term Meaning
State of system number of customers in the queueing system
Queue length number of customers waiting for service to begin
N.t / number of customers in the queueing system at time t
Pn .t / probability of exactly n customers in the system at time t
s number of (parallel) servers in the system
n mean arrival rate (average number of customers joining queue

per unit of time), when n customers are already in the system
n mean service rate for overall system (average number of customers

completing service per unit of time) when n customers are currently
in the system (Note: it is a combined rate of all busy servers)

Queueing theory notation
With respect to a steady-state queueing system, the following notations will be

used:
Term Meaning
1
P
LD nPn the expected number of customers in the system (both in the queue
nD0
waiting for service and being serviced)
1
P
Lq D .n s/Pn the expected queue length (excludes customers being served);
nDs
note: s is the number of servers
W waiting time in the system (random, different for all customers)
W D EW the expected waiting time in the system
Wq random waiting time in queue (excluding service time) for a customer
Wq D EWq the expected waiting time in the queue

Littles formulas
If n is the same for all n, n D , then for each queueing system in a

steady-state regime the following relations, known as Littles formulas, hold:
L D W
Lq D Wq
Furthermore, if the mean service time is constant .D 1=/ for all n, then the
expected waiting time W in the system is equal to the expected waiting time
Wq in the queue plus the mean service time 1 :
1
W D Wq C


Littles formulas
Proof:
Assume each arriving customer pays the system operator $1 per unit of time he/she
spends in the system
What is the long-run rate at which the system operator earns money?
From customers point of view:

Average amount of money paid by a customer is $W
Since arrival rate is , long-run rate of revenue is $W
From the operators point of view:

Since each customer in system pays $1 per unit of time in the system, the operator earns $L
on average
Long-run rate of revenue is $L
Equating these two quantities, we obtain L D W

Littles formulas
Remark: the previous argument carries through for:

Number of customers in queue:
Lq D Wq
where (as a reminder)
Lq D average number of customers waiting in line
Wq D average time a customer spends in line
Number of customers in service:

Ls D Ws
where
Ls D average number of customers in service
Ws D average time a customer spends in service

Birth-and-death processes
In the context of queueing theory, birth corresponds to arrival of a customer, and death
corresponds to the departure of a served customer.
The state N.t / of the system at any time t is equal to the total number of customers that
are either waiting for service or are being served.
Specifically, the birth-and-death queueing system model assumes:

Given N.t / D n, the current (at time t ) probability distribution of the remaining time until the
next birth (arrival) is exponential with parameter n .
Equivalently, we say that if there are n customers in the system at time t , the arrival rate of
new customers is n
Given N.t / D n, the current (at time t ) probability distribution of the remaining time until the
next death (service completion) is exponential with parameter n .
In other words, we say that if there are n customers in the system, then the customer service
rate is n .
At each moment of time, only one event can happen: either a arrival (birth) of one new
customer, or departure (death) of one serviced customer.
Thus, the from state n the system can make transition either to state n C 1 or n 1.


Steady-state solution:
n 1 n 2 1 0
Pn D Cn P0 ; where Cn D ; n 1;
n n 1 2 1
and
1
! 1
X
P0 D 1 C Cn :
nD1
Useful formulas can be obtained in the case when n D and n D s.
The traffic intensity factor is introduced as

D
s
If < 1, the system is considered to be stable

if 1, the customers arrive as fast or faster than they can be served, and the queueing
system explodes

Example: Massive Mall
Planning for construction of the proposed Massive Mall the largest shopping mall and
indoor golf course in the world includes determining the amount of customer parking
space to provide.
The planners for Massive Mall have a reliable number of parking spaces needed for mall
employees, but the number of customers desiring parking spaces at any time is unknown.
It is estimated that 1,000 customers per hour are arriving to the mall, and each customer
spends on average 3 hours in the mall
Solution: Queueing theory can be used to determine the required parking space
For the moment, it can be assumed that the parking space is infinite, and the mall planners
are only concerned with estimating how much of this space will be in use for the most time.

Example: Massive Mall

M/M/1: Single-server queueing systems
In a single-server system, s D 1 and n D ; n D , whence

n

Cn D D n

and
Pn D .1 /n
Then, the expected number of customers in the system is

1 1

nn D
X X
LD nPn D .1 / D
1
nD0 nD0
The expected number of customers in the queue

1
X 2 2
Lq D .n 1/Pn D L .1 P0 / D D
1 . /
nD0

M/M/1: Single-server queueing systems
Waiting time W in the queueing system is exponentially distributed with parameter
.1 /:
PfW > tg D e .1 /t ; for t 0
The expected time is given by

1 1
W D EW D D
.1 /
The waiting time in the queue Wq does not have exactly an exponential distribution
because
PfWq D 0g D P0 D 1 > 0
But the conditional distribution of Wq given that Wq > 0 is exponential with parameter
.1 /, just like the distribution of W :
PfWq > t j Wq > 0g D e .1 /t
The expected waiting time in the queue is equal to

Wq D EWq D
. /

Example: Drive-in banking
An average of 10 cars per hour arrive at a single-server drive-in teller. Assume that the average
service time for each customer is 4 minutes, and both interarrival and service times are
exponentially distributed
(a) What is the probability that the teller is idle?

(b) What is the average number of cars waiting in line?
(c) What is the average amount of time a drive-in customer spends in the banks drive-in?
(d) On the average, how many customers per hour will be served by the teller?

Example: Drive-in banking

Example: Gas station
Suppose that all car owners fill up their tanks when they are exactly half full. At the present time,
an average of 7.5 customers per hour arrive at a single-pump gas station. It takes an average of
4 minutes to service a car.
(a) Estimate the average waiting time and queue length

Example: Gas station
(b) Suppose that a gas shortage occurs and panic buying takes place. To model the panic
buying, suppose that all car owners now purchase the gas when their tanks are
three-quarters full. Since it takes less time filling up, assume that the average service
time has reduced to 3 1 3 minutes. How does it affect Lq and W ?

Example: Car washing facility
A car washing facility operates with one bay. Cars arrive on average every 15 minutes, and it
takes on average 10 minutes to wash one car. The manager is interested to determine the size
of parking lot such an arriving car would find a parking space at least 90% of the time

M/M/s: Multi-server queueing systems
When s > 1, we have for n D 0
1
D ; P0 D
s s sP1 r
1 1 1
s 1
C r
rD0
and for n 1
.=/n
8
P0 ; if 0 n s

n

<
Pn D
n
: .=/ P0 ;

if n s

s s s
n
The expressions for expected queue length and waiting time become
P0 .=/s 1
Lq D ; W D Wq C ;
s .1 /2

Lq 1
Wq D ; L D Wq C D Lq C


Example: Bank tellers
In a bank with two tellers, an average of 80 customers per hour arrive and wait in a single line
for the first available teller. The average time it takes to serve a good customer is 1.2 minutes.
(a) What is the expected number of customers present in the bank and how much time a
customer spends in the bank on average?

Example: Bank tellers
In a bank with two tellers, an average of 80 customers per hour arrive and wait in a single line
for the first available teller. The average time it takes to serve a good customer is 1.2 minutes.
(b) What fraction of time a particular teller is idle?

Example: Benefits of consolidation
A community is served by two cab companies. Each company owns two cabs and both share
the market equally, as evidenced by the fact calls for service arrive at each companys
dispatching office at the rate of eight per hour. The average time per ride is 12 minutes. The two
companies were recently bought by an investor, who is interested in consolidating them into a
single dispatching office. Is that beneficial to the community (assuming that pricing stays the
same)?

M/M/s/K: Queueing systems with finite queue
In many real-life situations, the queueing system cannot accommodate no more than K
customers.
Usually, it means that there is a limited room where the customers in the queue can wait
for service (e.g., waiting seats in a hair dressing salon), and when K customers are
present in the system, all other incoming customers will be balking, or turning away and
look for service someplace else.
In this case, the arrival rate can be modified as

(
; for n D 0; 1; 2; : : : ; K 1
n D
0; for n K

Observe that the traffic intensity factor D does not need to be less than 1, because
s
arrivals in the system are controlled by the system limit K .

Single-server finite-queue model, M/M/1/K
1
8

n ; 1
1 KC1

<
Pn D for n D 0; 1; : : : ; K

1

: ; D1
K C1
Then for 1 we have and for D 1 we have
.K C 1/KC1 K
n K
LD
X
1 1 KC1 LD D
K C1 2
nD0
Lq D L .1 P0 /
K 1
Lq D C 1
2 K C1

Single-server finite-queue model, M/M/1/K
Since some fraction of the arriving customers will be balking, we can define the effective
arrival rate eff as
eff D .1 PK /
and the rate at which customers balk as lost :
lost D PK
Since the arrival rate n depends on the number n of customers in the system, Littles
formulas do not apply!
However, the following modifications of Littles formulas hold for systems with finite queue,
where the arrival rate is replaced with the effective arrival rate eff :
L
W D
eff
Lq
Wq D
eff

Example: Car washing facility
Suppose that the car washing facility has 4 parking places. If the parking lot is full, all newly
arriving customers balk to other facilities. The owner wishes to determine how may customers
he loses to competition due to the limited parking space.

Multi-server finite-queue models, M/M/s/K
The expressions for probabilities Pn are

2 3 1
s K n s
X .=/n .=/s X
P0 D 4 C 5
n s s
nD0 nDsC1
and
.=/n
8

P0 ; n D 1; 2; : : : ; s
n

<
Pn D .=/n
P0 ; n D s; s C 1; : : : ; K
s s n s

0; n>K
:

Multi-server finite-queue models, M/M/s/K
The expressions for expected waiting time and queue length, etc:
P0 .=/s
K s
s/K s

Lq D 1 .K .1 /
s .1 /2
sX1 sX1
!
LD nPn C Lq C s 1 Pn
nD0 nD0
L
W D
.1PK /
Lq
Wq D
.1 PK /

Example: Consolidated cab company
Suppose that in the consolidated cab company new funds cannot be secured to purchase
additional cabs. The owner was advised by a consultant that one way to reduce the waiting time
is for the dispatching office to inform new customers of potential excessive delay once the
waiting list reaches 6 customers. This move is certain to get mew customers to seek service
elsewhere, but will reduce the waiting time for those on the waiting list. Assess the friends
advice.

Example: Reservations Office
The reservation office for a local car rental company has two agents answering incoming phone
calls for car rental reservations. In addition, one caller can be put on hold until one of the agents
is available to take the call. If all three phone lines (both agent lines and the hold line) are busy,
a potential customer gets a busy signal, in which case the call may go to car rental company.
The calls and attempted calls occur randomly (i.e., according to a Poisson process) at a mean
rate of 15 per hour. The length of a telephone conversation has an exponential distribution with
a mean of 4 minutes. Find the probability that
(a) A caller will get to talk to an agent immediately

(b) The caller will be put on hold, and
(c) The caller will get a busy signal

Example: Reservations Office

M/M/s/N/N: Queueing systems with finite population
This model usually applies to machine shops, etc., where the number of customers (i.e.,
equipment) that may ever require service, is finite.
We denote the size of calling population as N .
Since the calling population in such systems is usually small, then it is reasonable to
assume that the size K of the system can accommodate all N of its potential customers
.K D N /
In the single-server case (s D 1), expressions for probabilities Pn :
n 1
2 3
N
X N

P0 D 4 5
.N n/
nD0
n
N
Pn D P0 ; n D 1; 2; : : : ; N
.N n/
The other characteristics are calculated as

C
Lq D N .1 P0 /; LDN .1 P0 /

L Lq
W D ; Wq D
.N L/ .N L/

M/M/s/N/N: Queueing systems with finite population
In the multi-server case (s > 1), one has

2 3 1
sX1 n X N n
N N 5
P0 D 4 C
.N n/ n nDs
.N n/ s s n s
nD0
and
n
N
8

P0 ; n D 1; 2; : : : ; s
.N n/ n

< n
Pn D N
n s
P0 ; n D s; s C 1; : : : ; N

.N n/ s s

:
0; n>N

Example: Police helicopters
Police department of a large city has 5 helicopters. A helicopter breaks down and requires
service once every 30 days. The police department has two repair workers, each of whom takes
an average of 3 days to repair a helicopter.
(a) Determine the average number of helicopters in good condition
(b) Find the fraction of time a particular repair worker is idle

Example: Police helicopters

Queueing models with non-exponential distributions
So far, all queueing models were based on birth-and-death processes, and both their
interarrival times and service times had exponential distributions.
Although the assumption of exponential interarrival and service times serves well in many
cases, in some situations it is not applicable (e.g., when arrivals are scheduled or
regulated, or service requirements of the customers are similar, or there is a limit on
service duration: your order will be completed in 3 minutes, or its free!, etc.)

The M/G/1 model
M/G/1 model assumes that arrival process is still Poisson with a fixed mean arrival rate .
As before, it is assumed that service times are independent and have the same (arbitrary)
distribution.
Although this distribution no longer needs to be exponential, the mean service time is
assumed to be 1=, and the variance of service time is 2 .
When D = < 1 such a system would eventually reach steady state in which
P0 D 1 ;
2 2
C 2
Lq D ;
2.1 /

L D Lq C ;

Lq
Wq D ;

1
W D Wq C

When service time distribution is exponential, 2 D 1=2 , then the above formulas
coincide with the already developed ones for the M=M=1 case.

The M/D/1 model
M/D/1 model assumes that the service time distribution is deterministic (i.e., it is
constant). In this case, one has
2
Lq D
2.1 /
and the quantities L; Wq , and W are obtained as before.
In the M/D/s model the variance of service time is 0

The exponential service time in the M/M/s model has a large variance .D 1=/.
Many service time distributions fall within these two extremes

The M/Ek /s model
M/Ek /s model assumes that service times have Erlang distribution with parameter k :
.k/k k 1 kt
fEk .t/ D t e ; t 0
.k 1/
Here, is strictly positive: > 0 and k is an integer: k D 1; 2; : : :
1 1
Mean of Erlang distribution with parameter k is , and its variance is 2 D
k2
Note that by varying k we can adjust the variability of service times between that of the
exponential distribution (k D 1, 2 D 1=2 ) and the constant service times ( 2 D 0,
k ! 1).
Meaning of Erlang distribution:
Distribution of service time will be of Elang type with parameters and k if the service
process consists of k operations whose durations are independent exponentially
1
distributed with mean .
k

The M/Ek /s model
1
Substituting 2 D into the Pollaczek-Khintchine formulas, for the single-server
k2
M/Ek /1 model we have
1Ck 2
Lq D ;
2k . /
1Ck
Wq D ;
2k . /
1
W D Wq C ;

L D W
For M/Ek /s model, analytic formulas are not available. Numerical values of parameters L,

Lq , etc., have been tabulated for various values of D s , s , and k

The M/Ek /1 model
Figure: Values of L for the M=Ek =2 model

Example: Airline maintenance
An airline maintenance base wants to make a change in its overhaul operation. The present
situation is that only one airplane can be repaired at a time, and the expected repair time is 36
hours, whereas the expected time between arrivals is 45 hours. This situation has led to
frequent and prolonged delays in repairing incoming planes, even through the base operates
continuously. The average cost of an idle plane to the airline is $3,000 per hour. It is estimated
that each plane goes into the maintenance shop 5 times per year. It is believed that the input
process for the base is essentially Poisson and that the probability distribution of repair times is
Erlang, with shape parameter k D 2.
Alternative A is to provide a duplicate maintenance shop, so that two planes can be repaired
simultaneously. The cost, amortized over 5 years, is $400,000 per year for each of the airlines
airplanes.
Alternative B is to replace the present maintenance equipment by the most efficient (and
expensive) equipment available, thereby reducing the expected repair time to 18 hours. The
cost, amortized over 5 years, is $550,000 per year for each airplane. Which alternative should
the airline choose?



Queueing Theory Slides

Uploaded by

Copyright:

Available Formats

Queueing Theory Slides

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Queueing Theory Slides

Uploaded by

Copyright:

Available Formats

Queueing Theory

SIE 321 Probabilistic Models in Operations Research

SIE 321 Queueing Theory Prof. Krokhmal 1 / 57

Waiting lines are a part of everyday life

People wait in line to:

Waiting lines occur in industrial settings when:

Americans spend an estimated 37,000,000,000 hours per year waiting in queues.

Queueing theory is the study of waiting in all these various guises.

SIE 321 Queueing Theory Prof. Krokhmal 2 / 57

Queueing theory originates at the beginning of the 20th century.

Seminal contributions were made by Agner Krarup Erlang (then as an employee of

First application to telephone engineering:

SIE 321 Queueing Theory Prof. Krokhmal 3 / 57

Queueing theory seeks to answer question such as:

SIE 321 Queueing Theory Prof. Krokhmal 4 / 57

Commercial service systems:

Transportation service systems:

Interval service systems:

Social service systems:

SIE 321 Queueing Theory Prof. Krokhmal 5 / 57

Queueing theory considers operations when people, materials, equipment,

public lines at cafeterias, check-out counters, etc

equipment to be repaired produces waiting line at service facilities

vehicles form waiting lines at toll gates, traffic signals

SIE 321 Queueing Theory Prof. Krokhmal 6 / 57

SIE 321 Queueing Theory Prof. Krokhmal 7 / 57

Such cases are classified as finite waiting-line operations

SIE 321 Queueing Theory Prof. Krokhmal 8 / 57

SIE 321 Queueing Theory Prof. Krokhmal 9 / 57

SIE 321 Queueing Theory Prof. Krokhmal 10 / 57

Usually, the waiting line is a discrete array of individuals (items)

Time elapsed from service commencement to completion is called service time

SIE 321 Queueing Theory Prof. Krokhmal 12 / 57

When a unit joins the waiting line, waiting cost is incurred

Hence, waiting costs are reduced

On the other hand, increase in the service cost will occur

SIE 321 Queueing Theory Prof. Krokhmal 13 / 57

Type of queueing system can be denoted as, for example, M=M=s

Distribution of service times

Distribution of interarrival times

Example: M=G=s is a queueing system with exponential interarrival times, general

SIE 321 Queueing Theory Prof. Krokhmal 14 / 57

The following general notations will be used:

State of system number of customers in the queueing system

Queue length number of customers waiting for service to begin

N.t / number of customers in the queueing system at time t

Pn .t / probability of exactly n customers in the system at time t

s number of (parallel) servers in the system

n mean arrival rate (average number of customers joining queue

n mean service rate for overall system (average number of customers

SIE 321 Queueing Theory Prof. Krokhmal 15 / 57

With respect to a steady-state queueing system, the following notations will be

W waiting time in the system (random, different for all customers)

W D EW the expected waiting time in the system

Wq random waiting time in queue (excluding service time) for a customer

Wq D EWq the expected waiting time in the queue

SIE 321 Queueing Theory Prof. Krokhmal 16 / 57

If n is the same for all n, n D , then for each queueing system in a

SIE 321 Queueing Theory Prof. Krokhmal 17 / 57

n mean arrival rate (average number of customers joining queue

n mean service rate for overall system (average number of customers

If n is the same for all n, n D , then for each queueing system in a

Equating these two quantities, we obtain L D W

Useful formulas can be obtained in the case when n D and n D s.

The traffic intensity factor is introduced as

If < 1, the system is considered to be stable

In a single-server system, s D 1 and n D ; n D , whence

Then for 1 we have and for D 1 we have