（运筹学与控制论专业论文）有限源重试排队系统.pdf

中文摘要 摘要：基于顾客重试的排队理论源自电话话务服务问题的研究。重试排队系统由 于其合理的假设，以及在现代通讯网络、计算机网络、电话交换系统及供应链管 理等不同领域中广泛的应用背景，近二十年来得到许多专家学者的高度重视。 有限源重试排队是一类非常重要的排队模型。它假设产生顾客的顾客源是有 限的。每个顾客源在空闲的时候会以一定的产生率产生一个顾客。有限源的重试 模型特别适用于研究星形局域网、电话通讯网络和遵循c s m a c d 协议的局域网 等的性能指标。 此外服务器损坏的模型也越来越受到重视。因为在实际生活中，服务器经过 一段时间的工作，总是会出现损坏的情况的。这在通信系统和电话银行系统中最 普遍。而把有限源模型与服务器可修相结合，更有挑战性，也更具实际和应用背 景。具有二次选择服务的重试排队模型在生活中经常出现，近来引起了人们的广 泛关注。在呼叫中心和电话银行系统中的应用很广泛，因为在这些系统中顾客都 有可能会需要额外的服务。 根据实际问题的需要，本文建立并解决了两个有限源重试排队系统的模型， 即关于m i g 1 k 有限源服务器坏且可修的重试排队模型，关于m i g 1 i l k 带二次 服务的有限源重试排队模型，文中应用补充变量及l a p l a c e 变换以及离散变换法 给出了部分系统排队指标及可靠性指标，如重试队列中的平均队长，忙期，等待 时间，系统可用度及可靠度函数等。 关键词：重试排队；有限源；等待时间；忙期；二次选择服务；可修系统； 分类号：0 2 2 6 a bs t r a c t a b s i r a c t ： q u e u e i n gs y s t e m sb a s e do nc u s t o m e r s r e t r i a lb e h a v i o ra r 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 es 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 s 弱w e l l 弱w 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 fn u m e r o u se x p e r t sa n ds c h o l a r si nt h er e c e n t t w e n t yy e a r s 1 1 1 ef i n i t es o u r c er e t r i a lq u e u e i n gs y s t e mi sak i n do fv e r yi m p o r t a n tq u e u i n g s y s t e m i ta s s u m e st h a tt h es o g r c eg e n e r a t i n gc u s t o m e r si sf i n i t e e v e r ys o u r c e g e n e r a t e sac u s t o m e rw i t hac e r t a i ng e n e r a t i n gr a t ew h e ni t sf r e e t h ef i n i t er e t r i a l q u e u i n gi se s p e c i a l l ys u i t a b l et om o d e lt h es t a r - l i k el o c a la r e an e t w o r k s ，t e l e p h o n e c o m m u n i c a t i n gn e t w o r k sa n dl o c a la r e an e t w o r k sw i t hn o n - p e r s i s t e n tc s m a c d p r o t o c 0 1 b e s i d e s ，t h eq u e u i n gm o d e l sw i t hs e r v e rr e p a i r a b l ea r ep a i dm o r ea n dm o r e a t t e n t i o no n b e c a u s ei nt h er e a l i t y , t h es e r v e rw i l lh a v eab r e a k d o w na f t e ri th a v e w o r k e dac e r t a i nt i m e i ti sc o m m o ni nc o m m u n i c a t i n gs y s t e m sa n dt e l e p h o n e b a n k i n gs y s t e m s i fw ec o m b i n et h ef i n i t es o u r c er e t r i a lq u e u ew i t hs e r v e rr e p a i r a b l e ， t h em o d e lw i l lb em o r ec h a l l e n g i n g , a n dw i t l lm o r er e a l i t ya n da p p l i e db a c k g r o u n d s 1 1 1 er e t r i a lq u e u em o d e l sw i t hs e c o n do p t i o n a ls e r v i c ea p p e a ri no u rd a i l yl i f e f r e q u e n t l y , i td r a wp e o p l e sa t t e n t i o nw i d e l yr e c e n t l y i t sw i d e l yu s e di nc a l lc e n t e ra n d t e l e p h o n eb a n k i n gs y s t e m b e c a u s ec u s t o m e r si nt h e s es y s t e m sw i l lp r o b a b l yr e q u e s ta e x t r as e r v i c e a c c o r d i n gt 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 w of i n i t e r e t r i a lq u e u em o d e l s ，t h a ti s ，m g 1 kf i n i t es o u r c er e t r i a lq u e u ew i t hs e c o n do p t i o n a l s e r v i c e ，m g 1 kf i n i t es o u r c er e t r i a lq u e u ew i t hs e r v e rb r e a k d o w n sa n dr e p a i r a b l e 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 h a st h em e a nq u e u el e n g t hi nr e t r i a lo r b i t , a v a i l a b i l i t y , w a i t i n gt i m e ，b u s yp e r i o da n dt h er e l i a b i l i t yf u n c t i o no ft 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 ；f i n i t es o u r c e ；w a i t i n gt i m e ；b u s yp e r i o d ； 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 0 ：0 2 2 6 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：走黼乡 签字日期：z 仍寥年6 月多日 导师签名 签字日期 日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除 了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也 不包含为获得北京交通大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的 同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了谢意。 学位论文作者签名：赵林_ 1 兰签字日期：劢口留年6 月 4 3 致谢 二年的研究生学习和生活中，我要特别感谢导师王金亭副教授。他无论是在 科研上，还是在平时的生活中，都给了我无微不至的关怀与鼓励。当我在课程学 习中遇到难点时，他总能以循循善诱的授课方式使我豁然开朗；当我在科研上遇 到困惑时，他给了我很多新的思路和方法，使我受益匪浅。他严谨的治学风格， 乐观积极、甘于奉献的生活态度，将永远是我学习的榜样! 本论文是在王老师的精心指导和关怀下完成的。无论是在研究生课程学习过 程中，还是在论文选题、研究、定稿的过程中，王老师自始至终给了我大力的支 持和无私的关怀，在此向王老师表示深深的感谢。 感谢我同门的师姐师弟师妹。共同的学习生活使我收获颇丰。非常感谢在我 攻读硕士学位期间给予我帮助的院领导和老师。我还要感谢同窗二载的各位同学。 我从他们身上学到了很多有益的知识和学习方法。两年的同窗之谊，离别之际， 更显珍贵。我为自己两年来生活在那种坦诚相待、互帮互助的氛围中感到莫大的 荣幸! 对父母及家人的感激是无法用语言表达的，他们对我的无私支持和鼓励是我 前进的最大源泉和动力。 最后，感谢各位专家、学者在百忙中审阅我的论文，并给出批评意见。在完 成本论文、即将踏入工作岗位之时，我深深地感到：自己每一步的前进，都离不 开老师、亲朋和同学的支持与教诲，在此表达我对他们最衷心的感谢! 赵林飞 2 0 0 8 0 年5 月rj l 于北京交通大学理学院 1 1 排队系统概述 1 引言 排队论( q u e u e i n gt h e o r y ) 又称随机服务系统理论，是研究系统由于随机因 素的干扰而出现排队或拥挤现象的规律性的- f - j 学科，它通过研究各种服务系统 在排队等待中的概率特性，来解决系统的最优设计和最优控制。它适用于一切服 务系统，包括通信系统、交通与运输系统、生产与服务系统、存贮与装卸系统、 管理运筹系统以及电子计算机系统等。 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 年代以来，随着计算机通讯网络、异步转换模式( a t m ) 等高新 技术领域的发展，大量复杂系统设计和控制问题亟待人们解决。重试排队理论由 于其合理的假设，在实际生活中的应用比较广泛。t y 觚g 和j g c t e m p l e t o n 2 4 】以 及g i f a l i n 2 5 和v g k u l k a r n i 和h m l i a n g 2 6 分别给出了重试排队模型的一个概 述。1 9 9 9 年a g o m e z c o r r a l 2 7 对重试时间服从一般分布的的单服务台重试排队系 统给出了精确解；b k r i s h n ak u m a r 2 8 于2 0 0 2 年考虑了具有b e r n o u l l i 休假的m g i 重试排队模型。它可以与负顾客、二次选择、批量到达等因素相结合。能较好的 描述现实生活中的一些模型。因此在现代通讯网络、计算机网络、电话交换系统、 随机制造系统及供应链管理等不同领域中都有着广泛的应用背景，近二十年来得 到国际运筹管理学界、应用数学界、工程学界等许多专家学者的高度的重视及广 泛应用。 1 3 有限源排队 我们平常假设排队模型的顾客到达率是一个常数。是因为我们假设顾客源是 无限的，每个顾客源以很小的产生率产生一个顾客，所以总的看来顾客的到达率 就是一个固定值。但是在很多情况下，我们需要考虑当系统中顾客增加的时候， 初始顾客的产生率将会下降。如：一个工人同时看管k 台机器，机器一损坏工人马 上进行修理。修好后机器还是可能会坏。此时，这k 台机器就是顾客源，工人就相 当于服务器。当要排队修理的机器增加时，新的需要修理的机器的产生率会下降。 有限源的重试模型特别适用于研究星形局域网、电话通讯网络和遵循c s m a c d 协 议的局域网等的性能指标。1 9 9 8 年自从k o m y s h e vy n 2 9 做出第一篇关于有限源 重试排队模型以来，有限源重试排队模型得到了很快的发展。关于排队论的比较 全面的结果可以在【1 7 】关于m g 1 k 的排队模型中找到。在有限源排队模型中，一 般的指标都是通过利用率来表示的。1 9 9 3 年t a k a g i 4 】介绍了没有重试的经典有限 源排队模型的详细回顾。g i f a l i n 和j r a t a l e j o 【5 】给出了有限源重试模型的具体 形式，并给出了解决方法以得到排队指标。解决有限源重试排队一般使用离散变 换法将平衡公式简化。利用补充变量和l a p l a c e 变换得到队长、忙期、平均等待时 间等指标。 在有限源排队的研究中，j s z t r i k 6 对有限源排队模型系统的概念及其应用作 了比较全面的介绍。在里面他例举了有限源排队的几个现实例子。并进行了分析。 指出了有限源排队在网络系统中( 特别是节点的描述中) 的用途。在他的论文里 面，他着重介绍了有限源排队模型在通信系统中的应用，尤其强调了有限源排队 在评价计算机系统模型中的有效作用。j s z t r i k 7 也对有限源重试排队进行了研究。 但是他使用的是m o s e l 数学软件，然后得到数值分析解。而并没有给出解析解。 同样，j r o s z i k 和j s z t r i k 8 也只是给出了数值解的形式。p h u o et r a n - g i a 3 0 对移 动通信网络的重试顾客模型实例进行了研究。随着通信事业的蓬勃发展，有限源 重试排队模型越来越受到人们的重视。特别是加上信道的模型，可以很好的评估 2 通信策略。 1 4 服务器可修 在以往的模型中我们总是假设服务器是不会损坏的。但是在实际情形当中， 经过一段时间的工作，服务器会损坏。这时候服务器必须进行修理。修理完成以 后继续服务顾客。而这方面的工作有比较实际的背景。在之前的二十年里面，人 们把太多的精力放在了研究重试排队上面。而服务器运行后损坏是在有限源重试 模型的基础上考虑服务器可修的论文至今还没有完整的文献，而这种情形更接近 实际也更合理。考虑服务器可修的模型，从可靠性理论的角度是很值得研究的。 c a oj i n h u a 和c h e n gk a n 【9 】在1 9 8 2 年第一次从服务器可修角度对 3 2 】的排队模型进 行了研究。接着在1 9 9 5 年b i nl i u 和j i n h u ac a o 1 0 】又对服务器有多种损坏的情形进 行了研究。在2 0 0 1 年j i n t i n gw a n g 和j i n h u ac a o 1l 】又对重试排队情形下的服务器可 修的模型作了研究。另：；r b n a w e lg h a r b i 和m a l i k ai o u a l a l e n 3 4 给出关于服务器可修 的重试排队模型的g s p n 的分析。现在可修排队模型在需要正确性和实时的系统中 的应用越来越多。并且，电话系统、电话银行和航空公司的一些重要的用户，他 们都要求公司证明在一段时间内，公司提供的服务是特别有效且能保证质量的。 l ij h ，和w a n gj t 在 3 3 】中给出了带二次服务和反馈的不可靠的重试排队模型。在 2 0 0 7 年，l a n ih a q u e 和m i c h a e lj a r ms t r o n g 2 3 给出了服务器受损的各种模型，对 各种模型情况进行了总结。t y a n g 和h l i 2 5 1 给出了服务器启动失败的重试排队模 型。 服务器损坏的原因比较多。一般有两种情况： l 、服务器由于寿命的关系，在经过一段时间的运行之后，服务器会损坏； 2 、由于灾难的到达，强行损坏服务器。 在服务器可修的情况下，服务台都是不可靠的。我们除了需要得出排队系统 的一般指标外，还需要得到系统的可靠度和可用度指标。这对于系统的评估和预 测非常重要。 而有限源排队加服务器可修的重试排队模型至今还没有完整的论文。而这模 型有着很强的实际背景。得出的排队队长、忙期、平均等待时间和可靠度等指标 能够很好的描述c s m a c d 协议的局域网等实际系统。 1 5 二次选择服务 还有在我们一般的模型中，我们总是假设顾客在接受完服务后马上离开。但 是在实际的情形中，顾客可能要求二次服务。比如在银行，顾客取完钱后可能还 要交电费；司机修完车以后，可能又想给车换个轮胎。这些都是随机的。而二次 服务的模型相对来说做的不多。又比如在呼叫系统、银行系统中，顾客常有忘记 密码的状况发生，为了不影响系统的正常运作，顾客需重新等待接受服务，在这 里我们可以把服务台验证用户口令或密码看成必要服务，之后顾客选择的查询余 额或取款等业务可以看成是可选服务。二次服务的情形在日常生活中很普遍。而 和有限源重试模型相结合，更是可以应用到星形局域网、电话通讯网络和遵循 c s m a c d 协议的局域网等地方。具有二次选择服务的重试排队模型在实际生活中 经常出现，近来引起了人们的广泛关注。其特点为所有到达的顾客都需要接受首 次“主要服务，而只有一部分顾客可能会进一步要求服务台提供其它的服务， 另一部分则选择离去。例如，所有的货轮到达港口后均需要卸载货物的服务，然而 只有一部分货轮在卸货服务完成后还需要再次装载货物的服务。【2 0 分析了一个具 有二次服务的m g l 排队系统；w a n g 2 1 研究了一个具有二次选择服务且服务台可 能会出现故障的可修排队系统；k u m a r 2 2 分析了一个具有二次选择服务且是优 先非强占规则的m g 1 排队系统。m a d a n 3 0 研究了带二次服务的m g i 排队模型。 其中，第一次服务时间是服从一般分布的，第二次服务时间是服从指数分布的。 这种排队情形可以在日常生活中看到( 看【3 0 细节) 。通过使用补充变量的方法， 他研究了这种系统的稳态条件下的情形和与状态和时间相关条件下的情形。 m e d l l i 【3 1 】也研究了二次服务时间是服从一般分布的模型。 1 6 本课题研究的主要模型及方法 本课题研究的是重试时间为一般分布的有限源重试排队系统。“有限源”是 指，产生顾客的顾客源是有限的，每个顾客源以一定的产生率产生一个顾客。而 我们一般假设顾客源是无限的，每一个顾客源的顾客产生率很小，总的产生率为 一个定值。我们主要运用“补充变量法”得到系统的k o l m o g o r o v 方程，最终得到 我们所考察的排队模型的稳态队长分布及我们感兴趣的系统的相关性能指标。 根据实际问题的需要，本课题建立并解决了两个有限源的重试排队系统的模 型： ( 1 ) 服务器坏且可修的有限源重试排队系统，在此模型中我们有謦个顾客源， 每个顾客源空闲时以率口产生一个顾客。在服务器工作时由于种种原因，服务器 以率五损坏。损坏后马上进行修理，修理时间服从一般分布。修理完成后，服务器 完好如初，继续服务原来的顾客。服务时间是累加的。 4 ( 2 ) 具有二次选择的有限源重试排队系统，“二次选择服务”的特点为所有到 达的顾客都需要接受首次“主要 服务，但其中一部分顾客可能会进一步要求服 务台提供其它的服务，另一部分则选择离去；同时顾客源还是有限的。 2 嬲厂2 r 偬有限源服务器坏且可修的重试排队模型 2 1 模型应用背景 服务器模型是排队论的主要模型之一。在很多实际情况下，由于种种原因我 们需要考虑顾客源有限以及服务器可能损坏的情况。而在这些方面的文献还比较 少，特别是关于重试的有限源排队更是寥寥无几。有限源且服务器可修的不含重 试排队模型在t a k a g i 7 】的论文中已经有过比较详细的介绍。b i nl i l l 和j i n h u a c a o 1 0 介绍了有含，个单元的可修服务器的排队模型。g i f a l i n 和j r a r t a l e j o 4 】 介绍了有限源重试排队的模型，并介绍了一些求解方法。n k j a i s w a l 1 3 介绍了离 散变换法，对于求解有限源重试排队很有用处。 一般的排队模型总是假设服务器是不会损坏的。然而在很多实际情况中，服 务器在服务顾客的过程中，经过长时间的工作，可能会不可预知的出现故障。例 如，在计算机系统中，服务器就可能会损坏：可能是由于病毒入侵或者硬件故障 等等。由于维修能力以及服务器损坏对系统有重要影响，我们很有必要研究在服 务器会出现故障并可修的情况下的系统的可靠性。这样的系统更加符合实际。 在这篇论文里边，我们研究了m g 1 k 的带服务器可修的重试排队模型。初始 的到达顾客由k 个顾客源来产生，1 k f ，c ( t ) = 1 ，o ) = 以，占lo ) ( 而工+ 石+ 出) ) 0 刀k l ( 2 3 2 ) 最。( f ，x ，j ，) = p 犯 f ，c ( t ) = 2 ，占lo ) = 五岛( t ) ( y , y + 砂) ，0 ，z k l ( 2 3 3 ) 只。o ) = 尸犯 f ，c ( f ) = l ，n ( t ) = ，1 ) 0 n k l ( 2 3 4 ) 只。( ，) = p 仁 f ，c ( t ) = 2 ，n ( t ) = 玎) 0 靠k 一1 ( 2 3 5 ) 以下列出平衡公式： 了d p o ( t ) ：一( ( k 一力) a + n 比) p o 。( f ) + c 。日。o ，石) 岛( x ) d x l 甩k l ( 2 3 6 ) 百d z c ( t ) = 胁( f ，x ) 6 l ( x ) 出 9 ( 2 3 7 ) _ o p l ( t , x ) ：一( ( k - n - 1 ) 口+ 五+ 岛( x ) + 拿) 弓。o ，石) o to x 0 5 刀k 一1( 2 3 8 ) + ( k 一，1 ) 媚一( f ，x ) + j c o 最。( f ，x , y ) b ：( y ) d y 掣。掣t = 一( ( k 咿1 ) 口+ + o i , 胁力。娜k l ( 2 3 9 )us 栉s 五一ll z ，y ， + ( k 一刀) 鸩川( f ，x , y ) 置。o ，0 ) = ( k 一, o a p o 。o ) + ( 靠+ 0 p o 。+ l o ) 0s 以k 一1 ( 2 3 1 0 ) 忍。( f ，五0 ) = 犯。( f ，曲0 刀k 一1 ( 2 3 1 1 ) ( f ) ，昂置( f ) ，置一。( f ，了) ，忍。一。( f ，五j ，) 都为o ，且异。( o ) = 只。( 0 ，x , y ) = o ，日。( o ，0 ) = l 。 弓。( o ，功= 万( x ) 瓯o ，其中万( 功，瓯。都是指示函数。 对各变量做l a p l a c e 变换， 。( j ) = r e - s t e o 。( t ) d t 缈l 。( s ，功= r e - s t p l 。( f ，x ) d t 仍。( s ，x ，y ) = 【p 叫最。( f ，x , y ) d t 则上面的等式( 2 8 ) 一( 3 3 ) 可以变为： ( s + ( 克一n ) a + n p ) 9 0 。( s ) = i ：仍。o ，x ) b l ( x ) d x 0 栉k 一1( 2 3 1 2 ) 石o ) = l 仍0 0 ，z ) 6 l ( x ) d r ( 2 3 1 3 ) 掣：一o + ( k 一刀一l 皿+ 力+ 6 l ( x ) ) 饩。( j ，功 吸 ( 2 2 1 4 ) + ( k 一以) ，。一l ( s ，z ) + 【仍。( j ，x , y ) b 2 ( y ) d y + 万( 石) 瓯。 半= 1 j + ( k 一刀一1 ) 口+ 吃( j ，) ) 仍。( s ，五y ) o n k 一1 ( 2 3 1 5 )卯u s sk lk z j 1 ) ， + ( k n ) a 9 2 。一l ( s ，五少) 仍。( j ，0 ) = ( k n ) a ( o 胁( j ) + ( 刀+ 1 ) , u p o 斛l ( s ) 0 n k l ( 2 3 1 6 ) 仍。( j ，x ，0 ) = 名仍。( s ，力0 疗k 一1 ( 2 3 1 7 ) 再次使用离散变换法( 2 2 6 ) 用沙。矗( s ) ，l 。( j ，x ) ，y 2 。( s ，而y ) 分别表示。( j ) ，仍。( s ，工) ，仍。( s ，x , y ) 的离散变换的映 射。则以上式子( 2 3 1 2 ) 一( 2 3 1 7 ) 可以变为： 1 0 ( j + ( k 一，竹一1 ) + ( m + 1 ) a ) v o 饼( s ) + ( m + 1 ) ( 口一) 少0 m + l ( s ) = 胁洲妒( 邢， 导杪l 。( s ，x ) = 一( s + m 口+ 旯+ 6 1 ( x ) ) 妙l 拼( s ，x ) 小：小 m ：方+ 一1 卜 = 0 一少2 。( 占，x ，少) = 一( s + ，竹口+ 6 2 ( y ) ) 2 。( j ，石，y ) j ；f ，l 。0 ，0 ) = ( ( 聊+ 1 ) 口+ ( k 一2 m 一1 ) ) 沙o 。0 ) + ( k m ) g f o 。一l0 ) + ( m + 1 ) ( 口一) y o 。+ lo ) i ；f ，2 。( s ，x ，0 ) = 五y l 肼( s ，力 由( 2 3 2 0 ) 可得： 0 m k 一1( 2 3 1 8 ) 0 m k 一1( 2 3 1 9 ) 0 m k l( 2 3 2 0 ) 0 m k - i ( 2 3 2 1 ) 0 m k - 1 ( 2 3 2 2 ) 2 。( s ，而少) = 2 。( s ，x ，0 ) e x p 一( s + r u f f ) y ) ( 1 一b 2 ( y ) ) 代入( 2 3 1 9 ) 得 晏( 蹦) ：七+ m 口+ 加一f 1 2 ( s + ，l 嘲+ 6 1 ( 枷( s ，功+ r 。b ( x ) 蹴 m ， 容易求得 少l 。( j ，力= e x p ( 一( j + m e g + 兄( 1 一殷( s + ，l 口) ) ) 功( 1 一b l ( z ) ) ( f ，l 。( j ，o ) + i1 ) f k 一1 1 h l ， 则( 2 3 1 8 ) 可以化为： p + 【k m l ，+ 【研+ 1 ) 口) l | f ，o 。( s ) + 【肌+ d ( a 一j 少o 。+ i p j = f l l ( s + m t t + a ”肿帆b + 一1 ) ) _ ( = 1 弘 用( 2 3 2 1 ) 和( 2 3 2 3 ) 除去y l 。( s ，0 ) ，整理可得： 册( s ) 杪o 。( j ) + y 脚( j ) y o m + l ( s ) 一1 r 哪( s ) o m - i ( 占) ：f k = - 1 ( f l l ( s + m o t + 名( 1 一反o + 所口) ) ) 一万( j ) ) 其中： ( 2 3 2 3 ) ( 2 3 2 4 ) 。( s ) = s + ( ( k m 一1 ) + ( m + 1 ) 口) ( 1 一届( s + m 口+ z ( 1 一及( j + 聊口) ) ) ) + m , u f l , ( s + m 口+ 旯( 1 一f 1 2 ( s + m a ) ) y 册p ) = ( m + 1 ) ( 口一) ( 1 一届o + m 口+ 名( 1 一展0 + 脚口) ) ) ) ( s ) = ( k m ) z f l l ( s + 朋口+ 2 ( 1 一历( s + _ ，l 口) ) ) 令m = k - 1 ，k - 2 , 仉由( 2 3 2 4 ) 式我们能得到： 沙。所( s ) = q ( j ) 刀( s ) + d 辨( 5 ) 由于少* l ( s ) = 0 ，则 g l ( j ) = 0 ，以一l ( j ) = 0 c k 一2 ( s ) = ( 反( j + ( k 一1 ) o r + 五( 1 一殷( j + ( k 一1 ) 口) ) ) ) - 1 ( 2 3 2 5 ) d a ：一2 ( s ) = - p 1 眦删也啪h 啪) 0 = 1 ) i z 。( s ) j 九( 5 ) + y 。( s ) d 。+ l ( s ) 一w m ( s ) d 一l ( s ) = 一s + m o ! + 2 ”肿啪 1 ，挖鬈一2 l ，玎k 一2 在( 2 3 2 3 ) 式中令m = o ，则 石( s ) = ( 届( s + 允( 1 一履( s ) ) ) 一( s + ( ( k 一1 ) + 口) ( 1 一d i ( s ! - 2 , ( 1 - 殷( s ) ) ) ) ) d o ( s ) 一( 口一z ) ( 1 一届( j + 五( 1 一反( s ) ) ) ) d 。( j ) ) x ( 1 + ( j + ( ( k 1 ) + 口) ( 1 一屈( s + 名( 1 一岛( s ) ) ) ) c j ( s ) + ( 口一) ( 1 一届( s + 五( 1 一尾( s ) ) ) ) q ( s ) ) 一 对万( s ) 求导： 万( o ) = 届( 0 ) ( 1 一五色( o ) ) + ( ( ( 足一1 ) + 口) 属。( 0 ) ( 1 一无色( 0 ) ) - i ) ( c o ( o ) + d o ( o ) ) 一( 口一) 磊( o ) ( 1 一丑色( o ) ) ( c j ( o ) + d 。( 0 ) ) 忙期的平均长度是： e l l 】= 一万。( 0 ) = 屈1 ( 1 + 丑反1 ) + ( ( ( k 一1 ) p + 口) 屈l ( 1 + 丑履1 ) + 1 ) ( g ( o ) + d o ( o ) ) + ( 口一) 属。( 1 + 编1 ) ( g ( o ) + q ( o ) ) 其中 届- = 喝( o ) ，包。= 响( 0 ) 其中的d o ( o ) ，d ，( 0 ) ，c o ( 0 ) ，g ( o ) 可以通过( 2 3 2 5 ) 式求得。 2 4 等待时间 令表示到来顾客所见的系统的状态。，其中i 表示服务器状态c 何。以是重试区 中的顾客数荆。定义向量石= ( 而，) 1 2 而= 仨 媸 t 等于o , s , r 分别表示顾客源处于空闲，接受服务和等待的状态。 ( 功= i ( x l = 厂) ( x ) 表示重试区中的顾客人数。 为了求得到来顾客的概率，我们从微观的角度来考虑。令x o 。表示一个集合，里面 有个褫同理集钒有k f 个元素 有k ( = 1 卜在同一集合 p 。幸= = p 。( ：) 一1p ，。，= = p 。j 【一1 ( k ，= - 1 ) 一1p ：。= = p ：。j r 一1 ( k ，= 一1 ) 一1 我们固定一个顾客源f 。，当此顾客空闲时，用p 。表示服务器空闲且重试区中有n 瓦= 一) p o r t * = k - i c 概。 同理可以定义多。和多：。，则： p 1 = ( k - 1 ，阡) p i n * = k - i c k - n - 1 慨。 多：。= c k 一，( 足：2 p 2 n * = k - c k - n - 1 ，p ：。 则所固定的顾客源乇为空闲的概率是： a p = ( 多妇+ p l 。+ 多2 。) = ( k a ) 一万2 己( p o 。+一+ p 2 。) 2 【 1 力 由此可得出，在第芘个顾客源是空闲得情况下系统状态的条件概率是： 万弧= 多。= ( p ) p o 。= ( 万) 卅( k 一刀) 印o 。 万l 。= 聂。= ( 多) 1 多l 。= ( 万) 以( k 一，l 一1 ) a p l 。 ( 2 4 1 ) 万2 。= 多2 。= ( 多) 一多2 。= ( 万) 。1 ( k 一，l 一1 ) 印2 。 当( 口) 时： 曰= ( 万l 。+ 万2 。) = ( 名) a ( k - n - 1 ) p i 。+ p 2 。) = ( 五) 一a q 1 1 + 9 2 1 ) = ( 名) 叫( ( 足一1 ) m o o 一脚0 1 ) = ( j 譬h v 2 ( 口一) ) - 1 ( ( 名+ v 2 ) k a 一( v l 吃+ k ( 2 + v 2 ) 口) j 7 ) 当口= 时： 利用( 2 2 1 6 ) 和( 2 2 1 7 ) 式子： 召：(k-1)(1-fll(a+2(1-,b2(a) k 一( k 一1 ) f l i ( 口+ 五( 1 一殷( 口) ) ) 以下开始求解平均等待时间。 为了简便起见， 令马( x ) = 1 2 。以及b ：( y ) = 1 - e 一。 列出稳态公式： ( 饭一n ) a + n l u ) p o 。= p l 。 ( 2 4 2 ) ( ( k n 一1 ) a + 1 + 2 ) p l 。= ( k n ) a p 嘶+ ( 刀+ 1 ) m o 叶l + ( k n ) a v l 。一l + p 2 。 ( 2 4 3 ) ( ( k 一以一1 ) a + 1 ) p 2 。= ( k n ) a p 2 。一l + 2 p l 。 ( 2 4 4 ) 设t = o 时，俐= n ( o = n 。我们令表示顾客的等待时间。用无( f ) 表示到时刻t 顾客还没有接受服务的概率。，( f ) 表示顾客补充等待时间的概率分布函数。 r - l 贝j jf ( t ) = ( 乃川石。( f ) + 万2 川六。( f ) ) ( 2 4 5 ) n = l 定理2 4 1 ：等待时间的各阶矩是： 2 - 1 e w ”】= 瓯。+ ( 万) q 以彦扩研乃”1 】 i = 0j = 0 因此平均等待时间是： 2r l 研w 】= ( 万) 。彦矿 i = 0j = 0 关于的各阶期望迭代求解可以参考 5 】的附录曰( 第4 2 3 页) 【证明】为了得到以上定理，我们要得到函数分布的解。我们引入马氏过程f ( f ) ： 它的状态空间是 0 , 1 ，2 ) 1 ，k 一1 ) 。它的状态转移率是： i 1 ，( j ，1 ) = ( o ，刀) g ( 1 朋一( ，。肘) = ( k 一力一1 ) 口， ( m ) = ( 1 ，力+ 1 ) i 兄， ( ，聊) = ( 2 ，刀) f ， ( _ ，m ) = ( 1 ，o ) ； g ( o ，。h ，辨) = ( 捍一1 ) a ( 歹，m ) = ( 1 ，撑一1 ) i ( k n ) c t( ，朋) = ( 1 ，1 ) 1 4 l 1 ( j f ，m ) = ( 1 ，玎) 眦埘) 2 1 ( k 一7 l 一1 皿( ，m ) ：( 2 ，靠+ 1 ) 厶( t ) = p f ( f ) ( 1 , 0 ) l f ( o ) = o ，疗) ) 则，平衡公式： 允( f ) = 一