Page 392 - A First Course In Stochastic Models

MULTI-SERVER QUEUES WITH POISSON INPUT 387

Hence, for any 1 ≤ k ≤ c − 1 and j > k,
′
M (t) = −λM kj (t) + λ{1 − B(t)}M k+1,j (t), t > 0.
kj
k
Multiplying both sides of this differential equation by {1−B e (t)} , integrating over
t and using (9.6.16), we find after partial integration that
k
A kj = B k+1,j − B kj , 1 ≤ k ≤ c − 1, j > k, (9.6.17)
λE(S)
where B kj is a shorthand notation for
∞

k−1
B kj = {1 − B e (t)} {1 − B(t)}M kj (t) dt.
0
app
Next it is easy to establish the recursion scheme for p . To verify (9.6.12), we
j
use induction. Obviously, (9.6.12) holds for j = 0. Suppose now that (9.6.12)
holds for j = 0, . . . , n−1 for some 1 ≤ n ≤ c −1. Then, by (9.6.14) and (9.6.17)
n−1
app app app k
p n (1 − λA nn ) = λp 0 A 0n + λp k B k+1,n − B kn
k=1 λE(S)
n−1 n−1
app app app

B
B
= λp B k+1,n − λp k−1 kn = λp n−1 nn , (9.6.18)
k
k=0 k=1
where the second equality uses A 0n = B 1n and uses the induction assumption
app app
that p = cρp /k for 1 ≤ k ≤ n − 1. Using partial integration it is readily
k k−1
app
verified that B nn = (1−λA nn )E(S)/n. Hence we obtain from (9.6.18) that p n =
app
cρp /n, which completes the induction step. To verify (9.6.13) we first note that
n−1
c−1
app app app
B
λp 0 A 0j + λp k A kj = λp c−1 cj , j ≥ c. (9.6.19)
k=1
The derivation of this relation is similar to that of (9.6.18). Inserting (9.6.19) into
(9.6.14) and using (9.6.15), the desired result (9.6.17) follows.
Computational aspects
app
The recursion scheme for p is easy to apply in practice. In general the constants
j
a n and b n have to be evaluated by numerical integration. An explicit expression
for b n can be given for deterministic and phase-type services. To compute the a n ,
it is recommended to use Gauss–Legendre integration for deterministic services.
To do so for phase-type services, the infinite integral for a n must be first reduced
to an integral over (0, 1) by using that E[g(X)] = E[g(F −1 (U))] when F(x) =
P {X ≤ x} and U is uniformly distributed on (0, 1) (take F(x) = B e (x)). The
computational effort of the approximation algorithm depends only to a slight degree