Samenvatting Queuing Problems

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