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

江苏大学硕士学位论文 摘要 本课题主要研究具有负顾客的两类排队系统，一类是具有负顾客 的m i g i 可修排队系统，另一类是有灾难发生的排队系统。对m g i 可修排队系统，运用补充变量法和状态转移及l 变换分析，得到了该 类系统的三个不同模型的各自队长的概率母函数及部分可靠性指标。 对有灾难发生的排队系统，运用嵌入马氏链的方法，研究了b m a p s m 1 排队模型，并通过转移概率矩阵，得到了队长的概率母函数。而对于 有灾难发生的g e o g e o l 离散时间排队模型，通过状态转移也得到了 队长和等待队长的概率母函数，并通过数值例子给出了参数对几个性 能特征的影响，从而为下面求解各种排队指标( 如：队长，逗留时间 等) 打下了基础。 关键词：负顾客灾难补充变量法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 w ok i n d so fq u e u e sw i t hn e g a t i v e c u s t o m e r s ，t h eo n ek i n d i sm g 1 r e p a i r a b l eq u e u e sw i t hn e g a t i v e c u s t o m e r s ，t h eo t h e rk i n di sq u e u e sw i t hd i s a s t e r s f o rm g 1r e p a i r a b l e q u e u e 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 sm e t h o d ，“s t a t et r a n s f e r a 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 ”，w ed e r i v et h eg e n e r a t i n gf u n c t i o n so f q u e u e i n gl e n g t h sw h i c hb e l o n gt ot h r e ed i f f e r e n tm o d e l s f o r t h eq u e u e s w i t hd i s a s t e r s ，w er e s e a r c hb m a p s m 1q u e u e sw i t hd i s a s t e r sa n d h y s t e r e t i cc o n t r 0 1 b yu s eo f “i m b e d d e dm a r k o vc h a i n ”a n d t r a n s i t i o n p r o b a b i l i t ym a t r i x ，w e d e r i v et h eg e n e r a t i n gf u n c t i o no fq u e u e i n g l e n g t h f o rt h ed i s c r e t e - t i m eg e o g e o 1q u e u ew i t hd i s a s t e r s ，w ed e r i v e t h eg e n e r a t i n gf u n c t i o n so fq u e u e i n gl e n g t ha n dw a i t i n gq u e u e i n gl e n g t h b yu s e o f s t a t et r a n s f e ra n a l y s e s ”，a n du s i n gn u m e r i c a lr e s u l t s ，w es h o w t 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 ec h a r a c t e r i s t i c s w h i c hm a k e sp r e p a r a t i o nf o rg e t t i n gv a r i o u sq u e u ei n d e x 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 ，d i s a s t e r s ，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 ， l a p l a c et r a n s f o r m ，r e l i a b i l i t y , g e n e r a t i n gf u n c t i o n ，r e w i a lq u e u e s ， h y s t e r e t i cc o n t r o l i i 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学位保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权江苏大学可以将本学位论文的全部内容或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 保密口，在年解密后适用本授权书。 不保密团。 学位论文作者签名：l - 叼专荡 指导教师签名： r 上口p ，年4 月2 日少1 5 d r 年华, e lr 日 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已注明引用的内容以外，本论文不 包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完 全意识到本声明的法律结果由本人承担。 学位论文作者签名：向守亏 日期：) o d 年4 月皇日 江苏大学硕士学位论文 第一章绪论 本章对负顾客排队模型和特殊模型的发展及研究现状作一简单介绍，同时阐 明本课题的研究意义以及主要的研究内容。 排队论又称随机服务系统，是专门研究由于随机因素的影响而产生拥挤现象 的科学。它通过研究各种服务系统在排队等待中的概率特性，来解决系统的最优 设计和最优控制。排队论最早可追溯到上个世纪，在上世纪初，丹麦数学家、工 程师爱尔朗将概率论方法用于电话通话问题，从而开创了排队论这门学科的先 河。之后的几十年时间里排队论的理论得到迅速发展，并逐步趋于成熟。其文献 数以千计，特别在计算机技术迅猛发展的同时，排队论的发展更是日新月异，应 用领域也不断扩大。它适用于一切服务系统，特别在通信系统、交通系统、计算 机存储系统和生产管理系统等方面应用广泛。 排队系统由顾客和服务台构成，其中顾客是被服务的对象，服务台是进行服 务的对象。排队系统有三个组成部分：输入过程、排队规则及服务机构。输入过 程是描述顾客的来源及顾客是按怎样的规律抵达排队系统的：排队规则有先到先 服务、后到先服务、随机服务和有优先权的服务；服务机构主要是指服务台的数 目，进行服务时服务的方式是并联还是串联，接受服务的顾客是成批的还是单个 的，服务时间服从什么分布，顾客们接受服务的时间是否独立。反映排队系统的 主要特征有瞬时态与稳定态系统的队长、顾客在系统中的等待时间( 逗留时间) 、 忙期等。 自排队论这门学科形成以来，许多新的研究方向和研究方法层出不穷。大量 的科研工作者在此领域取得了丰硕的成果。排队论专家田乃硕等把矩阵解析法引 入g i m 1 型休假排队系统，并研究了部分服务台同步的休假排队模型，极大丰 富了排队模型的理论；史定华将频度转移法用于可修服务系统并且对可靠性作了 大量工作；g e l e n b e 将负顾客引入排队系统。当前，排队论的研究主要集中在排 队网络、矩阵解析法、数值计算、极限定理以及特殊模型等方面。其中特殊模型 主要是研究具有实际应用背景的满足特殊需要的有一定假定前提的排队模型，而 休假排队、可修排队以及由这两方面衍生的一些可修休假排队模型和负顾客排队 模型是特殊模型研究的几个重要方面。关于排队论的研究方法，主要有：e r l a n g 江苏大学硕士学位论文 的阶段化，k o s t e n 和c o x 的补充变量，n e u t s 的矩阵解析方法，史定华的向量马 氏过程方法、频度转移法。由于排队论研究的课题目趋复杂，很多问题难求精确 解，因此近似方法的研究正逐步深入。 1 1 负顾客的排队模型的发展及研究现状 负顾客的排队模型是排队论的一个新兴分支。负顾客或者是一次误操作或者 是外来对服务台实施服务援助或者是系统的灾难，其主要作用是抵消系统中通常 的顾客正顾客。负顾客的抵消作用按抵消时刻、抵消策略的不同对系统产生 不同的影响。抵消时刻可分为两类：一类是负顾客到达后立即抵消系统中现有的 正顾客；另一类是负顾客仅在服务结束时刻抵消现有的正顾客。抵消策略可分为： 抵消队首正在接受服务的顾客( r c h ) ；抵消队尾的顾客( r c e ) ：抵消整个系统 的顾客( d s t ) 以及随机数量的抵消。 g e l e n b e 最早将负顾客弓l 入排队模型。首先，在文【1 中作者建立了一个神经 网络模型，负顾客抵消排队系统中的一个正顾客。就像是一个“i n h i b i t o rs i g n a l ”。 此理论用途广泛，比如随机神经网络、生产系统和推论性的平行性领域等。接着， 在文 2 中g e l e n b e 又讨论了马尔可夫排队的稳定性，特别对负顾客的抵消规则 r c e 和r c h 进行了比较；在文 3 】中又讨论了马尔可夫排队网络，其中有负顾客 的到达以及顾客从一个服务台到另一个服务台可能成为负顾客的情况，得到了 个乘积形式解。这类工作又被拓展到了有多类顾客和负顾客对正顾客进行群抵消 等情况。w h e n d e r s o n 首次在文【4 中提出了负顾客队长的概念。之后，负顾客的 排队模型引起了广大科研工作者的广泛兴趣。 关于最典型的m 船，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 h o l m 积分方程；在 策略为l c f s r c h 系统中，作者运用了补充变量法，对稳态条件下的系统状态 转移概率进行分析，获得了结论；对其余具有不同的服务规则和抵消规则的系统， 作者也作了讨论。j a i n 和s i g r n 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 州。和c o r a l 的文 1 0 1 中的独到之处在于考虑当正顾客不存在时，到达的负顾客进入一个特殊 的轨道，然后当有正顾客到达时再去抵消，并且是重复请求的排队系统。作者证 明了稳态队长分布仍能满足第一类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 在文【11 】 中考虑有负顾客的多服务台再试排队模型。负顾客作为阻止系统超负荷的一种控 制措旌，其控制策略为：当服务台被全占用时，负指数时间内系统是正常工作的； 但若时间超过后服务台仍是满的，那么有随机数量的正顾客被抵消。朱翼隽在文 【1 2 】中创造性地提出了负顾客可以接受服务的思想，研究了一类服务规则为 f c f s 抵消规则为r c e 的负顾客的m g 1 排队模型，得到了队长分布的概率母 函数、虚等待时间及等待时间的l 变换表达式。文【1 3 】的作者运用补充变量法， 对具有负顾客的m g 1 可修排队模型进行了研究，得到了各自队长分布的广义 概率母函数。文c 1 4 的作者还将负顾客引入休假排队系统，研究了具有负顾客的 m g 1 和g i m 1 休假排队模型，分别得到了系统队长的概率母函数，大大丰富 了负顾客排队模型的理论体系。 1 2 具有灾难( d s t ) 发生的排队模型的研究现状 灾难是一类特殊的负顾客。灾难到达系统时会将全部顾客抵消，包括接受服 务的顾客。实际的服务系统不都是可靠的，并且灾难时有发生，比如突然的断电、 计算机病毒袭击通信系统等，这些都破坏了系统的正常运行。 对有灾难发生的经典排队模型，c h e n 和r e n s h a w 在文 1 5 1 中考虑了m m 1 排队模型。c h a e 1 6 1 ，j a i n 和s i g m a n 分别分析了m g 1 清空系统。其中韩国学者 江苏大学硕士学位论文 c h a e 在文【1 6 中考虑一次灾难发生后，系统中的顾客全部被抵消，服务台失效。 系统在服务台修理时可产生两类情况：一类是新到达的顾客不等待服务台修复而 直接离开；另一类是新到达的顾客等待服务台修复。作者讨论了以上两类系统的 循环周期，得到了在f c f s 服务规则下两类系统的稳态队长分布的概率母函数和 逗留时间分布的l 变换。w o n s y a n g 和k y u n g c c h a e 在文 1 7 中考虑了有灾难到 达的g i m 1 排队系统的队长及等待时间的分布，得到了稳态队长的分布。 对于有灾难发生的其他特殊模型，不少学者也在这方面作了大量的工作。 a r t a l e j o 和c o r r a l 在文【1 8 中研究了既有清理又有竞争再入的排队，即新到达的 顾客发现系统忙时会进入轨道等待，且轨道中的顾客与正在服务的顾客以一定比 例竞争接受服务，灾难发生时系统彻底清理并立即更新。a g o m e z c o r r a l 【i ， j r a r t a l e j o 和a g o m e z c o r r a l l 2 0 l 也分别对有灾难发生的重复请求排队作了研究。 关于负顾客的排队网络模型也有不少成果涌现( 参见文 2 u ， 2 2 1 ， 2 3 1 ， 2 4 1 ， 2 5 】) 。c h a o 在文 2 7 中考虑有灾难发生的排队网络，研究了网络排队的乘积形 式解。d u b i n a 和n i s h i m u r a s 在文 2 8 1 中研究了有不同种类顾客存在( 包括负顾 客) 的有灾难的混合网络，讨论了该模型下服务结束时刻的系统队长分布。y a n g w o os h i n 在文 2 9 1 中考虑了一个单服务台系统，顾客到达( b m a p ) 和灾难的到 达( m a p ) 是相关联的，d s t 发生时，抵消所有顾客，且对系统来说需要修理 时间才能正常运转。即使在d s t 到达时，系统是空的，修理时间也开始，修理 期间内允许无到达( 包括d s t ) ，得到了队长在嵌入点和任意时刻的分布，以及 在灾难和顾客到达时队长的分布，并给出了特例。d u b i n a ，a v k a r o l i k 在文 3 0 】 考虑了有d s t 到达的b m a p s m 1 排队系统，考虑了d s t 出现后系统经一段随 机时间后才恢复正常工作，得到了稳态的嵌入队长分布和任意时刻的队长分布， 并给出了数值例子。o v s e m e n o v a 在文【3 1 1 中考虑了较复杂的b m a p s m 1 排队 系统，有d s t 到达且有门限控制。这里作者将经典门限策略作一修改，考虑运 行方式或者在服务成功完成时刻转换或者在忙期开始时刻转换，得到了嵌入马氏 链的稳态概率分布，并给出了一个最优修改门限控制策略的迭代解。另外，关于 对b m a p g 1 排队系统的研究也有大量成果( 参见文 3 4 】 3 7 3 9 】) 。 1 3 本课题研究内容及解决问题的方法 本课题研究的是两类具有负顾客的排队模型，借助于研究排队模型常用方法 江苏大学硕士学位论文 “补充变量法”及“嵌入马氏链方法”，得到了所需的排队指标。 对负顾客的m g 1 可修排队系统，按照服务规则和抵消规则的不同，本文 考虑了三种不同服务机制的排队系统，运用补充变量法和状态转移及l 变换分 析得到了它们队长分布的l z 变换表达式、广义概率母函数、系统服务台可用度、 服务台使用故障频度以及可靠度指标。 对有灾难( d s t ) 发生的排队系统，首先运用嵌入马氏链的方法，研究了 b m a p s m 1 排队模型，并通过转移概率矩阵得到了队长的概率母函数；其次本 文还考虑了一种有灾难发生的g e o g e o 1 离散时间排队模型，通过状态转移也得 到了队长和等待队长的概率母函数，并通过数值例子给出了参数对几个性能特征 的影响。 江苏大学礤士学位论文 第二章研究排队模型的方法 研究排队模型的方法很多，现仅介绍几种最常用的方法。一种是嵌入马氏 链的方法，即寻求过程再生点。另一种方法是补充变量法即将非马氏过程变成向 量马氏过程。 2 1 嵌入马氏链法 对于一般服务或一般到达的排队系统，不是在任何时刻系统都具有马尔可| 夫 性质，只是在某些特殊的随机时刻系统才具有这种性质，我们称这种随机时刻点 为再生点，即从这个时刻起，系统好像又重新开始一样。利用再生点，一般服务 或一般到达的排队系统可化为马尔可夫链，用马尔可夫链的方法予以解决，这种 方法就叫做嵌入马尔可夫链法。徐光辉 4 4 】，孟玉珂 4 5 】，唐应辉唐小我 4 6 】， 陆传赉 4 7 】，华兴 4 8 】，孙容恒& 李建平 4 9 ，对此做了详细的论述。 2 1 。1 嵌入马尔可夫链点的寻找 设顾客是以参数为 的p o s s l o a 流到达，服务台是一般的服务时间分布，即 是m g 1 排队系统。对任选的一个时刻t ，正在接受服务的顾客可能还没有服务 完，于是从时刻t 起剩余的服务时间，般说来，已不服从原来的服务时间分布。 在一般服务分布下，剩余的服务时间分布不具有无记忆性。如果对m g 1 排队 系统顾客进入与离去的时刻进行观察和分析就会发现有些时刻足很特殊的，例 如，观察一顾客服务刚结束的时刻，从这个时刻服务台的工作有复原：或处于空 闲状态或接受另一顾客并为之服务。服务结束的时刻不一定是顾客的到达时刻， 对于走到半路中的顾客来讲，由于到达间隔时间服从负指数分布，因此剩余到达 时间( 由负指数分布无记忆性) 还是服从负指数分布，对于这些时刻，系统好像 重新开始一样，系统未来的状态完全由这个时刻系统所处的状态决定，且与以前 系统曾处于什么状态无关。这种时刻口q 做再生时刻或再生点。把服务台完成服务 的时刻一一找出，得到一个再生点列，即t 】, t 2 ，t 。 t n 是随机点列，间隔 时间t + l t n 也是随机的。我们来研究系统在时刻t 。时的状态。在时刻t 。，由于 一个顾客刚被服务完，假定这时系统中有个顾客，而在t n 十l - - t 。时间内到达l 一个顾客刚被服务完，假定这时系统中有n 。个顾客，而在t n 十l - - t 。时间内到达l 江苏大学硕士学位论文 第二章研究排队模型的方法 研究排队模型的方法很多，现仅介绍几种最常用的方法。一种是嵌入马氏 链的方法，即寻求过程再生点。另一种方法是补充变量法即将非马氏过程变成向 量马氏过程。 2 1 嵌入马氏链法 对于一般服务或一般到达的排队系统，不是在任何时刻系统都具有马尔可夫 性质，只是在某些特殊的随机时刻系统才具有这种性质，我们称这种随机时刻点 为再生点，即从这个时刻起，系统好像又重新开始一样。利用再生点，一般服务 或一般到达的排队系统可化为马尔可夫链，用马尔可夫链的方法予以解决，这种 方法就叫做嵌入马尔可夫链法。徐光辉 4 4 ，孟玉珂1 4 5 ，唐应辉& 唐小我 4 6 ， 陆传赉 4 7 】，华兴h 8 ，孙容恒& 李建平【4 9 ，对此做了详细的论述。 2 1 1 嵌入马尔可夫链点的寻找 设顾客是以参数为五的p o s s i o n 流到达，服务台是一般的服务时间分布，即 是m g l 排队系统。对任选的一个时刻t ，正在接受服务的顾客可能还没有服务 完，于是从时刻t 起剩余的服务时间，一般说来，己不服从原来的服务时间分布。 在一般服务分布下，剩余的服务时间分布不具有无记忆性。如果对m g 1 排队 系统顾客进入与离去的时刻进行观察和分析就会发现有些时刻是很特殊的，例 如，观察一顾客服务刚结束的时刻，从这个时刻服务台的工作有复原：或处于空 闲状态或接受另一顾客并为之服务。服务结束的时刻不一定是顾客的到达时刻， 对于走到半路中的顾客来讲，由于到达间隔时间服从负指数分布，因此剩余到达 时间( 由负指数分布无记忆性) 还是服从负指数分布，对于这些时刻，系统好像 重新开始一样，系统未来的状态完全由这个时刻系统所处的状态决定，且与以前 系统曾处于什么状态无关。这种时刻叫做再生时刻或再生点。把服务台完成服务 的时刻一一找出，得到一个再生点列，即t l ，t 2 ，t n 。 t n 是随机点列，间隔 时间“l t n 也是随机的。我们来研究系统在时刻t 。时的状态。在时刻t 。，由于 一个顾客刚被服务完，假定这时系统中有n 。个顾客，而在t 。+ l - - t 。时间内到达l 6 江苏大学硕士学位论文 个顾客，则时刻t n + l ( 服务台刚结束下一个顾客服务的时刻) 系统中应有n 。+ l 一1 个顾客( 假定n 。 0 ) 由于到达流是p o s s i o n 流，在这些再生时刻，观察系统的 状态一顾客数，它具有马尔可夫性。n 。表示一个顾客服务结束后刚离开系统时 留在系统中的顾客数，n n 。 就是一个马尔可夫链，这叫嵌入马尔可夫链。由于 t n + 1 一t 。对一切n 都是同分布的，到达又是以p o s s i o n 流，于是经过f 一f 。这段时 间，系统从状态。到巩+ 三一l 状态的概率相同，因此是一个齐次马尔可夫链。 为求得此马尔可夫链得平稳分布，首先应求出转移概率。 2 1 2 转移概率矩阵 用一顾客服务结束后离开系统时的队长作为系统的状态，因此系统的一步转 移就是一个顾客离开系统到下一个颓客离开系统这段时间系统状态的变化。 设服务时问v 的密度函数b ( t ) ，平均服务时间为 e e v 一1 f t b ( t ) d t ( 2 1 1 ) 1 b ( t ) 的l 变换记做曰( s ) ，即b ( j ) = f e - s t b ( t ) d t ( 2 1 2 ) 其中要求r ( s ) 0 ，即s 的实数部分大于零。再设p = 州 c 。：表示进入系统的第n 个顾客，t n ：表示c 。服务完离开系统的时刻， n 。：表示c 。离开系统后留下的队长，v 。：表示c 。的服务时间， a 。：表示c 。的服务时间v 。内到达系统的顾客数。 由定义知 v 。 是独立同分布的随机变量序列，分布密度为b ( t ) ； a 。) 是独立 同分布的随机变量序列，概率分布记做 a k ) 。 为了求得一步转移概率p i j ，需先求 a 。) 的概率分布 a k 。 而a k 一- - - p ( a 。= k )( 2 1 3 ) 由于服务时间v 。是随机的，事件 a 。= k 表示在第1 3 个顾客c 。的服务时间v 。 内以p o s s i o n 流到达k 个顾客，而o k o o 。若k = r ，说明( o ，t ) 内到达k 个顾客，而f ( 0 ，0 0 ) 。因此应该用连续时间的全概率公式求a k ，即 吼= 【p ( a 。= k i k = t ) b ( t ) d t ( 2 1 4 ) 江苏大学硕士学位论文 删。= | j i v 叫= 譬e 从而嘶= r 譬“6 ( r ) 砒( 。 0 时，服务台立刻接受顾客q + 。进行服务。服务时间为圪+ 。这段时间达到 的顾客数为a 。巴+ 。服务结束离开系统时，系统内有顾客数虬。= n 。+ 一。一1 。 若虬= 0 ，则c 。离开系统后，系统内无顾客，服务台处于空闲状态，这时q + ，还 未到达。巴+ 达到后立刻接受服务。在c 。接受服务时间内到达4 。个顾客。因 此巴“服务完离开系统时留下的队长虬+ 。= a 。因此从时刻f 。到时刻r 。顾客转 移为 江苏大学硕士学位论文 ri n 。+ a 。“一1虬0 川“2 “。虬= 0 设p ，= p ( 虬+ l = ，i n 。= f ) ( 2 1 1 0 ) 当i = 0 时，p o = p ( n = l n 。= o ) = p ( a = ) = d ( 2 1 1 1 ) 当i 1 时，p f = p ( 。+ i = ，i 。= f ) = p ( 。+ a 。+ 1 1 = i n n = f ) = e ( a 。+ l = _ ，一f + 1 ) = 口，一。1 ，( _ ，i 一1 )( 2 1 1 2 ) 由此得一步转移概率矩阵p = ( 既) = d 0n l d 0d l 0 d o 00 d 2口3 d 2码 qd 2 q oq ( 2 i 1 3 ) 由转移矩阵p 可知， 。) 是一个齐次马尔可夫链，且非周期不可约，当p ：兰 o ) 。进一步假定修理 时间y 与上述部件故障的规律是相互独立的，故障部件修复后与新部件一样。下 面对基本模型求其系统可用度。先令 加) a t = p t y _ t + a t 眇f - 涨 ( 22 由上式易证 1 一g ( r ) = e x p - k t ( y ) d y 0 g ( r ) = ( r ) e x p - p ( y ) d y 0 ( 2 2 3 ) 由于部件修理时间r 遵从一般分布， j v ( f ) ，f 0 ) 不是马尔可夫过程。例如 当知道时刻t 系统中有一部件故障，即知道n ( t ) = 1 ，时刻t 以后系统发展的概率 规律还不能完全确定下来，时刻t 以后系统发展的概率规律不仅依赖于时刻t 有 几个部件故障，还依赖于正在修理的部件在时刻t 以前已经修理了多长时间。 江苏大学硕士学位论文 我们引进一个补充变量x ( f ) ：当( f ) = 1 或2 时，( f ) 表示时刻t 正在修理 的部件已经修理过的时间；当_ v ( r ) = 0 时，没故障部件的修理，z ( r ) 可以不考虑。 这样过程 ( f ) ，x ( r ) ；f 0 ) 是一个连续时间的广义的马尔可夫过程，即在任意时 刻t ，当给定n ( t ) 和x ( t ) 的具体值，则过程 ( f ) ，x ( r ) ；r 0 ) 在时刻t 以后的概 率规律与时刻t 以前该过程的历史无关。对f 0 ，x 0 ，令 j b ( r ) = p ( ( f ) = o ) 鼻0 ，x ) 出= p n ( t ) = 1 ，茁 x ( t ) x + d x )( 2 2 4 ) 1 只( r ，功d x = p f n ( t ) = 2 ，x 石( r ) s x + 出) 假定时刻t = o 时，两个部件都是好的，即初始条件是 晶( 0 ) = 1 ，只( 0 ，x ) = b ( o ，x ) = 0( 2 2 5 ) 由( 2 2 ，4 ) 可导出如下方程组 石d 晶( f ) = 一a o p o ( t ) + p 。，x ) ( x ) 疵 ( 2 2 6 ) 昙郫，卅昙聃，加嘲+ 贴) 州“) ，o x o o ( 2 2 7 ) 兰b ( f ，工) + 昙最( r ，x ) = 一l u ( x ) p 2 ( t ，x ) + 鼻( f ，x ) ，o 0 ，必须n ( t ) = 2 ，x ( t ) = x ，且在 ( f ，t + a t 】内部件的修理没有完成：或者n ( t ) = 1 ，x ( t ) = x ，且在( r ，r + 明内一个 部件发生故障，因此 最( f + a t ，z + a t ) = 只0 ，x ) 1 一u ( x ) a t + p i ( f ，x ) & a t + o ( a t ) 4 ) 为使n ( t + a t ) = 1 ，0 x ( t + a t ) a t ，必须n ( t ) = 0 ，且( f ，f + 出 内一个部件 发生故障；或n ( t ) = 2 ，x ( t ) 为某正值x ，并且在( r ，r + a t 内正在修理的部件修理 完成。因此 a t ” p l ( t + a t ，0 ) a t = p 1 ( t + h t ，y ) d y = p o ( t ) a o a t + j 只o , x ) 4 x ) a t d x + 。( f ) 00 即( 2 2 9 ) 式。 5 ) ( 2 2 1 0 ) 式是由于n ( t ) = 2 和x ( t ) = 0 不可能同时发生。 6 ) ( 2 2 1 1 ) 式是由于全概军公式。 为解这个方程，对( 2 2 6 ) 一( 2 2 1 1 ) 的两端做l 变换，用初始条件( 2 2 5 ) ，得 s p o ( s ) - i = 一凡只( s ) + b ( s , x ) 4 x ) d x ( 2 2 1 2 ) 嵋o ，x ) + 一u 。p 0 ，x ) = 一 + ) 】舅0 ，x ) ，( 0 x )( 2 2 1 3 ) a x s p ? ( j ，x ) + 旱户? ( s ，工) = 一4 x ) p ；( s ，x ) + 五，只( s ，石) ，( o x m )( 2 2 1 4 ) a x 鼻+ ( s ，o ) = 九只( 5 ) + f 只( s ，x ) 4 z ) 出 ( 2 2 1 5 ) 只i ( s ，0 ) = 0 ( 2 2 1 6 ) 1 3 江苏大学硕士学位论文 聃) + m 0 棚出+ k 0 沁舳= ： 4 这是一组关于x 的微分积分方程。由( 2 2 1 3 ) 可解得 置+ ( 5 ，x ) = e + o ，0 ) e 一”n 【1 一g ( x ) 】 代入f 2 2 1 2 ) 得 s p o ( j ) 一1 = 一五日( j ) + 只( s ，o ) p 一”4 n 1 一g ( x ) ( x ) d r 0 = 一南e o ( s ) + e + ( s , 0 ) g + ( s + ) 其中g + ( s ) = i e 一“d g ( x ) = i e 一“g ( x ) d r ，解得 00 驰m 砸固睾孚+ 击 ( 2 2 1 4 ) 可改写为 要巧( s x ) + 【s + 4 x ) 】耳( s ，x ) 一a 鼻( s ，x ) = o 础 - j 时f ( 川砂 i ( s + , u ( z ) l d z 解得g ( s ，x ) = p 。 巧( s ，o ) + i 异( j ，y ) 口od y ) 将( 2 2 1 6 ) $ 1 ：1 ( 2 2 1 8 ) 式代入，得 ( 2 2 1 7 ) ( 2 2 1 8 ) ( 2 2 1 9 ) 巧( s ，x ) = e - s x 1 一g ( x ) 】 只+ ( 只o ) p 一如咖= e + o ，0 ) 1 - g ( x ) p 一“( 1 - p 一印) ( 2 2 2 0 ) o 将( 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 ) 和( 2 2 2 0 ) 代入( 2 2 1 5 ) 同样可得( 2 2 2 1 ) 式) 。将 ( 2 2 2 1 ) 代入( 2 2 1 8 ) ，( 2 2 1 9 ) 和( 2 2 2 0 ) ，可得 4 江苏大学硕士学位论文 耶，= 毒杀等黯 牝垆而等等器 聃朋= 未蠕鬈焉 系统的瞬时可用度是 a ( o = 晶( f ) + j e ，( t , x ) a x 0 r 2 2 2 2 ) 作l 变换，并将( 2 2 2 2 ) 式代入，得 4 + ( s ) = i e - s t a ( t ) d t = 碍o ) + f 鼻+ ( s , x ) d x ( 2 2 2 3 ) 0o 江苏大学硕士学位论文 第三章负顾客的m i g i i 可修排队模型 关于负顾客的排队系统，最早源自g e l e n b e ( 1 9 9 1 ) 3 1 的研究工作，此后几 乎每年都有令人鼓舞的成果产生。目前负顾客已经渗透到交通、机械、控制以及 计算机等许多领域。h a r r i s o n & p i t e l ( 1 9 9 3 ) 1 5 j ( 1 9 9 6 ) t ”，b a y e r & b o x m a ( 1 9 9 6 ) 州， a r t a l e j o & c o r r a l ( 1 9 9 9 ) ，z h uy i j u n ( 2 0 0 1 ) 1 12 1 ，这些文章都得到了有意义的结果。 本章把负顾客和可修系统结合起来，研究了三类负顾客的m g 1 排队系统，分别 是：服务规则为先到先服务且负顾客抵消队尾顾客的排队系统；服务规则为后到 先服务、负顾客抵消队首顾客且可接受服务的排队系统；服务规则为先到先服务、 负顾客抵消队尾顾客且容量有限的服务台提供两种服务的排队系统。 3 1 负顾客的m g 1 可修排队模型 3 1 1 模型的数学描述 ( 1 ) 正负顾客分别以到达率，万的p o s s i o n 流独立到达。系统中有一个服务台， 其寿命x 是负指数分布x ( f ) = p ( x f ) = 1 一e 一。顾客的服务时间b ，服务台的修 理时间h 均为一般的连续型随机变量。 l： 。p - j r ( x ) d x t f jp ( y ) a y b b ( t ) = i b ( x ) d x = 1 8 。h 日( f ) = i h ( x ) d x = 1 一e o 占i ( 2 ) 在服务台空闲期间即系统闲期内，服务台既不失效也不变坏，相当于在闲期 内关闭服务设备且处于冷备状态，不影响服务台的使用寿命。当服务台失效时， 正在接受服务的顾客需要等待其修复，再继续接受服务，己服务过的时间仍有效。 服务台修复后，完全恢复它的功能，其寿命仍为x ，且时刻t = 0 服务台是新的。 顾客的到达间隔，服务时间，服务台的运转寿命，以及服务台失效后的修理时间 是彼此独立的。服务规则和抵消规则是f c f s r c e 。 令( f ) 表示队长，采用补充变量法( 文 7 ) ，构造马尔可夫过程。引进下述 变量：x ( r ) 表示时刻t 顾客已用去的服务时间，y ( f ) 表示时刻t 已维修的时间， 则 ( f ) ，x ( f ) ，y ( 圳r o 是马尔可夫过程。 江苏大学硕士学位论文 状态概率定义为：e k ( t ) = 尸( ( f ) = 女) ，( 女= 0 , 1 ，2 ) 只o ，x ) d x = p ( ( r ) = 七，x j ( f ) 茎z + 出) ，( 七= 1 2 ) 只( f ，x ，y ) d y = p ( ( ，) = k ，z ( f ) = x ，y ，) 。b + 曰+ ( r ) ：卜+ ( 工) 出= l - e 十。弋砷“ b 一b 一( r ) ：_ 一( 曲出：1 一。- f 。，1 砷“何删r ) _ 沁) 咖小。一咖。 ( 3 ) 在服务台的空闲期间即系统闲期内，服务台既不发生失效也不变坏，相当于 在闲期内关闭服务设备且设备处于冷备状态，即不影响服务台的使用寿命。当服 务台失效时，正在接受服务的顾客需要等待其修复，再继续接受服务，已服务过 江苏大学硕士学位论文 的时间仍然有效。服务台修复后，完全恢复它的功能，其寿命仍为x ，且t = 0 时 刻服务台是新的。顾客的到达间隔，服务时间。以及服务台失效后的修理时间是 彼此独立的。 n ( f ) 分别代表正负顾客在时刻t 累积数目，令n ( t ) = n + ( f ) + 一( f ) ， + ( ，) 0 ，n 一( ，) 0 ，p ) 是一代数和，且( f ) 表示队长，显然 ( ，) i f o ) 不是 马尔可夫过程，采用补充变量法，引入补充变量：x 。( r ) 分别代表正负顾客在时 刻t 已接受的服务时间，y 2 ( f ) 表示时刻t 已维修的时间，则 + ( f ) ，z 2 0 ) ，y 2 ( f ) l t o ) 是马尔可夫过程。服务规则和抵消规则是l c f s r c h 。 状态概率定义为： b ( r ) = p ( n ( t ) = i ) ，( 七= 0 ，l ，2 ，) p a t ，x ) a x = p ( n ( t ) = 南，x x ( t ) x + 出) ，( k = 1 ，2 ，一) p k ( t ，x ，y ) a y = 尸( a i r ) = 尼，z o ) = x ，y y ( r ) y + 曲，) ，( 七= 1 ，2 ，) 常用符号 l 变换： ，+ ( j ) = f p “f ( t ) d t巧( 舻) = f