Page 345 - A First Course In Stochastic Models

340 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

stimulated much practically oriented research on computational aspects of queueing
models. It is to these aspects that the present chapter is addressed. Here considerable
attention is paid to robustness results. While it was seen in Section 5.2 that many
loss systems (no access of arrivals finding all servers busy) are exactly or nearly
insensitive to the distributional form of the service time except for its first moment,
it will be demonstrated in this chapter that many delay systems (full access of
arrivals) and many delay-loss systems (limited access of arrivals) allow for two-
moment approximations. The approximate methods for complex queueing models
are usually based on exact results for simpler related models and on asymptotic
expansions. The usefulness of asymptotic expansions can hardly be overestimated.
Algorithmic analysis of queueing systems is more than getting numerical answers.
The essence of algorithmic probability is to find probabilistic ideas which make
the computations transparent and natural. However, once an algorithm has been
developed according to these guidelines, one should always verify that it works in
practice. The algorithms presented in this chapter have all been thoroughly tested.
The cornerstones of the algorithms are:

• the embedded Markov chain method,
• the continuous-time Markov chain approach,
• renewal-theoretic methods,
• asymptotic expansions,
• discrete FFT method and numerical Laplace inversion.

This chapter is organized as follows. Section 9.1 reviews some basic concepts
including phase-type distributions and Little’s formula. In Section 9.2 we derive
algorithms for computing the state probabilities and the waiting-time probabilities
in the single-server queue with Poisson input and general service times (M/G/1
queue). These results are extended in Section 9.3 to the single-server queue with
batch Poisson input. In Section 9.4 we consider the finite-buffer M/G/1 queue
and the M/G/1 queue with impatient customers. The solution of these queue-
ing systems can be expressed in terms of the solution for the infinite-capacity
M/G/1 queue. The single-server queue with general interarrival times and ser-
vice times is the subject of Section 9.5. Section 9.6 deals with multi-server queues
with Poisson input, including both the case of single arrivals and the case of batch
arrivals. Tractable exact results are only obtained for the special case of determin-
istic services and exponential services. For the case of general service times we
derive several approximations. These approximations include two-moment approx-
imations that are based on exact results for simpler models and use a linear inter-
polation with respect to the squared coefficient of variation of the service time. In
Section 9.7 the multi-server queue with renewal input is discussed. In particular,
attention is paid to the tractable models with exponential services and determin-
istic services. In Section 9.8 we consider finite-capacity queueing systems with