Page 386 - A First Course In Stochastic Models

MULTI-SERVER QUEUES WITH POISSON INPUT 381

This gives for P (z) the following explicit expression:

c(1 − ρ)(1 − z) c−1 z − z k !

P (z) = c λD(1−z) , |z| ≤ 1. (9.6.8)
1 − z e 1 − z k
k=1
This expression for P (z) allows for a direct application of the FFT method. It
is important to have an accuracy check on the calculated complex roots z k and
the subsequent calculations by the discrete FFT method. Such an accuracy check
is provided by Little’s relation (9.6.5). Another accuracy check is obtained by
calculating the average queue size L q both from formula (9.6.7) and from the
∞

direct expression L q = (j − c)p j .
j=c
Waiting-time probabilities
In the paper of Crommelin (1932) an explicit expression has been derived for W q (x)
in terms of an infinite alternating series. However, this explicit expression turns out
to be of little computational use and is therefore not further discussed. It is possible
to deduce a recursion scheme for W q (x) from Crommelin’s original derivation, but
this recursion scheme is also hampered by numerical difficulties. It took more than
sixty years before a satisfying solution was found for the computation of W q (x).
An elegant and numerically stable algorithm was found by Franx (2001) using an
ingenious argument. The following expression holds for W q (x):

kc−1 j
−λ(kD−x) [λ(kD − x)]
W q (x) = Q kc−1−j e , (k − 1)D ≤ x < kD (9.6.9)
j!
j=0
for k = 1, 2, . . . , where

c+j

Q j = p i , j = 0, 1, . . . .
i=0
The first step in the proof is to assume that the arriving customers are assigned
in cyclic order to the servers: the customers with labels i, i + c, i + 2c, . . . are
assigned to server i for i = 1, . . . , c (the nth arriving customer gets label n). This
service discipline is not violating the assumption of service in order of arrival since
the service times are deterministic. Denote by W j the waiting time in queue of the
customer with label j. It is assumed that there is a single queue in front of all c
servers. Fix now x > 0. Also fix the positive integer k by (k − 1)D ≤ x < kD.
Next choose any integer n such that n > kc. Consider now the customers with the
labels n − kc and n. Both customers are served by the same server. This server is
called the marked server. To derive P (W n ≤ x), we condition upon the number
of waiting customers in the queue just after the epoch at which the customer with
label n − kc enters service with the marked server. Distinguish between two cases: