×

zbMATH — the first resource for mathematics

Rate conservation laws: A survey. (English) Zbl 0803.60092
This is a survey paper on rate conservation laws (RCL) arising in queueing and related stochastic areas. It is shown that many fundamental results such as Little’s formula, equilibrium equations, Mecke’s formula for a stationary random measure, can be formulated as RCL. Several generalizations of RCL are discussed. The survey contains a short historical background, examples from queueing and risk theory, and a list of 126 references.

MSC:
60K25 Queueing theory (aspects of probability theory)
90B22 Queues and service in operations research
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] F. Baccelli and P. Bremaud, Palm probabilities and stationary queueing systems, Lecture Notes in Statistics 41 (Springer-Verlag, New York, 1987).
[2] I. Bardhan, I. and K. Sigman, Rate conservation law for stationary semi-martingales, to appear in Prob, in Informational Eng. and Sci. (1993).
[3] F. Baskett, K.M. Chandy, R.R. Muntz and F.G. Palacios, Open, closed and mixed networks of queues with different classes of customers, J. ACM 22 (1975) 248-260. · Zbl 0313.68055 · doi:10.1145/321879.321887
[4] P. Billingsley,Probability and Measures (Wiley, New York, 1979). · Zbl 0411.60001
[5] A. Brandt, P. Franken and B. Lisek,Stationary Stochastic Models (Wiley, Chichester, 1990). · Zbl 0723.60112
[6] P. Bremaud, Bang-bang controls of point processes, Adv. Appl. Prob. 8 (1976) 385-394. · Zbl 0348.60077 · doi:10.2307/1425910
[7] P. Bremaud,Point Processes and Queues: Martingale Dynamics (Springer, New York, 1981). · Zbl 0478.60004
[8] P. Bremaud, An elementary proof of Sengupta’s invariance relation and a remark on Miyazawa’s conservation principle, J. Appl. Prob. 28 (1991) 950-954. · Zbl 0746.60092 · doi:10.2307/3214703
[9] P. Bremaud, R. Kannurpatti and R. Mazumdar, Event and time averages: a review and some generalizations, Adv. Appl. Prob. 24 (1992) 377-411. · Zbl 0761.60045 · doi:10.2307/1427697
[10] S.L. Brumelle, On the relation between customer and time averages in queues, J. Appl. Prob. 8 (1971) 508-520. · Zbl 0232.60085 · doi:10.2307/3212174
[11] S.L. Brumelle, A generalization ofL=?W to moments of queue length and waiting times, Oper. Res. 20 (1972) 1127-1136. · Zbl 0265.60086 · doi:10.1287/opre.20.6.1127
[12] P.H. Brill, An embedded level crossing technique for dams and queues, J. Appl. Prob. 16 (1979) 174-186. · Zbl 0396.60091 · doi:10.2307/3213385
[13] P.H. Brill and M.J.M. Posner, Level crossings in point processes applied to queues: Single server case, Oper. Res. 25 (1977) 662-674. · Zbl 0373.60114 · doi:10.1287/opre.25.4.662
[14] P.H. Brill and M.J.M. Posner, The system point method in exponential queues: A level crossing approach, Math. Oper. Res. 6 (1981) 31-49. · Zbl 0497.60089 · doi:10.1287/moor.6.1.31
[15] J.W. Cohen, On up- and down crossings, J. Appl. Prob. 13 (1977) 405-410. · Zbl 0365.60108 · doi:10.2307/3213014
[16] J.W. Cohen and M. Rubinovitch, On level crossing and cycles in dam processes, Math. Oper. Res. 2 (1977) 297-310. · Zbl 0389.60077 · doi:10.1287/moor.2.4.297
[17] O.L.V. Costa, Stationary distributions for piecewise-deterministic Markov processes, J. Appl. Prob. 27 (1990) 60-73. · Zbl 0703.60068 · doi:10.2307/3214595
[18] D.J. Daley and D. Vere-Jones,An introduction to the Theory of Point Processes (Springer, New York, 1988). · Zbl 0657.60069
[19] M.H.A. Davis, Piecewise-deterministic Markov process: A general class of nondiffusion stochastic models, J.R. Statist. Soc. B46 (1984) 353-388. · Zbl 0565.60070
[20] B.T. Doshi, Conditional and unconditional distributions forM/G/1 type queues with server vacations, Queueing Systems 7 (1990) 229-252. · Zbl 0714.60087 · doi:10.1007/BF01154544
[21] B.T. Doshi, Level-crossing analysis of queues, in:Queueing and Related Models, eds. U.N. Bhat and I.V. Basawa (Oxford University Press, 1992) pp. 3-33. · Zbl 0783.60093
[22] F. Dufresne and H.U. Gerber, The surplus immediately before and at ruin, and the amount of the claim ruin, Insurance: Mathematics and Economics 7 (1988) 193-199. · Zbl 0674.62072 · doi:10.1016/0167-6687(88)90076-5
[23] A.K. Erlang, Solution of some problems in the theory of probabilities of significance in automatic telephone exchanges, Post Office Electr. Eng. J. 10 (1917) 189-197.
[24] R. Elliott,Stochastic Calculus and Applications (Springer, New York, 1982). · Zbl 0503.60062
[25] M. El-Taha, On conditional ASTA: A samplepath approach, Stochastic Models 8 (1992) 157-177. · Zbl 0754.60108 · doi:10.1080/15326349208807218
[26] M. El-Taha and S. Stidham Jr., Sample-path analysis of stochastic discrete-event systems, preprint (1992).
[27] S.N. Ethier and T.G. Kurtz,Markov Processes: Characterization and Convergence (Wiley, New York, 1986). · Zbl 0592.60049
[28] W. Feller,Introduction to Probability Theory and its Applications, Vol. II (Wiley, New York, 1971). · Zbl 0219.60003
[29] J.M. Ferrandiz and A. Lazar, Rate conservation for stationary processes, J. Appl. Prob. 28 (1991) 146-158. · Zbl 0721.60106 · doi:10.2307/3214747
[30] P.D. Finch, On the distribution of queue size in queueing problems, Acta Math. Sci. Acad. Hung. 10 (1959) 327-336. · Zbl 0119.14804 · doi:10.1007/BF02024497
[31] P. Franken, Einige Anwendungen der Theorie zufällliger Punktprozesse in der Bedienungstheorie, I. Math. Nachr. 70 (1976) 303-319. · Zbl 0327.60060 · doi:10.1002/mana.19750700124
[32] P. Franken, D. König, U. Arndt and V. Schmidt,Queues and Point Processes (Wiley, Chichester, 1982). · Zbl 0505.60058
[33] S.W. Fuhrmann and R.B. Cooper, Stochastic decompositions in theM/G/1 queue with generalized vacations, Oper. Res. 33 (1985) 1117-1129. · Zbl 0585.90033 · doi:10.1287/opre.33.5.1117
[34] P.W. Glynn and W. Whitt, Extensions of the queueing relationsL-?W, Oper. Res. 37 (1989) 634-644. · Zbl 0677.90032 · doi:10.1287/opre.37.4.634
[35] B.V. Gnedenko and I.N. Kovalenko,Introduction to Queueing Theory, Israel Program for Scientific Translations (translated from Russian) (1968). · Zbl 0186.24502
[36] J. Grandell,Aspects of Risk Theory (Springer, Berlin, 1991). · Zbl 0717.62100
[37] P.R. Halmos,Measure Theory (Van Nostrand, New York, 1950).
[38] W. Henderson, Insensitivity and reversed Markov processes, Adv. Appl. Prob. 15 (1983) 752-768. · Zbl 0529.60092 · doi:10.2307/1427322
[39] D.P. Heyman and M.J. Sobel,Stochastic Models in Operations Research, Vol. I (MacGraw-Hill, New York, 1982). · Zbl 0503.90031
[40] D.P. Heyman and S. Stidham, Jr., The relation between customer and time averages in queues, Oper. Res. 28 (1980) 983-994. · Zbl 0439.60089 · doi:10.1287/opre.28.4.983
[41] J. Jacod,Calcul Stochastique et Problémes de Martingales, Lecture Notes in Math. 714 (Springer, Heidelberg, 1979). · Zbl 0414.60053
[42] M. Jankiewicz and T. Rolski, Piece-wise Markov processes on a general state space, Zastos. Math. 15 (1978) 421-436. · Zbl 0376.60093
[43] O. Kallenberg,Random Measures (Akademie-Verlag, Berlin, 1983).
[44] A.F. Karr,Point Processes and their Statistical Inference (Marcel Dekker, New York, 1986). · Zbl 0601.62120
[45] F.P. Kelly,Reversibility and Stochastic Networks (Wiley, New York, 1979).
[46] O. Kella and W. Whitt, Queues with server vacations and Levy processes with secondary jump input, Ann. Appl. Prob. 1 (1991) 104-117. · Zbl 0725.60079 · doi:10.1214/aoap/1177005983
[47] O. Kella and W. Whitt, Useful martingales for stochastic storage processes with Levy input, J. Appl. Prob. 29 (1992) 396-403. · Zbl 0761.60065 · doi:10.2307/3214576
[48] I. Kino and M. Miyazawa, The stationary work in system of a G/G/1 gradual input queue, J. Appl. Prob. 30 (1993) 207-222. · Zbl 0768.60087 · doi:10.2307/3214633
[49] D. König and M. Miyazawa, Relationships and decomposition in the delayed Bernoulli feedback queueing system, J. Appl. Prob. 25 (1988) 169-183. · Zbl 0642.60079 · doi:10.2307/3214243
[50] D. König, T. Rolski, V. Schmidt and D. Stoyan, Stochastic processes with embedded marked point processes (PMP) and their application in queuing, Math. Operationsforsch. Statist. Ser. Optimization 9 (1978) 125-141. · Zbl 0393.60047
[51] D. König and V. Schmidt, Imbedded and non-imbedded stationary characteristics of queueing systems with varying service rate and point processes, J. Appl. Prob. 17 (1980) 753-767. · Zbl 0435.60094 · doi:10.2307/3212969
[52] D. König and V. Schmidt, Stochastic inequalities between customer-stationary and time-stationary characteristics of queueing systems with point processes, J. Appl. Prob. 17 (1980) 768-777. · Zbl 0435.60095 · doi:10.2307/3212970
[53] D. König and V. Schmidt, Stationary queue-length characteristics in queues with delayed feedback, J. Appl. Prob. 22 (1985) 394-407. · Zbl 0564.60090 · doi:10.2307/3213782
[54] I. Kopocinska and B. Kopocinska, Steady state distributions of queue length in theGI/G/s queue, Zastos. Math. 16 (1977) 39-46. · Zbl 0375.60108
[55] M. Krakowski, Conservation methods in queueing theory, Rev. Franc. Automat. Inform. Rech. Oper. 7 (1973) 63-83. · Zbl 0258.60069
[56] M. Krakowski, Arrival and departure processes in queues, Pollaczeck-Khintchine formulas for bulk arrivals and bounded systems, Rev. Franc. Automat. Inform. Rech. Oper. 7 (1974) 45-56. · Zbl 0276.60090
[57] A. Kuczura, Piecewise Markov processes, SIAM J. Appl. Math. 24 (1973) 169-181. · Zbl 0251.60051 · doi:10.1137/0124018
[58] A.J. Lemoine, On two stationary distributions for the stable GI/G/1 queue, J. Appl. Prob. 11 (1974)849-852. · Zbl 0302.60059 · doi:10.2307/3212570
[59] R.S. Lipster and A.N. Shiryaev,Statistics of Random Processes II. Applications, transl. by A.B. Aries (Springer, New York, 1978).
[60] J.D.C. Little, A proof for the queueing formulaL=?W, Oper. Res. 9 (1961) 383-387. · Zbl 0108.14803 · doi:10.1287/opre.9.3.383
[61] R.M. Loynes, The stability of a queue with non-independent inter-arrival and service times, Proc. Camb. Phil. Soc. 58 (1962) 497-520. · Zbl 0203.22303 · doi:10.1017/S0305004100036781
[62] D.M. Lucantoni, K.S. Meier-Hellstern and M.F. Neuts, A single server queue with server vacations and a class of non-renewal arrival processes, Adv. Appl. Prob. 22 (1990) 676-705. · Zbl 0709.60094 · doi:10.2307/1427464
[63] A. Makowski, B. Melamed and W. Whitt, On averages seen by arrivals in discrete time, in:Proc. 28th IEEE Conf. on Decision and Control, Tampa, Florida (1989).
[64] R. Mazumdar, V. Badrinath, F. Guillemin and C. Rosenberg, Pathwise rate conservation and applications, Stochastic Proc. and their Appl. 47 (1993) 119-130. · Zbl 0786.60061 · doi:10.1016/0304-4149(93)90098-O
[65] R. Mazumdar, R. Kannurpatti and C. Rosenberg, On rate conservation law for non-stationary processes, J. Appl. Prob. 28 (1990) 762-770. · Zbl 0745.60044 · doi:10.2307/3214679
[66] J. Mecke, Stationäre zufällige Masse auf lokalkompakten Abelschen Gruppen, Z. Wahrscheinlich, verw. Geb. 9 (1967) 36-58. · Zbl 0164.46601 · doi:10.1007/BF00535466
[67] B. Melamed and W. Whitt, On arrivals that see time averages, Oper. Res. 38 (1990) 156-172. · Zbl 0702.60093 · doi:10.1287/opre.38.1.156
[68] B. Melamed and W. Whitt, On arrivals that see time averages: A martingale approach, J. Appl. Prob. 27 (1990) 376-384. · Zbl 0713.60098 · doi:10.2307/3214656
[69] M. Miyazawa, Stochastic order relations amongGI/GI/1 queues with a common traffic intensity, J. Oper. Res. Japan 19 (1976) 193-208. · Zbl 0402.60095
[70] M. Miyazawa, Time and customer processes in queues with stationary inputs, J. Appl. Prob. 14 (1977) 349-357. · Zbl 0365.60106 · doi:10.2307/3213005
[71] M. Miyazawa, A formal approach to queueing processes in the steady state and their applications, J. Appl. Prob. 16 (1979) 332-346. · Zbl 0403.60089 · doi:10.2307/3212901
[72] M. Miyazawa, Note on Palm measures in the intensity conservation law and inversion formula in PMP and their applications, Math. Operationsforsch. Statist. Ser. Optimization 12 (1981) 281-293. · Zbl 0511.60044
[73] M. Miyazawa, The derivation of invariance relations in complex queueing systems with stationary inputs, Adv. Appl. Prob. 15 (1983) 874-885. · Zbl 0535.60086 · doi:10.2307/1427329
[74] M. Miyazawa, The intensity conservation law for queues with randomly changed service reate, J. Appl. Prob. 22 (1985) 408-418. · Zbl 0564.60091 · doi:10.2307/3213783
[75] M. Miyazawa, Approximation of the queue-length distribution of anM/GI/s queue by the basic equations, J. Appl. Prob. 23 (1986) 443-458. · Zbl 0599.60084 · doi:10.2307/3214186
[76] M. Miyazawa, A generalized Pollaczek-Khinchine formula for theGI/GI/1/k queue and its application to approximation, Stochastic Models 3 (1987) 53-65. · Zbl 0619.60092 · doi:10.1080/15326348708807046
[77] M. Miyazawa, Comparison of the loss probability ofGI x/GI/1/k queues with a common traffic intensity, J. Oper. Res. Soc. Japan 32 (1989) 505-516. · Zbl 0705.60087
[78] M. Miyazawa, Rate conservation law with multiplicity and its applications to queues, Res. rep., Science University of Tokyo (1991).
[79] M. Miyazawa, The characterization of the stationary distributions of the supplemented self-clocking jump process, Math. Oper. Res. 16 (1991) 547-565. · Zbl 0742.60101 · doi:10.1287/moor.16.3.547
[80] M. Miyazawa, Palm distribution and time-dependent RCL on stationary increment scheme and their applications, Res. rep., Science University of Tokyo (1992).
[81] M. Miyazawa, On the system queue length distributions of LCFS-P queues wtih arbitrary acceptance and restarting policies, J. Appl. Prob. 29 (1992) 430-440. · Zbl 0754.60115 · doi:10.2307/3214579
[82] M. Miyazawa, Decomposition formulas for single server queues with server vacations -A unified approach by the rate conservation law, to appear in Stochastic Models 10, No. 2 (1994). · Zbl 0793.60100
[83] M. Miyazawa, Note on generalizations of Mecke’s formula and extensions ofH=?G, submitted for publication (1993).
[84] M. Miyazawa, Insensitivity and product form decomposability of reallocatable GSMP, Adv. Appl. Prob. 25 (1993) 415-437. · Zbl 0772.60079 · doi:10.2307/1427660
[85] M. Miyazawa, Palm calculus for a process with random measure and its applications to fluid queues and risk processes, submitted for publication (1993).
[86] M. Miyazawa, Time-dependent rate conservation law for a process defined with a stationary marked point process and its applications, to appear in J. Appl. Prob. 31 (1994). · Zbl 0795.60033
[87] M. Miyazawa and V. Schmidt, On Ladder height distributions of general risk processes, to appear in Ann. Appl. Prob. 4 (1994).
[88] M. Miyazawa and Y. Takahashi, Rate conservation principle for discrete-time queues, Queueing Systems 12 (1992) 215-230. · Zbl 0811.60078 · doi:10.1007/BF01158799
[89] M. Miyazawa and R.W. Wolff, Further results on ASTA for general stationary processes and related problems, J. Appl. Prob. 28 (1990) 792-804. · Zbl 0726.60048 · doi:10.2307/3214823
[90] M. Miyazawa and G. Yamazaki, The basic equations for a supplemented GSMP and its applications to queues, J. Appl. Prob. 25 (1988) 565-578. · Zbl 0662.60079 · doi:10.2307/3213985
[91] M. Miyazawa and G. Yamazaki, Relationships in stationary jump processes with countable state space and their applications, Stochastic Proc. and their Appl. 43 (1992) 177-189. · Zbl 0757.60097 · doi:10.1016/0304-4149(92)90058-X
[92] F. Papangelou, Integrability of expected increments of point processes and a related random change of scale, Trans. Am. Math. Soc. 165 (1972) 483-506. · Zbl 0236.60036 · doi:10.1090/S0002-9947-1972-0314102-9
[93] P. Protter,Stochastic Integration and Differential Equations (Springer, New York, 1990). · Zbl 0694.60047
[94] T. Rolski, A rate-conservative principles for stationary piece-wise Markov processes, Adv. Appl. Prob. 10 (1978) 392-410. · Zbl 0376.60092 · doi:10.2307/1426942
[95] T. Rolski,Stationary Random Processes Associated with Point Processes, Lecture Notes in Statistics 5 (Springer, New York, 1981). · Zbl 0467.60002
[96] T. Rolski and S. Stidham, Jr., Continuous versions of the queueing formulasL=?W andH=?G, Oper. Res. Lett. 2 (1983) 211-215. · Zbl 0527.60086 · doi:10.1016/0167-6377(83)90027-5
[97] C. Ryll-Nardzewski, Remarks on processes of calles,Proc. 4th Berkeley Symp. on Math. Stat. and Prob., Vol. 2 (1961) pp. 455-465.
[98] M. Rubinovitch and J.W. Cohen, Level crossings and stationary distributions for general dams, J. Appl. Prob. 17 (1980) 218-226. · Zbl 0437.60078 · doi:10.2307/3212938
[99] H. Sakasegawa and R.W. Wolff, The equality of the virtual delay and attained waiting time distributions, Adv. Appl. Prob. 22 (1990) 257-259. · Zbl 0719.60105 · doi:10.2307/1427611
[100] R. Schassberger, Insensitivity of steady-state distributions of generalized semi-Markov processes with speeds, Adv. Appl. Prob. 10 (1978) 836-851. · Zbl 0396.60085 · doi:10.2307/1426662
[101] B. Sengupta, An invariance relationship for the G/G/1 queue, Adv. Appl. Prob. 21 (1989) 956-957. · Zbl 0758.60103 · doi:10.2307/1427783
[102] B.A. Sevastyanov, An ergodic theorem for Markov processes and its application to telephone systems with refusals, Theor. Prob. Appl. 2 (1957) 104-112. · doi:10.1137/1102005
[103] J.G. Shanthikumar and M.J. Chandra, Application of level crossing analysis to discrete state processes in queueing systems, Nav. Res. Logistics Q. 29 (1982) 593-608. · Zbl 0543.60094 · doi:10.1002/nav.3800290407
[104] J.G. Shanthikumar and U. Sumita, On G/G/1 queues with LIFO-P service discipline, J. Oper. Res. Soc. Japan 29 (1986) 220-231. · Zbl 0609.60096
[105] K. Sigman, A note on a sample-path rate conservation law and its relationship withH=?G. Adv. Appl. Prob. 23 (1991) 662-665. · Zbl 0728.60089 · doi:10.2307/1427629
[106] S. Stidham Jr.,L= ?W: A discounted analogue and a new proof, Oper. Res. 20 (1972) 1115-1126. · Zbl 0248.60071 · doi:10.1287/opre.20.6.1115
[107] S. Stidham Jr., Regenerative processes in the theory of queues with applications to alternating-priority queue, Adv. Appl. Prob. 4 (1972) 542-577. · Zbl 0251.60059 · doi:10.2307/1425993
[108] S. Stidham Jr., A last wordonL=?W, Oper.Res. 22 (1974) 417-421. · Zbl 0274.60080 · doi:10.1287/opre.22.2.417
[109] S. Stidham Jr., On the relation between time and averages and customer averages in stationary random marked point process, NCSU-IE Tech. Rep. (1979).
[110] S. Stidham Jr., Sample-path analysis of queues,Applied Probability and Computer Science: The interface, eds. R. Disney and T. Ott (1982) pp. 41-70.
[111] S. Stidham Jr., A note on a sample-path approach to Palm probabilities, preprint (1992).
[112] S. Stidham Jr. and M. El-Taha, Sample-path analysis of processes with imbedded point processes, Queueing Systems 5 (1989) 131-165. · Zbl 0682.60083 · doi:10.1007/BF01149190
[113] S. Stidham Jr. and M. El-Taha, A note on sample-path stability conditions for input-output processes, submitted for publication (1992).
[114] L. Takacs,Introduction to the Theory of Queues (Oxford University Press, New York, 1962). · Zbl 0118.13503
[115] H. Takagi, Time-dependent analysis ofM/GI/1 vacation models with exhaustive service, Queueing Systems 6 (1990) 369-390. · Zbl 0696.60091 · doi:10.1007/BF02411484
[116] Y. Takahashi and O. Hashida, Delay analysis of discrete-time priority queue with structured inputs, Queueing Systems 8 (1991) 149-164. · Zbl 0727.60111 · doi:10.1007/BF02412247
[117] T. Takine and T. Hasegawa, A generalization of the decomposition property in theM/G/1 queue with server vacations, Oper. Res. Lett. 12 (1992) 97-99. · Zbl 0755.60087 · doi:10.1016/0167-6377(92)90070-J
[118] P.G. Taylor, Aspects of insensitivity in stochastic processes, Ph.D. thesis, University of Adelaide, South Australia (1987).
[119] W. Whitt, A review ofL=?W and extensions, Queueing Systems 9 (1991) 235-268. · Zbl 0727.60112 · doi:10.1007/BF01158466
[120] W. Whitt,H=?G and the Palm transform, Adv. Appl. Prob. 24 (1992) 755-758. · Zbl 0755.60089 · doi:10.2307/1427489
[121] P. Whittle,Probability via Expectations, 3rd ed. (Springer, New York, 1992). · Zbl 0755.60001
[122] R.W. Wolff, Sample path derivations of the excess, age and spread distributions, J. Appl. Prob. 13 (1988) 432-436. · Zbl 0641.60106 · doi:10.2307/3214453
[123] R.W. Wolff,Stochastic Modeling and The Theory of Queues (Prentice Hall, New Jersey, 1989). · Zbl 0701.60083
[124] M.A. Wortman and R.L. Disney, On the relationship between stationary and Palm moments of backlog in the G/G/1 priority queue, in:Queueing and Related Models, eds. U.N. Bhat and I.V. Basawa (Oxford University Press, 1992) pp. 161-174. · Zbl 0784.60090
[125] G. Yamazaki, Invariance relations in single server queues with LCFS service discipline, Ann. Inst. of Statistical Mathematics 42 (1990) 475-488. · Zbl 0719.60109 · doi:10.1007/BF00049303
[126] G. Yamazaki, H. Sakasegawa and J.G. Shanthikumar, A conservation law for single-server queues andits applications, J. Appl. Prob. 28 (1991) 198-209. · Zbl 0721.60108 · doi:10.2307/3214750
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.