（应用数学专业论文）带有负顾客且具有反馈的排队模型.pdf

江苏大学硕士学位论文 摘要 本课题主要研究了两类带有负顾客且具有反馈的排队模型，把负 顾客和反馈相结合，先考虑了一类带有负顾客且具有反馈的m g i 排 队模型，正顾客服务完以概率p 离开系统，以概率卜p 排到队尾继续 接受服务，负顾客抵消正顾客，运用补充变量法和状态转移及l 变换 分析法，得到了该类系统稳态队长的概率母函数，在此基础上讨论了 此类排队模型的可修状态，得到了一系列的可靠性指标。接着又考虑 了一类带有负顾客且具有两个服务阶段的反馈的m g i 重试排队模 型，通过分析稳态存在的条件和状态转移方程，得到了稳态时的一些 排队指标。 关键词：负顾客，反馈，重试，补充变量法，l 变换，概率母函数 i 江苏大学硕士学位论文 a b s t r a c t t h i sp a p e rm a i n l yr e s e a r c h e st w ok i n d s o fq u e u e sw i t hn e g a t i v e c u s t o m e r sa n df e e d b a c k ，b yc o m b i n i n gn e g a t i v ec u s t o m e r sa n df e e d b a c k w ef i r s tc o n s i d e rt h eo n ek i n di sm g iq u e u e sw i t hn e g a t i v ec u s t o m e r s a n df e e d b a c k ，w h e nt h ep o s i t i v ec u s t o m e rf i n i s h e si t ss e r v i c e ，i tw i l ll e a v e t h eq u e u ea tt h er a t eo fp ，a n dc o m eb a c kt ot h eq u e u ea tt h eo t h e rr a t eo f 1 - p ，a n dt h en e g a t i v ec u s t o m e rr e m o v eo n ep o s i t i v ec u s t o m e r b yu s eo f t h e s u p p l e m e n t a l v a r i a b l e s m e t h o d ，s t a t et r a n s f e ra n a l y s e s a n dl t r a n s f o r m ，w eg e tt h e i rg e n e r a t i o nf i m c t i o n si nt h es t e a d ys t a t e a n da t t h i sb a s e ，w ea l s oc o n s i d et h em g 1r e p a r i a b l eq u e u ew i t hn e g a t i v e c u s t o m e r sa n df e e d b a c k ，a n dg e tt h er e a l i a b l ei n d e x e s t h eo t h e rk i n di s t h em g 1r e t r i a lq u e u e sw i t hn e g a t i v ec u s t o m e r st w op h a s e so fs e r v i c e s a n df e e d b a c k ，b yu s eo ft h es a m em e t h o d ，w ea l s od e r i v es o m e p e r f o r m a n c em e a s u r e s k e yw o r d s ：n e g a t i v ec u s t o m e r s ， v a r i a b l e s m e t h o d ， f u n c t i o n i v f e e d b a c k ，r e t r i a l ，s u p p l e m e n t a l l a p l a c et r a n s f o r m ，g e n e r a t i n g 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规 定，同意学校保留并向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅。本人授权江苏大学可以将本学位论 文的全部内容或部分内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 保密口，在年解密后适用本授权书。 不保密邑 学位论文作者签名：缘溽 指导教师签名： 撕年f2 月“日 矿6 年t t ，月站日 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已注明引用的内容以外， 本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：缘沼 日期：”“年1 2 月“日 江苏大学硕士学位论文 第一章绪论 本章对排队论的发展以及负顾客排队模型的发展及研究现状作一简单介绍， 同时阐明本课题的研究意义以及主要的研究内容。 1 1 排队论发展简介 排队论又称随机服务系统，起源于2 0 世纪初的电话通话。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 ) 引进了生灭过程时，排队论才被数学界承认为一门重 要的学科。在二战期间和二战以后，排队论在运筹学这个新领域中成了一个重要 的内容。2 0 世纪5 0 年代初肯德尔( d q k e n d a l l ) 对排队论作了系统的研究，他 用嵌入马尔可夫( a m a r k o v ) 链方法研究排队论，使排队论得到了进一步发展。 他首先用三个字母组成的符号表示排队系统。2 0 世纪6 0 年代起，排队论研究的 课题日趋复杂，很多问题不是很难求得其精确解，就是求得的解非常复杂，不便 于应用，因而开始了近似方法的研究。 排队论的产生与发展来自实际的需要，实际的需要也必将决定它今后的发 展，排队论的发展日新月异，应用领域也不断扩大。它适用于一切服务系统，特 别在通信系统、交通系统、计算机存储系统和生产管理系统等方面应用广泛。 排队系统由顾客和服务台构成，其中顾客是被服务的对象，服务台是进行服 务的对象。排队系统有三个组成部分：输入过程、排队规则及服务机构。输入过 程是描述顾客的来源及顾客是按怎样的规律抵达排队系统的；排队规则有先到先 服务、后到先服务、随机服务和有优先权的服务；服务机构主要是指服务台的数 目，可以分为单服务台、有限个服务台与无限多个服务台。进行服务时服务的方 式可分为并联和串联，接受服务的顾客可以是成批的是也可以是单个的，服务时 间可以服从不同的分布，如定长分布、指数分布、几何分布与一般分布等。顾客 们接受服务的时间是否独立。反映排队系统的主要特征有瞬时态与稳定态系统的 队长、顾客在系统中的等待时间( 逗留时间) 、忙期等。 江苏大学硕士学位论文 自排队论这门学科形成以来，许多新的研究方向和研究方法层出不穷。大量 的科研工作者在此领域取得了丰硕的成果。排队论专家田乃硕等 3 4 】把矩阵解析法 引入g i m 1 型休假排队系统，并研究了部分服务台同步的休假排队模型，极大丰 富了排队模型的理论；史定华 4 2 将频度转移法用于可修服务系统并且对可靠性作 了大量工作：g e l e n b e 1 将负顾客引入排队系统。当前，排队论的研究主要集中在 排队网络 4 9 ，5 0 ，5 1 1 、矩阵解析法 3 0 ，3 1 ，5 2 、数值计算、极限定理以及特殊模型等 方面。其中特殊模型主要是研究具有实际应用背景的满足特殊需要的有一定假定 前提的排队模型，而休假排队、可修排队以及由这两方面衍生的一些可修休假排 队模型和负顾客排队模型是特殊模型研究的几个重要方面。关于排队论的研究方 法，主要有：e f l a n g 的阶段化，k o s t e n 和c o x 的补充变量，n e u t s 的矩阵解析方 法 3 0 ，5 3 1 ，史定华的向量马氏过程方法、频度转移法。由于排队论研究的课题日 趋复杂，很多问题难求精确解，因此近似方法的研究正逐步深入【4 4 ，4 5 。 1 2 负顾客排队模型的发展及研究现状 负顾客的排队模型是排队论的一个新兴分支。负顾客可视为一次误操作或者 是外来对服务台实施服务援助或者是系统的灾难，其主要作用是抵消系统中通常 的顾客正顾客。负顾客的抵消作用按抵消时刻、抵消策略的不同对系统产生 不同的影响。抵消时刻可分为两类：一类是负顾客到达后立郎抵消系统中现有的 正顾客；另一类是负顾客仅在服务结束时刻抵消现有的正顾客。抵消策略可分为： 抵消队首正在接受服务的顾客( r c h ) ；抵消队尾的顾客( r c e ) ；抵消整个系统 的顾客( d s t ) 以及随机数量的抵消。 g e l e n b e 是将负顾客引入排队模型 1 】和排队网络 2 】的第一人。在文【l 】中作者 采用标值点过程来研究问题，得到了不同抵消策略下的马氏链 l ( t ) 为正常返的 再生过程的充要条件，并且说明了新模型的稳态条件与负到达有关。文献 2 作 者将负顾客引进排队网络后，证明了能描述网络性质与顾客流方程解存在唯一性 的关系的几个定理。之后，负顾客的排队模型引起了各国学者的广泛兴趣 2 7 ，2 8 ，2 9 ，4 6 ，4 7 ，4 8 1a h a r r i s o n 和p i t e l 在文 3 】中获得了不同服务规则和抵消原则下的系统稳态队 长分布的概率母函数及平均队长。首先，对策略为先到先服务、抵消队尾顾客的 2 江苏大学硕士学位论文 系统，得到了稳态队长母函数的表达式，并引出了第一类f r e d h o l m 积分方程， 其次，对策略为先到先服务、抵消被服务顾客的系统，通过讨论对系统的服务时 间进行修正，获得队长分布的概率母函数，接着，对策略为后到先服务、抵消被 服务顾客的系统，作者运用补充变量法，对稳态条件下的系统状态转移概率进行 分析，获得结论，此外，对其余具有不同的服务规则和抵消规则的系统，作者也 作了讨论。j a i n 和s i g m a n 在文【4 】中分析了负到达抵消目前系统中的所有顾客的 情形，根据比率守恒律，得到了该系统的载荷量分布类似的 p o l l a c z e r - k h i n t c h i n ( p k ) 公式。b o u c h e r i e 和b o x m a 在文 5 】中研究了负顾客抵消 随机数量的正顾客的m g l 排队模型，作者利用两种不同的方法来研究稳态系 统的载荷量。b a y e r 和b o x m a 在文 6 】中讨论了负顾客的m g 1 排队模型的 w i e n e r - h o p f 分析和随机徘徊问题，得到了嵌入点时刻和任意时刻的队长分布的 概率母函数。在求嵌入点时刻的队长时，文章考患两种情形：一类是系统空时， 负到达自动消失；一类是系统空时，负到达停留在系统中，直到下一次服务结束 时才去抵消正顾客，分别得到了各自队长分布的概率母函数。 负到达也可以解释为灾难 1 0 ，1 2 ，1 3 ，1 4 ，1 5 ，1 6 ，灾难发生时抵消系统中所有顾 客，也可解释为集体退出【1 7 】或队伍溃散u s 。a r t a l e j o 和c o r r a l 在文【1 0 研究了 一个既有清理又有竞争再入的排队，即新到达的顾客发现系统忙时会进入轨道等 待，且轨道中的顾客与正在服务的顾客以一定的比例竞争接受服务，灾难发生时 系统彻底清理并立即更新，但他们只讨论了稳态情况下系统的性能指标。史定华 3 5 ，4 2 用补充变量法，构造向量马氏过程和吸收向量马氏过程，研究了该系统瞬 态情况，得到这一系统的一些重要指标的分布。 最近，朱翼隽在文【7 ，3 6 】中创造性地提出了负顾客可以接受服务的思想，研 究了一类服务规则为f c f s ，抵消规则为r c e 的负顾客的m g 1 排队模型，得 到了队长分布的概率母函数、虚等待时间及等待时间的l 变换表达式。文【8 】的 作者运用补充变量法，对具有负顾客的m g 1 可修排队模型进行了研究，得到 了各自队长分布的广义概率母函数。文 9 的作者还将负顾客引入休假排队系统， 研究了具有负顾客的m g 1 和g i m 1 休假排队模型，分别得到了系统队长的概 率母函数，大大丰富了负顾客排队模型的理论体系。 江苏大学硕士学位论文 1 3 本课题研究内容及解决问题的方法 本课题研究的是两类带有负顾客且具有反馈的排队模型，借助于研究排队模 型常用方法“补充变量法”及“嵌入马氏链方法”，得到了所需的排队指标。 对带有负顾客且具有反馈的m g 1 排队模型，按照抵消规则的不同，运用 补充变量法和状态转移及l 变换分析得到了它们队长分布的l z 变换表达式、 广义概率母函数，在此基础上接着又考虑了此模型的可修排队系统，得到了一系 列的可靠性指标。 对于带有负顾客且具有两个服务阶段反馈的m j g 1 重试排队系统，通过嵌 入马尔可夫链得到了系统稳态存在的充要条件，并利用补充变量法得到稳态时 系统队长和重试区域中队长以及一些其他的排队指标。 4 江苏大学硕士学位论文 第二章研究排队模型的方法 排队论是运筹学的重要分支，也是应用概率论的重要组成部分。它的基础是 概率论和随机过程。排队论已经发展了近一个世纪形成了一系列较成熟的研究方 法，取得了丰富的成果。下面简单介绍几种常用的研究排队模型的方法。 2 1 嵌入马氏链法 对于一般服务或一般到达的排队系统，不是在任何时刻系统都具有马尔可夫 性质，只是在某些特殊的随机时刻系统才具有这种性质，我们称这种随机时刻点 为再生点，即从这个时刻起，系统好像又重新开始一样。利用再生点，一般服务 或一般到达的排队系统可化为马尔可夫链，用马尔可夫链的方法予以解决，这种 方法就叫做嵌入马尔可夫链法。徐光辉 4 0 】，孟玉珂【3 7 】，唐应辉& 唐小我【3 8 】， 陆传赉【3 9 】，华兴 3 2 ，孙容恒& 李建平 3 3 】，对此做了详细的论述。 2 1 1 马尔可夫链嵌入点的寻找 设顾客是以参数为五的p o s s i o n 流到达，服务台是一般的服务时间分布，即 是m g 1 排队系统。对任选的一个时刻t ，正在接受服务的顾客可能还没有服务 完，于是从时刻t 起剩余的服务时间，一般说来，已不服从原来的服务时间分布。 在一般服务分布下，剩余的服务时间分布不具有无记忆性。如果对m g 1 排队 系统顾客进入与离去的时刻进行观察和分析就会发现有些时刻是很特殊的，例 如，观察一顾客服务刚结束的时刻，从这个时刻服务台的工作有复原；或处于空 闲状态或接受另一顾客并为之服务。服务结束的时刻不一定是顾客的到达时刻， 对于走到半路中的顾客来讲，由于到达间隔时间服从负指数分布，因此剩余到达 时间( 由负指数分布的无记忆性) 还是服从负指数分布，对于这些时刻，系统好 像重新开始一样，系统未来的状态完全由这个时刻系统所处的状态决定，且与以 前系统曾处于什么状态无关。这种时刻叫做再生时刻或再生点。把服务台完成服 务的时刻一一找出，得到一个再生点列，即t l , t 2 ，t n 。 t n ) 是随机点列，间 隔时间0 1 一t n 也是随机的。我们来研究系统在时刻t r i 时的状态。在时刻k ，由于 一个顾客刚被服务完，假定这时系统中有n n 个顾客，而在“l t n 时间内到达l 江苏大学硕士学位论文 个顾客，则时刻“l ( 服务台刚结束下一个顾客服务的时刻) 系统中应有n n + l 一1 个顾客( 假定n i l o ) 由于到达流是p o s s i o n 流，在这些再生时刻，观察系统的状态 一顾客数，它具有马尔可夫性。n 。表示一个顾客服务结束后刚离开系统时留在 系统中的顾客数，n n 。 就是一个马尔可夫链，这叫嵌入马尔可夫链。由于“l t l i 对一切n 都是同分布的，到达又是以p o s s i o n 流，于是经过f - t 。这段时间， 系统从状态m 到m + 三一1 状态的概率相同，因此是一个齐次马尔可夫链。为求 得此马尔可夫链的平稳分布，首先应求出转移概率。 2 1 2 转移概率矩阵 用一顾客服务结束后离开系统时的队长作为系统的状态，因此系统的一步转 移就是一个顾客离开系统到下一个顾客离开系统这段时间系统状态的变化。 设服务时间v 的密度函数b ( t ) ，平均服务时间为 研明= l ：f t b ( t ) d t ( 2 1 1 ) j b ( t ) 的l 变换记做b ( s ) ，即b ( s ) = f e 一“b ( t ) d t ( 2 1 2 ) 其中要求r ( s ) o ，即s 的实数部分大于零。再设p = 州 c 。：表示进入系统的第n 个顾客，t l l ：表示c 。服务完离开系统的时刻， n 。：表示c 。离开系统后留下的队长，v 。：表示c 。的服务时间， a 。：表示c 。的服务时间v 。内到达系统的顾客数。 由定义知 v 。) 是独立同分布的随机变量序列，分布密度为b ( t ) ： a n 是独立 同分布的随机变量序列，概率分布记做 a i ( ) 。 为了求得一步转移概率p i j ，需先求 a n ) 的概率分布 a k 。 而 a k - - - - - - p ( a n = k )( 2 1 3 ) 由于服务时间v 。是随机的，事件 a n = k ) 表示在第n 个顾客c 。的服务时间v 。 内以p o s s i o n 流到达k 个顾客，而o 吒 o o 。若圪= r ，说明( 0 ，t ) 内到达k 个顾客，而t ( 0 ，o o ) 。因此应该用连续时间的全概率公式求a k ，即 以2jp ( a 。= k i 圪= t ) b ( t ) d t ( 2 1 4 ) 姒圳圪f ) = 譬p “ ( 2 ”) 6 江苏大学硕士学位论文 从而 吒= r 譬“6 ( r ) 以( o 七 0 时，服务台立刻接受顾客c 。进行服务。服务时间为吃。这段时间达到 的顾客数为a 。c + 。服务结束离开系统时，系统内有顾客数m + ，= 帆+ 以+ 。一1 。 若以= 0 ，则e 离开系统后，系统内无顾客，服务台处于空闲状态，这时g + 。还 未到达。g 。到达后立刻接受服务。在e + 。接受服务时间内到达4 + ，个顾客。因 此g + 服务完离开系统时留下的队长m + 。= a 。因此从时刻，。到时刻+ 。顾客转 移为 = 默缸i 。1 麓： 叫。， 设p 。= p ( m + 1 = ，im = i ) 当i = 0 时，p o = p ( 以+ l = i 虬= 0 ) = ，( 以“= _ ，) = 口j ( 2 1 1 i ) 当i 1 时，p 口= p ( 。l = ，】虬= f ) = p ( 虬+ a 。l - i = _ ，i m = f ) = p ( 4 ，+ l = 一i + 1 ) = a ，一。“，( j i 一1 )( 2 1 1 2 ) 7 江苏大学硕士学位论文 由此得一步转移概率矩阵尸= ( 仇) = 口o口i a o口l 0 口o 0o d 2q 。 口2码 口1g 2 口oq 。 ( 2 1 1 3 ) 由转移矩阵p 可知， m 是一个齐次马尔可夫链，且非周期不可约，当p ：兰 o ) 。进一步假定修理 时间r 与上述部件故障的规律是相互独立的，故障部件修复后与新部件一样。下 面对基本模型求其系统可用度。先令 刖出= p t y t + a t 眇归涨 ( 2 2 2 ) 由上式易证 1 - g ( t ) = e x p - f a ( y ) d y o ( 2 2 3 ) f 。 g ( f ) = ( f ) e x p - f a ( y ) d y 0 由于部件修理时间】，遵从一般分布， ( r ) ，r20 ) 不是马尔可夫过程。例如， 当知道时刻t 系统中有一部件故障，即知道n ( t ) = 1 ，时刻t 以后系统发展的概率 规律还不能完全确定下来，时刻t 以后系统发展的概率规律不仅依赖于时刻t 有 几个部件故障，还依赖于正在修理的部件在时刻t 以前已经修理了多长时间。 我们引进一个补充变量x ( t ) ：当n ( t ) = l 或2 时，x ( t ) 表示时刻t 正在修理 的部件已经修理过的时间；当n ( t ) = 0 时，没故障部件的修理，x ( t ) 可以不考虑。 这样过程 ( f ) ，z ( f ) ；r 0 是一个连续时间二维的广义的马尔可夫过程，即在任 意时刻t ，当给定n ( t ) 和x ( t ) 的具体值，则过程 ( f ) ，z ( f ) ；r 0 ) 在时刻t 以后 的概率规律与时刻t 以前该过程的历史无关。对t 0 ，x 0 ，令 f r ( r ) = p ( ( r ) = o ) p t ( t ，x ) d x = p n ( t ) = l ，x x ( f ) x + 出)( 2 2 4 ) 【p a t ，x ) a x = p ( f ) = 2 ，x x ( t ) x + 西c ) 假定时刻t = 0 时，两个部件都是好的，即初始条件是 昂( o ) = 1 ，且( o ，工) = 只( o ，x ) = 0 ( 2 2 5 ) 由( 2 2 4 ) 可导出如下方程组 罢r ( f ) = 一九晶( f ) + p ( f ，x ) ) d x ( 2 2 6 ) 1 0 江苏大学硕士学位论文 昙置( t , x ) + 昙e ( t , x ) = _ + ( x ) 】只( f ，x ) ，0 工 o o ( 2 2 7 ) o t 苏 詈只( f ，卅昙t a t , x ) = 叫 ) p z ( t , x ) + & e d t , x ) ，o 0 ，必须u ( t ) = 2 ，s ( t ) = x ，且在 ( f ，t + 出】内部件的修理没有完成；或者( r ) = l ，工( f ) = x ，且在( f ，t + f 】内一个 部件发生故障，因此 只( f + a t ，x + a t ) = 最( f ，x ) 1 一4 x ) a t 】+ p i ( r ，x ) f + o ( a t ) l i p ( 2 2 8 ) 式。 4 ) 为使n ( t + f ) = 1 ，0 x ( f + 出) 出，必须n ( t ) = 0 ，且( f ，r + 址】内一个部件 发生故障；或n ( t ) = 2 ，x ( t ) 为某正值x ，并且在( r ，t + a t 】内正在修理的部件修 理完成。因此 只o + 出，o ) r = n ( f + 血，y ) a y = p o ( t ) & a t + f 最( f ，x ) ( x ) a t d x + 。( f ) 江苏大学硕士学位论文 即( 2 2 9 ) 式。 5 ) ( 2 2 1 0 ) 式是由于( f ) = 2 和x ( t ) = 0 不可能同时发生。 6 ) ( 2 2 1 1 ) 式是由于全概率公式。 为解这个方程，对( 2 2 6 ) - - ( 2 2 “) 的两端做l 变换，用初始条件( 2 2 5 ) ，得 巴 蟛( j ) 一1 = 一凡昂( s ) + l 暑( j ，工) ( x ) a k ( 2 2 1 2 ) i 嵋o ，工) + 导只( s x ) = _ + ( x ) 】鼻( 品x ) ，( o x ) ( 2 2 1 3 ) “ 墨巧( s ，工) + 旱，? ( s ，工) = 一( x ) 尸? ( s ，x ) + 只( s ，x ) ，( o x o o ) ( 2 2 1 4 ) 丑o ，o ) = 厶只( s ) + f 鼍( 只工) o ) d x ( 2 2 1 5 ) 巧( s ，0 ) = 0 巧(s)+n(s，x)出+应(是z)出2专00 这是一组关于x 的微分积分方程。由( 2 2 1 3 ) 口7 解得 只( s ，x ) = 只+ ( s ，o ) e 一5 + 4 p 【1 一g ( x ) 】 代入( 2 2 1 2 ) 得 童蜀( s ) 一1 = - 2 0 p o ( s ) + p l 。o ，o ) p 一” p 1 一g ( x ) ( x ) d x = 一，k 昂( s ) + 只( j ，o ) g 0 + ) 其中g ( s ) = p 一“a g ( x ) = p “g o ) a x ，解得 驰m 。聊孚+ 击 ( 2 2 1 4 ) 可改写为 导只( s ，x ) + s + ( z ) 只( s ，z ) 一 只( s ，z ) = 0 d x - jd + u ( y ) l d y扣+ ( ：】1 出 解得巧( s ，工) = 口。 巧( s ，0 ) + i 鼻。( s ，y ) p 。 咖 ( 2 2 1 6 ) ( 2 2 1 7 ) ( 2 2 1 8 ) f 2 2 1 9 ) 江苏大学硕士学位论文 将( 2 2 1 6 ) 和( 2 2 1 8 ) 式代入，得 巧( 蹦) = e - 1 一g ) 1 4n ( s ，0 ) e - 4 y a i v = 只( s ，0 ) 1 - g ( 工) f “( 1 - p 一如) ( 2 2 2 0 ) 将( 2 2 1 8 ) ( 2 2 1 9 ) ( 2 2 2 0 ) 代入( 2 2 1 7 ) ，有 解得 讹气导字+ 击啪聊即州肛 吼如) = 面万福音丽f 而( 2 2 2 1 ) ( 如果将( 2 2 1 8 ) ，( 2 2 1 9 ) 乘1 ( 2 2 2 0 ) 代k ( 2 2 1 5 ) 同样可得( 2 2 2 1 ) 式) 。将 ( 2 2 2 1 ) 代k ( 2 2 1 8 ) ，( 2 2 1 9 ) y ( 1 3 ( 2 2 2 0 ) ，可得 c o ( 垆毒等等等 牝垆而等署希丽 亿z 忽， 啪= 毒蠕警 系统的瞬时可用度是 4 ( f ) = e o q ) + n ( f ，x ) a x o 作l 变换，并将( 2 2 2 2 ) 式代入，得 4 o ) = i e “a ( t ) a t = t o ( s ) + f 只( s , x ) d x 00 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 5 3 年和1 9 8 9 1 3 0 1 年出版的两本专著中作详细阐述。该方法 主要从计算概率的角度解决随机模型研究中的数值计算问题，其突出特点在于用 该方法得出的结果均以矩阵形式给出，便于在计算机上进行计算。而传统的嵌入 马尔可夫链方法所得结果均以l a p l a c e 变换或母函数的形式给出。因此矩阵解析 方法是研究随机模型的一种有效的和重要的方法。 江苏大学硕士学位论文 定义考虑一个二维马尔可夫过程 z ( f ) ，s ( o ) ，状态空间是 q = ( 七，) ，k o ，1 s _ ，脚 ，称 z ( f ) ，( ，) 是一个拟生灭过程，如果其生成元可 以写成下列分块三对角形式。 q = 4c o b a c ba c b 4 其中所有子块都是m 阶方阵，满足 c 4 0 + c o ) e = 。+ a + c k = 佃+ 4 + c k = o 4 和4 有负的对角线元素和非负的非对角线元素，其余子块均是非负悻，e 是元 素全为l 的列向量。称状态集( k ，1 ) ，( k ，2 ) ( k ，m ) 为水平k 。若过程是正常返的， 以 ，j 表示过程 x ( f ) ，( ，) 的极限变量，并记 万。= l i m p x o ) = 七，t ) = ， = p = 七，j = ， 其中k o ，1 _ ，m 。为适应q 的分块形式，将稳态概率按水平写成分段形式 巩一防”巩2 ，万h j i 0 拟生灭过程是经典生灭过程从一维状态空间到多维状态空间的推广，正如生灭 过程的生成元具有三对角形式一样，拟生灭过程的生成元是分块三对角阵。从2 0 世纪8 0 年代到9 0 年代田乃硕等 3 3 ，5 4 ，5 5 ，5 6 把n e u t s 的矩阵几何解方法引入到休假 排队模型中，促进了多服务台休假排队系统的研究，并且初步建立起多服务台休假 中以条件随机分解为核心的理论框架，为经典排队论的发展和应用开辟了更为广阔 的前景。 1 4 江苏大学硕士学位论文 第三章带有负顾客且具有反馈的m g 1 排队模型 g e l e n b e 在上个世纪9 0 年代首次提出了负顾客的排队模型 1 。负顾客可以 看成是某些工作的外来援助或取消信号，一般作为系统的制约因素而存在，能抵 消系统中的正顾客。之后，国内外学者掀起了对带有负顾客的排队模型的研究风 潮。关于负顾客的排队模型的成果不断涌现 3 ，7 ，1 9 】。有不少文献研究了具有反 馈的排队模型 2 0 ，2 5 ，3 3 】。这类排队模型的特点是：顾客被服务完会以概率1 一盯继 续留下等待服务，以概率盯( o 盯1 ) 离开系统。本章考虑了这样带有负顾客且具 有反馈的排队模型，这一类的排队现象在日常生活中有许多相应的例子：如在通 讯系统中，数据传输到接受台，数据传输看成正顾客的到达，外来的干扰信号看 作负顾客的到达，当接受台发现数据传输错误时，数据会被要求反馈再次传输； 又如在商场中，通常的顾客看成正顾客，其他商家的诱惑等因素看成负顾客，正 顾客服务完会以一定的概率反馈接受售后服务。本章把负顾客和反馈结合起来， 研究了三类负顾客的m g 1 排队系统，分别是：抵消策略为负顾客抵消队尾的正 顾客的排队系统( r c e ) ；抵消规则为负顾客抵消队首的正顾客的排队系统 ( r c h ) ；以及负顾客抵消队首的正顾客且服务台可修的排队系统。 3 1负顾客的抵消策略为r o e 的m g 1 排队模型 3 1 1 模型的数学描述 正负顾客各自以到达率为刀，刀的p o s s i o n 流独立到达，负顾客到达时，若 系统空闲则自动消失，若系统中有正顾客，则抵消队尾的正顾客，负顾客不接受 服务，正顾客每次服务完后以概率l 一盯立刻排到队尾等待下一次服务，而以概 率c r ( o 仃1 ) 立刻离开系统，永不再来，若设孝为一个正顾客的总的服务次数， 则孝服从参数为口的几何分布，即- - g e o ( 盯) 正顾客的服务时间有一般分布函数 b ( t ) ，相应的密度为b ( t ) ，风险率函数为( r ) ，且b ( f ) = 1 - 口一j 。川砷6 。 顾客的到 达间隔与服务时间相互独立。 令n ( t ) 表示t 时刻系统中的正顾客数，显然 ( f ) ，t 0 不是马尔可夫过程， 江苏大学硕士学位论文 引入补充变量：x ( t ) 表示服务中的正顾客已接受的服务时间，则 ( r ) ，x ( f ) ，f 0 ) 是一个马尔可夫过程。 定义p k ( t ) = p ( n ( t ) = 彘) ，( j | = 0 , 1 ，2 ，) 最( f ，x ) d x = p ( ( f ) = k , x x ( f ) 工+ 西c ) ，( 七= 0 , l ，2 ，) 最2 熙p ( ( f ) 2 州女2 0 , 1 2 。) 记旯= + 万a ( z ) = 旯一z 一万z 一1 3 1 2 状态转移方程 ( i ) 状态( 0 ，t + h ，0 ) 由如下状态到达： ( 0 ，t ，0 ) 无正顾客到达，发生概率1 一厅+ o ( h ) ( 1 ，t ，x ) 正顾客接受服务完离开系统或有负顾客到达，发生概率 ( ( 巧“( x ) + 五一) 矗+ d ( 矗) 有方程p o ( t + h ) = p o ( t ) ( 1 - a + 厅) + f e , ( t , x ) ( c 日“( x ) + a ) h d x + 。( ) 两边同除h ，并令h 0 得 ( 丢“= f 即，坝掣( 咖矿) a x ( 3 1 1 ) ( i i ) 状态( 1 ，t + h ，0 ) 由如下状态到达： ( 0 ，t ，0 ) 有正顾客到达，发生概率2 + h + o ( h ) ( 2 ，t ，x ) 一正顾客服务完且离开系统，发生概率c r 4 x ) h + d ( ) 有方程p l ( t + h ，o ) 厅= 晶( f ) 五+ + f 昱( f ，工) 。 ) h d x + 。( ) 即 丢驰) “撇p o ( ) + f e ( t , x ) o z ( 蛐 ( 3 1 2 ) ( i i i ) 状态( k ，t + h ，0 ) 由如下状态到达： ( k + l ，t ，x ) 一正顾客服务完且离开系统，发生概率a u ( x ) h + o ( h ) 有方程只o + 向，o ) | i 2 = f 最+ 。( t , x ) c 7 4 z ) h d x + 。( ) 即 5 ( t ，o ) = f 掣( x ) 最+ 。( t , x ) d x ( k = 2 ，3 ”) ( 3 1 3 ) ( i v ) 状态( 1 ，t + h ，x + h ) 由如下状态到达： ( 1 ，t ，x ) 无正负顾客到达且服务未完成或服务完成且继续留下接受服务， 1 6 江苏大学硕士学位论文 发生概军1 一( 旯+ + 五一+ ( x ) ) a + ( 1 一c r ) t ( x ) h + d ( 向) = 1 一( 旯+ o 弘( x ) ) + d ( 厅) ( 2 ，t ，x ) 有负顾客到达，发生概率万 + d ( ) 有方程只( r + ，z + h ) = p 2c t ，x ) a - h + p l ( t ，工) 1 一( 五十c _ “( x ) ) 矗 + o ( ) 即 ( 昙十昙+ 五+ c 弘( x ) ) 置o ，z ) = a p 2 ( t , x ) ( 3 1 4 ) o t 优 ( v ) 状态( k ，t + h ，x + h ) 由如下状态到达： ( k - 1 ，t ，x ) 有正顾客到达，发生概率2 * h + o ( h ) ( k ，t ，x ) 无正负顾客到达且服务未完成或服务完成且继续留下接受服务，发 生概率1 一( 五+ 掣( j ) ) + d ( ) ( k + l ，t ，x ) 有负顾客到达，发生概率2 - h + d ( ) 有方程最( r + 厅，z + h ) = 最一i ( r ，x ) a + h + 丑+ l ( f ，x ) 五一h + 置 ( f ，x ) 【1 一( 五+ a u ( x ) ) h 】+ d ( ) 即( 昙+ 昙+ 旯+ 哪z ( x ) ) 最( f ，x ) = 圪一i ( f ，曲+ 万足“( f ，x ) ( k = 2 ，3 ) ( 3 1 5 ) o t 盘 初始条件 p o ( o ) = 0 只( o ，x ) = 0 并且有正规化方程 c o ( f ) + 岁 f p k ( t , x ) d x = 1 命题该系统存在稳态分布的充分必要条件是 o 。：塑旦：! ：! 坠型翌望二兰堡丝 1叭i6 ) o o 作和，有 雹( s ，0 ，z ) = f 。o ) q o ，z ，z ) 出+ r 舅o ) z + ( z ：一z s ) 巧( s ) 式( 3 1 1 2 ) x d 4 x ) ，并取积分得 f 。弘( x ) q + ( 了，z ) d x = q ( j ，0 ，z ) 足( 只z ) 一才f o ，z ) 1 8 d 研 缈 劲 哆 朋 ， 蛐 坳 聊 0 p 儿 。 。 o 0 0 江苏大学硕士学位论文 其中 k ( 5 ，z ) = f 。( z ) e 巾州功。( 雪( x ) ) 4 d x 解得 r ( 蹦) - r 掣( x ) e 巾州瑚。( 雪( 工) ) 4 ，。( s , x , z ) d x q ( j ，o ，z ) ：( 2 + z