Transcript [slides] Queueing theory

Queueing Theory
 Specification of a Queue
Source
• Finite
• Infinite
Arrival Process
Service Time Distribution
Maximum Queueing System Capacity
Number of Servers
Queue Discipline
Queueing Theory
1
Queueing Theory(cont.)
 Specification of a Queue(cont.)
Traffic Intensity (l/m)
Note: E[s] / E[t] = lE[s] = l/m
 Server Utilization
Probability that N customers are in the system
at time t.
Queueing Theory
2
Queueing Theory(cont.)
 Relationships:
 L = lW
(L: avg # in the system)
 Lq = lWq
(Lq : avg # in queue)
 W = Wq + 1/m (W: avg waiting time in sys.)
(Wq: avg waiting time in queue)
 Note: All four(L, Lq, W , Wq) can be determined
after ONE is found
Queueing Theory
3
Birth-And-Death Process
State:
l0
0
1
m1
2
m2
lN
l N-2 l N-1
l1
....
N-2
N-1
m N-1
N
mN
N+1
....
m N+1
In the long run, we have:
Rate IN = Rate Out Principle
Queueing Theory
4
Birth-And-Death Process(cont.)
 Equation Expressing This:
State
Rate In = Rate Out
0
m1P1 = l0P0
1
l0P0 + m2P2 = (l1 + m1) P1
2
l1P1 + m3P3 = (l2 + m2) P2
....
...................
N-1
lN-2PN-2 + mNPN = (lN-1 + mN-1) PN-1
N
lN-1PN-1 + mN+1PN+1 = (lN + mN) PN
....
...................
Queueing Theory
5
Birth-And-Death Process(cont.)
 Finding Steady State Process:
State
0: P1 = (l0 / m1) P0
1: P2 = (l1 / m2) P1 + (m1P1 - l0P0) / m2
= (l1 / m2) P1 + (m1P1 - m1P1) / m2
= (l1 / m2) P1
l1l0
P0
=
m 2 m1
Queueing Theory
6
Birth-And-Death Process(cont.)
 Finding Steady State Process(cont.):
State
n-1: Pn = (ln-1 / mn) Pn-1 + (mn-1Pn-1- ln-2Pn-2) / mn
= (ln-1 / mn) Pn-1 + (mn-1Pn-1- mn-1Pn-1) / mn
= (ln-1 / mn) Pn-1
ln -1ln -2  l0

P0
m n m n -1  m1
Queueing Theory
7
Birth-And-Death Process(cont.)
 Finding Steady State Process(cont.):
N: Pn+1 = (ln / mn+1) Pn+ (mnPn - ln-1Pn-1) / mn+1
= (ln / mn+1) Pn
ln ln -1  l0

P0
m n 1m n  m1
To Simplify:
Let C = (ln-1 ln-2 .... l0) / (mn mn-1 ......... m1)
Then Pn = Cn P0 , N = 1, 2, ....
Queueing Theory
8
M/M/1
 Recall:
r = l/ m
< 1 (for steady-state)
Cn = (l / m)n = rn , for n = 1, 2, ...
Pn = Cn × P0
The requirement that Sn0 Pn = 1
=> [1 + Sn1 Cn] P0 = 1
=> P0 = 1 / (1 + Sn1 Cn)
= 1 / (1 + Sn1 rn)
= 1 / (r0 + Sn1 rn) (r0  1)
Queueing Theory
9
M/M/1(cont.)
P0 = 1 / (Sn0 rn)
= (Sn0 rn) -1
= {1 / (1 - r)} -1
=1-r
Thus, Pn = (1 - r) rn , for n = 0, 1, 2,...
Note:
1) Sni0 xi = (1 - xn+1) / (1 - x), for any x,
2) Sn0 xn = 1 / (1 - x), if |x| < 1.
Queueing Theory
10
M/M/1(cont.)
Consequently,

L   n(1  r ) r n
n 0
d n
d   n
 (1  r ) r 
r  (1  r ) r
 r 
