
25-18 Handbook of Dynamic System Modeling
Neuts (1981), Walrand (1988). We limit ourselves to one well-known and very useful analytical result that
applies to the M/G/1 queueing system. In particular, it is possible to derive a simple expression for the
average queue length E[X] of such a system. This is known as the Pollaczek–Khinchin formula (or PK
formula):
E[X] =
ρ
1 −ρ
−
ρ
2
2(1 −ρ)
(1 −µ
2
σ
2
) (25.57)
where 1/µ and σ
2
are the mean and variance, respectively, of the service time distribution and ρ =λ/µ
is the traffic intensity as defined in Eq. (25.9), λ being the Poisson arrival rate. We can immediately see
that for exponentially distributed service times, where σ
2
=1/µ
2
, (Eq. 25.57) reduces to the average queue
length of the M/M/1system,E[X] =ρ/(1 −ρ), as in Eq. (25.33).
Finally, it is worth mentioning that many software tools have been developed over the years to facilitate
the process of modeling queueing systems and of estimating performance measures such as throughput,
mean queue lengths, and mean delays. Some are based on discrete event simulation (Extend and SimEvents
are two of the most recent commercial products of this type), while others are based on approximation
methods (RESQ and QNA are such examples). More specialized tools have also been developed for
particular application areas such as communication networks (e.g., Opnet) and manufacturing systems
(e.g., MPX).
References
Asmussen, S., Applied Probability and Queues, 2nd ed., Wiley, New York, 2003.
Baskett, F., Chandy, K. M., Muntz, R. R., and Palacios, R. R., Open, closed, and mixed networks of queues
with different classes of customers, J. ACM, 22(2), 248–260, 1975.
Bremaud, P., Point Processes and Queues, Springer, New York, 1981.
Burke, P. J., The output of a queueing system, Oper. Res., 4, 699–704, 1956.
Buzen, J. P., Computational algorithms for closed queueing networks with exponential servers, Commun.
of ACM, 16(9), 527–531, 1973.
Cassandras, C.G., and Lafortune, S., Introduction to Discrete Event Systems, Kluwer, Norwell, MA, 1999.
Chen, H., and Yao, D.D., Fundamentals of Queueing Networks, Springer, New York, 2000.
Gordon, W. J., and G. F. Newell, Closed queueing systems with exponential servers, Oper. Res., 15(2),
254–265, 1967.
Jackson, J. R., Jobshop-like queueing systems, Manage. Sci., 10(1), 131–142, 1963.
Kelly, F. P., Reversibility and Stochastic Networks, Wiley, New York, 1979.
Kleinrock, L., Queueing Systems, Volume I: Theory, Wiley, New York, 1975.
Lindley, D. V., The theory of queues with a single server, Proc. Cambridge Philos. Soc., 48, 277–289, 1952.
Little, J. D. C., A proof of L =λW, Oper. Res., 9(3), 383–387, 1961.
Neuts, M. F., Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach,Dover,NewYork,
1981.
Reiser, M. and Lavenberg, S. S., Mean-value analysis of closed multichain queueing networks, J. of ACM,
27(2), 313–322, 1980.
Stidham, S., Jr., A last word on L =λW, Oper. Res., 22, 417–421, 1974.
Trivedi, K. S., Probability and Statistics with Reliability, Queuing and Computer Science Applications,
Prentice-Hall, Englewood Cliffs, NJ, 1982.
Walrand, J., An Introduction to Queueing Networks, Prentice-Hall, Englewood Cliffs, NJ, 1988.