Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-27T08:32:10.074Z Has data issue: false hasContentIssue false
  • English
  • Français

Analysis of the GI/GI/1 Queue and its Variations via the LCFS Preemptive Resume Discipline and Its Random Walk Interpretation

Published online by Cambridge University Press:  27 July 2009

Michael Shalmon
Michael Shalmon
Affiliation:
INRS-Télécommunications Université du Québec, 3 Place du Commerce lle des Soeurs, Québec Canada H3E 1 H6
Get access Rights & Permissions [Opens in a new window]

Abstract

The unfinished work at arrival instants (FCFS waiting time) can be computed via the LCFS preemptive resume discipline. Analyzing the GI/GI/1 queue in this way gives full interpretation in queuing theoretic language to Feller's analysis of the fluctuations of the random walk. Also, this approach leads naturally to stochastic decompositions for the queue with set-up times, and for other variations of the standard queue. For the M/G/1 queue, the derivations are qualitative, and there are additional connections to branching processes.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 2 , Issue 2 , April 1988 , pp. 215 - 230
Copyright
Copyright © Cambridge University Press 1988

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

Borel, E. (1942). Sur l'emploi du theorème de Bernoulli pour faciliter le calcul d'une infinité des coefficients. Application au probleme de l'attente a un guichet,” C.R. de l'Academie des sciences. Paris 214:452–456.Google Scholar
Kleinrock, L.Queueing Systems, Vol. 1, New York: John Wiley.Google Scholar
Cohen, J.W. (1976). On Regenerative Processes in Queuing Theory. Springer-Verlag.CrossRefGoogle Scholar
Cohen, J.W. (1978). Properties of the process of level crossings during a busy cycle of the M/G/l queuing system. Mathematics of Operations Research 3:133–144.CrossRefGoogle Scholar
Cooper, R.B. (1981). Introduction to Queuing Theory, 2nd Ed.New York: North Holland.Google Scholar
Cooper, R.B. (1986). Benes's formula for M/G/1-FIFO “explained” by preemptive resume LIFO. Journal of Applied Probability 23:550–554.CrossRefGoogle Scholar
Doshi, B.T. (1985). A note on stochastic decomposition in a GI/G/l queue with vacations or set-up times. Journal of Applied Probability 22:419–428.CrossRefGoogle Scholar
Fakinos, D. (1981). The G/G1 queuing system with a particular queue discipline. Journal of the Royal Statistical Society B 43:190–196.Google Scholar
Fakinos, D. (1986). On the single server queue with preemptive resume last-come-first-served queue discipline. Journal of Applied Probability 23:243–248.CrossRefGoogle Scholar
Feller, W. (1971). An Introduction to Probability Theory and its Applications, Vol. II, 2nd ed.New York: Wiley.Google Scholar
Fuhrmann, S.W. (1984). A note on the M/G/l queue with server vacations. Operations Research 32:1368–1373.CrossRefGoogle Scholar
Fuhrmann, S.W. & Cooper, R.B. (1985). Stochastic decompositions in the M/G1 queue with generalized vacations. Operations Research 33:1117–1129.CrossRefGoogle Scholar
Gelenbe, E. & Iasnogorodski, R. (1980). A queue with server of walking type. Annales Institut Poincaré 16:63–73.Google Scholar
Kaplan, M.A. (1980). A two-fold tandem net with deterministic links and source interference. Operations Research 28:512–526.CrossRefGoogle Scholar
Keilson, J. & Servi, L.D. (1986). Oscillating random walk models for GI/GI/1 vacation systems with Bernoulli schedules. Journal of Applied Probability 23:790–802.CrossRefGoogle Scholar
Kelly, F.P. (1975). The departure process from a queuing system. Mathematical Proceedings Cambridge Philosophical Society 80:283–285.CrossRefGoogle Scholar
Kendall, D.G. (1951). Some problems in the theory of queues. Journal of the Royal Statistical Society B 13:151–183.Google Scholar
Levy, H. & Kleinrock, L. (1986). A queue with starter and a queue with vacation: delay analysis by decomposition. Operations Research 34:426–436.CrossRefGoogle Scholar
Ott, T.J. (1984). On the M/G/l queue with additional inputs. Journal of Applied Probability 21:129–142.CrossRefGoogle Scholar
Shalmon, M. & Kaplan, M.A. (1984). A tandem network of queues with deterministic service and intermediate arrivals. Operations Research 32:753–773.CrossRefGoogle Scholar
Shalmon, M. (1985). Queues and packet-multiplexing networks. Ph.D. Thesis, McGill University, Canada.Google Scholar
Shalmon, M. (1987). Exact delay analysis of packet-switching concentrating networks. IEEE Transactions Communication 35: 1265–1271.CrossRefGoogle Scholar
Shalmon, M. (1987). Stochastic decompositions in queuing systems with Poisson arrivals.Google Scholar
Wolff, R.W.Poisson arrivals see time averages. Operations Research 30:223–231.CrossRefGoogle Scholar