（概率论与数理统计专业论文）矩阵分析方法在重试排队系统中的应用.pdf

北京变通大学硕士学位论文 中文摘要 中文摘要 摘要： 重试排队理论是排队系统的一个重要分支通过将离散时间重试排队系统广 泛约应甩子电话交换系统，计算机和通信两络，謦决了许多实际同题饲如，在呼 叫中心问题中，若打进电话的顾客遇系统占线忙音，则其隔段时间后可能会再进 行重试，直至获得所需服务我们通过对重试排队系统的性能分析，可以适当控制 系统，减少顾客等待时间，提高服务质量和效率 近年来由于离散时间排队系统在数字通讯系统和网络等一些相关领域的应 用越来越为广泛，更多的学者致力于离散时间排队系统的研充研究离散时间排队 理论鹊重要原因之一是在模拟计算枕两络和通讯系统对，它们内部的所有行为都 是发生在一些规则的时间点上，因此离散时问排队系统比其对应的连续时问排队 系统更为合适，也更贴近于真实的情况 2 0 世纪7 0 年代以来n e u t s 等系统地发展了结构矩阵分析方法，本文主要通 过矩阵分析方法，将离散时间m l c l l 重试排队系统的各种复杂状态，通过简明的 矩阵表示出来，并利用逼近算法，得到一些数值算例最终得到了系统重试空间的 平均等待人数等数值结果，并讨论了不同参数变化对结果的主要影确最后，分析 了一种连续时间的重试排队系统，通过该模型比较了矩阵分析方法对于处理连续 时间和离散时间问题的不同 本文的主要模型有： ( 1 ) 空竭服务多重休假离散时间g j g l 重试排队系统 ( 2 1 服务器可修的离散时间m e l l 重试排队系绕其中又根据其服务器寿 命的分布不同，分为几何寿命，固定寿命和一般寿命分别进行讨论 ( 3 ) 异步服务的连续时间m m 2 重试排队系统 关键词：离散时间a t l c l t 排队；重试排队；休假；可修排队矩阵分析方法；p h 分 右 分类号：0 2 2 6 北京交通大学硕士学位论文 a b s t r a c t a b s t r a c t a b s t a c t ：r e c e n t l y , t h e r e i s a g r o w i n g i n t e r e s t i n t h e a n a l ”i 8 0 f d i s c r e t e - t i m e q u e u e sd u e t ot h e i r a 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 rr e l a t e da r e o n eo ft h em a i nr e a g ) n sf o ra n a l y z i n gd i s c r e t e - t i m eq u e u e si st h a tm a n yc o m p u t e r a 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 eb a s i sw h e r ee v e n t sc a n o n l yh a l 5 p e na tr e g u l a r l ys p a c e de p o c h s ，w h i c hm a k e st h ed i s c r e 协t i m es y s t e m m o r ea p p r o p r i a t et h a nt h e i rc o n t i n u o u s - t i m ec o u n t e r p a r t s 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 sa ni m p o r t a n t b r a n c ho fq u e u e i n gt h e o r y r e t r i a lq u e u e i n gs y s t e m sh a v eb e e nw i d e l yu s e d t om o d e lm a n yp r o b l e m si nt e l e p h o n es w i t c h i n gs y s t e m s ，c o m p u t e ra n dt e l e c o m - m u n i c a t i o nn e t w o r k s f o re x a m p l e ，i nac a l lc e n t e r ，i ft h ec a l l i n gc u s t o m e rg e ta b u s ys i g n a l ，h em a yr e t r ya f t e rs o m er a n d o mt i m eu n t i lg e tt h es e r v i c en e e d e d w e c a na p p r o p r i a t e l yc o n t r o lt h es y s t e m ，r e d u c ec u s t o m e rw a i t i n gt i m e ，a n di m p r o v e 8 d t i c eq u a l i t ya n de f f i c i e n c yb ya n a l y z i n gt h ep e r f o r m a n c eo ft h ew h o l es y s t e m s i n c e1 9 7 0 s ，s t r u c t u r e dm a t r i xa n a l y t i cm e t h o dh a sb e e nd e v e l o p i n gr a p i d l y b yn e u t se t c b yt h i sm e t h o d ，t h i sp a p e rd e n o t e dt h ec o m p l e xd i s c r e t e - t i m e g i i g l lr e t r i a lq u e u e i n gs y s t e m sw i t hs t r u c t u r e dm a t r i c e s ，a n do b t a i n e ds o m e n u m e r i c a lr e s u l t sb ya p p r o x i m a t i o na l g o r i t h m s s o m en u m e r i c a lr e s u l t ss u c ht h e e x p e c t e dc u s t o m e rn u m b e r si nt h eo r b i ta r ed e r i v e dt os h o wt h ei n f l u e n c eo ft h e p 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 ec h a r a c t e r i s t i c s f i n n y , at y p eo fc o n t i n u o u s r e t r i a lq u e u e i n gs y s t e mi sp r e s e n t e d ，w h i c hd e n o t e sd i f f e r e n c e st h ed i s c r e t e - t i m e a n dc o n t i n u o u s - t i m es c e n a r i o sw h e r em a t r i xa n a l y t i cm e t h o di su s e d t h ei n a l nm o d e l sa r ea sf o l l o w s ： ( 1 ) d i s c r e t e - t i m ec i c 1r e t r i a lq u e u e sw i t hm u l t i p l ev a c a t i o n sa n de x h a u s - t i v es e r v i c ep o l i c y ( 2 ) d i s c r e t e - t i m eg i g 1r e t r i a lq u e u e sw i t hs e r v e rb r e a k d o w n sa n dr e p a i r s i nt h i sc a s e ，d i f f e r e n ts e r v e rl i f e t i m ed i s t r i b u t i o n sa r ec o n s i d e r e d ，i n c l u d i n gt h e t h e g e o m e t r i cl i f e t i m e ，d e t e r m i n i s t i cl i f e t i m ea n dg e n e r a ll i f e t i m e ( 3 ) c o n t i n u o u s - t i m em m 2r e t r i a lq u e u e sw i t hh e t e r o g e n e o u ss o r v e r s ， k e y w o r d s ：d i s c r e t e - t i m eg i g 1q u e u e s ；r e t r i a lq u e u e s ；v a c a t i o nq u e u e s ； r e p a i r a b l eq u e u e s ；m a t r i xa n a l y t i cm e t h o d ；p hd i s t r i b u t i o n c l a s s n o ：0 2 2 6 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留，使用学位论文的规息特授 权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索，并 采用影印，缩印或扫描等复制手段保存，汇编以供查阅和借阅同意学校向国家有 关部门或机构送交论文的复印件和磁盘 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名 签字f i 期：年月 日 导师签名： 签字日期：年月 日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书而 使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意 学位论文作者签名签字i e l 期：年月h 北京交通大学硬士学位论文第一章绪论 i i 重试排队系统 第一章绪论 排队论( 又称随机服务系统) 是研究系统由于随机因素的干扰而出现排队( 或 拥塞) 现象的规律性的一门学科，它的产生与发展均来自实际的需要排队论适用 于很多服务系统，尤其在交通与运输系统，计算机，通信系统，存储系统等方面应用 得最为广泛 在通信系统中，到达的顾客若发现服务台暂时不能提供服务，他会离开服务系 统面隔一段时间后重新来尝试接受服务重试排队系统就是为解决这个问题而提 出的重试排队系统的特征是：若到达系统的顾客受阻时( 可能是服务台处于工作， 修理或休假状态b 寸) ，他必须离开服务台而进入到重试空间( o r b i t ) 中，经过段时 间后又来到服务台尝试接受服务，详见f 1 ，2 ，3 ，4 】 1 2 离散时间排队系统 离散时间重试排队理论是排队论中的一个重要分支近年来，由于离散时间排 队系统在数字通讯系统和网络等一些相关领域的应用越来越为广泛，更多的学者 致力于离散时问排队系统的研究许多计算机网络和互联网的运作都是以离散时 间为基准的，它们内部的所有行为都是发生在一些规则的时间点匕其实研究离散 时间排队理论的重要原因之一是在模拟计算机网络和通讯系统时，离散时间排队 系统比其对应的连续时间排队系统更为合适，也更贴近于真实的情况在现实生活 中，离散时间排队系统已经广泛应用于模拟计算机和通信网络，详见i s ，6 ，7 ，8 ，9 ， 1 0 ，1 1 】 在离散情况下，时间轴被分成等长的区间( s l o t ，时隙) 我们在0 ，1 2 n 这些整点观察整个系统与连续时间排队不同的是，在离散时间排队中到达和离开 同时发生的概率不再是0 因此我们有必要设定到达和离开同时发生时的先后顺 序在以前的文献中，有这样两种规则：( 1 ) 如果到达在离开之前发生，这样的系统 称之为l a t ea r r i v a ls y s t e m ( l a s ) ；( 2 ) 如果离开在到达之前发生，则称之为e a r l y a 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 ) 规则对于l a s 系统我们进一步假设服务在一个时隙内无法完成，这被称 为l a t ea r r i v a ls y s t e mw i t hd e l a y e da c c e 黯( l a s - d a ) ，详细定义可参考h u n t e r 6 1 3 矩阵分析方法 以指数分布为基础酶经典生灭过程，是分析处理随机现象的基本工具之而 北京交通大学硕士学位论文第一章绪论 2 0 世纪中期以来，随着计算机通讯网络，柔性制造系统，异步传输系统，电子商务 等高新技术领域的发展，提出了大量复杂随机系统的设计与控制问题与传统随机 模型不同，这些系统表现出多层次，多位相，变动参数，随机环境等复杂特性经典 生灭过程在处理这些问题时存在着极大的局限性7 0 年代以来，n e u t s 等系统地发 展了结构矩阵分析方法，使随机模型分析由指数分布为核心发展到广泛使用位相 型( p h a s et y p e ，简记p h ) 分布的新阶段经典生灭过程发展为拟生灭过程，导致生 灭过程稳态分布的古老方法发展为矩阵几何解法这变化为复杂随机模型的分 析提供了强有力的工具在随机模型的研究和应用中广泛使用这些新思想和新方 法，已经成为当代流行的趋势详见【1 2 ，1 3 ，1 4 ，1 5 ，1 6 ，1 7 ，1 8 ，1 9 ，2 0 ，2 1 】 1 3 1p h 分布 经典的指数分布具有易于进行解析处理的有点，但也有明显的局限性假定顾 客的到达和服务时问，部件的使用寿命等服从指数分布，其不合理性显而易见在 广泛使用指数分布的经典随机模型分析中，我们在一定程度上牺牲了模型的真实 性和实际应用价值，才换得解析处理的方便长期以来，随机模型分析中一直存在 个突出矛盾：一方面，离开指数分布，随机模型的定量分析就面临着实质性的困 难：另一方面，假定所研究的随机变量服从指数分布，在多数情况下将与客观事实 大相径庭 p h 分布的出现则较好的解决了这一矛盾p h 分布是个有限状态m a r k o v 过程吸收时间的分布j e n s e n 1 2 首先把这分布用于一类经济模型n e u t s 1 3 1 成 功地发展了处理这类分布的矩阵分析技巧，其分布被表示成矩阵指数的形式，清晰 地显示出p h 分布类与指数分布类的深亥4 类比另一方面，p h 分布的不同位相适 合于描述具有多层次和变动参数的复杂随机现象因此，p h 分布类迅速成为当代 随机模型分析的有力工具 1 3 2 拟生灭过程 考虑离散情况下一个二维m a r k o v 过程( x ，y ) ，有状态空间a = ( t ，j ) ： i o ，j = 1 ，2 ，m 状态集 ( i ，1 ) ，( i ，2 ) ，( i ，m ) ) 称为水平( 1 e v e l ) i ，其状 态转移矩阵可写成( 1 3 1 ) 中的分块三对角形式p ，则称( x ，y ) 是一个拟生灭过 程( q u a s ib i r t h - a n d - d e a t hp r o c e s s ，简记q b d ) ，其中所有子块是非负价阶方阵， ( 山，0 + 如1 ) 1 = ( a 蚶一1 + 屯i + a “i ) 1 = 1 ，i 1 1 为元素全部为1 的m 阶列 2 北京变通大学硬士学位论文第一章绪论 向量 p = a o ，0a o ，1 a 1 ，0a 1 1a 1 ，2 a 2 ，l如，2a z ，3 a i a la ，件1 ( 1 3 1 ) 由矩阵p 的形式可以看出，q b d 是经典生灭过程从一维状态空间到二维状 态空间的推广经典生灭过程的状态x = i 现在被分解成m 个子状态( ，1 ) ，( i ，2 ) ， ，( i ，m ) 这一结构顺应了刻画过程在多层次，多位相变动参数情况下演化的要 求 根据结构的不同，拟生灭过程又可以分为两类： ( 1 ) 状态转移矩阵形式与p 相同的被称为与水平相依的( 1 e v e l - d e p e n d e n t ) 拟 生灭过程 ( 2 ) 状态转移矩阵尸形如( 1 3 2 ) 的被称为与水平不相依的( 1 e v e l - i n d e p e n d e n t ) 拟生灭过程 p = b c a 2 a 1 4 0 a 2a 1 a o a 2 a 1 a o 3 ( 1 3 2 ) h 以 砧 ! ! 星窒堕盔兰堡主兰垡望塞蔓三童窒塑竖墨墨重堡堡曼墼堕塑垒型型! 重堕! 坠墨丝 第二章空竭服务多重休假离散时间g i g 1 重试排队系统 2 1 模型描述 作为经典排队系统的推广，休假排队中允许服务台采取各种在某些时候不接 待顾客的策略，这些暂时中断服务的时间( 通常为随机变量) 统称为休假，详见【2 2 ， 2 3 】 我们考虑离散时间e a s 系统中单服务器的重试休假排队假设对于时刻 服务器结束服务和结束休假依次发生在区间( ，l 一，竹) ，顾客到达，重试和服务器休 假开始依次发生在区间( n ，矿) 顾客的间隔到达时间 独立同分布，分布函数为a l = p 代= f ，f - 1 ，2 ，t o o 假设0 as1 ，其中a = 1 e 豳服务器对顾客的服务时间q 为独立同分 布，分布函数k = p 仰= m ) ，m = 1 ，2 ，s o o 假设0 p 1 ，其中 p = 1 e 【町】 假设重试空问中每位顾客在一个时隙中重试的概率为p ，因此可用最= 1 一 ( 1 一，( i 1 ) 表示当重试空问中有i 个顾客时至少有个顾客进行重试的概率 假设系统为空时服务器进行休假，即空竭服务策略( e x h a u s t i v es e r v i c ep o l i c y ) 如果休假期间没有顾客到达，服务器将继续进行下一次休假否则，如果休假结束 前重试空间中非空，则服务器将在每个时隙内以概率6 结束休假，以概率( 1 一 继续休假 h l f a 1 7 ，1 8 1 详细讲述了利用p h 分布来表示离散情况下的般分布可以使| 可 题简化我们利用m f a 1 8 中剩余时间的定义方法，可将f 和”的一般分布分别 表示为p h 分布- ，t ) 和归，s ) ，a = ( a l ，a 2 ，啦) ，p = 帆，b 7 ，虬) ， t = ( ，。0 一t ，：) ，s 一( ，扣o r ，：) ， i ( i ) a20 ) 为一i 阶单位矩阵0 和0 7 分别为相应阶的元素全部为零的列向量 和行向量 令f = l t l ，s o = 1 一s 1 ，其中1 为相应阶的元素全部为一的列向量我 们仅考虑0 t ，s k + 时即为我们需要得到的值定义。( 七) = 0 茁( 1 ( 动一毒( 2 ) ( 七) 以此来表示两种算法相互间的逼近程度，显然，值越大，f 。( k ) 越小，即逼近算法的准确度越高在数值算例中，我们主要通过第一种逼近算法，在 保证e ，( 均足够小的情况下，给出模型的主要参数对系统的影鸭 2 4 数值算例 在这一部分中，我们给出一些数值算例来分析不同的参数对系统主要性能指 标的影响 假设n = ( o 0 5 ，0 1 ，0 0 5 ，0 2 ，0 1 5 ，0 1 ，0 1 5 ，0 2 ) ，= ( 0 4 ，0 3 ，0 2 ，o 1 ) 首先，固定七= 1 0 ，p = 0 2 ，令服务器在一个时隙内结束休假的概率分别为 0 2 ，0 5 和0 8 经验证，所有取值均满足定理2 3 1 给出的平稳条件且经过计算， 印( 1 0 ) 的取值分别为2 3 8 3x1 0 一，7 5 4 6x1 0 ，1 8 9 0 1 0 一，表明七取1 0 是合 理的令巩= 铂1 ( i 0 ) 表示重试空间中有i 个顾客的概率，则m 的分布如图 2 1 所示可以看到j 的取值越大，系统为空的概率也就越大类似的，图2 2 表示 在不同j 取值下哟随单个顾客重试概率p 的变化情况，这更好的说明了上面的论 述 图2 3 给出了重试空间中的平均顾客数e ( n ) 在不同j 取值下随p 变化的曲 线，同样可以看到随着d 的增加，重试空间中的平均顾客数也是减少的，而这些都 是与实际一致的 8 整望盔兰堡主兰垡! 竺茎 墨三雯至望垦墨堑耋堡堡塞墼堕塑堡! 型! 垦鎏笙坠墨丝 田2 ，1p = 0 2 时o r b i t 中顾客人数的概率分布 图2 2 霄0 随p 变化曲线 田2 3e ( n ) 随p 变化曲线 9 ! ! 室銮堕盔兰塑兰焦堡塞蔓三茎壁查矍亘堡塑塑墼堕旦堡型型! 堡丛堡坠墨丝 第三章服务器可修的离散时间g i g 1 重试排队系统 在实际中，我们注意到，服务器在对顾客提供服务时有出现故漳的可能，这就 使对不可靠系统的研究变得很重要尽管在连续时间系统下对不可靠重试排队系 统的研究很多( 如a r t a l e j o 2 7 ，w a n g 等【2 8 】) ，对离散系统的研究却相对较少特 别是至今还没出现过考虑服务器不可靠的离散时间g i g 1 重试排队系统的文献， 因此我们在本章中开始对此类排队系统的研究 3 1 服务器寿命几何分布 3 1 1 模型描述 考虑离散时间e a s 系统下单服务器的重试可修排队顾客的间隔到达时间f 独立同分布，分布函数为口l = p f = ：) ，f = 1 ，2 ，t o o 假设0 a s l ，其中 a = 1 e 煳服务器对顾客的服务时间口为独立同分布，分布函数6 仇= p 目= m ) ， m = 1 2 ，5 o 。假设0 p s l ，其中p = x e 嘲 假设重试空间中每位顾客在个时隙中重试的概率为p ，因此可用巩= 1 一 ( 1 一力( i 1 ) 表示当重试空间中有i 个顾客时至少有个顾客进行重试的概率， 假设服务器服务过程中在个时隙内发生故障的概率为q ，故障发生后，服务 器立即进入修理状态，正在接受服务的顾客则等待至修理结束继续接受服务服务 器的修理时间( 为独立同分布，分布函数k = p ( = n ) ，n = 1 ，2 ，d o o 假 设0 弘1 ，其中f = l e 葫 利用剩余时间的定义方法，将f ，叩和( 的一般分布分别表示为p h 分布= ( a ，r ) ，s ) 和( ，y ，d ) n = ( a l ，眈，a t ) ，p = ( b l ，k ，以) ，一r = ( e l ，o z ，白) ， t = ( z ：，：) ，s = ( m 0 叫t ：) 一( ，嚣。，：) ， i ( i ) ( i 0 ) 为一i 阶位矩阵0 和0 7 分别为相应阶的元素全部为零的列向量和 行向量 令t o = 1 一t 1 ，s o = 1 一s 1 ，其中1 为相应阶的元素全部为一的列向量这 样我们有m = a t s 。t o ，k = p s m 一1 s o ，岛= 1 伊d o ，1 l t ，1 mss ， 1 n d 我们仅考虑0 t ，d ，d o o 的情况，即所以的位相都是有限的 假设在修理结束后，服务器可按两种规则分别对被打断的顾客继续提供服务： 服务累积( p r e e m p t i v er 鹤u l n es e r v i c e ) 或者服务重新启动( p r e e m p t i v er e p e a t8 昏 访c e ) ( 见a t f a 2 3 1 ) 在第一种情况下，故障发生前的服务有效，顾客继续接受服务至 1 0 j e 星銮望丝堡主兰垡i ! 塞 星三至壁壹墨旦堡塑堕墼堕堕旦! 垡! 重堕堡坠墨丝 完成离开在第二种情况下，顾客重新以初始服务时间分布”接受服务我们用矩 阵q 表示在已知故障发生的位相吨服务重新开始时所处的位相矩阵口为8 阶 其中元素q 。表示服务被打断是出于的位相为 r t ，而结束修理后回到因此， 在服务累积规则下，矩阵q 为单位矩阵，而在服务重新启动规则下，矩阵q = 1 卢， 其中1 为s 阶元素全部为1 的列向量 3 1 2 马尔可夫链 考虑状态空间z ( f ，j ，z ，m ，n ) ：i o ；j = 0 ，1 ，2 ；l = 1 ，2 ，句n = 1 ，2 ，s - n = 1 ，2 ，d ；m ，n = 0f o rj = o 变量i 表示重试空间中的顾客 数j 表示服务器状态( j = 0 ，1 ，2 分别表示服务器处于空阂，服务和修理状态) ，l 表 示到达的位相，r n 表示正在进行服务的位相，n 表示修理所处的位相我们用第一 个变量i 来表示水平( 1 e v e l ) ，则该状态空间的m a r k o v 链的概率转移矩阵与( 1 3 ，1 ) 中矩阵p 相同，其各个分块的元素如下 ( 1 一巩) t( 1 一口) ( p d ) 。卢q ( f 口) 。芦。1 、 a j = i ( 1 一巩妒ps d ( 1 一曲i t o s + ( t o a ) o ( 即) 】矿p s p 7 + g ( t o n ) o ( s 印) 0 1i t 0 ( 1 一q ) t q d 。t o q 。d 4 - q t q 。( d 。2 0 o oo 、 a 。i + l ：= l 0 ( 1 一q ) ( 1 】p 口) o sq i t o a ) o s $ 7 i ， 0 ( 1 一神( p n ) 。口o d o ( t o o ) o q v d + 口( p n ) o o o ( d 0 7 ) ，0 巩( i 一口) ，。芦哪。卢。1 、 a 。一1 = io 巩( 1 一口) t o ( s 啊) 巩a t o ( s 啊) 0 7i ， o oo 其中0 为相应阶的零矩阵 服务器只有空闲和服务状态的c s l g l l 重试排队概率转移矩阵的各个分块 a l f a 2 4 中已经作出详细解释，区别在于我们用( 1 一口) 表示服务器在个时隙内 没有发生故障的概率因此这里我们仅对修理状态与服务器的其它两个状态( 空闲 和服务) 间的转移情况加以说明 矩阵a j 表示重试空f 葡中顾客人数没有变化的情况分块矩阵左下角矩阵为 0 ，表示在重试空间中顾客人数不变时，服务器不可能直接由修理状态转入空闲，这 是由我们假设中e a s 事件的发生顺序决定的因此，当服务器处于修理状态对， 在个时隙内只可能以概率( 1 一q ) t 圆0od o 进人工作服务状态，或者以概率 t o q 圆d + a t 固q o ( d 0 7 ) 继续留在修理状态其中t 圆q 圆d 表示修理没 有结束，而g roqo ( d o 们表示服务器结束修理后在同一时骧内再次发生故障， 根据假设这是有可能发生的q ( t o a ) o 卢o1 表示有个新的到达启动服务，服 务器在时嗽末端发生故障开始修理q t 固s 圆 + q ( t o a ) $ ( s o f 3 ) 07 表示服 务器由修理到修理状态的转移根据e a s 的定义，在个时隙起点服务可能结束 ! ! 塞奎堡盔兰堡主堂垡! 坌苎墨三至望墨矍里笪丝堡墼堕塑垒! 丝! 璧茎壁坠墨丝 或者转入下一位相，因此，g r0so7 表示没有到达且服务没有结束时出现故障， 口( 掣n ) 圆( s o 用p7 表示一次服务结束，新的到达启动服务后出现故障 矩阵a + 1 表示重试空间中的顾客人数增加1 这种情况下根据e a s 定义， 服务器在时隙起点和末甥都不可能处于空闲状态，因此分块矩阵的首行和首列全 部为零矩降q ( t o a ) osp r 表示有个新的到达，而正在进行的服务没有结束 时服务器发生故障( t o a ) o q o d + q ( t o a ) 圆q 圆( d 0 7 ) 表示了在修理状态自 身转移的两种可能：一种是有修理没有结束，另一种则是个时隙内修理完成但服 务器再次发生故障 a 扣l 表示重试空间中的顾客人数减少1 ，即有顾客重试成功这时由e a s 的 定义我们知道，服务器在时眩的起点不可能处于修理状态，而在时欧的末端不可能 处于空闲状态，故分块矩阵的首列和最后一行均为零矩阵吼q ? o 芦。一r 表示一个 顾客重试成功，服务器在其接受服务的过程中发生故障而在这个时隙内没有新的 到达晚g 丁o ( s o p ) o7 的解释与上面类似，区别在于重试成功前有一个顾客结束 服务离开 3 1 3 董近算法 如下 同样，根据2 3 节中的逼近算法，对于形式相同的转移矩阵p ，其各分块矩阵 ( 1 一o k ) tl 一曲( f n ) o 卢 a 1 = i ( 1 0 k ) t o s o ( 1 一q ) 矿o s + ( r o a ) o ( 。i 叩) l 0( 1 一口) t 9 0 0 d o 0 o k ( 1 一曲t o 芦 以q r o 卢o 、 2 = lo 以( 1 一g ) t 。( s 。卢) 以皿。( s 0 卢) 。1l ， 、l o o0 4 0 = a 件1 t 不随i 变化 这样，通过类似算法，矩阵p + 的平稳概率向量，口( 0s ls 七一1 ) 和重试空间 中的平均顾客数e ( n ) 可直接得到 3 ，1 4 稳定性条件 对于不可靠的排队系统，我们引入广义服务时间，这表示一名顾客完成一次服 务需要的全部时间，也就是顾客从开始接受服务到服务结束离开的时问，其中可能 包括服务器的修理时问我们用石表示广义服务时间，万也服从般分布在y u a n 和l i l 2 9 中，作者讨论了对应的连续时间下的稳定性条件，其中服务和修理时间均 为p h 分布，而服务器的寿命为指数分布接下来，我们将证明面也可以表示成离 散时间的p h 分布 订漱 帅一旧蕊 矿t ! 堕塑盔堂堡主堂焦堡塞笪三童垦壹量亘堡鲤曼墼堕塑垡型! 里达鲎坠壅丝 定理3 l 1 丽的分布为一个8 ( 1 + 田维p 日分布p ，y ) ，其中r = ( 反0 ) ， y = ( 1 - q ) s 搦) = ( 暑) 证明：类似的，我们用j = o 表示吸收态，即当前顾客服务完成的状态这是时间 百等于由初始状态以概率向量r = 徊，o ) 进入吸收态 o 这个过程的时闻新 的m a x k o v 链的状态空间变为五； o ，m ，n ) ：j = o ，1 ，2 ；m = 1 ，2 ，s ；n = 1 ，2 ，d ；m ，n = 0 o rj = o ) 我们可以得到其转移矩降 ( 者：三爹莒三二) 腿( 1 - - q ) sq 伽s 3 ) ，v o 三( 菩) 我们可以发现v 不可约，每行所有元素的和为1 根据p h 分布的定义( 详见l a t o u c h e 和r a m a s w a m i 【1 6 1 ) ，定理证明完成且 推论3 1 2 服务器寿命服从几何分布，修理时间服从一般分布的a z o l 瓣队系 统，其广义服务时问的期望为e l n o + g e f ( | ) ， 证明：由于定理5 1 中给出e 嘲= r ( f y ) 1 ，通过简单代数运算即可得到 推论3 1 3 服务器寿命服从几何分布，修理时间服从一般分布的g i l a 1 排队系 统稳定的充- t - $ 件为e 嘲( 1 + 口e ( c 1 ) e 阁 3 1 5 数值算伪 在这部分中，我们将给出一些数值算倒来分析不同的参数对系统主要性能 指标的影响 假设 a = ( o 0 5 ，0 0 5 ，o 1 5 ，o 2 5 ，o 0 5 ，o 1 5 ，0 2 ，o 1 ) ， p = ( 0 4 ，0 3 ，0 2 ，o 1 ) ， ，r = ( 0 6 ，0 3 ，0 1 ) 则f = 8 , s = 4 , d 一3 ，e 矧一4 9 5 ，e m = 2 , e 豳= 1 5 ， 1 3 ! ! 塞銮堕盔皇塑主兰些堡茎錾重竖壹矍旦堡笪塑墼堕鲤! 型堡盟蔓堡堡坠墨丝 首先，取k = l o , p = 0 1 令服务器在个时隙内发生故障的概率口分别为 o 0 5 ，0 1 和0 2 经验证，所有取值均满足推论3 , 1 3 中的稳定性条件且白( t o ) 足 够小令m = 巩l ( i 20 ) 表示重试空间中有 个顾客的概率，刚m 的分布及重 试空闻中顾客数的期望e ( 靠) 翔表3 1 所示， 表3 1 节= 0 i 时重试空间中顾客人数分布 从表中可以看到q 的取值越大，系统为空的概率( 粕) 也就越小原因在q 值 越大服务器越容易出现放障，因此更多的顾客须要在重试空间中等待接受服务，厌 而使丌。减爹 同时可以看到，同服务累积规则相比，服务重新启动规则下伽更小丽仉“ 1 ) 更大这是由于后者需要更多的时闻提供服务从而使重试空间为空的概率减，j 、 在图3 1 和图3 2 中，我们表示了在q 不同时，和e ( n ) 随p 变化的曲线 q 值和服务规则的变化对系统的影响同表3 ，l 的结果一致图3 3 则很好的刻画了 不同系统中椰随p 变化的情况 3 , 2 服务器寿命非几何分布 3 2 1 模型描述 在3 1 节中我们假设服务器服务过程中在一个时隙内以固定概率发生故障，两 在现实生活中往往不是这样，服务器的寿命会服从某分布本节中我们主要考虑 两种情况：固定寿命和随机寿命在固定寿命中，我们假设服务器的寿命固定为 j e 星窒鎏盔兰堡主兰垡坌塞蔓三童壁墨墅亘笪塑查墼堕囹坐型! 重蔓登坠墨笪 触t - b 脚q _ o _ h - a 咄p 图3 1 耶随p 的变化 r 脚h 呻p 图3 2e ( n 】随p 的变化 1 5 ! e 星奎望查兰堡主兰垡鲨茎墨兰至墨壹堡亘堡塑塑墼堕塑堡! 型! 里堇壁坠墨丝 个时隙，而对于随机寿命的