（运筹学与控制论专业论文）有不成功启动的离散时间重试排队系统.pdf

北京交通大学硕士学位论文 中文摘要 中文摘要 摘要：离散时间重试排队理论足排队论中的一个重要分支近年来，由于离散时间排队系 统在数字通讯系统和网络等些相关领域的应用越来越为广泛，更多的学者致力于离散 时间排队系统的研究许多计算机网络和互联网的运作都是以离散时间为基准的，它们内 部的所有行为都是发生在一些规则的时间点上其实研究离散时间排队理论的重要原因 之一是在模拟计算机网络和通讯系统时，离散时间排队系统比其对应的连续时间排队系 统更为合适，也更贴近于真实的情况在现实生活中，离散时间排队系统已经广泛应用于 模拟计算机和通信网络 在本文中我们一共分析了四个不同的离散时间重试排队系统，分别足有不成功启动 和二次服务的离散时间g 切g 1 重试排队系统、有不成功启动和反馈的离散时间重试排 队系统、有不成功启动和一般重试时间的离散时间重试排队系统、有不成功启动和服务 台不可靠的离散时间重试排队系统，在每个模型中，我们讨论了在这个离散时间重试排队 系统中的马尔可夫链以及它的遍历条件，并计算出了该系统在稳态条件下的一些参数最 后用几个数值例子说明了一些参数对重试空间平均队长的影响另外，在一些模型中，本 文还给出了两个随机分解法则，作为随机法则的一个应用，我们得到了所讨论的系统队长 分布的边界 关键词：离散时间重试排队；二次服务；反馈；可修；随机分解；不可靠服务台 分类号：0 2 2 6 北京交通大学硕七学位论文 a b s t r a c t a b s t r a c t a b s t r a c t ：d i s c r e t e - t i m eq u e u e i n gs y s t e m sw i t hr e p e a t e dc u s t o m e r si 8a ni m p o r t a n tb r a n c ho fq u e u e i n gt h e o r y r e c e n t l y , t h e r ei sag r o w i n gi n t e r e s ti nt h ea n a l y s i s o fd i s c r e t e - t i m eq u e u e sd u et ot h e i ra p p l i c a t i o n si nc o m m u n i c a t i o ns y s t e m sa n do t h e r r e l a t e da r e a s m a n yc o m p u t e ra n dc o m m u n i c a t i o ns y s t e m so p e r a t eo nad i s c r e t et i m e b a s i sw h e r ee v e n t sv a no u l yh a p p e na tr e g u l a r l ys p a c e de p o c h s o n eo ft h em a i nr e a s o n s f o ra n a l y s i n gd i s c r e t e - t i m eq u e u e si st h a tt h e s es y s t e m sa l em o r ea p p r o p r i a t et h a nt h e i r c o n t i n u o u s - t i m ec o u n t e r p a r t sf o rm o d e l l i n gc o m p u t e ra n dt e l e c o m m u n i c a t i o ns y s t e m s n o wd i s c r e t e - t i m eq u e u e i n gs y s t e m sw i t hr e p e a t e dc u s t o m e r sh a sb e e nw i d e l yu s e di n v i e wo ft h e i ra p p l i c a b i l i t yi nt h es t u d yo fm a n yc o m p u t e ra n dc o m m u n i c a t i o ns y s t e m si n w h i c ht i m ei ss l o t t e d i nt h i sp a p e r ，w es t u d yf o u rq u e u e i n gs y s t e m s ，t h a ti 8 ，ad i s c r e t e 一死仇eg e o g 1 r e t r i a lq u e u ew i t hs t a r t i n gf a i l u r e sa n ds e c o n do p t i o n a ls e r v i c e ，ad i s c r e t e t i m er e t r i a lq u e u e 埘冼s t a r t i n gf a i l u r e sa n df e e d b a c k , ad i s c r e t e t i m er e t r i a lq u e u e 砸耽 g e n e r a fr e t r i a lt i m e 8a n ds t a r t i n gf a i l u r e s 。ad i s c r e t e t i m er e t r i a lq u e u ew i 境s t a r t i n gf a i l u r e sa n db r e a k d o w n s i ne a c hm o d e l ，w ea n a l y s et h em a r k o vc h a i nu n d e r l y i n g t h er e g a r d e dq u e u e i n gs y s t e ma n di t se r g o d i c i t yc o n d i t i o n ，t h e n ，w ep r e s e n ts o m ep e r - f o r m a n c em e a s u r e so ft h es y s t e mi ns t e a d y - s t a t e f i n a l l y , s o m en u m e r i c a le x a m p l e ss h o w t h ei n f l u e n c eo ft h ep a r a m e t e r so ns e v e r a lp e r f o r m a n c ed h a r a c t e r i s t i c s i ns o m em o d e l s ， w eg i v et w os t o c h a s t i cd e c o m p o s i t i o nl a w sa n da sa na p p l i c a t i o nw eg i v eb o u n d sf o rt h e p r o x i m i t yb e t w e e nt h es y s t e ms i z ed i s t r i b u t i o n so f o u rm o d e la n dt h ec o r r e s p o n d i n gm o d e l w i t h o u tr e t r i a l s k e y w o r d s ：d i s c r e t e - t i m er e t r i a lq u e u e s ；e s s e n t i a la n do p t i o n a ls e r v i c e ；f e e d b a c k ； r e p a i r ；s t o c h a s t i cd e c o m p o s i t i o n ；u n r e l i a b l es e r v e r c l a s s n o ：0 2 2 6 致谢 首先非常感谢导师王金亭副教授本论文的各项工作都足在王老师的悉心指导和亲 切关怀下顺利完成的两年多来，无论是在基础课学习过程中，还是在论文的选题、研究 以及成文的过程中王老师自始至终都给了我大量的支持和帮助，王老师以渊博宽广的知 识系统、严谨务实的治学态度和把握科学前沿的敏锐洞察力使我受益匪浅；他谦虚正直、 平易近人的长者风范和对学生无微不至的关怀是给我的另一笔人生财富，在此特向王老 师表示深深的敬意和感激 感谢关心我们成长的学校、学院领导，感谢在生活学习上给予我支持和帮助的所有 老师们 感谢同门的师弟师妹们，共同的学习、探讨与合作使我收获多多感谢所有一路走 来、互相勉励的同学和朋友，感谢他们在学习和生活中给予我的关心和帮助 对父母及家人的感激是无法用语言表达的，他们对我的无私支持和鼓励是我前进的 最大源泉和动力 最后，诚谢各位专家和学者在百忙中审阅我的论文，我将诚恳地接受您的宝贵意见和 建议，并期待您的批评和指导 北京交通大学硕士学位论文第一章绪论 第一章绪论 1 排队论和离散时问重试排队理论的发展简介 排队论是运筹学的重要组成部分2 0 世纪初丹麦数学家、电气工程师爱尔朗( a k e r l a n g ) 用概率论的方法研究了电话通话问题，开创了这门应用数学学科，并且建立了许 多基本原则3 0 年代中期，费勒( w f e l l e r ) 弓【进了生灭过程，排队论彳傲数学界承认为一 门重要的学科在二战期间和二战以后排队论成了运筹学这个新领域中的一个重要内 容2 0 世纪5 0 年代初肯德尔( d gk e n d a l l ) 对排队论进行了系统的研究，他使用嵌入马尔 可夫链的方法来研究排队论，使排队论得到了进一步的发展他首先用三个字母组成的符 号表示排队系统2 0 世纪6 0 年代起，排队论所研究的课题日益复杂化，许多问题不是很难 求得其精确解，就是得到的结果非常复杂，不便于应用，因而近似方法的研究成为研究的 主要方向 排队论( 又称随机服务系统) 是研究系统由于随机因素的干扰而出现排队( 或拥塞) 现 象的规律性的一门学科，它的产生与发展均来自实际的需要，这也将决定它今后的发展方 向排队论适用于一切服务系统，尤其在交通与运输系统、计算机、通信系统、存储系统 等方面应用得最为广泛 在过去的很多年里，学者们都专注于研究重试排队系统重试排队系统是指到达的顾 客发现服务台被占用时，进入重试空间( o r b i t ) 等待并重试这样的排队模型在许多现实的 领域也得到了广泛的应用另一方面，离散时间排队模型因为在计算机领域的重要性也 得到了广泛的应用，并且随着电子计算机的不断更新和发展，变得越来越重要， 1 9 5 8 年，m e i s l i a g 首先在离散时间排队系统方向发表了第一篇文章f 1 1 之后有许多学 者在这一基础上做了许多工作f 8 ，1 6 ，3 2 到了1 9 9 5 年，y a a g 和“首次将重试排队拓展到 离散时间排队系统f “1 ，发表了在离散时间重试排队系统领域中的第一篇文章本文就是 在这些基础之上研究了离散时间重试排队系统中四种不同的模型按照不同的模型，本 文共分为五章： 第一章，绪论，介绍排队论的发展史及一些基础知识， 第二章，对有不成功启动和二次服务的离散时间重试排队系统进行分析， 第三章，对有不成功启动和反馈的离散时间重试排队系统进行分析， 第四章，对有不成功启动和一般重试时间的离散时间重试排队系统进行分析 第五章，对有不成功启动和服务台不可靠的离散时间重试排队系统进行分析 2 排队系统的基本概念 产生排队现象的主要因素是由于某些资源、设备或空间( 场地) 的有限性及社会各部 门对它们的需求，而诸如服务机构的管理水平低劣，服务台( 员) 的效率不高，或顾客的无 北京交通大学硕士学位论文第一章绪论 计划性等一些其他因素也造成了一些不该有的排队现象的出现 排队论是研究大量服务过程的- - f l 数学理论，在社会生活中，我们会碰到很多排队现 象，比如到商场购物，在公共电话亭打电话，去图书馆借阅书刊，汽车到汽油站加油，将有 毛病的电器送维修部门维修等这些问题都可看作是顾客与服务台之间的一种服务关系 2 1 排队系统的组成部分 从决定排队系统进程的主要因素来看，排队系统由输入过程与到达规则、排队规则 和服务机构三部分组成 1 输入过程与到达规则，一般情况下，输入过程足用( 顾客) 到达间隔时问来描述 的根据到达间隔时间所服从的分布，输入过程可分为几何输入( b e r n o u l l i 输入) 、定长 输入、( 负) 指数输) k ( p o i s s o n 输入) 、爱尔朗输入、负二项输入与一般输入而到达规则是 指顾客到达系统的方式可以是单个到达、成批到达、依时到达、移态到达等今后如不特 别说明，到达均为单个到达 2 排队规则排队规则一般分为等待制、损失制和混合制在等待制与混合制中通常 又可分为先来先服务( f c f s ) 、后来先服务( l c f s ) 、随机服务( r o s ) 、优先非抢占服务、优 先抢占服务等在混合制中又分为队长( 容量) 有限、等待时间有限此外，还有顾客服务 后反馈以及共同占用、占而不用等等，今后，如不特别说明总认为系统的排队规则为等待 制先来先服务 3 服务机构服务机构主要指服务台的数日，有( 有限) 多个服务台时服务的方式是 并联还是串联，服务时间( 服务一个顾客所用的时间) 服从什么分布服务时间一般分为定 长分布、指数分布、几何分布与一般分布等 2 2 排队系统的表示方法 用x 表示顾客相继到达系统的间隔时间t 的概率分布，y 表示服务时间f 的概率分布， z 表示服务台的个数，m 表示系统内( 最大) 排队容量( 包括正在服务和排队等待的顾客) 又令m 为负指数分布，d 为确定型分布，j k 为阶爱尔朗分布( e r l a n g ) 分布，g 为一般 分布，g i 为一般独立的分布，g e o 为几何分布 通常用记号x y z m ( 或o o ) 来表达排队模型为方便起见，当系统最大排队容量 为。o 时，就可略写为x w z ，比如： g e o g n m 排队模型表示顾客到达的闯隔时间为几何分布，服务时间为一般分布， 有礼个服务窗且系统容量为m 的损失制排队模型 g e d g 1 排队模型表示顾客到达的间隔时间为几何分布，服务时间为一般分布，只设 有一个服务台的等待制排队模型 c l g x l l 排队模型表示间隔时间为一般分布，服务时间为一般独立分布，只设有一个 服务台且系统容量为无限的等待制排队模型 2 北京交通大学硕士学位论文第一章绪论 g e o o e o 1 排队模型表示每批有k 个顾客到达系统，且批与批到达间隔时间是几何 分布，服务时间为几何分布，只有一个服务台，且系统容量为无限的等待制排队模型 g e d g e d n 排队模型表示顾客到达的间隔时间与服务时间均为几何分布，系统内有他 个服务台 2 3 排队系统的主要指标 对一个排队系统的好坏进行评价要从顾客和服务机构两方面利益来考虑对顾客而 言，总希望等待时间或逗留时间越短越好，所以希望服务台个数越多越好但是，对服务 机构而言，增加服务台的个数，就意味着需要加大投资，增加多了要造成浪费，那么增加 多少最为合适呢? 顾客与服务机构考虑到自己的利益，非常关注排队系统中的几个指标： 队长、等待时阅、服务台的忙期因此，这几个指标就成了排队论的主要研究内容 1 ，队长，队长是指系统中的顾客数，也就是正在服务的顾客数与等待服务的顾客数 之和通常要求其分布和前两阶矩， 2 等待时阔，从顾客到达系统时开始算起一直到他被接受服务时为止的这段时间称 为( 该) 顾客的等待时间，而称从顾客到达系统时开始算起一直到他被服务完离开系统时 为止这段时间为顾客的逗留时间，即顾客的等待时间与服务时间之和我们也要求其分布 和前两阶矩 3 忙期忙期是指空闲的服务机构从有顾客到达系统时开始算起一直到服务机构又 没有顾客时为止的这段时间与忙期相对应的是闲期它是指服务机构从开始没有顾客 时算起一直到服务机构又有顾客时为止的这段时间，对于有礼个服务台的系统，通常还要 讨论其k 阶繁忙期从系统中开始有奄个顾客在等待服务时起一直到有一个服务台空闲时 止这段时间称为该系统阶繁忙期零阶繁忙期称繁忙期忙期，闲期、阶繁忙期也是随 机变量一般也要讨论它们的分布与前两阶矩 当然，对于不同的系统，上述三个指标的重要性也是不同的，有时甚至是没有意义的 例如，a e o a e o o o 系统与g e o a e o n n 系统，讨论顾客的等待时间都是没有意义的 3 离散时间马尔可夫链 3 1 定义 设x = 墨) ，n = 0 ，1 ，) 是定义在概率空间( q ，芦，p ) 上而取值在非负整数e = n u o ) 上的随机变量序列，用五；= t 表示时刻n 系统x 处于状态 这一事件则在事件五。= 出现的条件下，事件墨+ l = j 出现的条件概率为 p l j ( = p ( 弼。+ 1 = j 1 = i ) 又称它为系统x 的一步转移概率如果对任意非负整数i - ，i 2 ，“山i ，j 及切n o 有 p ( + 1 = j i = i ，= 砘k = 1 州2 一，礼一1 ) 3 北京交通大学硕士学位论文 第一章绪论 则称x 是一马尔可夫链( m a r 跏c h a i n ) 若p 玎m ) 与起始时刻n 无关，则称x 为齐次马尔 可夫链，并称式( 1 - 3 j 1 ) 为马氏性( 无后效性或无记忆性) ，即在已知”现在”的条件下，”将 来”与”过去”相互独立今后我们考虑齐次马尔可夫链的情形，简记p 玎( n ) 为p 西易知 p o 0 且p o = 1 i 0 p = p o o 量p 0 1 制， d ? = p ( = 引蜀= t ) = p ( + 。= j l x 击= t ) 尸t l = 0 ) 毋0 ，毋= 1 且对，j e ，下述的k 0 1 i i l o g o r o v - c h a p m a 肛方程( 以后简称k c 方程) 成立 砖例= 搿彬 若记砘= p ( x o = ) ，则鼽0 ， 研= 1 ，我们称协，i e ) 为齐次马尔可夫链x 的 初始分布，p ( = t ) 为齐次马尔可夫链x 的绝对概率利用全概率公式及马氏性得 p ( 矗= ) 且当m l 他 o ) 的最大公约数，则称它为状态i 的周期若对一切n2 1 有砖? = 0 ，则约定哦= o o 当吨1 时，称i 是有周期的状态，当d i = 1 时，称i 是非周期的状态，下面介绍几个定 理，证明略去( 本节定理、推论及证明参见【9 】) 定理1 3 1 若i j ，贝l j d i = d j 定理1 3 2 若状态f 有周期面，则必有正整数吖( 与 有关) ，使得对n m ，有p 0 推论1 3 3 若对某一m 0 ，有p 0 ，则对一切充分大的n ，1 劫雾“出 0 3 4 常返性 我们称 学= p ( = j ，x k j ，1 k 0 ，那么，该 马氏链是遍历的，且 是方程组 1 j k 满足条件 知 巧 0 及乃= 1 j = l 的唯一解 定理1 3 7有限马氏链的平稳分布恒存在。 6 “ 。衄 i i 巧 北京交通大学硕士学位论文第二章有不成功启动和二次服务的离散时间重试排队 第二章有不成功启动和二次服务的离散时间重试排队 1 模型的描述 考虑一单服务台离散时间重试排队，将时间轴等间距分割，每一段称作一个时隙( s l o t ) 进一步，在时间轴上标记0 ，1 ，m ，与连续时间排队不同的是，在离散时间排队中到 达和离开同时发生的概率不再足0 ，因此我们有必要设定到达和离开同时发生时的先后 顺序，在以前的文献中，有这样两种规则：( i ) 如果到达在离开之前发生，这样的系统称之 为l a t ea r r i v a ls y s t e m ( l a s ) ；( i i ) 如果离开在到达之前发生，则称之为e a r l ya r r i v a ls y s t e m ( e a s ) 这两个系统还可称之为a r r i v a lf i r s t ( a f ) 和d e p a r t u r ef i r s t ( d f ) 规则在本文中，如 无特别说明我们讨论第二种情形假设队列中的所有活动( 到达、离开、重试和修理) 均发 生在时隙的边界点上为了能够用数学的语言准确的描述这一模型，我们假定离开和修 理的结束点发生在( m 一，m ) ，而到达、重试和失效发生在( m ，m + ) ；也就是说，到达、重试 和失效发生在边界点之后的瞬间，离开和修理的结束点发生在边界点之前的瞬间当然， 我们也可以利用l a s 来研究与本文相同的模型，这样我们会得到一个不同的结果 顾客的到达过程是概率为p 的b e r n o u l l i 至t j 达过程当顾客茔u 达时，发现服务台忙碌或 者损坏，则顾客离开服务区，过一段时间后再回来重试，这些等待重试的顾客构成个 顾客源，称为重试空间( o r b i t ) 一个到达的顾客( 外部的或者重试的) 发现服务台空闲，则 立即启动服务台如果服务台成功启动( 以概率口) ，则顾客立即开始接受服务；如果服务 台没有成功启动( 以概率9 = 1 一疗) ，贝日服务台立即进行修理，同时顾客进入重试空间等 待，当顾客完成第一次( 必须的) 服务时以概率a 决定接受第二次( 选择的) 服务，否则，以概 率画= 1 一。永远离开系统 重试时问( 同一顾客连续两次重试的时间间隔) 服从l r 的几何分布，其中r 表示一个 顾客在一个时隙内没有重试的概率当服务台空闲且在一个时间段内有多个顾客重试时， 系统随机选择一个进行服务，其余顾客回到重试空间继续等待并重试 第一次( 必须的) 服务和第二次( 选择的) 服务的服务时间足独立且任意分布的，分布列 分别为 s - ，。】糊o o 和t 现，t 墨，概率母函数分别为& ( z ) = 。o o 。8 1 ， 和岛( z ) = 墨。s 2 ，t ， 对应的n 阶阶乘矩定义为岛。和岛。 修理时间是独立且任意分布的，分布列为 s 3 ，t ) 罄。，概率母函数为岛( z ) = 。o ；o ，8 3 ，t ， 扎阶阶乘矩为尻。我们还假定修理完成后服务台修复如新 最后，我们假设到达间隔时间、重试时间、服务时闯和修理时间都是相互独立的为 了避免一些平凡的情况，我们定义0 p 1 ，0 r 1 ，0 口墨1 我们将用pi p l4 - o t , 0 2 + 内来定义系统负荷强度，其中p l = 卵1 1 p 2 = 鹏1 内= ；柏1 7 北京交通犬学硕士学伊论文第二章有不成功启动和二次服务的离散时问重试排队 2 马尔可夫链 在时刻m + ( 时间点m 之后的瞬间时刻) ，系统可以描述为 k = ( ，m ) 其中c k 表示服务台的状态( o ，1 ，2 ，3 分别表示服务台空闲，提供第一次( 必须的) 服务，提供 第二次( 选择的) 服务和损坏) ，m 。表示重试空间中的顾客数当c l ，2 时，矗表示正 在服务的顾客的剩余服务时间，当c ，m = 3 时，f m 表示剩余修理时间 定义了上述补充变量，我们发现的下一个状态只取决于现在的状态或者说，给定 了当前的状态，下一个状态只与当前状态有关，而与之前的状态独立可见 义。，m n 是 马尔可夫链，其状态空间是 s = t ( o ，七) ：惫o ；( j ，i ，膏) ：j = l ，2 ，i 1 ，七o ；( 3 ，i ，七) ：i 1 ，k 1 ) 我们要求出这一马尔可夫链的平稳分布 丌o k = u mp 【c k = 0 ， r m = 明；i 1 ，k 0 i ，2 土骢p = 1 ，靠= i ，仇2 蜘1 ，k o ，j = 1 ，2 丌3 ， ，= 1 1 巴p f o ；= 2 ，厶= ，n m = 叫， 1 ，k i 下面给出系统的一步转移概率： 当七o 时 当i 2l ，奄0 时 p ( o ) ( o ，k ) = 矽2 ， p ，) ( o ，砷= 却矿， p ( 2 ，1 ) ( o ，k ) = 刀， p ( 3 ，1 ，k ) ( o ，) = 劈，( k 1 ) p ( o ， ) ( 1 ， ，) = p o s l ，t ， p ( o ，1 ) ( 1 ，t 。k ) = 箩( 1 一t k + 1 ) o s l ，t ， p ( i ，1 ，女) ( 1 ，i ，k ) = 丘p o s l ，t ， p ，+ 1 ) ( 1 ，自) = 丘多( 1 一r k + 1 ) 0 8 1 j ， p ( t ，i + i 。i 1 ) ( 1 ， ，) = p ，( 21 ) p ( i ，i + 1 ，女) ( 1 ，t ，k ) = 死 p ( 2 ，1 ，k ) ( 1 ，i ，女) = p o s l i ， 8 i ! 塞銮望盔兰鉴主兰垡笙奎 箜三童壹至堕塑塞垫塑三堡墨箜笪塞墼壁堡星垡鲎坠 当i 1 ，k o 时 当i 1 ，k 1 时 p ( 2 ，1 ，缸 1 ) ( 1 ，t ，k ) p ( s ，1 七) ( 1 ，i ，i ) p ( n ，l ， 十1 ) ( 1 j ， ) p c i ，1 ，k 1 ) ( 2 ，t ，柚 p ( i ，1 ，) ( 2 j ，脚 p ( 2 ，i + l ，k l 】( 2 ， ，k ) f ( 1 一r “) e s l i ， p o s i ，f ，( k 21 ) 箩( 1 一r k + 1 ) o s l - i ， o c s 2 ，擅，( k 2 1 ) 0 1 8 2 巾， p ，( k 1 ) p ( 2 ，i + l ，姊( 2 j ，) = 争 p ( e ， 一1 ) ( 3 ，i ，耐 p ( o ，砷( 3 ，i ，) p o 。1 ，k - 1 ) ( 3 。 ，女) p ( 1 ，1 k ) ( 3 ，k ) p ( 2 ，l ，k 一1 ) ( 3 ，q p ( 2 ，1 ，) ( 3 ，t ， p ( a ，1 ， 一1 ) ( 3 ，t ，助 p ( 3 ，1 ，( 3 t ，七) p ( a ，t + 1 ，k 一1 ) ( 3 ，t ，) p e s 3 如 声( 1 一r k ) 翰t | 5 f p o s a ，i ， a p ( i r k ) 夙3 ， p o s a , i ， p ( i r e ) 伊s 3 ， p o s a 南2 ) 声( 1 一矿) 如3 南 p ，( 2 ) p ( 3 ，件1 ，的( 3 ，t ，k ) = 声 其中多= 1 一p 易得平稳状态时的柯尔莫哥洛夫方程如下 7 f o ，老= 矽奄丌o ，毛+ a 矽七吼，1 ，是+ 加七毙，l 毒+ ( 1 一五味) 矽7 r 3 ，i ，蠢，k 0 ，( 2 2 ，1 ) 7 r l ，t ，k= p o s i ， 7 r 0 ，k + 庐( 1 一r 七+ 1 ) o s l ， 7 1 0 ，k + 1 + 5 e p o s l ，t 丌l ，1 知 7 r 2 ，t 。2 功 t 2 + s p ( 1 一r k + 1 ) o s l ， 丌1 ，1 ，1 + ( 1 5 0 ) p r l ，件1 ，k 一1 + 痧7 r 1 ，件i + p p s l ，i 丌2 ，1 ，k + p ( i r k + 1 ) 口5 1 ，l 丌2 ，1 ，k + 1 + ( 1 5 0 k ) 矽s l ，l 砚，1 ， + 声( 1 r k + 1 ) 口旬。i 和，i ，t + l i021 ，k o ) ( 1 6 j 七) 8 粤2 ，i f 坷l ，1 ，一1 + 口8 2 一雪时l ，l ，蠹+ ( 1 一品) p 丌2 ，+ l ，寿一i + 乒丌2 ，i + 1 k ，i 2 1 ，k 0 ， p 每5 3 ，f 7 r 0 ，七一l + 声( 1 一r k ) 如3 ， 丌0 ，七十a p 如3 7 r l ，1 ，七一l + d 眵( 1 一r ) ，f 1 ，l ，女+ p 如3 ，f 丌2 ，l ，一1 + 乒( 1 一r ) 踽，f 他，l 。 9 ( 2 2 2 ) ( 2 2 3 ) 北京交通夫学硕士学位论文 第二章有不成功启动和二次服务的离散时间重试摊双 + ( 1 5 1 k ) p 日s 3 ，i 7 r 3 ，1 ，k 一1 + 声( 1 一i - k ) 口s 3 ，i 7 e 3 ，1 ，k + ( 1 一矗詹) 矽3 f + i ，膏一l + 多_ 7 f 3 ，i + 1 ，七；( i 1 ，k 1 ) ( 2 2 4 ) 一致化条件为： 孤t + ，m + 嘶，* = 1 k = o j = li = 1k = 0 i = 1 七二1 为了求解这一方程组，我们引入如下母函数： 及辅助母函数 o o 锄，t ( 。) = 丌j ，讪，o 1 ，j = 1 ，2 ) ；孙( z ) = 7 r 3 j , k z k ，o 1 ) k = o k = 1 将( 2 2 1 ) 一( 2 2 4 ) 式同乘以扩，然后对求和得： 幽( ：) = 痧 如p z ) + 丘1 ，l ( r z ) + 如，i ( r 刁+ 也，1 ( r z ) 1 ( 2 2 ，5 ) 妒1 ，t ( 。) = p + p z ) 咖1 ，件，( 2 ) + p + 一p z o s l , i ( 2 ) + 画垂l ，1 0 ) + 如，l ( 2 ) + 九，1 ( z ) 】 也。( z ) = 如，t ( 。) = 一：口s r z ) + a 虮( r z ) + 加，- ( r z ) + ( r z ) 】， a s 2 + p z ) l ，1 ( z ) + 归+ p z ) 也一+ 1 ( 名) ， ( 2 2 6 ) ( 2 2 ，7 ) 眵+ p z ) 3 j + 1 ( z ) + ( p + p z ) g s s ， 睁o ( z ) + 丘l ，1 ( z ) + 也，l ( z ) + 8 ，l ( z ) 】 一参蠡3 j p ：) + 画妒l ，l z ) + 锄，( r z ) + 如，l p z ) ! ( 2 2 8 ) 将( 2 2 5 ) 式代入( 2 ，2 6 ) ( 2 2 8 ) 式得： 妒。j ( 。) ：p + p 。) 。，件，( 。) 一! 兰p 口s 。，t 粕( z ) + 旦：；丝8 s 1 ，d a 1 ，1 0 ) + 妒2 1 ( z ) + 拓，1 ( 2 ) ， ( 2 2 9 ) 九，( z ) ：p + ) 九冉。( z ) 一( 1 一= ) p 口5 3 ，i 如( z ) + 十p z ) o s 3 ，t 陋庐1 ，1 ( z ) + 也1 ( z ) + 也，1 ( z ) 】 ( 2 2 1 0 ) 将( 2 2 7 ) ( 2 2 9 ) ( 2 2 1 0 ) 式同乘以，然后对i 求和得： 粤邋撕，。) ：乏娑p s 。( 茁) ( 。) + 也荆】+ 旦【a 口s 。( z 卜z ( z ) 一三二三矽蜀( 功如( 孑) ， ( 2 2 1 1 ) 芝二堕；去里生庐。 ，z ) = o 晒+ p 2 ) 岛( z ) 砂l ，1 ( z ) 一p + p z ) 咖。，( z ) ， ( 2 2 1 2 ) 曼冬= 塑九( 。，z ) = 悔+ p z ) 睁岛( z ) 1 3 ，。( z ) + 瞄+ p z ) 日岛( z ) 【a ，1 ( 2 ) + 也，( z ) 】 1 0 艚n 汹 = 力 九 一一0 触 吁 脚 ：l j i 力 咖 k 膨札 脚 = 力 粕 北京交通大学硕士学位论文 第二章有不成功启动和二次服务的离散时间重试排队 一( 1 一z ) p p 5 如) 如( 2 ) ，( 2 2 1 3 ) 在( 2 2 1 1 ) 一( 2 2 1 3 ) h b ，令茹= 痧- b p z 得： ( 1 一z ) p o s - 晒+ p z ) 咖o ( z ) = + 形) 陋口毋侮4 - p z ) 一z 】1 ，l ( z ) + ( f + p z ) o s l ( 芦+ p z ) 也，l ( z ) + 妒3 ，1 ( 。) l ，( 2 2 1 4 ) q + p z ) s 2 + p z ) 驴l ，l ( z ) = ( 声+ p z ) 2 ，1 ( z ) ， ( 2 2 1 5 ) ( 1 一z ) p 目岛p + p z ) o ( z ) = ( 多+ p z ) 口岛 + p z ) 陋庐1 ，l 如) + 咖2 ，1 ( z ) 】 十( 乒+ p z ) e s 3 ( 芦+ p z ) 一l 】庐3 ，l ( z ) ( 2 2 1 6 ) 下面给出两个引理，证明很容易得到，我们将在后面用到它们 引理2 2 1 当o 。1 时，不等式s l ( x ) 而岛( 茁) 卫，& ( z ) 茁成立 证明 由母函数s 1 ( z ) ，岛( 茁) ，s 3 ( z ) 的凸性即可得引理成立 口 引理2 2 2 ( 1 ) 当p l 十叩2 + 船 o ( o z 1 ) ( 2 ) 当p 1 + n 砌+ , 0 3 l 时，下列极限存在且是正的： 1 一z1 罂蕊虿瓦弧i 蕊万再珂再磊万雨5 硒i 再五再面 证明考虑 ( z ) = e s l i p + p z ) a + q s 2 惰+ p z ) 】+ z 伊岛p + p z ) ，我们可以得当p 1 + n p 2 + p s 1 时， ( a ) v ( o ) = 目& ( 司幢+ 口岛( 囝) ( b ) v ( 1 ) = l ( c ) t ，7 ( 1 ) = 口p 卢1 ，1 + o p a b 2 1 + 0 + 确，1 0 因为幻( 0 ，1 ) ，。) = 硒，与上述性质矛盾，因此引理2 2 2 中的( 1 ) 成立( 2 ) 可 由( 1 ) 中不等式和罗必塔法则得到 口 由( 2 2 1 4 ) 一( 2 2 1 6 ) ，我们可以得到母函数 1 1 ( z ) = 岛侮+ p z )卵( 1 一z ) 庐o ( z ) 1 可西万再研再五双再面丽砑瓯万百万i ( 2 2 1 7 ) 屯出) = 警铲砀而筹葛觜希糍b 再 ( 2 2 埘 加荆= s 3 再( p + 面p _ z ) 两再两面丽p o z 万( 1 - 再z ) 而o ( z 丽) 丽雨( 2 2 1 9 ) 将咖1 ，1 p z ) ，也，i ( r z ) ，庐3 ，l ( z ) 代入( 2 2 5 ) 式得： 纰，= 器端酱篇簿钱筹浆舞乒嵩撇z ， 北京交通大学硕七学位论文第二章有不成功启动和二次服务的离散时间重试排队 = g ( r z ) 妒o ( r z )( 2 2 2 0 ) 由上式我们可以得到( z ) = 粕( o ) i l 。g ( 一z ) t e l - l 。g ( r 2 ) 收敛 引理2 2 3 当p l + o l p 2 + p 3 i 时，n 圣lg ( 产2 ) 收敛 证明 首先，我们将g ( z ) 变形为 o ( z ) = 1 + f ( z )( 2 2 2 1 ) 其中 耶，= 蔫兹翁赫装蛊高蜴辩弘 由引理2 ，2 2 和不等式 庐+ p 。一日s 1 + p z ) 陋+ o 岛归+ p z ) 】一z 百岛( f + p z ) 口 乒+ p z 一品( 乒+ p z ) 陋+ a 岛( 乒+ p 名) 】) + 百防+ p z s 3 晤+ p z ) 】0 易得，当o z 1 时，f 0 ) 0 当且仅当p l + 口融+ p a i 考虑等式( 2 2 2 i ) ，可以写成下述形式 o ( r ) = i i i i + f ( r “z ) 】 ( 2 2 2 2 ) 因为f m 。_ + o 。! ；毒孚= r 1 ，所以级数n 芒1f ( r z ) 收敛( 2 2 2 2 ) 式收敛当且仅当级 数n 墨1f ( r z ) 收敛，所以引理得证 口 现在，将( 2 2 1 7 ) 一( 2 2 ，1 9 ) 式代入( 2 2 i i ) 一( 2 2 1 3 ) 得母函数： 讹；) = 宝蔷半篡产瓯而覆丽p 厨z ( i - 翮z ) o 而丽面一删， 卿力= 掣i 辫笋丽葡嵩高答祭而再蝴 嘶= 等器砥而丽菡簧筹丽丽批卜 由一致化条件钆( 1 ) + 妒1 ( 1 ，1 ) + 锄( 1 ，1 ) + c a ( 1 ，1 ) = 1 得( 1 ) = 1 一p ，由此可得加( o ) 我们总结上述结果可得下面的定理 定理2 2 4 当且仅当p 1 时，马尔可夫链 溉，m n ) 足遍历的且有如下母函数： 坼) 刈刊氍错， 纵) = 掣群丽面研焉筹辫两而再蝴 似酃) = 掣i 辫笋面雨群鬻簿嘉而面一似巩 北京交通大学硕士学位论文第二章有不成功启动和二次服务的离散时间重试排队 撕，z ) = 篝兰吾半篡产砥面而鑫意端锄丽再再川， ，= 器恭罄器篙装蒜篙端乒 推论2 2 5 ( 1 ) 当服务台空闲时，重试空间中顾客数的概率母函数为如( 。) ( 2 ) 当服务台忙碌时，重试空间中顾客数的概率母函数为 纵m m 沪器篙舞戡篝器擀州z ， ( 3 ) 当服务台损坏时，重试空间中顾客数的概率母函数为 卿，加丽瓦毒篆筹幕两再似n 皿( 2 ) = 如( z ) + 毋1 ( 1 ，z ) + 也( 1 ，z ) + 庐3 ( 1 ，z ) = 蕊万再现再i 蠹享身f 丽丽i 雨j 似。)5 两万再研葫乏甄再面丽刁瓦f i 丁乏伽婶j ( 5 ) 系统队长的概率母函数为 垂( z ) = o ( z ) + z 1 ( 1 ，z ) + z 2 ( 1 ，z ) + 庐3 ( 1 ，z ) = 丽襻端畿p z 希) z o 赫p z 似z ， 口p + p 2 ) 陋+ o 归+】+岛 +) 一z “、7 推论2 2 6 ( 1 ) 服务台各个状态的稳态分布分别为 粕( 1 ) = 1 一p ，妒1 ( 1 ，1 ) = p l ，也( i ，1 ) = d 见，( 1 ，1 ) = m ( 2 ) 重试空间队长及系统队长的均值分别为 踟= 丝塑等窨塾型+ 砉鬻 e f 纠= ( p l + q 纯) + f 明， ( 3 ) 顾客在系统中的平均时间为 ：型 p 注2 2 7 由上我们有圣( 。) = 皿( 2 ) 舅p + 矽) 陋+ & p + ) 】，因此有 n 圣”( 1 ) = ( 獬p ”( 儡，。+ 确，。) 雪协一”( 1 ) ，嚣1 娄窒銮堕查兰堡主堂堡笙奎 蔓三童查至壁望塞塑塑三盗壁箜盟塞塑壁塑重茎笙坠 其中圣( “) ( 1 ) 和m ( “) ( 1 ) 分别是随机变量l 和分布的n 阶矩 注2 2 8 服务台各个状态躲稳态分布 妒o l l j 。1 一p ，1 【1 ，1 ) 5p l ，妒2 ( 1