Page 398 - A First Course In Stochastic Models

MULTI-SERVER QUEUES WITH POISSON INPUT 393

the state probabilities p j the recursion scheme
i−1

min(i, c)µp i = p k λ β s , i = 1, 2, . . . , (9.6.32)
k=0 s≥i−k

where µ = 1/E(S). Starting with p := 1, we successively compute p , p , . . .
1
2
0
and next obtain the desired p i by normalization. The normalization can be based
on Little’s relation
c−1 c−1

jp j + c(1 − p j ) = cρ (9.6.33)
j=0 j=0
stating that the average number of busy servers equals cρ. The computational effort
of the recursion scheme can be reduced by using the asymptotic expansion

p j ∼ στ −j as j → ∞, (9.6.34)
where τ is the unique solution of the equation

λτ[1 − β(τ)] = cµ(1 − τ) (9.6.35)

on the interval (1, R) and the constant σ is given by
c−1
i
(τ − 1) (c − i)p i τ /c
i=0
σ = . (9.6.36)
1 − λτ β (τ)/(cµ)
2 ′
∞ j
β
Here β(z) = j=1 j z and R is the convergence radius of the power series β(z).
To establish the asymptotic expansion, it is assumed that R > 1. In other words,
the batch-size distribution is not heavy-tailed. The derivation of the asymptotic
∞ j

expansion (9.6.34) is routine. Define the generating function P (z) = p j z ,
j=0
|z| ≤ 1. It is a matter of simple algebra to derive from (9.6.32) that
c−1
i
(1/c) (c − i)p i z
i=0
P (z) = .
1 − λz{1 − β(z)}/{cµ(1 − z)}
Next, by applying TheoremC.1 in Appendix C, we obtain (9.6.34).
From the generating function we also derive after considerable algebra that the
long-run average queue size is given by

c−1 2
1 ρ E(X ) ρ
L q = j(c − j)p j + − 1 + − cρ,
c(1 − ρ) 2(1 − ρ) E(X) 1 − ρ
j=1
where the random variable X denotes the batch size.