Numerical approximations for the steady‐state waiting times in a GI/G/1 queue
Tóm tắt
This paper focuses on easily computable numerical approximations for the distribution and moments of the steady‐state waiting times in a stable GI/G/1 queue. The approximation methodology is based on the theory of Fredholm integral equations and involves solving a linear system of equations. Numerical experimentation for various M/G/1 and GI/M/1 queues reveals that the methodology results in estimates for the mean and variance of waiting times within ±1% of the corresponding exact values. Comparisons with competing approaches establish that our methodology is not only more accurate, but also more amenable to obtaining waiting time approximations from the operational data. Approximations are also obtained for the distributions of steady‐state idle times and interdeparture times. The approximations presented in this paper are intended to be useful in rough‐cut analysis and design of manufacturing, telecommunications, and computer systems as well as in the verification of the accuracies of inequalities, bounds, and approximations.
Tài liệu tham khảo
M.H. Ackroyd, Computing the waiting time distribution for the G/G/1 queue by signal processing methods, IEEE Trans. Commun. 28 (1980) 52–58.
A.O. Allen, Probability, Statistics, and Queueing Theory with Computer Science Applications (Academic Press, Boston, 1990).
T.M. Apostle, Mathematical Analysis (Addison-Wesley, Reading, MA, 1974).
J.A. Buzacott and J.G. Shantikumar, Stochastic Models of Manufacturing Systems (Prentice-Hall, Englewood Cliffs, NJ, 1993).
M.L Chaudhry, M. Agarwal and J.G.C. Templeton, Exact and approximate numerical solutions of steady-state distributions arising in the queue GI/G/1, Queueing Systems 10 (1992) 105–152.
D.J. Daley, A.Y. Kreinin and C.D. Trengove, Inequalities concerning the waiting time in single server queues: A survey, in: Queueing and Related Models, eds. U.N. Bhatt and I.V. Basawa (Clarendon Press, Oxford, 1992) pp. 177–223.
M.J. Fryer and C.B. Winsten, An algorithm to compute the equilibrium distribution of a onedimensional bounded random walk, Oper. Res. 34 (1986) 449–454.
W.K. Grassmann and J.L. Jain, Numerical solutions of the waiting time distribution and idle time distribution of the arithmetic GI/G/1 queue, Oper. Res. 37 (1989) 141–150.
D. Gross and C.M. Harris, Fundamentals of Queueing Theory (Wiley, New York, 1985).
C.M. Harris, A note on mixed exponential approximation for GI/G/1 waiting times, Comput. Oper. Res. 36 (1985) 285–289.
W.J. Hopp and M.L. Spearman, Factory Physics: Foundations of Manufacturing Management (IRWIN, Chicago, 1996).
L. Kleinrock, Queueing Systems: Computer Applications, Vol. 2 (Wiley, New York, 1976).
A.G. Konheim, An elementary solution of the queueing system GI/G/1, SIAM J. Comput. 4 (1975) 540–545.
D.V. Lindley, The theory of queues with a single server, Proc. Camb. Phil. Soc. 48 (1952) 277–289.
M.J. Maron and R.J. Lopez, Numerical Analysis: A Practical Approach (Wadsworth, Belmont, CA, 1991).
M.F. Neuts, Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach (Johns Hopkins Univ. Press, Baltimore, MD, 1981).
J. Ponstein, Theory and solution of a discrete queueing problem, Statist. Neerlandica 20 (1974) 139–152.
N.U. Prabhu, Stochastic Storage Processes: Queues, Insurance Risk, and Dams (Springer, New York, 1980).
W.H. Press, B.P. Flannery, S.A. Teukolsky and W.T. Vetterling, Numerical Recipes: The Art of Scientific Computing (Cambridge Univ. Press, Cambridge, 1988).
V. Ramaswami and G. Latouche, An experimental evaluation of the matrix-geometric method for the GI/PH/1 queue, Comm. Statist. Stochastic Models 5 (1989) 629–667.
B.V. Rao, Approximations for waiting times in queueing systems, Ph.D. dissertation, Industrial Engineering Department, Texas A & M University, College Station, TX (1996).
B.V. Rao, R.L. Disney and J.J. Pignatiello Jr., Stochastic modeling and performance evaluation of CUSUM and related quality control schemes, Working Paper INEN/OR/WP/21/12–94, Industrial Engineering Department, Texas A & M University, College Station, TX (1994).
M. Schwartz, Telecommunication Networks: Protocols, Modeling and Analysis (Addison-Wesley, Reading, MA, 1987).
I.H. Sloan, A review of numerical methods for Fredholm equations of the second kind, in: The Application and Numerical Solution of Integral Equations, eds. R.S. Anderssen, F.R. de Hogg and M.A. Lukas (Sijthoff & Noordhoff, Alphen aan den Rija, 1980) pp. 51–74.
A.H. Stroud, Gaussian Quadrature Formulas (Prentice-Hall, Englewood Cliffs, NJ, 1966).
M.H. van Hoorn, Numerical analysis of multi-server queues with deterministic service and phasetype arrivals, Z. Oper. Res. 30A (1986) 15–28.
R.W. Wolff, Stochastic Modeling and the Theory of Queues (Prentice-Hall, Englewood Cliffs, NJ, 1989).