12/21/2021

COURSE 103:
QUEUEING SYSTEM
COURSE INSTRUCTOR: Dr. ADITI KHANNA
DEPARTMENT OF OPERATIONAL RESEARCH

CONTENTS 2

 INTRODUCTION TO QUEUEING SYSTEM

 STOCHASTIC PROCESSES

 SIMPLE MARKOVIAN QUEUEING MODELS

 NON MARKOVIAN QUEUEING MODELS

 DESIGN AND CONTROL OF QUEUES

 SIMULATION

1
 12/21/2021

BOOKS 3

1. Fundamentals of Queueing Theory, 5th Edition

- by Donald Gross; John F. Shortie; James M. Thompson;
Carl M. Harris

2. An Introduction to Queueing Theory: Modeling and Analysis in

Applications, 2nd Edition, 2015
- by U. Narayan Bhatt

INTRODUCTION 4

All of us have experienced the annoyance of having to wait in

line.

• We wait in line in our cars in traffic jams or at toll booths.

• We wait on hold for an operator to pick up our telephone calls.
calls
• We wait in line at supermarkets to check out.
• We wait in line at fast-food restaurants.
• We wait in line at banks and post offices.

2
 12/21/2021

INTRODUCTION (cont.) 5

• We, as customers, do not generally like these waits.

• The managers of the establishments at which we wait also do

not like us to wait, since it may cost them business.

Why then is there waiting?

INTRODUCTION (cont.) 6

The answer is simple: There is more demand for service than there is
facility for service available.

Why is this so?

• There may be a shortage of available servers.
servers
• It may be infeasible economically for a business to provide the level of
service necessary to prevent waiting.
• There may be a space limit to the amount of service that can be
provided.

3
 12/21/2021

INTRODUCTION (cont.) 7

These limitations can be removed with the expenditure of capital.

To know how much service should then be made available, one would
need to know:
• “How long must a customer wait?”
• “How
“H many peoplel will
ill fform iin th
the li
line?”
?”

Queueing theory attempts (and in many cases succeeds) to

answer these questions through detailed mathematical analysis.

DESCRIPTION OF A QUEUEING SYSTEM 8

A queueing system can be described as customers arriving for service,
waiting for service if it is not immediate, and if having waited for
service, leaving the system after being served.

The term “customer” is used in a general sense and does not imply
necessarily a human customer. For example:

 A customer could be a ball bearing waiting to be polished.

 An airplane waiting in line to take off.
 A computer program waiting to be run.

4
 12/21/2021

DESCRIPTION OF A QUEUEING SYSTEM (cont.) 9

DESCRIPTION OF A QUEUEING SYSTEM (cont.) 10

• Queueing
Q i theory
h was d
developed
l d to provide
id mathematical
h i l models
d l to
predict the behavior of systems that attempt to provide service for
randomly arising demands.

• The earliest problems studied where those of telephone traffic

congestion.
congestion

• The pioneer investigator was the Danish mathematician A. K.

Erlang, who, in 1909, published “The Theory of Probabilities and
Telephone Conversations.”

5
 12/21/2021

DESCRIPTION OF A QUEUEING SYSTEM (cont.) 11

There are many valuable applications of queueing theory,
theory most of which
have been well documented in the literature of probability, operations
research, management science, and industrial engineering.

Some examples are :

 Traffic flow (vehicles, aircraft, people, communications)
 Scheduling (patients in hospitals, jobs on machines, programs on a
computer)
 Facility design (banks, post offices, amusement parks, fast-food
restaurants).

CHARACTERISTICS OF A QUEUEING SYSTEM 12

Arrival
Number of Pattern
Service
service
Pattern
stages
Queueing
System
Number of
service Queue
channels Discipline
System
Capacity

6
 12/21/2021

CHARACTERISTICS OF A QUEUEING SYSTEM (cont.) 13

 The
Th process off arrivals
i l isi stochastic
t h ti ((random).
d )

 It is necessary to know the probability distribution

ARRIVAL describing the times between successive customer arrivals
PATTERN (interarrival times).
OF  E
Equivalently,
i l tl it isi necessary tto k
know th
the probability
b bilit
CUSTOMERS distribution describing of the number of arrivals.

 It is also necessary to know whether customers can arrive

