T-QBD过程的理论与应用
|
摘要
在复杂随机模型的分析中,拟生灭过程起着重要的作用。对有限位相的拟生灭过程,已经有了较为系统的处理方法;对于无限位相的过程,虽然有不少研究人员从各方面作了探讨,但它仍然是一个具有挑战性的课题,例如,其平稳分布的求解,目前还是一个未解决的难题。
在实际模型的分析中,一种特殊的无限位相拟生灭过程最为常见,即在其三对角形式的无穷小生成元中,每一个子块也是三对角形式的矩阵,我们称之为三对角无限位相拟生灭过程,简记为T-QBD过程。在本博士论文中,我们将对T-QBD过程以及可以用该过程描述的一些随机模型进行讨论。我们从几个实际的排队模型出发,给出了T-QBD过程的数学描述,这些模型既有水平相依的,也有水平独立的,既有简单边界的,又有复杂边界的,这些形式各异的过程将是本文讨论的主要对象。
在本文中,作者主要做了以下工作:
首先,对一种水平独立的T-QBD过程,我们讨论了其平稳分布在水平方向上的尾部特征。在对文献中分析尾部的一种方法作了进一步的讨论的基础上,我们分析了两个具体的排队模型,即T-SPH/M/1排队和M/T-SPH/1排队(关于T-SPH分布可参见定义2.4.2)。所得结果表明,在一定条件下,它们各自的联合平稳分布在水平方向具有几何衰减的特性,这些结论也为后文中进一步分析这两个模型作好了理论上的准备。
其次,在对T-SPH/M/1排队和M/T-SPH/1排队尾部分析的基础上,对这两个模型作了进一步的讨论,给出了各自的率算子的具体形式,从而得到了各自的算子几何解。其中对第一个模型,还得到了联合平稳分布,平稳队长分布以及两个边缘分布的解析形式解;对第二个模型,从算子几何解出发,给出联合平稳分布的数值解。另外,对该模型,我们还从不同的途径得到了其联合平稳分布前几个分量的解析解,虽然用该方法很难得到其余分量的解,但却有可能对其余分量解的形式做出预测。
另外,我们考虑了T-QBD过程联合平稳分布水平和位相的独立性问题,指出了其水平和位相相互独立且两个边缘分布都为几何分布的充分必要条件,并以两个实际模型为例给出了检验这些条件的具体方法。同时还讨论了一种广义独立性,并给出了一般二维马尔可夫过程平稳分布水平和位相相互独立的一个充分条件。另外,在讨论独立性时,我们还发现了算子几何解的一个有趣现象,即存在矩阵,它具有率算子的一些性质,例如满足算子几何解等,但却不是率算子,而且这样的矩阵可以有无穷多个。
最后,我们给出了计算T-QBD过程联合平稳分布数值解的有效算法,即分块矩形迭代算法(BRI算法)。该算法适用于前面提到的各种类型的T-QBD过程,并且还有可能推广到高维过程以及更一般的过程,如GI/M/1型过程等。对该算法,我们讨论了其收敛性,计算复杂性等问题,虽然没有给出一个基于给定误差界的终止条件,但结合具体模型,给出了终止迭代次数的经验公式。另外,在所得数值结果的基础上,分析了几个实际模型,对这些模型,不但验证了文献中的一些已知结果,还发现了它们的一些新性质,从面也说明了我们算法的有效性和实用性。
在本文的最后部分,我们把文中的内容作了总结,并对文中没有解决的而在实际应用及研究中又是有意义的一些问题作了描述,从而指出了以后研究的方向。
It is well known that the quasi-birth-and-death process (abbreviated as QBD pro-cess) plays an important role in analysis of complicated stochastic models. For QBDprocess with finite phases, the systematical method is now available; for situationswith countably phases, it is still a challenging problem even though many researchworks have been done in various aspects. For example, the general method to compu-tation the exact stationary distribution remains unsolved.
In the analysis of practical models, one important special QBD process withcountable phase is very common, that is, in the tri-diagonal infinitesimal generator,each sub-block is also a tri-diagonal matrix, we call such QBD process T-QBD pro-cess. In this dissertation, we will study T-QBD process and some stochastic modelsthat can be described using this special process. We bring forward the mathemati-cal description of T-QBD process starting from some practical queue models, someof them are level dependent, some are level independent, some with simple bound-aries, and some with complicated boundaries, these processes with various forms willbecome the main research object in this paper.
In this paper, the author mainly studies the following problems:
First, for the level independent T-QBD process, we discussed the tail characteris-tic of stationary distribution along level direction. After making further discussion onone of the tail analysis method in literature, we analyze two practical queue models,which are T-SPH/M/1 and M/T-SPH/1 queue(for the definition of T-SPH distribution,one can see Definition 2.4.2). The result indicates that under certain conditions, theirjoint stationary distributions have the characteristic of geometric decay in level direc-tion. Also, the result provides theoretical foundations for further analysis of these twomodels.
Second, based on tail analysis of T-SPH/M/1 queue and M/T-SPH/1 queue, fur-ther analysis is made and the forms of rate operator of each model are given, so thatoperator-geometric solution of each model is reached. For the first model, we canget the joint stationary distribution, stationary length distribution and two marginaldistributions in close form; For the second model, we give the numerical solution of joint stationary solution based on the operator-geometric solution. Furthermore, forthis model, we can get the analytical solution of first several component of the jointstationary distribution using other methods. Though it is very difficult to get solutionof other component, it is possible to predict its’form.
Third, we study the level-phase independence problem of joint stationary distri-bution of T-QBD process, and derive the necessary and sufficient conditions for leveland phase independence and both of the level and phase with geometric distributions.Taking two practical models as example, the practical method to verify these condi-tions is given. At the same time, one generalized independence is discussed, and onesufficient condition for independence problems of level and phase for general Markovprocess is given. Also, while the independence problem is discussed, we find an in-teresting fact of operator-geometric solution, that is, there exits some matrices whichhas properties as rate operator, for example, it fulfill the operator-geometric solutionbut is not rate operator, and the number of such matrix could be infinite.
In the end, we bring forward the efficient algorithm to calculate the numericalsolution for joint stationary distribution of T-QBD process, which is called block rect-angle iterative(BRI) algorithm. This algorithm is applicable for all types of T-QBDprocess mentioned above, also, it is possible for it to be extended to higher dimen-sional and more generalized process, such as GI/M/1 type process. We studied theconvergence and computing complexity of this algorithm, furthermore, using a con-crete model, we give out the experience formula of terminating iteration times, thoughthe exact stopping condition under given error is not given. Based on numerical re-sults, by analyzing several practical models, we not only verify some conclusion inthe literature, but also find some new properties for such models. Therefore, the ef-fectiveness and applicability of our algorithm is proved.
In the final part of this paper, we make conclusion to the whole thesis, and pointout some problems that are important in practical application and research but are notsolved in this paper, so that we can know what we will do in the future.
在实际模型的分析中,一种特殊的无限位相拟生灭过程最为常见,即在其三对角形式的无穷小生成元中,每一个子块也是三对角形式的矩阵,我们称之为三对角无限位相拟生灭过程,简记为T-QBD过程。在本博士论文中,我们将对T-QBD过程以及可以用该过程描述的一些随机模型进行讨论。我们从几个实际的排队模型出发,给出了T-QBD过程的数学描述,这些模型既有水平相依的,也有水平独立的,既有简单边界的,又有复杂边界的,这些形式各异的过程将是本文讨论的主要对象。
在本文中,作者主要做了以下工作:
首先,对一种水平独立的T-QBD过程,我们讨论了其平稳分布在水平方向上的尾部特征。在对文献中分析尾部的一种方法作了进一步的讨论的基础上,我们分析了两个具体的排队模型,即T-SPH/M/1排队和M/T-SPH/1排队(关于T-SPH分布可参见定义2.4.2)。所得结果表明,在一定条件下,它们各自的联合平稳分布在水平方向具有几何衰减的特性,这些结论也为后文中进一步分析这两个模型作好了理论上的准备。
其次,在对T-SPH/M/1排队和M/T-SPH/1排队尾部分析的基础上,对这两个模型作了进一步的讨论,给出了各自的率算子的具体形式,从而得到了各自的算子几何解。其中对第一个模型,还得到了联合平稳分布,平稳队长分布以及两个边缘分布的解析形式解;对第二个模型,从算子几何解出发,给出联合平稳分布的数值解。另外,对该模型,我们还从不同的途径得到了其联合平稳分布前几个分量的解析解,虽然用该方法很难得到其余分量的解,但却有可能对其余分量解的形式做出预测。
另外,我们考虑了T-QBD过程联合平稳分布水平和位相的独立性问题,指出了其水平和位相相互独立且两个边缘分布都为几何分布的充分必要条件,并以两个实际模型为例给出了检验这些条件的具体方法。同时还讨论了一种广义独立性,并给出了一般二维马尔可夫过程平稳分布水平和位相相互独立的一个充分条件。另外,在讨论独立性时,我们还发现了算子几何解的一个有趣现象,即存在矩阵,它具有率算子的一些性质,例如满足算子几何解等,但却不是率算子,而且这样的矩阵可以有无穷多个。
最后,我们给出了计算T-QBD过程联合平稳分布数值解的有效算法,即分块矩形迭代算法(BRI算法)。该算法适用于前面提到的各种类型的T-QBD过程,并且还有可能推广到高维过程以及更一般的过程,如GI/M/1型过程等。对该算法,我们讨论了其收敛性,计算复杂性等问题,虽然没有给出一个基于给定误差界的终止条件,但结合具体模型,给出了终止迭代次数的经验公式。另外,在所得数值结果的基础上,分析了几个实际模型,对这些模型,不但验证了文献中的一些已知结果,还发现了它们的一些新性质,从面也说明了我们算法的有效性和实用性。
在本文的最后部分,我们把文中的内容作了总结,并对文中没有解决的而在实际应用及研究中又是有意义的一些问题作了描述,从而指出了以后研究的方向。
It is well known that the quasi-birth-and-death process (abbreviated as QBD pro-cess) plays an important role in analysis of complicated stochastic models. For QBDprocess with finite phases, the systematical method is now available; for situationswith countably phases, it is still a challenging problem even though many researchworks have been done in various aspects. For example, the general method to compu-tation the exact stationary distribution remains unsolved.
In the analysis of practical models, one important special QBD process withcountable phase is very common, that is, in the tri-diagonal infinitesimal generator,each sub-block is also a tri-diagonal matrix, we call such QBD process T-QBD pro-cess. In this dissertation, we will study T-QBD process and some stochastic modelsthat can be described using this special process. We bring forward the mathemati-cal description of T-QBD process starting from some practical queue models, someof them are level dependent, some are level independent, some with simple bound-aries, and some with complicated boundaries, these processes with various forms willbecome the main research object in this paper.
In this paper, the author mainly studies the following problems:
First, for the level independent T-QBD process, we discussed the tail characteris-tic of stationary distribution along level direction. After making further discussion onone of the tail analysis method in literature, we analyze two practical queue models,which are T-SPH/M/1 and M/T-SPH/1 queue(for the definition of T-SPH distribution,one can see Definition 2.4.2). The result indicates that under certain conditions, theirjoint stationary distributions have the characteristic of geometric decay in level direc-tion. Also, the result provides theoretical foundations for further analysis of these twomodels.
Second, based on tail analysis of T-SPH/M/1 queue and M/T-SPH/1 queue, fur-ther analysis is made and the forms of rate operator of each model are given, so thatoperator-geometric solution of each model is reached. For the first model, we canget the joint stationary distribution, stationary length distribution and two marginaldistributions in close form; For the second model, we give the numerical solution of joint stationary solution based on the operator-geometric solution. Furthermore, forthis model, we can get the analytical solution of first several component of the jointstationary distribution using other methods. Though it is very difficult to get solutionof other component, it is possible to predict its’form.
Third, we study the level-phase independence problem of joint stationary distri-bution of T-QBD process, and derive the necessary and sufficient conditions for leveland phase independence and both of the level and phase with geometric distributions.Taking two practical models as example, the practical method to verify these condi-tions is given. At the same time, one generalized independence is discussed, and onesufficient condition for independence problems of level and phase for general Markovprocess is given. Also, while the independence problem is discussed, we find an in-teresting fact of operator-geometric solution, that is, there exits some matrices whichhas properties as rate operator, for example, it fulfill the operator-geometric solutionbut is not rate operator, and the number of such matrix could be infinite.
In the end, we bring forward the efficient algorithm to calculate the numericalsolution for joint stationary distribution of T-QBD process, which is called block rect-angle iterative(BRI) algorithm. This algorithm is applicable for all types of T-QBDprocess mentioned above, also, it is possible for it to be extended to higher dimen-sional and more generalized process, such as GI/M/1 type process. We studied theconvergence and computing complexity of this algorithm, furthermore, using a con-crete model, we give out the experience formula of terminating iteration times, thoughthe exact stopping condition under given error is not given. Based on numerical re-sults, by analyzing several practical models, we not only verify some conclusion inthe literature, but also find some new properties for such models. Therefore, the ef-fectiveness and applicability of our algorithm is proved.
In the final part of this paper, we make conclusion to the whole thesis, and pointout some problems that are important in practical application and research but are notsolved in this paper, so that we can know what we will do in the future.
引文
[1]汪仁官.概率论引论.北京大学出版社, 1994.
[2]田乃硕,李泉林. PH分布及其在随机模型中的应用.应用数学与计算数学学报, 9(2):1–16, 1995.
[3]张贤科,许甫华.高等代数学.清华大学出版社, 1998.
[4]史定华.随机模型的密度演化方法.科学出版社, 1999.
[5]田乃硕,岳德权.拟生灭过程与矩阵几何解.科学出版社, 2001.
[6]阮传概,孙伟.近世代数及其应用.北京邮电大学出版社, 2001.
[7]孙荣恒,李建平.排队论基础.科学出版社, 2002.
[8]程士宏.测度论与概率论基础.北京大学出版社, 2004.
[9]杨阳,赵以强,李刚.可数背景状态下QBD过程的平稳分布尾渐近态.南京气象学院学报, 29:235–241, 2006.
[10]张宏波,史定华. T-SPH排队队长平稳分布的尾部分析.运筹学学报,12:60–70, 2008.
[11]张宏波,史定华. T-QBD过程水平和位相的独立性.数学的实践与认识,39:排版中, 2009.
[12] I. J. B. F. Adan. A Compensation Approach for Queueing Problems. PhD thesis,Eindhoven University of Technology, 1991.
[13] I. J. B. F. Adan, G. J. van Houtum, J. Wessels, and W. H. M. Zijm. A com-pensation procedure for multiprogramming queues. OR Spectrum, 15:95–106,1993.
[14] I. J. B. F. Adan, J. Wessels, and W. H. M. Zijm. Analysis of the symmetricshortest queue problem. Stochastic Models, 6:693–713, 1990.
[15] I. J. B. F. Adan, J. Wessels, and W. H. M. Zijm. Analysis of the asymmetricshortest queue problem. Que. Sys., 8:1–58, 1991.
[16] I. J. B. F. Adan, J. Wessels, and W. H. M. Zijm. A compensation approach fortwo-dimensional Markov processes. Adv. Appl. Prob., 25:783–817, 1993.
[17] I. J. B. F. Adan and J. Wessels1. Shortest expected delay routing for Erlangservers. Queueing Systems, 23:77–105, 1999.
[18] N. Akar and K. Sohraby. Finite and infinite QBD chains: a simple and unifyingalgorithm approach. INFOCOM, 1997.
[19] A. S. Alfa. Matrix geometric solution of discrete time MAP/PH/1 priorityqueue. Naval Res. Logistics, 45:23–50, 1998.
[20] A. S. Alfa. Discrete time queues and matrix-analytic methods. TOP, 10:147–210, 2002.
[21] A. S. Alfa. Combined elapsed time and matrix-analytic method for the discretetime GI/G/1 and GIX/G/1 systems. Queueing Systems, 45:5–25, 2003.
[22] A. S. Alfa and Wei Li. Matrix-geometric analysis of the discrete time GI/G/1system. Stochastic Models, 17:541–554, 2001.
[23] A. S. Alfa, B. Liu, and Q. M. He. Discrete-time analysis of MAP/PH/1 mul-ticlass general preemptive priority queue. Naval Res. Logistics, 50:662–682,2003.
[24] W. Andreas. A short introduction to queueing theory. Technical report, Tech-nical University Berlin, 1999.
[25] R. B. Bapat and T. E. S. Raghavan. Nonnegative matrices and applications.Cambridge University Press, 1997.
[26] V. E. Benesˇ. Mathematical theory of connecting networks and telephone traffic.Academic Press, New York, 1965.
[27] D. A. Bini, G. Latouche, and B. Meini. Numerical methods for structuredMarkov chains. Oxford University Press, 2005.
[28] J. P. C. Blanc. On a numerical method for calculating state probabilities forqueuing systems with more than one waiting line. J. Comput. Appl. Math.,20:119–125, 1987.
[29] J. P. C. Blanc. The power-series algorithm applied to the shortest-queue model.PhD thesis, Tilburg University, 1989.
[30] J. P. C. Blanc. A numerical approach to cyclic-service queueing models. Queue-ing Systems, 6:173–188, 1990.
[31] J. P. C. Blanc. Performance evaluation of polling systems by means of thepower-series algorithm. Annl. Oper. Res., 35:155–186, 1992.
[32] J. P. C. Blanc. The power-series algorithm applied to the shortest-queue model.Operations Research, 40:157–167, 1992.
[33] J. P. C. Blanc, R. Iasnogorodski, and Ph. Nain. Analysis of the M/GI/1→/M/1queueing model. Queueing Systems, 3:129–156, 1988.
[34] O. J. Boxma and G. J. van Houtum. The compensation approach applied to a2×2 switch. Probab. Engrg. Inform. Sci. , 7:471–493, 1993.
[35] L. Breuer. On the MAP/G/1 queue with Lebesgue-dominated service time dis-tribution and LCFS preemptive repeat service discipline. Stochastic Models,18:589–595, 2002.
[36] L. Breuer and Dieter Baum. An Introduction to Queueing Theory: and Matrix-Analytic Methods. Springer, 2005.
[37] L. Breuer, A. Dudin, V. Klimenok, and G. Tsarenkov. A two-phaseBMAP/G/1/N→PH/1/M-1 system with blocking. Automation and RemoteControl, 65:104–115, 2004.
[38] L. W. Bright and P. G. Taylor. Calculating the equilibrium distribution in leverdependent quasi-birth-and-death process. Stochastic Models, 1:497–526, 1995.
[39] R. A. Brualdi. Introductory Combinatorics. Prentice Hall, 4th edition, 2004.
[40] E. Cinlar. Markov additive processes I. Z. Wahrscheinlichkeitstheorie verw.Geb, 24:85–93, 1972.
[41] E. Cinlar. Markov additive processes II. Z. Wahrscheinlichkeitstheorie verw.Geb, 24:95–121, 1972.
[42] J. W. Cohen and O. J. Boxma. Boundary value problems in quiuing system.Amsterdam, North-Holland, 1993.
[43] B. W. Conolly. The autostrada queuing problem. J. Appl. Prob., 21:394–403,1984.
[44] Robert B. Cooper. Introduction to queueing theory. Elsevier North Holland,Inc, North Holland, 2nd edition, 1981.
[45] Ana da Silva Soares and G. Latouche. Level-phase independence for ?uidqueues. stochastic Models, 21:327–341, 2005.
[46] B. T. Doshi. Queueing systems with vacations-a survey. Queueing Syst., 1:29–66.
[47] S. Drekic. An eigenvalue approach to analyzing a finite source priority queue-ing model. Ann. Oper. Res., 112:139–152, 2002.
[48] S. Drekic and D. G. Woolford. A preemptive priority queue with balking. Eur.J. Oper. Res., 164:387–401, 2005.
[49] G. Fayollye, R. Isanogorodski, and V. Malyshev. Random walks in the quarter-plane. Springer, 1999.
[50] L. Flatto. Two parallel queues created by arrivals with two demands-II. SIAMJ. Appl. Math., 45:861–878, 1985.
[51] L. Flatto and S. Hahn. Two parallel queues created by arrivals with twodemands-I. SIAM J. Appl. Math., 44:1041–1053, 1984.
[52] L. Flatto and H. P. McLean. Two queues in parallel. Comm. Pure. Appl. Math,30:255–263, 1977.
[53] R. D. Foley and D. R. McDonald. Join the shortest queue: stability and exactasymptotics. Ann. Appl. Prob., 11:569–607, 2001.
[54] G. J. Foschini and J. Salz. A basic dynamic routing problem and diffusion.IEEE Trans. Comm., 26:320–327, 1978.
[55] K. Fujimoto and Y. Takahashi. Tail behavior of the steady-state distribution intwo-stage tandem queues: numerical experiment and conjecture. J. Oper. Res.Soc. Japan, 39:525–540, 1996.
[56] K. Fujimoto, Y. Takahashi, and N. Makimoto. Asymptotic properties of sta-tionary distributions in two-stage tandem queueing systems. J. Oper. Res. Soc.Japan, 41:118–141, 1998.
[57] I. Gertsbakh. The shorter queue problem: a numerical study using the matrix-geometric solution. Eur. J. Oper. Res., 15:374–381, 1984.
[58] W. K. Grassmann. Transient and steady state results for two parallel queues.OMEGA Int. J. Mgmt Sci, 8:105–112, 1980.
[59] W. K. Grassmann. Finding equilibrium probabilities of QBD processes by spec-tral methods when eigenvalues vanish. Linear Algebra and its Applications,386:207–223, 2004.
[60] W. K. Grassmann and S. Drekic. Multiple eigenvalues in spectral analysis forsolving QBD processes. Methodel Comput. Appl. Probab.
[61] W. K. Grassmann and D. P. Heyman. Equilibrium distribution of block- struc-tured Markov chains with repeating rows. J. Appl. Prob., 27:557–576, 1990.
[62] David Anthony Green. Departure processes from MAP/PH/1 queues. PhDthesis, University of Adelaide, January 1999.
[63] Charles M. Grinstead and J. Laurie. Introduction to Probability. America Math-ematical Society, 1997.
[64] F. A. Haight. Two queues in parallel. Biometrika, 45:401–410, 1958.
[65] S. Halfin. The shortest queue problem. J. Appl. Prob., 22:865–878, 1985.
[66] P. R. Halmos. Measure theory. Springer-Verlag, 1998.
[67] L. Hapue, Y. Q. Zhao, and L. M. Liu. Sufficient conditions for a geometric tailin a QBD process with many countable levels and phases. Stochastic Models,1:77–99, 2005.
[68] Qi-Ming He and Hui Li. Stability conditions of the MMAP[k]/G[k]/1/LCFSpreemptive repeat queue. Queueing systems, 44:137–160, 2003.
[69] Qi-Ming He and M. F. Neuts. Two M/M/1 queues with transfers of customers.Queueing systems, 42:377–400, 2002.
[70] G. Hooghiemstra, M. Keane, and Van De Ree. Power series for stationarydistribution of coupled processor models. SIAM J. Appl. Math, 48:1159–1166,1988.
[71] B. V. Houdt and C. Blondia. Analyzing priority queues with 3 classes usingtree-like processes. Queueing syst., 54:99–109, 2006.
[72] G. J. Houtum, I. J. B. F. Adan, J. Wessels, and W. H. M. Zijm. Performanceanalysis of parallel identical machines with a generalized shortest queue arrivalmechanism. OR Spektrum, 23:411–428, 2001.
[73] K. P. Sapna Isotupa and David A. Stanford. An infinite-phase quasi-birth-and-death model for the non-preemptive priority M/PH/1 queue. Stochasitc Models,18(3):387–424, 2002.
[74] J. R. Jackson. Networks of waiting lines. Operations Research, 5:518–521,1957.
[75] Nicolai M. Josuttis. The C++ standard library, a tutorial and reference. Addi-son Wesley Longman, Inc., 1999.
[76] Olav Kallenberg. Foundations of Modern Probability. Springer, 1997.
[77] E. P. C. Kao. An introduction to stochastic processes. Duxbury Press, 1997.
[78] J. Keilson and L. D. Servi. A distributional form of little’s law. Oper. Res. Lett.,7:223–227.
[79] M. Kijima. Quasi-stationary distribution of single-server phase type queues.Mathematics of Operations Research, 18:423–437, 1993.
[80] J. F. C. Kingman. Two similar queues in parallel. Ann. Math. Statist., 32:1314–1323, 1961.
[81] C. Knessl, B. J. Maticowsky Z., Schuss, and C. Tier. Two parallel queues withdynamic routing. IEEE Trans. Comm., 34:1170–1175, 1986.
[82] G. M. Koole. On the use of the power series algorithm for general Markovprocesses, with an application to a petri net. INFORMS Journal on Computing,9:51–56, 1997.
[83] D. Kroese, W. R. Scheinhardt, and P. G. Taylor. Spectral properties of thetandem Jackson network seen as a quasi-birth-and-death process. Ann. Appl.Prob., 14(4):2057–2089, 2004.
[84] D. P. Kroese and V. F. Nicola. Efficient simulation of a tandem Jackson net-work. ACM Transactions on Modeling and Computer Simulation (TOMACS),12:119–141, 2002.
[85] I. A. Kurkova and Y. M. suhov. Malyshev’s theory and JS-Queue asymptoticsof stationary probabilities. Ann. Appl. Prob., 4:1313–1354, 2003.
[86] G. Latouche and Ramaswami. A logarithmic reduction algorithm for quasi-birth-death process. J. Appl. Prob., 30:650–674, 1993.
[87] G. Latouche and P. Taylor. Truncation and augmentation of level independentQBD processes. Stochastic Processes and Their Application, 99:53–80, 2002.
[88] G. Latouche and P. G. Taylor. Level-phase independence for GI/M/1 typeMarkov chains. J. Appl. Prob., 37:984–998, 2000.
[89] G. Latouche and P. G. Taylor. Drift conditions for matrix-analytic models.Math. Operat. Res., 28:346–360, 2002.
[90] Hui Li, Masakiyo Miyazawa, and Yiqiang Q. Zhao. Geometric decay in aQBD processes with countable background states with applications to a join-the-shortest-queue model. Stochastic Models, 23:413–438, 2007.
[91] Q. L. Li and J. H. Guo. Two types of RG-factorizations of quasi-birth-and-deathprocesses and their applications to stochastic integral functionals. StochasticModels, 20:299–340, 2004.
[92] Q. L. Li and C. Lin. Continuous-time QBD processes with continuous phasevariable. Computers and Mathematics with Applications, 52:1483–1510, 2006.
[93] Q. L. Li and Y. Q. Zhao. Heavy-tailed asymptotics of probability vectors ofMarkov chains of GI/G/1 type. Adv. Appl. Prob., 37:482–509, 2005.
[94] Q. L. Li and Y. Q. Zhao. Light-tailed asymptotics of probability vectors ofMarkov chains of GI/G/1 type. Adv. Appl. Prob., 37:1075–1093, 2005.
[95] Q. L. Li, Y. Q. Zhao, and L. M. Liu. An RG-factorization approach for aBMAP/M/1 generalized processor-sharing queue. Stochastic Models, 21:77–99, 2-3 2005.
[96] Zhao Tong Lian and L. M. Liu. A tandem network with MAP inputs. O. R.Lett., 36:189–195, 2008.
[97] Zhaotong Lian, Liming Liu, and Xiaoming Liu. Discriminatory processor shar-ing queues and the DREB method. Stochastic Models, 24:19–40, 2008.
[98] L. M. Liu, M. Miyazawa, and Y. Q. Zhao. Geometric decay in level-expandingQBD models. Ann. Oper. Res., 160:83–98, 2008.
[99] V. A. Malyshev. An analytic method in the theory of two-dimensional positiverandom walks. Sibirskii Math. Zh., 13:1314–1329, 1972.
[100] V. A. Malyshev. Asymptotic behavior of stationary probabilities for two-dimensional positive random walks. Sibirskii Math. Zh., 14:109–117, 1973.
[101] S. P. Meyn and R. L. Tweedie. Markov chains and stochastic stability. Springer-Verlag, 2005.
[102] D. R. Miller. Computation of steady-state probabilities for M/M/1 priorityqueues. Operations Research, 29:945–958, 1981.
[103] M. Miyazawa. A Markov renewal approach to M/G/1 type queues with count-able many background states. Queueing Systems, 46:177–196, 2004.
[104] M. Miyazawa and Y. Q. Zhao. The stationary tail asymptotic in the GI/G/1type queue with countable many background states. Adv. Appl. Prob., 36:1231–1251, 2004.
[105] A. Motyerm and P. G. Taylor. Decay rate for quasi-birth-and-death process withcountable many phases and tri-diagonal block generators. Adv. Appl. Prob.,38:522–544, 2006.
[106] M. F. Neuts. Markov chains with applications in queueing theory, which havea matrix-geometric invariant probability vector. Adv. Appl. Prob., 10:185–212,1978.
[107] M. F. Neuts. The probabilistic significance of the rate matrix in matrix-geometric invariant vectors. J. Appl. Prob., 17:291–296, 1980.
[108] M. F. Neuts. Matrix-geometric solutions in stochastic models: an algorithmicapproach. The Johns Hopkins University Press: Baltimore, 1981.
[109] M. F. Neuts. Some promising directions in algorithmic probability. pages 429–443. In: Advances in matrix analysis methods for stochastic models, Notablepublications, Inc., 1998.
[110] V. Ramaswami. Matrix analytic methods: a tutorial overview with some exten-sions and new results. pages 261–296, New York, 1997. In: Matrix-AnalysisMethods in Stochastic Models, Marcel Dekker.
[111] V. Ramaswami and P. G. Taylor. An operator-analytic approach to product-formnetworks. Stochastic Models, 12:121–142, 1996.
[112] V. Ramaswami and P. G. Taylor. Some properties of the rate operators in leveldependent quasi birth and death processes with a countable number of phases.Stochastic Models, 12:143–164, 1996.
[113] V. Ramswami and G. Latouche. A general class of Markov processes withexplicit matrix-geometric solutions. OR Spectrum, 8:209–218, 1986.
[114] B. M. Rao and M. J. M. Posner. Algorithmic and approximation analysis of theshorter queue model. Naval Res. Log., 34:381–398, 1987.
[115] S. M. Ross. Stochastic processes. John Wiley and Sons Inc., 1981.
[116] S. M. Ross. Introduction to probability and statistics for engineers and scien-tists. Elsevier Academic Press, 3rd edition, 2004.
[117] S. M. Ross. Introduction to probability models. Elsevier Academic Press, 9thedition, 2007.
[118] E. B. Saff and A. D. Snider. Fundamentals of Complex Analysis with Applica-tions to Engineering, Science. Prentice Hall, 3rd edition, 2003.
[119] Y. Sakuma and M. Miyazama. On the effect of finite buffer truncation in atwo-node Jackson network. J. Appl. Prob., 42:199–222, 2005.
[120] Y. Sakuma, M. Miyazama, and Y. Q. Zhao. Decay rate for a PH/M/2 queuewith shortest queue discipline. Queueing Syst., 53:189–201, 2006.
[121] E. Seneta. Nonnegative matrices and Markov chains. Springer, New York,1981.
[122] B. Sengupta. Phase type representation of matrix-geometric solution. Stochas-tic Models, 6:163–167, 1990.
[123] D. H. Shi, J. L. Guo, and L. M. Liu. SPH-distributions and the rectangle itera-tive algorithm. pages 207–224, New York, 1997. In: Matrices-analysis methodsin stochastic models, Marcel Decker.
[124] Dinghua Shi, Qinghua Chen, and Liming Liu. Markov chain-based numericalmethod for degree distributions of growing networks. Phys. Rev. E, 71:036140,2005.
[125] Dinghua Shi, Jinli Guo, and Liming Liu. On the SPH-distribution class. ActaMathematica Scientia, 2:137–160, 2005.
[126] Dinghua Shi, Hongbo Zhang, and Liming Liu. An algorithmic approach fordependent queues. Queueing Syst., Submitted.
[127] Y. Takahashi and N. Makimoto. Geometric decay of the steady-state proba-bilities in a quasi-birth-and-death process with countable number of phases.Stochastic Models, 17:1–24, 2001.
[128] N. S. Tian and Z. G. Zhang. Vacation Queueing Models: Theory and Applica-tions. Spinger, 2006.
[129] S. R. E. Turner. A join the shortest queue models in heavy traffic. J. Appl.Prob., 37:212–223, 2000.
[130] R. L. Tweedie. Operator-geometric stationary distributions of markov chainswith application to queuing models. Adv. Appl. Prob., 14:368–391, 1982.
[131] W. B. van den Hout. The power-series algorithm. PhD thesis, Tilburg Univer-sity, 1996.
[132] J. S. H. van Leeuwaarden and E. M. M. Winands. Quasi-birth-and-death pro-cesses with a explicit rate matrix. Stochastic Models, 22:77–98, 2006.
[133] Haishen Yao and Charles Knessl. On the infinite server shortest queue problem:symmetric case. Stochastic Models, 21:101–132, 2005.
[134] Haishen Yao and Charles Knessl. On the infinite server shortest queue problem:Non-symmetric case. Queueing Systems, 52:157–177, 2006.
[135] Hongbo Zhang and Dinghua Shi. Analysis of two queueing models with ex-plicit rate operators and stationary distributions. Stochastic analysis and appli-cations, Submitted.
[136] Y. Q. Zhao. Censoring technique in studying block-structured Markov chains.pages 417–433, P.Eds., 2000. In: advances in algorithmic methods for Stochas-tic Models, Notable Publications.
[137] Y. Q. Zhao and W. K. Grassmann. The shorter queue problem: a numericalstudy using the matrix geometric solution. Queueing Systems, 8:59–79, 1991.
[138] Y. Q. Zhao, W. Li, and Braun W. John. Censoring, factorization, and spectralanalysis for transition matrices with block-repeating entries. Methodology andComputing in Applied Probability, 5:35–58, 2003.
[139] A. P. Zwart. Queuing systems with heavy tails. PhD thesis, Technische Univer-siteit Eindhoven, September 2001.
[2]田乃硕,李泉林. PH分布及其在随机模型中的应用.应用数学与计算数学学报, 9(2):1–16, 1995.
[3]张贤科,许甫华.高等代数学.清华大学出版社, 1998.
[4]史定华.随机模型的密度演化方法.科学出版社, 1999.
[5]田乃硕,岳德权.拟生灭过程与矩阵几何解.科学出版社, 2001.
[6]阮传概,孙伟.近世代数及其应用.北京邮电大学出版社, 2001.
[7]孙荣恒,李建平.排队论基础.科学出版社, 2002.
[8]程士宏.测度论与概率论基础.北京大学出版社, 2004.
[9]杨阳,赵以强,李刚.可数背景状态下QBD过程的平稳分布尾渐近态.南京气象学院学报, 29:235–241, 2006.
[10]张宏波,史定华. T-SPH排队队长平稳分布的尾部分析.运筹学学报,12:60–70, 2008.
[11]张宏波,史定华. T-QBD过程水平和位相的独立性.数学的实践与认识,39:排版中, 2009.
[12] I. J. B. F. Adan. A Compensation Approach for Queueing Problems. PhD thesis,Eindhoven University of Technology, 1991.
[13] I. J. B. F. Adan, G. J. van Houtum, J. Wessels, and W. H. M. Zijm. A com-pensation procedure for multiprogramming queues. OR Spectrum, 15:95–106,1993.
[14] I. J. B. F. Adan, J. Wessels, and W. H. M. Zijm. Analysis of the symmetricshortest queue problem. Stochastic Models, 6:693–713, 1990.
[15] I. J. B. F. Adan, J. Wessels, and W. H. M. Zijm. Analysis of the asymmetricshortest queue problem. Que. Sys., 8:1–58, 1991.
[16] I. J. B. F. Adan, J. Wessels, and W. H. M. Zijm. A compensation approach fortwo-dimensional Markov processes. Adv. Appl. Prob., 25:783–817, 1993.
[17] I. J. B. F. Adan and J. Wessels1. Shortest expected delay routing for Erlangservers. Queueing Systems, 23:77–105, 1999.
[18] N. Akar and K. Sohraby. Finite and infinite QBD chains: a simple and unifyingalgorithm approach. INFOCOM, 1997.
[19] A. S. Alfa. Matrix geometric solution of discrete time MAP/PH/1 priorityqueue. Naval Res. Logistics, 45:23–50, 1998.
[20] A. S. Alfa. Discrete time queues and matrix-analytic methods. TOP, 10:147–210, 2002.
[21] A. S. Alfa. Combined elapsed time and matrix-analytic method for the discretetime GI/G/1 and GIX/G/1 systems. Queueing Systems, 45:5–25, 2003.
[22] A. S. Alfa and Wei Li. Matrix-geometric analysis of the discrete time GI/G/1system. Stochastic Models, 17:541–554, 2001.
[23] A. S. Alfa, B. Liu, and Q. M. He. Discrete-time analysis of MAP/PH/1 mul-ticlass general preemptive priority queue. Naval Res. Logistics, 50:662–682,2003.
[24] W. Andreas. A short introduction to queueing theory. Technical report, Tech-nical University Berlin, 1999.
[25] R. B. Bapat and T. E. S. Raghavan. Nonnegative matrices and applications.Cambridge University Press, 1997.
[26] V. E. Benesˇ. Mathematical theory of connecting networks and telephone traffic.Academic Press, New York, 1965.
[27] D. A. Bini, G. Latouche, and B. Meini. Numerical methods for structuredMarkov chains. Oxford University Press, 2005.
[28] J. P. C. Blanc. On a numerical method for calculating state probabilities forqueuing systems with more than one waiting line. J. Comput. Appl. Math.,20:119–125, 1987.
[29] J. P. C. Blanc. The power-series algorithm applied to the shortest-queue model.PhD thesis, Tilburg University, 1989.
[30] J. P. C. Blanc. A numerical approach to cyclic-service queueing models. Queue-ing Systems, 6:173–188, 1990.
[31] J. P. C. Blanc. Performance evaluation of polling systems by means of thepower-series algorithm. Annl. Oper. Res., 35:155–186, 1992.
[32] J. P. C. Blanc. The power-series algorithm applied to the shortest-queue model.Operations Research, 40:157–167, 1992.
[33] J. P. C. Blanc, R. Iasnogorodski, and Ph. Nain. Analysis of the M/GI/1→/M/1queueing model. Queueing Systems, 3:129–156, 1988.
[34] O. J. Boxma and G. J. van Houtum. The compensation approach applied to a2×2 switch. Probab. Engrg. Inform. Sci. , 7:471–493, 1993.
[35] L. Breuer. On the MAP/G/1 queue with Lebesgue-dominated service time dis-tribution and LCFS preemptive repeat service discipline. Stochastic Models,18:589–595, 2002.
[36] L. Breuer and Dieter Baum. An Introduction to Queueing Theory: and Matrix-Analytic Methods. Springer, 2005.
[37] L. Breuer, A. Dudin, V. Klimenok, and G. Tsarenkov. A two-phaseBMAP/G/1/N→PH/1/M-1 system with blocking. Automation and RemoteControl, 65:104–115, 2004.
[38] L. W. Bright and P. G. Taylor. Calculating the equilibrium distribution in leverdependent quasi-birth-and-death process. Stochastic Models, 1:497–526, 1995.
[39] R. A. Brualdi. Introductory Combinatorics. Prentice Hall, 4th edition, 2004.
[40] E. Cinlar. Markov additive processes I. Z. Wahrscheinlichkeitstheorie verw.Geb, 24:85–93, 1972.
[41] E. Cinlar. Markov additive processes II. Z. Wahrscheinlichkeitstheorie verw.Geb, 24:95–121, 1972.
[42] J. W. Cohen and O. J. Boxma. Boundary value problems in quiuing system.Amsterdam, North-Holland, 1993.
[43] B. W. Conolly. The autostrada queuing problem. J. Appl. Prob., 21:394–403,1984.
[44] Robert B. Cooper. Introduction to queueing theory. Elsevier North Holland,Inc, North Holland, 2nd edition, 1981.
[45] Ana da Silva Soares and G. Latouche. Level-phase independence for ?uidqueues. stochastic Models, 21:327–341, 2005.
[46] B. T. Doshi. Queueing systems with vacations-a survey. Queueing Syst., 1:29–66.
[47] S. Drekic. An eigenvalue approach to analyzing a finite source priority queue-ing model. Ann. Oper. Res., 112:139–152, 2002.
[48] S. Drekic and D. G. Woolford. A preemptive priority queue with balking. Eur.J. Oper. Res., 164:387–401, 2005.
[49] G. Fayollye, R. Isanogorodski, and V. Malyshev. Random walks in the quarter-plane. Springer, 1999.
[50] L. Flatto. Two parallel queues created by arrivals with two demands-II. SIAMJ. Appl. Math., 45:861–878, 1985.
[51] L. Flatto and S. Hahn. Two parallel queues created by arrivals with twodemands-I. SIAM J. Appl. Math., 44:1041–1053, 1984.
[52] L. Flatto and H. P. McLean. Two queues in parallel. Comm. Pure. Appl. Math,30:255–263, 1977.
[53] R. D. Foley and D. R. McDonald. Join the shortest queue: stability and exactasymptotics. Ann. Appl. Prob., 11:569–607, 2001.
[54] G. J. Foschini and J. Salz. A basic dynamic routing problem and diffusion.IEEE Trans. Comm., 26:320–327, 1978.
[55] K. Fujimoto and Y. Takahashi. Tail behavior of the steady-state distribution intwo-stage tandem queues: numerical experiment and conjecture. J. Oper. Res.Soc. Japan, 39:525–540, 1996.
[56] K. Fujimoto, Y. Takahashi, and N. Makimoto. Asymptotic properties of sta-tionary distributions in two-stage tandem queueing systems. J. Oper. Res. Soc.Japan, 41:118–141, 1998.
[57] I. Gertsbakh. The shorter queue problem: a numerical study using the matrix-geometric solution. Eur. J. Oper. Res., 15:374–381, 1984.
[58] W. K. Grassmann. Transient and steady state results for two parallel queues.OMEGA Int. J. Mgmt Sci, 8:105–112, 1980.
[59] W. K. Grassmann. Finding equilibrium probabilities of QBD processes by spec-tral methods when eigenvalues vanish. Linear Algebra and its Applications,386:207–223, 2004.
[60] W. K. Grassmann and S. Drekic. Multiple eigenvalues in spectral analysis forsolving QBD processes. Methodel Comput. Appl. Probab.
[61] W. K. Grassmann and D. P. Heyman. Equilibrium distribution of block- struc-tured Markov chains with repeating rows. J. Appl. Prob., 27:557–576, 1990.
[62] David Anthony Green. Departure processes from MAP/PH/1 queues. PhDthesis, University of Adelaide, January 1999.
[63] Charles M. Grinstead and J. Laurie. Introduction to Probability. America Math-ematical Society, 1997.
[64] F. A. Haight. Two queues in parallel. Biometrika, 45:401–410, 1958.
[65] S. Halfin. The shortest queue problem. J. Appl. Prob., 22:865–878, 1985.
[66] P. R. Halmos. Measure theory. Springer-Verlag, 1998.
[67] L. Hapue, Y. Q. Zhao, and L. M. Liu. Sufficient conditions for a geometric tailin a QBD process with many countable levels and phases. Stochastic Models,1:77–99, 2005.
[68] Qi-Ming He and Hui Li. Stability conditions of the MMAP[k]/G[k]/1/LCFSpreemptive repeat queue. Queueing systems, 44:137–160, 2003.
[69] Qi-Ming He and M. F. Neuts. Two M/M/1 queues with transfers of customers.Queueing systems, 42:377–400, 2002.
[70] G. Hooghiemstra, M. Keane, and Van De Ree. Power series for stationarydistribution of coupled processor models. SIAM J. Appl. Math, 48:1159–1166,1988.
[71] B. V. Houdt and C. Blondia. Analyzing priority queues with 3 classes usingtree-like processes. Queueing syst., 54:99–109, 2006.
[72] G. J. Houtum, I. J. B. F. Adan, J. Wessels, and W. H. M. Zijm. Performanceanalysis of parallel identical machines with a generalized shortest queue arrivalmechanism. OR Spektrum, 23:411–428, 2001.
[73] K. P. Sapna Isotupa and David A. Stanford. An infinite-phase quasi-birth-and-death model for the non-preemptive priority M/PH/1 queue. Stochasitc Models,18(3):387–424, 2002.
[74] J. R. Jackson. Networks of waiting lines. Operations Research, 5:518–521,1957.
[75] Nicolai M. Josuttis. The C++ standard library, a tutorial and reference. Addi-son Wesley Longman, Inc., 1999.
[76] Olav Kallenberg. Foundations of Modern Probability. Springer, 1997.
[77] E. P. C. Kao. An introduction to stochastic processes. Duxbury Press, 1997.
[78] J. Keilson and L. D. Servi. A distributional form of little’s law. Oper. Res. Lett.,7:223–227.
[79] M. Kijima. Quasi-stationary distribution of single-server phase type queues.Mathematics of Operations Research, 18:423–437, 1993.
[80] J. F. C. Kingman. Two similar queues in parallel. Ann. Math. Statist., 32:1314–1323, 1961.
[81] C. Knessl, B. J. Maticowsky Z., Schuss, and C. Tier. Two parallel queues withdynamic routing. IEEE Trans. Comm., 34:1170–1175, 1986.
[82] G. M. Koole. On the use of the power series algorithm for general Markovprocesses, with an application to a petri net. INFORMS Journal on Computing,9:51–56, 1997.
[83] D. Kroese, W. R. Scheinhardt, and P. G. Taylor. Spectral properties of thetandem Jackson network seen as a quasi-birth-and-death process. Ann. Appl.Prob., 14(4):2057–2089, 2004.
[84] D. P. Kroese and V. F. Nicola. Efficient simulation of a tandem Jackson net-work. ACM Transactions on Modeling and Computer Simulation (TOMACS),12:119–141, 2002.
[85] I. A. Kurkova and Y. M. suhov. Malyshev’s theory and JS-Queue asymptoticsof stationary probabilities. Ann. Appl. Prob., 4:1313–1354, 2003.
[86] G. Latouche and Ramaswami. A logarithmic reduction algorithm for quasi-birth-death process. J. Appl. Prob., 30:650–674, 1993.
[87] G. Latouche and P. Taylor. Truncation and augmentation of level independentQBD processes. Stochastic Processes and Their Application, 99:53–80, 2002.
[88] G. Latouche and P. G. Taylor. Level-phase independence for GI/M/1 typeMarkov chains. J. Appl. Prob., 37:984–998, 2000.
[89] G. Latouche and P. G. Taylor. Drift conditions for matrix-analytic models.Math. Operat. Res., 28:346–360, 2002.
[90] Hui Li, Masakiyo Miyazawa, and Yiqiang Q. Zhao. Geometric decay in aQBD processes with countable background states with applications to a join-the-shortest-queue model. Stochastic Models, 23:413–438, 2007.
[91] Q. L. Li and J. H. Guo. Two types of RG-factorizations of quasi-birth-and-deathprocesses and their applications to stochastic integral functionals. StochasticModels, 20:299–340, 2004.
[92] Q. L. Li and C. Lin. Continuous-time QBD processes with continuous phasevariable. Computers and Mathematics with Applications, 52:1483–1510, 2006.
[93] Q. L. Li and Y. Q. Zhao. Heavy-tailed asymptotics of probability vectors ofMarkov chains of GI/G/1 type. Adv. Appl. Prob., 37:482–509, 2005.
[94] Q. L. Li and Y. Q. Zhao. Light-tailed asymptotics of probability vectors ofMarkov chains of GI/G/1 type. Adv. Appl. Prob., 37:1075–1093, 2005.
[95] Q. L. Li, Y. Q. Zhao, and L. M. Liu. An RG-factorization approach for aBMAP/M/1 generalized processor-sharing queue. Stochastic Models, 21:77–99, 2-3 2005.
[96] Zhao Tong Lian and L. M. Liu. A tandem network with MAP inputs. O. R.Lett., 36:189–195, 2008.
[97] Zhaotong Lian, Liming Liu, and Xiaoming Liu. Discriminatory processor shar-ing queues and the DREB method. Stochastic Models, 24:19–40, 2008.
[98] L. M. Liu, M. Miyazawa, and Y. Q. Zhao. Geometric decay in level-expandingQBD models. Ann. Oper. Res., 160:83–98, 2008.
[99] V. A. Malyshev. An analytic method in the theory of two-dimensional positiverandom walks. Sibirskii Math. Zh., 13:1314–1329, 1972.
[100] V. A. Malyshev. Asymptotic behavior of stationary probabilities for two-dimensional positive random walks. Sibirskii Math. Zh., 14:109–117, 1973.
[101] S. P. Meyn and R. L. Tweedie. Markov chains and stochastic stability. Springer-Verlag, 2005.
[102] D. R. Miller. Computation of steady-state probabilities for M/M/1 priorityqueues. Operations Research, 29:945–958, 1981.
[103] M. Miyazawa. A Markov renewal approach to M/G/1 type queues with count-able many background states. Queueing Systems, 46:177–196, 2004.
[104] M. Miyazawa and Y. Q. Zhao. The stationary tail asymptotic in the GI/G/1type queue with countable many background states. Adv. Appl. Prob., 36:1231–1251, 2004.
[105] A. Motyerm and P. G. Taylor. Decay rate for quasi-birth-and-death process withcountable many phases and tri-diagonal block generators. Adv. Appl. Prob.,38:522–544, 2006.
[106] M. F. Neuts. Markov chains with applications in queueing theory, which havea matrix-geometric invariant probability vector. Adv. Appl. Prob., 10:185–212,1978.
[107] M. F. Neuts. The probabilistic significance of the rate matrix in matrix-geometric invariant vectors. J. Appl. Prob., 17:291–296, 1980.
[108] M. F. Neuts. Matrix-geometric solutions in stochastic models: an algorithmicapproach. The Johns Hopkins University Press: Baltimore, 1981.
[109] M. F. Neuts. Some promising directions in algorithmic probability. pages 429–443. In: Advances in matrix analysis methods for stochastic models, Notablepublications, Inc., 1998.
[110] V. Ramaswami. Matrix analytic methods: a tutorial overview with some exten-sions and new results. pages 261–296, New York, 1997. In: Matrix-AnalysisMethods in Stochastic Models, Marcel Dekker.
[111] V. Ramaswami and P. G. Taylor. An operator-analytic approach to product-formnetworks. Stochastic Models, 12:121–142, 1996.
[112] V. Ramaswami and P. G. Taylor. Some properties of the rate operators in leveldependent quasi birth and death processes with a countable number of phases.Stochastic Models, 12:143–164, 1996.
[113] V. Ramswami and G. Latouche. A general class of Markov processes withexplicit matrix-geometric solutions. OR Spectrum, 8:209–218, 1986.
[114] B. M. Rao and M. J. M. Posner. Algorithmic and approximation analysis of theshorter queue model. Naval Res. Log., 34:381–398, 1987.
[115] S. M. Ross. Stochastic processes. John Wiley and Sons Inc., 1981.
[116] S. M. Ross. Introduction to probability and statistics for engineers and scien-tists. Elsevier Academic Press, 3rd edition, 2004.
[117] S. M. Ross. Introduction to probability models. Elsevier Academic Press, 9thedition, 2007.
[118] E. B. Saff and A. D. Snider. Fundamentals of Complex Analysis with Applica-tions to Engineering, Science. Prentice Hall, 3rd edition, 2003.
[119] Y. Sakuma and M. Miyazama. On the effect of finite buffer truncation in atwo-node Jackson network. J. Appl. Prob., 42:199–222, 2005.
[120] Y. Sakuma, M. Miyazama, and Y. Q. Zhao. Decay rate for a PH/M/2 queuewith shortest queue discipline. Queueing Syst., 53:189–201, 2006.
[121] E. Seneta. Nonnegative matrices and Markov chains. Springer, New York,1981.
[122] B. Sengupta. Phase type representation of matrix-geometric solution. Stochas-tic Models, 6:163–167, 1990.
[123] D. H. Shi, J. L. Guo, and L. M. Liu. SPH-distributions and the rectangle itera-tive algorithm. pages 207–224, New York, 1997. In: Matrices-analysis methodsin stochastic models, Marcel Decker.
[124] Dinghua Shi, Qinghua Chen, and Liming Liu. Markov chain-based numericalmethod for degree distributions of growing networks. Phys. Rev. E, 71:036140,2005.
[125] Dinghua Shi, Jinli Guo, and Liming Liu. On the SPH-distribution class. ActaMathematica Scientia, 2:137–160, 2005.
[126] Dinghua Shi, Hongbo Zhang, and Liming Liu. An algorithmic approach fordependent queues. Queueing Syst., Submitted.
[127] Y. Takahashi and N. Makimoto. Geometric decay of the steady-state proba-bilities in a quasi-birth-and-death process with countable number of phases.Stochastic Models, 17:1–24, 2001.
[128] N. S. Tian and Z. G. Zhang. Vacation Queueing Models: Theory and Applica-tions. Spinger, 2006.
[129] S. R. E. Turner. A join the shortest queue models in heavy traffic. J. Appl.Prob., 37:212–223, 2000.
[130] R. L. Tweedie. Operator-geometric stationary distributions of markov chainswith application to queuing models. Adv. Appl. Prob., 14:368–391, 1982.
[131] W. B. van den Hout. The power-series algorithm. PhD thesis, Tilburg Univer-sity, 1996.
[132] J. S. H. van Leeuwaarden and E. M. M. Winands. Quasi-birth-and-death pro-cesses with a explicit rate matrix. Stochastic Models, 22:77–98, 2006.
[133] Haishen Yao and Charles Knessl. On the infinite server shortest queue problem:symmetric case. Stochastic Models, 21:101–132, 2005.
[134] Haishen Yao and Charles Knessl. On the infinite server shortest queue problem:Non-symmetric case. Queueing Systems, 52:157–177, 2006.
[135] Hongbo Zhang and Dinghua Shi. Analysis of two queueing models with ex-plicit rate operators and stationary distributions. Stochastic analysis and appli-cations, Submitted.
[136] Y. Q. Zhao. Censoring technique in studying block-structured Markov chains.pages 417–433, P.Eds., 2000. In: advances in algorithmic methods for Stochas-tic Models, Notable Publications.
[137] Y. Q. Zhao and W. K. Grassmann. The shorter queue problem: a numericalstudy using the matrix geometric solution. Queueing Systems, 8:59–79, 1991.
[138] Y. Q. Zhao, W. Li, and Braun W. John. Censoring, factorization, and spectralanalysis for transition matrices with block-repeating entries. Methodology andComputing in Applied Probability, 5:35–58, 2003.
[139] A. P. Zwart. Queuing systems with heavy tails. PhD thesis, Technische Univer-siteit Eindhoven, September 2001.