（应用数学专业论文）具有负顾客的休假排队系统.pdf

江苏大学硕士学位论文 摘要 本课题主要研究具有负顾客到达的两类休假排队系统一类是具 有b e r n o u l l i 反馈和负顾客到达的m ( me x ) g 1 休假排队系统，另一 类是有负顾客到达的m g 1 休假可修排队系统对于具有b e r n o u lli 反 馈和负顾客到达的m ( me x ) g 1 休假排队系统，运用补充变量法，母 函数法，状态转移及l 变换分析，得到了抵消规则为r c h 和r c e 下系 统瞬态和稳态队长分布的概率母函数对于有负顾客到达的m g 1 休假 可修排队系统，运用补充变量法得到了一些排队指标及一些可靠性指 标 关键词：负顾客；b e r n o u l l i 反馈；休假；可修排队系统；l 变换；补 充变量法 江苏大学硕士学位论文 a b s t r a c t t h i s p a p e rm a i n l y r e s e a r c ht w ok i n d so fq u e u e sw i t h n e g a t i v e c u s t o m e r sa n dv a c a t i o n s o n ek i n di sm ( m x ) g l q u e u ew i t hb e r n o u l l i f e e d b a c kn e g a t i v ec u s t o m e r sa n dv a c a t i o n s ，t h eo t h e rk i n di s r e p a i r a b l e m g 1q u e u es y s t e mw i t hn e g a t i v ec u s t o m e r sa n dv a c a t i o n s f o rt h ef i r s t k i n do f q u e u e w i t h n e g a t i v e c u s t o m e r sa n dv a c a t i o n s b yu s eo f s u p p l e m e n t a lv a r i a b l e sm e t h o d ，g e n e r a t i n gf u n c t i o na p p r o a c h ，s t a t e t r a n s f e ra n a l y s e s a n d “l a p l a c et r a n s f o r m ，q u e u e sg e n e r a t i n gf u n c t i o nf o r m ( m x i ) g 1s y s t e m w i t h n e g a t i v e a r r i v a l sa n d k m i n g s t r a t e g y ：r c h ( r e m o v a lo fc u s t o m e r a tt h eh e a d ) a n dr c e ( r e m o v a lo f c u s t o m e ra tt h ee n d ) a r ed e r i v e d f o rt h es e c o n dk i n do fq u e u ew i t h n e g a t i v ec u s t o m e r sa n dv a c a t i o n s ，b y u s eo f “s u p p l e m e n t a lv a r i a b l e s m e t h o d ，w eo b t a i ns o m eq u e u i n gq u a n t i t i e so ft h es y s t e ma n dt h e r e l i a b i l i t yq u a n t i t i e so ft h es e r v i c es t a t i o n k e yw o r d s ：n e g a t i v e c u s t o m e r ；b e r n o u l l if e e d b a c k ；v a c a t i o n ； r e p a i r a b l eq u e u es y s t e m ；l a p l a c e t r a n s f o r m ； s u p p l e m e n t a lv a r i a b l e s 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 保密口，在年解密后适用本授权书。 不保密口。 学位论文作者签名：殇劣绷0 矽叼年7 胡7 日 指导教师签名： 7 年2 月7 日 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已注明引用的内容以外，本论 文不包含任何其他个人或集体己经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：汤色冈7 j 日期：砂口7 年h 月7 日 江苏大学硕士学位论文 第一章绪论 本章对排队论的发展以及负顾客排队模型与休假排队模型的发展及研究现状 作一简单介绍，同时阐明本课题的研究意义以及主要的研究内容 1 1排队论发展简介 排队论又称随机服务系统，是专门研究由于随机因素的影响而产生拥挤现象 的科学它通过研究各种服务系统在排队等待中的概率特性，来解决系统的最优设 计和最优控制排队论最早可追溯到上个世纪，在上世纪初，丹麦数学家、工程师 e f l a n g 将概率论方法用于电话通话问题，从而开创了排队论这门学科的先河之后 的几十年时间里排队论的理论得到迅速发展，主要应用领域有：铁路，公路，航 空的运输管理，城市交通管理及控制，制定生产方案，生产任务的分配，医疗服 务，计算机设计、使用和维修、可靠性等等 排队系统由顾客和服务台构成，其中顾客是被服务的对象，服务台是进行服 务的对象排队系统有三个组成部分：输入过程、排队规则及服务机构输入过程是 描述顾客的来源及顾客是按怎样的规律抵达排队系统的；排队规则有先到先服务、 后到先服务、随机服务和有优先权的服务等；服务机构主要是指服务台的数目， 进行服务时服务的方式是并联还是串联，接受服务的顾客是成批的还是单个的， 服务时间服从什么分布，顾客们接受服务的时间是否独立反映排队系统的主要特 征有瞬时态与稳定态系统的队长、顾客在系统中的等待时间( 逗留时间) 、忙期等 自排队论这门学科形成以来，许多新的研究方向和研究方法层出不穷排队论 的研究主要集中在排队网络、矩阵解析法、数值计算、极限定理以及特殊模型等 方面关于排队论的研究方法，主要有：e d a n g 的阶段化，m c 法，k o s t e n 和c o x 的补充变量，n e u t s 的矩阵解析方法，史定华的向量马氏过程方法、频度转移法等 1 2 负顾客排队模型的研究现状 负顾客排队模型是排队论的一个新兴分支负顾客或者是一次误操作或者是外 来对服务台实施服务援助或者是系统的灾难，其主要作用是抵消系统中通常的顾 客正顾客负顾客的抵消作用按抵消时刻、抵消策略的不同对系统产生不同的 1 江苏大学硕士学位论文 影响抵消时刻可分为两类：一类是负顾客到达后立即抵消系统中现有的正顾客； 另一类是负顾客仅在服务结束时刻抵消现有的正顾客抵消策略可分为：抵消队首 正在接受服务的顾客( r c h ) ；抵消队尾的顾客( r c e ) ；抵消整个系统的顾客( d s t ) 以及随机数量的抵消 g e l e n b ef 1 1 最早将负顾客引入排队模型，开创了负顾客研究的先河这以后有 许多科研工作者投身到对负顾客研究的领域，产生了许多令人鼓舞的科研成果， 例如h a r r i s o n & p i t e 2 3 ，b a y r e & b o x m a 4 ，c o r r a l 5 ，a r t a l e j o & c o r r a l 6 7 ，z h u y i - j u n 8 等等 灾难是一类特殊的负顾客灾难到达系统时会将全部顾客( 包括正在接受服务 的) 抵消实际的服务系统不都是可靠的，并且灾难时有发生，比如突然的断电、 计算机病毒袭击通信系统等，这些都破坏了系统的正常运行c h e n 和r e n s h a w 1 1 ， w o n s y a n g 和k y u n g c c h a 1 2 】，a g o m e z - c o r r a l 1 5 】，j r a m l c o 和 a g o m e z c o r r a l 1 4 等人的研究都是对有灾难到达的创造性成果 关于负顾客的排队网络模型也有不少成果涌现( 参见文 1 7 】，【1 8 】，【1 9 】，【2 0 】， 【2 1 1 ) ，其中f o u m e a u , j m g e l e n b e ，e a n ds u m s ，r 1 9 讨论了具有多类正、负顾客的 平稳网络，负顾客可被视为信号，能抵消正在接受服务的正顾客，该网络的队长 也有乘积形式解g e l e n b e ，j m f o u m e a u 2 3 对一般的网络有了一个艺术性的推广： 作者引入了“重置 顾客并证明了网络稳态解具有乘积形式对于一个具有个不 可靠子系统的系统，个子系统中的任一个能随机地测试另外的子系统，且能在 自身运作的条件下，发现另外系统的失效且去重置该系统，从而整个系统的可靠 性得到了提高所以具有重置顾客的排队网络系统，可靠性有了很大的提高 1 3 休假排队模型的研究现状 经典的排队模型在排队论发展初期体现了其自身的研究价值，但到二十世纪 中后期，随着高科技领域的发展，经典的排队模型表现了一定的局限性在这一背 景下，上世纪7 0 年代，l e v y 与y c c h i a l i 从有效利用排队系统的闲期的观点出发首 先研究了m g 1 型休假排队系统，并引入了“休假”和“休假策略 等术语在一 些文献和应用中常出现的休假规则大致有：以触发休假开始为基础的规则，如空 竭服务、闸门服务、限量服务、b c m o n u i 休假、一般非空竭服务；以休假终止机 2 江苏大学硕士学位论文 制为基础的规则，如多重休假、单重休假、一般休假规则：门槛式休假等一方面， 休假排队反映了服务过程可能因某种理由发生中断这一客观事实；另一方面，各 种休假机制为系统的最优化设计和运行控制提供了极大的灵活性休假排队因此受 到广泛的关注也成为研究的热点之一在上世纪8 0 年代，研究的主要是休假m i g 1 型排队1 9 8 6 年，d o s h i 和t e g h e m 发表的两篇综述论文，总结了已有的研究成果 和方法，标志着休假排队己发展成一个有独立特色的研究方向在g 矾州1 休假排队 系统中，如果选取顾客到达时刻为嵌入点，它们即可能发生在忙期，也可能发生 在休假期并且休假的始点和终点均不在嵌入点的集合之内这一差别使得删1 型休假排队系统的分析增加了新的困难对休假时间分布具有m a r k o v 性质的 g i m 1 排队系统，无论嵌入点发生在休假还是在忙期，都能保证嵌入过程始终为 马尔可夫链为区别到达发生于忙期和假期两种不同情况，可将链的转移概率矩阵 表示成一个g i m 1 型结构矩阵田乃硕首先注意到这种联系，并把矩阵几何方法引 入休假g i m 1 型排队研究，推进了g 矾州1 型休假排队系统和多服务台休假排队系 统的研究休假排队系统理论的核心内容是随机分解，休假排队系统中的稳态指标， 通常可分解成两个独立随机变量之和，其中一个是对应经典的无休假系统中的同 名指标，另一个是休假引起的附加随机变量，称这样的结果为随机分解规律各种 随机分解结果以及导致这些结果的方法，是休假排队研究的一个突出特色随机分 解使休假排队与经典排队系统的比较一目了然，便于分析各种休假策略对经典排 队模型的影响由于经典排队系统的指标已经得到深入研究随机分解方法使休假 排队的分析转化为附加随机变量的研究，从而使稳态得以简化，随机分解不仅在 休假排队的理论分析中占有重要的地位，也为各种背景下的实际应用提供了极大 的便利近二十年，单服务台休假排队得到了伸入研究，建立了以随机分解为核心 的理论体系；多服务台休假排队也得到了一些特殊情况下的随机分解性质无论在 理论上还是在实际应用中，多服务台休假排队系统都更为重要然而，由于问题本 身的复杂性，2 0 多年来多服务台休假排队研究进展甚微，直到最近才取得了一些 实质性结果在多服务台情况下，休假策略可有更灵活多样的变化诸服务台可以同 步进入和终止休假状态，也可个别地开始和结束休假；还可以限制进入休假状态 地服务台个数，只有部分服务台可以休假多服务台休假排队系统中，当所有的服 务台全忙时，与无休假经典系统的行为没有区别而部分服务台工作时的边界状态 3 江苏大学硕士学位论文 概率通常及其复杂，并与对应的多台休假排队系统几乎没有什么可比性因此提出 了在服务台全忙的条件下将多台休假系统与对应的经典系统加以比较的思想，并 由此导致了各种条件随机分解结果2 0 多年的发展表明，休假排队研究不仅为经 典随机服务系统理论的发展注入了新的活力和生机，也为排队论在各种高新技术 领域的应用开辟了更广阔的前景 1 4 可修排队模型的研究发展 我们一般研究的排队系统都是假定服务台是不会发生故障的，但在实际生活 中却经常碰到服务台发生故障而不能为顾客服务的情形此时需要修理工人对发生 故障的服务台进行修理( 或更换) ，修理完成后再继续为顾客服务，我们把这类服 务台可能发生故障且可修复的排队系统统称为可修排队系统显然可修排队系统是 从服务台的性能角度提出来的，与休假排队系统有很大的差别，而且人们对这类 可修排队系统又提出了新的研究课题，即不仅要研究系统的排队问题，同时还要 研究因故障而产生的可靠性问题，例如系统的可用度和故障频度等因此，对可修 排队系统，无论是从排队论的角度，还是从可靠性理论的角度都是非常值得研究 的早在1 9 6 2 年a v i i t z h a k , b 和n a o r , p ，1 9 6 3 年t h i r u v e n g d a l l ，k 就研究了服务台 易坏的一些排队问题，利用补充变量的方法讨论一些有用的排队指标在随后的二 十年里关于服务台可能发生故障的文章也有很多，但是他们研究的问题仅限于系 统的一些排队性指标，直到1 9 8 2 年，我国的曹晋华和程侃两位老师真正的从可靠 性的角度全面地分析了一些有用的可靠性指标，例如：系统首次完全恢复时间的 分布，服务台首次失效时间分布，时刻t 服务台失效的概率，( 0 ，t ) 中服务台平 均失效次数等等以后关于服务台可修的排队模型都分析了可靠性指标关于服务 台可修的排队系统的文章中，人们不但讨论其排队指标而且也从可靠性角度对其 分析，许多复杂而且实用的排队模型应运而生 1 5 本课题研究内容及组织结构 本课题主要研究具有b e r n o u l l i 反馈的负顾客m g 1 休假排队模型，具有 b e r n o u l l i 反馈的负顾客m i x g 1 休假排队模型及有负顾客到达的m g 1 休假可 修排队系统借助于研究排队模型常用的方法：“补充变量法 及“母函数法”， 4 江苏大学硕士学位论文 得到了相应的排队指标 本文分五章，第一章为绪论，简要介绍负顾客排队及休假排队模型的研究现 状第二章介绍研究排队模型的主要方法，列出了几种常见的求解排队模型的方法 第三章研究具有b e r n o u l l i 反馈的负顾客m g 1 休假排队模型第四章研究具有 b e r n o u lli 反馈的负顾客m x g 1 休假排队模型第五章研究具有负顾客到达的 m g 1 休假可修排队模型 5 江苏大学硕士学位论文 第二章研究排队模型的方法 研究排队模型的方法很多，现仅介绍几种最常用的方法一种是嵌入马氏链的 方法，即寻求过程再生点另一种方法是补充变量法即将非马氏过程变成向量马氏 过程，再有就是拟生灭过程和矩阵分析法 2 1 嵌入马氏链法 对于一般服务或一般到达的排队系统，不是在任何时刻系统都具有马尔可夫 性质，只是在某些特殊的随机时刻系统才具有这种性质，我们称这种随机时刻点 为再生点，即从这个时刻起，系统好像又重新开始一样利用再生点，一般服务或 一般到达的排队系统的分析可转化为马尔可夫链的问题，用马尔可夫链的方法予 以解决，这种方法就叫做嵌入马尔可夫链法徐光辉 3 6 1 ，孟玉珂【3 7 】，唐应辉& 唐 , b 我 3 8 1 ，陆传赉【3 9 】，华兴【4 0 】，孙荣恒& 李建平【4 1 】，对此做了详细的论述 2 1 1 嵌入马尔可夫链点的寻找 设顾客是以参数为见的p o s s i o n 流到达，服务台是一般的服务时间分布，即是 m g 1 排队系统对任选的一个时刻t ，正在接受服务的顾客可能还没有服务完，于 是从时刻t 起剩余的服务时间，一般说来，已不服从原来的服务时间分布在一般 服务分布下，剩余的服务时间分布不具有无记忆性如果对m g 1 排队系统顾客进 入与离去的时刻进行观察和分析就会发现有些时刻是很特殊的，例如，观察一顾 客服务刚结束的时刻，从这个时刻服务台的工作有复原；或处于空闲状态或接受 另一顾客并为之服务服务结束的时刻不一定是顾客的到达时刻，对于走到半路中 的顾客来讲，由于到达间隔时间服从负指数分布，因此剩余到达时间( 由负指数 分布无记忆性) 还是服从负指数分布，对于这些时刻，系统好像重新开始一样， 系统未来的状态完全由这个时刻系统所处的状态决定，且与以前系统曾处于什么 状态无关，这种时刻叫做再生时刻或再生点把服务台完成服务的时刻一一找出， 得到一个再生点列，即t 1 ，t 2 ，t n t n ) 是随机点列，间隔时间6 + 1 一t n 也是随机 的我们来研究系统在时刻t n 时的状态在时刻t n ，由于一个顾客刚被服务完，假定 这时系统中有n n 个顾客，而在t n + l t i i 时间内到达l 个顾客，则时刻“1 ( 服务台 6 江苏大学硕士学位论文 刚结束下一个顾客服务的时刻) 系统中应有n + l - - 1 个顾客由于到达流是p o s s i o n 流，在这些再生时刻，观察系统的状态一顾客数，它具有马尔可夫性n n 表示一 个顾客服务结束后刚离开系统时留在系统中的顾客数，则 n n 就是一个马尔可夫 链，这叫嵌入马尔可夫链由于“l k 对一切n 都是同分布的，到达又是以p o s s i o n 流，于是经过乙钉一f 。这段时间，系统从状态。到。+ 工一1 状态的概率相同，因 此是一个齐次马尔可夫链为求得此马尔可夫链的平稳分布，首先应求出转移概率 2 1 2 转移概率矩阵 用一顾客服务结束后离开系统时的队长作为系统的状态，因此系统的一步转 移就是一个顾客离开系统到下一个顾客离开系统这段时间系统状态的变化 设服务时间v 的密度函数b ( t ) ，平均服务时间为 研矿】2 i 1 一j f 缈o ) a t ( 2 1 1 ) b ( t ) 的l 变换记做曰( s ) ，即曰( s ) 一f e - 酣b ( t ) d t ( 2 1 2 ) 其中要求r ( s ) o ，即s 的实数部分大于零再设p = c ：表示进入系统的第n 个顾客，t n ：表示c n 服务完离开系统的时刻， n n ：表示g 离开系统后留下的队长，v n ：表示g 的服务时间， ：表示g 的服务时间v n 内到达系统的顾客数 由定义知 v n 是独立同分布的随机变量序列，分布密度为b ( t ) ； a d 是独立 同分布的随机变量序列，概率分布记做 a k 为了求得一步转移概率p i j ，需先求 的概率分布 a k 而a k = p ( = k ) ( 2 1 3 ) 由于服务时间v n 是随机的，事件 氏= k ) 表示在第1 1 个顾客g 的服务时间 v n 内以p o s s i o n 流到达k 个顾客，而o k 0 0 若e i it ，说明( 0 ，t ) 内到达k 个顾客，而t ( o , o o ) 因此应用连续时间的全概率公式求a k ，即 口七5 j = p ( a 。= 后i k _ t ) b ( t ) d t ( 2 1 4 ) p - kik - t ) = 警e 却( 2 ”) 7 江苏大学硕士学位论文 从而 口。一f 号磬础6 ( t ) d t ，( os 七 0 时，服务台立刻接受顾客c 棚进行服务服务时间为k 这段时间达到的顾客数为 a 棚c 州服务结束离开系统时，系统内有顾客数。+ 。一n 。+ a 。n 1 若帆一0 ，则 c 。离开系统后，系统内无顾客，服务台处于空闲状态，这时c 棚还未到达c + 。达 到后立刻接受服务在c 州接受服务时间内到达a 柑个顾客因此c 棚服务完离开系 统时留下的队长虬“一a “因此从时刻f 。到时刻f 柚顾客的转移情况为 一艮a + 1 - 1 麓三三 叫 设p j l 一p ( n 。+ 。tj in 。f ) 当f = 0 时，p o jap + 1 一j lm - 0 ) tp + 。一j ) 。口，( 2 1 1 1 ) 当i 1 时，p 可p ( n 。+ 。一jin 。一f ) 一p ( n 。+ a “一1 一j i i f ) 。她+ l j 一i + 1 ) 一a 卜。“，( j f f 1 )( 2 1 1 2 ) 由此得一步转移概率矩阵 8 江苏大学硕士学位论文 p = 仞盯) 一 口o口1口2 口o口1口2 0 口oa 1 0 0 口o ( 2 1 1 3 ) 由转移矩阵p 可知，似是一个齐次马尔可夫链，且非周期不可约，当 p ：兰 1 时，这个马尔可夫链是遍历的，因此平稳分布存在状态转移图如图2 - 1 所示 2 1 3 平稳分布 图2 - 1m i g l 嵌入马尔可夫链状态转移图 我们已指出当p 1 时，嵌入马尔可夫链 。 存在平稳分布仞， ，【p ， 应当满 足平稳方程组 p ，。荟p ；p ，p o ( 2 1 1 4 ) 我们用母函数方法解此无限个方程，设 p ( s ) 。薹p ，s 7 ( 2 1 1 5 ) a ( s ) 2 篆叩 ( 2 1 1 6 ) 把式( 2 1 1 1 ) ，( 2 1 1 2 ) 代入平衡方程组，有 f + 1 p ，铴”善p 一钉 ( 2 1 1 7 ) 式( 2 1 1 7 ) 两端乘s j ，对j 求和，有 邱m 。荟叩荟( 善p j l 2 j - i + 1 ) 一 9 如吒q 一 江苏大学硕士学位论文 由此解得 。p o a ( 卅善p i $ i q 。，a 一“ 。p o a ( s ) + 昙( 荟p t s 。一p 。) 荟口r s 7 - p o a o ) + ( p ( s ) 一p 。m o ) ( 2 1 1 8 ) a 即) = 訾 叫9 ) 因p ( 1 ) = 1 a 1 ) = 1 ，上式中，令j 专1 用罗比塔法则，得 1 。l i l n p ( 1 ) ：l i m - a ( s ) p 。+ ，p o ( 1 - s ) a ( s ) 一粤：卫 s - - 。l 、7s 叫 a ( s ) 一1a ( 1 ) 一1 p 一1 其中用到a ( 1 ) 2 善撇。= e a 。】。p 从而得到 p o 一1 一p p ( s ) ：坠筌之燮 ( 2 1 2 0 ) 一 a f s l 一s 、 这就是平稳分布母函数的表达式由( 2 1 2 ) ，式( 2 1 2 0 ) 删- - 步化简，因为 郴，- 扣“一f 扩学嘞出 一fe 觚m 6 ( f ) 疵一f e 以6 ( f ) 出 一b ( 名( 1 一s ” ( 2 i 2 1 ) 代入式( 2 1 2 1 ) ，则 p ( s ) ：坠垡生哩幽( 2 1 2 2 ) 一 b ( 五( 1 一s ) ) 一s 、 它是嵌入马尔可夫链的平稳分布的母函数，这就是我们要求的最后结果称为 波来克泽克一辛钦( p o l l a c z e k - k h i n c h i n ) ( p - i q 第一变换式 2 2 补充变量法 补充变量法是研究排队模型的一种常用方法许多排队系统的队长过程 o ) ，f o 不是马氏过程，但是可以通过引入补充变量使得这个非马氏过程马氏 化e f l a a g 的阶段化思想可以看成是补充变量法产生的初始背景c o x 完整地提出了 1 0 江苏大学硕士学位论文 补充变量的技巧下面我们以m 工g 1 排队模型为例来说明用补充变量法解决排 队问题的主要思路 考虑一个经典的m 工g l 排队模型，顾客成批到达，每批到达的顾客数是随 机变量x ，批到达流是参数为五的波松流，服务时间为一般分布： g g o ) - 上g o 如| 1 一c x p ( 一f g 皿) ，e ( g ) = 去 系统中只有一个服务台； p 伍= * c ；c g ) 罗c ；z _ ， 设o ) 表示，时刻系统中的顾客数显然o ) 不是马尔可夫过程设x o ) = x 为r 时刻正在接受服务的顾客已经用去的服务时间，则引入补充变量x o ) 后 o ) ，x o ) 是一个二维马尔可夫过程 令p o ( t ) - 尸( o ) = 0 ) 只o ，x x = 尸( o ) 一n , x 0 昂一l i i n r o ) ，只g 协；l i m o ，x ) 出 由昂o + 出) = p 任t 对亥l j ，系统中没有顾客且在f 到f + 出没有顾客到达系统) + p ( 在f 时刻系统中有一个顾客开始服务且在f 到f + 出他的剩余服务时间为o ) 得晶1 6 f + a t ) ；e o ( t x l 一尬) + f g k o ，x 协+ 。( f ) 两端除以a t 并令缸专0 整理可得 ( 名+ 丢) 晶1 6 f ) 一f g 边o ，x 域 再令t 专o o 可得 儡= j f 麒g 蛾g ) 出 同理可得 这里规定 ( 丢m 刖) 只阱骞批 ) 纠 v ；0 白 l l 江苏大学硕士学位论文 只( 0 ) 一知。p o + j f g ) 已+ 。g ) 出 p o + f 只g 皿一1 然后可以对上述方程求解，从而得到一些排队指标 2 。3 拟生灭过程和矩阵分析法 矩阵解析方法是由美国随机模型( s t o c h a s t i cm o d e l ) 杂志主编m n e u t s 首次提 出，并且在他1 9 8 1 年和1 9 8 9 年出版的两本专著中作详细阐述该方法主要从计算 概率的角度解决随机模型研究中的数值计算问题，其突出特点在于用该方法得出 的结果均以矩阵形式给出，便于在计算机上进行计算而传统的嵌入马尔可夫链方 法所得结果均以l a p l a c e 变换或母函数的形式给出因此矩阵解析方法是研究随机 模型的一种有效的和重要的方法 定义 考虑一个二维马尔可夫过程 x o ) ，( f ) ，状态空间是 q = 船，办七芑0 , 1j m ，称 x ( f ) ，( ，) 是一个拟生灭过程，如果其生成元可以写 成下列分块三对角形式 a = 厶c o b l ac bac 曰a 其中所有子块都是m 阶方阵，满足 + c 。k = b + a + c = 矗+ a + c l 一0 a 和a 有负的对角线元素和非负的非对角线元素，其余子块均是非负阵，e 是 元素全为1 的列向量称状态集( 1 【，1 ) ，化2 ) m ) 为水平k 若过程是正常返的， 以留， 表示过程 x ( f ) ，( r ) 的极限变量，并记 一烘p 口o ) 一七，( f ) = ) = 尸伍一k , j = 其中k 0 , 1 j m 为适应q 的分块形式，将稳态概率按水平写成分段形式 以= ( 7 小巩2 ，) ，k 0 江苏大学硕士学位论文 拟生灭过程是经典生灭过程从一维状态空间到多维状态空间的推广，正如生灭过 程的生成元具有三对角形式一样，拟生灭过程的生成元是分块三对角阵从2 0 世纪踟 年代到9 0 年代田乃硕等把n c u t s 的矩阵几何解方法引入到休假排队模型中，促进了多 服务台休假排队系统的研究，并且初步建立起多服务台休假中以条件随机分解为核心 的理论框架，为经典排队论的发展和应用开辟了更为广阔的前景 江苏大学硕士学位论文 第三章具有b e r n o u l l i 反馈的负顾客m g 1 休假排删 关于负顾客的排队系统，最早源i 刍g e l e n b e ( 1 9 9 1 ) 【1 】的研究工作，此后几乎 每年都有令人鼓舞的成果产生目前负顾客已经渗透到交通、机械、控制以及计算 机等许多领域h a r d s o n & p i t e l ( 1 9 9 3 ) t ：2 1 ，( 1 9 9 6 ) 【3 1 ， b a y e r & b o x m a ( 1 9 9 6 ) t 4 1 ， a r t a l e j o & c o r r a l ( 1 9 9 9 ) t 6 ，z h uy i j 蚰( 2 0 0 1 ) 【8 1 等人的研究都得到了有意义的结果在通 常的排队系统中，有时还会遇到顾客对所得到的服务不满意，要求反馈的情形， 同时服务台也会因为各种原因而进入休假状态本章考虑把反馈，负顾客和休假排 队系统结合起来，在服务规则为先到先服务( f c f s ) 的条件下，分别研究了抵消 规则为r c h 和r c e 的情形，得到了系统瞬态和稳态队长分布的概率母函数 3 1 负顾客的抵消策略为r o h 的多重休假m g 1 排队模型 3 1 1 模型的数学描述 假设： ( 1 ) 正、负顾客分别以到达率为刀，才的p o i s s o n 流进入单服务台系统 ( 2 ) 负顾客仅起到抵消正顾客的作用，并不接受服务正顾客的服务时间序列 石) 独立同一般分布，分布函数为g ( t ) ，密度函数为g ，风险率函数为 妒嵩御：g 沪础跏一f o g ( t ) a t - 1 _ e x p 0 郎) 绯 ( 3 ) 服务台的休假时间y 为一连续型随机变量，且有： y ( f ) ip s f ) 2 上y o ) 出z1 一e x p - f o y ( s ) 凼) ， 其中y o ) 和7 0 ) 分别为y o ) 的密度函数和风险率函数 ( 4 ) 服务规则是先到先服务( f c f s ) ，休假策略为空竭服务多重休假( e s ，m v ) ， 负顾客抵消队首顾客( r e m o v a lo f c u s t o m e r sa tt h eh e a d ) ，若负顾客到达时系统中无 正顾客，则负顾客自动消失 ( 5 ) 若正顾客在接受服务的过程中无负顾客到达，则正顾客在服务完成后以概 率o ( o 0 1 ) 离开系统，以概率1 0 反馈到队尾等待下次服务 1 4 江苏大学硕士学位论文 ( 6 ) 系统开始时处于休假状态 ( 7 ) 记每个顾客完成一次服务所需的平均服务时间。 万1 = t d g ( r ) ，云 1 ，系 统存在稳定状态 3 1 2 系统的状态与概率定义 令( f ) 表示f 时刻系统中的正顾客数，为了区别假期和忙期，引进二值随机过程 ，o ) ，j ( f ) 取0 表示系统处于假期，( f ) 取1 表示系统处于忙期同时引进补充变量 x ( f ) 和y o ) 分别表示时刻t 正在服务的顾客已花的服务时间和正在休假的服务员已 花的休假时间，则随机过程：p o ) ，o ) ，x o ) ，】，( f ) ) 是状态空间 e = ( 0 ，0 ，_ ) ，) ，( 0 ，n ，) ，) ，g n ，砷：n = 1 2 ，；0 x o o ，0 y 畸上的向量马氏过程 ( v m p ) ，状态概率密度定义为： k n ( f ，) ，) 方一p ( d 一刀，y 0 3 z 变换：k z ) 2 荟如) ，) z “ p ( 叫，z ) 2 善p 取咖“ ( 4 ) 其他符号： 五+ 才 a ( z ) 。五一刀z 一才! z i z i 1 坤，) ，力- f o 讯缈州缈南出m 加f p 巾+ a ( 栅雨小蹦训) ，) 西， f ( s ，z ) 一f f e - ( s + a ( z ) ) y 矿( y ) 邢，) ，z ) d y 1 6 ( 3 4 ) ( 3 5 ) ( 3 6 ) 江苏大学硕士学位论文 3 1 5 状态方程组的解： 对( 3 1 ) 一( 3 6 ) 式取l 变换得： 【去+ s + 兄+ ( 功】p ：( s ，功一刀p ：4 ( j ，力，以= 1 ，2 ， ( 3 7 ) 【专+ s + 名+ y ( y ) 弘：( s ，) ，) 一刀七二( s ，y ) + 才七二+ 1 ( s ，) ，) ，刀一1 ，2 ， ( 3 8 ) 赢o ，0 ) 一面z n ( s ，功出+ 见一f 盛n ( s ，力出+ 0 一哳z ( s ，x ) u ( x ) a x + 【专+ s + 刀+ 厂( y ) 】七：( s ，) ，) 一才砰( s ，) ，) + 万( y ) r ( s ，y ) r ( y ) d y ，万一l 2 ， ( s ，0 ) 一o ，n 一1 ，2 ， ( 3 9 ) ( 3 1 0 ) ( 3 1 1 ) k o ( s ，o ) 一啊p ：( s ，茗) ) a x + 五一f p ：( s ，x ) 出+ f 七：( s ，y ) y ( y ) d y ( 3 1 2 ) 对( 3 7 ) 式进行z 变换得： 【兰+ s + 兄+ ( 功】p + o ，而力；a + z p + o ，x ，z ) 职 解方程可得：p + ( s ，而力= p + ( s ，0 ，z ) e 巾+ 五一矿妒反力 ( 3 1 3 ) 对屯+ o ，) ，) 进行z 变换，将( 3 8 ) 式两端同时乘以z ”，并关于刀 0 求和，再与 ( 3 9 ) 式相加并整理可得： 吴+ s + a ( z ) + y ( y ) i t o ，y ，z ) 万( ) ，) + 才( 1 一马成o ，) ，) ( 3 1 4 ) d yz 解方程( 3 1 4 ) ，并将对万( y ) 的计算归结到k ( s ，0 z ) 中去，可得到： k o ，y ，力be - ( ( z ) ) y 玖y ) 【k ( s ，0 ，z ) + 才( 1 一马，( s ，y ，z ) 】 ( 3 1 5 ) z 由( 3 1 1 ) ，( 3 1 2 ) 式及初始条件可得： k ( s ，0 ，z ) 一k ( s ，o ) + 1 对p ：( s ，o ) 施行z 变换，并结合( 3 1 0 ) ，( 3 1 2 ) 式可得： p ( 咖) 一( 詈+ 1 _ 吖p ( 蹦，批( 触+ 智p ( 蹦力出+ 1 7 ( 3 1 6 ) 江苏大学硕士学位论文 f k ( s ，y ，z ) r ( y ) d y k o ( s ，0 ) ( 3 1 7 ) 将( 3 1 3 ) ，( 3 1 5 ) ，( 3 1 6 ) 式代入( 3 1 7 ) 式并整理可得： 札吣，= 掣器兰薷鹄袋畿辫 为了确定k ( s ，0 ) ，给出如下两个引理： 引理1 ( 儒歇定理) p 8 】如果函数厂( z ) 和g ( z ) 在简单闭曲线l 及l 的内部解析， 且在曲线l 上有：厂( z ) o ，i f ( z ) i k 0 ) i ，则在l 的内部，厂( z ) 与，( z ) + g ( z ) 有相同 的零点个数 引理2 ( 推广的t a k a c s 引理) 【4 3 1 若： ( a ) r e ( s ) o ，l 甜i o ，u i 1 ，l y is 1 ； ( c ) r e ( s ) o ，川1 ，i v l l ，则方程z = u g ( s + 名一厩) 在单位圆 i z l - 1 内有唯一解它可以表示为： 坤鸬d = 喜等等e - ( s + a ) x x i - 1 础功艄抵 o ，归批1 内为 o ，比，y ) 的连续函数，在r e ( s ) o ，川 1 ，i v i s 1 内为( s ，“，d 的解析函数又若令 厂( ，) 。r ( o a v ) ，庇( “) 一r ( o ，“，1 ) ，石( s ) - y ( s ，1 ，1 ) ，贝j 有： l ，i 川r a f m 国瞄0 刚叫觯搿； 1 ，l 黔i m 舯1 , p 1 ， 譬碧 ( “) = o - 一p ，) ，q p 一 l g ( z ) 1 由引理( 1 ) 可知厂( z ) 与，( z ) + g ( z ) 在i z i ；1 的内部有 相同的零点个数 由引理( 2 ) 易知，( z ) 在| z | 1 的内部有唯一一个零点，故厂( z ) + g ( z ) 在l z l ；1 的 内部也有唯一的零点，设其为6 0 ) ，贝j j b ( s ) 也应为( 3 1 8 ) 式右端分子的零点即： 残( s ，o ) 【6 ( s ) 哥o + a ( 扶s ) ”一6 0 ) 】+ 6 0 ) 谚q + a p ( s ) ”+ 旯一p o ) 一1 ) ，( s ，6 ( s ) ) 0 ， 从而：碌( s ，o ) ：坐必尘! 垒( 兰滏二丛兰! 里垒垒q ( 兰逊 ”。 6 ( s ) 【矿( s + a ( 6 ( s ) ) ) - 1 注：由前面的证明可知，方程 z = ( p + z 一跳) 季( s + 名一旯+ z ) 一五一口( s + 力一五+ z )( 3 1 9 ) z i 一1 的内部有唯一的解为z = 6 ( s ) 为了确定6 ( s ) ，可以采用下面的方法：任 取一点s o ，r e ( s o ) 0 ，则 b ( s o ) = ( p + 6 ( ) 一o b ( s o ) ) 季( s o + 兄一z + b ( s o ) ) - 2 一口( + 名一五+ 6 ( ) ) 取定以后，可采用迭代的方法求得6 ( ) 的近似值令： 缸“= ( 秒+ 气一o z k ) p , ( s o + 2 - 2 + z k ) - _ t 一口( + 允一名+ 磊) ，选一初始值进行迭代可得 b ( s o ) 的近似值然后将6 ( s ) 在点展开成幂级数的形式： 6 ( s ) = b ( s o ) + 6 7 ( ) o 一) + 垡掣。一) z + ，其中6 ，( ) ，( ) ，可以利用隐 函数的求导法则求得，这样就可以用上式右端的级数去逼近6 ( s ) 数值例子： 假设顾客的服务时间序列协) 服从2 阶e r l a n g 分布，即： g q ) - 础引 - l - e - 骞譬娩。，则： 荆= ( 0 2 ，虿。o ) = 丽s + 2 0 取p 一0 5 ，刀= 2 ，才；1 ，盯= 6 ，则兄= 3 将_ i r i s 数值代入( 3 1 9 ) 式并取；1 ， 经整理可得：6 ( s 。) 2 器，运用参考文献【钙1 中的简单迭代法可以求得 b ( s o ) 的近似值，其中误差小于1 0 ，具体迭代结果如表1 ： 1 9 江苏大学硕士学位论文 表1 七 o0 1 0