MTH 203 – Introduction to

Operational Research

Semester 2, AY2022-2023

1
Chapter 4. Markovian Queuing Theory

2
“Queuing theory is the mathematical
study of waiting lines, or queues.”
----- Wikipedia

3
Queue for public transit…

4
Queue for food…

5
Queue for 11.11…

6
Queue for machine processing…

7
Queue for taking off…

8
• Queues exist because the resources are
limited.

• Eliminating waiting altogether is not

reasonable: the cost of providing more
resources could be very high.

9
The objective is to design queuing systems with
a “balance”.

cost of offering
a service

cost of waiting
experienced
by customers

10
• Queuing theory quantifies the phenomenon
of waiting by making use of performance
measures on things like
– How long will we wait for?
– How many people are there in the queue?
– Are the server busy or idle?
• The results of queuing analysis can be
incorporated in a cost optimization model.

11
 Our Questions
• What elements of a queuing system should
be considered?
• Depending on the elements, what types of
queuing models do we have?
• What are the properties of the queuing
models?
• What are the typical performance measures?
• How to quantify the performance measures?

12
4.1 Introduction: Markovian Queue

13
Queuing System

14
 Elements of a Queuing Model
1) Arrival process
How fast do the customer arrive? probabilistic

2) Service times
How fast are the customer get served?
3) Service mechanism
Parallel service, arranged in series, networked,
etc.

15
Parallel Service

16
Service arranged in series

17
Network Service

18
 Elements of a Queuing Model
1) Arrival process
How fast do the customer arrive? probabilistic
2) Service times
How fast are the customer get served?
3) Service mechanism
Parallel service, arranged in series, networked, etc.
4) Service capacity
Is there a limit on the number of customers?

19
service without capacity

service with capacity

20
 Elements of a Queuing Model
1) Arrival process
How fast do the customer arrive? probabilistic
2) Service times
How fast are the customer get served?
3) Service mechanism
Parallel service, arranged in series, networked, etc.
4) Service capacity
Is there a limit on the number of customers?
5) Queue discipline
First-come-first-served, last-come-first-served, etc.

21
First-come-first-served

22
Last-come-first-served

23
Let be the arrival rate (how many customers will come per
unit time), be the service rate (i.e. how many customers
can be served per unit time)
• – the average inter-arrival time (average time
between successive arrivals)
• – the average service time.

Example 4.1.1. If there are 5 customers per hour on average,

then the mean inter-arrival time 1/5 = 0.2 hours, .
Suppose that on average, each customer will be served for 20
minutes, then

(Here the unit time is “per hour”.)

24
 , i.e. service time is longer
than the inter-arrival time.

• If
Users arrive faster than they can be served. The
queue grows infinitely.

• If
The system is stable. Queues may build up from time
to time but eventually they will reduce in length.

25
Arrival Process

26
• In most queuing situations, arrivals occur
randomly, i.e. the occurrence of an event is
not influenced by the length of times that has
elapsed since the occurrence of the last event.
• We assume that the inter-arrival times and
service times are both described by the
exponential distribution.

Pdf:

Cdf:

27
The exponential distribution describes a totally random
phenomenon.
Lack of Memory Property. Given is the
exponential distribution of the time , between
successive events, if is the interval since the
occurrence of the last event, then the property implies
that

S T

last event now future

28
Proof:

29
Pure Birth Model

30
Pure Birth Model – only arrivals occur
• Define - probability of no arrivals during a
period of time .
• The inter-arrival time is exponentially distributed
and the arrival rate is customers per unit time.

31
For a sufficiently small time interval , Taylor
Expansion

At most one arrival

could occur during a
very small period

Let be the probability of having arrivals during time

period .
There are arrivals during if

• arrivals during , 0 arrival during

• arrivals during t and 1 arrival during .

32
Therefore,

Also,

33
Considering the limits as :

when

when
Solving the above differential equation, we obtain

34
 when
when

solve for .

35
Example 4.1.2. Babies are born in a small state at the rate
of one birth every 12 minutes. The time between births
follows an exponential distribution.

(a) Find the average number of birth per year.

Birth rate per day births/day
So the number of births per year = births/year
(b) Find the probability that no birth will occur in any one
day.

36
(c) Find the probability of issuing 50 birth
certificates in 3 hours, given that 40 certificates
were issued during the first 2 hours of the 3-
hour period.
Birth rate per hour
Due to the lack of memory of the exponential
distribution, the question is the same as having 10
births in one hour.

37
 Poisson Process
If the time between consecutive arrivals follows an
exponential distribution with parameter , then the number
of arrivals during time period follows a Poisson
distribution with parameter

is the number
of arrivals during
time period

• The process is called a Poisson

process with parameter .

38
 Exp Po

Time between successive Number of arrivals , during a

Random variable
arrivals during time period . time period .

Range

Density function

Expectation

