Page 191 - A First Course In Stochastic Models

184 CONTINUOUS-TIME MARKOV CHAINS

(c) Use partial-fraction expansion to show that p(i, s) = γ s (z 2 ) −i for i = 1, 2, . . . and
s = 0, 1. Specify the values of γ 0 and γ 1 .
4.21 Consider a multi-server queueing system with c unreliable servers. Jobs arrive according
to a Poisson process with rate λ. The required service times of the jobs are independent
random variables having a common exponential distribution with mean 1/µ. The service of
a job may be interrupted by a server breakdown. The server operates uninterruptedly during
an exponentially distributed time with mean 1/δ. It takes an exponentially distributed time
with mean 1/β to bring a broken-down server to the operative state. Any interrupted service
is resumed at the point it was interrupted. It is assumed that an interrupted service is taken
over by the first available server.
Denote by p(i, s) the limiting probability of having i jobs present and s operative servers
for i ≥ 0 and 0 ≤ s ≤ c. Prove that the probabilities p(i, s) can be computed by using the
geometric tail approach. In particular, verify that
i
p(i, s) ∼ γ s η as i → ∞
for a constant γ s , where η is the reciprocal of the smallest root of det [M(z)] = 0 on the
interval (1, ∞). Here M(z) = (m st (z)), s, t = 0, 1, . . . , c is a tridiagonal (c + 1) × (c + 1)
matrix with m ss (z) = λz − [λ + s(µ + δ) + (c − s)β] + sµ/z, m s,s−1 (z) = (c − s + 1)β
and m s,s+1 (z) = (s + 1)δ. This problem is based on Mitrani and Avi-Itzhak (1968).
4.22 Consider the unloader problem from Example 4.1.2 again. Assume now that the unload-
ing time of a ship has an Erlang (L, µ) distribution and the repair time of the unloader has
an Erlang (R, β) distribution. Letting ρ = (λL/µ)(1 + δR/β), it is assumed that the server
utilization ρ is less than 1. Interpret the unloading time of a ship as a sequence of L inde-
pendent unloading phases each having an exponential distribution with mean 1/µ. Also,
interpret the repair time of the unloader as a sequence of R independent repair phases each
having an exponential distribution with mean 1/β. Let state (i, 0) correspond to the situ-
ation the unloader is available and i uncompleted unloading phases are present (i ≥ 0).
Let state (i, r) correspond to the situation that there are i uncompleted unloading phases
(i ≥ 1) and the unloader is in repair with r remaining repair phases (1 ≤ r ≤ R). Denote by
p(i, s) the equilibrium probability of state (i, s) and define the generating functions G s (z)
∞ ∞
i i
by G 0 (z) = p(i, 0)z and G r (z) = p(i, r)z for |z| ≤ 1.
i=0 i=1
(a) Verify that
det A s (z)
G s (z) = , s = 0, 1, . . . , R.
det A(z)
L
T
Here A(z) is the (R + 1) × (R + 1) matrix A(z) = (1 − z)M − λz(1 − z )I + zQ , where
M = diag(µ, 0, . . . , 0) and Q T is the transpose of the transition matrix Q = (q ij ) with
q 0R = −q 00 = δ, q i,i−1 = −q ii = β for 1 ≤ i ≤ R and the other q ij = 0. The matrix
A s (z) results from replacing the (s + 1)th column vector of A(z) by the vector b(z) with
T
b (z) = ((µ(1 − z) − δz)p(0, 0), 0, . . . , 0).
(b) Conclude that for any s = 0, 1, . . . , R,
p(i, s) ∼ γ s η i as i → ∞
for a constant γ s , where η is the reciprocal of the smallest root of det A(x) = 0 on the
interval (1, ∞). Note that for Erlangian service the polynomial equation
R+1 L L R
det A(z) = (−1) [{λz(1 − z ) − µ(1 − z) + δz}{λz(1 − z ) + βz}
R
− δz(βz) ] = 0
is obtained by expanding det A(z) in the cofactors of its first row.