Lecture 1

Queueing Theory
SEEM 4670 Service Systems
Spring, 2020

1
A Queueing Example

• Imagine that you are going to order food at Coffee Corner.

• Suppose that people come with an arrival rate of 2 people per
minute, people take an average of 30 seconds to order food,
and only one cashier is working.
• Why do we still have to wait?
• Even if the cashier works much faster or there are fewer
customers, we may also need to wait. 2
What is Queueing Theory?
- number of servers
- configuration
Service System - service time distribution

Arrival customers
Process
Calling Population
- finite or infinite Service
- different types of customers

Queue
- interarrival times (independent or dependant)
- balking
- capacity
- discipline (FIFO, LIFO, priority, random selection,)
- reneging

• Queueing theory is concerned with the mathematical description of

queues (or waiting lines).
• The characteristics of a queueing system are modelled analytically.
• The results obtained from the queueing model can be used to 3
analyze and predict the performance of the queueing system and to
aid decision-making for enhancement of service delivery.
Inputs for Queueing Models
• A description of the way in which customers arrive at the system,
i.e., the arrival process. Of particular interest is the probability
distribution of the time between customer arrivals.
• A description of the way in which customers are served, i.e., the
service process. Of particular concern is the probability distribution
of the time to serve a customer.
• The number of servers. (In the previous example, the number of
cashiers.)
• The maximum number of customers that the system can
accommodate, i.e., the capacity of the system.
• The size of the pool of customers, i.e., the population of the
customers.
• The way in which waiting customers are chosen for service, i.e., the 4
service discipline. (e.g., first-come, first-served)
Standard Notation for the Inputs
• Kendall’s notation for queueing theory: X/Y/Z
• X and Y are letters used to describe the arrival and service
processes respectively. More specifically, they are used to
describe the probability distributions in modeling the
interarrival times and service times of customers. Frequently
used symbols include:
 M – Exponential distribution
 D – Deterministic
 G, GI – General distribution
• Z is a positive integer (which can be ∞) stating the number of
servers.
5
Examples of Queues
• M/M/1 – a queue with a single server, Poisson arrivals and
exponentially distributed service times
• M/M/s – a queue with s servers, Poisson arrivals and
exponentially distributed service times
• M/G/ ∞ – a queue with an infinite number of servers, Poisson
arrivals and a general service time distribution
• D/G/s – a queue with s servers, deterministic arrivals and a
general service time distribution

6
Outputs for Queueing Models
We are interested in the key performance metrics that can be
obtained from queueing models, e.g.,

• Number of customers in the system

• Number of customers waiting to be served (in the queue)
• Total time in the system
• Time in the queue waiting to be served

7
Notation
• L : average number of customers in the system
• 𝐿𝑞 : average number of customers waiting to be served
• 𝐿𝑠 : average number of customers in service
• W : average total time in the system
• 𝑊𝑞 : average time in the queue waiting to be served
• 𝜆 : average arrival rate
• 𝜇 : average service rate
• 1 / 𝜇 : average service time
• a(t) : number of people to arrive at the system in the time interval
[0,t]
• d(t) : number of people to depart from the system in the time
interval [0,t]
• N(t) : number of people in the system at time t. Note that
N(t) = a(t) – d(t)
• 𝑙(𝑡) : total accumulated person minutes in the system during the 8
time interval [0,t]
Little’s Law
𝑡 𝑡
𝑙 𝑡 = න 𝑁 𝜏 𝑑𝜏 = න [𝑎 𝜏 − 𝑑 𝜏 ]𝑑𝜏
0 0

Let the average total time and the average number of customers in the
system within interval [0,t] be W(t) and L(t).
𝑙 𝑡 𝑙 𝑡 𝑙 𝑡 𝑎 𝑡
We have 𝑊 𝑡 = and 𝐿 𝑡 = = × .
𝑎 𝑡 𝑡 𝑎 𝑡 𝑡
Taking the limit of the latter as 𝑡 → ∞, we have
𝑙 𝑡 𝑎 𝑡
lim 𝐿 𝑡 = lim [ × ] 9
𝑡→∞ 𝑡→∞ 𝑎 𝑡 𝑡
𝐿 = 𝑊𝜆
Little’s Law
Similarly we have
𝐿𝑞 = 𝜆𝑊𝑞
and
𝐿𝑠 = 𝜆/𝜇
Finally we have
𝑊 = 𝑊𝑞 + 1/𝜇

