Page 383 - A First Course In Stochastic Models

378 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

the M/D/c queue will be given in Section 9.6.1. In Section 9.6.2 we consider the
M/G/c queue with general service times and give several approximations including
two-moment approximations based on exact results for the M/M/c queue and the
X
M/D/c queue. In Section 9.6.3 we consider the M /G/c queue with batch arrivals
X
X
and general service times. In particular, the M /M/c queue and the M /D/c
queue are dealt with.
9.6.1 The M/D/c Queue
In this model the arrival process of customers is a Poisson process with rate λ, the
service time of a customer is a constant D, and c identical servers are available. It
is assumed that the server utilization ρ = λD/c is smaller than 1.
An exact algorithm analysis of the M/D/c queue goes back to Crommelin (1932)
and is based on the following observation. Since the service times are equal to the
constant D, any customer in service at time t will have left the system at time
t + D, while the customers present at time t + D are exactly those customers
either waiting in queue at time t or having arrived in (t, t + D). Let p j (s) be the
probability of having j customers in the system at time s. Then, by conditioning
on the number of customers present at time t,
c j c+j j−k+c
−λD (λD) −λD (λD)
p j (t + D) = p k (t)e + p k (t)e
j! (j − k + c)!
k=0 k=c+1
for j = 0, 1, . . . , since the number of arrivals in a time D is Poisson distributed
with mean λD. Next, by letting t → ∞ in these equations, we find that the
time-average probabilities p j satisfy the linear equations

c c+j j−k+c
(λD) j −λD (λD)
−λD
p j = e p k + p k e , j ≥ 0. (9.6.1)
j! (j − k + c)!
k=0 k=c+1
∞
Also, we have the normalizing equation j=0 p j = 1. This infinite system of
linear equations can be reduced to a finite system of linear equations by using the
geometric tail approach discussed in Section 3.4.2. It will be shown below that the
state probabilities p j exhibit the geometric tail behaviour
p j ∼ στ −j as j → ∞, (9.6.2)
where τ is the unique solution of the equation

e λD(1−τ) c (9.6.3)
τ = 1
on the interval (1, ∞) and the constant σ is given by

c−1
k
c
σ = (c − λDτ) −1 p k (τ − τ ). (9.6.4)
k=0