Page 370 - A First Course In Stochastic Models

X
THE M /G/1 QUEUE 365
To prove this result, fix k and imagine that a reward of 1 is earned for each customer
taking the kth position in its batch. Then the long-run average reward per customer
is η k by definition. By the renewal-reward theorem, the long-run average reward per
∞
customer equals the expected reward j=k j earned for a single batch divided
β
by the expected batch size β. This gives (9.3.8). Consider now a test customer
belonging to a batch that arrives when the system has reached steady state. Denote
by D (∞) the delay in queue of this test customer. The delay D (∞) can be written
as D (∞) = X 0 + X 1 , where X 0 is the delay caused by the customers present
just before the batch of the test customer arrives and X 1 is the delay caused by
customers belonging to the batch of the test customer. The random variables X 0
and X 1 are independent of each other and so E(e −sD (∞) ) = E(e −sX 0 )E(e −sX 1 ).
Assuming that the position of the test customer in the batch is distributed according
to {η k }, we have by (9.3.8) that
∞ ∞ ∞
k−1 1 k−1
∗
∗
E(e −sX 1 ) = η k [b (s)] = [b (s)] β j
β
k=1 k=1 j=k
∞ j
1 k−1 1 − G(b (s))
∗
∗
= β j [b (s)] = .
β β[1 − b (s)]
∗
j=1 k=1
To find E(e −sX 0 ), note that an arriving group of customers can be considered as
a singly arriving supercustomer. The probability density of the total time to serve
a supercustomer has the Laplace transform β ∗ (s). In other words, the delay in
SC
queue of the first customer of each batch can be described by a standard M/G/1
queue for which the service-time density has the Laplace transform β ∗ (s). Thus,
SC
using the result (2.5.12) for the M/G/1 queue,
(1 − ρ)s
E(e −sX 0 ) = .
s − λ + λβ ∗ (s)
SC

∞ −sx −1 −sD (∞)
Since e {1 − W q (x)} dx = s [1 − E(e )] by relation (E.8) in
0
Appendix E, we have now derived (9.3.7) heuristically.
Alternative algorithm
A simpler algorithm than numerical Laplace inversion can be given for the
X
M /D/1 queue with deterministic services. This alternative algorithm is discussed
X
in Section 9.5.3 in the more general context of the M /D/c queue. A simple algo-
rithm is also possible when the service time of a customer is a mixture of Erlangian
distributions with the same scale parameters. In this case the service time of a cus-
tomer can be interpreted as a random sum of independent phases each having
X
an exponentially distributed length with the same mean. The M /G/1 queue with
Y
generalized Erlangian services is in fact an M /M/1 queue in which the batch size
Y is distributed as the total number of service phases generated by all customers in