 

Dr. Nehal Khaled

 Simulation is often used in the analysis of queueing models.
 A simple but typical queueing model:

 Queueing models provide the analyst with a powerful tool for designing and
evaluating the performance of queueing systems.

 Typical measures of system performance:

o Server utilization, length of waiting lines, and delays of customers
o For relatively simple systems, compute mathematically
o For realistic models of complex systems, simulation is usually required.
2
 First, we should define queue characteristics in a consistent way
o Standard Queueing Notation Kendall’s Notation:

A/B/C/N/K/D
• where A is the interarrival time distribution
• where B is the service-time distribution
• where C is number of servers
• where N is system capacity
• where K is population size/ calling population
• where D is Queue’s discipline

3
 A and B can follow any distribution :
 D → Deterministic Distribution is not random
 M → Exponential (Markov) This is probably the most common of the random
distributions
 Ek → Erlang distribution of order k
 G → General denotes distribution not specified; results are valid for all distributions
 Bulk arrivals denoted using superscripts. E.g. M[x]

 C is the number of parallel servers

 One/many (identical) servers
 The A/S/1 queue has a single server and the A/S/c queue c servers.
4
 N is the system capacity(queue length)
 The capacity of queue, or the maximum number of customers allowed in the
queue.
 Limited capacity,
 e.g., an automatic car wash only has room for 10 cars to wait in line to
enter the mechanism.
 Unlimited capacity,
 e.g., concert ticket sales with no limit on the number of people allowed to
wait to purchase tickets.

 If this number is omitted, the capacity is assumed to be unlimited, or infinite.

 This can affect the effective arrival rate, since some arrivals may have to be
discarded

5
 K is the size of the calling population
 The size of the population from which the customers come.
 may be assumed to be finite or infinite.
 Finite population model: if arrival rate depends on 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
 If this number is omitted, the population is assumed to be unlimited, or
infinite.

6
 D is the Queue’s discipline: the logical ordering of customers in a queue that determines
which customer is chosen for service when a server becomes free.

7
 M/M/3/20/1500/FCFS is a queue system with:
 Interarrivals are exponentially distributed
 Service times exponentially distributed
 Three servers
 System capacity 20
 Population size is 1500
 Service discipline is FCFS

 M/M/3: Typically, assume infinite system capacity, infinite population, and FIFO
service. In such cases, last three parameters dropped.

8
 Some important queueing measurements
o L = long-run average number of customers in the system
o LQ = long-run average number in queue
o w = long-run average time spent in system
o wq = long-run average time spent in queue
o  = server utilization (fraction of time server is busy)

9
 An important law in queueing theory states
 Mean number of customers in system L = w

Arrivals Black Box Departures

average number in system = arrival rate × average system time

 where L is the long-run number in the system,
  is the arrival rate
 w is the long-run time in the system

 Often called "Little's Equation"

 This holds for most queueing systems