dr  n 0 
n  0 dr

d
1
1
 (1  r ) r
 (1  r ) r
dr (1  r )
(1  r ) 2
 r (1  r )
or
 l (m  l )
Queueing Theory
11
M/M/1(cont.)
Similarly,
Lq = Sn1 (n - 1) Pn
= Sn1 nPn - Sn1 Pn
= Sn0 nPn - (Sn0 Pn - P0)
= L - 1(1 - P0)
= r / (1 - r) - 1 + (1 - r)
= r2 / (1 - r) or
= l2 / m(m - l)
Queueing Theory
12
M/M/1 Example I
Traffic to a message switching center for one of the
outgoing communication lines arrive in a random
pattern at an average rate of 240 messages per
minute. The line has a transmission rate of 800
characters per second. The message length
distribution (including control characters) is
approximately exponential with an average length
of 176 characters. Calculate the following
principal statistical measures of system
performance, assuming that a very large number
of message buffers are provided:
Queueing Theory
13
M/M/1 Example I (cont.)
 (a) Average number of messages in the system
 (b) Average number of messages in the queue
waiting to be transmitted.
 (c) Average time a message spends in the system.
 (d) Average time a message waits for transmission
 (e) Probability that 10 or more messages are
waiting to be transmitted.
 (f) 90th percentile waiting time in queue.
Queueing Theory
14
M/M/1 Example I (cont.)
 E[s] = Average Message Length / Line Speed
= {176 char/message} / {800 char/sec}
= 0.22 sec/message
or
 m = 1 / 0.22 {message / sec}
= 4.55 message / sec
 l = 240 message / min
= 4 message / sec
 r = l E[s] = l / m
= 0.88
Queueing Theory
15
M/M/1 Example I (cont.)
 (a) L= r / (1 - r) = 7.33 (messages)
 (b) Lq = r2 / (1 - r) = 6.45 (messages)
 (c) W = E[s] / (1 - r) = 1.83 (sec)
 (d) Wq = r × E[s] / (1 - r) = 1.61 (sec)
 (e) P [11 or more messages in the system]
= r11 = 0.245
 (f) pq(90) = W ln{(100-90) r}
= W ln(10r)
= 3.98 (sec)
Queueing Theory
16
M/M/1 Example II
A branch office of a large engineering firm has one
on-line terminal that is connected to a central
computer system during the normal eight-hour
working day. Engineers, who work throughout the
city, drive to the branch office to use the terminal
to make routine calculations. Statistics collected
over a period of time indicate that the arrival
pattern of people at the branch office to use the
terminal has a Poisson (random) distribution, with
a mean of 10 people coming to use the terminal
each day. The distribution of time spent by an
engineer at a terminal is exponential, with a
Queueing Theory
17
M/M/1 Example II (cont.)
mean of 30 minutes. The branch office receives
complains from the staff about the terminal
service. It is reported that individuals often wait
over an hour to use the terminal and it rarely takes
less than an hour and a half in the office to
complete a few calculations. The manager is
puzzled because the statistics show that the
terminal is in use only 5 hours out of 8, on the
average. This level of utilization would not seem
to justify the acquisition of another terminal. What
insight can queueing theory provide?
Queueing Theory
18
M/M/1 Example II (cont.)
 {10 person / day}×{1 day / 8hr}×{1hr / 60 min}
= 10 person / 480 min
= 1 person / 48 min
==> l = 1 / 48 (person / min)
 30 minutes : 1 person
= 1 (min) : 1/30 (person)
==> m = 1 / 30 (person / min)
 r = l / m = {1/48} / {1/30} = 30 / 48
=5/8
Queueing Theory
19
M/M/1 Example II (cont.)
 Arrival Rate
l = 1 / 48 (customer / min)
 Server Utilization
r = l / m = 5 / 8 = 0.625
 Probability of 2 or more customers in system
P[N  2] = r2 = 0.391
 Mean steady-state number in the system
L = E[N] = r / (1 - r) = 1.667
 S.D. of number of customers in the system