These results are general as we did not make any assumptions

about the interarrival or service time probability distributions.

10
Markovian Queues
• A Markovian process is a stochastic process in which the
conditional probability of being in any state at some future
time given the present and past states equals the probability
of being in the state in the future given only the present state.
• The past history of the system does not provide any
information needed to predict future states.
• Recall a discrete-time Markov chain:
P 𝑋𝑛+1 = 𝑥 𝑋1 = 𝑥1 , 𝑋2 = 𝑥2 , … , 𝑋𝑛 = 𝑥𝑛
= P 𝑋𝑛+1 = 𝑥 𝑋𝑛 = 𝑥𝑛
• Queues with Poisson arrivals and exponentially distributed
service times are known as Markovian queues.
11
Exponential Distributions
A continuous random variable X is said to have an exponential
distribution with parameter λ, or denoted by 𝑋~ exp 𝜆 , where λ > 0,
if its probability density function (pdf) is given by
𝜆𝑒 −𝜆𝑥 , 𝑥 ≥ 0
𝑓 𝑥 =ቊ
0, 𝑥<0
𝜆 is called the rate.
It is easy to verify that the cumulative
𝑥
distribution function (cdf) is
−𝜆𝑥
𝐹 𝑥 = 𝑃{𝑋 ≤ 𝑥} = න 𝜆𝑒 𝑑𝑡 = ቊ −𝜆𝑡 1 − 𝑒 ,𝑥 ≥ 0
0 0, 𝑥<0
𝑒 −𝜆𝑥 , 𝑥 ≥ 0
ത
𝐹 𝑥 =𝑃 𝑋 >𝑥 =1−𝐹 𝑥 =ቊ
1, 𝑥<0
Recall some facts:
1
• 𝐸 𝑋 =
𝜆
1 12
• 𝑉𝑎𝑟 𝑋 =
𝜆2
Graphs of Exponential Distributions
𝑦 = 𝜆𝑒 −𝜆𝑥 , 𝑥 ≥ 0

13
Memoryless Property
• A random variable Y is said to be without memory, or memoryless,
if
𝑃 𝑌 > 𝑠 + 𝑡 𝑌 > 𝑡 = 𝑃 𝑌 > 𝑠 ∀𝑠, 𝑡 ≥ 0.
• If we think of Y as being the lifetime of some instrument, then the
above equation states that the probability that the instrument lives
for at least (s + t) hours given that it has survived t hours is the same
as the initial probability that it lives for at least s hours.
• In other words, if the instrument is alive at time t, then the
distribution of the remaining amount of time that it survives is the
same as the original lifetime distribution; that is, the instrument
does not remember that it has already been in use for a time t.
• It turns out that the exponential distribution is the unique
continuous distribution possessing this property.
14
Poisson Distributions
A discrete random variable Y is said to have a Poisson
distribution with parameter λ, or denoted by 𝑌~ Poi 𝜆 , where
λ > 0, if its probability mass function is given by
𝜆 𝑛 𝑒 −𝜆
P(𝑌 = 𝑛) = ൞ 𝑛! , 𝑛 ≥ 0
0, 𝑛<0

Important fact:
The number of customer arrivals in a fixed time period follows a
Poisson distribution with mean 𝜆  their interarrival times are
independent and identically distributed exponential random
variables having mean 1/λ. 15
Markovian Queues
Assumption: Both the interarrival times and service times are
exponentially distributed.

Suppose that customers arrive at the system according to a

Poisson process with an arrival rate of 𝜆.
The probability of no arrivals in a small amount of time ∆𝑡 is
∞ 𝑘
−𝜆∆𝑡
𝑃 𝑎 ∆𝑡 = 0 = 𝑒 −𝜆∆𝑡 = ෍ = 1 − 𝜆∆𝑡 + 𝑜( ∆𝑡 2 )
𝑘!
𝑘=0
where 𝑜( ∆𝑡 2 ) are terms of order ∆𝑡 2 or smaller.
For small ∆𝑡 we have
𝑃 𝑎 ∆𝑡 = 0 ≈ 1 − 𝜆∆𝑡
𝑃 𝑎 ∆𝑡 = 1 ≈ 𝜆∆𝑡 16
𝑃 𝑎 ∆𝑡 > 1 ≈ 0
Markovian Queues
Similarly, if service times are exponentially distributed with a
mean of 1/𝜇, the probability of two or more service
completions in a very small amount of time is also 0, while the
probability of no service completion is 1 − 𝜇∆𝑡 and the
probability of exactly 1 service completion is 𝜇∆𝑡.

