（概率论与数理统计专业论文）单移除策略下的可修重试排队系统.pdf

中文摘要 摘要：基于顾客重试的排队理论源自电话话务服务问题的研究。重试排队系统由 于其合理的假设，以及在现代通讯网络、计算机网络、电话交换系统及供应链管 理等不同领域中广泛的应用背景，近二十年来得到许多专家学者的高度重视。 负顾客是一类特殊的顾客，它可视为一次误操作或是系统的灾难，一般是作 为系统的制约因素而存在，能抵消队伍中的正顾客。在重试捧队系统中，负顾客 和重试摔队系统的结合是比较新的研究方向，有负顾客的重试排队在研究顾客重 试行为的同时也刻画通讯网络中信号干扰、计算机网络中的病毒影响等现象。 此外，带有优先权顾客的重试捧队系统近来也受到广泛的关注。由于在通信 系统、电子计算机系统中，某些顾客必须获得优先服务，因此有优先权的捧队系 统的研究有着重要的应用背景。 根据实际问题的需要，本文建立并解决了三个带有负顾客的重试排队系统的 模型，即具有批量到达及负顾客的m i g i i 可修重试排队系统，具有二次选择服 务及负顾客的m i g i i 重试排队系统，有优先权及负顾客的m ，m ，g i ，g 2 i i 可修 重试排队系统。此外，我们还讨论了服务台故障的两种情况：一是由于机器自身 寿命而导致的服务器故障，二是由于负顾客到达而引起的服务器故障。文中应用 补充变量及母函数法给出了部分系统排队指标及可靠性指标，如重试队列中的平 均队长，系统可靠度，稳态故障频度及可靠度函数等。 关键词：重试排队；负顾客；优先权顾客；批量到达；二次可选服务；可修系统； 分类号：0 2 2 6 a b s t r a c t ： q u e u i n gs y s t e m sb a s e do nc u s t o m e l - 5 r e t r i a lb e h a v i o ra f es t e p p e df r o mt h es t u d y o ft e l e p h o n e8 e r v i c ep r o b l e m s d u et oi t sr e a s o n a b l ea s s u m p t i o n sa sw e l la sw i d e l y a p p l i e db a c k g r o u n d i nm o d e r nt e l e c o m m u n i c a t i o nn e t w o r k s , c o m p u t e rs y s t e m s , t e l e p h o n es w i t c h i n gs y s t e m sa n ds u p p l yc h a i nm a n a g e m e n t , r e t r i a lq u e u i n gs y s t e m s h a v ea t t r a c t e dt h ee x t e n s i v ea t t e n t i o no fl l t l m e r o n sa 【p a 忸a n ds c h o l a r si nt h er c c , c l l t t w e n t yy e a r s t h en e g a t i v ec u s t o m e ri sak i n do f p a r t i c u l a rc u s t o m e r , w h i c hc a l lb ev i e w e da sa l l i m p i 哪，盯m a n i p u l a t i o no rd i s a s t e ro fs y s t e ma n dm a yk i l lt h ep o s i t i v ec u s t o m e ri nt h e q u e u e i nt h er e t r i a lq u e u i n gs y s t e m , t h ec o m b i n a t i o no ft h en e g a t i v ec u s t o m e ra n d q u e u i n gs y s t e mi san e wr e s e a r c ha r e a , w h i c hs t u d yc i 衄佃m e r s r e t r i a lb e h a v i o ra sw e l l a ss i g n a li n t e r f e r e n c ei nt e l e c o m m u n i c a t i o nn e t w o r k sa n dt h ei n f l u e n c eo fv i r u si n c o m p u t e rn e t w o r k s i na d d i t i o n ，r e t r i a lq u e u i n gs y s t e mw i t hp r i o r i t ys u b s c r i b e r sh a sb e e na t t a c h e dg r e a t i m p o r t a n c et ot h er e s e a r c h e r s i nt h et e l e c o m m u n i c a t i o ns y s t e m ，e l e c t r i c a la n dc o m p u t e r s y s t e m s s o m e ：c u 蚍哪e 糟h a v et oo b t a i np r i o r i t ys e r v i c e t h e r e f o r e ，t h es t u d yo ft h i s k i n do f q u e u i n gs y s t e mi sb a s e do ni m p o r t a n ta p p l i e db a c k g r o u n d a c c o r d i n g t op r a c t i c a lb a c k g r o u n d , t h i sp a p e re s t a b l i s h e sa n dr e s o l v e st h r e er e t r i a l q u e u em o d e l s ，t h a ti s ，r e p a i r a b l e m i g i ib a t c ha r r i v a lr e t r i a lq u e u ew i t hn e g a t i v e c u s t o m e r s 细m g 1r e t r i a lq u e u e 、v i l hs e c o n do p t i o n a ls e i c ca n dn e g a t i v e c q l k g t o m e r s ，a n dar e p a i r a b l em ，m 2 c , ，g 2 1r e t r i a lq u e u e sw i t hp n o r i t yc a l s t o m e 葛 a n dn e g a t i v ea r r i v a l s f u r t h e r m o r e ，w ca n a l y z et w ok i n d so fs e r v e rb r e a k d o w n s ：o n ei s t h en o r m a lb r e a k d o w n s t h a ti st h es e r v 盯t h i sa ta nf i x e dr a t e ；n 豫o t h e ri sa b n o r m a l b r e a k d o w n s ，t h a ti s ，t h e8 e r v e rf a i l si m m e d i a t e l ya f t e ra na r r i v a lo fn e g a t i v ec u s t o m e r u s i n gas u p p l e m e n t a r yv a r i a b l em e t h o d ，w eg e ts o m ei n d e x e sf o rb o t hq u e u i n ga n d r e l i a b i l i t ym e a s u r e so fi n t e r e s t , s u c ha st h em 黜q u e u el e n g t h i nr e t r i a l o r b i t , a v a i l a b i l i t y , f a i l u r e 姻u e u c ya n dt h er e l i a b i l i t yf u n c t i o no f t h es y s t e m k e y w o r d s ：r e t r i a lq u e u e s ：n e g a t i v ec 1 l s m m e r s ；p r i o r i t ys u b s c r i b e r s ；b a t c h a r r i v a l s ； s e c o n do p t i o n a ls e r v i c e ；r e p a i r a b l es y s t e m ； c l a s s n o ：0 2 2 6 学位论文版权使用授权书 本学位论文作者完全了懈北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：导师签名： 签字日期：年月日签字日期：年月日 i e 立交显太堂亟掌缱j 佥塞独剑焦直明 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：签字日期：年月日 致谢 三年的研究生学习和生活中，我要特别感谢导师王金亭副教授。他无论是在 科研上。还是在平时的生活中，都给了我无微不至的关怀与鼓励。当我在课程学 习中遇到难点时，他总能以循循善诱的授课方式使我豁然开朗；当我在科研上遇 到困惑时，他给了我很多新的思路和方法，使我受益匪浅。他严谨的治学风格， 乐观积极、甘于奉献的生活态度，将永远是我学习的榜样! 本论文是在王老师的精心指导和关怀下完成的无论是在研究生课程学习过 程中，还是在论文选题、研究、定稿的过程中，王老师自始至终给了我大力的支 持和无私的关怀，在此向王老师表示深深的感谢。 感谢我同门的师姐师弟师妹。“三人行，必有我师”，共同的学习生活使我收 获颇丰。非常感谢在我攻读硕士学位期间给予我帮助的院领导和老师。我还要感 谢同窗三载的各位同学。我从他们身上学到了很多有益的知识和学习方法。三年 的同窗之谊，离别之际，更显珍贵。我为自己三年来生活在那种坦诚相待、互帮 互助的氛围中感到莫大的荣幸! 对父母及家人的感激是无法用语言表达的，他们对我的无私支持和鼓励是我 前进的最大源泉和动力。 最后，感谢各位专家、学者在百忙中审阅我的论文，并给出批评意见。在完 成本论文、即将踏入工作岗位之时，我深深地感到：自己每一步的前进，都离不 开老师、亲朋和同学的支持与教诲，在此表达我对他们最衷心的感谢! 梁玉哲 2 0 0 7 年1 2 月 于北京交通大学理学院 1 引言一模型研究的历史发展及应用背景 1 1 排队系统概述 1 1 1 排队论的历史与发展简述 排队论( o u e u i n g t h e o r y ) 又称随机服务系统理论，是研究系统由于随机因素 的干扰而出现排队或拥挤现象的规律性的一门学科，它通过研究各种服务系统在 排队等待中的概率特性，来解决系统的最优设计和最优控制。它适用于一切服务 系统，包括通信系统、交通与运输系统、生产与服务系统、存贮与装卸系统、管 理运筹系统以及电子计算机系统等。 排队论是运筹学的重要分支，也是应用概率的重要分支，所研究的问题有很 强的实际背景，它起源于2 0 世纪初丹麦数学家、电信工程师爱尔朗( a i ce 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 ) 对排队论作了系统的研究，他用马尔可夫链( m a r k o v c h m ) 方法研究排队论，并首先使用三个字母组成的符号表示排队系统，使排队论 得到进一步发展。特别是7 0 年代以来，随着计算机技术的迅猛发展，通信网的建 立和完善，信息科学、生命科学及控制理论的蓬勃发展均涉及到最优设计与最佳 服务问题，从而使排队理论与应用获得飞速发展。 1 1 2 排队系统的基本组成部分 排队是日常生活和工作中常见的现象。例如顾客到商店购物形成的排队；病 人到医院看病形成的排队；在售票处形成的排队等；另一种捧队是物的排队，例 如路口红灯下面的汽车、文件等待打印或发送等。 尽管排队系统是多种多样的，但从决定排队系统进程的主要因素看，它主要 由三部分组成：输入过程、捧队规则、服务机构。 1 输入过程输入过程是描述顾客来源及顾客是按怎样的规律到达排队系 统 ( 1 ) 顾客总数：顾客的来源可以是有限的也可以是无限的。 ( 2 ) 到达类型：顾客可以是单个到达，也可以是批量到达 ( 3 ) 相继顾客到达的间隔时间服从什么样的概率分布，分布的参数是什么，到 达的问隔时间之间是否独立 2 捧队规则一般分为等待制、损失制和混合： ( i ) 损失制：指顾客到达时，若所有服务台均被占，服务机构又不允许顾客等 待，此时该顾客自动离去，如通常使用的损失制电话系统。 ( 2 ) 等待制：指顾客到达时，若所有服务台均被占，他们就排队等待服务。等 待制又分为先到先服务、后到先服务、随机服务、有优先权的服务等。其中有优 先权的服务是指：在排队等待的顾客中，某些类型的顾客具有特殊性，在服务顺 序上要给予特别待遇，让他们先得到服务，例如病危病人先治疗，带小孩的顾客 先进站等。 ( 3 ) 混合制：等待制和损失制的混合，分为队长( 容量) 有限的混合制系统，等待 时间有限的混合制系统( 等待时问固定时间，否则就离去) ，以及逗留时间确限制 的混合制系统。 3 服务机构，刻划服务机构的主要方面为： ( 1 ) 服务台的数目。( 2 ) 顾客所需 的服务时间服从什么样的概率分布，每个顾客所需的服务时间是否独立，是成批 服务或是单个服务等，本课题研究的服务时问概率分布是一般分布。 1 1 3 经典排队系统的符号表示 个排队系统由许多条件决定，1 9 5 1 年肯德尔用三个字母组成的符号a b c 来 表示排队系统。其中a 表示输入分布类型，b 表示服务时间的分布类型，c 表示服 务机构中服务台的个数，一般用m 表示指数分布，用g 表示一般分布，后来在前两 个字母的右上角加字母以表示每次到达几个顾客与每次服务几个顾客，一般还假 2 定到达间隔时间序列为独立同分布的随机变量序列，服务时间序列也为独立同分 布的随机变量序列且这两个随机变量序列也相互独立。 图1 经典排队图 1 1 4 描述排队系统的主要数量指标 一个排队系统要从两方面考虑，即服务机构和顾客的利益来考虑，顾客希望 等待的时间越短越好，那就需要服务机构的服务台越多越好，服务速度越快越好； 而服务机构要想获得高的利润就必须优化考虑服务台的个数、服务速度以及服务 策略等。综合考虑排队的几个重要指标：队长、等待时间、服务台的忙期、系统 的服务强度和损失率等。 1 2 重试排队模型的历史发展及应用背景 重试排队系统的特征就是当顾客到达系统时如果发现服务台空闲，则立即接 受服务；如果发现服务台忙，就必须离开服务区域，进入重试区域( o r b i t ) ，经过一 段时间后再次要求服务，不断进行重试，直到重试成功。基于顾客重试的排队理 论源自电话话务服务问题的研究。最早的工作见于上个世纪4 0 - - 5 0 年代k o s t e n 1 】， w i l k i n s o n 2 和c o h e n 3 ，他们发现这类排队系统是分析电话网络中电话用户行为 的合适的数学模型。 自2 0 世纪7 0 年代以来，随着计算机通讯网络、异步转换模式( 删) 等高 新技术领域的发展，大量复杂系统设计和控制问题亟待人们解决。重试排队理论 由于其合理的假设，以及在现代通讯网络、计算机网络、电话交换系统、随机制 造系统及供应链管理等不同领域中都有着广泛的应用背景，近二十年来得到国际 运筹管理学界、应用数学界、工程学界等许多专家学者的高度重视及广泛应用( 【4 】、 【5 】、【6 】等) 。据统计，自5 0 年代至今已发表4 0 0 多篇相关论文，而其中6 5 的英 文文献是在1 9 9 0 一1 9 9 9 年间发表的( 参见【7 】) 。关于重试排队理论的专门国际会 议已经召开六次。同时，国际上一些重要期刊也都相继出版关于重试排队系统的 专刊，如 8 】等。1 9 9 7 年有f a l i n 等专著【9 】出版。总的来说，近二十年来此理论发 展十分迅猛。k o s t e n 谈到：“如果不考虑这种重试行为的影响，任何理论结果都应 被看作为可疑的( s u s p e c t ) 。”现在，重试捧队系统已被认为是排队理论和通讯网络 理论的一个重要组成部分，它在许多实际问题中得到了应用，如基于顾客重试的 g - n e t w o r k s ，呼叫中心问题，局域网冲突问题，c e l l u l a r n e t w o r k s 中服务质量问题等 等。 对于连续时间的重试排队系统，已经有不少作者进行研究，但是大多数关于 重试排队系统研究的文献，它们的重试时阃分布是服从指数分布。在最近几年，又 有不少作者对具有一般重试时间的m g i 排队模型进行了研究，1 9 9 4 年t y a n g 【t 0 采用一种近似的方法对具有一般重试时间的m g 1 排队模型进行了研究，1 9 9 9 年 a g o m e z - c o r r a l 11 1 对有一般重试时阃的单服务台重试排队系统给出了精确解，b i g - i s h n a k m n a r 1 2 于2 0 0 2 年考虑了具有b e r n o u l l i 休假的m g 1 重试排队模型。 b u f f e r 图2 重试排队图 有负顾客的排队模型是近年来的热点话题。1 9 8 9 年，g e l e n b e 1 3 首次在研究神 经网络模型时引入“负神经元”的概念，之后他又在计算机网络中引入“负顾客” 用以刻画异于传统的系统控制及服务模式。他把到达系统的顾客分成两类：一类 是正顾客，就是我们平时所说的顾客，他们必须接受服务后才可离开系统；另一 4 类是负顾客，他们到达系统后，若系统中有正顾客，则带走正在接受服务的正顾 客，本身也离开系统，若系统中没有正顾客，则他立刻离开系统，负顾客本身并 不需要服务。他认为负顾客虽然对正在排队的正顾客造成负面的影响，但是从整 个系统的平衡来说，负顾客的存在可能是系统处于稳态的因素之一。自从o e l e n b e 引入这个概念以后，带有负顾客的排队系统就被应用到各个领域，比如说排队网 络、随机神经网络、计算机网络、通讯网络等领域。 1 9 9 1 年，o e i d a b e , p g l y n n 和ks i g m a a t 4 对带有负顾客的m g 1 捧队系统傲 了稳态分析，其中负顾客的到来对系统的影响有两种：或是带走系统中正在接受 服务的正顾客，或带走队列最后一个顾客，并对这两种机制做了比较。j m f o u m e a u , c , e l b e , s o u r o s 0 5 允许系统有多种不同的顾客，负顾客到达带走成批顾客。而对 移除队列中最后一个正顾客的情形，p e t e rg h a r r i s o n 和f d w i g ep i t c ! 1 6 也傲了相 关的研究，他们得出了一种计算系统稳态队长的母函数的方法，他们用一个交互 式的运算法则得出了系统只有一个顾客时的稳态概率和顾客所得到的部分服务时 间的密度函数，这个算法比较复杂，包括了补充变量法，l a p l a c e 变换和三个数值 积分。 负顾客与重试排队的结合是比较新的研究方向，在最近几年才出现过。有负 顾客的重试排队在研究顾客重试行为的同时也刻画通讯网络中信号干扰、计算机 网络中的病毒影响等现象。 带有负顾客的重试排队系统虽然已有人研究过，但是前人所做的工作，无论 是整批移除还是灾难，负顾客的作用仅仅是带走正顾客。然而，在实际中，负顾 客既然可以被认为是“灾难”，那么它有可能不仅带走正顾客，同时还使得系统 处于瘫痪状态。比如说计算机病毒，它除了破坏当前正在被处理的程序或数据外， 它有可能使操作系统处于崩溃。 纵观负顾客的概念从引入到发展，负顾客到达对系统造成的影响是多种多样 的，大致可分为以下几种： ( 1 ) 单移除( i n d i v i d u a lr e m o v a l ) ：负顾客到达后，若系统正在工作，则带走正 在接受服务的正顾客；若系统处于空闲状态，则立即离开，对系统不造成任何影 响。 ( 2 ) 整批移除( b a t o hr e m o v a l ) - 负顾客到达后，带走固定数量或随机数量的正 5 顾客。 ( 3 ) 灾难( d i s a s t e r ) ：负顾客到达系统后，所有的正顾客( 包括正在接受服务的 和等待的1 全部自动被移除。 ( 4 ) 触发移除( t r i g g e r e dm o v e m e n t ) ：负顾客起到一个触发信号的作用，它把一 个顾客从一个节点移到别的节点或迫使整批的顾客离开服务系统。 ( 5 ) 随机移除( r a n d o mw o r kr e m o v a l ) ：负顾客在瞬间毁掉随机数量的工作。 本课题主要考虑的是在单移除策略下的可修重试排队系统，并根据实际问题 的需要建立一些排队模型，以期达到控制系统的目的。 1 3 本课题研究的主要模型及方法 本课题研究的是重试时间为一般分布的重试捧队系统。主要通过“嵌入马氏 链方法”得到系统稳态的充要条件，运用“补充变量法”得到系统的k o l m o g o r o v 方程，最终得到我们所考察的排队模型的稳态队长分布及我们感兴趣的系统的相 关性能指标。 根据实际问题的需要，本课题建立并解决了三个带有负顾客的重试排队系统 的模型： ( 1 ) 具有批量到达及负顾客的m g 1 可修重试捧队系统，在此模型中我们假 设正顾客是成批到达，批与批之间的到达是参数为a 的泊松流( p o i s s o nn o w ) 。批 量到达的排队现象是很常见的，比如在互联网络中，数据包的传递可以是随机数 目的。此外，模型首次讨论了服务台故障的两种情况：一是由于机器自身寿命而 导致的服务器故障，二是由于负顾客到达而引起的服务器故障； ( 2 ) 具有二次选择及负顾客的m g 1 重试排队系统，“二次选择服务”的特点 为所有到达的顾客都需要接受首次“主要”服务，但其中一部分顾客可能会进一 步要求服务台提供其它的服务，另一部分则选择离去； ( 3 ) 有优先权及负顾客的托，m ：o , ，0 2 1 9 修重试排队系统，本模型首次研 究了在不可靠的服务器中，将优先权与负顾客相结合的重试排队系统。其中，负 顾客的到来可能会导致机器故障。这种不可靠系统在通讯网络中有着广泛的应用。 6 2 具有批量到达及负顾客的m 一。g 1 可修重试排队系统 2 1 模型的应用背景 在实际生活中，我们经常会碰到服务台发生故障而不能为顾客服务的情形，如 银行的自动取款机发生故障，而导致顾客无法进行取款、查询余额等业务。此时需 要修理工人对发生故障的服务台进行修理( 或更换) ，修理完成后再继续为顾客服务， 我们把这类服务台可能发生故障且可修复的排队系统称为可修排队系统。显然可修 排队系统是从服务台的性能角度提出来的，而且人们对这类可修系统又提出了新的 研究课题，即不仅要研究系统的排队问题，同时还要研究因故障而产生的可靠性问 题，可用度和故障频度等。因此，对于可修排队系统，无论是从排队论的角度，还 是从可靠性理论的角度都是非常值得研究的。【1 7 】分析了一个服务台故障且可修的 m g 1 重试排队；y a n g 和l i 1 8 研究了一个具有服务台启动失效情况的重试掉队模 型；w a n g 等【1 9 】从可靠性的角度研究了一个可修的m g i 重试排队模型，并得到 了各种排队指标和可靠性指标。 此外，本模型不仅考虑了由于机器自身寿命而导致的服务器故障，还研究了由 于负顾客到达而引起的服务器故障，从而进一步将负顾客、修理及重试排队结合起 来。这样的模型更适合于对通讯网络中的噪音、信号干扰现象、计算机网络中的病 毒干扰现象的研究。 2 2 模型的描述 我们考虑一个具有批量到达及负顾客的m g 1 重试可修排队系统，假设： 1 成批到达系统中每一到达时刻不是到来一个顾客，而是到达一批顾客，每 批顾客的数目为一个随机变量孝，且p 亭- k ) - c , ，罗尼吒t * ，批与批之间的到达 筒 是参数为a 的p o i s s o n 流。 2 负顾客的到达过程是强度为a 一的泊松过程。 3 单服务器服务时间的累积分布函数是g ( x ) ，密度函数是酏【) ，失效率函 数是p ( x ) ，有有限的一阶矩卢，服务器前除了正在服务的顾客外没有其余的等待空 7 间。 4 正顾客( 包括新到达的和重试的) 到达系统时，若发现服务器空闲，则这 批顾客中的其中一个进入系统接受服务，服务结束后离开，其余进入o r b i t 中；若 发现服务器处于工作或修理状态，则全部进入o r b i t 中，不断进行重试，直到重试 成功。各个顾客重试时间相互独立并服从参数为6 的指数分布。 5 负顾客来到系统时，若发现服务器处于工作状态，它使得服务器马上进入修 理状态后立即消失，同时带走正在接受服务的正顾客( 若服务器处于工作状态) ； 若发现服务器处于修理或空闲状态，负顾客自然消失，不会对系统造成任何影响。 6 由负顾客导致机器损坏而产生的修理时间的累积分布函数为 i ( x ) ，密度函数 为h ( x ) ，失效率函数为v ( x ) 。有有限的一阶矩y 。和二阶矩r ：。服务器发生故障马上 进行修理，修好后进入空闲状态，等待顾客到来。 7 机器在工作过程中发生故障后，暂停服务，转而进入修理状态。顾客在服务 器中等待，待修理完成后继续接受服务。由机器自然损坏导致的修理时间的分布函 数为西o ) ，密度函数为石o ) ，失效率函数为9 ( x ) ，有有限的一阶矩磊和二阶矩元。 机器寿命x 服从参数为口的指数分布。 8 系统中包含的各随机过程假设为相互独立的 图3 有负顾客到达的可修重试排队系统 8 令c o ) 表示服务器在时刻t 所处的状态，c ( t ) 一o ，1 , 2 分别表示服务器在时刻t 处 于空闲、工作和修理状态。再令： 若c o ) - 1 ，宇( f ) 表示：在时刻f 正在接受服务的正顾客已逝去的服务时间。 c ( f ) 一2 ，仍o ) 表示：在时刻t 已逝去的修理时间( 由于负顾客引起) 。 c o ) 一2 ，仉o ) 表示：在时刻f 已逝去的修理时间( 由于机器自身故障引起) 。 这样，随机过程 ( c o ) o ) ，亭o ) ，仇o ) ，叩2 ( f ) ) ；f2o 就是一个马氏过程。 对一乏0 ，令 i o ) - p c o ) - o ，( f ) - 露) a r t ，工) 出- e c ( t ) , l , j v ( t ) - n ，石亭o ) 工+ 出) r o ，y ) 方- p c ( t ) - 2 , - v ( t ) - n ，yc 叩l o ) y + 砂 是( f ，j ，y ) c 耖- l c ( t ) - 2 , - v ( t ) - n ，亭( f ) - 而y t ，如o ) y + 方) 在此定义毋。( f ，工) - o ，足。o ，) ，) - 0 豆。以毛y ) 一0 ， 即在时刻f ，系统状态都可由随机变量( c o ) ，( f ) ，亭o ) ，o ) 叩2 0 ) ) 来描述。 2 3 状态转移方程及其解 ( 丢+ a + 脚) l ( f ) 一j ：e ( f ，工) ，l o ) 出+ f 民o ，) ，h ( ) ，) 西， ( 三a t + 三o x 1 e ( f ，工) 一一a + a - + - a ( x ) + 口) 只o ，z ) + a 砉q 见。( f ，毒) + r 是。而) ，) ，( y ) 方 ( 三a t + 三o y l 咒( f ，) ，) - 一( a + y ( y ) ) r o ，_ ) ，) + a 耋q r t ( f ，y ) 争专卜训) | - ( 州) 酏训m 耋饵胁_ ) ，) ( 2 3 1 ) ( 2 3 2 ) ( 2 3 3 ) ( 2 3 4 ) 边界条件： 只o ，o ) - a q ，- 。一，( f ) + o + 1 ) 6 ， + 。( f ) f = l 墨p ，o ) - a 1 只o ，x ) d x 最( f ，工，0 ) - a b ( t ，功 初始条件： h ( o ) - p c ( o ) 一0 ，( o ) 一田- 1 归一化方程为： 薹 l o ) + f 只p ，工胁+ r 足( f ，) ，) 方+ f f 忘以而_ ) ，毋) - 1 为解上述方程，定义下面的母函数： 。荟7 一。矽口o ，而z ) 。荟风o ，z 弦4 凡z ) 。荟r “y 矿 叫 是b 工，儿：) 。荟豆o ，而y 弦。箭 ( 2 3 5 ) ( 2 3 6 ) ( 2 3 7 ) ( 2 3 8 ) ( 2 3 9 ) c 。荟q r 啪 同时定义f ( f ) 的l a p l a c e s t i e l t j 髂变换为：f o ) 一f c x p 甜弦( f ) ，r e ( s ) ，0 。 定理2 3 1 状态概率的母函数及其拉氏变换为： f o ，z ) 一 忐篙尝1 ) - ah 蚴力，枷妒o ，1 ) + s c l o ，。o ) ” 。 a - h ( s + g - a c ( t ，a ) ) f ， b ， 、( s , x , t o ) d x + 1 ，若z ： 5 + a 一知( 珊) 。 ( 2 3 1 0 ) 曰g ，z ，；石三专 ； ；薹格 妒。，z y 。，z ，一a 一口p ，汕c 妒。，z 一1 g 3 。， 耶力。舞篱券端 蚴 肌力一塑业号黜端蒜半塑型 妒o ，z 即o ，z ) i 占( 妒( s ，z ) ) 一2i ( 2 3 1 3 ) 这里妒o ，z ) ：_ s + a 一丑c ( ：) + a 。+ 口一口石( 妒o ，z ) ) q ( s ，z ) ：一s + a 一舱( z ) 办。瓠器唧b 訾出卜 洲：。矗志唧缸害出卜 虿 o ，z ) ) - 1 一g o ，z ) ) 柏青韶z 。g o ，z ”存h 一1 肉的榍 【证明】对方程( 2 3 1 ) 一( 2 3 9 ) 取拉氏变换得： s o o ) 一1 - - x l o o ) + f 风o ，工) p o ) 出+ f r o ，y ) r ( y ) d y ( s + a + 开d ) l o ) 一j ：且o ，茗) p o ) 出+ j ：兄o ，y ) r ( y ) d y ，厅2 1 ( 2 3 1 4 ) ( 2 3 1 5 ) ( ，+ 去+ a + a 一+ + 口) e b 工) 一 砉q 口 一t o 力+ f j i i b 毛y ) 触) 西， ( 2 3 1 6 ) ( s + 专+ a + r ( ，) r y ，- a 套q r i 。“” g 3 ，乃 ( j + 专+ a + 尹。，) 毫瓴y ，- a 砉q 袁：一t o ， g 3 ，田 只“o ) _ a 耋c t r 一+ l ( s ) + o + 1 ) 6 乙+ - o ) ( 2 3 1 9 ) 1 1 r o ，o ) a j ：只o ，并) 出 最o ，而o ) = 口只o ，功 耄仁+ f e 仅工皿+ f 民o ，y ) 咖+ f f 豆伍毛) ，) 凼矽) - ( 2 3 2 0 ) ( 2 3 2 1 ) 佗3 2 2 ) 丹盯力程( z 3 1 4 ) - ( 2 j 2 1 ) 职撙幽裂伺： ( m ) 邝，加6 z 丝笋- 1 + r 耶，础) p o + r 耶，y ，咖( ) r 坳 ( 2 3 2 3 ) ( s + 去+ a + a 。+ p + 口) 口o ，x ，z ) - 知( z ) 口b 彬) + f 扇o ，工，y ，z ) f ( y ) a y ( 2 3 2 4 ) ( 专“呐，卜m c z 肌荆 砑 卜哟，卜训力毗力 厕 耶胁a 警邝力+ 6 笪笋 ( 2 3 功 z蛇，1 7 、 r o ，o ，z ) - a i ；b z 冲 瑚 j i o ，0 ，z ) - a b o ，毛z ) 佗3 2 外 解差分方程( 2 3 2 5 ) ( 2 3 2 6 ) ，并利用( 2 3 2 9 ) 得： j | 圣o ，工，y ，z ) - a b o ，工，：) e x p 一( s + a 一知o ) ) ) ，) 【1 一詹( ) ，) 】 尺o ，y ，z ) - r o ，0 , z ) c x p 一o + a a c ( z ) ) ) 】【1 一日( ) ，) 】 此外， f 蠢o ，训，z ) f ( y ) a y a b z 龋( a a c t o ) j ：r o ，y ，z ) r ( y ) a y r o ，0 z ) j l ( s + a 一知q ) ) 解方程( 2 3 堋有： ( 2 3 3 0 ) ( 2 3 3 1 ) b o ，毛z ) = 矿o ，0 , z ) e x p - 妒( s ，z ) 工 【1 一g ( 力】 且： ( 2 3 3 2 ) i 矿o ，石，z ) u ( x ) d z = b ( 0z ) g 。( 舳z ) ) 利用上述方程，由( 2 3 2 3 ) 可得： ( s + 五) ，) 地号字- l + 耶，g w ) ) 埘o ，m + 五一顾z ” ( 2 3 3 3 ) 联立( 2 3 2 7 ) ( 2 3 2 8 ) 及( 2 3 3 3 ) ，得到： 咖加坐型鼍糕拶坠型生坚 ( 2 ，均 艿 g 伽劫一刁尘= m 一掣g 砌卜 z ) 一a 一 。+ a 一五c ( z ) ) f o ，善，z ) 出一1 ( 2 3 3 5 ) 欲解方程( 2 3 3 5 ) ，利用与w a n g 等【1 9 】类似的方法， 考虑系数f ( z ) = g ( o ，z ) ) - z ，易见： ( 1 ) = g ( 矿( s ，1 ) ) 一1 0 则，( z ) 是凸函数，因此，( z ) 在区间【o ，l 】上恰有一个根国。 若z 2 国，即g ( ( j ，砌= ( - 0 ，由( 2 3 3 5 ) 可直接得到： ，。=2-h*(s+2i-2c(石co)f丽b(_s,x,to)dv+l 6 ) 若o z ，则系数g ( 妒( j ，z ) ) 一z 是严格正的，因此( 2 3 3 5 ) 在区间o z s 缈上 几她“巾r 篇篇掣却 m 北京蛮亟右堂亟堂位j 幺塞2 县直批量到达盈鱼厦查的丛：世q l 互篮重达挂丛丕统 这里 札加唧扛寄 咖 ，0 z 由 当) ，专国时，( ) 式的右边在积分号下的函数有无限阶，阶数为l ， 田一y 则积分r 习了弓蒲砂是发散的，因此函数与“z ) 一( z 哼功 另一方面，o ，z ) ，由此我们可以确定出常数c l ： c - = f 竺簖梨篇岩咖 因此( ) 可以简化为： ，。，z，=与。，z，r!：!；i耋；篆笔；紫砂，。szs国 。， 若国 t 石- 百 t c ( z ) ) 瓴o ，力妒s ，z )s + 五一j l c ( z ) ：口与碎丝三! ) _ 1 ! 二i ：尘墨二丝垃 妒o ，z ) lg ( 矿o ，z ) ) - zl s + 五一t c ( z ) o + 五一彳d z ) ) ，o ，z ) - i b o ，d h o + 2 一五“力) 一1 则定理2 3 1 可以证出。口 2 , 4 排队指标 定理2 a 1 当系统处于稳态时，则服务器与系统均处于空闲状态的概率为： j ： 刍盟2 i + a 一 + 口只+ c l ( o 1 ) 系统处于忙碌状态下的概率为： 曰：三一 l + 旯一 + c 哌+ c l ( o ，1 ) 系统处于修理状态下的概率为： 丑： 墨幺亟 i + a 一 + 砺+ c l ( o ，1 ) 【证明】由j 2 卿嘞o ，力，丑2 脚脚s b l o ，：) ， ：j - + u z j 删 且= l i m u 粤j f r o ，力+ j i i ( s , z ) l l l l 得。 z - ) lj l 一 这里c i ( o 1 ) 可由定理2 3 1 推出 1 6 ( 2 4 1 ) 定理2 4 2 p ( f ) = 打扣“的母函数由下式给出： 帅= 幽号芋趴刚，+ 豢别篇晶 妒【s ，z j烈墨r z j 尹【5 ，z j lg 妒j ，z ”一zl 伊o ，z ) c l o ，z ) 口( 5 ，1 ) + c j o ，z ) 一旯一b o ，1 ) h ( 矿o ，z ) ) 一1 卜c 2 ( j ，z ) ( 2 4 4 ) 以及在重试队列中对长的稳态分布吼= p r ( f ) = 疗) 的概率母函数为： 以。2 万面珂而万1 鬲硐 “a 一，耙( z ) ) c i ( o ，z ) + a i1 - h ( 五一枷( z ) ) i + 至! ! 竺鲨丛! 二竺望! 鱼! ! ：型二! ：! ：竺二竺! 鲨 ! 二竺望二竺f ! 二! ! 竺二竺鲨强。 ( o ，z ) lg ( 妒( o ，z ) ) 一zl ( 2 4 5 ) 【证明】由式p ( j ，z ) = 厂( j ，z ) + 矿( j ，z ) + f o ，z ) + 豆( s ，z ) 以及p ( z ) = 慨s p ( s ! z ) 可证得。 2 5 可靠性指标 僻匦笺篇黜蒜铲 、 矿o ，1 ) l5 c l ( s ，1 ) + ( s ，1 ) 一旯一j i l ( j ) l + 坚垫! 巡! ：竺二堕坐竺：竺翊 舳1 ) ( 5 ，1 ) + 她1 ) 一删( 5 ) j ( 2 5 1 ) 【证明】由下式可得： 一( j ) = ，( j ) + 口( s ) = 姆i ( j ，z ) + 口( j ，z ) 推论2 5 1 服务台的稳态可用度为： 彳： ! 刍型2 1 + a 一 + 口元+ c a o ，1 ) 1 7 ( 2 5 2 ) 定理2 4 2 服务器使用故障频度的拉氏变换为： o ) = 石而a 1 丽- s c 而2 ( s , 1 ) 、 ( s ，1 ) + s c l ( s ，1 ) 一a 一i l ( s ) 【证明】由下式可得： m ( j ) = c o b o ，1 ) = g i - m b ( j ，z ) 一 推论2 4 2 服务器的稳态故障频率为： 职：! 二一 l + a 一 + 嵋+ c j ( o , i ) 【证明】由下式可证： 乃= 卿