Page 371 - A First Course In Stochastic Models

366 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

X
one batch. For this particular M /G/1 queue the waiting-time probabilities W q (x)
can be computed by a modification of the algorithm given in Example 5.5.1.

Approximations for the waiting-time probabilities
Suppose that Assumption 9.3.1 is satisfied and let b(t) denote the density of the
service-time distribution function B(t). Then the following asymptotic expansion
applies:
−δx
1 − W q (x) ∼ γ e as x → ∞,
where δ is the smallest positive solution to
∞ j
∞
δt δ
β j e b(t) dt = 1 +
0 λ
j=1
and the constant γ is given by
−1
 
∞ j−1
(1 − ρ)δ ∞ δt ∞ δt

γ =  1 − λ te b(t) dt jβ j e b(t) dt 
λβ 0 j=1 0
−1
∞

δt
× 1 − e b(t) dt .
0
9.4 M/G/1 QUEUES WITH BOUNDED WAITING TIMES
In Section 9.2.4 we studied the limiting distribution function V ∞ (x) of the work
in system in the M/G/1 queue. This distribution function will play a key role in
the analysis of both the finite-buffer M/G/1 queue with partial overflow and the
M/G/1 queue with impatient customers.

9.4.1 The Finite-Buffer M/G/1 Queue
Consider the M/G/1 queue with a finite buffer, i.e. the finite dam model. Instead
of a service time of a customer, we speak of the amount of work brought in by
a customer. Customers arrive according to a Poisson process with rate λ. The
amounts of work brought in by the customers are independent random variables
having a common probability distribution function B(x) with probability density
b(x). Denoting by µ the first moment of the amount of work brought in by a
customer, it is assumed that ρ = λµ is less than 1. Each customer puts their
amount of work into a buffer. The buffer has a finite capacity of K. A customer
who brings more work than can be stored in the buffer causes an overflow, where
only the excess of work is lost (partial overflow). The buffer is emptied at a unity
rate whenever there is work in the buffer. The finite-buffer M/G/1 queue has
a variety of applications such as dam and production/inventory systems with a