i.e., for small ∆𝑡 we have

𝑃 𝑑 ∆𝑡 = 0 ≈ 1 − 𝜇∆𝑡
𝑃 𝑑 ∆𝑡 = 1 ≈ 𝜇∆𝑡
𝑃 𝑑 ∆𝑡 > 1 ≈ 0

17
Markovian Queues
Let
• 𝜆𝑖 𝑡 : arrival rate with 𝑖 people in the system at time t
• 𝜇𝑖 𝑡 : service rate with 𝑖 people in the system at time t
• 𝑃𝑖 𝑡 : probability of having 𝑖 people in the system at time t

Then we can write

𝑃0 𝑡 + ∆𝑡 = 1 − 𝜆0 𝑡 ∆𝑡 𝑃0 𝑡
+𝜇1 𝑡 ∆𝑡𝑃1 (𝑡)
and for 𝑖 = 1,2, …
𝑃𝑖 𝑡 + ∆𝑡 = 𝜆𝑖−1 𝑡 ∆𝑡 𝑃𝑖−1 𝑡
+ 1 − 𝜆𝑖 𝑡 ∆𝑡 1 − 𝜇𝑖 𝑡 ∆𝑡 𝑃𝑖 𝑡
+𝜇𝑖+1 𝑡 ∆𝑡𝑃𝑖+1 (𝑡) 18
Markovian Queues
Therefore, we have
𝑃0 𝑡 + ∆𝑡 − 𝑃0 𝑡
= −𝜆0 𝑡 𝑃0 𝑡 + 𝜇1 𝑡 𝑃1 (𝑡)
∆𝑡
and for 𝑖 = 1,2, …
𝑃𝑖 𝑡 + ∆𝑡 − 𝑃𝑖 𝑡
∆𝑡
= 𝜆𝑖−1 𝑡 𝑃𝑖−1 𝑡 − 𝜆𝑖 𝑡 + 𝜇𝑖 𝑡 − 𝜆𝑖 𝑡 𝜇𝑖 𝑡 ∆𝑡 𝑃𝑖 𝑡 + 𝜇𝑖+1 𝑡 𝑃𝑖+1 (𝑡)

Taking the limits as ∆𝑡 → 0, we have

𝑑𝑃0 𝑡
= −𝜆0 𝑡 𝑃0 𝑡 + 𝜇1 𝑡 𝑃1 (𝑡)
𝑑𝑡
𝑑𝑃𝑖 𝑡
= 𝜆𝑖−1 𝑡 𝑃𝑖−1 𝑡 − 𝜆𝑖 𝑡 + 𝜇𝑖 𝑡 𝑃𝑖 𝑡 + 𝜇𝑖+1 𝑡 𝑃𝑖+1 (𝑡)
𝑑𝑡

The above differential equations are known as Chapman-Kolmogorov 19

equations.
Steady-State Balance Equations
• Here, we assume that both arrival and service rates are
constant over time. i.e., 𝜆𝑖 𝑡 = 𝜆𝑖 and 𝜇𝑖 𝑡 = 𝜇𝑖 ∀𝑖.
• We are interested in the long-run average performance of the
Markovian queue systems.
𝑑𝑃𝑖 𝑡
• When 𝑃𝑖 𝑡 = 𝑃𝑖 and = 0, we have
𝑑𝑡
𝜆0 𝑃0 = 𝜇1 𝑃1
(𝜆𝑖 + 𝜇𝑖 )𝑃𝑖 = 𝜆𝑖−1 𝑃𝑖−1 + 𝜇𝑖+1 𝑃𝑖+1 ∀𝑖 = 1,2, …
𝜆0 𝜆1 𝜆2 𝜆𝑖−2 𝜆𝑖−1 𝜆𝑖 𝜆𝑖+1