simultaneously (batch or bulk arrivals), and if so, the
probability distribution describing the size of the batch.

CHARACTERISTICS OF A QUEUEING SYSTEM (cont.) 14

 It is also necessary to know the reaction of a customer upon

entering the system.
ARRIVAL
 A customer may decide to wait no matter how long the queue
PATTERN becomes. Such customers are called as Patient Customers.
OF
 On the other hand, if the queue is too long, the customer may
CUSTOMERS decide not to enter the system. Such customers are called as
Impatient Customers. There are 3 types of impatient
customers.

7
 12/21/2021

CHARACTERISTICS OF A QUEUEING SYSTEM (cont.) 15

T
Types off IImpatient
ti t CCustomers:
t

1. If a customer decides not to enter the queue upon

ARRIVAL arrival, the customer is said to have balked.
PATTERN
2. A customer may enter the queue, but after a time lose
OF patience
ti and
dddecide
id tto lleave. IIn thi
this case, th
the customer
t
CUSTOMERS is said to have reneged.

3. In the event that there are two or more parallel waiting

lines, customers may switch from one to another, that
is, jockey for position.

CHARACTERISTICS OF A QUEUEING SYSTEM (cont.) 16

 The
Th process off service
i ((or departures)
d t ) is
i also
l stochastic.
t h ti

 It is necessary to know the probability distribution of the

SERVICE times between successive customer departures (inter-
PATTERN departure times or service times).
OF  E
Equivalently,
i l tl it isi necessary tto k
know th
the probability
b bilit
CUSTOMERS distribution describing of the number of departures.

 It is also necessary to know whether customers are served

simultaneously (batch service), and if so, the probability
distribution describing the size of the batch.

8
 12/21/2021

CHARACTERISTICS OF A QUEUEING SYSTEM (cont.) 17

 The service process may depend on the number of

SERVICE customers waiting for service.

PATTERN  A server may work faster if the queue is building up

OF or, on the contrary, may get flustered and become
less efficient.
CUSTOMERS
 The situation in which service depends on the
number of customers waiting is referred to as state-
dependent service.

CHARACTERISTICS OF A QUEUEING SYSTEM (cont.) 18

 It refers to the manner in which customers are selected for
service when a queue has formed.

 The most common discipline that can be observed in everyday

life is first come, first served (FCFS / FIFO).
QUEUE
DISCIPLINE  Some others in common usage
g are:

• Last come, first served (LCFS).

• Selection for service in random order (RSS).

• Variety of priority schemes.

9
 12/21/2021

CHARACTERISTICS OF A QUEUEING SYSTEM (cont.) 19

Priority Queue Disciplines come into picture when customers are of different
types, some having higher priority, and some having lower priority.

There are two general situations in priority disciplines.

1. Pre-emptive Priority : The customer with the highest priority is allowed

QUEUE to enter service immediately even if a customer with lower priority is
DISCIPLINE already in service when the higher-priority customer enters the system;
that
h is,
i the
h llower priority
i i customer iin service
i iis pre-empted,
d its
i service
i
stopped, to be resumed again after the higher priority customer is
served.

2. 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, even though this customer has a lower priority.

CHARACTERISTICS OF A QUEUEING SYSTEM (cont.) 20

 It refers to the maximum number of customers the system can

accommodate.

 In some queueing processes there is a physical limitation to the

amount of waiting room, so that when the line reaches a certain
SYSTEM length, no further customers are allowed to enter until space
CAPACITY becomes available as the result of a service completion. These are
referred to as finite queueing situations.

 When there is no physical limitation, the system capacity is infinite.

 A queue with limited waiting room can be viewed as one with

forced balking.

10
 12/21/2021

CHARACTERISTICS OF A QUEUEING SYSTEM (cont.) 21

 It refers to the to the number of parallel service stations that
can serve customers simultaneously.

NUMBER OF
SERVICE
CHANNELS
Multi-channel Queueing Systems

 It is generally assumed that the service mechanisms of parallel

channels operate independently of each other.

CHARACTERISTICS OF A QUEUEING SYSTEM (cont.) 22

 A queueing system may have only a single stage of

service, as in the hair-styling salon.

NUMBER OF  It may have several stages. An example of a

