Abstract
We propose a new research direction to reinvigorate research into better understanding of the M/G/K and other queueing systems—via obtaining tight bounds on the mean waiting time as functions of the moments of the service distribution. Analogous to the classical Markov–Krein theorem, we conjecture that the bounds on the mean waiting time are achieved by service distributions corresponding to the upper/lower principal representations of the moment sequence. We present analytical, numerical, and simulation evidence in support of our conjectures.
Similar content being viewed by others
Explore related subjects
Discover the latest articles and news from researchers in related subjects, suggested using machine learning.References
Bertsimas, D., Natarajan, K.: A semidefinite optimization approach to the steady-state analysis of queueing systems. Queueing Syst. 56(1), 27–39 (2007)
Bertsimas, D., Popescu, I.: Optimal inequalities in probability theory: A convex optimization approach. SIAM J. Optim. 15, 780–804 (2005)
Breuer, L.: Transient and stationary distributions for the GI/G/k queue with Lebesgue-dominated inter-arrival time distribution. Queueing Syst. 45(1), 47–57 (2003)
Burman, D., Smith, D.: A light-traffic theorem for multi-server queues. Math. Oper. Res. 8, 15–25 (1983)
Daley, D., Rolski, T.: Some comparability results for waiting times in single- and many-server queues. J. Appl. Probab. 21, 887–900 (1984)
Daley, D.J.: Some results for the mean waiting-time and workload in GI/GI/k queues. In: Dshalalow, J.H. (ed.) Frontiers in Queueing: Models and Applications in Science and Engineering, Boca Raton, FL, USA, pp. 35–59 (1997)
de Smit, J.H.A.: A numerical solution for the multiserver queue with hyper-exponential service times. Oper. Res. Lett. 2(5), 217–224 (1983)
de Smit, J.H.A.: The queue GI/M/s with customers of different types or the queue GI/H m /s. Adv. Appl. Probab. 15(2), 392–419 (1983)
de Smit, J.H.A.: The queue GI/H m /s in continuous time. J. Appl. Probab. 22(1), 214–222 (1985)
Eckberg, A. Jr.: Sharp bounds on Laplace–Stieltjes transforms, with applications to various queueing problems. Math. Oper. Res. 2(2), 132–142 (1977)
Foss, S., Korshunov, D.: Heavy tails in multi-server queue. Queueing Syst. 52(1), 31–48 (2006)
Gamarnik, D., Momčilović, P.: Steady-state analysis of a multiserver queue in the Halfin–Whitt regime. Adv. Appl. Probab. 40(2), 548–577 (2008)
Gans, N., Koole, G., Mandelbaum, A.: Telephone call centers: tutorial, review, and research prospects. Manuf. Serv. Oper. Manag. 5, 79–141 (2003)
Gupta, V., Dai, J., Harchol-Balter, M., Zwart, B.: On the inapproximability of M/G/K: why two moments of job size distribution are not enough. Queueing Syst. 64(1), 5–48 (2010)
Gupta, V., Osogami, T.: On Markov-Krein characterization of mean sojourn time in queueing systems. Technical Report CMU-CS-11-109, School of Computer Science, Carnegie Mellon University (2011)
Hokstad, P.: Approximations for the M/G/m queue. Oper. Res. 26(3), 510–523 (1978)
Hokstad, P.: The steady state solution of the M/K 2/m queue. Adv. Appl. Probab. 12(3), 799–823 (1980)
Karlin, S., Studden, W.J.: Tchebycheff Systems: With Applications in Analysis and Statistics. Wiley, New York (1966)
Kimura, T.: Diffusion approximation for an M/G/m queue. Oper. Res. 31, 304–321 (1983)
Kingman, J.: Inequalities in the theory of queues. J. R. Stat. Soc. 32(1), 102–110 (1970)
Köllerström, J.: Heavy traffic theory for queues with several servers. I. J. Appl. Probab. 11, 544–552 (1974)
Lee, A., Longton, P.: Queueing process associated with airline passenger check-in. Oper. Res. Q. 10, 56–71 (1959)
Ma, B., Mark, J.: Approximation of the mean queue length of an M/G/c queueing system. Oper. Res. 43(1), 158–165 (1995)
Miyazawa, M.: Approximation of the queue-length distribution of an M/GI/s queue by the basic equations. J. Appl. Probab. 23, 443–458 (1986)
Müller, A., Stoyan, D.: Comparison Methods for Stochastic Models and Risks. Wiley Series in Probability and Statistics. Wiley, Chichester (2002)
Neuts, M.F.: Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach. Dover, New York (1995), revised edn.
Nozaki, S., Ross, S.: Approximations in finite-capacity multi-server queues with Poisson arrivals. J. Appl. Probab. 15(4), 826–834 (1978)
Osogami, T., Raymond, R.: Semidefinite optimization for transient analysis of queues. ACM SIGMETRICS Perform. Eval. Rev. 38(1), 363–364 (2010)
Scheller-Wolf, A., Sigman, K.: New bounds for expected delay in FIFO GI/GI/c queues. Queueing Syst. 26(1–2), 169–186 (1997)
Scheller-Wolf, A., Vesilo, R.: Structural interpretation and derivation of necessary and sufficient conditions for delay moments in FIFO multiserver queues. Queueing Syst. 54(3), 221–232 (2006)
Stoyan, D.: Approximations for M/G/s queues. Math. Oper.forsch. Stat., Ser. Optim. 7, 587–594 (1976)
Stoyan, D.: Comparison Methods for Queues and Other Stochastic Models. Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics. Wiley, Chichester (1983). Translation from the German edited by D.J. Daley
Tijms, H.C., Van Hoorn, M.H., Federgruen, A.: Approximations for the steady-state probabilities in the M/G/c queue. Adv. Appl. Probab. 13, 186–206 (1981)
Whitt, W.: The effect of variability in the GI/G/s queue. J. Appl. Probab. 17, 1062–1071 (1980)
Whitt, W.: Comparison conjectures about the M/G/s queue. Oper. Res. Lett. 2(5), 203–209 (1983)
Whitt, W.: On approximations for queues, I: Extremal distributions. AT&T Bell Lab. Tech. J. 63, 115–138 (1984)
Whitt, W.: Approximations for the GI/G/m queue. Prod. Oper. Manag. 2(2), 114–161 (1993)
Whitt, W.: A diffusion approximation for the G/GI/n/m queue. Oper. Res. 52, 922–941 (2004)
Wolff, R.W.: Stochastic Modeling and the Theory of Queues. Prentice Hall, New York (1989)
Yao, D.: Refining the diffusion approximation for the M/G/m queue. Oper. Res. 33, 1266–1277 (1985)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Gupta, V., Osogami, T. On Markov–Krein characterization of the mean waiting time in M/G/K and other queueing systems. Queueing Syst 68, 339–352 (2011). https://doi.org/10.1007/s11134-011-9248-8
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11134-011-9248-8