0 1 2 ⋯⋯ i-1 i i+1
⋯⋯
20
𝜇1 𝜇2 𝜇3 𝜇𝑖−1 𝜇𝑖 𝜇𝑖+1 𝜇𝑖+2
Steady-State Balance Equations
Therefore, we have
𝜆0
𝑃1 = 𝑃0
𝜇1
and when 𝑖 = 1, (𝜆1 + 𝜇1 )𝑃1 = 𝜆0 𝑃0 + 𝜇2 𝑃2
𝜆
𝜆1 + 𝜇1 0 𝑃0 − 𝜆0 𝑃0
𝜆1 + 𝜇1 𝑃1 − 𝜆0 𝑃0 𝜇1 𝜆0 𝜆1
𝑃2 = = = 𝑃0
𝜇2 𝜇2 𝜇1 𝜇2
In general,
ς𝑖−1
𝑗=0 𝜆𝑗
𝑃𝑖 = 𝑖 𝑃0 −−−− −
ς𝑗=1 𝜇𝑗

21
Steady-State Balance Equations
Another condition: σ∞
𝑖=0 𝑃𝑖 = 1 −−−− −☻

So, together with , we have

∞
ς𝑘−1
𝑗=0 𝜆𝑗
𝑃0 + ෍ 𝑃0 = 1
ς𝑘𝑗=1 𝜇𝑗
𝑘=1
1
𝑃0 = 𝑘−1
∞
ς 𝑗=0 𝜆𝑗
1 + σ𝑘=1 𝑘
ς𝑗=1 𝜇𝑗
For 𝑖 = 1,2, …
ς𝑖−1
𝑗=0 𝜆𝑗 ς𝑖−1
𝑗=0 𝜆𝑗
𝑃𝑖 = 𝑃0 = 𝑘−1
ς𝑖𝑗=1 𝜇𝑗 𝑖 ∞
ς 𝑗=0 𝜆𝑗
(ς𝑗=1 𝜇𝑗 )(1 + σ𝑘=1 𝑘 ) 22
ς𝑗=1 𝜇𝑗
Steady-State Balance Equations
• The derived results enable us to compute some key
performance measures. e.g.,
∞

𝐿 = ෍ 𝑖𝑃𝑖
𝑖=0
∞

𝐿𝑞 = ෍(𝑖 − 𝑠)𝑃𝑖
𝑖=𝑠
where 𝑠 is the number of servers.

23
M/M/1 Model
• In the M/M/1 Model, we assume Poisson arrivals, exponentially
distributed service times, and a single sever.
1 server
Customers
𝜆𝑖 = 𝜆 ∀𝑖
𝜇𝑖 = 𝜇 ∀𝑖
𝜆 𝜆 𝜆 𝜆 𝜆 𝜆 𝜆

0 1 2 ⋯⋯ i-1 i i+1
⋯⋯

𝜇 𝜇 𝜇 𝜇 𝜇 𝜇 𝜇
𝜆
• Let 𝜌 = which is called the utilization ratio (percentage of time
,
𝜇
the server is busy). 24
𝜆𝑖
• By , we have 𝑃𝑖 = 𝑃 = 𝜌𝑖 𝑃0
𝜇𝑖 0
M/M/1 Model
• By ☻, σ∞ 𝑖
𝑖=0 𝜌 𝑃0 = 1, therefore,
1
𝑃0 =
σ∞
𝑖=0 𝜌
𝑖

• For 0 < 𝜌 < 1,

𝑃0 = 1 − 𝜌
𝑃𝑖 = 1 − 𝜌 𝜌𝑖 ∀𝑖 = 0,1,2, …
∞ ∞
𝜌
𝐿 = ෍ 𝑖𝑃𝑖 = ෍ 𝑖 1 − 𝜌 𝜌𝑖 =
1−𝜌
𝑖=0 𝑖=0
𝐿 𝜌 𝜆/𝜇 1
𝑊= = = =
𝜆 𝜆(1 − 𝜌) 𝜆(1 − 𝜌) 𝜇(1 − 𝜌)
1 1 1 𝜌
𝑊𝑞 = 𝑊 − = − =
𝜇 𝜇 1−𝜌 𝜇 𝜇(1 − 𝜌)
𝜌 2
𝐿𝑞 = 𝜆𝑊𝑞 =
1−𝜌
Note that as 𝜌 → 1, the performance measures get very bad.
• For 𝜌 ≥ 1, the people come faster than the server can serve. Thus the queue 25
grows without bound.
M/M/1 Model
Waiting time vs. Utilization
250