P(number of arrivals in
Cumulative P(inter-arrival time
time period t)
probability

P(no arrivals during

period A)

39
Departure Process and Pure Death Model

40
Pure Death Model: only departures occur
• Assume that the system starts with
customers at time 0, with no new arrivals
allowed.
• Departures occur at the rate customers per
unit time.
• For a sufficiently small time interval ,
– (no departure within ) =
– (one departure within ) =

41
 (no departure within ) =
(one departure within ) =

• Define probability of having n remaining

after a time period .

Case 1: remaining after time

N remaining after time and no departure during

42
 (no departure within ) =
(one departure within ) =

Case 2: remaining after time

remaining after time and no departure during
OR
remaining after time and one departure during

43
 (no departure within ) =
(one departure within ) =

Case 3: remaining after time

remaining after time and no departure during
OR
remaining after time and one departure during

44
When

Solving the above equations we have

This is a truncated Poisson distribution.

45
Example 4.1.3 The florist section in a grocery store
stocks 18 dozen roses at the beginning of each week. On
average, the florist sells 3 dozens a day (one dozen at a
time), but the actual demand follows a Poisson
distribution. Whenever the stock level reaches 5 dozens,
a new order of 18 new dozens is placed for delivery at the
beginning of the following week. Because of the nature of
the item, all roses left at the end of the week are
disposed of. Determine the following:

(a) The probability of placing an order in any one day of

the week.
This is a pure death model, with dozens and departure
rate dozens/day
46
The probability of having remaining dozens by the end of
day is

New order will be placed if stock level reaches 5 dozens, i.e.,

the remaining is .
Hence, the probability of placing an order by the end of day
is

The result is summarized below:

(day) 1 2 3 4 5 6 7
0.0000 0.0088 0.1242 0.4240 0.7324 0.9083 0.9755
47
(b) The average number of dozen roses discarded at the
end of the week.

All remaining will be discarded at the end of the week.

The probability of having remaining dozens at the end of the
week ( ) is

We can calculate the expected value:

So the average number of dozen roses to be discarded is 1.

48
Poisson process is a continuous time Markov
chain, so the queuing system with such an
arrival and service pattern is called a
Markovian queuing system.

49
 Queue Types
By following Kendall’s notation in the form
“A/S/c” where
 A – distribution of inter-arrival times
 S – distribution of service times
 c – the number of servers
In this chapter we will consider
 M/M/1 queues (e.g. machine processing)
 M/M/K queues (e.g. supermarket checkout)

50
General Poisson Queuing Model

51
 Assumptions
• The general queuing model combines both
arrivals and departures, where the inter-arrival
and service times follow the exponential
distributions.
• The queuing system is in a steady-state, achieved
after the system has been operated for a
sufficiently long time.
• Both the arrival and departure rates are state
dependent – they depend on the number of
customers in the service facility.
52
Notations:
• – number of customers in the system (in-
queue plus in-service)
• – arrival rate, given customers in the
system.
• – departure rate, given customers in the
system.
• – steady-state probability of customers in
the system.

53
 Transition-rate Diagram

0 1 2 … …

• State : the number of customers in the system is .

• For , state can change to only two possible
states: state (when a departure occurs at rate
and state (when an arrival occurs at rate )
• State 0 can change to only state 1 when an arrival occurs
at rate .

54
• We want to find , which is a function of
and .

• Under steady-state conditions, for , the

expected rates of flow into and out of state
must be equal to each other.

55
 0 1 2 … …

• For state
Expected rate of flow into state

Expected rate of flow out of state

So
• For state 0
flow out of state 0 flow into state 0
56
 How can we solve
the equations?
Balance equations:

For ,
For

So ,
…
⋯
By induction,
⋯

is determined from

57
Example 4.1.4. Big Brothers Grocery operates with three
checkout counters. The manager
uses the following schedule to
determine the number of counters
in operation, depending on the
number of customers in line:
Number of customers in store Number of counters in operation
Less than 4 1
4 to 6 2
More than 6 3

Customers arrive in the counters area according to a Poisson

distribution with a mean rate of 10 customers per hour. The
average checkout time per customer is exponential with mean
12 minutes. (1) Determine the steady-state probability of
customers in the checkout area.
58
Based on the information we know that

So

59
Also,

60
(2) What is the probability that only one counter will be open?
P(only one counter is open)
P(the number of customers is less than 4)

(3) What is the expected number of idle counters? (Note that by

“idle” we mean not serving any customers.)
Expected number of idle counters

So on average, there is one counter idle.

61
Example 4.1.5. A barbershop
serves one customer at a time
and provides three seats for
waiting customers. If the place
is full, customers go elsewhere. Arrivals occur
according to a Poisson distribution with mean 4 per
hour. The time to get a haircut is exponential with
mean 15 minutes. Determine the following:
(1) The steady-state probabilities.
(2) The expected number of customers in the shop.
(3) The probability that customers will go elsewhere
because the shop is full.

62
(1) According to the question, we have
customers/hour,
customers/hour.

So

and when .

63
(2) The expected number of customers in the shop

(3) P(customer will go elsewhere)

P(there are 4 customers in the shop, one being
served and three waiting)

64
Example 4.1.6. Consider a one-server queuing
situation in which the arrival and service rates
are given by

This situation is equivalent to reducing the

arrival rate and increasing the service rate as the
number in the system, , increases.
(1) Set up the transition diagram, and determine
the balance equation for the system.

65
There are 5 states:

So the transition diagram is

0 1 2

The balance equations are:

66
(2) Determine the steady-state probabilities.

Method 1. Solve this linear system

Method 2. Using formula

and so
, .

67