Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-13T22:46:41.825Z Has data issue: false hasContentIssue false
  • English
  • Français

On the M/G/1 queue by additional inputs

Published online by Cambridge University Press:  14 July 2016

Teunis J. Ott
Teunis J. Ott*
Affiliation:
Regional Bell Operating Companies
*
∗ Postal address: Bell Laboratories, Rm 4L435, Crawfords Comer Road, Holmdel, NJ 07733, U.S.A.
Get access Rights & Permissions [Opens in a new window]

Abstract

A single-server queueing system is studied, the input into which consists of the sum of two independent stochastic processes. One of these is an ‘M/G' type input process, the other a much more general process which need not be Markov. There are two types of busy period, depending on which arrival process started the busy period. Stochastic monotonicity results are derived and it is found that under a stationarity-like condition the probability of being in a busy period which started with an ‘M/G' arrival is independent of time and is the same it would be with the ‘M/G' process as only input process. Also, distributional results are obtained for the virtual waiting-time process, and these results are used to reduce the study of a single-server queueing system with as input the sum of independent ‘M/G' and ‘GI/G' input streams to the study of a related GI/G/1 queueing system.

The purpose of this paper is to pave the way for a study of an M/G/1 queueing system with periodic arrivals of additional work, and for optimal scheduling of maintenance processes in certain real-time computer systems.

Keywords

QUEUEING THEORYMULTIPLE INPUT STREAMS
Type
Research Papers
Information
Journal of Applied Probability , Volume 21 , Issue 1 , March 1984 , pp. 129 - 142
Copyright
Copyright © Applied Probability Trust 1984 

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] Barberis, G. (1980) A useful tool in the theory of priority queueing. IEEE Trans. Communication COMM-26, 1757–1962.CrossRefGoogle Scholar
[2] Bhat, U. N., Wheeler, A. C. and Fisher, M. J. (1974) On the existence of limiting distributions in stochastic systems with secondary inputs. Opsearch 11, 81–89.Google Scholar
[3] Daley, D. J. (1968) Stochastically monotone Markov chains. Z. Wahrscheinlichkeitsth. 10, 305–317.CrossRefGoogle Scholar
[4] Fisher, M. J. (1977) An approximation of queueing systems with interruptions. Management Sci. 24, 338–344.CrossRefGoogle Scholar
[5] Franken, P., König, D., Arndt, U. and Schmidt, V. (1981) Queues and Point Processes. Akademie-Verlag, Berlin.Google Scholar
[6] Kamae, T., Krengel, U. and O'brien, G. L. (1977) Stochastic inequalities on partially ordered spaces. Ann. Prob. 5, 899–912.CrossRefGoogle Scholar
[7] Kamoun, F. (1976) Design Considerations for Large Computer Communications Networks, , Department of Computer Science, University of California, Los Angeles.Google Scholar
[8] Keilson, J. and Kester, A. J. M. (1977) Monotone matrices and monotone Markov processes. Stoch. Proc. Appl. 5, 231–241.CrossRefGoogle Scholar
[9] Kleinrock, L. and Kamoun, F. (1976) Data communications through large packet switching networks. Proc. 8th Teletraffic Congress, Melbourne. Google Scholar
[10] Kuczura, A. (1972) Queues with mixed renewal and Poisson inputs. Bell System Tech. J. 51, 1305–1326.CrossRefGoogle Scholar
[11] Kuczura, A. (1972) Loss systems with mixed renewal and Poisson inputs. Operat. Res. 21, 787–795.CrossRefGoogle Scholar
[12] Lehman, E. L. (1959) Testing Statistical Hypotheses. Wiley, New York.Google Scholar
[13] Lukacs, E. (1970) Characteristic Functions, 2nd edn. Hafner, New York.Google Scholar
[14] Ott, T. J. (1977) The covariance function of the virtual waiting time process in an M/G/1 queue. Adv. Appl. Prob. 9, 158–168.CrossRefGoogle Scholar
[15] Ot, T. J. On the M/G/1 queue with additional periodic inputs, I: Exact results. Unpublished.Google Scholar
[16] Ot, T. J. On scheduling maintenance processes in a real time computer system with clock generated interrupts. Unpublished.Google Scholar
[17] Ot, T. J. An alternative approach to the M/G/1 queue with additional inputs. Unpublished.Google Scholar
[18] Sahin, I. (1971) Equilibrium behavior of a stochastic system with secondary input. J. Appl. Prob. 8, 252–260.CrossRefGoogle Scholar
[19] Sahin, I. (1978) Moment inequalities for a class of stochastic systems. Stoch. Proc. Appl. 7, 123–130.CrossRefGoogle Scholar
[20] Sahin, I. and Bhat, U. N. (1971) A stochastic system with scheduled secondary inputs. Operat. Res. 16, 436–446.CrossRefGoogle Scholar
[21] Sahin, I. and Perrakis, S. (1976) Moment inequalities for a class of single server queues. INFOR 14, 144–152.Google Scholar
[22] Stoyan, D. (1977) Bounds and approximations in queuing through monotonicity and continuity, Operat. Res. 25, 851–863.CrossRefGoogle Scholar
[23] Stoyan, D. (1977) Qualitative Properties and Bounds for Stochastic Models (in German). Akademie-Verlag, Berlin.Google Scholar
[24] Stoyan, D. (1982) Comparison Methods for Queues and Other Stochastic Models (English translation of [23]). Wiley, New York.Google Scholar
[25] Takács, L. (1962) Introduction to the Theory of Queues. Oxford University Press, New York.Google Scholar
[26] Whitt, W. (1980) The effect of variability in the GI/G/s queue. J. Appl. Prob. 17, 1062–1071.CrossRefGoogle Scholar
[27] Whitt, W. (1981) Comparing counting processes and queues. Adv. Appl. Prob. 13, 207–220.CrossRefGoogle Scholar
[28] Whitt, W. Monotone Markov processes. Unpublished.Google Scholar