200
Waiting time (secs)

150

100

50

0
0.000 0.200 0.400 0.600 0.800 1.000 1.200
Utilization ratio

• Systems perform very well as long as their utilization ratios are less
than about 0.8.
• When the utilization ratio is between 0.8 and 0.9, service begins to
degrade.
26
• Service degrades very rapidly as the utilization ratio goes above 0.9.
M/M/1 Model
• In addition to the average, we are also interested in the
variation.
• Consider the variance of the number of customers in the
system, denoted by N:
∞

𝑉 𝑁 = 𝐸 𝑁2 − 𝐸 𝑁 2
= ෍ 𝑖 2 𝑃𝑖 − 𝐿2
𝑖=0
∞ 2 2
2 𝑖
𝜌 𝜌 + 𝜌2 𝜌
= 1−𝜌 ෍𝑖 𝜌 − = −
1−𝜌 1−𝜌 2 1−𝜌
𝑖=0
𝜌
=
1−𝜌 2
27
M/M/1 Model
Example:
Suppose that there is only one cashier working at Coffee Corner, her
service time is exponentially distributed with an average of 10
seconds, and customers arrive according to a Poisson process with an
arrival rate of 240 people per hour.
60×60 𝜆 240
• 𝜆 = 240, 𝜇 = = 360, 𝜌 = = = 0.667
10 𝜇 360
𝜌 0.667
• 𝐿= = =2
1−𝜌 1−0.667
1 1
• 𝑊= = = 0.008333 = 30𝑠𝑒𝑐
𝜇 1−𝜌 360× 1−0.667
1 1
• 𝑊𝑞 = 𝑊 − = 0.008333 − = 0.005556 = 20𝑠𝑒𝑐
𝜇 360
• 𝐿𝑞 = 𝜆𝑊𝑞 = 240 × 0.005556 = 1.3333
𝜌 0.667 28
• 𝑉𝑎𝑟 𝑁 = = =6
1−𝜌 2 1−0.667 2
• 𝑆𝑡𝑑 𝑁 = 𝑉𝑎𝑟 𝑁 = 6 = 2.449
M/M/1 Model
Example (Cont.)
∞ ∞

𝑃 5 𝑜𝑟 𝑚𝑜𝑟𝑒 𝑖𝑛 𝑠𝑦𝑠𝑡𝑒𝑚 = ෍ 𝑃𝑖 = ෍ 1 − 0.667 0.667𝑖

𝑖=5 𝑖=5
5
1 − 0.667 0.667
= = 0.6675 = 0.13167
1 − 0.667
𝑃 𝑏𝑢𝑠𝑦 = 𝑃 1 𝑜𝑟 𝑚𝑜𝑟𝑒 = 0.667

The following lists the key performance measures for different values
of 𝜆:

29
M/M/1 Queue with a
Restricted Queue Length
• The assumptions are the same as the regular M/M/1 Model but now we
limit the number of customers in the system to K.
1 server
Customers
Max people in the system is K
𝜆, 𝑖 = 0,1,2, … , 𝐾 − 1
𝜆𝑖 = ቊ
0, 𝑖 = 𝐾, 𝐾 + 1, …
𝜇, 𝑖 = 1,2, … , 𝐾
𝜇𝑖 = ቊ
0, 𝑖 = 𝐾 + 1, 𝐾 + 2 …
𝜆 𝜆 𝜆 𝜆 𝜆 𝜆

0 1 2 ⋯⋯ K-2 K-1 K

𝜇 𝜇 𝜇 𝜇 𝜇 𝜇
• Example: Customer Service Hotline with only 30
a single customer service agent and
a limited number of customers on hold.
M/M/1 Queue with a
Restricted Queue Length
Similar to the regular M/M/1 Model, by ,
𝜌𝑖 𝑃 , 𝑖 = 0,1,2, … , 𝐾
𝑃𝑖 = ቊ 0
0, 𝑖 = 𝐾 + 1, …
Assume that 𝜌 ≠ 1. By ☻, we have
𝐾