sN = sqrt(r) / (1 - r) = 2.108
Queueing Theory
20
M/M/1 Example II (cont.)
 Mean time a customer spends in the system
W = E[w] = E[s] / (1 - r) = 80 (min)
 S.D. of time a customer spends in the system
sw = E[w] = 80 (min)
 Mean steady-state number of customers in queue
Lq = r2 / (1 - r) = 1.04
 Mean steady-state queue length of nonempty Qs
E[Nq | Nq > 0] = 1 / (1 - r) = 2.67
 Mean time in queue
Wq = E[q] = r×E[s] / (1 - r) = 50 (min)
Queueing Theory
21
M/M/1 Example II (cont.)
 Mean time in queue for those who must wait
E[q | q > 0] = E[w] = 80 (min)
 90th percentile of the time in queue
pq(90) = E[w] ln (10 r)
= 80 * 1.8326
= 146.6 (min)
 90th percentile of the time in system
pw(90) = 2.3 * E[w] = 184 (min)
Queueing Theory
22
M/M/1 Example II (cont.)
 Defined by equation P[w  pw(90)] = 0.9
response time of system pw(90) - amount of time
in the system such that 90% of all arriving
customers spend less than this amount of time in
the system
Queueing Theory
23
M/M/s (s > 1)
Recall: l n = l , for n = 0, 1, 2,.....
m n = n m , for n = 1, 2,..., s
= s m , for n = s, s+1,...
Rate Diagram
l
0
l
1
m
l
2
2m
l
3
m
...
s-2
s-1
(s-1)m sm
Queueing Theory
l
l
s
s+1
...
sm
24
M/M/s (cont.)
State
0
1
2
....
s-1
s
s+1
....
Rate In = Rate Out
mP1 = lP0
2mP2 + lP0 = (l + m) P1
3mP3 + lP1 = (l + 2m) P2
...................
smPs + lPs-2 = {l + (s-1)m} Ps-1
smPs+1 + lPs-1 = (l + sm) Ps
smPs+2 + lPs = (l + sm) Ps+1
...................
Queueing Theory
25
M/M/s (cont.)
 Now, solve for P1 , P2, P3... in terms of P0
P1 = (l / m) P0
P2 = (l / 2m) P1 = (1/2!) × (l / m)2 P0
P3 = (l / 3m) P2 = (1/3!) × (l / m)3 P0
.........
Ps = (1/s!) × (l / m)s P0
Ps+1 = (1/s) × (l / m) Ps

l m
=
Queueing Theory
s
s!
l

P0
sm
26
M/M/s (cont.)
Ps  2
(l / m )
 (1 / s)  (l / m ) Ps 1 
s!
s
2
 l 
  P0
 sm 

Ps  j
(l / m )
 (1 / s )  (l / m ) Ps  j 1 
s!
s
j
 l 
  P0
 sm 

Queueing Theory
27
M/M/s (cont.)
Therefore, if we denote Pn = Cn× P0 ,
(l / m)n
Cn = ---------- , for n = 1, 2, ...., s.
n!
ns
s
(l / m )  l 
and Cn 
, for n = s+1, s+2,...
 
s!  sm 
then

l m n

s! s n  s
Queueing Theory
28
M/M/s (cont.)
So, if l < sm >
1
P0 
 s1 l m n l m s 
n s 
l sm  



s! n s
 n 0 n!

1

 s 1 l m n l m s

1



s! 1  (l sm) 
 n 0 n!
(l m ) n
Pn 
P0 ,
n!
(l m ) n

P0 ,
n s
s!s
if 0  n  s
if s  n
Queueing Theory
29
M/M/s (cont.)
Now solve for Lq: Note, r = l / sm
Lq = Sns (n - s) Pn
= Sj0 j Ps+j ; Note, n = s + j
s
(l
/
m)

= S j ---------- rj P0
j=0
s!
(l / m)s
d