STAGES OF multistage queueing system would be a physical
examination procedure, where each patient must
SERVICE
proceed through several stages, such as medical
history; ear, nose, and throat examination; blood
tests; electrocardiogram; eye examination; and so
on.

11
 12/21/2021

CHARACTERISTICS OF A QUEUEING SYSTEM (cont.) 23

 The population of potential customers, may be

assumed to be finite or infinite.

CALLING  Finite population model: if arrival rate depends on

POPULATION the number of customers being served and waiting.

 Infinite population model: if arrival rate is not

affected by the number of customers being served
and waiting.

CHARACTERISTICS OF A QUEUEING SYSTEM (cont.) 24

12
 12/21/2021

CHARACTERISTICS OF A QUEUEING SYSTEM (cont.) 25

 Th
The six
i characteristics
h t i ti off queueing
i g systems
t are ggenerally
ll sufficient
ffi i t tto
completely describe a process under study.

 It is extremely important to use the correct model or at least the model that
best describes the real situation being studied.

 Before performing any mathematical analyses, it is absolutely necessary to

describe adequately the process being modeled. Knowledge of the basic six
characteristics is essential in this task.

 A great deal of thought is often required in this model selection procedure.

KENDALL’S NOTATION FOR QUEUEING MODELS 26

It is
i a shorthand
h th d ffor d
describing
ibi g a queueing
i g processes gi
given b
by Kendall.
K d ll

Using this notation, a queueing process can be described by a series of symbols

and slashes such as A/B/X/Y/Z, where
A indicates the interarrival-time distribution.

B indicates the probability distribution for service time.

X indicates the number of parallel service channels.

Y indicates the restriction on system capacity.

Z indicates the queue discipline.

13
 12/21/2021

KENDALL’S NOTATION (cont.) 27

For example
example, the notation
M/D/2/∞/FCFS indicates a
queueing process with:

• Exponential interarrival times.

• Deterministic service time.
• Two parallel servers.
• No restriction on the
maximum number allowed in
the system, and
• First-come, first-served queue
discipline.
Queueing Notation A/B/X/Y//Z

KENDALL’S NOTATION (cont.) 28

 IIn many situations

it ti only
l the
th fi
firstt th
three symbols
b l are used.
d Current
C t practice
ti iis tto omit
it
the service-capacity symbol if no restriction is imposed (Y = ∞) and to omit the queue
discipline if it is first come, first served (Z = FCFS).
 Thus M/D/2 would be a queueing system with exponential input, deterministic
service, two servers, no limit on system capacity, and first-come, first-served
discipline.
 The symbol G represents a general probability distribution; that is,
is no assumption is
made as to the precise form of the distribution.
 It may also appear strange that the symbol M is used for exponential. The use of the
symbol E, as one might expect, would be too easily confused with Ek, which is used
for the Erlang type-k distribution. So M is used instead which stands for the Markovian
or memoryless property of the exponential.

14
 12/21/2021

Example of a Retail Outlet 29

• C
Customers
t arrive
i ini a completely
l t l random
d ffashion
hi which
hi h can b
be modeled
d l d
according to a Poisson distribution ( the time between arrivals is
Exponentially distributed).