𝑃0 ෍ 𝜌𝑖 = 1
𝑖=0
1 − 𝜌𝐾+1
𝑃0 =1
1−𝜌
1−𝜌
𝑃0 =
1 − 𝜌𝐾+1
Thus
𝜌𝑖 (1 − 𝜌)
𝑃𝑖 = ൞ 1 − 𝜌𝐾+1 , 𝑖 = 0,1,2, … , 𝐾
0, 𝑖 = 𝐾 + 1, …
𝐾
𝜌𝑖 (1 − 𝜌) 𝜌 1 − 𝐾 + 1 𝜌𝐾 + 𝐾𝜌𝐾+1
𝐿 = ෍𝑖 =
1 − 𝜌𝐾+1 (1 − 𝜌)(1 − 𝜌𝐾+1 )
𝑖=0 31
Note that the above results are also true for 𝜌 > 1.
M/M/1 Queue with a
Restricted Queue Length
Comparing the values of 𝐿 obtained from M/M/1 Models with and without a
restricted queue length for different values of 𝜌 and 𝐾:

• For 𝜌 < 1, as 𝐾 goes up, 𝐿 approaches that of the M/M/1 queue with no
restriction on the queue length.
• For 𝜌 > 1, the results for M/M/1 queue without a restricted queue length
do not apply, but the results for the queue with a restricted number in the
system can still be computed and 𝐿 rapidly approaches 𝐾. 32
• For small values of 𝜌, 𝐾 has little effect on 𝐿; as 𝜌 goes up, the effect of 𝐾
increases.
M/M/1 Queue with a
Restricted Queue Length
• Note that when there are 𝐾 customers in the system, any
additional arrivals are turned away or lost.
• Let 𝜆𝑒𝑓𝑓 be the effective arrival rate.
1 − 𝜌 𝜌𝐾 1 − 𝜌𝐾
𝜆𝑒𝑓𝑓 = 𝜆 1 − 𝑃𝐾 = 𝜆 1 − 𝐾+1 =𝜆
1−𝜌 1 − 𝜌𝐾+1
• Therefore,
𝐿 1 − 𝐾 + 1 𝜌𝐾 + 𝐾𝜌𝐾+1
𝑊= =
𝜆𝑒𝑓𝑓 𝜇(1 − 𝜌)(1 − 𝜌𝐾 )
1
𝑊𝑞 = 𝑊 −
𝜇
𝐿𝑞 = 𝜆𝑒𝑓𝑓 𝑊𝑞
33
M/M/1 Queue with a
Restricted Queue Length
What about 𝜌 = 1?
It is easy to see that 𝑃𝑖 = 𝑃0 ∀𝑖 = 1,2, … , 𝐾
By ☻, we have
1
𝑃𝑖 = ቐ𝐾 + 1 , 𝑖 = 0,1,2, … , 𝐾
0, 𝑖 = 𝐾 + 1, …
Thus,
𝐾
1 𝐾
𝐿 = ෍𝑖 =
𝐾+1 2
𝑖=0
1 𝜆𝐾
𝜆𝑒𝑓𝑓 = 𝜆 1 − 𝑃𝐾 = 𝜆 1 − =
𝐾+1 𝐾+1
𝐿 𝐾 𝐾+1 𝐾+1
𝑊= = × =
𝜆𝑒𝑓𝑓 2 𝜆𝐾 2𝜆
1 𝐾+1 1
𝑊𝑞 = 𝑊 − = −
𝜇 2𝜆 𝜇
𝐾 𝐾
34
𝐿𝑞 = 𝜆𝑒𝑓𝑓 𝑊𝑞 = −
2 𝐾+1
M/M/1 Queue with a
Restricted Queue Length
There is a tradeoff between (i) increasing the capacity of the system (or
percentage of people served) and (ii) decreasing the average waiting time in
the system.
The following figure illustrates this tradeoff for a case in a call centre with only
a single customer service agent that people phone in at a rate of 27 per hour
and the average time the customer service agent spends with a customer is 2
27
minutes. In this case, 𝜌 = 60/2 = 0.9.

35
M/M/s Model
• In the M/M/s Model, we assume Poisson arrivals, exponentially distributed
service times, and s servers.

