Julian Klep
OR Models for Pre-Master IEM
Winston Ch. 1, 3, 9, 15, 16, 18, 20
LECTURE 12 – QUEING
M/M/1
𝜆 questions an hour
𝜇 answers can be provided an hour
𝜆 < 𝜇 → statistical equilibrium
Little’s Law Stable equilibrium
o 𝐿=𝜆⋅𝑊
o L = average number of X
present in queuing system
o 𝜆 = average number of
arrivals entering the system
o 𝑊 = average time a
customer spends in the
system
Due to steady state behavior
(equilibrium), the steady state
probability of I customers in the Dynamical / statistical equilibrium
system is denoted by 𝑃𝑖
GEOMETRIC SERIES PROOF OF THEOREM
If 𝜌 < 1 → Σ 𝜌 =1+𝜌+𝜌 +𝜌 +⋯ =( )
If 𝜌 < 1 → Σ 𝑗𝜌 = 𝜌 + 2𝜌 + 3𝜌 + ⋯ = ( )
Thus;
o ∑ 𝜌 = , the formula holds for all 𝜌 (due to l’Hôpital’s rule)
To proof theorem
o ∑ 𝑗𝜌 = ∑ 𝑗𝜌
o Σ 𝑗𝜌 = ∑ (𝑗 + 1)𝜌 − ∑ 𝜌
o Σ 𝑗𝜌 = ∑ 𝜌 − ∑ 𝜌 −1
o Σ 𝑗𝜌 = ∑ 𝜌 − ( )
+1
o ∑ 𝑗𝜌 = 𝜌∑ 𝜌 −( )
+1
( )
o Σ 𝑗𝜌 = ( )
−1−( )
+1
o Σ 𝑗𝜌 = ( )
49
, Julian Klep
OR Models for Pre-Master IEM
Winston Ch. 1, 3, 9, 15, 16, 18, 20
FLOW BALANCE EQUATIONS
State transition diagram:
o 𝜆𝑃 = average number of transitions per hour from state n to state n + 1
o 𝜇𝑃 = average number of transitions per hour from state n to state n – 1
Due to equilibrium, and successive substitution
o 𝜆𝑃 = 𝜇𝑃 → 𝑃 = 𝑃
𝑃 = 𝜌𝑃
o 𝜆𝑃 = 𝜇𝑃 → 𝑃 = 𝑃
𝑃 = 𝜌𝑃
Substituting P1
𝑃 = 𝜌 ⋅ (𝜌𝑃 )
𝑃 =𝜌 𝑃
o 𝜆𝑃 = 𝜇𝑃
𝜆𝜌 𝑃 = 𝜇𝑃
𝑃 =𝜌 𝑃
o Etc.
In general, we state
o (𝜆 + 𝜇)𝑃 = 𝜆𝑃 + 𝜇𝑃
𝑃 = 𝜌 𝑃 (𝑖 = 1, 2, … )
Sum of all probabilities should equal 1, using above formula we get
o 1=∑ 𝑃
o 1=𝑃 ⋅Σ 𝜌 → (Σ 𝜌 = , 𝑖𝑠 𝑡ℎ𝑒 𝑠𝑢𝑚 𝑜𝑓 𝑔𝑒𝑜𝑚𝑒𝑡𝑟𝑖𝑐 𝑠𝑒𝑟𝑖𝑒𝑠 𝑝𝑎𝑔𝑒 46)
o 1=
o 𝑃 = 1−𝜌
In general (Important)
o 𝑃 = 𝑃 ⋅ 𝜌 = (𝟏 − 𝒑)𝝆𝒊 (𝑖 = 0, 1, … )
Utilization 𝜌
o 𝝆 = 𝟏 − 𝑷𝟎
50
OR Models for Pre-Master IEM
Winston Ch. 1, 3, 9, 15, 16, 18, 20
LECTURE 12 – QUEING
M/M/1
𝜆 questions an hour
𝜇 answers can be provided an hour
𝜆 < 𝜇 → statistical equilibrium
Little’s Law Stable equilibrium
o 𝐿=𝜆⋅𝑊
o L = average number of X
present in queuing system
o 𝜆 = average number of
arrivals entering the system
o 𝑊 = average time a
customer spends in the
system
Due to steady state behavior
(equilibrium), the steady state
probability of I customers in the Dynamical / statistical equilibrium
system is denoted by 𝑃𝑖
GEOMETRIC SERIES PROOF OF THEOREM
If 𝜌 < 1 → Σ 𝜌 =1+𝜌+𝜌 +𝜌 +⋯ =( )
If 𝜌 < 1 → Σ 𝑗𝜌 = 𝜌 + 2𝜌 + 3𝜌 + ⋯ = ( )
Thus;
o ∑ 𝜌 = , the formula holds for all 𝜌 (due to l’Hôpital’s rule)
To proof theorem
o ∑ 𝑗𝜌 = ∑ 𝑗𝜌
o Σ 𝑗𝜌 = ∑ (𝑗 + 1)𝜌 − ∑ 𝜌
o Σ 𝑗𝜌 = ∑ 𝜌 − ∑ 𝜌 −1
o Σ 𝑗𝜌 = ∑ 𝜌 − ( )
+1
o ∑ 𝑗𝜌 = 𝜌∑ 𝜌 −( )
+1
( )
o Σ 𝑗𝜌 = ( )
−1−( )
+1
o Σ 𝑗𝜌 = ( )
49
, Julian Klep
OR Models for Pre-Master IEM
Winston Ch. 1, 3, 9, 15, 16, 18, 20
FLOW BALANCE EQUATIONS
State transition diagram:
o 𝜆𝑃 = average number of transitions per hour from state n to state n + 1
o 𝜇𝑃 = average number of transitions per hour from state n to state n – 1
Due to equilibrium, and successive substitution
o 𝜆𝑃 = 𝜇𝑃 → 𝑃 = 𝑃
𝑃 = 𝜌𝑃
o 𝜆𝑃 = 𝜇𝑃 → 𝑃 = 𝑃
𝑃 = 𝜌𝑃
Substituting P1
𝑃 = 𝜌 ⋅ (𝜌𝑃 )
𝑃 =𝜌 𝑃
o 𝜆𝑃 = 𝜇𝑃
𝜆𝜌 𝑃 = 𝜇𝑃
𝑃 =𝜌 𝑃
o Etc.
In general, we state
o (𝜆 + 𝜇)𝑃 = 𝜆𝑃 + 𝜇𝑃
𝑃 = 𝜌 𝑃 (𝑖 = 1, 2, … )
Sum of all probabilities should equal 1, using above formula we get
o 1=∑ 𝑃
o 1=𝑃 ⋅Σ 𝜌 → (Σ 𝜌 = , 𝑖𝑠 𝑡ℎ𝑒 𝑠𝑢𝑚 𝑜𝑓 𝑔𝑒𝑜𝑚𝑒𝑡𝑟𝑖𝑐 𝑠𝑒𝑟𝑖𝑒𝑠 𝑝𝑎𝑔𝑒 46)
o 1=
o 𝑃 = 1−𝜌
In general (Important)
o 𝑃 = 𝑃 ⋅ 𝜌 = (𝟏 − 𝒑)𝝆𝒊 (𝑖 = 0, 1, … )
Utilization 𝜌
o 𝝆 = 𝟏 − 𝑷𝟎
50