• The service time (billing time at checkout counters behaves in a random

fashion, which can be modeled by an exponential distribution.

• Customer are served according to first come first served basis.

• There are multiple (say 5) check-out counters.

• The outlet has a finite capacity (say 100).

Example of a Retail Outlet (cont.) 30

The Kendall’s Notation

for this queueing system is

M/M/5/100/FCFS

15
 12/21/2021

Example of a Ticket Vending Machine 31

• Customers arrive in a completely random fashion which can be modeled

according to a Poisson distribution.

• Service time (ticket vending times) are deterministic .

• Customers are served according to first come first served basis.

• There are, say 2 ticket vending machines.

• The outlet has a finite capacity (say 20).

Example of a Ticket Vending Machine (cont.) 32

The Kendall’s Notation

f this
for thi queueing
i system
t iis

M/D/2/20/FCFS

16
 12/21/2021

Glimpses of Applications of
Queueing Theory 33

34

17
 12/21/2021

35

36

18
 12/21/2021

37

38

19
 12/21/2021

39

40

20
 12/21/2021

41

QUEUEING SYSTEM
INTRODUCTION – PART II

21
 12/21/2021

WHY STUDY QUEUES? 43

 Waiting cannot be completely eliminated without incurring

inordinate expenses.

 The goal is to reduce its adverse impact to tolerable limits.

 The objective of studying queues is to offer reasonably

satisfactory services to waiting customers.

OBJECTIVES OF STUDYING A QUEUEING SYSTEM 44

 Queueing theory helps in determining the measures of

performance of waiting lines such as:

1. Average waiting time in the queue.

2. Average productivity of the service facility.

 These measures can then be used in decision making and in

designing an optimal system.

22
 12/21/2021

MEASURING SYSTEM PERFORMANCE 45

Generally there are three types of system responses of interest:

1. Some measure of the waiting time that a typical customer might be

forced to endure.

2. An indication of the manner in which customers may accumulate; and

3. A measure of the idle time of the servers.

Since most queueing systems have stochastic elements, these measures are
often random variables and their probability distributions, or at the very least
their expected values, are desired.

MEASURING SYSTEM PERFORMANCE (cont.) 46

There are two types off customer waiting

Th i i times:
i
[Link] time a customer spends in the queue.
[Link] time a customer spends in the system (queue plus service).
There are two customer accumulation (number of customers) measures:
[Link] number of customers in the queue.
2. The total number of customers in the system.
Idle-service measures can include:
[Link] percentage of time any particular server may be idle.
[Link] time the entire system is devoid of customers.

23
 12/21/2021

TASK OF A QUEUEING ANALYST 47

Descriptive Prescriptive
Modeling Modeling

Design of Control
Queue of Queue

TASK OF A QUEUEING ANALYST (Cont.) 48

Ultimately, the issue generally comes down to a

trade-off of better customer service versus the expense of

providing more service capability,

that is, determining the increase in investment of service

for a corresponding decrease in customer delay.

24
 12/21/2021

COST / CAPACITY TRADE-OFF MODEL 49

Total
cost
Cost

Cost of
service

Cost of waiting

Process capacity

SOME GENERAL RESULTS FOR G/G/1 AND

G/G/c QUEUEUS (cont.) 50

 Transient
T i t / Ti
Time-dependent
d d t condition
diti : When
Wh a queueingi system
t h
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 / Stationary / Equilibrium condition : After sufficient time has

elapsed (i e as t  ∞)), the state of the system becomes essentially
(i.e.,
independent of the initial state and the elapsed time.

 Queueing theory has tended to focus largely on the steady-state condition.

25
 12/21/2021

SOME GENERAL RESULTS FOR G/G/1 AND

G/G/c QUEUEUS (cont.) 51

T
Terminology
i l and
dNNotation
t ti :
 State of system = number of customers in queueing system.
 N(t) = Random variable denoting number of customers in the system at time t.
 Nq(t) = Random variable denoting number of customers in the queue at time t.
 Ns((t)) = Random variable denoting number of customers in service at time t.
 N(t) = Nq(t) + Ns(t).
 pn(t) = P{N(t) = n} = Probability of exactly n customers in queueing system at
time t.
 c = number of servers (parallel service channels) in queueing system.

SOME GENERAL RESULTS FOR G/G/1 AND

G/G/c QUEUEUS (cont.) 52
 λn = mean arrival rate (expected number of arrival per unit time) of new customers when n
customers are in system.

 When λn is a constant for all n, this constant is denoted by λ.

 1/λ is the expected interarrival time.

 μn = mean service rate for overall system (expected number of customers completing service
per unit time) when n customers are in system.

 When mean service rate per busy server is constant for all n≥1, this constant is denoted by μ.

 μn = cμ when n ≥ c (all servers are busy).

 1/μ is the expected service time.

26
 12/21/2021

SOME GENERAL RESULTS FOR G/G/1 AND

G/G/c QUEUEUS (cont.) 53

Some notations in steady state, i.e., when t  ∞

 N = Random variable denoting number of customers in the system in steady state.
 Nq = Random variable denoting number of customers in the queue in steady state.
 T = Random variable denoting time spent in the system.
 Tq = Random
R d variable
i bl denoting
d i time
i spent iin the
h queue.
 S = Random variable denoting service times.
 T = Tq + S.
 pn = P{N = n} = Probability of exactly n customers in the system in steady state.

SOME GENERAL RESULTS FOR G/G/1 AND

G/G/c QUEUEUS (cont.) 54

27
 12/21/2021

SOME GENERAL RESULTS FOR G/G/1 AND

G/G/c QUEUEUS (cont.) 55

TRAFFIC INTENSITY / UTILIZATION FACTOR (ρ)

Let the average rate of customers entering the system : λ

Let the average rate of serving the customers : µ

Th
Then, a measure off ttraffic
ffi congestion
g ti forf a c-server systems
t iis gi
given b
by
ρ = λ/cμ

In other words, ρ is the expected fraction of time (probability) the

individual servers are busy.

SOME GENERAL RESULTS FOR G/G/1 AND

G/G/c QUEUEUS (cont.) 56
Importance of Traffic Intensity (ρ) for Infinite Capacity Queueing Systems :

 When ρ > 1 (λ > cμ), the average number of arrivals into the system exceeds the
maximum average service rate of the system, and we would expect, as time goes on,
the queue to get bigger and bigger. The queue size never settles down and there is
no steady-state.

 When ρ = 1,
1 unless arrivals and service are deterministic and perfectly scheduled,
scheduled no
steady state exists, since randomness will prevent the queue from ever emptying out
and allowing the servers to catch up, thus causing the queue to grow without bound.

 It turns out that for steady-state results to exist, ρ must be strictly less than 1.

For a finite capacity system, steady-state always exists irrespective of the value of ρ.

28
 12/21/2021

SOME GENERAL RESULTS FOR G/G/1 AND

G/G/c QUEUEUS (cont.) 57

If one knows the average arrival rate and average service rate,
then the minimum number of parallel servers required to
guarantee a steady
steady-state
state solution can be calculated immediately
by finding the smallest c such that λ/cμ < 1.

SOME GENERAL RESULTS FOR G/G/1 AND G/G/c

QUEUEUS (cont.) 58

LITTLE’S FORMULA

 One of the most powerful relationships in queueing theory was developed by John D. C. Little
in the early 1960s (see Little, 1961, for the original proof).
 Little related the steady-state mean system sizes to the steady-state average customer waiting
times.
 Little’s
l ’ fformula
l (for
f any G/G/c queue) are:
L = λ W … (1) and Lq = λ Wq ...(2)
 It is necessary to find only one of the four expected-value measures, in view of Little’s
formulas.
 Also, T = Tq + S which gives E[T] = E[Tq] + E[S] which gives W = Wq + 1/µ … (3)

29
 12/21/2021

SOME GENERAL RESULTS FOR G/G/1 AND G/G/c

QUEUEUS (cont.) 59

SOME GENERAL RESULTS FOR G/G/1 AND G/G/c

QUEUEUS (cont.) 60

From (6),
(6) we can easily derive the probability that any given server is busy in a multi-server
multi server
system in the steady state, denoted by pb.

Since we have just shown that the expected number present in service at any instant in the steady
state is r = λ/µ, it follows from the symmetry of the c servers that the expected number present at
one server is r/c = λ/cµ = ρ.

Then,, a simple
p expected-value
p argument
g gives:
g 0.(1-p
( pb ) + 1. pb = r/c = ρ
which gives pb = r/c = ρ

 In a multi-server queue G/G/c, probability that any given server is busy: pb = r/c = ρ .

 For a single-server queue G/G/1, probability of the system being idle (N = 0) is the same as the
probability of a server being idle. Thus, in this case
pb = 1 – p0, and p0 = 1 – ρ = 1 – r = 1 – λ/μ which gives pb = r .

30
 12/21/2021

SOME GENERAL RESULTS FOR G/G/1 AND G/G/c

QUEUEUS (cont.) 61

 The quantity r = λ/μ, the expected number of customers in service, has another
interesting connotation.

 r = λ/μ is sometimes also referred to as the offered load, since, on average, each
customer requires 1/μ time units of service and the average number of customers
arriving per unit time is λ,
λ so that the product λ(1/μ) = r is the amount of work
arriving to the system per unit time.

 Dividing r by the number of servers c, i.e., r/c = ρ gives the average amount of
work coming to each server per unit time.

SOME GENERAL RESULTS FOR G/G/1 AND G/G/c

QUEUEUS (cont.) 62

Summary of General Results for G/G/c Queues

31