s servers
Customers ⁞
𝜆𝑖 = 𝜆 ∀𝑖
𝑖𝜇, 𝑖 = 1,2, … , 𝑠
𝜇𝑖 = ቊ
𝑠𝜇, 𝑖 = 𝑠, 𝑠 + 1 …
𝜆 𝜆 𝜆 𝜆 𝜆 𝜆 𝜆

0 1 2 ⋯⋯ s-1 s s+1 ⋯⋯

𝜇 2𝜇 3𝜇 (𝑠 − 1)𝜇 𝑠𝜇 𝑠𝜇 𝑠𝜇
36
• Example: Airline check-in counter
with 𝑠 customer service agents.
M/M/s Model
For utilization ratio 𝜆Τ 𝑠𝜇 < 1, using similar techniques, we obtain
𝜆∕𝜇 𝑖
𝑃0 , 𝑖 = 0,1,2, … , 𝑠
𝑃𝑖 = 𝑖!
𝜆∕𝜇 𝑖
𝑃, 𝑖 = 𝑠 + 1, …
𝑠! 𝑠 𝑖−𝑠 0
𝑠 −1
𝜆Τ𝜇 𝜆Τ𝜇 𝑖 𝑠 𝜆
𝑃0 = ෍ +
𝑖! 𝑠! 𝑠𝜇 − 𝜆
𝑖=0
We can also derive
∞ ∞
𝜆∕𝜇 𝑖 𝜆Τ𝜇 𝑠 𝑠𝜇
𝑃 𝑤𝑎𝑖𝑡 = ෍ 𝑃𝑖 = ෍ 𝑖−𝑠
𝑃0 = 𝑃0
𝑠! 𝑠 𝑠! 𝑠𝜇 − 𝜆
𝑖=𝑠 𝑖=𝑠
𝜆𝜇 𝜆Τ𝜇 𝑠
𝐿𝑞 = 𝑃
𝑠 − 1 ! 𝑠𝜇 − 𝜆 2 0 37
𝑊𝑞 , 𝑊, and 𝐿 can be computed easily with the results of Little’s Law.
M/M/s Model
Example:
Suppose that you are going to check your luggage at an airline check-in
counter with 6 customer service agents. The service time of check-in is
exponentially distributed with a mean of 2 minutes. So 𝜇 = 0.5 (per minute).
Passengers arrive at the check-in counter according to a Poisson process with a
rate of 𝜆.

38
M/M/s Model
Example (Cont.)

• Mean time in the system is always exactly 2 minutes more

than the time a passenger spends waiting in the line.
• As long as the utilization ratio is less than about 0.8, the time 39
spent waiting time is very small. As the utilization ratio
increases beyond 0.8, the waiting time increases dramatically.
M/M/s Model
Example (Cont.)
Suppose that the arrival rate is fixed at 175 per hour. What is the
benefit of adding extra customer service agents to the check-in
counter?

40
 M/M/s Model
Example (Cont.)
Now, suppose that there are 6 departing flights and each
of the 6 customer service agents performs check-in for a
different flight. Assume that the arrival rates of the
passengers of the 6 flights are the same. Which system is
more efficient?
Original New

⁞ ⁞ ⁞
41

M/M/s Model with an arrival rate of 𝜆 M/M/1 Model with an arrival rate of 𝜆/𝑠
M/M/s Model
Example (Cont.)

• M/M/1 queues with 1/6 arrival rate have higher total time in system
and waiting time than those of M/M/6. The difference becomes much
larger as 𝜆 increases.
• Although 𝐿 is smaller in M/M/1, this is not true that there are fewer
people at the check-in counter (including those are waiting) than those
of M/M/6 because there are six M/M/1 queues. Therefore the 𝐿 values
of M/M/1 should be multiplied by 6 to calculate the average number of 42
people at the check-in counter.
• From a customer service point of view, separate queues cannot ensure a
first-come, first-served discipline.
M/M/ ∞ Model
• In the M/M/ ∞ Model, we assume Poisson arrivals, exponentially
distributed service times, and ∞ servers.

∞ servers
No waiting line is formed. ⁞

𝜆𝑖 = 𝜆 ∀𝑖
𝜇𝑖 = 𝑖𝜇 ∀𝑖
𝜆 𝜆 𝜆

