（运筹学与控制论专业论文）带反馈的bernoulli休假离散时间geomxg1排队系统.pdf

中山大学硕士学位论文 带反馈的b e r n o u l l i 休假离散时间g e o m g 1 排队系统 专业：运筹学与控制论 硕士生：王会芳 指导教师：尹小玲副教授 摘要 从二十世纪九十年代开始，离散时间排队系统模型因其在数字通信系统中的 潜在应用价值而受到越来越多的关注，目前关于离散休假时间排队系统已有大量 的研究成果与此同时，我们也注意到大多数国内外文献关于离散休假模型都集 中于多重休假系统的研究，而关于b e r n o u l l i 休假系统的讨论比较少见在本文， 作者首次将b e r n o u l l i 休假与b e r n o u l l i 反馈两种机制引入到批到达的g e o m g 1 排队系统中，丰富了离散时间排队模型的理论体系 本文考虑具有一般服务时间分布的带反馈的b e r n o u l l i 休假批到达单服务器 离散时间排队系统我们首先使用补充变量法和概率母函数法研究了在遍历条件 下排队系统的马尔科夫链，求得了在平稳状态下任意时刻系统中顾客数的概率母 函数、平均队长以及平均等待时间等然后讨论了一些重要的特殊情况，通过与 已有文献相关结论的比较，进一步验证了本文结论的正确性最后，给出了本模 型的数值例子 关键词：离散时间排队系统，b e r n o u l l i 休假，b e r n o u l l i 反馈，补充变量法 中山大学硕士学位论文 ad i s c r e t e - - t i m eg e o m ： g 1 q u e u e i n gs y s t e mw i t h f e e d b a c ka n db e r n o u l l iv a c a t i o np o l i c y m a j o r ：s t o c h a s t i co p e r a t i o nr e s e a r c h n a m e ：w a n gh u i f a n g s u p e r v i s o r ：a s s o c i a t ep r o f y mx i a o l i n g a b s t r a c t s i n c e19 9 0 st h ed i s c r e t e t i m eq u e u e i n gs y s t e mh a sr e c e i v e dm o r ea n dm o r e a t t e n t i o nb e c a u s eo fi t sp o t e n t i a la p p l i c a t i o nv a l u e ，a n dt h e r eh a v eb e e nl o t so fr e s u l t s o nd i s c r e t e - t i m eq u e u e i n gs y s t e m s m e a n w h i l e ，w en o t i c et h a ti nt h el i t e r a t u r em o s to f d i s c r e t e t i m em o d e l sw i t hv a c a t i o n sf o c u s e do nm u l t i p l eo n e s ，a n df e wm o d e l sw i t h b e r n o u l l i v a c a t i o n sw e r es t u d i e d t h i si st h ef i r s tp a p e rt h a ti n t r o d u c e sb o t hb e r n o u l l i f e e d b a c ka n db e r n o u l l iv a c a t i o np o l i c i e si n t oad i s c r e t e t i m eg e o m g 1q u e u e i n g s y s t e mw h i c he x t e n d st h er e s u l t so fq u e u e i n gt h e o r y w es t u d yas i n g l es e r v e rq u e u ew i t hb a t c ha r r i v a l sa n dg e n e r a ls e r v i c et i m e d i s t r i b u t i o nb a s e do nb e r n o u l l iv a c a t i o np o l i c y a tf i r s tw ei n v e s t i g a t et h em a r k o v c h a i nu n d e r l y i n gt h ec o n s i d e r e ds y s t e ma n di t se r g o d i c i t yc o n d i t i o n w eo b t a i ns t e a d y s t a t er e s u l t si nt e r m so ft h eg e n e r a t i n gf u n c t i o n sf o rt h en u m b e ro fc u s t o m e r si nt h e s y s t e m , t h ea v e r a g en u m b e ro fc u s t o m e r sa n dt h ea v e r a g ew a i t i n gt i m ei nt h eq u e u e t h e ns o m es p e c i a lc a s e so fi n t e r e s ta r ed i s c u s s e da n ds o m ek n o w nr e s u l t sa r ed e d v e d f i n a l l y , s o m en u m e r i c a le x a m p l e so f t h eq u e u ea l ep r o v i d e d k e yw o r d 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 , b e r n o u l l iv a c a t i o n , b e r n o u l l if e e d b a c k , s u p p l e m e n t a r yv a r i a b l em e t h o d 原创性声明 本人郑重声明：所呈交的学位论文，是在本人导师的指 导下，独立进行研究工作所取得的成果除文中已经注明引 用的内容外，本论文不包含任何其他个人或集体已经发表或 撰写过的作品成果对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明本人完全意识到本声明的 法律结果由本人承担 学位论文作者签名：王锦 日期：呻年夕月竹日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规 定，即：学校有权保留学位论文并向国家主管部门或其指定 机构送交论文的电子版和纸质版，有权将学位论文用于非赢 利目的的少量复制并允许论文进入学校图书馆、院系资料室 被查阅，有权将学位论文的内容编入有关数据库进行检索， 可以采用复印、缩印或其他方法保存学位论文 学位论文作者签名：王会易 日期：伊口7 r 年5 月少f 日 导师签名：户夕，疆 日期：醒矽年厂月z j ；【日 中山大学硕士学位论文 1 1 排队论简要介绍 第一章绪论 排队论是研究等待线路( 或队列) 的数学学科它对一些与排队相关的过程 进行数学分析，包括到达队列( 的尾部) 、在队列中等待、和在队列前端接受服 务等通过排队论的研究，可以推导和计算出一些排队指标，如顾客在队列或系 统中的平均等待时间、正在等待或接受服务的顾客平均人数、和系统处于特定状 态的概率 “排队 一词在法语中起源于拉丁文c a u d a ，意为“尾部由于排队论的研 究结果常常可以帮助大家解决提供服务类的商业决策问题，所以排队论被归于运 筹学分支的观点已得到广泛的认可它的许多理论在商业、工业、医疗、公共服 务和工程学方面都有许多的应用价值，其中在顾客服务、交通运输及通信系统中 的应用尤为突出排队理论可直接应用于智能运输系统、呼叫中心、p a b x s 、网络 系统、无线电通讯、服务队列、高级通信系统和交通阻塞方面 最早有关排队轮的著作一般人公认的是1 9 0 9 年丹麦数学家e r l a n g 所发表的 论文其后从事排队论研究的先驱人物有法国数学家f p o e l a c z e k 和苏联数学家 a k h i n t c h i n e 他们在这方面的研究课题都在三十年代完成并载于他们后来撰写 的著作 1 ，2 中第二次世界大战以后，运筹学得到了广泛而深入的发展五十年 代初期英国人d g k e n d a l l 系统地阐述了排队问题，并且利用嵌入马尔科夫链的 方法推动了排队论的进一步发展，k e n d a l l 的两篇重要论文分别发表于1 9 5 1 年 和1 9 5 3 年 3 ，4 六十年代，排队论研究的课题日趋复杂，开始了近似法的探讨与队列上下限 问题的研究，在应用方面排队论进入了生产线，交通线排队论在计算机，计算 机网络，通讯方面的应用主要开始于七十年代由于排队问题多呈网络出现，计 算机上的繁琐使得研究范围扩及到计算方法上面离散时间排队论应运而生，并 且开启了排队论研究的新领域本章第二节给出了关于离散时间排队理论的简要 介绍与发展历程 1 中山大学硕士学位论文 经典的排队模型可用如下框图表示： 篆“j 口臣亘) 备刘竺坠il 竖墅望r 蔚 l 排队规则服务规则 ； 图1 一l 1 2 关于离散型排队系统 顾客的到达和离去只能发生在有固定间隔的离散时刻的排队系统称为离散 时间的排队系统从二十世纪九十年代开始，离散时间的排队系统模型因其在数 字通信系统中的潜在应用价值而受到越来越多的关注众所周知，在计算机及通 信系统中的基本时间单位为二进制码，所以离散模型在此类系统的研究中显得更 加合适而且，在实践中离散模型也可以用来估计连续时间系统目前在排队论研 究领域中大部分的文献著作都是关于连续时间排队模型的，主要原因还是因为离 散时间模型的研究比连续情况难度增加了很多( w o o d w a r d 5 ) 在给定的一个 时刻，连续时间队列最多只能经历一个状态转移，但在离散情形下，一个时刻可 能会发生多种状态的变化离散时间系统的这种特征使对它的分析和理解变得更 加困难 与连续时间排队相比，离散时间排队研究是较晚开始的离散排队首先由 m e i s l i n gt ( 1 9 5 8 ) 6 提出，并指出对应于连续时间排队论建立和发展离散时间 排队理论的可能性当时排队论研究的主流还是连续时间系统随后，d a f e r m o s 与n e u t s ( 1 9 7 1 ) 7 ，n e u t s 等( 1 9 7 3 ，i i v ) 【8 】，h u s 与b u r k e ( 1 9 7 6 ) 9 】， c h a n 与m a a ( 1 9 7 8 ) 1 0 】，m o r f i s o n ( 1 9 7 9 ) 【1 l 】，b h a r a hk u m a r ( 1 9 8 0 ) 1 2 】 等研究了各种离散时间排队模型的稳态指标和计算方法k o b y r a s h i ( 1 9 7 7 ) 【1 3 对 离散时间排队在计算机通信领域应用作了长篇综述，指出离散时间排队更适合于 计算机网络的建模和分析，这篇综述对离散时间排队的研究和应用起到了积极的 2 中山大学硕士学位论文 推动作用h u n t e rj j ( 1 9 8 3 ) 1 4 也对离散排队进行了研究但关于此类模型的详 细讨论首次见于b r u n e e l 、k i m ( 1 9 9 3 ) 1 5 和w o o d w a r d ( 1 9 9 4 ) e 5 的著作 中d a d u n a ( 2 0 0 1 ) 1 6 对多种离散时间排队网络给出了“乘机解形式的稳态指 标的解析表达式最近，随着计算机与通信网络技术的发展，更多的排队论学者 投入到离散排队系统的研究中，并取得了一系列的研究成果 在离散排队模型中，时间轴被划分为一串具有相同间隔的时间区间序列这 样，就可以对整个时间轴标以序号0 ，1 ，m ，假设系统中的所有“活动 ( 到 达、服务开始或结束、离去、休假等) 都发生在时间区间的边界处根据在某个 边界点到达与离去发生的先后次序，有先到达( a f ) 和先离去( d f ) 两种机制 在a f 机制下，到达先于离去；d f 机制则相反，而这两种机制分别与延迟进入迟 到达系统( l a s - d a ) 和早到达系统( e a s ) 相对应( 分别如图卜2 和图卜3 所示) 了 i o ：潜在翔迭点 ：潜在离去点 t 簟：潜在离去之詹点 p ：潜在离去之蘸点 图1 - 2 迟到达延迟进入系统示意图 0 ：潜在戮选点 ：潜在鬻去点 耄：滋在覆去之慝赢 p ：潜在鬻去之髓点 秘l 似 h d 潜秘老 图1 - 3 早到达系统示意图 3 中山大学硕士学位论文 1 3 关于休假排队系统 休假排队系统在现实生活中是一类很重要的模型经典排队论假设服务 台在任何时候都可用于接待顾客，休假排队泛指服务台在某些时候不能被顾客利 用的排队系统。导致服务暂时中断的理由可以有多种多样的解释，而暂时不能用 于接待顾客的那些时间统称为休假在休假期间，服务器可能在修理、也可能进 行其他服务或者只是被迫停止服务大量实际问题均可通过在经典排队系统中引 入某种休假策略加以描述和研究2 0 世纪中期以来，随着计算机通讯网络、柔性 制造系统( f m s ) 、异步转换模式( a t m ) 等高新技术领域的发展、提出了大量复 杂系统的设计与控制问题，经典排队模型在处理这类问题时存在着极大的局限性 休假排队研究正是在这些实际应用背景中产生的 经典排队中早已涉及到与休假排队相关的内容，如优先权排队、轮循排队等， 更重要的是，休假模型可以被广泛地应用于这些排队系统的研究比如，在一个 轮询系统中，有n 个队列在同时等待一个服务器进行服务，而服务器每次只能根 据已有的规则服务一个队列中的顾客，然后再转入其他的队列中进行服务考虑 n 个队列中的任意一个队列当服务器不在这个队列中进行服务时，此队列中的 顾客就可以把服务器看作是在进行休假这是轮循系统的一个例子在计算机系 统中，处理器有多个队列的进程等待完成就属于这种情况 作为随机运筹学中一个有独立特色的方向和经典排队论的新发展，休假排队 研究是从2 0 世纪7 0 年代才开始的l e v y 与y e c h i a l i ( 1 9 7 5 ) 1 7 从有效利用排 队系统闲期的观点出发，首先研究了m g 1 型排队，并且得出了著名的随机分解 结果进一步，c o o p e r ( 1 9 7 0 ) 1 8 ，c o u r t o i s ( 1 9 8 0 ) 1 9 ，f u h r m a n n ( 1 9 8 4 ) 2 0 ，f u h r m a n n 与c o o p e r ( 1 9 8 5 ) 2 1 ，h a r r i s 与m a r c h a l ( 1 9 8 8 ) 2 2 ，k e i l s o n 与r a m a s w a m y ( 1 9 8 8 ) 2 3 ，l e v y 与k l e i n r o c k ( 1 9 8 6 ) 2 4 等众多工作相继讨 论了各种休假策略及服务规则的m g 1 型排队系统。初步形成了以随机分解为核 心的休假排队理论框架1 9 8 6 年，几乎同时在美国和欧洲发表了d o s h i ( 1 9 8 6 ) 2 5 和t e g h e m ( 1 9 8 6 ) 2 6 两篇综述论文，总结了已有的研究成果和方法，标 志着休假排队已发展成一个有独立特色的研究方向从8 0 年代末到9 0 年代，田 乃硕等( 1 9 8 9 ) 首先把矩阵几何解法引入休假排队研究，推进了g i m 1 型休假 4 中山大学硕士学位论文 排队系统和多服务台休假排队系统的研究 1 4 经典g e d m i g l l 排队系统 考虑一个迟到达延迟进入系统，经典g e o m g 1 排队系统的模型描述如下： 顾客到达遵循参数允( o 五 l ，口= e ( s ) ，彳( z ) = e ( z 5 ) = 矿瓦 到达间隔与服务时间独立，先到先服务( f i f s ) 排队规则 用嵌入马尔科夫链方法，以毛表示第n 个顾客离开系统的时刻，其中力1 设e = q 以下我们列出关于该排队系统的一些主要成果，具体证明可以参考文献 3 4 定理卜l ( 流通强度) 在一个服务期间内平均到达顾客数是p = 献 注：p 是平均服务时间与平均到达间隔之比，称为系统的流通强度或负载 为 定理卜2 ( 离去时刻队长) 若p l ，离去时刻的稳态队长r 的概率母函数 其中k ( z ) = 2 + 2 z 饰) = 鼍铲斗i 定理卜3 ( 任意时刻队长) 若p 1 ，g e o m g 1 排队的任意时刻与离去时 刻有相同的稳态队长分布 5 中山大学硕士学位论文 定理卜4 ( 稳态等待时间) 若p 1 ，稳态等待时间形的概率母函数为 形( z ) 2 正( 1 再- p ) f ( 1 - 砑z ) ，旧 定理卜5 ( v - 均忙期) g e o m g 1 排队系统忙期的概率母函数b ( z ) 满足函 数方程 平均忙期为 b ( z ) = 彳【必( b ( z ) ) 】， 郴) 2 南 把经典g e o m g 1 系统推广到成批到达假设每次到达顾客数c 是独立同分 布的，有 q = p c = f ，f o ， = e ( c ) ， c ( z ) = c , z 。 定理卜6 ( 离去时刻队长) 若p 2 ， ( 2 - 9 ) 丑，l ( 材一1 ) z = q a c l a u z + 墨，l ( o ) a r p a z + e , ，l ( o ) 以r p a z + p 2 ，i ( o ) 2 r p a 。z + p i ，l ( 甜) 允 + e o ，o ( 0 ) 兄c l 吼z + 毋，o ( o ) a a z ， 1 2 ( 2 1 0 ) 中山大学硕士学位论文 只。， 一1 ) 矿：9 名q z 一吒+ ( n - 1q 只j ，。( o ) z n ) 五，瓦+ ( 杰q 只一+ l ，。( o ) z ”) 旯再说+ 只，。( o ) z 一2 r p a 。 + 只+ l ，。( o ) z n t r p a u + ( n - 1q 只- j 。( 甜弦一) 名+ 只， ) 少万+ ( 窆q 一，。( o ) z ”) 元q + 只o ( o ) 矿砘；n 2 ( 2 11 ) 将公式( 2 - 7 ) 、( 2 - 8 ) 和( 2 - 9 ) 对刀求和，得到 只，。( u - 1 ) z ”= q + 1 ，( o ) z ”五五+ q 乞一( o 弦”t r p v u + 。( o ) z ”t r p v 。 n = o n = li = ln = 2i = l n = o + 只，。( o ) z ”劢巩+ 只，。( z ，) 矿五+ q 训o ) z ”a ， 用概率母函数表示为 扩l ( z ) = 仍，o ( z ) c ( z ) 元，p k + 仍，o ( z ) c ( z ) l r p v , + 仍，o ( z ) 五僦+ 仍，o ( z ) 概 + 编。( z ) 五十，。( z ) c ( z ) 兄 强以) 阢批诫+ c ( 彬帆+ 砘+ 确 饥沁) 瓦+ c ( m 强水) 阻批_ + c 肌三万+ 盈卜慨心) 万+ c ( 批 ， 同样，将公式( 2 一1 0 ) 和( 2 一1 1 ) 对玎求和，得到 ( 2 - 1 2 ) 杰只，。似一1 ) ，：q 主少见吼+ o o n - | q t 。( o ) z ”力，两+ 羔窆q 只一，。( o 弦”名巧现 n = ln = l n = 2 ，= ln = li = l + 艺，。( o ) z 一l r p a 。+ + i 。( o ) 少砥+ q _ f 。 ) z ”五 n = l n = ln = 2t = i + 羔只，。( z ，) z 一万+ 妻主q 只t 。( o ) z ”兄吼+ 妻只，。( o ) z n m 慨， 用概率母函数表示为 1 3 中l i j 大学硕士学位论文 够l , u - - i ( 加q c ( 砒吼圯和) ) 办p a i r 慨以) c 兄碗圯和) 盈砘 + 仍，。( z ) 一毋，。( o ) z j 西i 酰+ 仍，。o ) c ( z ) 力+ 仍，。( z ) 万+ ，。( z ) c o ) 名吼 + 【- ，o ( z ) _ p o ，o ( o ) j 饥 = q c ( 批吼圯驯c ( m r + 导c ( 彬一r + 万+ 导万i 瓦慨心) c ( m + - l z zl l -_ j + ，。( z ) c ( z ) 允+ 万 吼一只，l ( o ) 2 r p a 。一异，。( o ) 瓦， 对( 2 1 2 ) 和( 2 1 3 ) 的两边都乘以，并对u 1 求和得到 ( 2 - 1 3 ) 砉川( z ) r = ( z ) l 三c ( z ) 石+ c ( z ) 加+ 万+ e - l p 窆屹r + 艺o z ) r - + c ( z ) 五 ， u 王il z j u = lu = l 一一 妻u = l 1 ( z 矿= q c ( z ) 名言吼r + 仍“z ) c ( z ) 知+ c ( z ) 石+ 万+ ! g 万j i 万妻u = l 吼， ”互il + 砉仍z h “ c ( z ) 兄+ 万 + 编，o ( z ) c ( z ) 五+ 五 妻u = l 吒r 一只“。) 而砉吼r 一忍0 ( o ) 万善a t 3 吼儿 用概率母函数表示，得 州舻) 强酬三) 庸c ( 批，+ 丢万+ 刀i 加( 卅础) 呗。( 瑚 万+ c ( 砒 ， iz z i lj 州础瑚c 础卅舭) c 肌三c ( z ) 庸盈七万 两( x ) + 仍( 础) 一仍 0 ( z ) c ( z ) 五+ 万 + 脚 c ( z ) 旯+ 万 彳( x ) 一互，l ( o ) 2 r p a ( x ) 一e o o ( o ) z a ( x ) ， 移项得 x - c 名一刁啪棚氇心) l c 万坝彬，七力+ 2 r p b ( 矿小) 【c 允+ 万】， lz z 。 ( 2 1 4 ) 1 4 中山大学硕士学位论文 x - c ( z ) 兄一万 仍( x ，z ) = 9 c 圳小啪) c 肌j 1c 庸盈+ 万 西( 沪啪) 厕 + 脚 c ( z ) 名+ 万 彳( x ) 一丑，。( o ) 一2 r p a ( x ) - p o o ( o ) 劢( _ ) c ) ， 令k ( z ) = c ( z ) 五+ 名，代入( 2 1 4 ) 、( 2 一1 5 ) 式得 ( 2 一1 5 ) x - k ( z ) 】( x ，z ) = 仍，。( z ) p f + z r zk ( z ) b ( x ) 一，。( z ) k ( z ) ，( 2 - 1 6 ) x - k ( 训孵，加q 圳圳c ( 矿1 】慨。( 班( z ) 万半以) 一1 + ( 班( 圳( 班 ( 2 - 1 7 ) 再令x = k ( z ) ，可以得出如下关系式： 仍，。( z ) pr + z r zk ( z ) b ( k ( z ) ) 一，。( z ) k ( z ) = o ，( 2 - 1 8 ) q 础酢) ) 【c ( z ) _ 1 】慨。( 班 万半彳( 酢) ) 一1 + ( 班( 圳( 聊) ) - 0 ， ( 2 - 1 9 ) 由( 2 1 8 ) 式，我们可以得到关于铴，。( z ) 与仍，。( z ) 的关系式如下： ，。( z ) = p r + z r z b ( k ( z ) ) 仍，。( z ) ， 。砰羞一缈 从而 1 5 ( 2 - 2 0 ) ( 2 - 2 1 ) 中山大学硕士学位论文 以二# 彳( k ( z ) ) b ( k ( z ) ) 【1 一c ( z ) 】 “力2 而阵琢瓦品赢商9 把( 2 2 1 ) 、( 2 2 2 ) 代入( 2 - 1 6 ) 和( 2 - 1 7 ) 中，得到： , p a x ，z ) ( 2 - 2 2 ) 2 a ( k ( z ) ) 【l c ( z ) 】p 三竺曰( x ) qp 2 二竺彳( k ( z ) ) 曰( 足( z ) ) 【l c ( z ) 】q 【x 一酢) 】 二彳( 酢) ) 【万+ p b ( k ( 砌】- l - - 酢) 】 二# 郴) 【万+ p b ( k ( z ) ) 】- l p 五! ： 孚彳( k ( z ”【l c ( z ) 】【曰( x ) 一曰( k ( z ) ) 】 2 西翻霉丽瓦品面面矾 啪力= 一a a ( x ) c ( z ) - 1 q + 篇糕一q ， ( 2 - 2 4 ) 以下根据归一化条件q + 只，。( 甜) + 只，。 ) = 1 ，即q + c p o ( 1 ，1 ) + 仍( 1 ，1 ) = 1 n = ou = on = lu = o 来求解p 将( 2 1 6 ) 式和( 2 一1 7 ) 式相加，得： 1 6 中山大学硕士学位论文 【x - k ( z ) o , o ( x ，z ) + c i ( x ，z ) 】 叫驯c ( z ) 一1 h 刊万半帅半鼬) _ 1h 酢) 【心) - l 】 一仉，、 础删【l - c ( z ) 】卜半鲍帅半脚h jn c( =q名彳xz)-q+j三三三三二i萎夏：鬲；：_：；：云乙五一q p 五! 二之兰么( k ( z ) ) b ( k ( z ) ) 【1 一c ( z ) 】【么( x ) 一1 】 坐么( k ( z ) ) 【歹+ 加( k ( z ) ) 卜1 。 q 五【l c ( z ) 】 【彳( x ) 一彳( k ( z ) ) 】+ p 二专竺彳( k ( z ) ) 【b ( 功一b ( k ( z ) ) 】 坐彳( k ( z ) ) 【万+ 加( k ( z ) ) 卜1 注意到 k ( z ) = c ( z ) 2 + a ， 有 1 一足( z ) = 1 一c ( z ) z 一万= a - c ( z ) , t = 元( 1 一c ( z ) ) ， 因此 ( x ，z ) + 仇( x ，z ) = 巫= 装 等+ p _ f - i - r z 卿，等) 二竺彳( k ( z ) ) ；+ 加( k ( z ) ) 一l 【 x k ( z ) z x k ( z ) j 首先，令z - - - ) 1 ，可以得到 1 7 ( 2 - 2 6 ) 中山大学硕士学位论文 ( x ，1 ) 4 - 仍 ，1 ) = l ：i m 。【( x ，z ) + 觋( x ，z ) j 划m 竺型竺竺二兰竺兰竺窆主 h 1 坐彳( k ( z ) ) _ ；+ 加( k ( z ) ) 一i = l 酬i m q 舭n o ( z ) 等+ p 半郴( z ) ) 等 ， ：_ - 上七( z ji x k ( 2 ) 1 z 、 x k ( z ) j 。 其中 0 ( z ) = l k ( z ) d o ( z ) 一r + z r za ( k ( z ) ) 融p b ( k ( z ) ) 】一l 由- 于n o o ) = d o ( o = 0 ，所以由洛必达法则，有 f a o ( x ，1 ) + 仍( x ，1 ) = 姆【( 那) + 仍( 那) 】 =q器等+p字脚殄b(x)-b(k(z)ix-dg(zo ) l x k ( z ) 1 z 、一7 ：- 1 = q 器l 等+ p 等 ， 而 联( z ) l ：。= - k 7 ( z ) f ：。= 一力厂， 联( 札。= 一；难( z ) ) 【万+ p b ( k ( 删捌+ 半小酢) 心( z ) 融p b ( k ( 删捌 + p 半郴( 州( 酢胚训州 = 彳+ 仅九y + p p 九y ， 所以 1 8 中山大学硕士学位论文 删亿驴q 器l 等协b 川( x ) - l j 再令x 专1 ，根据洛必达法则，得到 ( 2 - 2 7 ) 编( 1 ，1 ) + 仍( 1 ，1 ) = l ，i m l 。 ( x ，1 ) + 仍( x ，1 ) 】= f 二- 生a 2 鱼, y 2 - 盟p , f l a y q ， ( 2 2 8 ) 根据归一化条件q + ( o o ( 1 ，1 ) + 仍( 1 ，1 ) = l ，得 q + q 二丝兰二翌丝兰：1 ， 哥七c c 2 y + p 9 研 故q ：y - z a y = - p f l a y 其中，1j | a 2 y + p f l a y + r 1 2 4 稳态分布及各项排队指标 定理2 - 1 ：马尔科夫链 圪，m n ) 是遍历的当且仅当( 口+ p f l ) x r 0 时，有 ( a + p p ) 2 r f ， 所以( 口+ p p ) 砂 f 是马尔科夫链 匕，m ) 遍历的必要条件 ( 2 - 2 9 ) 我们观察上面条件式的两端，其中彳厂表示单位时间平均到达的顾客数，口为 一个顾客的平均服务时间，为一次休假的平均时间考虑从一次服务结束到下 次服务结束的这段过程，系统会经历一次服务，同时以概率p 经历一次休假，所 以这段过程的平均时间为a + p f l ，且在其间有平均f 个顾客离开系统 1 9 中山大学硕士学位论文 因此( 甜+ p ) 砂 f 意味着在从一次服务结束到下次服务结束的过程当中， 平均到达的顾客数小于平均离去的顾客数所以当满足条件( 口+ p ) 砂 f 时， 系统是平稳的，即( 口+ p ) 兄7 f 也是马尔科夫链 匕，m ) 遍历的充分条件 归纳上面的结论，我们得到以下定理： 口 定理2 - 2 当( 口+ p 夕) 兄y f 成立时，马尔科夫链 匕，m e n ) 的平稳分布可 由以下概率母函数给出： 鹏z ) ：兰兰些坐型堕竺娑q ， ( 2 - 3 0 ) 纵圳2 函向孚磊而碉矾 归一。 们力：背q + 瓮掣一 izj 其中，q = 三二竺挈丝，k ( z ) = c ( z ) 元+ 万 ， 推论2 - 1 ( 1 ) 当服务器闲( 即空闲或休假) 时系统顾客数的概率母函数为 ( 2 - 3 1 ) 塑r + r z 彳( c ( z ) 元+ 乃一1 缈纵1 加孚磊赢面丽9 q 。3 2 证明：直接计算 中山大学硕士学位论文 p 兄二兰彳( k ( z ) ) 【1 一c ( z ) 】【l b ( k ( z ) ) 】 缈纵1 力钮+ i 研z 享赢面碉q p 半么( k ( z ) ) 【1 一曰( k ( z ) ) 】 = q + = l 一q 。坐彳( k ( z ) ) 【歹+ p b ( k ( 圳】一l 。 三r + r za ( k ( z ) ) 一1 半4 ( k ( z ) ) 【歹+ p b ( k ( z ) ) 】一1 f + r za ( c ( z ) 五+ 万) 一1 = _ = ：量一( ) 三竺么( c ( z ) 五+ 乃- 万+ 加( c ( z ) 兄+ 万) 1 1 。 ( 2 ) 当服务器忙时系统中顾客数的概率母函数为 口 枇) 2 孚磊丽1 - a ( c 丙( z ) a + 丽a ) q ( 2 - 3 3 ) 证明：直接计算 = 一2 c ( z ) - 1 舛高警一9 半彳( 酢) ) 融p b ( k ( 砌】一1 叫酢) ) 半【歹郴( 酢) ) 】一l = 一二= _ 兰二- d 坐三彳( k ( z ) ) 【万+ 加( k ( z ) ) 卜1 ：= ! 二丝咝型 o 坐彳( k ( z ) ) 万+ 加( k ( _ z ) ) 卜1 ：! = 丝塑塑墨墨2 f ) 二兰彳( c o ) 五+ 乃| _ 万+ 加( c ( z ) 兄+ 万) 一1 。 ( 3 ) 系统中顾客数的概率母函数为 2 l 口 中山大学硕士学位论文 。，=q+o，力+仍o，z，=z二石iii函a丢妻与笺写蜀笔sipb z q i ，+ 陀l ( c i z ) 九+ 力) lp+i c i) 以+ 九) i 证明：将前面两个引理的结果相加得 = q + ( 1 ，z ) + 仍( 1 ，z ) 一兰竺鲨 睢 ! 二丝塑 q = = l 一p + = 二_ _ 二二= 型一p 半么( k ( z ) ) 【歹+ p b ( k ( z ) ) 】一l 半么( k ( z ) ) 防p b ( k ( z ) ) 】一1 i 尘兰彳( k ( z ) ) 一彳( k ( z ) ) 以下的推论给出了系统在平稳状态下的些排队指标 推论2 - 2 ( 1 ) 系统空闲的概率 其中，p = q ：f - g a - = y - _ p f 1 2 y ：1 一p ， 些竺些为系统的可利用因子 ，_ ( 2 ) 系统休假的概率 口 ( 2 3 5 ) 帆1 ) = i 面p f l i 兄y 瓦q = 了p p 2 r ( 2 3 6 ) ( 3 ) 服务器在服务的概率 删) 2 而箬丽q = 孚 ( 2 _ 3 7 ) 中山大学硕士学位论文 ( 4 ) 在平稳状态下系统中的平均顾客数 乞：塑巡装粤业q ，( 2 - 3 8 ) ，= - - - - ，- - 一i ， 9 2 ( d ( 1 ) ) 2 一 其中，n ( 1 ) = - ，n ”( 1 ) = 2 f u a y ，d 7 ( 1 ) = f 一献y p 肜7 ， d ”( 1 ) = 一 【2 p 筇+ 么8 ( 1 ) + p b ”( 1 ) 】名2 厂2 + 2 【甜+ p 】，a y + a + p f l 2 c 。( 1 ) ) 上式中彳( 1 ) = i ( i - 1 ) a ，为到达时间分布的二阶阶乘矩，同理( 1 ) = i ( i - 1 ) b ， c ”( 1 ) = i ( i - 1 ) c , 证明：令 删= 耐( k ( z ) ) ( z 1 ) ， d ( z ) = z 一( f + 肱) 么( k ( z ) ) 【万+ p b ( k ( z ) ) 】 则系统中顾客数的概率母函数 ( z ) = q + ( 1 ，z ) + ( 0 1 ( 1 ，z ) ：! 堕型三二! !d z - ( f + r z ) a ( k ( z ) ) l 万+ p b ( k ( z ) ) l 。 ：n ( z ) q = d ( 纠 令乞为在平稳状态下系统中的平均顾客数，则 l i 驴mk 嘲( 鬻卜卿盟铲q ， 注意到n ( 1 ) = 0 ，d ( 1 ) = 0 ，所以使用洛必达法则得到 l i + m 。型笫等幽9 = 迎铲q ， 9 2 - + 1 2 ( d ( z ) ) 2 。 2 ( d ( 1 ) ) 而 ( z ) = f a ( k ( z ) ) k ( z ) ( z 1 ) + 7 么( k ( z ) ) ， n ”( z ) = 朔”( k ( z ) ) ( k ( z ) ) 2 ( z 1 ) + 剐( k ( z ) ) k ”( z ) ( z - 1 ) + 2 y a ( k ( z ) ) k ( z ) ， 中山大学硕士学位论文 d 7 ( z ) = 1 一叫( k ( z ) ) 【矽+ p 8 ( k ( z ) ) 】一( - + 肱) 彳7 ( k o ) ) k ( z ) 歹+ p b ( k ( z ) ) 】 - p ( f + r z ) a ( k ( z ) ) b 7 ( k ( z ) ) k ( z ) ， d ”( z ) = 2 刊( k ( z ) ) k 7 ( z ) 万+ p b ( k ( z ) ) 卜2 p ，么( k ( z ) ) b 7 ( k ( z ) ) 足( z ) 一( f + r z ) 4 。( k ( z ) ) ( k ( z ”2 【万+ p 8 ( k ( z ) ) 卜( f + r z ) 么7 ( k ( z ”k 。( z ) 【万+ p b ( k ( z ) ) 】 一2 p ( f + r z ) a ( k ( z ) ) b ( k ( z ) ) ( k ( z ) ) 2 一p ( f + r z ) a ( x ( z ) ) b ”( k ( z ) ) ( k ( z ) ) 2 - p ( f + r z ) a ( k ( z ) ) b 7 ( k ( z ) ) k ( z ) ， 将z - - - 1 代入，得到 7 ( 1 ) = f ，n ”( 1 ) = 2 f z a y ，d ( 1 ) = f 一砒y p 膨y ， d ”( 1 ) = 一 【2 p 筇+ 4 ”( 1 ) + 加”( 1 ) 】名2 7 2 + 2 o t + p f l ，允厂+ 【口+ p 】a c 。( 1 ) ) ， 其中，么”( 1 ) = i ( i - 1 ) a ，b 。( 1 ) = i ( i - 1 ) b , ，c 。( 1 ) = i ( i - 1 ) c ， i = 2i f 2i = 2 口 由