Page 407 - A First Course In Stochastic Models

402 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

Denoting the one-step transition probabilities of this Markov chain by p ij , the π j
are the unique solution to the equations

∞

π j = π k p kj , j = 1, 2, . . .
k=j−1
∞
π
together with the normalizing equation j=0 j = 1. Substituting (9.7.9) into these
equations yields that π 0 , . . . , π c−1 are the unique solution to the finite system of
linear equations
c−2

π j = π k p kj + π c−1 p ∗ c−1, j , 1 ≤ j ≤ c − 1,
k=j−1
c−2
π c−1

π j + = 1, (9.7.13)
1 − η
j=0
where
∞
k−c+1
∗
p c−1,j = η p kj , 1 ≤ j ≤ c − 1.
k=c−1
The constant η is the unique solution to the equation η = exp [−cµD(1−η)] on the
interval (0,1). It remains to specify the p kj for 1≤ j ≤ c − 1. Since the probability
that an exponentially distributed service time is completed within a time D equals
1 − exp (−µD), we have
!
k + 1 −µDj −µD k+1−j
p kj = e (1 − e ) , 0 ≤ k ≤ c − 1 and 0 ≤ j ≤ k + 1.
j
The probabilities p kj for k > c − 1 require a little bit more explanation. We first
note that the times between service completions are independent exponentials with
common mean 1/(cµ) as long as c or more customers are present. Thus, starting
with k+1 ≥ c customers present, the time until the (k+1−c)th service completion
has an E k+1−c distribution. By conditioning on the epoch of this (k+1−c)th service
completion, we find for any k ≥ c that
c −µ(D−x)j −µ(D−x) c−j k+1−c x −cµx
D ! k−c
p kj = e {1 − e } (cµ) e dx
0 j (k − c)!
! D k−c
c −jµD (cµx) −µx −µD c−j
= e cµ (e − e ) dx, 0 ≤ j ≤ c.
j 0 (k − c)!
This expression is needed to evaluate p ∗ . We find
c−1,j
! D
c −jµD cµηx −µx −µD c−j
p ∗ = p c−1,j + cµη e e (e − e ) dx
c−1,j
j 0