（概率论与数理统计专业论文）有负顾客到达的离散时间排队系统.pdf

北京交通大学硕士学位论文 中文摘要 中文摘要 摘要t 离散时间g 一排队系统，即有负顾客到达的排队系统。近年来成为排队系统 中的研究热点，离散时间排队在数字通讯，计算机网络以及b i s n 网络中有广泛 的应用在计算机通信和a t m 网络中基本单位是二进码或定长a t m 信元的持 续信元，数据或信号的到达均发生在在固定间隔的离散时间点上因此离散排队 系统更适合研究这一类问题由于不同的事件可能发生在同个时问点，因此需 要定义到达和离开的先后顺序 负顾客是相对于正顾客而出现的，是一种特殊的顾客，作为一种控制机制在 许多电信及计算机网络中有广泛的应用负顾客的到达会对系统产生负面的影响 在有等待空间的一般排队系统中，影响主要有sr c h ：负顾客到达移除队首的顾 客；r c e ：负顾客到达移除队尾的顾客；d s t ：负顾客到达移除系统内所有顾客； 负顾客到达导致服务器坏在重试排队系统中，影响主要有- 负顾客移除正在接 受服务的顾客；负顾客的到达导致服务器坏；负顾客移除o r b i t 内的所有顾客 本文我们共分析了三个不同的离散时闻g 一摊队系统分别为t 1 离散时间可修g e o g e o 1 o oc 广排队，模型为有排队空问的g 排队，考 虑r c h 和r c e 两种移除规则，负顾客的到达引起服务器坏 f 2 】两种到达模式离散时间可修g e o g e o 1g - - 重试排队，模型为重试g 排 队，考虑e a s 和l a s 两种到达模型，负顾客仅移除正在接受服务的顾客对系 统的其他没有影响 【3 】独立负顾客到达离散时问可修g e o g e o 1g i 广重试排队模型中正负顾 客的到达相互独立，负顾客导致服务器坏并且讨论了此排队模型和与其相对应 的连续时间排队模型的关系 在每个模型中我们分别讨论了离散时问g 一排队的马尔科夫链及其遍历条 件，并给出了系统在稳态条件下的性能参数以及负顾客对系统的影响最后将用 具体的数值来说明负顾客对系统的影响，在重试排队系统中还给出了随机分解法 则并据此得到了所讨论的队长的边界分布 关键词：离散时间排队；负顾客；重试排队可修；随机分解；马尔可夫链； 分类号t0 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 ：d i s c r e t e - t i m e q u e u e i n g s y s t e m w i t h n e g a t i v e c u s t o m e r s ，g q u e u e s h a sb e e nar e p a i di n c r e a s ei nt h el i t e r a t u r e d i s c r e t e - t i m eq u e u e i n gm o d e l sw a s w i d e l yu s e di nt h es l o ts y s t e ms u c h 鹄s l o t t e da l o h a a n da t mi nb - i s d n n e g a t i v e c u s t o m e r sb r eu s e da sac o n t r o lm ( 幽m l i s n li nm a n yt e l e c o m m u n i c a t i o na n d0 0 1 1 1 - p u t e rn e t w o r k s n e g a t i v ea r r i 诎h a v eb e e ni n t e r p r e t e da si n h i b i t o ra n ds y n c h r o n i z a t i o ns i g - n a l s 。8 0t h ee x i s t e n c eo fn e g a t i v ee u f f e o m e r sp r o v i d e sam e c h a n i s mt oc o n t r o l a l le x c e s s i v ec o n g e s t i o nc o n g e s t i o na tt h es y s t e m t y v i c a lk i l l i n gs t r a t e g i e sa r e r c h ：r e m o v a lo f c u s t o m e ra tt h eh e a d ；r o e ：r e m o v a lo f c n s t o m e ra tt h ee n d ；d s t ：r e m o v a l a l lc u s t o m e r si nt h es y s t e m ； i nt h i sp a p e rw ec o n s i d e rt h r e eq u e u e i n gs y s t e m s t h a ti s ： f 1 ad i s e r e t e - t i m eg e o g e o 7 1 g - q u e u ew i t hu n r e l i a b l e8 e r v 汀n _ i sm o d e l w ea n a l y s i sad i s c r e t e - t i m es i n g l e - s e r v e r c o n s i d e rb o t ht h ec a s e sw h e r en e g a t i v e c u s t o m e r sr e m o v ep o s i t i v ec u s t o m e r sf r o mt h e h e a do ft h eq u e u ea n d ，t h ee n do f t h eq u e u e 2 1 0 nt h eg e o g e o 1r e t r i a lg q u e u ew i t hl a t ea n de a r l ya r r i v a l s 眦 m o d e lw ec o n s i d e re a sa n dl a s ，a n dw eg i v et h ec o m p a r eo ft h et w om o d e l s 3 1 ad i s c r e t e - t i m er e t r i a lq u e u e w i t hn e g a t i v ea r r i v a l sa n ds e r v e rf a i l u r e s i nt h i sm o d e l ，i ti ss h o w nt h a t ，i nt h el i m i t i n gc a s e ，t h er e l a t i o n sd e v e l o p e dh e r e t e n dt ot h ec o n t i n u o u s - t i m ec o u n t e r p a r t i ne a c hm o d e l ，w ea n a l y s i st h em a r k o vc h s i nu n d e r l i n gt h eq u e u e i n gs y s t e m a n do b t a i ni t se r g o d i c i t yc o n d i t i o n w ep r e s e n t8 0 m ep e r f o m m n e em e a s u l - e so ft h e s y s t e m i n s t e a d y - s t e a d y , t h ee f f e c t o f n e g a t i v e c u s t o m e r s o n t h e s y s t e m f i n a l l y , s o m e n u m e r i c a le x a m p l e ss h o wt h ei n f l u e n c eo ft h ep 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 e c h a r a c t e r i s t i c s i nt h er e t r i a lq u e u e i n gs y s t e m ，w eg i v et h es t o c h a s t i cd e c o m p o s i t i o n l a w sa n da na p p l i c a t i o nw eg i v eb o u n d sf o rt h ep r o x i m i t yb e t w e e nt h es y s t e ms i z e d i s t r i b u t i o n so fo u i m o d e la n dt h ec o r r e s p o n d i n gm o d e lw i t h o u tr e t r i a l k e y w o r d s ：d i s c r e t e - t i m eq u e u e s ；n e g a t i v ec u s t o m e r s ；r e t r i a lq u e u e s ；s t o e h a p t i cd e c o m p o s i t i o n ；m a r k o vc h a i n c l a 8 s n o ：0 2 2 6 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留使用学位论文的规定特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存，汇编以供查阅和借阅同意学校向国 家有关部门或机构送交论文的复印件和磁盘 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名t导师签名； 签字日期t年月日签字日期t年月 日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果。除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料与我- n y - 作的同卷对本研究所馓的任何贡献均巳在论文中作 了明确的说明并表示了谢意 学位论文作者签名签字日期：年月 甘 北京交通大学硕士学位论文 第一章绪论 第一章绪论 1 1 排队论和离散时间g 排队简介及发展 排队论( 又称随机服务系统) 是研究系统由于随机因素的干扰而出现排队 ( 或拥塞) 现象的规律性的一仃学科它适用于一切服务系统，包括通信系统，交 通与运输系统，生产预算服务系统，存储与装卸系统管理运筹系统以及计算机网 络等 排队论源于电话服务理论的研究，1 9 0 9 年- 1 9 2 0 年丹麦数学家，电器学家 a k e r l a n g 用概率论方法研究电话通话问题，从而开创了这门学科3 0 年代中期 w f e l l e r 引进生灭过程的研究方法第二次世界大战以前其研究多侧重于电话和 距离通信方面的研究，发展较为缓慢二战后，由于排队论渗透到军事经济，生 产与服务的领域，理论和应用都有较大发展，使之成为运筹学管理科学的一个热 门分支，5 0 年代初d g k e n d a l l 用嵌入马氏链( a m a r k o v ) 方法研究排队论使排 队论得到了进一步的发展随着计算机的不断更新和发展通信网的建立和完善， 信息科学及控制理论的蓬勃发展均涉及到最优化设计与最佳服务问题 过去的十几年，有负顾客到达的排队系统( g 一排队) 成为研究的热点负顾客 区别于正顾客，他可以对系统产生各种影响t 删除排队中的顾客，删除正在接受 服务的顾客，删除重试排队中的顾客，或者导致服务器坏等多种影响这方面的 排队模型在实践中也得到了广泛的应用。负顾客作为一种控制机铡在通信计算机 网络中有着广泛的应用 1 9 8 9 ，g e l e n b e 1 1 首先在对神经网络进行建模时提出了负顾客的概念，用以刻 画正负神经元他陆续发表了一系列论文，把负顾客引入到排队理论及排队网络 中来【2 , 3 ，4 】之后在此基础上做了很多的工作连续时间( 广排队已经得到了很多 的研究 1 l ，1 2 ，1 3 】，但离散时间g 一排队系统近期才得到发展【5 ，1 6 ，1 9 ，2 2 ，2 3 本文 就是在这些基础之上研究离散时间g i 广排队系统的三个不同的模型 1 2 排队系统的基本概念 1 2 1 排队系统的组成成分 般排队系统由输入过程与到达规则，捧队规则，服务机构的结构，服务 时同与服务规则组成 1 、输入过程与到达规则输入过程是用顾客到达时间间隔时间来描述的根 据到达时间间隔所服从的分布可分为t 定长分布，( 负) 指数分布( p o i s 8 0 n 到达) 爱尔朗到达、几何到达( b e r n o u l l i 到达) 、负二项到达与般到达到达规则可以 北京交通大学硕士学位论文 第一章绪论 分为单个到达、成批到达，依时到达、移态到达等 2 、排队规则一般分为等待制，损失制和混合制在等待制和混合制中又可 分为先来先服务( f c f s ) 后来后服务l c f s ) 、随机服务( r o s ) 优先菲抢占服 务，优先抢占服务等在混合制中又分为队长( 容量) 有限、等待时间有限，此外， 还有顾客服务后反馈以及共同占用、占而不用等等今后，如不特别说明总认为系 统的排队规则为等待制先来先服务 3 、服务机构主要指服务台的数日。有( 有限) 多个服务台时服务的方式是并 联还是串联，服务时闻( 服务个顾客所用的时阅) 服从什么分布，服务时闻一般 分为定长分布。指数分布、几何分布与一般分布等 1 2 2 捧队系统的主要指标 对一个捧队系统的好坏进行评价要从顾客和服务机梅两方面币j 益来考虑 对顾客而言，总希望等待时间或逗留时间越短越好，所以希望服务台个数越多越 好但是，对服务机构丽言，增加服务台的个数。就意味着需要加大投资，增加多 了要造成浪费，那么增加多少最为合适呢? 顾客与服务机构考虑到自己的利益，非 常关注排队系统中的几个指标；队长等待时阆、服务台的忙期因此，这几个指 标就成了排队论的主要研究内容 1 队长：队长是指系统中的顾客数，也就是正在服务的顾客效与等待服务的 顾客数之和通常要求其分布和前两阶矩 2 等待时问从顾客到达系统时开始算起一直到他被接受服务时为止的这段 时问称为( 该) 顾客的等待时闻而称从顾客到达系统时开始算起一直到他被服务 完离开系统时为止这段时间为顾客的逗留时间，即顾客的等待时间与服务时问之 和我们也要求其分布和前两阶矩 3 忙期忙期是指空阿盼服务机构从有顾客到达系统时开始算起一直到服务 机构又没有顾客时为止的这段时间与忙期相对应的是闲期它是指服务机构从 开始没有顾客时算起一直到服务机构又有顾客时为止的这段时问对于有n 个服 务台的系统，通常还要讨论其k 阶繁忙期从系统中开始有k 个顾客在等待服务 时起一直到有一个服务台空闲时止这段时问称为该系统k 阶繁忙期零阶繁忙期 称繁忙期忙期、闲期、k 阶繁忙期也是随机变量般也要讨论它们的分布与前 两阶矩 1 3 离散时间。排队系统 离散时间排队系统中，事件均发生在个时间点上我们将时问轴分为均 匀的时隙( s l o t ) 顾客的到达、离开可能发生在同个时同点，因此有必要来定义 2 北京交通大学硕士学位论文第一章绪论 顾客到达、离开的先后顺序文献中常见有两种模型；( 1 ) 顾客的到达先于离开， 即l a s 模型( l a t ea r r i v a ls y s t e m ) ；【2 ) 顾客的离开先于到达，称此系统为e a s 模型( e a r l ya r r i v a ls y s t e m ) e a s 模型，在时间轴上我们将时间点记为0 ，1 ，2 ，r n 考虑任意个时间 点假设顾客的离开发生在时间段( i 一，仃1 ) ，到达发生在( 弘m + ) ，其中m 一( m + ) 表示m 时刻的前( 后) 一瞬问此模型可以甩图表示： dd 顾客离开。顾客到达 n + l a s 模型：在时间轴上我们将时问点记为0 ，1 ，2 ，m 考虑任意一个时间 点假设顾客的离开发生在时间段( m ，m + ) ，到达发生在( w $ - - , - 0 ，其中m 一( m + ) 表示m 时刻的前( 后) 一瞬间此模型可以用图表示： o 顾客到达顾客离开 1 1 + 负顾客的到达也两种方式：可能与正顾客混在起，以某个概率出现饲如 顾客的到达服从参数为p 的几何过程正顾客以q + 的概率出现，负顾客以q 一的 概率出现负顾客可能与正顾客相互独立出现，即为两个顾客流饲如正负顾客 分别以参数为p ，q 的几何过程达到，且相互独立此时我们需要定义正负顾客到 达的先后顺序 3 ! ! 夏至适盔兰堡主堂垡丝塞笙三雯堡墼堕塑要鳖鱼型垒! 型! 竺鱼二壁坠 第二章离散时间可修g e o c e o 1 o og 排队 2 1 模型的描述 假设从外界到达的顾客( 包括正顾客和负顾客) 时间间隔服从几何分布，到 达率为p p 表示在个s l o t 内到达的概率顾客分为两类r 正顾客和负顾客，分 别以矿和口一的概率出现( g + + q 一= 1 ) 正顾客到达系统后，若服务器空闲，则 立即接受服务，若忙。则排队等待负顾客到达系统导致服务器变坏进入修理态， 正在接受服务的顾客丢失，定义顾客( 包括正负顾客) 到达先于服务开始 服务过程为几何分布且相互独立，服务率为i ，其中s 表示在个s l o t 服务 没有完成的概率顾客接受服务完成后立即离开系统 服务器的修理过程亦服从几何分布n 表示在个s l o t 修理没有完成的概率 我们考虑e a s 模型 2 2 马氏链及稳态概率的求解 考虑时刻m + 。系统可由马氏过程= ( c k ， k ) ，来表示其中c m 表示 服务器的状态，取值为o ，l ，2 ( 分另q 表示服务器空闲、忙、坏) a f m 表示排队的顾 客数目可知其状态空间为 ( 1 ，) ：i = 0 ，1 ，2 ；知o ) 令稳态概率为 ”， 2 0 骢p 【= 1 ，= 纠， 死2 妻p = 2 ，= 明，k 0 ， 下面我们求稳态概率， 状态间的步转移概率尸i 坩，= p y 仇+ l = p l ，k = 为 足= 乒 只1 o j ( 0 o ) = 筇 只2 斟n 西= a f 尸h o ) ( 1 朋。p q + 只l 脚( 1 m = 硒+ j 抛+ 只即m o ) 一面崎+ 4 些塞奎巡堡主堂堡垒塞 箜三童塞墼堕回亘壁垡! ! 坦竺! 塑垒二韭坠 只l ，t 1 ( 1 辨= 印 r 2 ，1 ) ( 1 ，0 ) = a 矿 ，b ，0 l ( 2 期= 瑚一 只1 ，o ) ( 2 0 2p 叮一 o ) ( 2 t 0 ) = p q 一十。爹 只l ，k ) ( 1 ，耐= 印+ i p q + e c 2 ，k ) ( 1 耐= 却q + 只l ， ) ( 1 j2 够+ i 内+ p ( 2 ，k ) ( 1 ， ) = 却矿 只l ，k + 1 ) ( 1 ， ) = 筇 只2 ，i + 1 ) ( 1 ，i ) = 两 只1 t 1 ) ( 1 ，膏) = s p q + 只l ， ) ( 乏耐= 瑚一 只2 ，知) ( 2 肺= i x 一+ o 爹 r 2 ，i 一1 ) ( 2 肺= o z p q + p ( o 知) ( o 砷= 哥产+ p g 一一 日1 向( m i ) = i 矽+ p q 一一 最o ，女l ，肺= w + p ( o , - + l x l , k ) ；p ( 1 一r k + 1 ) + p g 一( 1 一产+ 1 ) 最l ，抖1 ) ( 1 。姊= i 敢l r + 1 ) + 搿一( 1 一r “1 ) 只l ，4 一1 ) ( 1 ，耐= ( 1 一南4 ) s p q + 由概率分析可得系统的k o l r n o g o r o v 方程为。 n o , o 2p r o , o + 莉。l ，0 + 咖o ，2 , 万l ， = a o 印q + 哟诲+ ( s 乒+ 印口+ ) 霄l + a p q + 万2 1 + 季哥霄l j + l + 压弦2 i + l + ( 1 一南， ) s z + 7 r 1 见，= 而艘一珊 + p 叮一n + ( p g 一+ q 却叻 + ( 1 一如- ) d ：职+ 殛扣l 归一化条件为， 哪+ ( 霄t + 霄玷) = 1 k - - o 定义母函数， 协( 力= 哪声，i = o ，1 ，2 ；o ； 0 在0 2 1 成立的完要条件是t 堕 l 一! ! ： i + s p q a + f w 一 ( 2 ) 若 丝： 1 一 塑： i + s p q 一丘+ a p q 一 则， 磐面面再万 矛面磊i 再i 矛未石丽可再丽鬲再丙丽 ：，!一 俯+ p 鼋一一卿+ s ) ( a p q + 。+ 舡) 一p q + p q 一 由引理可得。 妒1 ( 1 ) 二 伽( 1 ) 一 又由归一化条件t 可知： 职+ 啦+ q 船一) 丽i 矛= 矛酉丽i 面f 而丌0 o 两孑焉焉篝b 哪够i + 棚一一加+ s ) ( 丘w + 十砸) 一触+ 盯“” 妒i ( 1 ) + 忱( 1 ) + _ r o , o = 1 x o 一= l - - 罚p 丽q - ：一而p q + 6 ! ! 塞壅堕查堂堡主兰垡丝奎 复三童堕墼堕堕亘堡垒! 型壁型! 竺垡二竖坠 由丌0 0 可以得到 p q + ， 期一 i + 洲一a + a p q 一 为马氏链遍历的充要条件 由以上可以得到以下结论： 推论2 2 2 马氏链= ( ，m ) 遍历的充要条件是正j + s 】o q - 1 一 j a + l a p q - 推论2 2 3 “j 服务台忙时系境内等待顾客的概率母函数为； ，、p 口+ ( 一p q + 口z + p + 画画) 丌o d 妒1 2 面丽而万气矛面再面丁巧再丽了孑丽砜孑面i 雨再i 丽巧 ( 别服务台坏日中秉耽内等怿_ 咦器的兢平母函最为 妒：( = ) = 面面再河= 蔚函面再p 矿q - ( 再- p 面q + s 可z + 云p 巧+ 霄而) 两, o 币再云再蟊再丽 推论2 2 4 n j 系统内总寺寺顾客薮f u 的概率母函敷为二 ，、一p 口+ i p q + & z 2 一咖+ a ( 卢j + p ) + p c + s ( 面+ p ) l z + + p ) ( 乒画+ p ) 妒2 矛面再= 丽函万再酽河面叹面再砑f 巧矿石再葡再丽和p 彻系统内队长r m 的概率母函敷为： 纰，= 而舞笔矧搿薷装拦高烧黑絮砉笔丽哪 2 3 数值分析 这一节我们将用具体的数值箅饲来分析几个参量对系统的影响显然，选 择的参量数值需满足稳定条件 图1 反映的是q + 对服务器状态的影响随着矿的变大，正顾客增多服务 器忙概率变大，坏的概率变小面服务器空阕的概率在矿取适当值的时候可以取 到最小值 图2 考虑不同的服务率服务器空闲的概率取，= 0 7 5 ，0 7 ，0 6 ，o 逐渐变小 时，系统空闲的概率变大可以看出伽( 1 ) 存在最小值即q + 变大时，驴o ( 1 ) 将首 先减小，到达最小值时变大。这是由负蕨客的到达所引起的， 图3 描述的是系统排队人数的变化取_ = o 7 5 , 0 7 ，0 6 一e ( 州是关于q + 的个凸函数，存在个最大值 7 i ! 壅奎堕丕堂堡主堂垡堡皇 墨三重堡墼堕塑卫丝堡! ! 堡型! 塑鱼二堡坠 图2 1 正顾客的到达鼋+ 对系统状态的影响 图2 2 服务事不同对系统空闱的影响 b j 塞奎堕盔兰堕主堂垡鲨塞笪三童塞墼堕旦亘堡垒! 型! 塑! 竺璺二壁坠 图2 3 正顾客的到达矿对系统队长的影响 9 a ! 巫奎重盔兰堡圭竺垡丝塞 蔓三雯堕壁型姿堡壅堡墼堕塑里丝垒竺堡竺! 重堡垒：堡坠 第三章两种到达模式离散时间可修g e o g e o i 重试g 排 队 3 1 模型的描述 假设从外界到达的顾客( 包括正顾客和负顾客) 时问间隔服从几何分布，到 达率为p p 表示在个s l o t 内到达的概率。顾客分为两类t 正顾客和负顾客，分 别以q + 和q 一的概率出现( 矿+ q 一= 1 ) 正顾客到达系统后，若服务器空闲， 则立即接受服务，若忙，则进入o r b t 内等待重试定义顾客( 包括正，负顾客) 到 达先于服务开始 服务过程为几何分布且相互独立，服务率为i ，其中s 表示在个s o l t 服务 没有完成的概率 重试过程为几何分布且相互独立，重试率为f 。其中r 表示在个s l o t 重试 没有成功的概率 3 2 马氏链及稳态概率的求解 首先考虑e a s 模型 dd n + 顾客离开0 顾客到达重试 考虑时掰m + ，系统可以用马氏过程y ，m = ( c k ， f m ) 来表示其中c k 表示 服务器的状态，取值为0 ，1 ( 分别表示服务器空闲、忙) r m 表示捧o r b i t 内重试 的人数可知其状态空间为 ( f ，k ) ：i = 0 ，1 ，k 0 1 令 嘶5 ，规p = o ，= q 可l 。，里p i e = 1 ，= q ，i 0 ， 1 0 j ! 塞壅堕盔兰堡堂垡丝塞箜三里亘壁型姿坚墨堡墼堕塑旦堡璺塑丝竺! 里堡垒：堡坠 表示其稳态概率，下面我们求其稳态概率 状态间的步转移概率f 0 = p + l = l y m = f j 为， 只仉) ( o 埘= 庐一十p g 一产 日l ，b ) ( o ，q = i 矽。+ 册一一 只o 耐0 ，埘= 期+ 巧l ，k ) o ，耐= 晒+ 劫矿 邱，1 ) ( 1 ，i ) = 烈l r 1 ) + 加一( 1 一r 1 ) 最l ，蚌1 ) ( 1 埘= 碜( 1 一r 1 ) + 期( 1 一r 1 ) 只l ，女一1 ) ( 1 ， ) = ( 1 6 0 , k ) s m + 由概率分析可得系统的k o l m o g o r o v 方程为z 丌0 ，k = 侈+ 朋一) ，丌o i + + 朋一) r - 7 1 1 ，女( 3 2 1 ) r 1 = p q + z - o , k + 嫡+ p 口一) ( 1 一r 1 ) 丌o k + t + ( 萄i + p q 一) ( 1 一，+ 1 ) 7 f 1 七+ l + ( 市+ 5 可+ ) 7 r 1 + ( 1 一如k ) p q + 8 7 r 1 ，女一l( 3 2 2 ) 归一化条件为， ( 丌0 + 礼k ) = 1 女= 0 定义母函数； o o 忱( ：) = 以，i ，i = 0 ，1 ，0 sz 0 1 1 ( 3 2 5 ) ! ! 壅奎望盔兰堡主芏垡堡塞 至三垦塑塑型垄竖壅堡墼堕塑旦堡g 竺笪竺! 重堡垡：生坠 在0 z i 成立的充分必要条件是， 塑： i s + s p q 俐极限l i r a l 一面鬲i ：1 = 丽千；= 万丽芝菥存在的充分必要条件是z 旦 1 由引理我们可以将p l ( z ) 的定义域扩展为t0 z 1 由式( 3 2 5 ) 可以得 到， 妒t ( 1 = 而丽p q = + 丽i 啪( 1 ) 由归一化条件妒o ( 1 ) + q l ( 1 ) ；1 可以得到， 妒。( 1 ) = 1 一生+ s p q - 坤) = 而p q + = s 十s 加一 将( 3 2 5 ) 式式带入( 3 2 3 ) 式可得； ( z ) = g ( r 2 ) 妒o ( r z ) 其中 g ( ：) ：堑型：= 堡丝：! 塑：! 荦+ p g 一一s p q + z 由迭代可以推出， 唧( z ) = 伽( o ) 1 7g ( r n ) ( 3 2 6 ) 引理3 2 2 n 。o ol g ( r “z ) 收敛的充分要条件是i 善鲁 1 证明：g ( ：) = 1 + f ( ：) ，其中f ( ：) = 自5 + 魁p q 盐- - 2 s 量p q + 一z 由引理可知，当条件 i 掌鲁 1 成立时，f ( z ) 在0 2 1 的条件下非负我们用下式来表示； g ( ，。) = 【1 + f ( r “。) 】 由于 规掰t ， 些矍窒望盔堂堡堂垡堡塞 墨三童塑堑型垄堡塞塑墼堕塑亘丝璺塑g 竺! 重堇堡：塑坠 可以得到甚，f ( r ”：) 是收敛的因此可以得到h 墨。v ( r “：) 是收敛的 令z = 1 ，可得； o o 蜘( o ) = 伽( 1 ) f g ( r ”) 】一1 n = l 椅伽t u ) 带八上i 2 6 ) 式哪得t 嘶) = 1 - 丽p q + l 甓鬻 推论3 2 3 马氏链= ( ，仍) 遍历的充分必要条件是正i + a p q - 1 推论3 2 4 j ) 系统空闲状态下。o r b i t 内的顾客数的概率母函敷为， 嘶卜 1 - 筹，甓筹 其中 g ( ；) = 硒+ 面p q - 再- - f ( f f + 丽p q 万- ) s p q + z ( 2 ) 系统忙状态下，o r b i t 内的顾客敷的概率母函数为， 州。而看冬而毗) ( 系统o r m , t 内总的顾客数c n ) 的概率母函数为； 妒( z ) = l ，o o ( z ) + l p l ( ：) 2 袅s p 篙p c is p q 嘶) + 一一 十z 。 ( 4 ) 系统内怎的顾客敷f 纠的概率母函数为t 妒( z ) = q o o ( z ) + z 妒l ( z ) = 凳s p 黑p c l 謦s 唼x z 协( z ) 上一t 推娩3 2 5 ( j ) 系统空阁的概率为；蜘( 1 ) = 1 一群鲁 例系统忙的概率为，妒l ( 1 ) = 正i + l t a l - 可以发现，系统堂闲，忙的概率与重试率r 无关 俐o r b i t 内的平均顾客敷为t 即卜篇螂，+ 薹鬻， j ! 巫奎堕盔堂堡芏垡堡塞 笪三雯堕登型垄堡塞塞墼堕塑亘丝鱼竺璺竺! 重堡垒：堂坠 “，系统内的平均顾客数为； m 卜高粤嘉纵卅丽g f + p q - + g p q + 邮, ，薹勰p ( 5 ) g ( ) = e ( n ) + 妒l ( 1 ) 推论3 2 6 ( j ) 当r = 0 时，系统内的总的顾客数为t = ! ! 二盏i p + 堕p q - - 丝s p ：q + z 型：塑 此时庐( 力是模型g e d g l ，o og - 排队的系统的概率母函数显然，当r = 0 时，每一个s l o t 内顾客都进行重试这与g e o g e o 1 o og - 排队的顾客源是类似 的 ( 2 ) 当口一= 0 时， 庐( z ) = 咖( z ) = g ( ：) = 1 - 刍氍掰 s p p s p z s p s p z 此时咖( z ) 是模型g e o l g e o 1 重试排队的系统的概率母函数显然，q - ：= 0 相当 于没有负顾客的到达，即为普通的排队系统 ( 当r = 0 ，q 一= 0 时， ：l ! 二! 堕型 印一s p z 此时庐( 力是模型g e o a e o l l l o o 排队的系统的概率母函数 3 3 l a s - d a 模型的描述 下面我们考虑l a s - d a 模型的描述， l p a ! 塞奎堕盔堂堡圭兰堡堡塞 蔓三童堕壁型垄堕塞塞墼堕塑亘丝鱼竺笪竺! 重堕鱼：壁坠 0 顾客至u 达顾客离开+ 顾客重试 状态间的一步转移概率= p y 卅1 = y i = y ) 为， 只o k ) ( 0 ) = 矽+ p q 一一 只l 。k ) 杈 = 弦，+ 鲫一一 只1 i 1 ) ( 0 = ( 1 一如， ) p l g + 5 局，k ) ( 1 ，埘= p q + 只l ，】( 1 t ) = 够+ 卿+ ( 1 一产) r 0 ，k + 1 ) ( 1 ，埘= 乒( 1 一一+ 1 ) + p q 一( 1 一产+ 1 ) 曩l ，i + 1 ) ( 1 ，埘= 弗( 1 一一+ 1 ) + p g 一( 1 一r + 1 ) 只1 - 一1 ) ( 1 ，埘= ( 1 一a o ，k ) p q + s 运用e a s 模型的方法，我们可以得出l a s - d a 模型系统参量； 推论3 3 1 - 马氏链= ( ，) 遍历的充分必要条件是正i + s p q - 1 推论3 3 2 j ) 系统空闷状态下，o r b t 内的顾客数的概率母函教为。 纵扣【l _ 蒜j 髋帮 其中 g ：望塑：二堕鲤：! ! 塑：! 丝：竺堑! s p + 卿一一s p 矿o ( 系统忙状态下。o r b i t 内的顾客数的概率母函数为， 川= 而嘉刍而毗) ( 3 ) 系统o r b i t 内总的顾客敷f 卅的概率母函数为， 妒( 力= 蜘0 ) + 妒l 如) 2 丽5 f f 瓦+ p f - - 面s p q 再+ z 州z )印十肿一一s p a + z ( 4 ) 系统内总的顾客敷仁，的概率母函数为t 咖( 名) 鼍伽( ：) + z 妒l ( z ) 而够+ 甓p q - + - s p q + z 绯)筇+ p q 一一 ”、。 j e 星奎适盔兰堡主堂垡堡塞塑三童堕登型垄堡苎塑墼堕旦亘丝鱼竺垒竺! 重达鱼：壁坠 推论3 3 3 ( j ) 系统空闲的概率为；妒o ( 1 ) = 1 一；竿鲁 ，缈系统忙的概率为，妒l ( 1 ) = i + 盥= s p l q - 可以发现，系统空闭，忙的概率与重试率r 无关 俐o r b i t 内的平均顾客敷为。 剐卜毋咎s 蒜p q 纵，+ 星勰c ( r ， 、7 ( 印+ p 口一一+ ) ”! ：”) “) 系统内的平均顾客敷为 即卜高窘斋邮，+ 篇硒+ p q - 州，薹粥， 1 5 ) e ( l ) = e ( n ) 4 - 妒l ( 1 ) 3 4 随机分解 这一节我们将介绍系统的随机分解性质 f u h r m a n na n dc o o p e r 在文献1 1 6 1 中首先提出了随机分解的性质【1 2 。1 6 】 给出了连续时间排队系统下的随机分解【7 。1 3 ，14 】讨论了离散时间排队系统的 随机分解下面来研究我们所分析的的系统的随机分解性质t ( z ) 表示的是g e o g e d l o og - 排队系统下系统的总人数的概率母函数。 t ( 2 ) 表示的是g e o g e o 1g 一重试排队系统在系统空闲的条件下系统的总人 数的概率母函数 庐( z ) 表示的是我们考虑的系统的总人数的概率母函数 由上面的分析我们可以得到； 很显然可以得到 ( ：) ：! ! 二盏堕丝：塑望 一 硒+ 瑚一一s 舻2 酢) = 端 ( 力= n ( z ) t ( 力 韭壅奎逗盔兰堕主堂垡垒塞星三童堕盐型垄夔茎塞墼堕囹卫丝鱼塑笆竺! 重堡旦：篓坠 图3 1 负顾客的到达矿对系统空用的影响 由此我们可以得到以下定理； 定理3 4 1 g e o g e o 1g - 重试排队系统总人数可以由两部分来表示；g e o g e o 1 o o g - 排队系统总人数( ) 和g e o g e o 1 ( 7 - 重试排队系统在空闲条件下的总人敷 m 印l = l o + m 作为随机分解的应用，我们可以得出g e o g e o 1g 一重试排队系统总人数和 g e o g e o 1 i o o ( l o ) 系统中的总人数的差别即： 2 ) s主i=o-7to,o l p 卜p l o 叫i 2 驾铲 2 ( 1 ) s l p l = 以一= 川2 等等产 ru 一 3 5 数值算例 这一节梅用具俸的数值算饲来分析几个参量对系统的影响显然，选择的参 量数值需满足稳定条件 图1 和图2 反映的是负顾客的到达g + 对系统的影响分别取矿= 0 9 ，0 6 ，0 2 可以看出。随着s 的变大，, a o ( 1 ) 为一减函数即s 变大，系统空闲的概率变小， 忙的概率变大 1 7 i ! 夏奎堕盔竺堡主竺垡堡茎蔓三童堕登型垄堡壅塞墼堕塑旦堡壁竺璺竺! 重堡鱼：堡坠 图3 2 顾客的到达矿对系统忙的影晌 田3 3 顾客的到达矿对系统o r b i t 内等待重试的废客效的影晌 j ! 壅銮适盔兰堡主堂堡垒塞蔓三垦堕登型垄堕壅塞墼堕塑里丝垡竺笆塑! 重堡垒：堡坠 图3 4 重试率r 对系统o r b i t 内等待重试的履客数的影响 图3 5e a , q 和l , 4 8 一d a 楱翌的对比 j ! 塞奎堕盔堂堡兰垡丝塞堑三里堕盐型垄堕茎堕墼堕塑里丝g 竺坦竺! 重蔓璺：壁坠 图3 6e a s 和l a s d a 模型的对比 田3 7g e o g e o l 岱重试捧队和q 叫西o l 岱排队的对比 j 塞窒重盔堂堕主堂垡丝塞 墨三里堕壁型垄矍壅塑墼堕旦亘鳖璺竺型! 垦茎垒：鲎坠 图3 反映的是负顾客的到达q + 对系统o r b i t 内重试人数的影响显然，e ( n ) 相对于参数s 为一增函数我们分别取q + = 0 9 ，0 6 ，0 2 ，可以比较出不同的负顾 客对系统的影响 图4 反映的是重试率r 对系统o r b i t 内等待重试的顾客数e ( n ) 的影响分 别取r = 0 9 5 ，0 8 5 ，o l ，选取= 0 0 0 1 ，当r 趋紧于1 时，e ( n 1 逐渐变大 图5 和图6 反映的是e a sa n dl a s d a 两种不同的到达模型之间的差异 同种条件下l a s d a 模型下重试等待的人数将多于e a s 模型中的 图7 ，r 变小，重试排队和一般排队的差异逐渐变小当r = 0 时，显然相互 重合 韭壅奎堕盔兰堡望堡垒茎蔓堕垦塾塞鱼塑查型垄塑墼堕塑亘丝g 竺鱼竺! 重堡垒：壁坠 第四章独立负顾客到达离散时间可修g e o g e o 1 重试g 排队 4 , 1 模型的描述 正顾客和负顾客得到达为几何过程分别以p 和q 的概率到达，且楣互独立 正顾客到达系统后，若服务器空闲则立即接受服务，若服务器忙或者出于修理态， 则进入o r b i t 进行重试等待重试率为f = 1 一r ，其中r 是个顾客在个s o l t 内没有重试的概率负顾客到达系统后，服务器立即进入修理态修理过程为参 数为矗= 1 一o t ，其中q 表示个s l o t 内服务器没有修好的概率 服务率为参数为i = 1 一s 的几何过程，其中s 表示个s l o t 内服务没有完 成的概率 定义正顾客得到达先于负顾客的到达 4 2 马氏链及稳态概率的求解 考虑时刻m + ，则系统可以用氏过程= ( c k ， ，m ) 来表示其中c k 表示 服务器的状态，取值为0 ，1 ，2 分别表示服务器空闲、忙、坏) k 表示o r b i t 内重试顾客数可知其状态空间为 ( i ，动：i = o ，1 ，2 ；七o 状态间的步转移概率f 坩，= p y m + t = l = y ) 其中七0 为t 只o ，) ( o 瑚= 两一 只1 i ) ( o ，耐一i 两， 只站) ( 0 耐= 却移 p ( 0 ，女) ( 1 ，埘= 两 确i ) ( 1 ，t ) 一s 两+ 印口 只- ) ( 1 埘= 面呵 p ( o 乒+ 1 ) ( 1 ，埘= 面( 1 一r 1 ) 只l ，1 ) ( 1 瑚= i 两( 1 一r + 1 ) 砟，抖1 ) ( 1 舯；a 雨( 1 一r 1 ) 只l ，女一i j ( 1 瑚一( 1 一) s p i o 辩= q 只l 朋( 2 肿= 劫g + 鼬 2 2 i ! 塞奎重盔堂堡主堂垡丝塞星堕童塑塞鱼璧查型垄查墼堕塑亘丝鱼苎鱼塑! 重堡鱼：煎坠 只2 ，女) 2 ，衅= q f + 鳓 q 2 k 一1 ) ( 2 ，i ) = ( 1 一南，k ) n p 只l ，一1 ) ( 2 ，= ( 1 5 0 , i ) s p q 由概率分析可得系统的k o l m o g o r o v 方程为； i f 0 ，i= 参弦百o + 亏孬f 仉 + 印季r 霄2 主， 七20 ， l r l , = p 畸砘i + ( 黟每季+ 鲫丌1