Simulating Stable Stochastic Systems, I: General Multiserver Queues

ABSTRACT

A technique is introduced for analyzing simulations of stochastic systems in the steady state. From the viewpoint of classical statistics, questions of simulation run duration and of starting and stopping simulations are addressed. This is possible because of the existence of a random grouping of observations which produces independent identically distributed blocks from the start of the simulation. The analysis is presented in the context of the general multiserver queue, with arbitrarily distributed interarrival and service times. In this case, it is the busy period structure of the system which produces the grouping mentioned above. Numerical illustrations are given for the M/M/1 queue. Statistical methods are employed so as to obtain confidence intervals for a variety of parameters of interest, such as the expected value of the stationary customer waiting time, the expected value of a function of the stationary waiting time, the expected number of customers served and length of a busy cycle, the tail of the stationary waiting time distribution, and the standard deviation of the stationary waiting time. Consideration is also given to determining system sensitivity to errors and uncertainty in the input parameters.

REFERENCES

• 1: ANDERSON, T. W. A~t It, troduction to Multivariate Statistical Analysis. Wiley, New York, 1958.
• 2: ANSCOMJ3~:, F.J. Sequential estimation. J. R. Statist. Soc. B. 15, (1953), 1-21.
• 3: BLOMQVIST, N. On the transient behavior of the GI/G/1 waiting times. Skand. Aktuarietidskr. (1970), 118-129.
• 4: CHUNG, K.L. A Course itt Probability Theory. Harcourt, Brace and World, New York, 1968.
• 5: COX, D. 1)~., AND SMITH, W.L. Queues. Methuen & Co., London, 1961.
• 6: F~:Lh,.:I~, E.C. The biological standardization of insulin. J. R. Statist. Soc. Suppl. 7 (1940), 1-64.
• 7: GLEHART, D.L. Functional limit theorems for the queue GI/G/1 in light traffic. Adv. Appl. Prob. $ (1971), 269-281.
• 8: KENNEDY, D. P. A note on the number of busy servers in a GI/G/s queue in light traffic. J. A ppl. Probability 9 (1972), 868-869.
• 9: KIEFER, Z., AND WOLFOWITZ, J. Oil the theory of queues with many servers. Trans. Amer, Math. Soc. 78 (1955), 1-18.
• 10: K~Em:a, J., ,~ND WOLFOWITZ, J. On the characteristics of the general queueing process with applications to random walk. A~n. Math. Statist. 27 (1956), 147-161.
• 11: LOYNES, R.M. The stability of a queue with nonindependent interarrival and service times. Proc. Camb. Phil. Soc. 58 (1962), 497-520.
• 12: l~ov, S. N., AND POTTHOFF, }{. F. Confidence bounds on vector analogues of the "ratio of means" and the "ratio of variances" for two correlated normal variates and some associated tests. A~n. Maih. Statist. 29 (1958), 829-841.
• 13: WHITT, W. Embedded renewal processes in the GI/G/s queue. J. Appl. Prob. 9 (1972) 650-658.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Measurement, Performance, Reliability, Theory