Page 389 - A First Course In Stochastic Models

384 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

where the latter equality uses (9.6.6). This leads to

c−1

k c
c λD(1−z)
λu(1−z)
1 − z e − e p k (z − z ) /(1 − z)
k=0
B u (z) = .
c λD(1−z)
1 − z e
c λD(1−τ)
Next, by Theorem C.1 in Appendix C and τ e = 1, we find
σe −λ(τ−1)u −j
1 − b j (u) ∼ τ as j → ∞.
τ − 1
Take now j = kc − 1 and x = (k − 1)D + u. Then 1 − b j (u) = 1 − W q (x). Since
c λD(1−τ)
the equation τ e = 1 implies τ −(k−1)c = e −λ(τ−1)(k−1)D , we obtain
σe −λ(τ−1)x
1 − b kc−1 ∼ c−1 as k → ∞,
(τ − 1)τ
which proves the desired result (9.6.11).

9.6.2 The M/G/c Queue
In this multi-server model with c servers the arrival process of customers is a
Poisson process with rate λ and the service time S of a customer has a general
probability distribution function B(t). It is assumed that the server utilization ρ =
λE(S)/c is smaller than 1.
The M/G/c queue with general service times permits no simple analytical solu-
tion, not even for the average waiting time. Useful approximations can be obtained
by the regenerative approach discussed in Section 9.2.1. In applying this approach
to the multi-server queue, we encounter the difficulty that the number of customers
left behind at a service completion epoch does not provide sufficient information
to describe the future behaviour of the system. In fact we need the additional infor-
mation of the elapsed service times of the other services (if any) still in progress. A
full inclusion of this information in the state description would lead to an intractable
analysis. However, as an approximation, we will aggregate the information of the
elapsed service times in such a way that the resulting approximate model enables
us to carry through the regenerative analysis. A closer look at the regenerative
approach reveals that we need only a suitable approximation to the probability
distribution of the time elapsed between service completions. We now make the
following approximation assumption with regard to the behaviour of the process at
the service completion epochs.

Assumption 9.6.1 (approximation assumption) (a) If at a service completion
epoch, k customers are left behind in the system with 1 ≤ k < c, then the time
e
e
until the next service completion epoch is distributed as min(S , . . . , S ), where
1 k