10
o For simple queueing systems such as those we have been examining, stability can be
determined in a fairly easy way
• The arrival rate, , must be less than the service rate
• i.e. customers must arrive with less frequency than they can be served
• Consider a simple single queue system with a single server (G/G/1//)
• Define the service rate to be 
• This system is stable if  < 

• If  > , then, over a period of time there is a net rate of increase in the system of  – 

• If we have a system with multiple servers (ex: G/G/c//) then it will be stable if the net service
rate of all servers together is greater than the arrival rate
• If all servers have the same rate , then the system is stable if  < c

11
 Definition: the proportion of time that a server is busy.
 server utilization is ρ.

 For a single-server stable queue:  = E(s)=  1



 For G/G/c/∞/∞ queues: ρ=  / c

 Example: A physician who schedules patients every 10 minutes and spends Si minutes with
the ith patient:
 9 minutes with probability 0.9
Si = 
12 minutes with probability 0.1

o Arrivals are deterministic, A1 = A2 = … = -1 = 10.

o Services are stochastic, E(Si) = 9*0.9+12*0.1=9.3 min
o On average, the physician's utilization =  = E(s) = 0.93 < 1.

13
 Markovian models: exponential-distribution arrival process (arrival rate = ).
 Service times may be exponentially distributed as well (M) or arbitrary (G).
 A queueing system is in statistical equilibrium if the probability that the system is in a
given state is not time dependent:
P( L(t) = n ) = Pn(t) = Pn.

 Markovian means that a certain state(n) depends only on the previous state (n-1) or next
state (n+1)

14
 the steady-state parameter, L, the time-average number of customers in the system is:

L=  nP
n =0
n

o Apply Little’s equation to the whole system and to the queue alone:

L 1
w= , wQ = w −
 
LQ = wQ

15
 State transition diagram
 Balance equations and 𝑃𝑘
 Zero state
 Average number of customers in the system
 Average time spent in the system

16
      

0 1 2 3 ... k-2 k-1 k k+1 ...

     

17
State Rate In = Rate Out
0 𝜇𝑃1 = 𝜆𝑃0 (eq 1)
1 𝜆𝑃0 + 𝜇𝑃2 = 𝜆 + 𝜇 𝑃1 (eq 2)

2 𝜆𝑃1 + 𝜇𝑃3 = (𝜆 + 𝜇)𝑃2 (eq 3)

.... ...................
k-1 𝜆𝑃𝑘−2 + 𝜇𝑃𝑘 = 𝜆 + 𝜇 𝑃𝑘−1
k 𝜆𝑃𝑘−1 + 𝜇𝑃𝑘+1 = 𝜆 + 𝜇 𝑃𝑘
     
0 1 2 3 ... k-2 k-1 k k+1 ...
      18
 𝜆
From eq.1, we find 𝑃1 = 𝑃0
𝜇
𝜆 2
Sub. In eq.2, then 𝑃2 = 𝑃0
𝜇
𝜆 3
Sub. In eq.3, then 𝑃3 = 𝑃0
𝜇
𝜆 𝑘
Consequently, 𝑃𝑘 = 𝑃0
𝜇

19
We know that, σ∞
𝑘=0 𝑃𝑘 = 1
∞ 𝑘 ∞ 𝑘
𝜆 𝜆 ∞
∴෍ 𝑃0 = 1 ⇒ 𝑃0 ෍ =1 1
𝜇 𝜇 ෍ 𝑎𝑘 =
1−𝑎
𝑘=0 𝑘=0 𝑘=0

1 1 𝝀
∴ 𝑃0 = =1 ⇒ ∴ 𝑷𝟎 = 𝟏 −
∞ 𝜆 𝑘 𝝁
σ𝑘=0 ൘1− 𝜆
𝜇 𝜇

20
 𝜆 𝑘 𝜆
∵ 𝑃𝑘 = 𝑃0 , and 𝑃0 = 1 −
𝜇 𝜇
𝑘
𝜆 𝜆
∴ 𝑃𝑘 = 1 −
𝜇 𝜇

21
For M/M/1, Find the probability that there is n customers or less than that.

𝑛 𝑛 𝑘
𝜆 𝜆
𝑃 𝑘 ≤ 𝑛 = ෍ 𝑃𝑘 = 1 − ෍
𝜇 𝜇
𝑘=0 𝑘=0

𝑛 𝑛+1
1 − 𝑎
෍ 𝑎𝑘 =
1−𝑎
𝑘=0

22
 𝑛 𝑛 𝑘
𝜆 𝜆
𝑃 𝑘 ≤ 𝑛 = ෍ 𝑃𝑘 = 1 − ෍
𝜇 𝜇
𝑘=0 𝑘=0
𝑛+1
𝜆
𝜆 1− 𝜇
𝑛+1
𝜆
𝑃 𝑘 ≤𝑛 = 1− =1−
𝜇 𝜆 𝜇
1−
𝜇
𝑛 𝑛+1
1 − 𝑎
෍ 𝑎𝑘 =
1−𝑎
𝑘=0

23
For M/M/1, Find the probability that there is more than n customers in the
queue.
𝑛+1
𝜆
𝑃 𝑘 >𝑛 =1−𝑃 𝑘 ≤𝑛 =
𝜇

24
The average number of customers in the system could be calculated as
follows:
∞ ∞ 𝑘
𝜆 𝜆
𝐿 = ෍ 𝑘𝑃𝑘 = 1 − ෍𝑘
𝜇 𝜇
𝑘=0 𝑘=0

25
 𝐿 𝜌 1
𝑤= =
𝜆 1−𝜌𝜆
1/𝜇
𝑤=
1−𝜌

26
 =  / , Pn = (1 −  ) n
  2 2
L= = , LQ = =
 −  1−   ( −  ) 1 − 
1 1  
w= = , wQ = =
 −   (1 −  )  ( −  )  (1 −  )

27
• Single-chair unisex hair-styling shop
• Interarrival and service times are exponentially distributed
•  = 2 customers/hour and µ = 3 customers/hour

= = 2 L=

=
2
= 2 Customers
 3  −  3− 2
1
P0 = 1−  = w = L = 2 = 1hour
3  2
1 1 2
P1 =1/3*2/3=2/9 wQ = w − = 1− = hour
 3 3

P2 =1/3*(2/3) =4/27
2 2 4 4
LQ = = = Customers
 (  −  ) 3(3 − 2) 3
L = LQ +  = 4 + 2 = 2 Customers
3
16
P4 = 1−  Pn =
n=0 81  3 3
Thank you

29