Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-14T19:21:55.587Z Has data issue: false hasContentIssue false

Stochastic comparisons for queueing models via random sums and intervals

Published online by Cambridge University Press:  01 July 2016

Alain Jean-Marie
Affiliation:
INRIA
Zhen Liu*
Affiliation:
INRIA
*
Postal address for both authors: INRIA Sophia-Antipolis, 2004 Route des Lucioles, BP 109, 06565 Valbonne, France.

Abstract

We consider the relationships among the stochastic ordering of random variables, of their random partial sums, and of the number of events of a point process in random intervals. Two types of result are obtained. Firstly, conditions are given under which a stochastic ordering between sequences of random variables is inherited by (vectors of) random partial sums of these variables. These results extend and generalize theorems known in the literature. Secondly, for the strong, (increasing) convex and (increasing) concave stochastic orderings, conditions are provided under which the numbers of events of a given point process in two ordered random intervals are also ordered.

These results are applied to some comparison problems in queueing systems. It is shown that if the service times in two M/GI/1 systems are compared in the sense of the strong stochastic ordering, or the (increasing) convex or (increasing) concave ordering, then the busy periods are compared for the same ordering. Stochastic bounds in the sense of increasing convex ordering on waiting times and on response times are provided for queues with bulk arrivals. The cyclic and Bernoulli policies for customer allocation to parallel queues are compared in the transient regime using the increasing convex ordering. Comparisons for the five above orderings are established for the cycle times in polling systems.

MSC classification

Type
Research Article
Copyright
Copyright © Applied Probability Trust 1992 

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] Baccelli, F. (1991) Stochastic ordering of random processes with an imbedded point process. J. Appl. Prob. 28, 553567.CrossRefGoogle Scholar
[2] Baccelli, F. and Bremaud, P. (1987) Palm Probabilities and Stationary Queues. Lecture Notes in Statistics 41, Springer-Verlag, Berlin.Google Scholar
[3] Borovkov, A. A. (1976) Stochastic Processes in Queueing Theory. Springer-Verlag, Berlin.Google Scholar
[4] Boxma, O. J., Levy, H. and Yechiali, U. (1992) Cyclic reservation schemes for efficient operation of multiple-queue single server systems. Ann. Operat. Res. To appear.Google Scholar
[5] Brown, M. (1980) Bounds, inequalities and monotonicity properties for some specialized renewal processes. Ann. Prob. 8, 227240.CrossRefGoogle Scholar
[6] Chang, C. S. (1989) Comparison Theorems for Queueing Systems and Their Applications to ISDN. Ph.D. Dissertation, Dept. of Electrical Engineering, Columbia University, New York.Google Scholar
[7] Erdélyi, A., (Ed.) (1955) Higher Transcendental Functions , Vol. III. McGraw-Hill, New York.Google Scholar
[8] Feller, W. (1966) An Introduction to Probability Theory and its Applications , vol. 2. Wiley, New York.Google Scholar
[9] Hansen, B. G. (1992) Some monotonicity properties of the compound geometric distribution and of the renewal function. Georg-August-University, Göttingen.Google Scholar
[10] Hansen, B. G. and Frenk, J. B. G. (1991) Some monotonicity properties of the delayed renewal function. J. Appl. Prob. 28, 811821.CrossRefGoogle Scholar
[11] Jean-Marie, A. and Liu, Z. (1991) Stochastic orderings on partial sums of random variables and on counting measures of random intervals. INRIA Research Report 1422, April 1991.Google Scholar
[12] Kleinrock, L. (1975) Queueing Networks , Vol. 1, Wiley, New York.Google Scholar
[13] Lindvall, T. (1986) On coupling of renewal processes with use of failure rates. Stoc. Proc. Appl. 22, 115.Google Scholar
[14] Loynes, R. M. (1962) The stability of queues with non-independent inter-arrival and service times. Proc. Camb. Phil. Soc. 58, 497520.Google Scholar
[15] Marshall, A. W. and Olkin, I. (1979) Inequalities: Theory of Majorization and its Applications. Academic Press, New York.Google Scholar
[16] Rolski, T. (1976) Order relations in the set of probability distribution functions and their applications in queueing theory. Dissertationes Mathematicae, Polska Akademia Nauk, Instytut Matematyczny, 1976.Google Scholar
[17] Rolski, T. and Szekli, R. (1991) Stochastic ordering and thinning of point processes. Stoch. Proc. Appl. 37, 299312.CrossRefGoogle Scholar
[18] Ross, S. (1983) Stochastic Processes. Wiley, New York.Google Scholar
[19] Stoyan, D. (1983) Comparison Methods for Queues and Other Stochastic Models (English translation ed. Daley, D. J.). Wiley, New York.Google Scholar
[20] Strassen, V. (1965) The existence of probability measures with given marginals. Ann. Math. Statist. 36, 423439.Google Scholar
[21] Tedijanto, T. E. (1992) A note on the comparison between Bernoulli and limited policies in vacation models. Performance Evaluation 15, 8997.Google Scholar
[22] Whitt, W. (1981) Comparing counting processes and queues. Adv. Appl. Prob. 13, 207220.CrossRefGoogle Scholar