（应用数学专业论文）mxmc→mmnk串联排队系统分析.pdf

硕十论文 m 。i m c 一( m ) m n l k 串联排队系统分析 摘要 本文研究了含特殊类顾客的m ( 曲m c 一( m ) im 刀k 有限容量的串联排队系 统，这一模型在银行排队服务系统、公共服务系统、通讯问题、计算机配置问题等方面 有着广泛的应用。 本文共分四章，第一章简要介绍了排队论的发展进程、串联排队模型和成批到达排 队系统的背景、研究历程等相关内容，同时还阐明本论文模型的基本内容和主要指标的 计算。第二章给出了本论文所需要的理论知识和基本方法。第三章是在经典的模型 m m 1jm m 1 的基础上，添加了批量到达、特殊类顾客到达，即模型 m “m cj ( m ) m 疗k 。本章用矩阵几何分析的方法得出了系统模型的q 一矩阵， 运用拟生灭过程的方法给出了系统平稳的充要条件、平稳队长分布及其算法，i 级服务 系统的忙期分布及其在忙期内服务完的顾客数的概率母函数，i 级服务系统受阻时间分 布的拉普拉斯一司蒂阶变换。 最后，第四章本章对本文所作的研究工作和取得的进展，以及进一步研究的方向作 一些简要的概述。 关键词：串联排队系统，拟生灭过程，特殊服务，成批到达，矩阵几何分析 a b s t r a c t n e 。s t a g et a n d e mq u e u e i n gs y s t e m m j m c 专( m ) m ，z kw i t hs p e c i a l c u s t o m e r si sm a i n l ys t u d i e di nt h i sp a p e r t h et a n d e mq u e u e i n gs y s t e mi sw i d e l yu s e di i lt h e s e r v i c i n ga n dq u e u e i n gs y s t e mo fb a n k ， d e p l o y m e n tp r o b l e m sa n ds oo n p u b l i cs e r v i c es y s t e m ，t r a f f i cp r o b l e m s ，c o m p u t e r t h ew h o l et h e s i si n c l u d e sf o u rc h a p t e r s i nt h ef i r s tc h a p t e r ，t h ed e v e l o p m e n t h i s t o r ya n d s m t a so ft h eq u e u et h e o r y ，t h er e s e a r c hb a c k g r o u n do f t h et a n d e mq u e u em o d e la n dt h eq u e u e s y s t e mw h o s ec u s t u m e r sa r ea r r i v i n gi n b a t c h s i m u l t a n e o u s l yt h eb a s i cc o n t e n ta n dt h e p r i m a r yi n d e x e so ft h i sp a p e ra r ep r e s e n t e d i nt h es e c o n dc h a p t e r , t h eb a s i so ft h e o r e t i c a l k n o w l e d g eo ft h eq u e u et h e o r yi si n t r o d u c e dw h i c hw o u l db eu s e di nt h i s p a p e r i nt h e 恤d c h a p t e r ，a r r i v i n gi nb a t c ha n ds p e c i a ls e r v i c eo ft h es p e c i a lc u s t o m e r sa r ea d d e di nt h ea u e u e s y s t e mm i m 1 寸m m 1 ，n a m e l ym x m c _ ( m ) m 刀k i nt h i sc h 印t e lt h e t r a n s f e r r i n gp r o b a b i l i t ym a t r i xo ft h et a n d e mq u e u e i n gs y s t e mi s p r e s e n t e db ym e a n so f m a t n xa n a l y s i st h e o r y t h e s u f f i c i e n t - n e c e s s a r yc o n d i t i o n sf o rt h es y s t e m s t a b i l i t ya r c p r e s e n t e db yq u a s i _ b i r t h - d e a t h p r o c e s st h e o r y a n dt h ed i s t r i b u t i o no f s t a t i o n a r yq u e u el e n g t h a n di t sa l g o r i t h ma r eo b t a i n e d t h eb u s yt i m ed i s t r i b u t i o no ft h e s t a g e i ，t h ep r o b a b i l i t y g e n e r a lf u n c t i o no ft h en u m b e ro fc u s t o m e r ss e r v e r e di nb u s yt i m eo ft h es t a g e ia 】o b t a i n e d b ym e a n so ft h ei m b e d d e dm a r k o vc h a i n a n dt h ed i s t r i b u t i o no f t h es t a g e is e r v i c eb l o c k e d t i m ei sf u r t h e ra n a l y z e d h a el a s tc h a p t e rp r o v i d e sa n a l y s i sa n ds u m m a r ya b o u tt h e r e s e a r c hs u b je c ta n dr e s e a r c h p r o g r e s s i na d d i t i o n ，t h ef u r t h e rr e s e a r c hd i r e c t i o n sa r es u g g e s t e d k e yw o r d s ：t h er a n d e mq u e u e i n g ，q u a s i - b i r t h d e a t h p r o c e s s ，a r r i v i n gi nb a t c l l ，s p e c i a l s e r v i c e ，m a t r t i x - g e m e t r i cs o l u t i o n s 声明尸i j j 了 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名：0 咖年多月矽日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名：_ 氢险盈 一 少卢年6 月杉日 硕士论文 m m c 一( m ) m n k 串联排队系统分析 第一章引言 本章简要地介绍排队论的发展进程及应用、串联排队模型和成批到达排队系统的背 景、研究历程等相关内容，同时还阐明本论文模型的基本内容和主要指标的计算。 1 1 排队论发展进程 排队论是具有特殊实际价值的现代应用数学分支之一，是集概率论、数理统计、随 机过程之一体，成功地解决现实生活中形形色色的实际问题的面镜子。它是运筹学中 内容异常丰富的一个精华部分；是研究系统受随机因素的影响而产生排队现象，进而揭 示其概率规律性的一门科学。 自从19 0 9 年丹麦电话工程师爱尔朗( 么k e r l a n g ) 的开创性论文“概率论和电话通 话”发表以来，爱尔朗创立了一套关于随机过程方面的理论，进而以“排队论”命名的 一门新的学科诞生了。2 0 世纪3 0 年代中期，费勒f 形f e l l e r ) 把生灭过程引进排队论之 时，数学界才把排队论认同是一门重要学科。在第二次大战以前，其研究多侧重于电话 与远距离通信方面，发展也比较缓慢；但二战以后，排队论渗透到军事、经济、生产与 服务等多种部门，它的理论和应用得到了快速地发展，迅速成为了运筹学和管理学的一 个热门分支。2 0 世纪5 0 年代初，英国学者肯德尔( d g k e n d a l l ) 引入了嵌入马尔科夫链 的方法，成为研究排队理论的经典方法。 7 0 年代以来，随着电子计算机的不断更新与发展，通信网的建立与完善，信息科学、 生命科学及控制理论的蓬勃发展，在许多场合下所涉及到的最优设计与最佳服务问题均 构成了排队问题。对这些问题的行为分析、统计分析、运行分析、计算机仿真，使排队 理论与应用获得了质和量上的飞速发展。 排队论是研究服务过程的概率特性的数学理论。在各个领域内，排队内容虽然不同， 但是排队过程都可以由三个特征来定义：输入过程、服务过程、排队规则。 ( 1 ) 输入过程：描述有关服务请求的序列，在一般情况下，输入过程即为由顾客 相继到达的时刻之间的间隔分布束确定的。 ( 2 ) 服务过程：具有服务台的数量以及顾客占用服务台的服务时间长度等特征。 譬如：顾客可以由单个服务设备处理( 单服务台) ，亦可以由有限个服务台 或无限个服务台处理。每个顾客占用服务设备或被服务的时间可以是相同的 时长( 即定长时间) ，服务时间亦可以具有指数分布、几何分布、一般分布 世 寸o ( 3 )排队规则：确定对阻塞顾客的安排( 当顾客发现所有服务设备全忙时) ，例 如它可以假设被阻塞顾客立即离丌系统，或被阻塞顾客在一个队列内等待服 第一章引言硕f ：论文 务并且按照f c f s ( 先到先服务) 方式给予服务。故排队规则可以分为三种 制式：即等待制、损失制和混合制。 对于一个排队系统，主要以顾客和服务机构两方面的利益来权衡它的好坏。一方面， 就顾客利益来说，他们总是希望等待时间或是逗留时间越短越好，即要求服务台的个数 尽可能多些；另一方面，对于服务机构来说，服务台个数的增加就意味着增加投资，势 必会对服务机构的利润产生影响。因此，排队论的主要内容，就是要研究排队系统的以 下几个指标：系统队长、顾客的等待时间、服务台的忙期长度等指标。对于经典的排队 论研究主要有以下几种常用的方法：嵌入马尔可夫法、补充变量法、拟生灭过程理论、 半马尔可夫过程理论，还有国内侯振挺教授提出的马氏骨架方法、国外b r i l l 教授提出 的水平穿越方法等。 1 2 排队论的应用问题 排队论应用的具体案例不胜枚举，主要应用在如下几个方面。 ( 1 ) 通讯问题 电话交换机通常仅由有限条电话线供用户通话，如果在某一时刻所有的电话线均被 占用，那么新的用户就必须等到有一条线路空下来才能通话，此时用户对电话线的使用 就是排队问题，电话线为服务台，用户占用电话线的时间为服务时间，而一般情况下， 使用电话线的排列规则为“先到先占”。在人造卫星通讯方面，通讯卫星是服务台，地 面上通讯站的使用要求可以视为顾客的到达，服务时间依据通讯站发射讯息的长度和卫 星转播讯息的时间而定，排队规则可以是先到先占或者是用户依次轮流使用。 ( 2 ) 公共服务问题 许多公共服务事业对群众提供依次服务、群众对公共服务设施的使用情况也可以纳 入排队问题。例如在银行、邮局，他们的的服务人员可以看作服务台，在医院，病床可 以看作服务台，他们的服务时间和到达顾客则与实际的情况完全一致，一般情况下排队 规则均为先到先服务，但是在某些场合下也可以有优先权的出现，例如病危的患者就有 优先占用空闲病床的权利。 ( 3 ) 救护，公安服务系统 警察、消防人员、消防车、医院的救护车均可以当作服务台，紧急事故的发生可视 为顾客的到达，通常这类问题都要求极低的服务台使用率，因而当一件紧急事故发生时 有足够的应付能力。 ( 4 ) 存量问题 储存系统中存量变化的随机行为和排队论中的队长变化的随机行为有相似的地方。 一般情况下商店进货的策略是根据货物销售情况来决定的，商店一方面力求减轻存货的 压积；另一方面要想方设法地满足顾客的需求。图书馆根据藏书库的容量及书籍的使用 2 硕：l ：论文 m i m c 斗( m ) m 一k 串联排队系统分析 率来淘汰无用的旧书；水库管理部门需要制定放水的策略，一方面提供发电，灌溉的需 要；另一方面要尽量把水源枯竭、由于连续暴雨而造成的积水过多，这两种情形的发生 率减至最低。 ( 5 ) 生产流水线问题 在工厂生产流水线上，为了保证生产线的水平，必须合理安排机器、工人及物料运 输设备，降低生产过程中原料和半成品的存量，往往也可以通过对相应排队问题的研究 来获得解决。在这类问题里，顾客为工厂的产品，机器、工人及有关生产和运输设备可 视为服务台。 ( 6 ) 计算机的配置问题 计算机内部的中央处理机、输入和输出设备可以看作服务台，顾客则为计算机程序， 在计算机网络问题里，计算机本身也可以当作服务台，计算机程序或指令通过网络可由 个计算机传送至另一计算机，这类问题通常都以网络队列形式出现。 排队论的应用远不止上述的几种。有些时候在一个排队问题里，顾客和服务台也并 不是一成不变，甚至可以互相颠倒。例如：有时出租车排队等候乘客，而有时乘客也排 队等侯出租车，汽车驾驶员和乘客都关心自己的等待时间而相互以对方为服务台。因此 在排队系统中，如何决定何者为顾客、何者为服务台，通常是看问题的性质或者如何方 便j 。能地解决问题。排队论运用起来是非常灵活的；此外排队论使用的模型和其它数学 模型一样，模型本身只是现实问题的一个数学表示方法，因而永远不能代表实际本身， 排队模型的解也总是一个对实际问题的近似。因此数学模型提供给我们的是一个客观的 理论根据，在数学模型的解加上，人们能够对应地作出正确的判断才是明智的决策。 1 3 串联排队网络系统的研究 一个排队网络是由多个服务设备组成的一个系统，在系统中的顾客可以属于不同的 类别，他们除了可以有不同的服务时间分布外，还可以在服务台之间相互转移，并且可 以有不同路径的转移概率。排队网络按照客源的情况，可以分为下面三类：开网、闭网 以及混合网络。在一个开排队网络中，顾客从外面到达网络，并最终离开网络：在一个 闭排队网络中，顾客在服务台之间循环，无顾客到达和离开；在一个混合排队网络中， 有一些顾客类相对于网络是丌的，而另一些顾客类相对于网络是闭的。另外，按照网络 状态过程描述的情况，又可以分为m a r k o v 型的和非m a r k o v 型的。 在排队论里有关网络的研究晟早见之于1 9 5 7 年杰克逊所发表的论文，在这篇文章 里，网络本身包括有m 个服务站，其中每个服务站有一定个数的相同服务台，但是每 个服务台都具有指数分布的服务时间，顾客到达网络依循参数为a 的p o s s i o n 流，各服 务站的外部输入与各服务时间相互独立。进入服务站i 的概率为a ，当顾客在服务站f 完 成服务后可以加入队列，也可以离开服务系统。而q ，= l 一 ：p 。就是离开服务系统的 _ - v j 3 第一章引言 硕士论文 概率。在开放网络里，由于各个队列的长度是相互独立的，故容易证明网络的平稳分布 等于各服务点平稳分布的乘积。假如在j a c k s o n 开网络中，顾客既不能由外界到达，也 不能离开到别处去，而其顾客在网络上的总数为一常数，则称为指数闭网络，或称 j a c k s o n 闭网络。由于在密闭的网络里，顾客的总数为固定的，因此队列长度不是互 相独立的。虽然可以先求出各个队列的边际分布，但是由于各分布并非是互相独立的， 因此联合分布不能用此方法得到。但是我们可以通过假设将闭网络改为一个开放的网 络，进而求解得出其平稳分布仍为一乘积型的。 那么非指数网络是否也具有乘积型的解? 许多学者作了研究。如：m u n t z ( 1 9 7 2 ) 、 b a s k e t t ( 1 9 7 5 ) 、c h a n d y ( 1 9 7 7 ) 、n o e t z e t ( 1 9 7 9 ) 等对在不同的服务时间分布、不同的服 务规则下的网络排队作了详细的研究，得出非指数网络排队的平稳分布仍具有乘积型 解。另外l l y ( 1 9 7 6 ) 与b a r b o u r ( 1 9 7 6 ) 研究了有多种排队规则在内的多种种类顾客、 一般服务分布的排队网络，巧妙地运用可逆性得出了一种乘积型解。 串联排队网络系统是模拟交通运输、计算机网络的一个很好的数字化模型。因此， 对于串联排队的理论与应用的研究是非常重要的。简单地说，在医院看病，需经挂号、 候诊看病、检查( 拍片、抽血、验尿等) ，划价、交费、取药等一系列窗口；大学新生 入学，需办理注册、户口、住宿、图书证等一系列手续等均属于串联排队模型。在国外 m a n d j e s ，m a n n e r s a l & n o r r o s 4 3 ( 2 0 0 7 ) 研究了高斯输入( g a u s s i a n ) 的两级串联排队 网络，并且两队列以常数c i ，江1 ，2 ，( c l c 2 ) 的概率服务，得出了平稳队长的分布。 b o x m a 1 8 1 研究了两级串联排队系统，且i 级服务台的服务时间是同分布的，得出了串 联系统平稳的充要条件、等待时间的分布，以及在i i 级服务系统逗留时间、等待时间分 布的精确表达式。m i t c h e l l ，v a n d el i e f v o o r t 3 6 ( 2 0 0 3 1 考虑了g g 1 型的串联排队 网络，该文章通过分析每个队列变化的特征及损失概率分布得出了离去过程的一种近似 模型。m o r r i s o n 3 7 1 & b o x m a ( 1 9 7 9 ) 4 1 1 分别研究了独立的p o s s i o n 流与b e r n o u l l i 到达过 程的串联排队系统，这种假设对交通排队网络非常适用；d a d u n a ( 1 9 9 7 ) 3 8 1 探讨了状态 独立的b e r n o u l l i 到达过程的串联排队系统，服务时间遵循不同参数的几何分布，得出了 队长的联合分布及等待时间分布。 对于有限容量的串联排队网络系统，在数据传输、生产线等模型中应用非常广泛 的。早在二十世纪六十年代，就有许多学者对有阻塞的排队网络作了简要的研究。 a v i l t z h a k & y a d i n 2 9 1 和s u z u k i 2 1 1 考虑了泊松流( p o s s i o n ) 到达、一般服务时间的两 级串联排队，并得出了等待时间的表达式。p r a b h u 2 2 1 分析了文献f 2 1 ，2 9 1 中模型的随 机过程的一些瞬时结果。近来l a n g a r i s 2 3 1 假设i i 级服务系统具有伽马分布输入、服务 时间服从伽马分布的情况下，也得出了一些相似的结果，相关的结果还可参照文献 1 2 9 ，3 0 ，3 1 3 2 1 。此外还有学者运用逼近的方法研究有限容量的串联排队系统，并求出了 系统指标的近似数值解。如：a 1 t i o k f 4 0 1 、b r a n d w a i n & j o w 4 4 1 、g e r s h w i n 4 8 1 、 4 硕上论文 m i m i c - - ( m i i m i n l k 串联排队系统分析 h i l l i e r & b o l i n g ( 1 9 6 7 ) 4 6 1 。但是，关于有限容量的串联排队网络系统指标的精确求解 方面的工作不多，而且大多考虑比较简单的系统，如：k o n l e i m & r e i s e r ( 1 9 7 6 ) 1 5 5 l 考虑 了系统m m 1 - - - m 1 k ，用复分析的方法给出了系统平稳的充要条件及平稳概率分 布。l a t o u c h e & n e u t s ( 1 9 8 0 1 用矩阵分析理论给出了系统m m ，一m c k 的平稳队 长分布。此后月a 刀& s r i s k a n d a r a j a h 2 8 1 对有阻塞、无等待空间的串联排队系统作了详细 的研究( 此类机制排队模型的相关文献，可参看p e r r o s l 3 9 i 和p e r r o s & a l t i o k l 3 5 1 ) 。 g e m e z c o r r a l 1 9 1 在2 0 0 2 年研究了i 级服务系统排队等待空间无限、级服务系统没有 排队等待空间的串联排队模型，即m a p 尸日lj g 1 模型。只有在u 级服务系统把 服务台前顾客服务完时，i 级服务系统服务完的顾客才可以到级服务系统要求服务， 顾客以马尔可夫过程到达串联系统，主要运用了嵌入马尔可夫链的方法、马尔可夫更新 过程基本理论研究了该模型。k o n h e i m & r e 括e r 4 2 ，4 9 1 研究了有阻塞的串联排队系统， 他们把概率分布所满足的平稳方程通过z 变换，进而研究了概率分布的母函数的一些性 质，得出了模型稳念存在的充要条件及计算概率分布的算法，另外l a t o u c h e & n e u t s1 5 6 l 运用拟生灭过程的方法得出了这个模型以及相关模型的稳态条件。 在国内，贾波、周家良f 1 2 1 5 1 对串联开排队网络作了详细的研究，先后在串联机 制中加入反馈、有限容量规则，富有技巧性地求得了多级串联、串联反馈、并联排队系 统的有关概率指标，并给出了相应的稳态分布的显式精确解及相关的指标。聂盼红 f 5 8 1 ( 2 0 0 4 1 在串联开排队网络系统分析中，研究了两级杰克逊j a c k s o n 串联开排队模型， 并给出了m 级j a c k s o n 串联系统的平稳队长分布，此外，该论文还研究了两类有限容量 的级串联开排队系统，并分别给出了它们的稳态结果及忙期分布。郭志芳1 5 9 i ( 2 0 0 6 ) 在级串联开排队系统网络中，又添加了休假机制，并得出了稳态队长、忙期长度与逗 留时间分布，并进行了计算机模拟与仿真。王松建( 2 0 0 7 ) 在级串联丌排队系统网络中， 又分别添加了反馈规则、启动机制，在模型一中用矩阵分析方法，得出了系统稳态解及 相关指标；在模型二中运用了递推方法，亦求出了稳态概率解，还得到了逗留时间、忙 期长度分布。 1 4 成批到达的排队系统 一 成批到达的排队模型，在多姿多彩的现实世界中比比皆是。诸如：邮政中成袋的邮 件运送、铁路或海运中的集装箱运转、高楼电梯为人或货物的运行系统等都是成批到达 的排队系统。 关于此类排队系统的研究，在李建平的排队论基础一书中就有探讨，书中主要介 绍了几类批到达的排队模型：彰m 1 、m s g 1 、g p g 1 ，用嵌入马尔科夫链的 方法给出模型的平稳分布、等待时间分布等；在国内，研究的批量到达的串联排队系统 一般都是输入过程是p o s s i o n 流到达、服务时间服从指数分布或p h 分布。如：苏时光、 气 第一章引言硕上论文 陈薇f 5 7 1 探讨了有限容量的m 肘c 专p h 1 k 两级串联开排队模型，得到了系统的 平稳条件，并且用矩阵迭代法给出了平稳队长分布和受阻概率的l s t 。徐光辉、袁学明 n 6 1 更为一般地研究了有限容量的成批到达、成批服务的两级串联排队网络模型，用矩 阵几何解的方法对m 似) m c 专p h ( r ) 1 k 进行了探讨，得出了m a r k o v 过程的q 一矩 阵，给出了系统平稳的充要条件、平稳队长分布及其算法。 近年来，许多国外学者研究了批量马尔可夫到达过程( b 心尸) 的串联排队系统，所 谓的b m a p 准确地说包括多种输入流，譬如：泊松流输入( p o s s i o n ) 、爱尔朗输入 ( e r l i n g ) 、高维的马尔可夫输入、朋型更新过程、马尔可夫调制泊松流输入f 脚p 1 等 等。对于b m a p 型输入的串联排队，文献1 9 ，2 7 ，5 0 一5 4 1 作了简要研究。其中b r e u e r 和 d “讲胛1 5 0 l 于2 0 0 4 年研究了b m a p g 1 一朋1 m 一1 型有阻塞的串联排队系统， 分别给出了i 级服务系统等待空间在有限和无限两种情况下，两级系统的稳态队长概率 分布，以及i 级服务系统的等待时间分布。k l i m e n o k & t a r a m i n 2 4 1 ( 2 0 0 7 ) 研究了有 损失制的两级串联系统，用嵌入马尔科夫链的方法得出了系统的稳态条件、稳态分布， 探讨了系统状态过程在任意时刻的队长分布及其他相关指标。2 0 1 0 年 k l i m e n o k & t a r a m i n 2 5 1 在【2 4 的基础上，又将反馈机制加入了串联排队系统，相应的 研究了q 一矩阵的正常返性、稳态分布及相关指标。c h es o o n gk i m 2 6 1 等人在2 0 0 6 年 研究了含反馈的b m a p g l 专朋1 m ( 批量马尔可夫到达) 的串联损失制排队系 统，并给出了平稳条件存在的充要条件、系统队长的概率分布、等待时间的分布。 c h es o o n gk i m 1 7 1 等人在2 0 1 0 年研究了含有优先权顾客的和重试机制的有限容量的两 级串联系统，顾客以批量马尔可夫过程到达( b 心尸) i 级服务系统，i 级服务系统的服务 时间服从一般分布，级服务系统服务时间服从p h 分布。即 b m a p g l 专跗1 m ，当重试区域有f 个顾客时，重试时间遵循参数为巩的指数分 布。该文还探讨了当i i 级服务系统中顾客数达到m 个时，经i 级服务系统服务完的顾客 损失情况；考察了以i 级服务系统服务完成时刻为嵌入点的嵌入马尔科夫链以及在任意 时刻系统状态过程，研究了顾客直接进入i 级服务系统并得到服务的概率、级服务系 统损失顾客的概率；此外还给出了模拟准确的到达过程和服务过程的一个可行性的算 法。 最近，g o m e z c o r r a l 2 7 1 、m o w t z o u m s & l a n g a r i s 3 3 1 首次将重试排队加入了串联 排队系统中，并作了简单的研究。其中g o m e z c o r r a l 2 7 1 在2 0 0 2 年研究了 m a p 尸h 1 斗p h l k + 1 重试串联排队模型，主要运用了拟生灭过程方法，探讨了 马氏过程的无穷小生成元的正常返性，并用算法给出了一个近似解和一个修正的矩阵几 何稳态向量。m o w t z o u k i s & l a n g a r i s 3 3 1 研究了含有重试顾客的两级串联排队模型，以 母函数的方式得到了系统稳态概率分布及系统性能的一些相关的数字性结果，还讨论了 在无重试情形下的一些结果，并以指数服务作为特例进行了研究。c h es o o n gk i m 3 4 1 6 硕士论文 m m c 寸( m ) m i n l k 串联排队系统分析 等人在2 0 0 9 年又研究了含反馈的b m a p g 1 _ ( m a p ) i m c 的重试串联排队模型，这 种排队模型在远程数据传输及银行服务系统中的应用非常广泛，该文献运用嵌入马尔科 夫链的方法求出了稳态队长分布，马氏链遍历的充要条件及任意时刻的稳态队长分布； 任意时刻i 级服务系统的平均顾客数，i 级服务系统忙着的服务台数，优先权顾客与无 优先权顾客的损失率等相关指标。 1 5 本文的主要研究内容 本文主要研究了含特殊类顾客的m o ) m c f m ) m 以k 有限容量的串联排队 模型，它是在经典的m m 1jm m 1 的基础上，在i i 级服务系统等待空间内除了 i 级服务系统服务完的普通类顾客外，又添加了特殊类顾客的到达；将到达i 级服务系 统的普通类顾客改为成批到达，并且i 级、级服务系统各有c 、刀个并联的服务台，该 模型在分析公共服务排队系统中有着直接的应用日订景。论文用矩阵几何分析的方法得出 了系统模型的q 一矩阵，运用拟生灭过程的方法给出了系统平稳的充要条件、平稳队长 分布及其算法，i 级服务系统的平均队长；另外，由模型的特征还求出了i 级服务系统 的忙期分布( l s t l 及其在忙期内服务完的顾客数的p g f ，i 级服务系统受阻时间的l s t ( 或u 级服务系统的繁忙期) 。 7 第二章预备知识硕i ：论文 第二章预备知识 2 1 生灭过程 2 1 1 生灭过程的定义 设 x ( ，) ，t o ) 为具有状态空间，( 或如) 的连续参数齐次胁砌v 链，如果其转移 概率矩阵尸( ，) = ( 岛( 满足： 对任意的i ，j ， i b ，f + l ( ，) = 4 t + d ( r ) ， i b f - l ( f ) = 鸬f + d ( f ) ， i 既( ，) = 1 一( 五+ 以) f + d ( f ) ， l p o , ( t ) = d ( ，) ， 则 x ( ，) ，r o ) 为生灭过程。 2 1 2 生灭过程的微分方程组 丑 0 1 a o = o ，当f 1 时，鸬 0 1 2 0 = o ，i 0 i j - i i 2 如果系统在时刻f 处于状态，的概率，记为尸( f ) ，即 p ( r ) = 尸 ( ，) = f ) ， 经过无穷小时间缸，系统仍处于状态f ( 当状态空间有限时0 f k ；当状态空间 可数时0 f o o ) ，则可以用以下互斥事件来描述这一事件： ( 1 ) 在时刻，时，系统处于状态f ，经过缸时间后，状态无变化。则它的概率为 只( ，) ( 1 一以，一，a t ) + o ( a t ) ， ( 2 ) 在时刻，时，系统处于状态f 一1 ，经过出时间后，状态转移到f ，则它的概率 为 p l ( r ) 以一l a t + o ( a t ) ， ( 3 ) 在时刻，时，系统处于状态i + l ，经过f 时间后，状态转移到，则它的概率 为 只+ l ( ，) f + l a t + o ( a t ) ； ( 4 ) 系统在( t + a t ) 内发生两次或两次以上转移，它的概率为o ( m ) 。 当状态空间为有限状态时，由全概率定理可得： 只( t + f ) = o ) ( 1 一丑f 一，a t ) + p lo ) 丑一l a t + 只+ l ( ，) ，+ l a t - i - 0 ( 6 0 ，0 i k ， 方程两边同除以f ，整理后得 兰皇! 兰掣：五一，只一。( f ) 一( 丑+ ，) p ( f ) f 一一、一。 + 鸬+ 1 只+ l ( f ) + o ( a t ) ，0 f k ， 8 硕十论文 m 。m i c - ( m ) m i n l k 串联排队系统分析 两边对，取极限，即令f 一0 可得 只。= 乃一1 只一1 0 ) 一( 丑+ a ，) 只( f ) + k t + l + l ( t ) + d ( 址) ，0 f 0 ， ( 2 6 ) 存在，且与初始条件无关。 2 2 矩阵解析法与拟生灭过程 2 2 1 矩阵解析法 矩阵解析法是n e u t s 发明并创立起来的，这些年来在排队论研究中发挥了极其重要 的作用。有关这一方法的理论与应用，他分别在1 9 8 1 年和1 9 8 9 年发表了两本著作，用 心分布取代了指数分布，使传统的生灭过程发展成了q b d ，嵌入m a r k o v 链法发展成 了结构矩阵分析。在这一变化过程中，矩阵几何分布和矩阵指数分布应运而生，在随机 模型的分析中起着重要作用。由于朋分布可以逼近任意非负随机变量的分布，从而使 一般分布假定下的随机模型能够得到易于计算的逼近。 2 2 2 拟生灭过程 对于多服务台休假排队的研究一般选用拟生灭过程来处理，而q b d 过程这一术语 首先是e he v a n s ( 1 9 6 7 1 和w a l l a c e ( 1 9 6 9 ) 引用到排队论中的。它是经典生灭过程的最新发 展，也是经典生灭过程的一个新的推广，它把随机过程的状态空间由一维推广到多维， 这时矩阵的形式也为三对角形式，不过q b d 过程的生成元是分块的三对角矩阵而非数 q 第二章预备知识 硕 ：论文 字。由于各种多因素、变动参数、随机环境模型分析的需要，q 肋过程已成为当代随 机模型分析的重要工具。 设一个胁砌v 过程似( ，) ，( ，) ) ，其状态空间为 q = ( 后，力，k 0 ，1 m ， 若其状态过程的q 一矩阵能划分为分块三对角形式 q = a oc o 蜀 彳c ba c ( 2 7 ) 其中所有子块都是m 阶方阵，且 ( 4 + c 0 ) p = ( 尽+ a + c ) e = ( b + 彳+ c ) p = 0 ， a 和a 有负的对角元素和非负的非对角元素，其余子块均是非负阵，称( ，) ，( ，) ) 是一 个q s d 。 定理2 2 1 【2 】过程q 正常返，当且仅当矩阵方程 】，2 召+ 刚+ c = 0 ， 的最小非负解为r 的谱半径s p ( r ) l ，并且线性齐次方程组 ( 4 + r b , ) = 0 ， 有正解。 这罩巩= ( 死1 ，死2 ，2 k m ) ，七0 为过程9 平稳概率向量。 参考文献m 扰船 6 0 9 8 1 ) 中的引理1 5 1 与定理1 5 1 ，并引用类似于定理1 7 1 的证 明方法，我们有如下叙述： 对于m a r k o v 过程的9 一矩阵有如下形式： q = 彳o a la o a 2a 1a o b o ，b 0 1 分别是( 朋l - m ) x ( 肌l - m ) 、( 所l - m ) xm 阶矩阵，反。是m ( 一所) 阶矩阵， b 。、4 均为, r 阶方阵，且、骂。、么。均为非奇异矩阵，码聊，七= 1 , 2 ， 记 f， 玩。 1 研捌2 l 壹驴色。童胪- b k 。| ， 、膏= l七= l 其中月是方程x 4 = 0 的最小非负解。 定理2 2 2 6 0 】若印( r ) l ，则阶方阵b 【r 】是一个生成子。 硕士论文 m 。m c _ ( 肘) m n k 串联排队系统分析 定理2 2 3 川q 是正常返的充要条件为印( r ) 0 ，使得 ( x o ，置) 研月】= 0 ， 此时q 有平稳概率向量( x o ，x 1 ，x l r ，x 1 r 2 ，) ，且x o p ( 。训4 - x l ( ，一r ) - 1 p 。= l 。 此处i s e , = ( 1 ，1 ，1 ) 7 为i 维列向量，江1 , 2 ， 令彳= a 。，m 维行向量万满足： 七= o n a = o ，恐。= 1 ， 显然向量万、矩阵r 均与马尔可夫过程q 的边界条件有关，从而有 定理2 2 。4 对于马氏过程 q = 玩4 骂a la o 4a 1 a o 若a = 鸽+ a i + 么2 不可约，则印( 月) 0 存在时，我们称f ( s ) 为厂( f ) 的拉普拉斯变换，简记为l s t 。 性质1 ：当随机变量彳的概率密度为厂( f ) ( f 0 ) ，且e x ”存在时，n - 倒= 一f 一( 0 ) e x 2 = f 矿( 0 ) e x ”= ( 一1 ) ”f ( 帕( 0 ) 性质2 - ( 卷积性质) 设随机变量x 、y 的概率密度分别为厂( f ) 和g ( ，) ，其相应的l s t 分别为f ( s ) 与g ( s ) ，若存在z 的概率密度为乃( ，) ，且 厅( ，) = 厂( ，) 宰g ( ，) = 上( f f ) g ( f ) d f ， 则厅( f ) 的l s t 为： 日( f ) = f ( t ) o ( ，) 1 2 硕十论文 m 。i m i c - ( m ) i m i n l k 串联排队系统分析 第三章含特殊类顾客i r m j m cj ( m ) m 聆k 串联排队系统概率分 析 3 1 模型描述 论文研究的是含特殊类顾客的m i m i c 一( m ) m i u k 两级串联排队系统，模型 如图所示。 m 工众 i心 力1 普通； 蹶徽莎 批输入 i 级服务台 图1 模型假定： ( 1 ) 顾客以参数为见的p o s s i o n 流成批到达i 级服务系统，每批的批量为一随机变量 x ，且p ( x = f ) = p ，= 1 , 2 ，n ，n 为一正整数，此类顾客称为普通类顾客。 ( 2 ) 设e ( x ) = b ，d ( x ) = 盯2 ，且x 的概率母函数( 尸甜) 为x ( z ) 。 ( 3 )i 级服务系统有c 个服务台，每个服务台的服务时间独立同分布，均服从参数为期 的负指数分布，不妨设1 c n 。 ( 4 )i 级排队系统的等待空间为。 ( 5 )级服务系统有刀个服务台，每个服务台的服务时间独立同分布，均服从参数为 ：的负指数分布。 ( 6 ) 特殊类顾客为不经过i 级服务系统，直接进入i i 级服务系统接受服务的顾客，特 殊类顾客以参数为厶的p o s s i o n 流到达i i 级服务系统。 ( 7 ) i 级服务系统的服务时问记为置，其分布函数为蜀( ，) ，i i 级服务系统的服务时间 记为e 。，其分布为e 。( ，) 。 ( 8 )i i 级服务系统的容量有限，且设为k 。当级服务系统中少于，2 个服务台服务时， 经i 级服务系统服务完的普通类顾客可以进入级服务系统，要求服务；当i i 级 服务系统中服务台都处于服务时，经i 级服务系统服务完的普通类顾客不能进入 1 3 第三章含特殊类顾客的m m c _ ( m ) i m i n l k 的串联排队概率系统 硕十论文 级服务系统，这时该普通类顾客暂时停留在i 级服务系统服务台前，同时其他 c 一1 个服务台立即中断服务，直至该普通类顾客离开被占的i 级服务台；但此时 特殊类顾客可以进入级服务系统要求服务，即特殊类顾客最多到达k 一刀一1 。 ( 9 )当级服务系统的容量达到k 时，到达的特殊类顾客必须离开i 级服务系统或整 个串联服务系统，永不再来。 ( 1 0 ) 普通类、特殊类顾客到达间隔，普通类到达批量，i 级服务系统服务时间，级 服务系统服务时间均相互独立。 设厶o ) ，l 2o ) 分别为时刻f 时，i 级服务系统的队长( 包括正在接受i 级服务台服 务的普通类顾客) ，i i 级服务系统的队长( 包括正在接受级服务台服务的顾客以及接 受完i 级服务台的服务，因受阻而未离开i 级服务系统的那个普通类顾客) 。于是它们就 构成系统的二维状态过程 仁。( ，) ，三：o ) ；f o ) ， 状态空间为 e = 砸，) ：f 0 ；0 歹k 各个状态可以按下列规则排列： ( o ，o ) ，( o ，1 ) ，( o ，甩) ，0 1 9 ( 0 ，k ) ， ( 1 ，o ) ，( 1 ，1 ) ，( 1 ，刀) ，( 1 ，k ) ， ( 2 ，0 ) ，( 2 ，1 ) ，( 2 ，玎) ，( 2 ，k ) ， g ，o ) ，i 9 1 ) ，( f ，刀) ，o ，k ) i = 0 , 1 2 ， 由系统的模型假设可知， 厶( ，l l ：o ) ；，o ) 是一个尬砌v 过程。 3 2 状态过程的o 一矩阵 各变量可能的变化情况为：由于普通类顾客成批到达，此时i 级服务系统的队长 厶o ) 以概率p ，增加f 普通类顾客；或者c 个服务台服务完一个普通类顾客，此时厶( f ) 减 少1 ，1 f