（运筹学与控制论专业论文）关于mmpp（2）到达的两个排队系统分析.pdf

摘要 关于m m p p ( 2 ) 到达的两个排队系统分析 摘要 本文分别研究了具有纯有限服务单假时间的m m p p ( 2 ) e 2 1 的排队模型和反馈 次数服从几何分布的m m p p ( 2 ) g 1 的排队模型。两个模型均是关于m m p p ( 2 ) 到 达，m m p p ( 2 ) 是较e l a n g 分布和尸日分布等到达间隔更为广泛的一类马尔可夫到达。 具有纯有限服务单假时间排队模型和反馈次数服从几何分布的排队模型已经得到许多 学者的研究，获得了不少成果。但对上述排队系统引入m m p p ( 2 ) 到达，这在国内外 公开发表的文献中还未曾见到。 针对上述情况，本文采用递推方式给出了马尔可夫过程的转移矩阵，并利用矩阵 分析方法进行求解，分别得至： j - - y m m p p ( 2 ) e 2 i ( p l ，s v ) 系统的业务量强度以及系统 的忙期，任何时刻系统为空的概率以及等待时间指标。也得到了反馈次数服从几何分 布的m m p p ( 2 ) g 1 的排队模型平稳条件、平均队长、忙期的平均长度以及在一个忙 期内服务完的平均顾客数。 关键词：排队系统，m m p p ( 2 ) ，反馈，母函数，相位 a b s t r a c t t w oq u e u e i n gs y s t e m sa r es t u d i e di nt h i sa r t i c l e ，o n ei sm m p p ( 2 ) e 2 1q u e u e - i n gs y s t e mw i t hp u r el i m i t e da n ds i n g l ev a c a t i o n ，t h eo t h e ri sm m p p ( 2 ) g 1q u e u e - i n gs y s t e mw i t hf e e d b a c kt i m e sh a v i n gg e o m e t r i cd i s t r i b u t i o n b o t hs y s t e m sa r ea b o u t m m p p ( 2 ) a r r i v a lp r o c e s s e s m m p p ( 2 ) a r r i v a li sak i n do fm o r ew i d e l yu s e dm a r k o v i a n a r r i v a lp r o c e s s e st h a nt h a to fe r l a n g - a n dp h - d i s t r i b u t i o n s t h eq u e u e i n gs y s t e mw i t h p u r el i m i t e da n ds i n g l ev a c a t i o n ，b e s i d e st h eq u e u e i n gs y s t e m sw i t hf e e d b a c kt i m e sh a v i n g g e o m e t r i cd i s t r i b u t i o nh a v eb e e ns t u d i e db ym a n yr e s e a r c h e r sa n dal o to fr e s u l t sh a v e b e e no b t a i n e d h o w e v e rb o t hs y s t e m sw i t hm m p p ( 2 ) a r r i v a lp r o c e s s e sh a v en o tb e e n s t u d i e di no p e nl i t e r a t u r e s f o rt h i sr e a s o n ，t h eg e n e r a t o rm a t r i xo fm a r k o v p r o c e s si sg i v e ni nr e c u r r e n c ef o r m u 1 a t i o n ，t h et r a f f i cd e n s i t y ，t h eb u s yp e r i o d ，t h ep r o b a b i l i t yf o rt h es y s t e mt ob ei d l ea ta n y t i m ea n dt h ew a i t i n gt i m eo fm m p p ( 2 ) e 2 i ( p l ，s v ) q u e u e i n gs y s t e ma r eo b t a i n e d b ym e a n so fm a t r i xa n a l y s i st h e o r ya n dp r o b a b i l i t yt h e o r y a tt h es a m et i m e ，t h es t e a d y c o n d i t i o n ，t h em e a nq u e u el e n g t h ，t h em e a nb u s yp e r i o dl e n g t h sa n dt h ea v e r a g ea m o u n t o fc u s t o m e r sb e i n gs e r v e di nt h eb u s yp e r i o do fm m p p ( 2 ) g 1s y s t e mw i t hf e e d b a c k t i m e sh a v i n gg e o m e t r i cd i s t r i b u t i o na r eo b t a i n e d k e y w o r d s ：q u e u e i n gs y s t e m ，m a r k o v - m o d u l a t e dp o i s s o np r o c e s s e sw i t ht w os t a t e s ， f e e d b a c k ，g e n e r a t i n gf u n c t i o n ，p h a c e i i 声明尸明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名：遂至玺酉硼g 年了月f 日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的全部或部分内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的全部或部分内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名：盖篮耳 前年了月日 硕士学位论文关于m m p p ( 2 ) 至t j 达的两个排队系统分析 第一章绪论 1 1 排队论简介 排队论( q u e u e i n gt h e o r y ) 是研究系统随机聚散现象和随机服务系统工作过程的数学 理论和方法，又名随机服务系统理论，为运筹学的一个重要分支，它主要研究由于顾 客的到达和离开以及服务器的工作和休假，而引起的队伍积累和消散的问题，解决相 应排队系统的最优设计和最优控制问题。 排队论起源于2 0 世纪1 0 年代后期丹麦工程师爱尔朗( a k e r l a n g ) 的一篇论 文s o l u t i o no fs o m ep r o b l e m si nt h et h e o r yo fp r o b a b i l i t yo fs i g n i f i c a n c ei na u t o m a t i c t e l e p h o n ee x c h a n g e s ，该篇文章是针对电话交换机的使用情况进行分析的，当时称为 话务理论。他在热力学统计平衡理论的启发下，成功地建立了电话统计平衡模型，并 由此得到组递推状态方程，从而导出了著名的爱尔朗电话损失率公式。因此排队论 问题最初是从通信中提炼出来的，在这以后，通信始终是排队论发展的重要推进力量 和源泉。 爱尔朗之后从事排队论研究的先驱人物有法国的f p o l l a c z e k 和俄国数学家金 勤( a k h i n c h i n ) ，他们有关排队论的工作主要在2 0 世纪3 0 年代，前者主要研究泊松型输 入，一般服务时间的单服务台和多服务系统，后者的贡献主要是在数学理论上把排队 系统更加系统化。2 0 世纪5 0 年代初期英国数学家肯德尔( k e n d a l l ) 等人通过引入排队过 程的嵌入马尔可夫链( e m b e d d e dm a r k o vc h a i n ) 这一有用工具，大大推动了排队论的 进一步发展。进入2 0 世纪6 0 年代后，随着应用广度和深度的发展，作为嵌入马尔可夫 链的发展和补充，人们引入了马尔可夫更新过程模型和补充变量的方法，该方法通过 增加变量，构造向量马氏过程( v m p ) ，从而建立密度演化方程，并求解各种统计特征 量。到3 2 0 世纪7 0 年代，由于实际问题的复杂性，往往不能用某种已有的数学模型来 描述，并且给出问题的精确解变的越来越困难，因而排队论的研究重点逐渐由寻找排 队问题的精确解转移到新的数学模型的建立和近似法的研究。 】 第1 章绪论硕士学位论文 排队论的产生与发展来自于现实生活的需要，实际的需要必将决定它今后的发展 方向，排队论的应用范围很广，它应用于一切服务系统，尤其在通讯系统、交通系 统、计算机、存储系统、生产管理等方面应用得最多。 排队系统尽管干差万别，但都可以抽象为：顾客按照一定的分布率到达，然后按 照特定的排队规则依次等候一定数量的服务器为其服务。服务器的服务时间按照一定 的分布进行且与顾客的到达相互独立，顾客被服务结束后，离开排队系统。 一个排队系统可以通过以下五个特征来描述： ( 1 ) 顾客到达的时间间隔分布； ( 2 ) 服务器的服务时间分布： ( 3 ) 排队规则：顾客到达后接受服务的先后次序。例如先进先出( f i f o ) ，即先到达 的顾客先接受服务；后进先出( l i f o ) ，即最后到达的顾客先接受服务等等。 ( 4 ) 队伍容量七，庇o ； 队伍中的顾客数至多可达七，即队长达到忌后，队伍不再接纳任何顾客，直到队伍 中某顾客接受完服务后离开系统，使得队长小于容量七。 ( 5 ) 服务器个数，n 1 。 排队系统的符号表示： 沿用k e n d a u ( 1 9 5 1 ) 采用的表示方法，一个排队过程通常采用符号a b x y z 作 为记录的标准，其中a 表示顾客到达间隔时间分布的类型，b 代表服务器服务 时间分布的类型，x 表示服务器个数，y 表示队伍的容量，z 代表排队规则。例 如m d 1 o o l i f o 表示顾客按照指数分布间隔到达排队系统，服务器服务完一个顾 客的时间服从定长分布，1 个服务台，队列按照最后进入系统的顾客先接受服务的规律 排列，队列的长度不加限制的排队系统。 排队系统问题的求解： 研究排队系统问题的主要目的是研究其运行效率，考核服务质量，以便据此提出 改进措施。通常评价排队系统优劣有7 项数量指标： 2 硕士学位论文 关于m m p p ( 2 ) 至：i j 达的两个排队系统分析 ( 1 ) 系统的负荷水平p ：它是衡量服务台在承担服务和满足需要方面能力的尺度： ( 2 ) 系统的空闲概率：系统处于没有顾客来到要求服务状态的概率； ( 3 ) 忙期：即服务机构连续繁忙的时期。这是与服务机构直接有关的，关系到他们 的工作强度； ( 4 ) 队长：系统中排队等待服务和正在服务的顾客总数； ( 5 ) 等待队长：系统中排队等待服务的顾客数； ( 6 ) 等待时间：从顾客到达时起直到他开始接受服务时止这段时间。这对顾客来说 是最为关心的，因为每个顾客都希望他的等待时间愈短愈好； ( 7 ) 逗留时间：一个顾客在系统中的停留时间，包括等待时间和服务时间。 自排队论这门学科形成以来，新的研究方向和研究方法层出不穷。大量的科研工 作者在此领域取得了丰硕的成果。排队论专家田乃硕等把矩阵解析法引入休假排队系 统，并研究了部分服务台同步的休假排队模型，极大的丰富了排队模型的理论；史定 华将频度转移法用于可修服务系统并且对可靠性作了大量工作；g e l e n b e 将负顾客引入 排队系统。当前，排队论的研究主要集中在排队网络、矩阵解析法、数值计算、极限 定理以及特殊模型等方面。 排队论经过大约半个世纪的发展，已经成为一个独立的数学分支，特别是它在国 防和经济发展中得到了直接的应用，所以吸引了大量学者的研究兴趣。关于独立到达 和独立服务的排队论问题，在主要方面已基本趋于完善，大量的实际问题又给我们提 出了突破两个独立性的新要求。 最近2 0 年来，通信发展异常迅速，它与计算机的结合对排队论提出了许多新 的课题，吸引了通信、计算机、和应用数学三方面的学者共同的关心和努力，有 关排队论的学术论文数以千记，它们主要发表在像i e e et r a n s a c t i o no nc o m m u n ( o n i n f o r m a t i o nt h e o r y ) 、i e e ej o u r n a lo ns a c 、c o m m u n c a t i o ns t a t i s t i c si ns t o c h a s t i c m o d e l s 、j o u r n a lo fa p p l i e dp r o b a b i l i t y 、a d v a n c e da p p l i e dp r o b a b i l i t y 、o p e r a t i o nr e - s e a r c h 、b e l ls y s tt e c hj o u r n a l 、q u e u e i n gs y s t e m s 等著名期刊的相关的专业性学术会 3 第1 章绪论硕士学位论文 议上。 1 2 m m p p ( 2 ) 的内容、背景及现状 自从1 9 9 3 年9 月1 5 日美国政府提出“国家信息基础设施( n i i ) ”即“信息高速公路” 以来，在全世界已掀起一个异步传递模式( a t m ) 的研究高潮。人们从不同的侧重 点在研究a t m 。在i t u t 于1 9 9 0 年6 月正式通过了美国关于b i s d n 的1 3 个国际建议之 后，a t m 网络的研究取得了很大的进展，已提出几十种a t m 交换机方案，许多大公司 己相继推出他们的a t m 交换机和终端设备产品。总之，这些年来对a t m 的研究始终处 在热潮之中，没有减弱的趋势。 a t m 采用异步时分复用技术，各种不同特性和不同传输要求的业务所产生的信元 都汇集到一个缓冲器( b u 舶r ) 内排队，队列中的信元被逐个输送到传输线上。b i s d n 综 合着各种业务而不是单一的业务，这些业务的速率大小、突发度大小、突发长度、所 要求的服务质量，以及实时性等对于不同的业务相差甚远，这就给描述输入业务流带 来了困难。与常用的电路交换电话网相比( 我们不妨称它为指数网，因为呼叫的到 达时间间隔和服务时间都是指数分布，而指数分布在连续型概率分布中是唯一的具 有无记忆性的分布函数，无记忆性在数学上又有许多使问题简化的特性可以加以利 用) ，b - i s d n 中的业务流至少有两个明显特征：相关性和突发性，这是通常的电话网 中的业务所没有的。因此以往的建立在到达时间间隔独立、服务时间独立这两个前提 基础上的排队论不能用了，或者说不够用了。 无论如何，要分析传输性能、确保运输质量，并最大可能的应用网络资源， 必须首先了解各类业务的统计特性，以及形成相应的排队分析方法。这是不可 避免的首先需要解决的问题。从著名文章【1 】中我们知道网络业务有着不同于简 单的p o i s s o n 过程和更新过程的特征。通过大量文献可发现，对业务流建模后的 分析方法，大致可分为矩阵几何分析方法和特征值分析方法。对于业务流的模 型，则有半m a r k o v 过程、m a r k o v 调$ 1 p o i s s o n 过程( m m p p ) 、m a r k o v 调制定长过 4 硕士学位论文关于m m p p ( 2 ) 到达的两个排队系统分析 程( m m d p ) 、开关批量b e r n o u l l i 过程( s b b p ) 、批量m a r k o v 至：l j 达过程( b m a p ) 、中 断( 或开关) p o i s s o n 过程( i p p ) 、自回归模型等。 但是纵观所有的这些模型，t h em a r k o v m o d u l a t e dp o i s s o np r o c e s s ( m m p p ) 尤其 值得研究，它能够描述信息到达时间的边缘分布和自相关性，而且它的复杂程度又适 中，研究它的工具也有很好的完善。因此m m p p 在文章【2 】一【8 中引起很大的重视，广 泛应用于多媒体业务模型 9 1 一 1 4 1 。其中m 口r 忌伽调制p 历s s 咖过程( m m p 尸) 是一种双随 机过程，虽然信包( 元) 流已不是p o i s s o n 流，我们可以设想是“分段”的p o i s s o n 流。 但这种分段不是在时间上的确定性分段，而是经过一个m a r k o v 链的调制，当链的状态 是i 时，强度取常数九，故m m p p 是由一个m a r k o v 链的生成矩阵和一个p o i s s o n 过 程的强度向量所确定的。 人们 - 3 惯用m m p p ( 2 ) - - 调制用的m a r k o v 链只有两个状态，去描述话音流，因 为此时模型只有四个参数，较易确定。h h e f f e s 2 3 】和d m l u c a n t o n i 2 4 首先对话音数 据业务用m m p p ( 2 ) 建模，d a i g l ej n 和l a n g f o r dj d 曾用半m a r k o v 过程作为分组语 音统计复用系统的模型。在排队分析时归结为一个拟生灭过程，然后用n e u t s 的矩阵几 何分析方法求解。 如果我们将网络中的信元视为排队论中的顾客流，将a t m 交换机造成的时延看作 为排队论中的服务过程，显而易见，排队理论将对网络协议的制定、提高网络质量起 到一定的指导作用，同时a t m 网络技术的发展也为排队理论提供了广阔的应用舞台。 值得一提的是m m p p 是m a r k o va r r i v e dp r o c e s s ( m a p ) 的特例，是b a t c hm a r k ( - v i a na r r i v a lp r o c e s s m a p ) 【1 6 1 的子类，更多的关于m m p p 、m a p 、b m a p n 其它 的马氏调制过程的信息可参看 2 5 】 1 3休假排队系统的内容、背景及现状 休假排队泛指服务台在某些时候不能被顾客利用的排队系统，导致服务暂时中断 的理由有多种多样的解释，而暂时不能用于接待顾客的那些时间统称为休假。一些诱 5 第1 章绪论 硕士学位论文 发休假排队研究的典型例子是辅助工作、保养策略、机器故障、启动时间、轮循服 务、交通堵塞、优先权等【3 4 】。 大量的实际问题均可通过在经典排队论系统中引入某种休假策略加以描述和 研究。2 0 世纪中期以来随着计算机通讯网络，柔性制造系统( f m s ) ，异步转换模 式( a t m ) 等高新技术领域的发展，提出了大量复杂系统的设计与控制问题，经典排队 模型在处理这类问题时存在着极大的局限性。休假排队正是在这些实用背景中产生 的。 休假排队研究是从2 0 世纪7 0 年代才开始的。l e v y 与y e c k a l i ( 1 9 7 5 ) 【2 2 】从有效利用排 队系统闲期的观点出发，首先研究y m g 1 型休假排队系统，并引人了“休假”和 “休假策略”等术语。一方面，休假排队系统反映了服务过程可能因某种理由发生中 断这一客观事实；另一方面，各种休假机制为系统的优化设计和运行控制提供了极大 的灵活性。因此休假排队立刻受到广泛关注并成为一个研究热点。 从8 0 年代末n 9 0 年代，田乃硕等【3 4 】首先把矩阵几何解方法引入休假排队研究，推 进t g i m 1 型休假排队系统和多服务台休假排队系统的研究。平行于休假排队理论 研究的进展，取得的结果迅速在众多领域得到了卓而有效的应用。例如，中心处理机 时间表的设计与控制、最优保养策略的拟定和实施、生产过程的经济效益分析、行政 工作及其他维持性工作对中心处理机运行过程的影响、数据通讯网络中定时询查系统 分析、柔性制造系统的生产调度、a t m 中的拥塞分析问题等等。2 0 多年的发展表明， 休假排队研究不仅为经典随机服务系统理论的发展注入了新的活力和生机，也为排队 论在各种高新技术领域的应用开辟了更广阔的前景。 1 4 本文的主要研究内容 本文首先研究了模型m m p p ( 2 ) e 2 i ( s l ，s v ) ，对该模型引入了单假时间纯有 限策略( 即服务员每服务一个信元就度一个假时间，当假时间结束时，如果系统不空， 则服务立刻开始，否则服务员成为空闲一直到一个新信元到达为止) ，可以视为服务时 6 硕士学位论文关于m m p p ( 2 ) 到达的两个排队系统分析 间为( 日+ y ) 的m m p p ( 2 ) e 2 1 系统。本论文运用矩阵解析的方法对该系统模型进 行分析，得到了其状态的q 矩阵；分析了这个系统的运行特征：稳态队长概率解，顾 客的稳态等待时间，忙期，系统的业务量强度，以及任何时刻系统为空的概率。 其次主要分析了反馈次数服从几何分布的m m p p ( 2 ) g 1 系统模型。其中：顾客 的到达过程为m m p p ( 2 1 到达，服务台的服务时间服从一般分布，反馈次数均服从几 何分布。本文在讨论该系统模型的性能指标方面得到了该模型的平稳条件、队长母函 数的隐形表达式、系统的平均队长、忙期l s t 的隐形表达式、忙期的平均长度、以及 在忙期内服务完的平均顾客数。本文把休假、反馈理论与m m p p ( 2 ) 到达系统结合起 来，用矩阵分析方法对其进行综合排队分析，这在国内外公开发表的文献中还未曾见 到。 一 7 第2 章预备知识 硕士学位论文 第二章预备知识 2 1 关于m m p p ( 2 ) 的介绍 m a r k o v 调制p o i s s o n 过程( m m p p ) 是一种双随机过程，这种p o i s s o n 过程的 强度是由一个m a r k o v 链来调制，当链的状态是i 时，我们称相位为i ，强度取 常数九，i = 1 ，2 ，n ，这里是调制链的状态数，因此m m p p 是由用以调制 的m a r k o v 链的无穷小生成矩阵和一个p o i s s o n 过程的强度向量所唯一确定的。 当n = 2 时，便是m m p p ( 2 ) 。 在本文中，水平是指系统中的顾客数，相位是指m a r k o v 链所处的状态。 二阶m a r k o v 调制p o i s s o n 过程中m a r k o v 链的无穷小生成矩阵为 p o i s s o n 过程的强度矩阵为 r r ：i 叶 l 饱 饥1 ， 一7 2j ( 2 1 ) a = 2 ， 即为到达率矩阵，其中九为当m a r k o v 链处于状态i 时的p o i s s o n 率。 其中 天= ( 入l ，入2 ) t = a e e = ( 1 ，1 ) t 那么该m a r k o v 链的稳定概率分布为 n = ( 1 1 1 , i i ，) = 糕 8 ( 2 3 ) ( 2 4 ) 硕士学位论文关于m m p p ( 2 ) 蛩j 达的两个排队系统分析 过程的平均到达率为： m = a l l l i + ) l 2 h 2 = h a e 记到达过程的瞬时到达率为p ( t ) ，则 它的协方差函数是 p ( t ) = e 皿 ( 2 5 ) ( 2 6 ) r ( t ) = n h e m e 】a e ( 2 7 ) 记n ( t ) 为在( 0 ，t ) 内m m p p ( 2 ) 的到达数，则由【3 1 】知l v ( t ) 分布的母函数为 g ( z ，t ) = e 印 【冗+ ( 名一1 ) a l t e p i n ( 归n 】= i i e m d i a g ( 警e 砒t ，等e 也。) e 夕7 ( 1 ，亡) = 、2 1 7 2 鬲+ a - 2 7 i 亡 ( 2 8 ) ( 2 9 ) ( 2 1 0 ) 竺群亡一呈塑群( 1 一e 一( 讥+ 能) 亡) ( 饥+ 能) 3 。 ( 饥+ 伪) 4 r 。 。，。 ( 2 1 1 ) 定义g ( z ) 是第一次从水平1 到水平。通过时间的概率母函数，即 其中 g ( 名) = g 。) z j j = o g o ) = 战】 以= p 【在相位i 时系统的水平为l ，经过歹次转移第一次进入水平0 ，此时相位 为明 则从j 到0 的第一次通过时间的概率母函数为【g ( z ) 】 0 0 g ( z ) = z 如【g ( z ) n j = o 其中4 是在一个服务时间内到达歹个顾客的概率。 9 第2 章预备知识 硕士学位论文 同理令k ( z ) 表示相继两次进入水平。之间的转移次数( 花费时间) 的矩阵概率母函 数，类似的结论有 其中岛是从水平。开始第一次转移到水平j 的概率。 开关p o i s s o n 过程( i n t e r r u p t e dp o i s s o np r o c e s s e s ，i p p ) 可以看做一个2 状态 的m m p p ，它是这样的一种随机过程，一个强度为入的p o i s s o n 过程经过一条线路， 在线路上有一个开关，它的断开和合上的时间长度皆随机，其中合上的平均时间长 为1 ，断开的平均时间长为u 。在线路的另一端得到的就是开关p o i s s o n 过程， 简记为i p p 。i p p 用以调制的m a r k o v 过程有q 矩阵 兄= a 制 2 2 矩阵解析法 由于n e u t s 发展的矩阵解析法在这十多年来得到空前的发展，他的两本专 著( 1 9 s l ，1 9 8 9 ) 1 8 】是关于这一方法的理论基础和应用领域的代表作。他的两本专著分别 讨论了拟生灭过程于m g 1 型m a r k o v 过程的基本周期( 包括忙期在内) ，以及它 们的矩公式。以p 日分布为基础，n e u t s 引进了g ，驯1 型与m v l 型两类m a r k o v 过程，使得原来在指数分布假定下才能分析的很多随机模型推广到p 日分布的情彤。 由于p h 分布可以逼近任意非负随机变量的分布，从而使一般分布假定下的随机模型 能够得到易于计算的逼近。 1n g 弓 z 触 = p k 硕士学位论文关于m m p p ( 2 ) 到达的两个排队系统分析 2 3 母函数方法 设x 是取非负整数值的离散型随机变量，它的母函数记为 皿( z ) = k = 0 p k z 七，i z l 1 ( 2 1 2 ) 其中 p 七= p z = 七) ，七= 0 ，1 ，2 皿( 名) 在1 上是一致收敛且绝对收敛，因此，母函数对任何取非负整数值的随机变 量都存在。 母函数的主要性质有： 性质l ( 唯一性) 取非负整数值的离散型随机变量，其概率分布切七，七0 ) 与其母 函数是一一对应的。 性质2 若e x 】存在，则e 】= 皿7 ( 1 ) 若d 】存在，则d 】= 皿”( 1 ) + 皿，( 1 ) 一【皿，( 1 ) 】2 性质3 设五，恐，恐，均为取非负正整数值离散随机变量，若墨，恐，恐， 相互独立，则x = x l + 恐+ + 的母函数为 皿。= 皿霉。( z ) 皿。：0 ) 皿霉。( z ) 性质4 若x 1 ，x 2 ，x 3 ，是独立同分布的整数值随机变量，是与【) 独立的 取正整数值的随机变量，, 见e jy = 竺l 五的母函数为 r - z ( z ) = g 睁( z ) 】 其中g ( z ) ，皿( z ) 分别是n ，x 1 的母函数。 儒歇定理如果函数( z ) 和g ( z ) 在简单闭曲线l 的内部d 解析，且在曲线l 上 有 f ( z ) 0 ，i ，( z ) i i g ( z ) 1 则在l 内部，f ( z ) 与，( z ) + g ( z ) 有相同的零点个数。 1 1 第2 章预备知识硕士学位论文 2 4嵌入马尔可夫链方法 在泊松到达与服务时间为负指数分布的排队系统中，在任何时刻系统都具有马尔 可夫性质，因而可用连续参数马尔可夫链的方法化成可求解的平衡方程组，得到系统 的平衡解。对于如m g 1 或g x l m l l 那样的一般服务或一般到达的排队系统，不是 在任何时刻系统都具有马尔可夫性质，只是在某些特殊的随机时刻系统才具有这种性 质，我们称这种随机时刻点为再生点，即从这个时刻起，系统行为好像又重新开始一 样。利用再生点，前面所述的如m i g l l 或g i m 1 1 那样的一般服务或一般到达的排 队系统的分析，可用马尔可夫链的方法予以解决，这种方法就叫做嵌入马尔可夫链 法。徐光辉 3 3 】，孟玉珂【3 9 】，唐应辉和唐小我【3 8 】，陆传赉，华兴，孙荣恒【3 0 】，和李 建平，对此做了详细的论述。 2 5l i t t l e sl a w e x = a ( e t ) e x q = a ( e w ) 其中入是系统的进入率，e x 是系统中任一时刻的平均队长，e t 是每一位顾客在系统 中的平均逗留时间，e 蜀是平均等待队长，e w 是平均等待时间。 2 6 d l l ( d i s t r i b u t i o nl i t t l e sl a w ) 1 2 平稳状态下当下面两个条件成立时，我们有 l 口= ( ) ( 1 ) 顾客离开系统与他们到达系统的顺序相同，臣 j f i f o ； ( 2 ) 到达顾客的等待时间与将来顾客的到达间隔相独立【2 7 】。 硕士学位论文关于m m p p ( 2 ) 到达的两个排队系统分析 其中三q 是等待队长，是等待时间。 注：满足d l l 定理的模型，诸如：f j f 0 的g g l 排队；带有休假的f j f 0 的g g l 排 队；f i f o 且具有几何分布的批量到达系统。d l l 定理对多服务台分布及非更新到达 的排队系统不成立。 2 7 交错更新过程 定义2 1 令 忍，i 1 ) 和舭，i 1 1 是独立同分布的非负随机变量序列，且反与y i 又相互独立。z 和掣分别是和玑的一般表示。令p k o l 0n p y 0 】 0 ， n 此e x 】 o 和e m 0 。记忍= 轨+ 玑，名表示忍的一般式，f g r s n = 警l 忍 n p s o = 0 】= 1 ，令 几( 亡) ，亡o ) = s u p n ：n o ，8 n 亡】。则计数过程 n ( t ) ，亡o ) 称为一个交错更新过程，名称为更新区间，如称为第扎个更新过程。 交错更新过程是在z 区间和y 区间之间交替，则有定理： 定理2 7 1 设 礼( 亡) ，芒o 是一个交错更新过程，在z 与y 之间交替。那么在任意时 刻，过程在z 区间的概率由z 区间的平均长度与平均更新区间长度之比给出，即 只= 器= 薪 其中只= l i r n t - o o p 【在n nt 系统处于z 区间】 类似的 b = 锱= 薪 其中己= l i r n t p 【在时刻t 系统处于可区间】 ( 2 1 3 ) ( 2 1 4 ) 1 3 第3 章m m p p ( 2 ) e 2 i ( p l ，s y ) 的系统分析 硕士学位论文 第三章m m p p ( 2 ) e 2 i ( p l ，s y ) 的系统分析 3 1 引言 由于经典排队论的研究已趋完整，它的许多结果在通信中得到了很好的应用。通 信体制是原有体制的发展，在新体制下的业务流不过是一种重新描述，因此人们自然 会从经典排队论中去寻找某种继承。人们愿意用m m p p ( 2 ) ( 调制用的m a r k o v 链只有 两个状态) 去描述话音流 3 1 】。休假排队模型反映了服务过程可能因某种理由发生中断这 一客观事实，尽管近年来关于带服务台休假的排队系统的研究已经取得了一系列丰硕 的成果【2 6 】，研究热点依然集中在m g i ( e ，m y ) 和m g i ( e ，s y ) 及有关模型，将这 一研究引向非泊松到达领域，从理论研究的角度看是十分有理论意义的。本文正是对 带有单假时间纯有限服务的m m p p ( 2 ) 到达，服务时1 8 f r 从e r l a n g 分布的排队系统进 行了概率分析。整章安排如下： ( 1 ) 系统定义即模型假设； ( 2 ) 求系统的转移率矩阵与平稳条件； ( 3 ) 求系统的业务量强度； ( 4 ) 求系统的忙期长度以及在忙期时间内离去的平均顾客数： ( 5 ) 求系统在平稳条件下的队长分布及任一时刻系统为空的概率； ( 6 ) 求出稳态条件下顾客等待时间与逗留时间。 3 2 系统模型描述 m m p p ( 2 ) e 2 i ( p l ，s y ) 系统模型假定： ( 1 ) 信元按照m m p p 到达，调制m a r k o v 链的生成矩阵( 无穷小生成子) 为r ， 是它的平稳概率分布。在各相位的p o i s s o n 到达率形成的对角矩阵为 1 4 a = d i a g ( ) h ，入2 ，h ) 硕士学位论文 关于m m p p ( 2 ) 至r j 达的两个排队系统分析 并记天= ( 入1 ，入2 ，h ) t = a e 。 其中e = ( 1 ，1 ) t 为仇维列向量。 当m = 2 时即为m m p p ( 2 ) 到达。 ( 2 ) 假定服务时间相互独立同分布，服从2 阶e r l a n g 分布，分布函数为日( z ) = # 2 x e - 肛z ，l s t 为日+ ( s ) 2 瓦等斋，服务时间的阶矩记为肛“) ，于是肛( 1 ) 为平均服 务时间，这些服务时间与到达过程独立。 ( 3 ) 每一次服务完成时都度一个假时间，当假时间结束时，如果系统不空，则服务 立刻开始，否则，服务员成为空闲一直到一个新的顾客到达为止。休假时间y 服从指 数分布，其分布函数为v ( x ) = l e 篮，其l s t 为矿( s ) = ，休假时间独立于 a + s 到达间隔与服务时间，则原系统可视为服务时间为( 日+ y ) 的系统，引入广义服务时 f 司f ( x ) = g ( x ) ，- cy ) ，有l s t 为p8 ) = h + ( s ) 矿( s ) ，这是因为服务结束后系统中 无顾客时，其后的假时间己并入服务时间，若这一假时间内无信元到达，相当于按广 义服务时间“完成服务 后直接进入空闲期。 ( 4 ) 顾客按照次序服务，这个次序与它们的服务时间独立。 ( 5 ) 服务是非抢占的，即一个顾客一旦被服务就连续被服务完。 ( 6 ) 对于给定的服务员开始与假时间的规则不改变m m p p ( 2 ) 到达过程。 3 3系统的转移率矩阵与平稳条件 令j ( t ) 表示t 时刻排队系统中的占有数，称为水平，例如占有数i 就称系统处 在水平t ，t 0 。j ( t ) 表示m a r k o v 链：在时刻t 所处的状态，称为相位，( t ) = j ， 当歹= t 时，说明系统是以强度为九篚 p o i s s o n 过程到达，0 j m 。状态的次序是 字典式的，即定义戤= 【x i o ，x i l ，z 拥】，z = k o ，x l ，x 2 】，其中( ) j 表示在相位j 下系统处于水平i 的概率。当m = 2 时为m m p p ( 2 ) 到达。 我们首先列出矩阵 1 5 第3 章m m p p ( 2 ) e 2 i ( p l ，s y ) 的系统分析 硕士学位论文 其中： 记 q ( x ) = 岛( z ) b l ( x ) 鼠( z ) a o ( x ) a l ( x ) a ( z ) 0 a o ( x ) a n 一1 ( z ) 00 a n 一2 ( 。) 00 a n ( z ) ：厂霉 j o ) = p ( 佗，t ) d ( h ( t ) 半y ( t ) ) e ( a a ) 。a 出 鼠( z ) = u ( x ) ，c a n ( z ) a n = a n ( o 。) b n = 玩( 。) ( 3 1 ) ( 3 2 ) ( 3 3 ) ( 3 4 ) l u = u ( o 。) 矩阵p ( n ，t ) 的元素( n ，t ) 描述的是调制m a r k o v 链在t = 0 时相位为i 的条件下， 在( 0 ，t ) 内有礼个到达且在时刻t 的相位为j 的概率。 a n ( i ，j ) 描述的是一个服务开始，且调制m a r k o v 链处于相位i 的条件下，服务结 束时，有礼个顾客到达且此时相位为j 的概率。 v ( x ) 的元素阢j ( z ) 表示在t = 0 时闲期开始，并且调制m 0 7 - 后伽链处于相位i 的 条牛- v ，在时刻z 之前第一个到达空系统( 闲期结束) ，此时相位为歹的概率。矿描 述了在一个闲期期间内的相位转移行为。 基于m m p p ( 2 ) 的情形，p ( n ，亡) = 【p _ f j ( n ，t ) 】 1 6 ( 佗，t ) = p n ( t ) = 扎，j ( t ) = j l j ( o ) = i 】 = p n ( t ) = n i j ( t ) = 歹，j ( o ) = i p j ( t ) = j l j ( o ) = 4 硕士学位论文关于m m p p ( 2 ) 到达的两个排队系统分析 则 其中 脚，- = - d i a g ( 学e 呐t ，学e 也。) 晰 p ( t ) = 【岛( t ) 】 故p ( n ，t ) 的母函数是 p ( z ，亡) = p ( n ，t ) z n = 耋e 瞰出叼( 学e 呐t ，学e 也2 ) ：e r e e ( z 一1 ) a t ：e 冗+ 0 1 ) a t ：e r ( z ) t ( 3 5 ) r ( z ) = r + ( z 一1 ) h ( 3 6 ) n ( 0 ) = r a 。( 3 7 ) r ( z ) 一r ( 0 ) = z a ( 3 8 ) 设a n ) ，b c x ) ，矿( z ) ，y ( z ) 的l a p l a c e s t i e l t j e s 变换分别记为a ：( s ) ，磁( s ) ，u ( s ) ，v + 8 ) 则 f + ( s ) = h ( s ) y + ( s ) ( 3 9 ) 则有 矿( s ) ：厂o o e “e ( r a ) t a 出 j 0 = 【s i r + h i 一1 a ( 3 1 0 ) 如= 群( o ) 风= 磁( o ) u = u ( o ) = ( a r ) - 1 a = 一r ( o ) 】a ( 3 1 1 ) 1 7 第3 章m m p p ( 2 ) e 2 1 ( p l ，s y ) 的系统分析 硕士学位论文 令 则 a ( z ，s ) = 钙( s ) 矿 o 。 广，2 。至ze 叫z 脚) d f ( 咖n 2 至上e 叫叩( z ) d f ( z 矽 2 上e 叫工薹以咖脚) = e - 8 e r + ( 卜1 ) a 】z d f ( x ) ( 3 1 2 ) b ( z ，s ) = 联( s ) 扩= u ( s ) 越( s ) 扩 n = 0n = o = u + ( s ) 心( s ) 扩 n = o = 【s i r + a 】a a ( z ，s ) v ( z ，s ) = u ( s ) z = 【s i 一冗+ a 】- 1 a z = 【s i 一冗( o ) 】- 1 【冗( 石) 一r ( o ) 】 u 0 ，0 ) = 【人一嗣一1 a = u 定理3 3 1 m m p p ( 2 ) e 2 i ( p l ，s v ) 系统平稳的充要条件是 p 全y i a e ( j u ( 1 ) + e y ) 1 ( 3 1 3 ) ( 3 1 4 ) ( 3 1 5 ) 证明：由文献【3 1 】知，卫= 2 ；0 ，z 1 ，x 2 - 1 是由计算不可约随机矩阵q ( ) 的平稳概率向 量得到的，它是在顾客离开的瞬时系统中的顾客数分布。即考虑了顾客在离