0 1 2 ⋯⋯

𝜇 2𝜇 3𝜇
43
• Example: Internet & cloud services.
M/M/ ∞ Model
By similar techniques, we can derive
𝜆/𝜇 𝑖 𝑒 − 𝜆/𝜇
𝑃𝑖 = , 𝑖 = 1,2, …
𝑖!
Note that the above is simply the Poisson probability mass
function with parameter𝜆/𝜇. Thus we have
𝐿 = 𝜆/𝜇
𝑊 = 1/𝜇
Thus the average time in the system for an M/M/ ∞ queue is
simply the mean service time. Finally we have
𝑊𝑞 = 𝑊 − 1/𝜇 = 0
𝐿𝑞 = 0
44
M/M/ 𝑠 Queue with No Waiting
• The assumptions are the same as the regular M/M/s Model but there is no
capacity for waiting.

No waiting line is formed.

𝜆, 𝑖 = 0,1,2, … , 𝑠 − 1 𝒔 servers
𝜆𝑖 = ቊ ⁞
0, 𝑖 = 𝑠, 𝑠 + 1, …
𝑖𝜇, 𝑖 = 1,2, … , 𝑠
𝜇𝑖 = ቊ
0, 𝑖 = 𝑠 + 1, …
𝜆 𝜆 𝜆 𝜆 𝜆

0 1 2 ⋯⋯ s-1 s

𝜇 2𝜇 3𝜇 (𝑠 − 1)𝜇 𝑠𝜇

Example: Parking garages 45

M/M/ 𝑠 Queue with No Waiting
By similar techniques, we can derive
−1
𝑠
𝜌𝑖 𝜌𝑗
𝑃𝑖 = ෍ , 𝑖 = 0,1, … , 𝑠
𝑖! 𝑗!
𝑗=0
𝑖
𝑠−1 𝜌
𝜌 σ𝑖=1
𝐿= 𝑖!
𝑠 𝜌𝑖
σ𝑖=0
𝑖!
where 𝜌 = 𝜆/𝜇.
𝑊 = 1/𝜇
𝑊𝑞 = 0
𝐿𝑞 = 0
46
M/M/ 𝑠 Queue with No Waiting
Example:
Suppose that there is a parking lot with 10 spaces and the time
that vehicles stay at the parking lot is exponentially distributed
with a mean of 2 hours. What are the expected number of
vehicles in the parking lot and the proportion of time the
parking lot being full?

47
M/G/1 Model
• The assumptions are the same as the M/M/1 Model but now the
exponentially distributed service times become service times with a
general distribution.
• Let 𝑆 be the service time. 𝐸 𝑆 = 1/𝜇, 𝑉𝑎𝑟 𝑆 = 𝜎 2 , and 𝜌 =
𝜆𝐸 𝑆 = 𝜆/𝜇.
𝜌2 +𝜆2 𝜎 2 𝜌2 +𝜆2 𝜎2
• Then 𝐿 = 𝜌 + , 𝑊𝑞 =
2 1−𝜌 2𝜆 1−𝜌
• Observation: service time variation hurts!
• For example, for M/D/1,
M/D/1 𝜌2 𝜌 1 M/M/1
𝑊𝑞 = = = 𝑊𝑞
2𝜆 1 − 𝜌 2𝜇 1 − 𝜌 2

M/D/1 1 M/M/1 48
𝐿𝑞 = 𝐿𝑞
2
GI/G/s Model
• The interarrival times and the service times follow general
distributions.
• s servers serve the customers.
𝑉𝑎𝑟(𝐴)
• Let 𝐴 be the interarrival time. Define 𝑐𝑎 = and 𝑐𝑒 =
𝐸 𝐴
𝑉𝑎𝑟(𝑆)
. 𝑐𝑎 is called the coefficient of variation of the
𝐸 𝑆
interarrival time distribution and 𝑐𝑒 is called the coefficient
of variation of the service time distribution.
𝑐𝑎2 + 𝑐𝑒2 𝜌 2 𝑠+1 −1 1
𝑊𝑞 ≈ ∙ ∙
2 𝑠 1−𝜌 𝜇
• Observation: The larger the coefficients of variations, 49
the poor the performance is!
Summary of analytic results

50
Summary of analytic results

51