×

On the stability of a queueing system with uncountably branching fluid limits. (English. Russian original) Zbl 1101.90019

Probl. Inf. Transm. 41, No. 3, 254-279 (2005); translation from Probl. Peredachi Inf. 2005, No. 3, 76-104 (2005).
The paper considers a queueing system containing two stations and two servers. Station 1 receives an input stream of customers with rate \(\lambda _1<1\), Station 2 with rate \(\lambda _2>1\); both service rates are equal to 1. Having completed the service customers leave the system. The second server is always located at Station 2. The first server assists it from time to time - along with its own service at the first station.
There are three possible states of the system. Neutral: each server works at its “own” station. The first is operating as an FCFS single server queue; the second station contains two buffers, the server serves the customers accumulated in one of them, while new customers are accumulated in the second one. When the first buffer becomes empty, they change place. State of readiness: the system operates as in neutral state, but the first customer is ready to come to the second station. The state of assistance: both servers operate at the second station taking customers from the same buffer. The system changes its states in the following order: neutral, readiness, assistance, then neutral again, etc. according to a given algorithm.
There are two variants of stochastic assumptions: (SA1) the interarrival times of first stream are i.i.d. with mean \(1/\lambda _1\), for the second one Poisson with parameter \(\lambda _2\), the service times i.i.d. with mean 1; (SA2) the input streams are Poisson with parameters \(\lambda _1\) and \(\lambda _2\), the service times exponential with parameter 1. By using the fluid approximation one finds conditions for the stability and instability of the system and shows that fluid limits admit a branching with uncountable number of branches.

MSC:

90B22 Queues and service in operations research
60J85 Applications of branching processes
60K25 Queueing theory (aspects of probability theory)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Rybko, A.N. and Stolyar, A.L., Ergodicity of Stochastic Processes Describing the Operation of Open Queueing Networks, Probl. Peredachi Inf., 1992, vol. 28, no.3, pp. 3–26 [Probl. Inf. Trans. (Engl. Transl.), 1992, vol. 28, no. 3, pp. 199–220]. · Zbl 0768.60089
[2] Dai, J.G., On Positive Harris Recurrence of Multiclass Queueing Networks: A Unified Approach via Fluid Models, Ann. Appl. Probab., 1995, vol. 5, no.1, pp. 49–77. · Zbl 0822.60083 · doi:10.1214/aoap/1177004828
[3] Stolyar, A.L., On the Stability of Multiclass Queueing Networks: A Relaxed Sufficient Condition via Limiting Fluid Processes, Markov Process. Related Fields, 1995, vol. 1, no.4, pp. 491–512. · Zbl 0902.60079
[4] Dai, J.G. and Meyn, S.P., Stability and Convergence of Moments for Multiclass Queueing Networks via Fluid Limit Models, IEEE Trans. Automat. Control, 1995, vol. 40, no.11, pp. 1889–1904. · Zbl 0836.90074 · doi:10.1109/9.471210
[5] Chen, H., Fluid Approximations and Stability of Multiclass Queueing Networks: Work-Conserving Disciplines, Ann. Appl. Probab., 1995, vol. 5, no.3, pp. 637–665. · Zbl 0847.60073 · doi:10.1214/aoap/1177004699
[6] Down, D.G., On the Stability of Polling Models with Multiple Servers, CWI Report BS-R 9605, Amsterdam, 1996. · Zbl 0938.60096
[7] Foss, S.G. and Rybko, A.N., Stability of Multiclass Jakson-Type Networks, Markov Process. Related Fields, 1996, vol. 2, no.3, pp. 461–486. · Zbl 0902.60081
[8] Meyn, S.P., Transience of Multiclass Queueing Networks and Their Fluid Models, Ann. Appl. Probab., 1995, vol. 5, no.4, pp. 946–957. · Zbl 0865.60079 · doi:10.1214/aoap/1177004601
[9] Puhalskii, A.A. and Rybko, A.N., Nonergodicity of a Queueing Network under Nonstability of Its Fluid Model, Probl. Peredachi Inf., 2000, vol. 36, no.1, pp. 26–47 [Probl. Inf. Trans. (Engl. Transl.), 2000, vol. 36, no. 1, pp. 23–41]. · Zbl 0966.60095
[10] Kumar, P.R. and Seidman, T.I., Dynamic Instabilities and Stabilization Methods in Distributed Real-Time Scheduling of Manufacturing Systems, IEEE Trans. Automat. Control, 1990, vol. 35, no.3, pp. 289–298. · Zbl 0715.90062 · doi:10.1109/9.50339
[11] Chen, H. and Mandelbaum, A., Discrete Flow Networks: Bottleneck Analysis and Fluid Approximations, Math. Oper. Res., 1991, vol. 16, no.2, pp. 408–446. · Zbl 0735.60095 · doi:10.1287/moor.16.2.408
[12] Bramson, M., Instability of FIFO Queueing Networks, Ann. Appl. Probab., 1994, vol. 4, no.2, pp. 414–431. · Zbl 0804.60079 · doi:10.1214/aoap/1177005066
[13] Malyshev, V.A., Networks and Dynamical Systems, Adv. Appl. Probab., 1993, vol. 25, no.1, pp. 140–175. · Zbl 0768.60075 · doi:10.2307/1427500
[14] Ignatyik, I. and Malyshev, V., Classification of Random Walks in \(\mathbb{Z}\) 4 + , Selecta Math., 1993, vol. 12, no.2, pp. 129–166.
[15] Fayolle, G., Malyshev, V.A., and Menshikov, M.V., Topics in the Constructive Theory of Countable Markov Chains, Cambridge: Cambridge Univ. Press, 1995. · Zbl 0823.60053
[16] Foss, S. and Kovalevskii, A., A Stability Criterion via Fluid Limits and Its Application to a Polling System, Queueing Syst., 1999, vol. 32, no.1–3, pp. 131–168. · Zbl 0945.90013 · doi:10.1023/A:1019187004209
[17] Hunt, P.J., Pathological Behavior in Loss Networks, J. Appl. Probab., 1995, vol. 32, no.2, pp. 519–533. · Zbl 0823.60093 · doi:10.2307/3215305
[18] Harris, T.E., The Theory of Branching Processes, Berlin: Springer, 1963. Translated under the title Teoriya vetvyashchikhsya sluchainykh protsessov, Moscow: Mir, 1966.
[19] Asmussen, S. and Hering, H., Branching Processes, Boston: Birkhauser, 1983. · Zbl 0516.60095
[20] Athreya, K.B. and Ney, P.F., Branching Processes, Berlin: Springer, 1972. · Zbl 0259.60002
[21] Roesler, U., Topchii, V.A., and Vatutin, V.A., The Rate of Convergence for Weighted Branching Processes, Siberian Adv. Math., 2002, vol. 12, no.4, pp. 57–82. · Zbl 1046.60076
[22] Shiryaev, A.N., Veroyatnost’, Moscow: Nauka, 1989, 2nd ed. Translated under the title Probability, New York: Springer, 1996.
[23] Kratzer, A. and Franz, W., Transzendente Funktionen, Leipzig: Akademische, 1960. Translated under the title Transtsendentnye funktsii, Moscow: Inostr. Lit., 1963.
[24] Foss, S.G. and Denisov, D.E., On Transience Conditions for Markov Chains, Sibirsk. Mat. Zh., 2001, vol. 42, no.2, pp. 425–433 [Siberian Math. J. (Engl. Transl.), 2001, vol. 42, no. 2, pp. 364–371]. · Zbl 1074.60505
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.