On the stationary distribution of queue lengths in a multi-class priority queueing system with customer transfers. (English) Zbl 1196.60155
The paper deals with a multi-class priority queueing system with customer transfers from lower priority queues to higher priority queues. Conditions for the queueing system to be stable/unstable are obtained. An auxiliary queueing system with an product-form solution for the stationary queue length distribution is considered. Sample path relationships between the queue lengths in the original queueing system and the auxiliary queueing system are obtained, which lead to bounds for the stationary distribution of the queue lengths in the original queueing system. Using matrix-analytic methods, it is shown that the tail asymptotics of the stationary distribution is exact geometric, if the queue with the highest priority is overloaded.
Reviewer: Andreas Brandt (Berlin)
MSC:
| 60K25 | Queueing theory (aspects of probability theory) |
| 90B22 | Queues and service in operations research |
Keywords:
priority queueing system; tail asymptotic; matrix-analytic methods; sample path relationshipReferences:
| [1] | Adan, I.J.B.F., Wessels, J., Zijm, W.H.M.: Analysis of the asymmetric shortest queue problem with threshold jockeying. Stoch. Models 7, 615–628 (1991) · Zbl 0741.60093 · doi:10.1080/15326349108807209 |
| [2] | Argon, N.T., Ziya, S., Righer, R.: Scheduling impatient jobs in a clearing system with insights on patient triage in mass casualty incidents. Probab. Eng. Inf. Sci. 22, 301–332 (2008) · Zbl 1211.90105 · doi:10.1017/S0269964808000272 |
| [3] | Asmussen, S.: Applied Probability and Queues, 2nd edn. Springer, New York (2003) · Zbl 1029.60001 |
| [4] | Brandt, A., Brandt, M.: On a two-queue priority system with impatience and its application to a call center. Methodol. Comput. Appl. Probab. 1, 191–210 (1999) · Zbl 0948.60087 · doi:10.1023/A:1010009304213 |
| [5] | Chao, X., Miyazawa, M., Pinedo, M.: Queueing Networks, Customers, Signals and Production Form Solutions. Wiley, New York (1999) · Zbl 0936.90010 |
| [6] | Chen, M.F.: On three classical problems for Markov chains with continuous time parameters. J. Appl. Probab. 28(2), 305–320 (1991) · Zbl 0761.60064 · doi:10.2307/3214868 |
| [7] | Choi, B.D., Kim, B.: Non-ergodicity criteria for denumerable continuous time Markov processes. Oper. Res. Lett. 32, 574–580 (2004) · Zbl 1067.60067 · doi:10.1016/j.orl.2004.03.001 |
| [8] | Cohen, J.W.: The Single Server Queue. North-Holland, Amsterdam (1982) · Zbl 0481.60003 |
| [9] | Fayolle, G., Malyshev, V.A., Menshikov, M.V.: Topics in the Constructive Theory of Countable Markov Chains. Cambridge University Press, Cambridge (1995) · Zbl 0823.60053 |
| [10] | Foley, R.D., McDonald, D.R.: Join the shortest queue: stability and exact asymptotics. Ann. Appl. Probab. 11, 569–607 (2001) · Zbl 1016.60078 |
| [11] | Foster, F.G.: On stochastic matrices associated with certain queueing processes. Ann. Math. Stat. 24, 355–360 (1953) · Zbl 0051.10601 · doi:10.1214/aoms/1177728976 |
| [12] | Gomez-Corral, A., Krishnamoorthy, A., Narayanan, V.C.: The impact of self-generation of priorities on multi-server queues with finite capacity. Stoch. Models 21, 427–447 (2005) · Zbl 1073.60086 · doi:10.1081/STM-200056015 |
| [13] | Hajek, B.: Optimal control of two interacting service stations. IEEE Trans. Automat. Contr. AC-29, 491–499 (1984) · Zbl 0555.90047 · doi:10.1109/TAC.1984.1103577 |
| [14] | He, Q.M., Xie, J.G., Zhao, X.B.: Stability conditions of a preemptive repeat priority MMAP[N]/PH[N]/S queue with customer transfers (short version). In: ASMDA (Advanced Stochastic Models and Data Analysis) 2009 Conference Proceedings (accepted) |
| [15] | Jackson, J.R.: Networks of waiting lines. Oper. Res. 5, 518–521 (1975) · doi:10.1287/opre.5.4.518 |
| [16] | Kroese, D.P., Scheinhardt, W.R.W., Taylor, P.G.: Spectral properties of the tandem Jackson network, seen as a quasi-birth-and-death process. Ann. Appl. Probab. 14(4), 2057–2089 (2004) · Zbl 1078.60078 · doi:10.1214/105051604000000477 |
| [17] | Latouche, G., Ramaswami, V.: Introduction to Matrix Analytic Methods in Stochastic Modelling. SIAM, Philadelphia (1999) · Zbl 0922.60001 |
| [18] | Li, H., Miyazawa, M., Zhao, Y.Q.: Geometric decay in a QBD process with countable background states with applications to a join-the-shortest-queue model. Stoch. Models 23, 413–438 (2007) · Zbl 1124.60074 · doi:10.1080/15326340701471042 |
| [19] | Lucantoni, D.M.: New results on the single server queue with a batch Markovian arrival process. Stoch. Models 7, 1–46 (1991) · Zbl 0733.60115 · doi:10.1080/15326349108807174 |
| [20] | Meyn, S.P., Tweedie, R.: Markov Chains and Stochastic Stability. Springer, Berlin (1993) · Zbl 0925.60001 |
| [21] | Miller, D.G.: Computation of steady-state probabilities for M/M/1 priority queues. Oper. Res. 29, 945–958 (1981) · Zbl 0468.60089 · doi:10.1287/opre.29.5.945 |
| [22] | Miyazawa, M., Zhao, Y.Q.: The stationary tail asymptotics in the GI/G/1 type queue with countably many background states. Adv. Appl. Probab. 36(4), 1231–1251 (2004) · Zbl 1136.60366 · doi:10.1239/aap/1103662965 |
| [23] | Neuts, M.F.: A versatile Markovian point process. J. Appl. Probab. 16, 764–779 (1979) · Zbl 0422.60043 · doi:10.2307/3213143 |
| [24] | Neuts, M.F.: Matrix-Geometric Solutions in Stochastic Models–An Algorithmic Approach. Johns Hopkins Press, Baltimore (1981) · Zbl 0469.60002 |
| [25] | Neuts, M.F.: The caudal characteristic curve of queues. Adv. Appl. Probab. 18, 221–254 (1986) · Zbl 0588.60094 · doi:10.2307/1427244 |
| [26] | Seneta, E.: Non-Negative Matrices: An Introduction to Theory and Applications. Wiley, New York (1973) · Zbl 0278.15011 |
| [27] | Stoyan, D.: Comparison Methods for Queues and Other Stochastic Models. Wiley, New York (1983) · Zbl 0536.60085 |
| [28] | Takagi, H.: Queueing Systems. Vacation and Priority Systems, vol. 1. Elsevier, Amsterdam (1991) · Zbl 0744.60114 |
| [29] | Takahashi, Y., Fujimoto, K., Makimoto, N.: Geometric decay of the steady-state probabilities in a quasi-birth-and-death number of phases. Stoch. Models 17(1), 1–24 (2001) · Zbl 0985.60074 · doi:10.1081/STM-100001397 |
| [30] | Wang, Q.: Modeling and analysis of high risk patient queues. Eur. J. Oper. Res. 155, 502–515 (2004) · Zbl 1044.90016 · doi:10.1016/S0377-2217(02)00916-5 |
| [31] | Whitt, W.: Deciding which queue to join: some counterexamples. Oper. Res. 34, 55–62 (1986) · Zbl 0622.90035 · doi:10.1287/opre.34.1.55 |
| [32] | Xie, J.G., He, Q.M., Zhao, X.B.: Stability of a priority queueing system with customer transfers. Oper. Res. Lett. 36, 705–709 (2008) · Zbl 1151.90369 · doi:10.1016/j.orl.2008.06.007 |
| [33] | Xie, J.G., He, Q.M., Zhao, X.B.: On the stationary distribution of the queue lengths in a multi-class priority queueing system with customer transfers. Working Paper #08-03, Department of Industrial Engineering, Dalhousie University (2008) · Zbl 1196.60155 |
| [34] | Xu, S.H., Chen, H.: On the asymptote of the optimal routing policy for two service stations. IEEE Trans. Automat. Contr. 38, 187–189 (1990) · doi:10.1109/9.186338 |
| [35] | Xu, S.H., Zhao, Y.Q.: Dynamic routing and jockeying controls in a two-station queueing system. Adv. Appl. Probab. 28, 1201–1226 (1996) · Zbl 0867.90057 · doi:10.2307/1428170 |
| [36] | Zhao, Y., Grassmann, W.K.: Queueing analysis of a jockeying model. Oper. Res. 43, 520–529 (1995) · Zbl 0839.90048 · doi:10.1287/opre.43.3.520 |
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.
