Page 379 - A First Course In Stochastic Models

374 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

and
m
b (0) 1
′
2
W q = − + , (9.5.11)
b 2 (0) η i
i=1
where b (0) is the derivative of b 2 (s) at s = 0. Once the roots η 1 , . . . , η m have
′
2
been computed, the waiting-time probabilities can be obtained by numerical Laplace
inversion of (9.5.8). A few words are in order on the computation of the (com-
plex) roots η 1 , . . . , η m . If the interarrival-time density is a phase-type density as
well, then equation (9.5.9) reduces to a polynomial equation. Standard methods are
available to compute the roots of a polynomial equation; see Appendix G. Another
important case is the case of constant interarrival times. For the D/P h/1 queue,
equation (9.5.9) becomes

b 2 (−s) − e −sD b 1 (−s) = 0. (9.5.12)

For Coxian-2 services this equation is a special case of (9.5.6) and has two real
roots that are easily found by bisection. In general the equation (9.5.12) can be
numerically solved by tools discussed in Appendix G. In Appendix G we give
special attention to the numerical solution of (9.5.12) when the service-time dis-
tribution is a mixture of an Erlang (m − 1, µ) distribution and an Erlang (m, µ)
distribution.

9.5.4 The P h/G/1 Queue

∞ −st
∗
For phase-type arrivals the Laplace transform a (s) = e a(t) dt of the prob-
0
ability density a(t) of the interarrival time can be written as
a 1 (s)
∗
a (s) = ,
a 2 (s)
for polynomials a 1 (s) and a 2 (s), where the degree of a 1 (s) is lower than the degree
of a 2 (s). Let m be the degree of a 2 (s). It is no restriction to assume that a 1 (s) and
a 2 (s) have no common zeros and that the coefficient of s m in a 2 (s) is equal to 1.

∗ ∞ −st
Also, let b (s) = e b(t) dt denote the Laplace transform of the service-time
0
density b(t). It is assumed that b (s) and a 2 (s) have no common zero. For the case
∗
of m ≥ 2, it follows from results in Cohen (1982) that

∞ 1 −αa 2 (0)s(1 − ρ) δ i − s
m−1
−sx
e 1 − W q (x) dx = 1 − ,
∗
0 s a 2 (−s) − b (s)a 1 (−s) δ i
i=1
(9.5.13)
where δ 1 , . . . , δ m−1 are the roots of
a 2 (−s) − b (s)a 1 (−s) = 0 (9.5.14)
∗