= P0 ------------ r S ------ rj
j=0
s!
dr
Queueing Theory
30
M/M/s (cont.)
(l / m)s
d 
Lq = P0 ------------ r ------ S rj
s!
dr j=0
(l / m)s
d
1
= P0 ------------ r ------ --------s!
dr (1 - r)
(l / m)s
r
= P0 ------------ ---------2
s!
(1 - r)
Queueing Theory
31
M/M/s (cont.)
(l / m)s r
Lq = P0 ----------- --------, r = l / sm
s!
(1 - r)2
(Lq : avg # in queue)
Wq = Lq / l
(Wq: avg waiting time in Q)
W = Wq + 1 / m
(W: avg waiting time in sys.)
L = l (Wq + 1/m) (L: avg # in the system)
= Lq + l / m
Queueing Theory
32
Steady-State Parameters of
M/M/s Queue
r
= l / sm
1

 s 1 l / m    l  1 sm  

P0  

   
n!   m  s! sm  l  
n 0





1
n

1 
 s 1 sr   

s 1
  

  sr 

s! 1  r  

 n 0 n!  

P(L()  s) = {(l/m)s P0} / {s!(1- l/sm)}
= {(sr)s P0} / {s! (1 - r)}
n
s
Queueing Theory
33
Steady-State Parameters of
M/M/s Queue (cont.)
L = sr + {(sr)s+1 P0} / {s (s!) (1 - r)2}
= sr + {r P (L()  s) } / {1 - r}
W =L/l
Wq = W - 1/m
Lq = l Wq
= {(sr)s+1 P0} / {s (s!) (1 - r)2}
= {r P (L()  s) } / {1 - r}
L - Lq = l / m = sr
Queueing Theory
34
M/M/s Case Example I
Example:
M/M/2 ; s = 2
m = 1/8 (=service rate/server)
l = 1 10 ,
110
0
110
1
1
110
2
21
110
3
21
.......
21
r  l  sm  110  21   0
Queueing Theory
35
M/M/s Case Example I (cont.)
P0 
1
 0.80 0.81 0.82
1 





1!
2!
1  0.4 
 0!
= 0.429 (@ 43% of time, system is empty)
as compared to s = 1: P0 = 0.20
(l / m)s r
Lq = P0 ----------- --------s!
(1 - r)2
= 0.429 × {0.82 ´ 0.4} / { 2! ´ (1 - 0.4)2 }
= 0.152
Queueing Theory
36
M/M/s Case Example I (cont.)
Wq = Lq / l = 0.152 / (1/10) = 1.52 (min)
W = Wq + 1 / m = 1.52 + 1 / (1/8) = 9.52 (min)
What proportion of time is both repairman busy?
(long run)
P(N  2) = 1 - P0 - P1
= 1 - 0.429 - 0.343
= 0.228
(Good or Bad?)
Queueing Theory
37
M/M/s Example II
Many early examples of queueing theory applied to
practical problems concerning tool cribs.
Attendants manage the tool cribs while mechanics,
assumed to be from an infinite calling population,
arrive for service. Assume Poisson arrivals at rate
2 mechanics per minute and exponentially
distributed service times with mean 40 seconds.
Queueing Theory
38
M/M/s Example II (cont.)
l = 2 per minute, and m = 60/40 = 3/2 per minute.
Since, the offered load is greater than 1, that is,
since, l / m = 2 / (3/2) = 4/3 > 1, more than one
server is needed if the system is to have a
statistical equilibrium. The requirement for steady
state is that s > l / m = 4/3. Thus, at least s = 2
attendants are needed. The quantity 4/3 is the
expected number of busy server, and for s  2,
r = 4 / (3s) is the long-run proportion of time each
server is busy. (What would happen if there were
only s = 1 server?)
Queueing Theory
39
M/M/s Example II (cont.)
Let there be s = 2 attendants. First, P0 is calculated as
1
 1 4 / 3   4  1 2(3 / 2)  
P0  

   
 n 0 n!   3  2! 2(3 / 2)  2  
= {1 + 4/3 + (16/9)(1/2)(3)} -1
= {15 / 3}-1 = 1/5 = 0.2
The probability that all servers are busy is given by
P(L()  2) = {(4/3)2 (1/5)} / {2!(1- 2/)}
= (8/3) (1/5) = 0.533
n
2
Queueing Theory
40
M/M/s Example II (cont.)
Thus, the time-average length of the waiting line of
mechanics is
Lq = {(2/3)(8/15)} / (1 - 2/3) = 1.07 mechanics
and the time-average number in system is given by
L = Lq+ l/m = 16/15 + 4/3 = 12/5 = 2.4 mechanics
Using Little’s relationships, the average time a
mechanic spends at the tool crib is
W
= L / l = 2.4 / 2 = 1.2 minutes
while the avg time spent waiting for an attendant is
Wq = W - 1/m = 1.2 - 2/3 = 0.533 minute
Queueing Theory
41
M/M/1/N (single server)
Undefined
Rate Diagram
l
0
l
1
m
l
2
m
l
3
...
N-2
m
N-1
m
0
l
N
m
N+1
0
Undefined
Queueing Theory
42
M/M/1/N (cont.)
1. Form Balance Equations:
2. Solve
for
P
:
0
N
Pn  1 or

n 0
P0 + (l/m)1 P0 + ××××  (l/m)N P0 = 1
P0 {1+ (l/m)1 + ××××  (l/m)N } = 1
N
P0 = 1 / {  ( l / m ) n }
n 0

1
1  (l / m) N 1 


 1  (l / m) 
= (1 - r) / (1 - rN+1)
Queueing Theory
43
M/M/1/N (cont.)
 1 r  n
So, Pn  
r
N 1 
1  r 
, for n = 0, 1, 2, ..., N
Hence,
N
L = S n Pn
n=0
1-r
d
N
= ---------- r S ----- rn
1- rN+1 n=0 dr
1-r
d N
= ---------- r ----- S rn
1- rN+1
dr n=0
Queueing Theory
44
M/M/1/N (cont.)
1 r
d 1  r N1 
L
r 

N 1
1 r
dr  1  r 
N 1
 ( N  1)r  Nr  1
r
(1  r N 1 )(1  r)
N
r
( N  1)r N 1


N 1
(1  r) (1  r )
Queueing Theory
45
M/M/1/N (cont.)
As usual (when s = 1)
Lq = L - (1- P0)
W = L / le , where le = l (1 - PN)
Wq = Lq / le
Queueing Theory
46
M/M/1/N Example
The unisex barbershop can hold only three
customers, one in service and two waiting.
Additional customers are turned away when the
system is full. Determine the measures of
effectiveness for this system. The traffic intensity
is l / m = 2 / 3.
The probability that there are three customers in the
system is computed by
Pn = P3 = {(1-2/3) (2/3)3} / { 1 - (2/3)4} = 8 / 65
= 0.123
Queueing Theory
47
M/M/1/N Example (cont.)
The expected # of customers in the shop is given by
2/3 {1 - 4(2/3)3 + 3(2/3)4} 66
L = -------------------------------=
-----{1 - (2/3)4} (1 - 2/3)
65
= 1.015 (customers)
Now, the effective arrival rate, le , is given by
le = l (1 - Pn) = 2(1 - 8/65) = 2 × 57 / 65
=114/65
= 1.754 (customers/hour)
Then W can be calculated as
W = L / le = 1.015 / 1.754 = 0.579 (hour)
Queueing Theory
48
M/M/1/N Example (cont.)
In order to calculate Lq, first determine P0 as
P0 = (1 - r) / (1 - rN+1) = (1 - 2/3) / {1 - (2/3)4}
= {1/3} / {65/81} = 27 / 65
= 0.415
Then the average length of the queue is given by
Lq = L - (1- P0) = 1.015 - (1 - 0.415)
= 0.43 (customer)
Queueing Theory
49
M/M/1/N Example (cont.)
Note that 1- P0 = 0.585 is the average number of
customers being served, or equivalently, the
probability that the single server is busy. Thus the
server utilization, or proportion of time the server
is busy in the long run, is given by
r = 1- P0 = le / m = 0.585
Finally, the waiting time in the queue is determined
by Little’s equation as
Wq = Lq / le = 0.43 / 1.754 = 0.245 (hour)
Queueing Theory
50
M/M/1/N Example (cont.)
The reader should compare these results to those of
the unisex barbershop before the capacity
constraint was placed on the system. Specifically,
in systems with limited capacity, the traffic
intensity l / m can assume any positive value and
no longer equals the server utilization r = le / m.
Note that server utilization decreases from 67% to
58.5% when the system imposes a capacity
constraint.
Queueing Theory
51
M/M/1/N Example (cont.)
Since P0 and P3 have been computed, it is easy to
check the value of L using equation L = SNn0 nPn.
To make the check requires computation of P1 & P2:
P1 = {(1 - 2/3)(2/3)} / {1- (2/3)4} = 18/65 = 0.277
Since P0 + P1 + P2 + P3 = 1,
P2
= 1 - P0 - P1 - P3 = 1 - 27/65 - 18/65 8/65
= 12 / 65
= 0.185
Queueing Theory
52
M/M/1/N Example (cont.)
L =
N
 nP
n 0
n
= 0×(27/65) + 1×(18/65) + 2×(12/65) + 3×(8/65)
= 66 / 65
= 1.015 (customer)
which is the same value as the expected
number computed.
Queueing Theory
53
M/M/s/N
Undefined
Rate Diagram
l
0
l
1
m
l
2
2m
...
s-1
l
s
sm
s+1
sm
0
l
...
N-1
N
sm
N+1
0
Undefined
Queueing Theory
54
Steady-State Parameters of
M/M/s/N
P0 
1
s
N


(l / m )n (l / m )s
ns

( l / sm ) 
1
s! ns 1
 n1 n!



(l / m ) n
Pn 
P0 , for n = 1, 2, ... s
n!
n
(l / m )
for
n
=
s,
s+1,
...
N

P
,
0
n s
s!s
 0, for n > N
Queueing Theory
55
Steady-State Parameters of
M/M/s/N (cont.)
s 1
s 1
n 0
n 0
L   nPn  Lq  s (1   Pn )
P0 (l / m ) s r
N s
N s
Lq 
1

r

(
N

s
)
r
(1  r )
2
s!(1  r )


Note: W and Wq are obtained from these quantities
just as shown for the single server case.
Queueing Theory
56
Steady-State Parameters of
M/G/1 Queue
r =l/m
 L = r + {l2 (m2 + s2)} / {2 (1 - r)}
= r + {r2 (1 + s2 m2)} / {2 (1 - r)}
 W = m1 + {l (m2 + s2)} / {2 (1 - r)}
 Wq = {l (m2 + s2)} / {2 (1 - r)}
 Lq = {l2 (m2 + s2)} / {2 (1 - r)}
= {r2 (1 + s2 m2)} / {2 (1 - r)}
 P0 = 1 - r
Queueing Theory
57
M/G/1 Example
There are two workers competing for a job. Able
claims an average service time which is faster than
Baker’s, but Baker claims to be more consistent, if
not as fast. The arrivals occur according to a
Poisson process at a rate of l= 2 per hour. (1/30
per minute). Able’s statistics are an average
service time of 24 minutes with a standard
deviation of 20 minutes. Baker’s service statistics
are an average service time of 25 minutes, but a
standard deviation of only 2 minutes. If the
average length of the queue is the criterion for
hiring, which worker should be hired?
Queueing Theory
58
M/G/1 Example (cont.)
 For Able,
l = 1/30 (per min), m1 = 24 (min),
r = l / m  24/30  5
s2  202 = 400(min2)
Lq = {l2 (m2 + s2)} / {2 (1 - r)}
= {(1/30)2 (242 + 400)} / {2 (1-4/5)}
= 2.711 (customers)
 For Baker,
l = 1/30 (per min), m1 = 25 (min),
r = l / m  25/30  56
s2  22 = 4(min2)
Lq = {(1/30)2 (252 + 4)} / {2 (1-5/6)}
= 2.097 (customers)
Queueing Theory
59
M/G/1 Example (cont.)
Although working faster on the average, Able’s
greater service variability results in an average
queue length about 30% greater than Baker’s. On
the other hand, the proportion of arrivals who
would find Able idle and thus experience no delay
is P0 = 1 - r = 1 / 5 = 20%, while the proportion
who would find Baker idle and thus experience no
delay is P0 = 1 - r = 1 / 6 = 16.7%. On the basis of
average queue length, Lq , Baker wins.
Queueing Theory
60
Steady-State Parameters of
M/Ek/1 Queue
l
1k
l2
1+k
r2
L = --- + ------ ---------- = r + ------- -------m
2k m(m- l)
2k 1 - r
1
1
1k
l
1+k
r
m
W = --- + ------ ---------- = m1 + ------- -------m
2k m(m- l)
2k 1 - r
1k
l
1+k r m1
Wq = ------ ---------- = ------- -------2k m(m- l)
2k 1 - r
Lq
1k
l2
1+k
r2
= ------ ---------- = ------- -------2k m(m- l)
2k 1 - r
Queueing Theory
61
M/Ek/1 Example
Patient arrive for a physical examination according
to a Poisson process at the rate of one per hour.
The physical examination requires three stages,
each one independently and exponentially
distributed with a service time of 15 minutes. A
patient must go through all three stages before the
next patient is admitted to the treatment facility.
Determine the average number of delayed patients
,Lq , for this system.
Queueing Theory
62
M/Ek/1 Example (cont.)
If patients follow this treatment pattern, the
service-time distribution will be Erlang of order
k=3. The necessary treatment parameters are l =
1/60 per minute and m = 1/45 per minute; thus
1k
Lq
------ 1/60)
l2
1+3
(1/60)2
= ------ ---------- = ------- -----------------2k m(m- l)
2 x 3 (1/45) (1/45
2 135

= ---- ------ = ---- (patients)
3 60
2
Queueing Theory
63
Steady-State Parameters of
M/D/1 Queue
l
1
l2
1
r2
L = --- + --- ---------- = r + --- -------m
2 m(m- l)
2 1-r
W
1
1
l
1 1 r m1
= --- + --- ---------- = m + --- -------m
2 m(m- l)
2 1-r
1
l
1 r m1
= --- ---------- = --- -------2 m(m- l)
2 1-r
1
l
1 r2
= --- ---------- = --- ------2 m(m- l)
2 1-r
Wq
Lq
Queueing Theory
64
M/D/1 Example
Arrivals to an airport are all directed to the same
runway. At a certain time of the day, these arrivals
are Poisson distributed at a rate of 30 per hour.
The time to land an aircraft is a constant 90
seconds. Determine Lq, Wq, L and W for this
airport. In this case l= 0.5 per minute, and 1/m =
1.5 minutes, or m = 2/3 per minute.
Queueing Theory
65
M/D/1 Example (cont.)
The runway utilization is
r  l  m = (1/2) / (2/3) = 3/4
The steady-state parameters are given by
Lq = {(3/4) 2} / {2 (1 - 3/4)}
= 9 / 8 = 1.125 aircraft
Wq = Lq / l = (9/8) / (1/2) = 2.25 minutes
W = Wq + 1 / m = 2.25 + 1.5 = 3.75 minutes
L = Lq + l / m = 1.125 + 0.75 = 1.875 aircraft
Queueing Theory
66
Steady-State Parameters of
M/G/ Queue
P0
Pn
W
Wq
L
Lq
= e-l/m
= {e-l/m (l/m)n} / n! , n = 0, 1,...
=1/m
=0
=l/m
=0
Queueing Theory
67
M/G/ Example
Prior to introducing their new on-line computer
information service, The Connection must plan
their system capacity in terms of the number of
users that can be logged on simultaneously. If the
service is successful, customers are expected to
log on at a rate of l = 500 per hour, according to a
Poisson process, and stay connected for an
average of 1/m = 20 minutes (or 1/3 hour). In the
real system there will be an upper limit on
simultaneous users, but for planning purpose The
Queueing Theory
68
M/G/ Example (cont.)
Connection can pretend that the number of
simultaneous users is infinite. An M/G/ model of
the system implies that the expected number of
simultaneous users is L = l/m = 500(3) = 1500, so
a capacity greater than 1500 is certainly required.
To ensure that they have adequate capacity 95% of
the time, The Connection could allow the number
of simultaneous users to be the smallest value s
such that
Queueing Theory
69
M/G/ Example (cont.)
P(L()  s) = Ssn0 Pn
= Ssn0 {e-1500 (1500)n}/n!  0.95
A capacity of s=1564 simultaneous users satisfies
this requirement.
Queueing Theory
70
Steady-State Parameters of
M/M/s/K/K Queue
K
 s 1  K  l 
K!
P0       
ns
n
m
(
K

n
)!
s
!
s
 n 0    n  s
n
l
 
m
n



1
n
 K  l 
Pn     P0 ,
 n  m 
n = 0, 1, ..., s-1
n
l
K!
  P0 , n = s, s+1, ... K

n s 
(K  n )!s!s  m 
Queueing Theory
71
Steady-State Parameters of
M/M/s/K/K Queue (cont.)
L
Lq
le
W
Wq
r
= SKn=0 n Pn
 SKn=s+1 (n - s) Pn
= SKn=0 (K - n) l Pn
= L / le
 Lq / le
 (L - Lq) / s
= le / sm
Queueing Theory
72
M/M/s/K/K Example
There are two workers that are responsible for 10
milling machines. The machines run on the
average of 20 minutes, then require an average 5minute service period both times exponentially
distributed. Therefore, l = 1/20 and m = 1/5.
Determine the various measures of performance
for this system.
Queueing Theory
73
M/M/s/K/K Example (cont.)
All of the performance measures depend on P0
1
 10  5 
10!
 5  
P0       
 
n2 
 n0  n  20  n2 (10  n)!2!2  20  
= 0.065
Using P0 we can obtain the other Pn, from which we
can compute the average number of machines
waiting for service
Lq  S10n=2+1 (n - 2) Pn
= 1.46 (machines)
2 1
n
10
Queueing Theory
n
74
M/M/s/K/K Example (cont.)
The effective arrival rate
le = SKn=0 (K - n) l Pn
= S10n=0 (10 - n) (1/20) Pn
= 0.342 (machines/minute)
and the average waiting time in the queue
Wq  Lq / le  27 (minutes)
Similarly, we can compute the expected number of
machines being serviced or waiting to be served
L = SKn=0 n Pn = S10n=0 n Pn = 3.17 (machines)
Queueing Theory
75
M/M/s/K/K Example (cont.)
The average number of machines being serviced is
given by
L - Lq = 3.17 - 1.46 = 1.71 (machines)
since the machines must be running, waiting to be
served, or in service, the average number of
running machines is given by
K - L = 10 - 3.17 = 6.83 (machines)
A frequently asked question is: What will happen if
the number of servers is increased or decreased?
Queueing Theory
76
M/M/s/K/K Example (cont.)
If the number of workers in this example increases to
three(s=3), then the time-average number of
running machines increases to
K - L = 7.74 (machines)
an increase of 0.91 machine, on the average.
Conversely, what happens if the number of servers
decreases to one? Then the time-average number
of running machines decreases to
K - L = 3.98 (machines)
Queueing Theory
77
M/M/s/K/K Example (cont.)
The decrease from two to one server has resulted in a
drop of nearly three machines running, on the
average.
This example illustrates several general relationships
that have been found to hold for almost all queues.
If the number of servers is decreased, delays,
server utilization, and the probability of an arrival
having to wait to begin service all increase.
Queueing Theory
78