马尔可夫骨架过程在GI/G/1排队系统中的应用
|
摘要
在应用随机过程中，排队论无疑是其中极为重要的一类。M／G／1及GI／GI／1排队系统是排队系统中的两个最重要的排队模型。本文首先介绍了马尔可夫骨架过程的基本知识，排队论的现状及排队系统的马氏化及各种遍历性准则。以前排队论多是研究排队过程的平稳分布，即研究普通遍历性，最近，中南大学概率论与数理统计研究所对排队过程的瞬时分布和各种遍历性进行系统研究，本文在此基础上，对M／G／1和GI／GI／1排队进行了处理，得到了如下一些结果。
第一，首先给出了GI／GI／1排队系统队长(L(t)，θ_1(t)，θ_2(t))的瞬时分布所满足的方程，证明了GI／GI／1排队系统队长(L(t)，θ_1(t)，θ_2(t))的概率分布满足二种不同方程，并且是这些方程的最小非负解，进一步给出了其拉氏变换的表达式，还给出了闲忙周期的拉氏变换的表达式，同时对等待时间(W(t)，θ(t))也作了同样的处理。
第二，对M／G／1排队系统，给出了队长(L(t)，θ(t))的Harris遍历，l-遍历，几何遍历的充要条件，同时证明了队长(L(t)，θ(t))不是一致遍历的。
第三，给出GI／G／1排队系统队长(L(t)，θ_1(t)，θ_2(t))及等待时间(W(t)，θ(t))的极限分布及各种遍历性条件。
Queueing theory is a greatly important kind of application stochastic processes. The M/G/1 and GI/G/1 queueing systems are the most typical and the important queueing modes among all the queueing systems. In this dissertation, we first introduce the basic knowledge of Markov skeleton processes, the present condition of queueing theory, and the Markovization of queueing system and the criteria for several types of ergodicity. In the past, the research on queueing system had mostly focused on stability and distribution, that is, the common ergodicity. While recently, the Institute of Probability and Statistics in Central South University has undergone a systematic research on the instantaneous distribution and all kinds of ergodicity. Based on the research, this dissertation has studied the M/G/1 and GI/GI/1 queueing systems, and drew the following conclusions: Firstly, we present the equation which satisfies the transient distribution of the length
of (L(T),θ1(t),θ2(t) for GI/G/1 queueing systems, and proves that the length
(L(t),θ1(t),θ2(t)) for GI/G/1 queueing systems satisfy two types of equation, and are
their minimal nonnegative solutions. Furthermore, we give out not only the expression of Laplace transformation, but also the expression of Laplace transformation of busy-idle period, as well as the equation that satisfies the waiting
time of (W(t),θ(t)).
Secondly, for M/G/1 queueing system, we state the necessary and sufficient conditions of Harris ergodicity, 1-ergodicity, geometric ergodicity of the length of
(L(t),θ(t)), and prove the length of (L(t),θ(t)) is not uniform ergodicity. Lastly, we put forward the limited distribution of the length (L(t), θ1 (t), θ2 (t)) and the waiting time of (W(t),θ(t)) of GI/G/1 queueing system, in the mean time, we obtain the conditions of several kind of ergodicity of the length (L(t),θ1(t),θ2(t))
and the waiting time (W(t),0(t)).
第一，首先给出了GI／GI／1排队系统队长(L(t)，θ_1(t)，θ_2(t))的瞬时分布所满足的方程，证明了GI／GI／1排队系统队长(L(t)，θ_1(t)，θ_2(t))的概率分布满足二种不同方程，并且是这些方程的最小非负解，进一步给出了其拉氏变换的表达式，还给出了闲忙周期的拉氏变换的表达式，同时对等待时间(W(t)，θ(t))也作了同样的处理。
第二，对M／G／1排队系统，给出了队长(L(t)，θ(t))的Harris遍历，l-遍历，几何遍历的充要条件，同时证明了队长(L(t)，θ(t))不是一致遍历的。
第三，给出GI／G／1排队系统队长(L(t)，θ_1(t)，θ_2(t))及等待时间(W(t)，θ(t))的极限分布及各种遍历性条件。
Queueing theory is a greatly important kind of application stochastic processes. The M/G/1 and GI/G/1 queueing systems are the most typical and the important queueing modes among all the queueing systems. In this dissertation, we first introduce the basic knowledge of Markov skeleton processes, the present condition of queueing theory, and the Markovization of queueing system and the criteria for several types of ergodicity. In the past, the research on queueing system had mostly focused on stability and distribution, that is, the common ergodicity. While recently, the Institute of Probability and Statistics in Central South University has undergone a systematic research on the instantaneous distribution and all kinds of ergodicity. Based on the research, this dissertation has studied the M/G/1 and GI/GI/1 queueing systems, and drew the following conclusions: Firstly, we present the equation which satisfies the transient distribution of the length
of (L(T),θ1(t),θ2(t) for GI/G/1 queueing systems, and proves that the length
(L(t),θ1(t),θ2(t)) for GI/G/1 queueing systems satisfy two types of equation, and are
their minimal nonnegative solutions. Furthermore, we give out not only the expression of Laplace transformation, but also the expression of Laplace transformation of busy-idle period, as well as the equation that satisfies the waiting
time of (W(t),θ(t)).
Secondly, for M/G/1 queueing system, we state the necessary and sufficient conditions of Harris ergodicity, 1-ergodicity, geometric ergodicity of the length of
(L(t),θ(t)), and prove the length of (L(t),θ(t)) is not uniform ergodicity. Lastly, we put forward the limited distribution of the length (L(t), θ1 (t), θ2 (t)) and the waiting time of (W(t),θ(t)) of GI/G/1 queueing system, in the mean time, we obtain the conditions of several kind of ergodicity of the length (L(t),θ1(t),θ2(t))
and the waiting time (W(t),0(t)).
引文
[1] Anderson,W.J., Continuous-time Markov chains. Springer Series in Statistics[M], New York: Springer-Verlag,1991.
[2] Bailey, N.T.J., A contiunous time treatment of a simple queue using generating functions, J.Roy.Soc.,B, 1954,16,288-291.
[3] Bhat,U.N.,Nance,R.E.,and Claybrook,B.G., Busy period analysis of a timesharing system:Transform inversion, J.ACM, 1972,19,453-463.
[4] Chen, M.F. and Wang, Y.Z., Algebraic Convergence of Markov Chains, Ann. Appl.Prob., To appear.
[5] Chen, M.F., Eigenvalues,inequalities and ergodic theory (Ⅱ), Advances in Math. (China), 1999,28(6),481-505.
[6] Chen, M.F., Ergodic donvergence rate of Markov processes- Eigenvalues, Inequalities and Ergodic Theory. Proceedings of ICM 2002, Vol.Ⅲ,25-40. Beijing: Higher Education Press, 2002.
[7] Chen, M.F., Estimate of exponential convergence rate in total variation by spectral gap, Acta Math.sin.New Ser.(A),1998 41(1), 9-16.
[8] Chen, M.F., From Markov Chains to Non-equilibrium Particle Systems, Singapore: World Scientific, 1992.
[9] Chung, K.L., Markov chains with stationary transition probabilities[J]. 2nd Springer-Verlag, Berlin, 1967.
[10] Chung, K.L. and Fuchs W.H.J., On the distribution of values of sums of random variables, Mem.Amer.Math.Soc.,1951,6,1-12.
[11] Davis, J.L., Renewal theory from the point of view of the theory of probability, Tran.Amer.Math. Soc., 1948,63,422-438.
[12] Davis,M.H.A, Piecewise-deterministic Markov processes: a general class of non-diffusion stochastic models, J.R. Statist. Soc.B. 1988, 46, 353-388.
[13] Davis, M.H.A, Markov models and Optimization,London:Chaoman and Hall, 1993.
[14] Finch, P.D., On the distribution of gueue size in gueuing problem,Acta Math. Acad. Sci. Hungar.,1959,10,327-336.
[15] Finch, P.D., On the busy period in the gueuing system GI/G/1, J. Aust. Math. Soc.,1961,2,217-228.
[16] Foster, F.G., On the stochastic matrices associated with certain queuing processes, Ann.Math.Statist., 1953,24,355-360.
[17] 侯振挺等，生灭过程，长沙：湖南科学技术出版社，2000．
[18] 侯振挺等，马尔可夫骨架过程．混杂系统模型，长沙：湖南科学技术出版社，2000．
[19] 侯振挺，刘源远，排队过程的马氏化及各种遍历性，待发表．
[20] 侯振挺，Q-过程的唯一性准则[M]，长沙：湖南科学技术出版社，1982．
[21] 侯振挺，邹捷中，张汉君等，马尔可夫过程的Q．矩阵问题[M]，长沙：湖南科学技术出版社，1994．
[22] Hou Zhenting, Markov skeleton processes and applications to queueing systems, Acta Mathematicae Applicatae Sinica,English Series, 2002, 18(4), 537-552.
[23] Hou Zhenting, Yuan Chenggui, Zou Jiezhong et al, Transient distribution of the length of GI/G/n queueing systems, Stochastic Analysis and Applications, 21(3), 2003,567-592.
[24] Hou, Z.T. and Li, X.H., Ergodicity of Quasi-birth and death processes(Ⅰ) (Ⅱ), submitted.
[25] Hou Z.T. Lin X. Wang Y.M., Ergodicity of the queue length L(t) of M/G/1 queueing system, submitted.
[26] Hou, Z.T. and Liu, Y.Y., Explicit Criteria for Several Types of Ergodicity of Markov Chains in M/G/1 Queue with vacations, submitted.
[27] Hou,Z.T. and Liu, Y.Y., Explicit Criteria for Several Types of Ergodicity of Markov Chains in Classical GI/G/n Queue, submitted.
[28] Hou, Z.T. and Li, X.H., Ergodicity of queue length L(t) of M/M/c queue systems with server vacations, submitted.
[29] Hou, Zhenting and Li,Min, GI/G/1 Queueing System.submitted
[30] Hou Zhenting,Wang yimin. Explicit Expression for Laplice Transformation of Transient Queue Length Distribution of GI/G/1 Queuing System,Systems Science and Information,2003(4).
[31] 侯振挺，郭先平，马尔可夫决策过程，长沙：湖南科学技术出版社，1997
[32] Hou, Z.T., Guo,Q.F., Time-homogeneous Markov processes with countable state space[M]. New York: Springer-Verlag,1988
[33] Hou, Zhenting, Liu Zaiming, Zou Jiezhong., QNQL Processes:(H,Q)-processes and their Applications, Chinese Science Bulletin, 1977, 42(11): 881-886.
[34] Hou, Zhenting, Liu Zaiming, Zou Jiezhong., Markov Skeleton Processes. Chinese Science Bulletin, 1998, 43(11): 881-889.
[35] 胡迪鹤，可数状态的可尔可夫过程论[M]，武汉：武汉大学出版社，1983．
[36] 华兴[美]，排队论与随机服务系统，上海翻译出版公司，1987．
[37] Kendall, D.G., Some problems in the theory of queues, J. Roy. Statist. Soc., B,1951,13,151-185.
[38] 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,24,338-354.
[39] Levy, p., Semi-Markovian Processes,Proc:Ⅲ Internat. Congr.Math. (Amsterdam), 1954,416-426
[40] 李民，马尔可夫骨架过程与GI/G/1排队系统：[博士学位论文]．长沙：中南大学，2002．
[41] Li, X.H. and Hou, Z.T., Ergodicity of markov chains of the GI/M/1 type and the application in queue system, submitted.
[42] Li, X.H. and Hou, Z.T., Ergodicity of PH/G/1 Queueing System, submitted.
[43] Li, X.H. and Hou, Z.T., Ergodicity of markov chains of the GI/M/1 type and the application in queue system, submitted.
[44] Li, X.H. and Hou, Z.T., Ergodicity of PH/G/1 Queueing System, submitted.
[45] Liu, Y.Y. and Hou, Z.T., Ergodicity of waiting time and queue length of M/G/1 queueing system with vacations, submitted.
[46] Liu, Y.Y. and Hou, Z.T., Ergodicity of waiting time and queue length of M/G/1 queueing system with vacations, submitted.
[47] Lindley D.V., The theory of gueues with a simgle server, Proc. Camb. Phil. Soc., 1951,48,227-289.
[48] 陆传赉，排队论，北京：北京邮电学院出版社，1994．
[49] Mao,Y.H., Alebraic Convergence for Discrete-time Ergodic Markov Chains, Scientia Sinica, 2003, 33(2), 152-160.
[50] Mao, Y.H., Algebraic Convergence for Dicrete-time Markov Chains, Scientia Sinica, submitted, 2002.
[51] Meyn, S.P. and Tweedie, R.L., Markov Chains and Stochastic Stability Springer-Verlag & Beijing World Publishing Corporation, 1999.
[52] Neuts, M.E, Probability distributions of phase type, in Liber Amicorum Prof. Belgium Univ. Of Louvain, 1975,173-206.
[53] Neuts, M., Matrix-Geometric Solutions in Stochastic Models. Baltimore: The Johns Hopink University Press, 1981.
[54] Saaty, T.J., Time dependent solution of the many server Poisson queue, Operat. Res.,1951,13,151-185.
[55] Serfozo, R, Introduction to stochastic networks, Springer-Verlag, 1999.
[56] 盛友招，排队论及其在计算机通信中的应用，北京：北京邮电大学出版社，1998．
[57] 盛昭翰，王涛，刘德林，非线形时间序列模型的稳定性分析-遍历性理论与应用，北京：科学出版社，1993．
[58] Smith W.L., Regenerative stochastic processes, Proc. Roy. Soc. London, A, 1955, 232, 6-31.
[59] Takács, L., Delay distributions for simple trunk groups with recurrent input and exponential service times, Bell Syst.Tech.J., 1962,41,311-320.
[60] 田乃硕，拟生灭过程与矩阵几何解，北京：科学出版社，2002．
[61] 田乃硕，休假随机服务系统，北京：北京大学出版社，2001．
[62] 吴芳，GI/M/n队列，应用数学学报，1961，11,295-305．
[63] 徐光辉，随机服务系统，北京：科学出版社，1988．
[64] 徐光辉，GI/M/n的瞬时分布性质，应用数学学报，1965，15，91-120．
[65] 严加安，鞅与随机分析引论，上海：上海科技出版社，1981．
[66] 越明义，队列理论中的M/M/s问题，应用数学，1959，9，494-502．
[67] Zhang, H.J.et al, Strong ergodicity of monotone transition functions, Statistic & Probability Letters, 2001,55,63-69.
[68] 张汉君等，标准转移函数的多项式一致收敛，数学年刊，2000，21(3)．351-356．
[69] 张福德，排队论及其程序设计，长春：吉林大学出版社，1986．
[2] Bailey, N.T.J., A contiunous time treatment of a simple queue using generating functions, J.Roy.Soc.,B, 1954,16,288-291.
[3] Bhat,U.N.,Nance,R.E.,and Claybrook,B.G., Busy period analysis of a timesharing system:Transform inversion, J.ACM, 1972,19,453-463.
[4] Chen, M.F. and Wang, Y.Z., Algebraic Convergence of Markov Chains, Ann. Appl.Prob., To appear.
[5] Chen, M.F., Eigenvalues,inequalities and ergodic theory (Ⅱ), Advances in Math. (China), 1999,28(6),481-505.
[6] Chen, M.F., Ergodic donvergence rate of Markov processes- Eigenvalues, Inequalities and Ergodic Theory. Proceedings of ICM 2002, Vol.Ⅲ,25-40. Beijing: Higher Education Press, 2002.
[7] Chen, M.F., Estimate of exponential convergence rate in total variation by spectral gap, Acta Math.sin.New Ser.(A),1998 41(1), 9-16.
[8] Chen, M.F., From Markov Chains to Non-equilibrium Particle Systems, Singapore: World Scientific, 1992.
[9] Chung, K.L., Markov chains with stationary transition probabilities[J]. 2nd Springer-Verlag, Berlin, 1967.
[10] Chung, K.L. and Fuchs W.H.J., On the distribution of values of sums of random variables, Mem.Amer.Math.Soc.,1951,6,1-12.
[11] Davis, J.L., Renewal theory from the point of view of the theory of probability, Tran.Amer.Math. Soc., 1948,63,422-438.
[12] Davis,M.H.A, Piecewise-deterministic Markov processes: a general class of non-diffusion stochastic models, J.R. Statist. Soc.B. 1988, 46, 353-388.
[13] Davis, M.H.A, Markov models and Optimization,London:Chaoman and Hall, 1993.
[14] Finch, P.D., On the distribution of gueue size in gueuing problem,Acta Math. Acad. Sci. Hungar.,1959,10,327-336.
[15] Finch, P.D., On the busy period in the gueuing system GI/G/1, J. Aust. Math. Soc.,1961,2,217-228.
[16] Foster, F.G., On the stochastic matrices associated with certain queuing processes, Ann.Math.Statist., 1953,24,355-360.
[17] 侯振挺等，生灭过程，长沙：湖南科学技术出版社，2000．
[18] 侯振挺等，马尔可夫骨架过程．混杂系统模型，长沙：湖南科学技术出版社，2000．
[19] 侯振挺，刘源远，排队过程的马氏化及各种遍历性，待发表．
[20] 侯振挺，Q-过程的唯一性准则[M]，长沙：湖南科学技术出版社，1982．
[21] 侯振挺，邹捷中，张汉君等，马尔可夫过程的Q．矩阵问题[M]，长沙：湖南科学技术出版社，1994．
[22] Hou Zhenting, Markov skeleton processes and applications to queueing systems, Acta Mathematicae Applicatae Sinica,English Series, 2002, 18(4), 537-552.
[23] Hou Zhenting, Yuan Chenggui, Zou Jiezhong et al, Transient distribution of the length of GI/G/n queueing systems, Stochastic Analysis and Applications, 21(3), 2003,567-592.
[24] Hou, Z.T. and Li, X.H., Ergodicity of Quasi-birth and death processes(Ⅰ) (Ⅱ), submitted.
[25] Hou Z.T. Lin X. Wang Y.M., Ergodicity of the queue length L(t) of M/G/1 queueing system, submitted.
[26] Hou, Z.T. and Liu, Y.Y., Explicit Criteria for Several Types of Ergodicity of Markov Chains in M/G/1 Queue with vacations, submitted.
[27] Hou,Z.T. and Liu, Y.Y., Explicit Criteria for Several Types of Ergodicity of Markov Chains in Classical GI/G/n Queue, submitted.
[28] Hou, Z.T. and Li, X.H., Ergodicity of queue length L(t) of M/M/c queue systems with server vacations, submitted.
[29] Hou, Zhenting and Li,Min, GI/G/1 Queueing System.submitted
[30] Hou Zhenting,Wang yimin. Explicit Expression for Laplice Transformation of Transient Queue Length Distribution of GI/G/1 Queuing System,Systems Science and Information,2003(4).
[31] 侯振挺，郭先平，马尔可夫决策过程，长沙：湖南科学技术出版社，1997
[32] Hou, Z.T., Guo,Q.F., Time-homogeneous Markov processes with countable state space[M]. New York: Springer-Verlag,1988
[33] Hou, Zhenting, Liu Zaiming, Zou Jiezhong., QNQL Processes:(H,Q)-processes and their Applications, Chinese Science Bulletin, 1977, 42(11): 881-886.
[34] Hou, Zhenting, Liu Zaiming, Zou Jiezhong., Markov Skeleton Processes. Chinese Science Bulletin, 1998, 43(11): 881-889.
[35] 胡迪鹤，可数状态的可尔可夫过程论[M]，武汉：武汉大学出版社，1983．
[36] 华兴[美]，排队论与随机服务系统，上海翻译出版公司，1987．
[37] Kendall, D.G., Some problems in the theory of queues, J. Roy. Statist. Soc., B,1951,13,151-185.
[38] 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,24,338-354.
[39] Levy, p., Semi-Markovian Processes,Proc:Ⅲ Internat. Congr.Math. (Amsterdam), 1954,416-426
[40] 李民，马尔可夫骨架过程与GI/G/1排队系统：[博士学位论文]．长沙：中南大学，2002．
[41] Li, X.H. and Hou, Z.T., Ergodicity of markov chains of the GI/M/1 type and the application in queue system, submitted.
[42] Li, X.H. and Hou, Z.T., Ergodicity of PH/G/1 Queueing System, submitted.
[43] Li, X.H. and Hou, Z.T., Ergodicity of markov chains of the GI/M/1 type and the application in queue system, submitted.
[44] Li, X.H. and Hou, Z.T., Ergodicity of PH/G/1 Queueing System, submitted.
[45] Liu, Y.Y. and Hou, Z.T., Ergodicity of waiting time and queue length of M/G/1 queueing system with vacations, submitted.
[46] Liu, Y.Y. and Hou, Z.T., Ergodicity of waiting time and queue length of M/G/1 queueing system with vacations, submitted.
[47] Lindley D.V., The theory of gueues with a simgle server, Proc. Camb. Phil. Soc., 1951,48,227-289.
[48] 陆传赉，排队论，北京：北京邮电学院出版社，1994．
[49] Mao,Y.H., Alebraic Convergence for Discrete-time Ergodic Markov Chains, Scientia Sinica, 2003, 33(2), 152-160.
[50] Mao, Y.H., Algebraic Convergence for Dicrete-time Markov Chains, Scientia Sinica, submitted, 2002.
[51] Meyn, S.P. and Tweedie, R.L., Markov Chains and Stochastic Stability Springer-Verlag & Beijing World Publishing Corporation, 1999.
[52] Neuts, M.E, Probability distributions of phase type, in Liber Amicorum Prof. Belgium Univ. Of Louvain, 1975,173-206.
[53] Neuts, M., Matrix-Geometric Solutions in Stochastic Models. Baltimore: The Johns Hopink University Press, 1981.
[54] Saaty, T.J., Time dependent solution of the many server Poisson queue, Operat. Res.,1951,13,151-185.
[55] Serfozo, R, Introduction to stochastic networks, Springer-Verlag, 1999.
[56] 盛友招，排队论及其在计算机通信中的应用，北京：北京邮电大学出版社，1998．
[57] 盛昭翰，王涛，刘德林，非线形时间序列模型的稳定性分析-遍历性理论与应用，北京：科学出版社，1993．
[58] Smith W.L., Regenerative stochastic processes, Proc. Roy. Soc. London, A, 1955, 232, 6-31.
[59] Takács, L., Delay distributions for simple trunk groups with recurrent input and exponential service times, Bell Syst.Tech.J., 1962,41,311-320.
[60] 田乃硕，拟生灭过程与矩阵几何解，北京：科学出版社，2002．
[61] 田乃硕，休假随机服务系统，北京：北京大学出版社，2001．
[62] 吴芳，GI/M/n队列，应用数学学报，1961，11,295-305．
[63] 徐光辉，随机服务系统，北京：科学出版社，1988．
[64] 徐光辉，GI/M/n的瞬时分布性质，应用数学学报，1965，15，91-120．
[65] 严加安，鞅与随机分析引论，上海：上海科技出版社，1981．
[66] 越明义，队列理论中的M/M/s问题，应用数学，1959，9，494-502．
[67] Zhang, H.J.et al, Strong ergodicity of monotone transition functions, Statistic & Probability Letters, 2001,55,63-69.
[68] 张汉君等，标准转移函数的多项式一致收敛，数学年刊，2000，21(3)．351-356．
[69] 张福德，排队论及其程序设计，长春：吉林大学出版社，1986．
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |