Page 347 - A First Course In Stochastic Models

342 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

Phase-type distributions
In queueing applications it is often convenient to approximate the interarrival time
and/or the service time by distributions that are built out of a finite sum or a
finite mixture of exponentially distributed components, or a combination of both.
These distributions are called phase-type distributions. For practical purposes it
usually suffices to use finite mixtures of Erlangian distributions with the same scale
parameters or Coxian-2 distributions. These distributions are discussed in detail
in Appendix B. The class of Coxian-2 distributions contains the hyperexponential
distribution of order 2 as special case. The hyperexponential distribution always has
a coefficient of variation greater than or equal to 1. This distribution is particulary
suited to model irregular interarrival (or service) times which have the feature that
most outcomes tend to be small and large outcomes occur only occasionally. The
class of mixtures of Erlangian distributions with the same scale parameters is much
more versatile than the class of Coxian-2 distributions and allows us to cover any
positive value of the coefficient of variation. In particular, a mixture of E k−1 and
E k distributions with the same scale parameters is convenient to represent regular
interarrival (or service) times which have a coefficient of variation smaller than or
equal to 1. The theoretical basis for the use of mixtures of Erlangian distributions
with the same scale parameters is provided by Theorem 5.5.1. This theorem states
that each non-negative random variable can be approximated arbitrarily closely by a
random sum of exponentially distributed phases with the same means. This explains
why finite mixtures of Erlangian distributions with the same scale parameters are
widely used for queueing calculations.

Performance measures

It is convenient to use the GI/G/c/c + N queue as a vehicle to introduce some
basic notation. Thus, we assume a multi-server queue with c identical servers and
a waiting room of capacity N (≤ ∞) for customers awaiting to be served. A
customer who finds c + N other customers present upon arrival is rejected and has
no further influence on the system. Otherwise, the arriving customer is admitted
to the system and waits in queue until a server becomes available. The customers
arrive according to a renewal process. In other words, the interarrival times are
positive, independent random variables having a common probability distribution
function A(t). The service times of the customers are independent random variables
with a common probability distribution function B(x) and are also independent of
the arrival process. The queue discipline specifying which customer is to be served
next is first-come first-served (FCFS) unless stated otherwise. A server cannot be
idle when customers are waiting in queue and a busy server works at unity rate. A
customer leaves the system upon service completion. Let

λ = the long-run average arrival rate of customers,

E(S) = the mean service time of a customer.