基于马尔可夫骨架过程理论的最小队长排队系统
|
摘要
最小队长排队系统是排队论中一类重要的排队模型,此模型已经应用到信息通讯中的码分多址(CDMA)蜂窝系统.本论文应用由侯振挺等人所创立的马尔可夫骨架过程这一新的理论工具研究了此类排队模型,此论文的内容和主要结果如下:
第一章概述了排队论研究的历史和现状,同时列出了论文的结构及主要结果.
第二章介绍了马尔可夫骨架过程理论,包括马尔可夫骨架过程的概念、向后和向前方程、极限分布等.
第三章研究了M/(G/1)~2型最小队长排队系统,得到此类排队模型队长的瞬时分布和极限分布,并证明了它的瞬时分布是一个向后方程的最小非负解.
第四章分析了GI/(M/1)~2型最小队长排队系统,得到此类排队模型队长的瞬时分布和极限分布,同时证明了它的瞬时分布是一个向后方程的最小非负解.
第五章研究了GI/(G/1)~2型最小队长排队系统,得到此类排队模型队长的瞬时分布和极限分布,并证明了它的瞬时分布是一个向后方程的最小非负解.
The shortest queueing system is one of the important class models in queueing theory, this model has been applied to information and communication in Code Division Multiple Access (CDMA) cellular systems.In this thesis ,apply with the theory of Markov skeleton process ,which is a new theory tools establised by Hou Zhenting etal,to study the shortest queueing system.The content and main result of the thesis as follows:
In chapter 1, the queuing theory research history and the present situation are outlined ,simultaneously has listed the thesis structure and the main result.
In chapter 2,the preliminary knowledge of Markov skeleton process are introduced, including the concept of Markov skeleton process, backward and forward equation, limit distribution, and other important elements.
In chapter 3,study the M/(G/1)~2 type shortest queueing system and the transient distribution and the limit distribution of the queue length of the types queueing model are obtained and prove that the transient distribution is the minimal nonnegative solution of the backward equation.
In chapter 4,analysis the GI/(M/1)~2 type shortest queueing system and the transient distribution and the limit distribution of the queue length of the types queueing model are obtained and prove that the transient distribution is the minimal nonnegative solution of the backward equation.
In chapter 5,study the GI/(G/1)~2 type shortest queueing system, the transient distribution and the limit distribution of the queue length of the types queueing model are obtained and prove that the transient distribution is the minimal nonnegative solution of the backward equation.
第一章概述了排队论研究的历史和现状,同时列出了论文的结构及主要结果.
第二章介绍了马尔可夫骨架过程理论,包括马尔可夫骨架过程的概念、向后和向前方程、极限分布等.
第三章研究了M/(G/1)~2型最小队长排队系统,得到此类排队模型队长的瞬时分布和极限分布,并证明了它的瞬时分布是一个向后方程的最小非负解.
第四章分析了GI/(M/1)~2型最小队长排队系统,得到此类排队模型队长的瞬时分布和极限分布,同时证明了它的瞬时分布是一个向后方程的最小非负解.
第五章研究了GI/(G/1)~2型最小队长排队系统,得到此类排队模型队长的瞬时分布和极限分布,并证明了它的瞬时分布是一个向后方程的最小非负解.
The shortest queueing system is one of the important class models in queueing theory, this model has been applied to information and communication in Code Division Multiple Access (CDMA) cellular systems.In this thesis ,apply with the theory of Markov skeleton process ,which is a new theory tools establised by Hou Zhenting etal,to study the shortest queueing system.The content and main result of the thesis as follows:
In chapter 1, the queuing theory research history and the present situation are outlined ,simultaneously has listed the thesis structure and the main result.
In chapter 2,the preliminary knowledge of Markov skeleton process are introduced, including the concept of Markov skeleton process, backward and forward equation, limit distribution, and other important elements.
In chapter 3,study the M/(G/1)~2 type shortest queueing system and the transient distribution and the limit distribution of the queue length of the types queueing model are obtained and prove that the transient distribution is the minimal nonnegative solution of the backward equation.
In chapter 4,analysis the GI/(M/1)~2 type shortest queueing system and the transient distribution and the limit distribution of the queue length of the types queueing model are obtained and prove that the transient distribution is the minimal nonnegative solution of the backward equation.
In chapter 5,study the GI/(G/1)~2 type shortest queueing system, the transient distribution and the limit distribution of the queue length of the types queueing model are obtained and prove that the transient distribution is the minimal nonnegative solution of the backward equation.
引文
[1] Haight F.A.Two queues in parallel.Biometrica ,1958,2(4):401-410.
[2] Kingman J.F.C.Two similar queues in parallel.Ann Math Statist,1961,5(3):1314-1323.
[3] FlattoL. and McKean H.P.Two queues in parallel.Comm Pure Appl Math, 1977,32(3) : 255-263.
[4] Cohen J.W and Boxman O.J.Boundry Value Problems in Queueing System Analysis. North-Holland :Amsterdam, 1983:65-82
[5] Conolly B.W. The autostrada queueing problem.J Appl Prob,1984,23(2):394-403.
[6] Halfin S.The shortest queue problem.J Appl Prob, 1985,10(2):865-878.
[7] Knessl C Matkowsky Schuss B J Z and Tier C. Two parallel queues with dynamic routing.IEEE Trans Commun, 1986,34(2):1170-1175.
[8] Adan I.J.B.F Wessels J and Zijm W.H.M.Analysis of the symmetric shortest queue problem .Comm Statist Stochastic Models ,1990,12(6):691-713.
[9] Adan I J B F Wessels J and Zijm W H M.Analysis of the asymmetric shortest queue problem.Queueing Systems Theory Appl, 1991,25(8): 1-58.
[10] Adan I van HoutumG.J van der Wal J. Upper and lower bounds for the waiting times in the symmetric shortest queueproblem .Ann Oper Pes, 1994,17(4): 197-217.
[11] Disney R.L and Mitchell W.E.A soloutiong for queues with instantaneou jockeying and other customer selection rules.Naval Research Logistics, 1971,13(7):315-325.
[12] Elsayed E.A and Bastani A.General solutions of jockeying problem.European Journal of Operational Research ,1985,19(2):387-396.
[13] Kao E.P.C and Lin C.A matrix-geometric solution of the jockeying problem.European Journal of Operational Research, 1990,25(4):67-74.
[14] Zhao Y and Grassmann W.K.A solution of the shortest queue model with jockeying in term of traffic intensity ρ. Naval Research Logistics,1990,26(3):773-787.
[15] Adan I.J.B.F Wessels J and Zijm W.H.M.Analysis of the asymmetric shortest queue problem with threshold jockeying. Stochastic Models ,1991,7(1):615-628.
[16] Gertsbakh I. The shoter queue problem -A numerical study using the matrix-geometric solutiong .Eur J Oper Res, 1984,28(1):374-381.
[17] Neuts M.F.Matrix-Geometric Solution in Stochastic Models. Baltimor :Johns Hopkins University Press, 1981:56-156
[18] Foschini G..J and Salz J.A basic dynamic routing problem and diffusion.IEEE Trans Commun,1978,15(6):320-327.
[19]Grassmann W.K.Transient and steady state results for two parallel queues.OMEGA Int J Mgrnt Sci,1980,34(8):105-112.
[20]Rao B.M and Posner M.J.M.Algorithmic and approximation annlysis of the shortest queue model.Naval Res Log,1987,26(3):81-398.
[21]G.Hooghiemstra M.Keane and Van De Ree S.Power series for stationnary distributon of coupled processor models.SIAM J Appl Math,1988,10(4):1159-1166.
[22]Adan I.J.B.F Wessels J and Zijm W.H.M.Matrix-geometric analysis of the shortest queue problem with threshold jockeying.Oper Res Lett,1998,13(6):107-112
[23]侯振挺,刘再明,邹捷中.马尔可夫骨架过程.经济数学,1997a,14(1):1-13.
[24]侯振挺,刘再明,邹捷中.QNQL过程-(H,Q)过程应用及举例.科学通报,1997b,42(9):1003-1008.
[25]侯振挺,刘再明,邹捷中.马尔可夫骨架过程的有限维分布.经济数学,1997c,14(2):1-8.
[26]侯振挺,刘再明,邹捷中.马尔可夫骨架过程.长沙铁道学院学报,1999,17(2):1-10
[27]侯振挺,刘再明,邹捷中,李学伟.马尔可夫骨架过程.科学通报,1999,43(11):881-889.
[28]侯振挺等.马尔可夫骨架过程-----混杂系统模型.长沙:湖南科学技术出版社:2000
[29]Hou Zhenting and Liu Guoxing.Markov Skeleton Processes and their applications.Beijing:Science Press,2005:1-52,92-124
[30]Hou Z.T.Markov skeleton process and application to queueing system.Acta Mathematic Appliatong Sinica,2002,18(4):537-552
[31]Hou Z.T.Transient distributiong of the length of GI/G/N queueing systems.Stochastic nalysis and Applications,2003,21(3):567-592.
[32]Bailey N.T.J.A contiunous time treatment of a simple queue using generating functions.J Roy B,1954,16(2):288-291.
[33]Finch P.D.On the distribution of queue size in queuing problem.Acta Math Acad Sci Hungar,1959,10(1):327-336.
[34]Saaty T.J.Time dependent solution of the many server poisson queue.Operat Res,1951,13(2):151-185.
[35]徐光辉.随机服务系统.北京:科学出版社,1988:25-53
[36]越明义.排队理论中的M/M/s问题.应用数学,1959,9(3):494-502.
[37]Kendall D.G..Stochastic processes occurring in the theory of Queues and their analysis by the methods of the imbedded Markov chain.Ann Math Statist,1953,13(2):338-354
[38]Kendall D.G..Some problems in the theory of queues.J Roy Statist SocB,1951,13(3):151-185
[39]Foster F.G..On the stochastic matrices associated with certainqueuing processes.Ann Math Statist,1953,24(2):355-360.
[40]Takacs L.Delay distributions for trunk groups with recurrent input and exponential service times.Bell Syst Tech J,1962,41(1):311-320
[41]吴方.GI/M/n排队.应用数学学报,1961,11(4):295-305.
[42]Bhat U.N Nance R.E and Claybrook B.G..Busy period analysis of a time-sharing system-Transform inversion.J ACM,1972,19(5):453-463.
[43]Neuts M.F.Probability distributions of phase type in Liber Amicorum prof.Belgium:Univ Of Louvain,1975:173-206.
[44]邓永录,梁之舜.随机点过程及其应.北京:科学出版社,1998:23-56,98-123
[45]Haishen Yao.and Charles Knessl.On the infinite server shortest queue problem:symmetric case.Stochastic Models,2005,21(1):101-132.
[46]Chakranarthy S.R.and Thiaghrajan S.Two parallel finite queues with simultaneous service and Markovian arrivals.Journal of Applied Mathematics and Stochastic Analysis,1997,10(4):383-405.
[47]Cox D.R.The analysis of non-Markovian stochastic process by the inclusion of supplementary variables.Proc Camb Phill Soc,1955,8(2):433-441
[48]王益民.马尔可夫骨架过程在GI/G/n排队系统中的应用[博士学位论文].长沙:中南大学,2002:23-65
[49]何宁卡.马尔可夫骨架过程的极限理论及其应用[博士学位论文].长沙:中南大学,2004:16-23
[50]蒋放鸣.马尔可夫骨架过程及其应用[博士学位论文].长沙:中南大学,2004:13-25
[51]李民.马尔可夫骨架过程GI/G/n与排队系统[博士学位论文].长沙:中南大学,2002:15-32
[52]戴清.马尔可夫骨架过程及其在Frac/G/1排队论中的应用[博士学位论文].长沙:中南大学,2004:10-26
[53]黄奇.马尔可夫骨架过程在可靠性理论中的应用[博士学位论文].长沙:中南大学,2004:45-48
[54]刘娟.马尔可夫骨架过程在有负顾客的GI/G/1重试可修排队系统中的应用[硕士学位论文].长沙:中南大学,2004:23-28
[55]Markov A.A.Extension of the law of large numbers to dependent quantities.IZV FIZ-Matem Obsch Kazan Uni,1906,15(2):135-156.
[56]Levy P.Semi-Marokovian Process.Proc Ⅲ Internet Congr Math(Amst- erdam),1954,25(3):416-426.
[57]Davis M.H.A.A Pieeewise-deterministic Markov process-a general class of no-diffusion stochastic models.J R Statist SocB,1984,12(5):353-388.
[58]Davis M.H.A.Markov Models and Optimization.London:Chapman and Hall.1993:63-89
[59]Kendall D.G.Stochastic process occurring in the theory of queues and their analysis by the methods of the mbedded Markov chain.Ann Math Statist,1953,24(6):338-354.
[60]Takacs L.The transient behavior of a single server queuing process with a poisson input.Proceeding of the Fourth Berkeley symposittm on Mathematical statistics and probality,1960.
[61]侯振挺,郭先平.马尔可夫决策过程.长沙:湖南科学技术出版社,1997:26-59
[62]侯振挺.生灭过程.长沙:湖南科学技术出版社,2000:36-57
[63]严加安.测度论讲义.北京:科学出版社,1988:32-64
[64]盛友招.排队论及其在计算机通信中的应用.北京:北京邮电大学出版社,1998:31-46
[65]侯振挺.马尔可夫骨架过程-混杂系统模型.长沙:湖南科学技术出版社,2000:69-93
[66]钱敏平,龚光鲁.随机过程论.北京:北京大学出版社,1997:31-79
[2] Kingman J.F.C.Two similar queues in parallel.Ann Math Statist,1961,5(3):1314-1323.
[3] FlattoL. and McKean H.P.Two queues in parallel.Comm Pure Appl Math, 1977,32(3) : 255-263.
[4] Cohen J.W and Boxman O.J.Boundry Value Problems in Queueing System Analysis. North-Holland :Amsterdam, 1983:65-82
[5] Conolly B.W. The autostrada queueing problem.J Appl Prob,1984,23(2):394-403.
[6] Halfin S.The shortest queue problem.J Appl Prob, 1985,10(2):865-878.
[7] Knessl C Matkowsky Schuss B J Z and Tier C. Two parallel queues with dynamic routing.IEEE Trans Commun, 1986,34(2):1170-1175.
[8] Adan I.J.B.F Wessels J and Zijm W.H.M.Analysis of the symmetric shortest queue problem .Comm Statist Stochastic Models ,1990,12(6):691-713.
[9] Adan I J B F Wessels J and Zijm W H M.Analysis of the asymmetric shortest queue problem.Queueing Systems Theory Appl, 1991,25(8): 1-58.
[10] Adan I van HoutumG.J van der Wal J. Upper and lower bounds for the waiting times in the symmetric shortest queueproblem .Ann Oper Pes, 1994,17(4): 197-217.
[11] Disney R.L and Mitchell W.E.A soloutiong for queues with instantaneou jockeying and other customer selection rules.Naval Research Logistics, 1971,13(7):315-325.
[12] Elsayed E.A and Bastani A.General solutions of jockeying problem.European Journal of Operational Research ,1985,19(2):387-396.
[13] Kao E.P.C and Lin C.A matrix-geometric solution of the jockeying problem.European Journal of Operational Research, 1990,25(4):67-74.
[14] Zhao Y and Grassmann W.K.A solution of the shortest queue model with jockeying in term of traffic intensity ρ. Naval Research Logistics,1990,26(3):773-787.
[15] Adan I.J.B.F Wessels J and Zijm W.H.M.Analysis of the asymmetric shortest queue problem with threshold jockeying. Stochastic Models ,1991,7(1):615-628.
[16] Gertsbakh I. The shoter queue problem -A numerical study using the matrix-geometric solutiong .Eur J Oper Res, 1984,28(1):374-381.
[17] Neuts M.F.Matrix-Geometric Solution in Stochastic Models. Baltimor :Johns Hopkins University Press, 1981:56-156
[18] Foschini G..J and Salz J.A basic dynamic routing problem and diffusion.IEEE Trans Commun,1978,15(6):320-327.
[19]Grassmann W.K.Transient and steady state results for two parallel queues.OMEGA Int J Mgrnt Sci,1980,34(8):105-112.
[20]Rao B.M and Posner M.J.M.Algorithmic and approximation annlysis of the shortest queue model.Naval Res Log,1987,26(3):81-398.
[21]G.Hooghiemstra M.Keane and Van De Ree S.Power series for stationnary distributon of coupled processor models.SIAM J Appl Math,1988,10(4):1159-1166.
[22]Adan I.J.B.F Wessels J and Zijm W.H.M.Matrix-geometric analysis of the shortest queue problem with threshold jockeying.Oper Res Lett,1998,13(6):107-112
[23]侯振挺,刘再明,邹捷中.马尔可夫骨架过程.经济数学,1997a,14(1):1-13.
[24]侯振挺,刘再明,邹捷中.QNQL过程-(H,Q)过程应用及举例.科学通报,1997b,42(9):1003-1008.
[25]侯振挺,刘再明,邹捷中.马尔可夫骨架过程的有限维分布.经济数学,1997c,14(2):1-8.
[26]侯振挺,刘再明,邹捷中.马尔可夫骨架过程.长沙铁道学院学报,1999,17(2):1-10
[27]侯振挺,刘再明,邹捷中,李学伟.马尔可夫骨架过程.科学通报,1999,43(11):881-889.
[28]侯振挺等.马尔可夫骨架过程-----混杂系统模型.长沙:湖南科学技术出版社:2000
[29]Hou Zhenting and Liu Guoxing.Markov Skeleton Processes and their applications.Beijing:Science Press,2005:1-52,92-124
[30]Hou Z.T.Markov skeleton process and application to queueing system.Acta Mathematic Appliatong Sinica,2002,18(4):537-552
[31]Hou Z.T.Transient distributiong of the length of GI/G/N queueing systems.Stochastic nalysis and Applications,2003,21(3):567-592.
[32]Bailey N.T.J.A contiunous time treatment of a simple queue using generating functions.J Roy B,1954,16(2):288-291.
[33]Finch P.D.On the distribution of queue size in queuing problem.Acta Math Acad Sci Hungar,1959,10(1):327-336.
[34]Saaty T.J.Time dependent solution of the many server poisson queue.Operat Res,1951,13(2):151-185.
[35]徐光辉.随机服务系统.北京:科学出版社,1988:25-53
[36]越明义.排队理论中的M/M/s问题.应用数学,1959,9(3):494-502.
[37]Kendall D.G..Stochastic processes occurring in the theory of Queues and their analysis by the methods of the imbedded Markov chain.Ann Math Statist,1953,13(2):338-354
[38]Kendall D.G..Some problems in the theory of queues.J Roy Statist SocB,1951,13(3):151-185
[39]Foster F.G..On the stochastic matrices associated with certainqueuing processes.Ann Math Statist,1953,24(2):355-360.
[40]Takacs L.Delay distributions for trunk groups with recurrent input and exponential service times.Bell Syst Tech J,1962,41(1):311-320
[41]吴方.GI/M/n排队.应用数学学报,1961,11(4):295-305.
[42]Bhat U.N Nance R.E and Claybrook B.G..Busy period analysis of a time-sharing system-Transform inversion.J ACM,1972,19(5):453-463.
[43]Neuts M.F.Probability distributions of phase type in Liber Amicorum prof.Belgium:Univ Of Louvain,1975:173-206.
[44]邓永录,梁之舜.随机点过程及其应.北京:科学出版社,1998:23-56,98-123
[45]Haishen Yao.and Charles Knessl.On the infinite server shortest queue problem:symmetric case.Stochastic Models,2005,21(1):101-132.
[46]Chakranarthy S.R.and Thiaghrajan S.Two parallel finite queues with simultaneous service and Markovian arrivals.Journal of Applied Mathematics and Stochastic Analysis,1997,10(4):383-405.
[47]Cox D.R.The analysis of non-Markovian stochastic process by the inclusion of supplementary variables.Proc Camb Phill Soc,1955,8(2):433-441
[48]王益民.马尔可夫骨架过程在GI/G/n排队系统中的应用[博士学位论文].长沙:中南大学,2002:23-65
[49]何宁卡.马尔可夫骨架过程的极限理论及其应用[博士学位论文].长沙:中南大学,2004:16-23
[50]蒋放鸣.马尔可夫骨架过程及其应用[博士学位论文].长沙:中南大学,2004:13-25
[51]李民.马尔可夫骨架过程GI/G/n与排队系统[博士学位论文].长沙:中南大学,2002:15-32
[52]戴清.马尔可夫骨架过程及其在Frac/G/1排队论中的应用[博士学位论文].长沙:中南大学,2004:10-26
[53]黄奇.马尔可夫骨架过程在可靠性理论中的应用[博士学位论文].长沙:中南大学,2004:45-48
[54]刘娟.马尔可夫骨架过程在有负顾客的GI/G/1重试可修排队系统中的应用[硕士学位论文].长沙:中南大学,2004:23-28
[55]Markov A.A.Extension of the law of large numbers to dependent quantities.IZV FIZ-Matem Obsch Kazan Uni,1906,15(2):135-156.
[56]Levy P.Semi-Marokovian Process.Proc Ⅲ Internet Congr Math(Amst- erdam),1954,25(3):416-426.
[57]Davis M.H.A.A Pieeewise-deterministic Markov process-a general class of no-diffusion stochastic models.J R Statist SocB,1984,12(5):353-388.
[58]Davis M.H.A.Markov Models and Optimization.London:Chapman and Hall.1993:63-89
[59]Kendall D.G.Stochastic process occurring in the theory of queues and their analysis by the methods of the mbedded Markov chain.Ann Math Statist,1953,24(6):338-354.
[60]Takacs L.The transient behavior of a single server queuing process with a poisson input.Proceeding of the Fourth Berkeley symposittm on Mathematical statistics and probality,1960.
[61]侯振挺,郭先平.马尔可夫决策过程.长沙:湖南科学技术出版社,1997:26-59
[62]侯振挺.生灭过程.长沙:湖南科学技术出版社,2000:36-57
[63]严加安.测度论讲义.北京:科学出版社,1988:32-64
[64]盛友招.排队论及其在计算机通信中的应用.北京:北京邮电大学出版社,1998:31-46
[65]侯振挺.马尔可夫骨架过程-混杂系统模型.长沙:湖南科学技术出版社,2000:69-93
[66]钱敏平,龚光鲁.随机过程论.北京:北京大学出版社,1997:31-79