（应用数学专业论文）带有负顾客的可修排队模型.pdf

江苏大学硕士学位论文 摘要 本课题主要研究了三类带有负顾客的可修排队系统。先考虑了一类 带有负顾客且具有反馈的m c 1 可修排队系统，正顾客每次服务完后 以概率p 离开系统，而以概率1 - p 立刻排到队尾继续接受服务，负顾 客抵消中间顾客。接着又考虑了一类具有两种故障状态的( 正常和异 常) 负顾客m g 1 可修排队系统，其中正常故障状态是由于服务台的 寿命终止而引起系统失效；异常故障状态是由于服务员操作失误等其 他原因而造成系统失效。最后研究了具有灾难到达且具有反馈的 m g 1 可修重试排队系统，服务台可能出现两种故障状态。我们主要 运用补充变量法和状态转移方程及l 变换分析法，得到了一些排队指 标和可靠性指标。 关键词：负顾客，反馈，重试，可修排队系统，队长，可靠性，补充 变量法 江苏大学硕士学位论文 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 h r e ek i n d s o fr e p a i r a b l eq u e u e i n g s y s t e mm g 1w i t hn e g a t i v ec u s t o m e r s w ef i r s tc o n s i d e rt h eo n ek i n di s m g 1r e p a i r a b l eq u e u e i n gs y s t e mw i t hn 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 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 et h eq u e u ea t t 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 f1 - pa n dt h e n 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 ri nt h em i d d l eo ft h e q u e u e i n gs y s t e m t h e nw ea l s oc o n s i d e rt h er e p a i r a b l eq u e u e i n gs y s t e m m g 1w i t h n e g a t i v e c u s t o m e r sa n dt w ok i n d so fb r e a k d o w n s t a t e s ( n o r m a la n da b n o r m a l ) n o r m a lb r e a k d o w ni sc a u s e db yt h el i f e t e r m i n a t i o no fs e r v i c es t a t i o na n da b n o r m a lb r e a k d o w nr e s u l t sf r o mt h e o p e r a t i o nl a p s e a tl a s t ，w es t u d yt h em g 1r e p a i r a b l eq u e u e i n gs y s t e m w i t h c a t a s t r o p h e s a n d r e t r i a l ，t h e s e r v i c es t a t i o n m a yo c c u rt w o b r e a k d o w ns t a t e s b yu s eo ft h es u p p l e m e n t a lv a r i a b l e sm e t h o d ，s t a t e t r a n s f e ra n a l y s e sa n dlt r a n s f o r m ，w ed e r i v e q u e u e i n gi n d e x e sa n d r e l i a b i l i t yi n d e x e s k e y w o r d s ：n e g a t i v ec u s t o m e r s ，f e e d b a c k ，r e t r i a l ，r e p a i r a b l eq u e u e i n g s y s t e m ，q u e u e i n gl e n g t h ，r e l i a b i l i t y , s u p p l e m e n tv a r i a b l e m e t h o d 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存和汇编本学位论文。 保密口 本学位论文属于，在年我解密后适用本授权书。 不保密i z i 学位论文作者签名：砌、杰、 指导教师签名： 硼年瑚，7 日君年2 月1 7 日 独创性申明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容以外，本 论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本 文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：剁、疥 日期：飙湃，2 月7 日 江苏大学硕士学位论文 1 1排队论发展简介 第一章绪论 排队论又称随机服务系统，源于e r l a n g 关于电话服务的研究，是专门研究 由于随机因素的影响而产生拥挤现象的科学，第二次世界大战以后得到迅猛的发 展，并且发展成为运筹学的一个重要分支。它通过研究各种服务系统在排队等待 中的概率特性，来解决系统的最优设计和最优控制。排队论最早可追溯到上个世 纪，在上世纪初，丹麦数学家、工程师爱尔朗将概率论方法用于电话通话问题， 从而开创了排队论这门学科的先河。之后的几十年时间里排队论的理论得到迅速 发展，并逐步趋于成熟。其文献数以千计，特别在计算机技术迅猛发展的同时， 排队论的发展更是日新月异，应用领域也不断扩大。它适用于一切服务系统，特 别在通信系统、交通系统、计算机系统、存储系统和生产管理系统，大规模生产 线的设计与优化等方面应用广泛。 2 0 世纪3 0 年代中期，当费勒( w f e l l e r ) 引进生灭过程时排队论才被数学 界承认为一门重要的学科。2 0 世纪5 0 年代初肯德尔( d g k e n d a l l ) 对排队论 作了系统的研究，他用嵌入马尔可夫链( m c ：m a r k o vc h a i n ) 方法研究排队模型， 使排队论得到进一步发展。他首先引进经典排队中较为方便的记号，如m g 1 表 示泊松到达、一般服务、一个服务台、无限等待空间的排队系统。2 0 世纪6 0 年 代起，排队论研究的课题日益复杂，很多问题很难求得其精确解，就是求得的解 也非常复杂，不便于应用，因而丌始了近似方法的研究。排队论的产生与发展来 自于实际的需要。实际的需要也必将决定它今后的发展方向。 排队系统由顾客和服务台构成，其中顾客是被服务的对象，服务台是进行服 务的设备。排队系统有三个组成部分：输入过程、排队规则及服务机构。输入过 程是描述顾客的来源及顾客是按怎样的规律抵达排队系统的；排队规则有先到先 服务、后到先服务、随机服务和有优先权的服务；服务机构主要是指服务台的数 目，进行服务时服务的方式是并行还是纵列，接受服务的顾客是成批的还是单个 的，服务时间服从什么分布，顾客们接受服务的时间是否独立。反映排队系统的 主要特征有瞬态与稳态系统的队长、顾客在系统中的等待时间( 逗留时间) 、忙 江苏大学硕士学位论文 期等。 自排队论这门学科形成以来，新的研究方向和研究方法层出不穷。大量的科 研工作者在此领域取得了丰硕的成果。排队论专家田乃硕等把矩阵解析法引入 g i m 1 型休假排队系统，并研究了部分服务台同步休假的排队模型，极大丰富 了排队模型的理论；史定华将频度转移法用于可修服务系统并且对可靠性作了大 量工作；g e l e n b e 将负顾客引入排队系统等。当前，排队论的研究主要集中在排 队网络、矩阵解析法、数值计算、极限定理以及特殊模型等方面。其中特殊模型 主要是研究具有实际应用背景的满足特殊需要的有一定假设前提的排队模型，而 多个服务阶段排队、重试排队以及由这两方面衍生的一些具有多个服务阶段的重 试排队模型和具有反馈的重试排队模型是特殊模型研究的几个重要方面。关于排 队论的研究方法，主要有：e r l a n g 的阶段化，k e n d a l l 的嵌入马氏链，k o s t e n 和c o x 的补充变量，n e u t s 的矩阵解析方法，史定华的向量马氏过程和频度转移 法。由于排队论研究的课题日趋复杂，很多问题难求精确解，因此近似方法的研 究正逐步深入。 1 2 负顾客的排队模型的发展及研究现状 负顾客的排队模型是排队论的一个新兴分支。负顾客或者是一次误操作或者 是外来对服务台实施服务援助或者是系统的灾难，其主要作用是抵消系统中通常 的顾客正顾客。负顾客的抵消作用按抵消时刻、抵消策略的不同对系统产生 不同的影响。抵消时刻可分为两类：一类是负顾客到达后立即抵消系统中现有的 正顾客；另一类是负顾客仅在服务结束时刻抵消现有的正顾客。抵消策略可分为： 抵消队首正在接受服务的顾客( r c t t ) , 抵消队尾的顾客( r c e ) ；抵消整个系统的 顾客( d s t ) 以及随机数量的抵消。 g e l e n b e 最早将负顾客引入排队模型。首先，在文 1 中作者建立了一个神 经网络模型，负顾客抵消排队系统中的一个正顾客，就像是一个“i n h i b i t o r s i g n a l ”。此理论用途广泛，比如随机神经网络、生产系统和推论性的平行性领 域等。接着，在文 2 中g e l e n b e 又讨论了马尔可夫排队的稳定性，特别对负顾 客的抵消规则r c e 和r c h 进行了比较；在文 3 中又讨论了马尔可夫排队网络， 其中有负顾客的到达以及顾客从一个服务台到另一个服务台可能成为负顾客的 2 江苏大学硕士学位论文 情况，得到了一个乘积形式解。这类工作又被拓展到了有多类顾客和负顾客对正 顾客进行群抵消等情况。w h e n d e r s o n 首次在文 4 中提出了负顾客队长的概念。 之后，负顾客的排队模型引起了广大科研工作者的广泛兴趣。 关于最典型的m 6 1 排队模型，许多学者对此都做了研究。首先，h a r r i s o n 和p i t e l 在文 5 中得到了m m 1 排队模型中逗留时间的l 变换，其中负顾客也 以p o i s s o n 流到达。接着，在文 6 中h a r r i s o n 和p i t e l 讨论了有负到达的m g 1 排队模型，得到了不同服务规则和抵消规则下的系统稳态队长分布的概率母函数 及平均队长。其中在策略为f c f s - r c e 系统中引出了第一类f r e d b o l m 积分方程； 在策略为l c f s - r c h 系统中，作者运用了补充变量法，对稳态条件下的系统状态 转移概率进行分析，获得了结论；对其余具有不同的服务规则和抵消规则的系统， 作者也作了讨论。j a i n 和s i g m a n 在文 7 中分析了负到达抵消目前系统中的所 有顾客的情形，根据比率守恒律，得到了该系统的载荷量分布类似的 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 在文 8 中研究了负顾客 抵消随机数量的正顾客的m g 1 排队模型，作者利用两种不同的方法来研究稳态 系统的载荷量。b a y e r 和b o x m a 在文 9 中讨论了负顾客的m g 1 排队模型的 w i e n e r h o p f 分析和随机徘徊问题，得到了嵌入点时刻和任意时刻的队长分布的 概率母函数。在求嵌入点时刻的队长时，文章考虑两种情形：一类是系统空时， 负到达自动消失；一类是系统空时，负到达停留在系统中，直到下一次服务结束 时才去抵消正顾客，分别得到了各自队长分布的概率母函数。a r t a l e j o 和c o r r a l 的文 1 0 中的独到之处在于考虑当正顾客不存在时，到达的负顾客进入一个特殊 的轨道，然后当有正顾客到达时再去抵消，并且是重复请求的排队系统。作者证 明了稳态队长分布仍能满足第一类f r e d h o l m 积分方程，并给出了一个有效的第 一类f r e d h o l m 积分方程的迭代解法。v l a d i m i rv a n i s i m o v 和j e s u s r a r t a l e j o 在文 1 1 中考虑有负顾客的多服务台再试排队模型。负顾客作为阻止系统超负荷 的一种控制措施，其控制策略为：当服务台被全占用时，负指数时间内系统是正 常工作的：但若时间超过后服务台仍是满的，那么有随机数量的正顾客被抵消。 朱翼隽在文 1 2 中创造性地提出了负顾客可以接受服务的思想，研究了一类服务 规则为f c f s 抵消规则为r c e 的负顾客的m g 1 排队模型，得到了队长分布的概 率母函数、虚等待时间及等待时间的l 变换表达式。文 1 3 的作者运用补充变量 3 江苏大学硕士学位论文 法，对具有负顾客的m g 1 可修排队模型进行了研究，得到了各自队长分布的广 义概率母函数。文 1 4 的作者还将负顾客引入休假排队系统，研究了具有负顾客 的m g 1 和g i m 1 休假排队模型，分别得到了系统队长的概率母函数，大大丰 富了负顾客排队模型的理论体系。 1 3 可修排队模型的研究发展 我们一般研究的排队系统都是假定服务台是不会发生故障的，但在实际生活 中却经常碰到服务台发生故障而不能为顾客服务的情形。此时需要修理工人对发 生故障的服务台进行修理( 或更换) ，修理完成后再继续为顾客服务，我们把这 类服务台可能发生故障且可修复的排队系统统称为可修排队系统。显然可修排队 系统是从服务台的性能角度提出来的，与休假排队系统有很大的差别，而且人们 对这类可修排队系统又提出了新的研究课题，即不仅要研究系统的排队问题，同 时还要研究因故障而产生的可靠性问题，例如系统的可用度和故障频度等。因此， 对可修排队系统，无论是从排队论的角度，还是从可靠性理论的角度都是非常值 得研究的。早在1 9 6 2 年a v i - i t z h a k ，b 和n a o r ，p f ”1 ，1 9 6 3 年t h i r u v e n g d a n ，k t l 6 1 就研究了服务台易坏的一些排队问题，利用补充变量的方法讨论一些有用的排队 指标。在随后的二十年里关于服务台可能发生故障的文章也有很多 文献1 7 1 9 ，但是他们研究的问题仅限于系统的一些排队性指标，直到1 9 8 2 年，我国的 曹晋华和程侃两位老师 文献2 0 真正的从可靠性的角度全面地分析了一些有用 的可靠性指标，例如：系统首次完全恢复时问的分布，服务台首次失效时间分布， 时刻t 服务台失效的概率，( 0 ，t ) 中服务台平均失效次数等等。以后关于服务 台可修的排队模型都分析了可靠性指标。关于服务台可修的排队系统的文章中， 人们不但讨论其排队指标而且也从可靠性角度对其分析，许多复杂而且实用的排 队模型应运而生。 1 。4 本课题的研究内容和组织结构 本课题主要研究带有负顾客且具有反馈的m g 1 可修排队系统，具有两种故 障状态的负顾客m g 1 可修排队系统及具有灾难到达且具有反馈的m g 1 可修重 4 江苏大学硕士学位论文 试排队系统。借助于研究排队模型的常用方法“补充变量法”及“嵌入马氏链方 法 ，得到了所需的排队指标。 本课题分为五章，第一章为绪论，介绍排队论的发展简史，负顾客排队和可 修排队系统的研究现状和发展。第二章给出了排队模型研究的主要方法，介绍研 究排队模型的三种常用方法。第三章研究了一类带有负顾客且具有反馈的m g 1 可修排队系统，负顾客抵消排队系统中的中间顾客( r c m ) 。使用补充变量法分析 该模型，得到了这一模型的排队指标和可靠性指标，并且发现此类排队系统完全 取决于队长为2 的概率。第四章研究了一类具有两种故障状态的负顾客m g 1 可修 排队系统，使用补充变量法得到了这一模型的排队指标和可靠性指标。第五章研 究具有灾难到达且具有反馈的m g 1 可修重试排队系统，服务台可能出现两种故 障状态，仍然使用补充变量法得到了这一模型的排队指标和可靠性指标。 5 江苏大学硕士学位论文 第二章排队模型研究的主要方法 排队论是运筹学的重要分支，也是应用概率论的重要组成部分。它的基础是 概率论和随机过程。排队论已经发展了近一个世纪，形成了一系列较成熟的研究 方法，取得了丰富的成果。下面简单介绍几种常用的研究排队模型的方法。 2 1 嵌入马尔可夫链法 在泊松到达与服务时间为负指数分布的排队系统中，在任何时刻系统都具有 马尔可夫性质，因而可用连续参数马尔可夫链的方法化成可求解的平衡方程组， 得到系统的平稳解。对于一般服务或一般到达的排队系统，不是在任何时刻系统 都具有马尔可夫性质，只是在某些特殊的随机时刻系统才具有这种性质，我们称 这种随机时刻点为再生点，即从这个时刻起，好像又重新开始一样。利用再生点， 一般服务或一般到达的排队系统的分析，用马尔可夫链的方法予以解决，这种方 法就叫做嵌入马尔可夫链法。徐光辉 2 1 1 ，孟玉珂2 引，唐应辉唐小我2 3 1 ，陆传 赉】，华兴1 2 5 1 ，孙荣恒李建平【2 6 1 ，对此做了详细的论述。以下我们先说明马尔 可夫链并以经典的m c 1 排队系统为例，说明用嵌入马尔可夫链的方法来解决排 队问题的主要思路。 定义2 1 1 设随机过程忸( f ) ，t 丁 的状态空间s 为r 中的可列集，如果对 t 中任意，z 个 f 2 0 ) 由于到达流是 p o i s s o n 流，在这些再生时刻，观察系统的状态顾客数，它具有马尔可夫性。 n 。表示一个顾客服务结束后刚离开系统时留在系统中的顾客数，则 。) 就是一 个马尔可夫链，这叫原系统状态( f ) 的嵌入马尔可夫链。由于t 叶。一t 。对一切n 都是同分布的，到达又是p o i s s o n 流，于是经过乙+ 。一乙这段时间，系统从状态虬 到。+ 三一1 状态的概率相同，因此是一个齐次马尔可夫链。为求得此马尔可夫 链的平稳分布，首先应求出转移概率。 2 1 2 转移概率矩阵 用一顾客服务结束后离开系统时的队长作为系统的状态，因此系统的一步转 7 江苏大学硕士学位论文 移就是一个顾客离开系统到下一个顾客离开系统这段时间系统状态的变化。 设服务时间v 的密度函数为b ( t ) ，平均服务时间为 q 吲= 万1 = f 咖( f ) 疵 ( 2 1 1 ) b ( t ) 的l 变换记为b + ( s ) ，即b + ( s ) = f e - t b ( t ) d t ( 2 1 2 ) 其中要求r ( s ) o ，即s 的实数部分大于零。 再设尸= ，c 。：表示进入系统的第，z 个顾客，t 。：表示c 。服务完离开 系统的时刻，n 。：表示c 。离开系统后留下的队长，k ：表示c 。的服务时问， 八：表示c 。的服务时间k 内到达系统的顾客数。 由定义知 k ) 是独立同分布的随机变量序列，分布密度为b ( t ) ； 丸) 是独立 同分布的随机变量序列，概率分布记为 口。 。 为了求得一步转移概率p 盯，需先求 的概率分布 口。 。 而a t 三p = k ) ( 2 1 3 ) 由于服务时间k 是随机的，事件 = k ) 表示在第，z 个顾客c 。的服务时间k 内 以p o i s s o n 流到达霓个顾客，而o 吒 0 0 。若k = t ，说明( 0 ，t ) 内到达露个 顾客，而f ( o ，) 。因此应该用连续时间的全概率公式求口。，即 口女= r p = 七i k ：t ) b ( t ) d t ( 2 1 4 ) 取叫k - f ) = 警p 埘 ( 2 1 5 ) 从而口。= j o 号告础6 ( f ) 出，( 。七 0 时，服务台立刻接受顾客g + 。进行服务。服务时间为圪卅。这段时间达到 的顾客数为a 川。c 枷服务结束离开系统时，系统内有顾客数n 州= n 。+ 4 州一1 。 若。= 0 ，则c 。离开系统后，系统内无顾客，服务台处于空闲状态，这时c 州还 未到达。g + 。到达后立刻接受服务。 c n + 。接受服务时间内到达4 + 。个顾客。因 此c 槲服务完离开系统时留下的队长，+ 。= a 枷。因此从时刻f 。到时刻，州顾客转 移为 ”艮以+ 1 1 ：笺 叫 设p l f = p ( 槲= 川以= f ) 当i = 0 时，p o ，= p + l = i in 。= o ) = 尸( a 槲= j ) = 口 ( 2 1 1 1 ) 当i 1 时，p ，= p ( 州= j in 。= i ) = p ( 。+ a + l - 1 = j i 。= f ) 9 江苏大学硕士学位论文 = e ( a 。+ l = j i + 1 ) = 口一l + l ，( _ ，i 一1 ) ( 2 1 1 2 ) 由此得一步转移概率矩阵p = ( p 矿) = a o8 l 口2 d oa l a 2 0 口o a l 00 a o ( 2 1 1 3 ) 由转移矩阵p 可知， 。 是一个齐次马尔可夫链，且非周期不可约，当p ：兰 1 时，这个马尔可夫链是遍历的，因此平稳分布存在。状态转移图如图2 1 所示 2 1 3 平稳分布 图2 1m g 1 嵌入马尔可大链状态转移图 我们已指出当p 0 ) 。进一步假定修理 时间y 与上述部件故障的规律是相互独立的，故障部件修复后与新部件一样。下 面对基本模型求其系统可用度。先令 心舻科汉y h 郇” 2 嵩 ( 2 2 2 ) 由上式易证 f 1 一g ( f ) = e x p 一i z ( y ) d y o ( 2 2 3 )、， g ( t ) = z ( t ) e x p 一l ( y ) 匆】 o 由于部件修理时间y 遵从一般分布，州o ) ，t 0 ) 不是马尔可夫过程。例如， 当知道时刻t 系统中有一部件故障，即知道( f ) = 1 ，时刻t 以后系统发展的概率 规律还不能完全确定下来，时刻t 以后系统发展的概率规律不仅依赖于时刻t 有 几个部件故障，还依赖于正在修理的部件在时刻t 以前已经修理了多长时间。 我, f r i l l 进一个补充变量x ( t ) ：当n ( t ) = 1 或2 时，x ( t ) 表示时刻t 正在修理 的部件已经修理过的时问；当o ) = 0 时，没故障部件的修理，盖( f ) 可以不考虑。 这样过程 ( f ) ，x ( f ) ；，0 ) 是一个连续时间的广义的马尔可夫过程，即在任意时 刻t ，当给定( f ) 和x ( f ) 的具体值，则过程 ( f ) ，x ( f ) ；f 0 ) 在时刻t 以后的概 江苏大学硕士学位论文 率规律与时刻t 以前该过程的历史无关。对f 0 ，x 0 ，令 f 蜀p ) = 曩( f ) = 田 只o ，x ) a x = p ( f ) = 1 ，x x ( r ) x + a x ( 2 2 4 ) i b o ，功出= p j v ( t ) = 2 ，x x ( t ) x + d x 假定时刻t = o 时，两个部件都是好的，即初始条件是 只( 0 ) = 1 ，只( 0 ，功= 最( o ，矽= 0( 2 2 5 ) 由( 2 2 4 ) 及状态转移情况可导出如下方程组 丢郫) 一厶郫) + p ) 刖出 ( 2 2 6 ) 昙弓( f ，功+ 昙 ，z ) = _ 【五+ ( 砷懈o ，x ) ，o x ( 2 2 7 ) 昙最( f ，功+ 昙最( 岛功= 一t ( x ) p 2 ( t ，x ) + 置o ，x ) ，o 0 ，必须o ) = 2 ，x ( f ) = x ， 且在( f ，t + & 】内部件的修理没有完成；或者( f ) = 1 ，x ( f ) = x ，且在( f ，t + a t 内 一个部件发生故障，因此 最o + a t ，石+ a t ) = 最( f ，力【1 一4 功a t 】+ p l o ，x ) & a t + o ( a t ) 即( 2 2 8 ) 式。 ( 4 ) 为使o + a t ) = 1 ，0 x ( t + & ) a t ，必须( f ) = o ，且o ，t + a t l 内一 个部件发生故障；或( f ) = 2 ，x ( f ) 为某正值x ，并且在o ，t + a t 内正在修理的部 件修理完成。因此 a t p , ( t + a t ，0 ) a t = 仁p + & ，y ) d y = p o ( t ) a o a t + j 只( 船) 4 x ) a t d x + 。( & ) 00 即( 2 2 9 ) 式。 ( 5 ) ( 2 2 1 0 ) 式是由于( f ) = 2 和x = 0 不可能同时发生。 ( 6 ) ( 2 2 1 1 ) 式是由于全概率公式。 为解这个方程，对( 2 2 6 ) 一( 2 2 1 1 ) 的两端做l 变换，用初始条件( 2 2 5 ) ，得 s g ( s ) 一l = 一九昂( s ) + n + ( s ，x ) 4 x ) 出 ( 2 2 1 2 ) 0 啦+ ( s ，力+ 丢舅o ，砷= - t + ( 功】耳( s ，功，( o x o o ) 蚪( s ，功+ 丢巧( s ，功= 一( 力e ( s ，力+ e ( s ，功，( o x ) 最+ ( 岛o ) = 凡昂( d + 严( s ，砷( 力出 巧( s ，0 ) = 0 聪( s ) + 了0 只o ，力出+ 了0 巧( s ，功出= 詈 u 这是一组关于x 的微分积分方程。由( 2 2 1 3 ) 可解得 e o ，力= e + o ，o ) e 一 。【1 一g ( 力】 1 4 ( 2 2 1 3 ) ( 2 2 1 4 ) ( 2 2 1 5 ) ( 2 2 1 6 ) ( 2 2 1 7 ) ( 2 2 1 8 ) 江苏大学硕士学位论文 代入( 2 2 1 2 ) 徙j l 蟛( s ) 一1 = 一九昂( s ) + 暑( s ，o ) p 小+ 。 1 一g ( 功p ( z ) 出 0 = 一九胃o ) + 弓( s ，o ) g + o + 五) 其中g + ( s ) = p d g ( x ) = p g ( x ) d x ，解得 00 片( s ) ：舅( j ，o ) 掣+ 去 ( 2 2 1 9 ) s + 九j + 如 ( 2 2 1 4 ) 可改写为 丢巧( 蹦) + 【雕) 】巧( 蹦) 一 趴蹦) - 0 一ii s + p ( y ) 】砂ti 【s + 声( z ) 】虹 解得巧( s ，工) = e ； = 佃。+ 么+ c 弘= p + 彳+ c = o a o 和a 有负的对角线元素和非负的非对角线元素，其余子块均是非负阵，e 是元 素全为1 的列向量a 称状态集他1 ) ，化2 ) ( 1 【，m ) 为水平k 。若过程是正常返 的，以留，) 表示过程 x ( ，) ，( ，) ) 的极限变量，并记 1 6 江苏大学硕士学位论文 万蚵= ! i m p 口o ) = 七，o ) = a - - e x = 七，j = j ) 其中k 0 , 1 j m 。为适应q 的分块形式，将稳态概率按水平写成分段形式 n - k = ( 7 小n - k 2 ，) ，k 0 拟生灭过程是经典生灭过程从一维状态空间到多维状态空间的推广，正如生灭 过程的生成元具有三对角形式一样，拟生灭过程的生成元是分块三对角阵。从2 0 世纪8 0 年代到9 0 年代田乃硕等把n e u t s 的矩阵几何解方法引入到休假排队模型中， 促进了多服务台休假排队系统的研究，并且初步建立起多服务台休假中以条件随机 分解为核心的理论框架，为经典排队论的发展和应用开辟了更为广阔的前景。 1 7 江苏大学硕士学位论文 第三章一类带有负顾客且具有反馈的h g 1 可修排队系统 g e l e n b e 在1 9 9 1 年提出了负顾客的排队模型1 2 7 1 ，从而开创了负顾客排队模 型的先河，此后几乎每年都有令人鼓舞的成果产生1 2 s - 3 0 】。其中负顾客抵消正顾 客，即负顾客代表某种工作消失信号或者是神经网络中的控制信号，抵消规则一 般是负顾客抵消排队系统中的第一个顾客或者最后一个顾客。作者首次将负顾客 和反馈相结合研究了一类带有负顾客且具有反馈的m g 1 可修排队系统，特别的 是抵消中间顾客，中间顾客是排队系统中除去第一个和最后一个的顾客。若只有 两个顾客时，负顾客自动消失，否则抵消中间任意一个顾客。有不少文献研究了具 有反馈的排队模型 3 1 - 3 2 j 。这类排队模型的特点是：顾客被服务完会以概率1 一仃 继续留下等待服务，以概率盯( 0 仃1 1 离开系统。生活中有这样的例子，如在 网络上的搜索引擎，在搜索资源时信息的出现看成正顾客的到达，打开搜索引擎 相当于系统中的第一个顾客，筛选信息可以看作负顾客的到达，关闭搜索引擎相 当于系统中的最后一个顾客。 3 1 模型的数学描述 ( 1 ) 正，负顾客分别以到达率a + ，名一的p o s s i o n 流独立到达，令兄= 名+ + 名一， 正顾客先来先服务，负顾客抵消中间顾客，负顾客不接受服务，正顾客每次服 务完后以概率1 一立刻排到队尾等待下一次服务，以概率盯( 0 盯1 ) 立刻离 开系统，永不再来。若设f 为一个正顾客的总的服务次数，则f 服从参数为 的几何分布，即善一g e o ( o - 1 。 ( 2 ) 系统中有一个服务台，其寿命j 是负指数分布 x ( t ) = p 瞄f ) = 1 一e 一，顾客的服务时间历服务台的修理时间均为一般的 连续型随机变量， 1 8 江苏大学硕士学位论文 曰b o ) ：f b ( x ) d x ：1 一e c r ( j ) 凼 日一日( f ) = f h ( x ) a x = 1 一p 私力咖 ( 3 ) 在服务台空闲期间即系统闲期内，服务台既不失效也不变坏。当服务 台失效时，正在接受服务的顾客需要等待其修复，再继续接受服务，已服务过的 时间仍有效。服务台修复后，完全恢复它的功能，其寿命仍为丘且时刻芒= 0 服 务台是新的。顾客的到达间隔，服务时间，服务台的运转寿命以及服务台失效后 的修理时间各自独立同分布且相互独立。 令n ( t ) 表示队长，采用补充变量法，构造马尔可夫过程。引进变量：x ( t ) 表示时刻灏客已用去的服务时间，y ( t ) 表示时刻t 已维修的时间，则 ( f ) ，x ( ，) ，r ( t ) t o ) 是向量马尔可夫过程。 状态概率定义为 最( ，) = 尸( o ) = 七) ，( k = 0 ，1 ，2 ) p k ( t ，x ) d x = p ( n ( t ) = k ，x - x ( t ) x + d x ) ，( k = l 2 ，) 最( ，x ，y ) d y = p ( n ( t ) = k ，x ( r ) = x ，y - o ) 是状态空间 = o ，( ( 1 ，z ) ，x ) ，( ( 2 ，勰) ，墨y ) ，( ( 3 ，栉) ，五y ) l 艘= l ，2 ，o 墨y 上的向量m a r k o v 过程。 其状态概率定义力 最( f ) = p s ( f ) = o p i bo ，x ) 威= 尸 s o ) = ( 1 ，刀) ，x x ( t ) x + d x ，l = 1 ，2 ， 墨。o ，x ，j ，) 出= 户 s ( ) = ( 2 ，撵) ，y y o ) y + 咖) ，靠= 1 ，2 ， 吼。( f ，x ，j ，) 砂= p s ( ，) = ( 3 ，行) ，y 0 。 ( 2 ) q ，o ，x 协表示一个联合概率，它表示时刻t 服务台处于工作状态，重试 队列中有i 个顾客，正在接受服务的顾客已完成的服务时间在x 到x + d x 之间，此 处i 0 。 ( 3 ) r j ! 【1 ) ( f ，x ，y 炒表示一个联合概率，它表示时刻t 服务台由于第一类故障 而处于维修状态，重试队列中有i 个顾客，之前正在接受服务的顾客已完成的服 务时间为x ，服务台已完成的维修时间在y 到y + d y 之间，此处i o 。 江苏大学硕士学位论文 ( 4 ) 硝2 ( ，y ) 砂表示一个联合概率，它表示时刻t 服务台由于第二类故障 而处于维修状态，重试队列中有i 个顾客，之前正在接受服务的顾客已完成的服 务时间为x ，服务已完成的维修时间在y 到y + d y 之间，此处i 0 。 则在任意时刻，系统的状态都可以由随机变量( f ) ，石( f ) ，x ( f ) 和e o ) 来描 述。通过考虑时刻t 到f + a t 之间过程的转移情况，并令址一0 ，可以得到描述系 统的状态转移过程。 很显然，届，历以及灾难到达率v ( 0 ) 的存在充分保证了 ( ( ，) ，x ( ，) ，巧( ，) ，e ( r ) ) 的极限概率存在并且为正数。所以，我们可以定义 置= ；蛩只o ) ，q g ) = j 骢q o ，x ) ， r j ! ( 1 ) g ，少) = l i r ar 夕o ，工，y ) ，尺j 2 ) = l i mr j 2 o ，y ) 则可以得到系统的状态转移方程为： 阢+ f 乡k = ( 1 一p ) f o j g 咖g ) 出+ p f q 一，g ) g ) 出 ( 5 1 1 ) 喙d + 2 + a + t 阱v q ，阱n b 归涉+ 蛾g ) ( 5 1 2 ) 导+ 五+ 届) 月，g ，少) = 见尺旦i g ，y ) ( 5 3 ) 万d + 元+ 岛) 尺p ) = 艘璺( y ) ( 5 t 4 ) 相应的边界条件为： q ( 0 ) = 兄p + o + 1 ) f 辉+ ( 5 1 5 ) 硝g ，o ) = 砸；g ) ( 5 1 6 ) r n 2 m v - ! 、= 芝n = o j f o 只g ) 出 ( 5 1 7 ) 归一化条件为 主i = 0k + r q ，b ) 出+ fr 尺，t 。b ，y 澎，吵+ j c o 硝2 ，炒) = 1 ( 5 1 8 ) 江苏大学硕士学位论文 且对于固定的x 和y ，定义 q 。g ) = o ，r ( i j ，) = o ，r ( ；) ( y ) - - - o 我们定义如下的概率母函数： 尸g ) = p , z ，q ( z ，x ) = q g ) z ， r o ) ( x ，y ，z ) = r j ! 【1 ) g ，少) z ， 灭2 ( ) ，z ) = 尺j 2 k ，h 1 。 则