Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-26T15:39:29.913Z Has data issue: false hasContentIssue false
  • English
  • Français

Stochastic bounds for the queue GI/G/1 in heavy traffic

Published online by Cambridge University Press:  24 October 2008

Julian Köllerström
Julian Köllerström
Affiliation:
University of Kent at Canterbury, Kent, CT2 7NF
Get access Rights & Permissions [Opens in a new window]

Extract

It is often of greater practical value to have results about queueing theory which involve probabilities rather than characteristic functions. To quote Kendall (4), section 5, ‘These results of Prabhu, further exploited by himself and Takács, are rapidly raising the Laplacian curtain which has hitherto obscured much of the details of the queue-theoretic scene’. In this paper we derive the exponential limit formula for the equilibrium waiting time distribution function G, for the queue GI/G/1 in heavy traffic, using stochastic bounds which are asymptotically sharp as the traffic intensity (defined below) increases to unity (which has not been done before to the author's knowledge). This formula was derived by Kingman (5), (6) and (9), using characteristic functions, who, in section 9 of the latter paper, stressed the need for improving the precision of the approximation ‘by giving inequalities, bounds for errors, and generally by setting the theory on a more elegant and rigorous basis’. Kingman (6) and (9) also sketched a proof of the same result using a Brownian approximation, which was done in detail by Viskov (18); but here again the same difficulties are present in practical interpretation, error bounds etc.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 84 , Issue 2 , September 1978 , pp. 361 - 375
Copyright
Copyright © Cambridge Philosophical Society 1978

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

(1)Blomqvist, N.A simple derivation of the GI/G/1 waiting time distribution in heavy traffic. Scand. J. Statist. 1 (1974), 39–40.Google Scholar
(2)Delbrouck, L. E. N.Convexity properties, moment inequalities and asymptotic exponential approximations for delay distributions in GI/G/1 systems. Stochastic Processes Appl. 3 (1975), 193–207.CrossRefGoogle Scholar
(3)Feller, W.An introduction to probability theory and its applications, vol. II, 1st ed. (New York: Wiley, 1966).Google Scholar
(4)Kendall, D. G.Some recent work and further problems in the theory of queues. Theor. Probability Appl. 9 (1964), 1–13.CrossRefGoogle Scholar
(5)Kingman, J. F. C.The single server quene in heavy traffic. Proc. Cambridge Philos. Soc. 57 (1961), 902–904.CrossRefGoogle Scholar
(6)Kingman, J. F. C.On queues in heavy traffic. J. Roy. Statist. Soc. B 24 (1962), 383–392.Google Scholar
(7)Kingman, J. F. C.Some inequalities for the queue GI/G/1. Biometrika 49 (1962), 315–324.CrossRefGoogle Scholar
(8)Kingman, J. F. C.A martingale inequality in the theory of queues. Proc. Cambridge Philos. Soc. 59 (1964), 359–361.CrossRefGoogle Scholar
(9)Kingman, J. F. C. The heavy traffic approximation in the theory of queues. Ed. Smith, W. L. and Wilkinson, W. E., Proceedings of the Symposium on Congestion Theory, pp. 137–169 (University of North Carolina at Chapel Hill Press, 1965).Google Scholar
(10)Kingman, J. F. C.On the algebra of queues. J. Appl. Probability 3 (1966), 285–326.CrossRefGoogle Scholar
(11)Kingman, J. F. C.Inequalities in the theory of queues. J. Roy. Statist. Soc. B 32 (1970), 102–110.Google Scholar
(12)Köllerström, J.Heavy traffic theory for queues with several servers. I. J. Appl. Probability 11 (1974), 544–552.CrossRefGoogle Scholar
(13)Köllerström, J.Stochastic bounds for the single-server queue. Math. Proc. Cambridge Philos. Soc. 80 (1976), 521–525.CrossRefGoogle Scholar
(14)Köllerström, J. Some analysis in the theory of queues with several servers. D.Phil. Thesis (1976), University of Oxford.Google Scholar
(15)Lindley, D. V.Theory of queues with a single server. Proc. Cambridge Philos. Soc. 48 (1952), 277–289.CrossRefGoogle Scholar
(16)Marshall, K. T. Some inequalities for single server queues. Ph.D. Thesis (1966), Department of Industrial Engineering, University of California, Berkeley.Google Scholar
(17)Ross, S. M.Bounds on the delay distribution in GI/G/1 queues. J. Appl. Probability 11 (1974), 417–421.CrossRefGoogle Scholar
(18)Viskov, O. V.Two asymptotic formulae of the theory of mass service. Teor. Verojatnost. i Priminen 9 (1964), 177–178.Google Scholar
(19)Kiefer, J. and Wolfowitz, J.On the characteristics of the general queueing process with applications to random walk. Ann. Math. Statist. 27 (1956), 147–161.CrossRefGoogle Scholar
(20)Lemoine, A. J.On random walks and stable GI/G/1 queues. Maths. Operat. Res. 1 (1976), 159–164.CrossRefGoogle Scholar
(21)Loève, M.Probability theory (Princeton, N.J.: Van Nostrand, 1963).Google Scholar
(22)Zygmund, A.A remark on characteristic functions. Ann. Math. Statist. 18 (1947), 272–276.CrossRefGoogle Scholar