Journal of Applied Mathematics and Stochastic Analysis
Volume 11 (1998), Issue 3, Pages 355-368
doi:10.1155/S104895339800029X
Some reflections on the Renewal-theory paradox in queueing theory
1Florida Atlantic University, Department of Computer Science and Engineering, Boca Raton 33431-0991, FL, USA
2The University of Texas at Dallas, School of Management, P.O. Box 830688, Richardson 75083-0688, TX, USA
3The University of Tennessee, Management Science Program, College of Business Admin, Knoxville 37996-0562, TN, USA
Received 1 October 1997; Revised 1 January 1998
Copyright © 1998 Robert B. Cooper et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
The classical renewal-theory (waiting time, or inspection) paradox states
that the length of the renewal interval that covers a randomly-selected
time epoch tends to be longer than an ordinary renewal interval. This
paradox manifests itself in numerous interesting ways in queueing theory,
a prime example being the celebrated Pollaczek-Khintchine formula for the
mean waiting time in the M/G/1 queue. In this expository paper, we give
intuitive arguments that “explain” why the renewal-theory paradox is ubiquitous in queueing theory, and why it sometimes produces anomalous results. In particular, we use these intuitive arguments to explain decomposition in vacation models, and to derive formulas that describe some recently-discovered counterintuitive results for polling models, such as the reduction of waiting times as a consequence of forcing the server to set up
even when no work is waiting.