Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-23T21:23:38.790Z Has data issue: false hasContentIssue false
  • English
  • Français

The depletion time for M/G/1 systems and a related limit theorem

Published online by Cambridge University Press:  01 July 2016

Julian Keilson  and
Ushio Sumita
Julian Keilson*
Affiliation:
University of Rochester
Ushio Sumita*
Affiliation:
University of Rochester
*
Postal address for both authors: The Graduate School of Management, The University of Rochester, Rochester, NY 14627, U.S.A.
Postal address for both authors: The Graduate School of Management, The University of Rochester, Rochester, NY 14627, U.S.A.
Get access Rights & Permissions [Opens in a new window]

Abstract

Waiting-time distributions for M/G/1 systems with priority dependent on class, order of arrival, service length, etc., are difficult to obtain. For single-server multipurpose processors the difficulties are compounded. A certain ergodic post-arrival depletion time is shown to be a true maximum for all delay times of interest. Explicit numerical evaluation of the distribution of this time is available. A heavy-traffic distribution for this time is shown to provide a simple and useful engineering tool with good results and insensitivity to service-time distribution even at modest traffic intensity levels. The relationship to the diffusion approximation for heavy traffic is described.

Keywords

M/G/1 QUEUESPRIORITYSERVER BACKLOGWAITING TIMESDEPLETION TIMESHEAVY TRAFFIC
Type
Research Article
Information
Advances in Applied Probability , Volume 15 , Issue 2 , June 1983 , pp. 420 - 443
Copyright
Copyright © Applied Probability Trust 1983 

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.)

Footnotes

∗

During part of the development of the paper, U. Sumita was in the Department of Industrial Engineering and Operations Research at Syracuse University.

Research partly supported by GTE Laboratories.

References

[1] Abramowitz, M. and Stegun, I. A. (1965) Handbook of Mathematical Functions. Dover, New York.Google Scholar
[2] Carrier, G. F., Krook, M. and Pearson, C. E. (1966) Functions of a Complex Variable. McGraw-Hill, New York.Google Scholar
[3] Copson, E. T. (1935) An Introduction to the Theory of Functions of a Complex Variable. Oxford University Press, New York.Google Scholar
[4] Daley, D. J. (1968) Stochastically monotone Markov chains. Z. Wahrscheinlichkeitsth. 10, 305–317.CrossRefGoogle Scholar
[5] Gaver, D. P. (1962) A waiting line with interrupted service, including priorities. J. R. Statist. Soc., B24, 73–90.Google Scholar
[6] Gaver, D. P. (1968) Diffusion approximations and models for certain congestion problems. J. Appl. Prob. 5, 607–623.Google Scholar
[7] Keilson, J. (1962) Queues subject to service interruption. Ann. Math. Statist. 33, 1314–1322.Google Scholar
[8] Keilson, J. (1963) The first passage time density for homogeneous skip-free walks on the continuum. Ann. Math. Statist. 34, 375–380.Google Scholar
[9] Keilson, J. (1974) Sojourn times, exit times, and jitter in multivariate Markov processes. Adv. Appl. Prob. 6, 747–756.Google Scholar
[10] Keilson, J. (1978) Exponential spectra as a tool for the study of server-systems with several classes of customers. J. Appl. Prob. 15, 162–170.Google Scholar
[11] Keilson, J. (1979) Markov Chain Models–Rarity and Exponentiality. Springer-Verlag, Berlin.CrossRefGoogle Scholar
[12] Keilson, J. and Kester, A. (1977) Monotone matrices and monotone Markov processes. Stoch. Proc. Appl. 5, 231–241.CrossRefGoogle Scholar
[13] Keilson, J. and Kooharian, A. (1960) Time dependent queueing processes. Ann. Math. Statist. 31, 104–112.Google Scholar
[14] Keilson, J. and Nunn, W. (1979) Laguerre transformation as a tool for the numerical solution of integral equations of convolution type. Appl. Math. Comput. 5, 313–359.Google Scholar
[15] Keilson, J., Nunn, W. and Sumita, U. (1981) The bilateral Laguerre transform. Appl. Math. Comput. 8, 137–174.Google Scholar
[16] Keilson, J. and Steutel, F. W. (1974) Mixtures of distributions, moment inequalities and measures of exponentiality and normality. Ann. Prob. 2, 112–130.Google Scholar
[17] Kingman, J. F. C. (1964) The heavy traffic approximation in the theory of queues. Proc. Symp. Congestion Theory, ed. Smith, W. L. and Wilkinson, R. I., University of North Carolina, Chapel Hill, 137–169.Google Scholar
[18] Sumita, U. (1981) Development of the Laguerre Transform Method for Numerical Exploration of Applied Probability Models, Ph.D. Dissertation, Graduate School of Management, University of Rochester.Google Scholar
[19] Takács, L. (1957) On certain sojourn time problems in the theory of stochastic processes. Acta. Math. 8, 169–191.Google Scholar
[20] Takács, L. (1962) Introduction to the Theory of Queues. Oxford University Press, New York.Google Scholar
[21] Takács, L. (1977) Combinatorial Methods in the Theory of Stochastic Processess. Robert E. Krieger Publishing Company, Huntington, New York.Google Scholar
[22] Tomkó, J. (1972) The rate of convergence in limit theorems for service systems with finite queue capacity. J. Appl. Prob. 9, 87–102.Google Scholar