Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-22T14:59:56.840Z Has data issue: false hasContentIssue false
  • English
  • Français

On the mean sojourn time of jobs in queues by general service disciplines

Part of: Operations research and management science Special processes

Published online by Cambridge University Press:  01 July 2016

Gunter Ritter
Gunter Ritter*
Affiliation:
Universität Passau
*
* Postal address: Fakultät für Mathematik und Informatik, Universität Passau, 94030 Passau, Germany.
Get access Rights & Permissions [Opens in a new window]

Abstract

Existence and finiteness of the sample-mean limit of sojourn times of jobs in a queueing system are investigated. The queueing system operates under rather general multiprocessor disciplines allowing job classes and priorities. The input stream of jobs consisting of job classes and interarrival and processing times is stationary and ergodic and may contain batch arrivals. Existence of the sample-mean limit is proved by means of the superadditive ergodic theorem, and its finiteness is controlled by uniform mixing of the input stream.

Keywords

QUEUEING SYSTEMSSTATIONARY AND ERGODIC INTERARRIVAL AND PROCESSING TIMESG/G/mG/G1/mBATCH ARRIVALSGENERAL MULTIPROCESSOR DISCIPLINESJOB CLASSESPRIORITIESWORK CONSERVATIONSOJOURN TIMEWAITING TIMESUPERADDITIVE ERGODIC THEOREMUNIFORM MIXING

MSC classification

Primary: 60K25: Queueing theory
Secondary: 90B22: Queues and service
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 26 , Issue 2 , June 1994 , pp. 516 - 538
Copyright
Copyright © Applied Probability Trust 1994 

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

[1] Asmussen, S. (1987) Applied Probability and Queues. Wiley, Chichester.Google Scholar
[2] Baccelli, F. and Bremaud, P. (1987) Palm Probabilities and Stationary Queues. Lecture Notes in Statistics 41, Springer-Verlag, Berlin.Google Scholar
[3] Bacelli, F. and Liu, Zhen (1992) On a class of stochastic recursive sequences arising in queueing theory. Ann. Prob. 20, 350–374.Google Scholar
[4] Borovkov, A. A. (1978) Ergodic and stability theorems for a class of stochastic equations and their applications. Teoriya Veroyatnost. i Primenen 23, 241–262 (in Russian).Google Scholar
[5] Borovkov, A. A. (1980) Asymptotic Methods in Queueing Theory. Izd. Nauka, Moscow (in Russian).Google Scholar
[6] Bradley, R. C. (1986) Basic properties of strong mixing conditions. In Dependence in Probability and Statistics. Oberwolfach 1985, ed. Eberlein, E. and Taqqu, M. S.. Birkhäuser, Boston.Google Scholar
[7] Daley, D. J. and Rolski, T. (1992) Finiteness of waiting time moments in general stationary single-server queues. Ann. Appl. Prob. 2, 987–1008.Google Scholar
[8] Durrett, R. (1991) Probability. Wadsworth & Brooks/Cole, Pacific Grove, CA.Google Scholar
[9] Feller, W. (1971) An Introduction to Probability Theory and its Applications II, 2nd edn. Wiley, New York.Google Scholar
[10] Flett, T. M. (1980) Differential Analysis. Cambridge University Press.Google Scholar
[11] Flipo, D. (1981) Comparaison des disciplines de service des files d'attente G/G/1. Ann. Inst. H. Poincaré, XVII, 191–212.Google Scholar
[12] Franken, P., König, D., Arndt, U. and Schmidt, V. (1982) Queues and Point Processes. Wiley, Chichester.Google Scholar
[13] Gray, R. M. (1987) Probability, Random Processes and Ergodic Properties. Springer-Verlag, New York.Google Scholar
[14] Hall, P. and Heyde, C. C. (1980) Martingale Limit Theory and Its Applications. Academic Press, New York.Google Scholar
[15] Ibragimov, I. A. (1962) Some limit theorems for stationary processes. Theory Prob. Appl. 7, 349–382.Google Scholar
[16] Ibragimov, I. A. (1975) A note on the central limit theorem for dependent random variables. Theory Prob. Appl. 20, 135–141.Google Scholar
[17] Ibragimov, I. A. and Linnik, Yu. V. (1971) Independent and Stationary Sequences of Random Variables. Wolters-Noordhoff, Groningen.Google Scholar
[18] Kelly, F. P. (1979) Reversibility and Stochastic Networks. Wiley, Chichester.Google Scholar
[19] Kiefer, J. and Wolfowitz, J. (1956) On the characteristics of the general queueing process with applications to random walk. Ann. Math. Statist. 27, 147–161.CrossRefGoogle Scholar
[20] Kingman, J. F. C. (1970) Inequalities in the theory of queues. J. R. Statist. Soc. B 32, 102–110.Google Scholar
[21] Krengel, U. (1985) Ergodic Theorems. de Gruyter, Berlin.CrossRefGoogle Scholar
[22] Lindley, D. V. (1952) The theory of queues with a single server. Proc. Camb. Phil. Soc. 48, 277–289.Google Scholar
[23] Loynes, R. M. (1962) The stability of a queue with non-independent inter-arrival and service times. Proc. Camb. Phil. Soc. 58, 497–520.CrossRefGoogle Scholar
[24] Miyazawa, M. (1977) Time and customer processes in queues with stationary inputs. J. Appl. Prob. 14, 349–357.CrossRefGoogle Scholar
[25] Miyazawa, M. (1979) A formal approach to queueing processes in the steady-state and their applications. J. Appl. Prob. 16, 332–346.CrossRefGoogle Scholar
[26] Ritter, G. and Wacker, U. (1991) The mean waiting time in a G/G/m/8 queue with the LCFS-P service discipline. Adv. Appl. Prob. 23, 406–428.CrossRefGoogle Scholar
[27] Rolski, T. (1981) Stationary Random Processes Associated with Point Processes. Lecture Notes in Statistics 5, Springer-Verlag, Berlin.Google Scholar
[28] Shanthikumar, J. G. and Sumita, U. (1987) Convex ordering of sojourn times in single-server queues: extremal properties of FIFO and LIFO service disciplines. J. Appl. Prob. 24, 737–748.CrossRefGoogle Scholar
[29] Vasicek, O. A. (1977) An inequality for the variance of waiting time under a general queueing discipline. Operat. Res. 25, 879–884.CrossRefGoogle Scholar
[30] Wolff, R. (1991) On finite delay-moment conditions in queues. Operat. Res. 39, 771–775.CrossRefGoogle Scholar