Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-15T01:48:25.398Z Has data issue: false hasContentIssue false
  • English
  • Français

The effect of service time variability on maximum queue lengths in MX /G/1 queues

Part of:Special processesOperations research and management science

Published online by Cambridge University Press:  14 July 2016

Ger Koole,
Misja Nuyens and
Rhonda Righter
Ger Koole*
Affiliation:
Vrije Universiteit Amsterdam
Misja Nuyens*
Affiliation:
Vrije Universiteit Amsterdam
Rhonda Righter*
Affiliation:
University of California, Berkeley
*
∗ Postal address: Department of Mathematics, Vrije Universiteit Amsterdam, De Boelelaan 1081a, 1081 HV Amsterdam, The Netherlands.
∗ Postal address: Department of Mathematics, Vrije Universiteit Amsterdam, De Boelelaan 1081a, 1081 HV Amsterdam, The Netherlands.
∗∗∗∗ Postal address: Department of Industrial Engineering and Operations Research, University of California, Berkeley, CA 94720, USA. Email address: rrighter@ieor.berkeley.edu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We study the impact of service time distributions on the distribution of the maximum queue length during a busy period for the MX /G/1 queue. The maximum queue length is an important random variable to understand when designing the buffer size for finite-buffer (M/G/1/n) systems. We show the somewhat surprising result that, for three variations of the preemptive last-come–first-served discipline, the maximum queue length during a busy period is smaller when service times are more variable (in the convex sense).

Keywords

Maximum queue lengthbusy periodservice disciplineLCFSvariabilitystochastic orderingbuffer overflow

MSC classification

Primary:60K25: Queueing theory
Secondary:90B22: Queues and service

Information

Type
Short Communications
Information
Journal of Applied Probability , Volume 42 , Issue 3 , September 2005, pp. 883 - 891
Copyright
© Applied Probability Trust 2005 

References

Adiri, I., Frostig, E. and Rinnooy Kan, A. H. G. (1991). Scheduling on a single machine with a single breakdown to minimize stochastically the number of tardy Jobs. Naval Res. Logistics 38, 261–271.3.0.CO;2-I>CrossRefGoogle Scholar
Birge, J., Frenk, J. B. G., Mittenthal, J. and Rinnooy Kan, A. H. G. (1990). Single-machine scheduling subject to stochastic breakdowns. Naval Res. Logistics 37, 661–677.3.0.CO;2-3>CrossRefGoogle Scholar
Cai, X., Sun, X. Q. and Zhou, X. (2004). Stochastic scheduling subject to machine breakdowns: the preemptive-repeat model with discounted reward and other criteria. Naval Res. Logistics 51, 800–817.CrossRefGoogle Scholar
Cai, X., Wu, X. Y. and Zhou, X. (2005). Dynamically optimal policies for stochastic scheduling subject to preemptive-repeat machine breakdowns. To appear in IEEE Trans. Automation Sci. Eng. CrossRefGoogle Scholar
Chang, C.-S., Chao, X., Pinedo, M. and Shanthikumar, J. G. (1991). Stochastic convexity for multidimensional processes and its applications. IEEE Trans. Automatic Control 36, 1347–1355.CrossRefGoogle Scholar
Hordijk, A. (2001). Comparison of queues with different discrete-time arrival processes. Prob. Eng. Inf. Sci. 15, 1–14.CrossRefGoogle Scholar
Kelly, F. P. (1979). Reversibility and Stochastic Networks. John Wiley, New York.Google Scholar
Makowski, A. M. (1994). On an elementary characterization of the increasing convex ordering, with an application. J. Appl. Prob%. 31, 834–840.CrossRefGoogle Scholar
Miyazawa, M. (1990). Complementary generating functions for M{X}/GI/1/k and GI/M{Y}/1/k queues and their application to the comparison of loss probabilities. J. Appl. Prob. 27, 684–692.CrossRefGoogle Scholar
Miyazawa, M. and Shanthikumar, J. G. (1991). Monotonicity of the loss probabilities of single server finite queues with respect to convex order of arrival or service processes. Prob. Eng. Inf. Sci. 5, 43–52.CrossRefGoogle Scholar
Shanthikumar, J. G. and Yao, D. D. (1994). Stochastic comparisons in closed Jackson networks. In Stochastic Orders and Their Applications, eds Shaked, M. and Shanthikumar, J. G., Academic Press, New York, pp. 433–460.Google Scholar