State-dependent stochastic networks. I: Approximation and applications with continuous diffusion limits. (English) Zbl 0945.60025
In this lengthy and comprehensive article, the authors study the transient evolution of state-dependent open \((\text{M}_{\xi}/\text{M}_{\xi}/1)^k\) queueing networks. These are exponential networks in which the arrival and service rates, as well as routing probabilities, depend on the state, the vector of queue lengths. For properly normalised queue-length processes, they derive functional laws of large numbers (FLLN) and functional central limit theorems (FCLTs). They develop new tools to establish convergence, existence and uniqueness of the limits. Their approach to reflection problems with nonconstant directions of reflections is based upon P. Dupuis and H. Ishii [Ann. Probab. 21, No. 1, 554-580 (1993; Zbl 0787.60099)].
The fluid limit is the unique solution to a multidimensional autonomous ordinary differential equation with state-dependent reflection. The proof of FLLN is based on Lipschitz property of time-dependent reflection operator. The weak limit given in FCLT is the unique strong solution to a stochastic differential equation with time-dependent reflection. These results unify and generalize existing approximation techniques. This state-dependent model provides a flexible framework for accomodating a wide variety of phenomena in queueing networks. The results obtained support the design, analysis and optimization of various manufacturing service, communication and other systems.
In particular, this paper extends the results of the authors [in: Stochastic networks. IMA Vol. Math. Appl. 71, 239-282 (1995; Zbl 0829.60081)], and W. A. Massey and W. Whitt [Queueing Syst. 13, No. 1-3, 183-250 (1993; Zbl 0778.60068)]. The article contains 85 useful references.
The fluid limit is the unique solution to a multidimensional autonomous ordinary differential equation with state-dependent reflection. The proof of FLLN is based on Lipschitz property of time-dependent reflection operator. The weak limit given in FCLT is the unique strong solution to a stochastic differential equation with time-dependent reflection. These results unify and generalize existing approximation techniques. This state-dependent model provides a flexible framework for accomodating a wide variety of phenomena in queueing networks. The results obtained support the design, analysis and optimization of various manufacturing service, communication and other systems.
In particular, this paper extends the results of the authors [in: Stochastic networks. IMA Vol. Math. Appl. 71, 239-282 (1995; Zbl 0829.60081)], and W. A. Massey and W. Whitt [Queueing Syst. 13, No. 1-3, 183-250 (1993; Zbl 0778.60068)]. The article contains 85 useful references.
Reviewer: P.R.Parthasarathy (Madras)
MSC:
| 60F17 | Functional limit theorems; invariance principles |
| 60K25 | Queueing theory (aspects of probability theory) |
| 90B22 | Queues and service in operations research |
| 60G17 | Sample path properties |
| 60J70 | Applications of Brownian motions and diffusion theory (population genetics, absorption problems, etc.) |
| 60K30 | Applications of queueing theory (congestion, allocation, storage, traffic, etc.) |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 90B10 | Deterministic network models in operations research |
| 90B30 | Production models |
| 90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |
References:
| [1] | ABATE, J. and WHITT, W. 1987. Transient behavior of regulated Brownian motion, I: starting at the origin. Adv. in Appl. Probab. 19 560 598. JSTOR: · Zbl 0628.60083 · doi:10.2307/1427408 |
| [2] | ABATE, J. and WHITT, W. 1987. Transient behavior of regulated Brownian motion, II: non-zero initial condition. Adv. in Appl. Probab. 19 599 631. JSTOR: · Zbl 0628.60084 · doi:10.2307/1427409 |
| [3] | ANICK, D., MITRA, D. and SONDHI, M. M. 1982. Stochastic theory of a data-handling sy stem with multiple sources. Bell Sy stem Tech. J. 61 1871 1894. |
| [4] | ANISIMOV, V. V. 1997. Switching processes: asy mptotic theory and applications. In New Z. Trends in Probability and Statistics A. N. Shiry ayev et al., eds.. · Zbl 0872.60073 |
| [5] | ANULOVA, S. V. 1990. Functional limit theorems for network of queues. In Proc. IFAC Congress, Abstract. · Zbl 0727.60033 |
| [6] | AUBIN, J. P. and CELLINA, A. 1984. Differential Inclusions. Springer, New York. · Zbl 0538.34007 |
| [7] | BARBOUR, A. D. 1974. On a functional central limit theorems for Markov population processes. Adv. in Appl. Probab. 6 21 39. JSTOR: · Zbl 0279.60074 · doi:10.2307/1426205 |
| [8] | BERMAN, A. and PLEMMONS, R. J. 1979. Nonnegative Matrices in the Mathematical Sciences. Academic Press, New York. · Zbl 0484.15016 |
| [9] | BILLINGSLEY, P. 1968. Convergence of Probability Measures. Wiley, New York. · Zbl 0172.21201 |
| [10] | BOUCHERIE, R. J. and VAN DIJK, N. M. 1993. A generalization of Norton’s theorem for queueing networks. Queueing Sy stems Theory Appl. 13 251 289. · Zbl 0790.60074 · doi:10.1007/BF01158934 |
| [11] | BREMAUD, P. 1981. Point Processes and Queues: Martingale Dy namics. Springer, Berlin. · Zbl 0478.60004 |
| [12] | BUZACOTT, J. A. and YAO, D. D. 1986. On queueing network models of flexible manufacturing sy stems. Queueing Sy stems Theory Appl. 1 5 27. · Zbl 0649.90061 · doi:10.1007/BF01149326 |
| [13] | CHEN, H. 1990. Generalized regulated mapping, fluid and diffusion limits. Unpublished notes. |
| [14] | CHEN, H. and MANDELBAUM, A. 1991. Discrete flow networks: bottleneck analysis and fluid approximations. Math. Oper. Res. 16 408 446. JSTOR: · Zbl 0735.60095 · doi:10.1287/moor.16.2.408 |
| [15] | CHEN, H. and MANDELBAUM, A. 1991. Discrete flow networks: diffusion approximations and bottlenecks. Ann. Probab. 19 1463 1519. · Zbl 0757.60094 · doi:10.1214/aop/1176990220 |
| [16] | CLARKE, F. H. 1983. Optimization and Nonsmooth Analy sis. Wiley, New York. |
| [17] | COFFMAN, E. G., JR., PUHALSKII, A. A., REIMAN, M. I. and WRIGHT, P. 1994. Processor shared buffers with reneging. Performance Evaluation 19 25 46. · Zbl 0818.68029 · doi:10.1016/0166-5316(94)90053-1 |
| [18] | COFFMAN, E. G., JR., PUHALSKII, A. A. and REIMAN, M. I. 1991. Storage limited queues in heavy traffic. Probab. Engrg. Inform. Sci. 5 499 522. · Zbl 1134.60392 · doi:10.1017/S0269964800002254 |
| [19] | COTTLE, R. W., PANG, J. S. and STONE, R. E. 1992. The Linear Complementarity Problem. Academic Press, New York. · Zbl 0757.90078 |
| [20] | DAVIS, G. A. and NIHAN, N. L. 1993. Large population approximations of a general stochastic traffic assignment model. Oper. Res. 41 169 178. · Zbl 0771.90035 · doi:10.1287/opre.41.1.169 |
| [21] | DUPUIS, P. and ISHII, H. 1990. On oblique derivative problems for fully nonlinear secondorder elliptic partial differential equations on nonsmooth domains. Nonlinear Anal. Z. 15 12 1123 1138. · Zbl 0736.35044 · doi:10.1016/0362-546X(90)90048-L |
| [22] | DUPUIS, P. and ISHII, H. 1991. On Lipschitz continuity of the solution mapping to the Skorokhod problem, with applications. Stochastics Stochastics Rep. 35 31 62. · Zbl 0721.60062 |
| [23] | DUPUIS, P. and ISHII, H. 1993. SDEs with oblique reflection on nonsmooth domains. Ann. Probab. 21 554 580. · Zbl 0787.60099 · doi:10.1214/aop/1176989415 |
| [24] | ELLIOTT, R. J. 1982. Stochastic Calculus and Applications. Springer, New York. · Zbl 0503.60062 |
| [25] | ETHIER, S. N. and KURTZ, T. G. 1986. Markov Process: Characterization and Convergence. Wiley, New York. · Zbl 0592.60049 |
| [26] | FILIPPOV, A. F. 1988. Differential Equations with Discontinuous Right Hand Sides. Kluwer Academic, Dordrecht. · Zbl 0664.34001 |
| [27] | GIORNO, V., NEGRI, C. and NOBILE, A. 1985. A solvable model for a finite-capacity sy stem. J. Appl. Probab. 22 903 911. JSTOR: · Zbl 0576.60089 · doi:10.2307/3213957 |
| [28] | HALE, J. 1969. Ordinary Differential Equations. Wiley, New York. · Zbl 0186.40901 |
| [29] | HALFIN, S. and WHITT, W. 1981. Heavy-traffic limits theorem for queues with many exponential servers. Oper. Res. 29 567 588. JSTOR: · Zbl 0455.60079 · doi:10.1287/opre.29.3.567 |
| [30] | HARRISON, J. M. 1985. Brownian Motion and Stochastic Flow Sy stems. Wiley, New York. · Zbl 0659.60112 |
| [31] | HARRISON, J. M. and REIMAN, M. I. 1981. Reflected brownian motion on an orthant. Ann. Z. Probab. 9 2 302 308. · Zbl 0462.60073 · doi:10.1214/aop/1176994471 |
| [32] | HARRISON, J. M. and SHEPP, L. A. 1984. A tandem storage sy stem and its diffusion limit. Stochastic Process. Appl. 16 257 274. · Zbl 0526.60091 · doi:10.1016/0304-4149(84)90024-3 |
| [33] | HEFFES, H. 1982. Moment formulae for a class of mixed multi-job-ty pe queueing networks. Bell Sy stem Tech. J. 61 709 745. · Zbl 0479.68043 |
| [34] | IGLEHART, D. L. 1965. Limit diffusion approximations for the many-server queue and repairman problem. J. Appl. Probab. 2 429 441. · Zbl 0216.47204 · doi:10.2307/3212203 |
| [35] | IGLEHART, D. L. and LEMOINE, A. J. 1973. Approximations for the repairman problem with two repair facilities, I: no spares. Adv. in Appl. Probab. 5 595 613. JSTOR: · Zbl 0275.60100 · doi:10.2307/1425836 |
| [36] | ISHAM, V. 1993. Stochastic models for epidemics with special reference to AIDS. Ann. Z. Appl. Probab. 3 1 1 27. · Zbl 0778.92019 · doi:10.1214/aoap/1177005505 |
| [37] | JACKSON, R. J. 1963. Jobshop-like queueing sy stems. Management Sci. 10 131 142. |
| [38] | JACOD, J. and SHIRy AYEV, A. N. 1987. Limit Theorems for Stochastic Processes. Springer, Berlin. |
| [39] | JENNINGS, O. B., MANDELBAUM, A., MASSEY, W. A. and WHITT, W. 1996. Server staffing to meet time varying demand. Management Science 42 1383 1394. · Zbl 0880.90052 · doi:10.1287/mnsc.42.10.1383 |
| [40] | KARATZAS, I. and SHREVE, S. E. 1988. Brownian Motion and Stochastic Calculus. Springer, New York. · Zbl 0638.60065 |
| [41] | KASPI, H. and MANDELBAUM, A. 1992. Regenerative closed queueing networks. Stochastics Stochastics Rep. 39 239 258. · Zbl 0767.60094 · doi:10.1080/17442509208833777 |
| [42] | KLOEDEN, P. and PLATEN, E. 1992. Numerical Solutions of Stochastic Differential Equations. Springer, Berlin. · Zbl 0925.65261 |
| [43] | KNESSL, C. and MORRISON, J. A. 1991. Heavy-traffic analysis of a data-handling sy stem with many sources. SIAM J. Appl. Math. 51 187 213. JSTOR: · Zbl 0716.60115 · doi:10.1137/0151012 |
| [44] | KOGAN, Y. A. and LIPTSER, R. S. 1993. Limit non-stationary behavior of large closed queueing networks with bottlenecks. Queueing Sy stems Theory Appl. 14 33 55. · Zbl 0780.60087 · doi:10.1007/BF01153525 |
| [45] | KOGAN, Y. A., LIPTSER, R. S. and SMORODINSKII, A. V. 1986. Gaussian diffusion approximation of closed Markov models of computer networks. Problems Inform. Transmission 22 38 51. · Zbl 0619.60043 |
| [46] | KRICHAGINA, E. V. 1992. Asy mptotic analysis of queueing networks martingale approach. Stochastics Stochastics Rep. 40 43 76. · Zbl 0762.60082 · doi:10.1080/17442509208833781 |
| [47] | KRZESINSKI, A. E. 1987. Multiclass queueing networks with state-dependent routing. Performance Evaluation 7 125 143. · Zbl 0619.90023 · doi:10.1016/0166-5316(87)90027-7 |
| [48] | KURTZ, T. G. 1970. Solutions of ordinary differential equations as limits of pure jump Markov processes. J. Appl. Probab. 7 49 58. JSTOR: · Zbl 0191.47301 · doi:10.2307/3212147 |
| [49] | KURTZ, T. G. 1971. Limit theorems for sequences of jump Markov processes approximating ordinary differential processes. J. Appl. Probab. 8 344 356. JSTOR: · Zbl 0219.60060 · doi:10.2307/3211904 |
| [50] | KURTZ, T. G. 1978. Strong approximation theorems for density dependent Markov chains. Stochastic Process. Appl. 6 223 240. · Zbl 0373.60085 · doi:10.1016/0304-4149(78)90020-0 |
| [51] | KURTZ, T. G. 1980. Representation of Markov processes as multiparameter time changes. Ann. Probab. 8 682 715. · Zbl 0442.60072 · doi:10.1214/aop/1176994660 |
| [52] | KUSHNER, H. J. and MARTINS, L. F. 1993. Heavy traffic analysis of a data transmission sy stems with many independent sources. SIAM J. Appl. Math. 53 1095 1122. JSTOR: · Zbl 0780.60093 · doi:10.1137/0153055 |
| [53] | LIPTSER, R. S. and SHIRy AYEV, A. N. 1989. Theory of Martingales. Kluwer Academic, Dordrecht. · Zbl 0728.60048 |
| [54] | MANDELBAUM, A. 1989. The dy namic complementarity problem. |
| [55] | MANDELBAUM, A. and MASSEY, W. A. 1995. Strong approximations for time-dependent queues. Math. Oper. Res. 20 33 64. JSTOR: · Zbl 0834.60096 · doi:10.1287/moor.20.1.33 |
| [56] | MANDELBAUM, A., MASSEY, W. A. and PATS, G. 1997. Approximations for time-dependent networks. Unpublished manuscript. |
| [57] | MANDELBAUM, A., MASSEY, W. A. and PATS, G. 1995. Time-dependent reflection problem. Technical Report, Technion. |
| [58] | MANDELBAUM, A., MASSEY, W. A. and REIMAN, M. I. 1997. Strong approximations for Markovian service networks. · Zbl 0911.90167 · doi:10.1023/A:1019112920622 |
| [59] | MANDELBAUM, A. and PATS, G. 1995. State-dependent queues: approximations and applicaZ tions. In IMA Volumes in Mathematics and Its Applications F. Kelly and R. J.. Williams, eds. 71 239 282. Springer, Berlin. · Zbl 0829.60081 |
| [60] | MASSEY, W. A. and WHITT, W. 1993. Networks of infinite-server queues with non-stationary Poisson input. Queueing Sy stems Theory Appl. 13 183 250. · Zbl 0778.60068 · doi:10.1007/BF01158933 |
| [61] | MITRA, D. 1988. Stochastic theory of a fluid model of producers and consumers coupled by a buffer. Adv. in Appl. Probab. 20 646 676. JSTOR: · Zbl 0656.60079 · doi:10.2307/1427040 |
| [62] | MITRA, D. and MCKENNA, J. 1986. Asy mptotic expansions for closed Markovian networks with state-dependent service rates. J. Assoc. Comput. Mach. 33 568 592. · Zbl 0647.60097 · doi:10.1145/5925.5935 |
| [63] | MITRANI, I. and PUHALSKII, A. A. 1993. Limiting results for multiprocessor sy stems with breakdowns and repairs. Queueing Sy stems Theory Appl. 14 293 311. · Zbl 0802.68010 · doi:10.1007/BF01158870 |
| [64] | PATS, G. 1997. State-dependent queueing networks. Part II: approximations with discontinuous diffusion limits. Unpublished manuscript. |
| [65] | PATS, G. 1994. State-dependent queueing networks: approximations and applications. Ph.D. thesis, Faculty of Industrial Engineering and Management, Technion. |
| [66] | PEGDEN, C., SHANNON, R. and SADOWSKI, R. 1995. Introduction to Simulation Using SIMAN, 2nd ed. McGraw-Hill, New York. |
| [67] | POMAREDE, J. L. 1976. A unified approach via graphs to Skorokhod’s topologies on the function space. Ph.D. dissertation, Dept. Statistics, Yale Univ. |
| [68] | PRISGROVE, L. A. 1987. Closed queueing networks with multiple servers: transient and steady-state approximations. Technical Report 20, Dept. Operations Research, Stanford Univ. |
| [69] | PROTTER, P. 1990. Stochastic Integration and Differential Equations. Springer, Berlin. · Zbl 0694.60047 |
| [70] | SERFOZO, R. F. 1989. Markovian network processes: congestion-dependent routing and processing. Queueing Sy stems Theory Appl. 5 5 36. · Zbl 0714.60082 · doi:10.1007/BF01149184 |
| [71] | SERFOZO, R. F. 1993. Queueing networks with dependent nodes and concurrent movements. Queueing Sy stems Theory Appl. 13 143 182. · Zbl 0778.60065 · doi:10.1007/BF01158932 |
| [72] | SLOMINSKI, L. 1989. Stability of strong solutions of stochastic differential equations. Stochastic Process. Appl. 31 173 202. · Zbl 0673.60065 · doi:10.1016/0304-4149(89)90087-2 |
| [73] | STROOK, D. W. and VARADHAN, S. R. S. 1979. Multidimensional Diffusion Processes. Springer, Berlin. · Zbl 0426.60069 |
| [74] | Sy SKI, R. 1986. Introduction to Congestion Theory in Telephone Sy stems, 2nd ed. NorthHolland, Amsterdam. |
| [75] | TOWSLEY, D. F. 1980. Queueing network models with state-dependent routing. J. Assoc. Comput. Mach. 27 323 337. · Zbl 0441.68037 · doi:10.1145/322186.322196 |
| [76] | VANDERGRAFT, A. J. 1983. A fluid model of networks of queues. Management Sci. 29 1198 1208. · Zbl 0523.60087 · doi:10.1287/mnsc.29.10.1198 |
| [77] | WHITE, J. A., SCHMIDT, J. W. and BENNETT, G. K. 1974. Analy sis of Queueing Sy stems. Academic Press, New York. |
| [78] | WHITT, W. 1984. Open and closed models for networks of queues. Bell Sy stem Tech. J. 63 1911 1979. · Zbl 0594.90032 |
| [79] | WHITT, W. 1992. Understanding the efficiency of multi-server service sy stems. Management Sci. 38 708 723. · Zbl 0825.90409 · doi:10.1287/mnsc.38.5.708 |
| [80] | WORTHINGTON, D. J. 1987. Queueing models for hospital waiting lists. J. Oper. Res. Soc. 38 413 422. |
| [81] | YAMADA, K. 1986. Multi-dimensional Bessel processes as heavy traffic limits of certain tandem queues. Stochastic Process. Appl. 23 35 56. · Zbl 0613.60086 · doi:10.1016/0304-4149(86)90015-3 |
| [82] | YAMADA, K. 1993. Diffusion approximations for open state-dependent queueing networks under heavy traffic situation. Technical Report, Inst. Information Science and Electronics, Univ. Tsukuba, Japan. |
| [83] | YAO, D. D. and BUZACOTT, J. A. 1985. Modelling of a class of state-dependent routing in flexible manufacturing sy stems. Ann. Oper. Res. 3 153 167. |
| [84] | YAO, D. D. and BUZACOTT, J. A. 1986. Models of flexible manufacturing sy stems with limited local buffers. International Journal of Production Research 24 107 117. · Zbl 0583.90046 |
| [85] | TECHNION CITY, HAIFA 32000 ISRAEL E-MAIL: avim@tx.technion.ac.il gennadi@ie.technion.ac.il |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
