Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-14T03:22:41.978Z Has data issue: false hasContentIssue false
  • English
  • Français

The effect of variability in the GI/G/s queue

Published online by Cambridge University Press:  14 July 2016

Ward Whitt
Ward Whitt*
Affiliation:
Bell Laboratories
*
∗Postal address: Bell Laboratories, Holmdel, NJ 07733, U.S.A.
Get access Rights & Permissions [Opens in a new window]

Abstract

In 1969 H. and D. Stoyan showed that the stationary waiting-time distribution in a GI/G/1 queue increases in the ordering determined by the expected value of all non-decreasing convex functions when the interarrival-time and service-time distributions become more variable, as expressed in the ordering determined by the expected value of all convex functions. Ross (1978) and Wolff (1977) showed by counterexample that this conclusion does not extend to all GI/G/s queues. Here it is shown that this conclusion does hold for all GI/G/s queues for several other measures of congestion which coincide with the waiting time in single-server systems. One such alternate measure of congestion is the clearing time, the time required after the arrival epoch of the nth customer for the system to serve all customers in the system at that time, excluding the nth customer. The stochastic comparisons also imply an ordering for the expected waiting times in M/G/s queues.

Keywords

QUEUESMULTISERVER QUEUESSTOCHASTIC COMPARISONSINEQUALITIESBOUNDS
Type
Research Papers
Information
Journal of Applied Probability , Volume 17 , Issue 4 , December 1980 , pp. 1062 - 1071
Copyright
Copyright © Applied Probability Trust 

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

Barlow, R. E. and Proschan, F. (1975) Statistical Theory of Reliability and Life Testing. Holt, Rinehart and Winston, New York.Google Scholar
Bessler, S. A. and Veinott, A. F. Jr. (1966) Optimal policy for a dynamic multi-echelon inventory model. Naval. Res. Logist. Quart. 13, 355–389.Google Scholar
Blackwell, D. (1953) Equivalent comparisons of experiments. Ann. Math. Statist. 24, 265–272.Google Scholar
Borovkov, A. A. (1976) Stochastic Processes in Queueing Theory (English translation). Springer-Verlag, New York.Google Scholar
Brumelle, S. L. (1971) On the relation between customer and time averages in queues. J. Appl. Prob. 8, 508–520.Google Scholar
Brumelle, S. L. and Vickson, R. G. (1975) A unified approach to stochastic dominance. In Stochastic Optimization Models in Finance, ed. Ziemba, W. T. and Vickson, R. G. Academic Press, New York.Google Scholar
Chong, K. M. and Rice, N. M. (1971) Equimeasurable Rearrangements of Functions. Queen's Papers in Pure and Applied Mathematics, Number 28.Google Scholar
Cox, D. R. and Smith, W. L. (1961) Queues. Methuen, London.Google Scholar
Hardy, G. H., Littlewood, J. E. and Pólya, G. (1929) Some simple inequalities satisfied by convex functions. Messenger of Math. 58, 145–152.Google Scholar
Jacobs, D. R. and Schach, S. (1972) Stochastic order relationships between GI/G/k systems. Ann. Math. Statist. 43, 1623–1633.Google Scholar
Kamae, T., Krengel, U. and O'brien, G. L. (1977) Stochastic inequalities on partially ordered spaces. Ann. Prob. 5, 899–912.Google Scholar
Kiefer, J. and Wolfowitz, J. (1955) On the theory of queues with many servers. Trans. Amer. Math. Soc. 78, 1–18.Google Scholar
Kirstein, B. M. (1976) Monotonicity and comparability of time-homogeneous Markov processes with discrete state spaces. Math. Operationsforsch. u. Statist. 7, 151–168.Google Scholar
König, D., Schmidt, V. and Stoyan, D. (1977) On some relations between stationary distributions of queue lengths and imbedded queue lengths in G/G/s queueing systems. Math. Operationsforsch. u. Statist. 7, 577–586.Google Scholar
Loynes, R. M. (1962) The stability of a queue with non-independent inter-arrival and service times. Proc. Camb. Phil. Soc. 58, 497–520.Google Scholar
Marshall, K. T. (1968) Some inequalities in queueing. Operat. Res. 16, 651–665.CrossRefGoogle Scholar
Marshall, K. T. and Wolff, R. W. (1971) Customer average and time average queue lengths and waiting times. J. Appl. Prob. 8, 535–542.Google Scholar
Mori, M. (1975) Some bounds for queues. J. Operat. Res. Soc. Japan, 18, 152–181.Google Scholar
Niu, S. (1977) Bounds and comparisons for some queueing systems. Operations Research Center Report 77–32, University of California, Berkeley.Google Scholar
Rolski, T. (1976) Order Relations in the Set of Probability Distribution Functions and Their Applications in Queueing Theory. Dissertationes Mathematicae CXXXII, Polish Academy of Sciences, Warsaw.Google Scholar
Rolski, T. and Stoyan, D. (1976) On the comparison of waiting times in GI/G/1 queues. Operat. Res., 24, 197–200.Google Scholar
Ross, S. M. (1978) Average delay in queues with non-stationary Poisson arrivals. J. Appl. Prob. 15, 602–609.Google Scholar
Rothchild, M. and Stiglitz, J. E. (1970) Increasing risk: I, A definition. J. Econ. Theory 2, 225–243.Google Scholar
Rothchild, M. and Stiglitz, J. E. (1971) Increasing risk: II, Its economic consequences. J. Econ. Theory 3, 66–84.Google Scholar
Sonderman, D. (1979) Comparing multi-server queues with finite waiting rooms, I: Same number of servers. Adv. Appl. Prob. 11, 439–447.Google Scholar
Stoyan, D. (1972) Monotonicity properties of stochastic models (in German). Z. Angew. Math. Mech. 52, 23–30.Google Scholar
Stoyan, D. (1977a) Further stochastic order relations among GI/G/1 queues with a common traffic intensity. Math. Operationsforsch. Statist., Ser. Optimization 8, 541–548.CrossRefGoogle Scholar
Stoyan, D. (1977b) Inequalities for multi-server queues and a tandem queue. Zast. Mat. 15, 415–419.Google Scholar
Stoyan, D. (1977c) Bounds and approximations in queueing through montonicity and continuity. Operat. Res., 25, 851–863.Google Scholar
Stoyan, D. (1977d) Qualitative Properties and Bounds for Stochastic Models (in German). Akademie-Verlag, Berlin.Google Scholar
Stoyan, H. and Stoyan, D. (1969) Monotonicity properties of waiting times in the GI/G/1 model (in German). Z. Angew. Math. Mech. 49, 729–734.Google Scholar
Strassen, V. (1965) The existence of probability measures with given marginals. Ann. Math. Statist. 36, 423–439.Google Scholar
Whitt, W. (1980) Comparing counting processes and queues. Adv. Appl. Prob. 13 (1).Google Scholar
Wolff, R. W. (1977) The effect of service time regularity on system performance. In Computer Performance, ed. Chandy, K. M. and Reiser, M., North Holland, Amsterdam, 297–304.Google Scholar