（概率论与数理统计专业论文）几类可修排队系统研究.pdf

及取 外， 得中 同志 保留 位论 采用 研究 社会 作者 摘要 本文主要研究几类可修的排队系统。 排队系统偶然遭遇了重大的故障，当前所有的顾客( 等待的和正 在被服务的) 全部丢失。修理过程马上开始，经过一个负指数分布的 修理时间后系统又重新进入正常工作状态。当系统瘫痪处于修理状态 时，新的顾客会变的没有耐心：每一个独立的顾客都遵循一个随机的 忍耐时间，当这个时间在系统修理成功之前来临的话顾客就会放弃等 待并且不再回来。我们对此排队模型进行研究，获得以下各种参数： 被服务顾客的逗留时间；顾客被服务率；由于故障丢失顾客率；由于 失去耐心丢失顾客率。 本文主要研究三个模型：一、m m 1 模型：泊松到达，只有一个 服务台，服务时间服从负指数分布，在发生故障时系统的容量有限； 二、m m c 模型：泊松到达，c 个服务台，服务时间均服从负指数分 布，在发生故障时系统的容量有限；三、m m 模型：泊松到达，无 穷个服务台，服务时间均服从负指数分布。并且针对以上三个模型， 分别研究系统在任何时候都可以发生故障和只有在工作时才发生故 障这两种情况。 关键词排队系统故障，失去耐心，概率发生函数，逗留时间，放弃 室 a bs t r a c t i nt h i sp a p e r , af e wk i n d so fq u e u es y s t e m sw h i c ha r ea b l et or e p a i r a r ec o n s i d e r e d t h es y s t e ms u f f e r so c c a s i o n a l l yad i s a s t r o u sb r e a k d o w n ，u p o nw h i c h a l lp r e s e n tc u s t o m e r s ( w a i t i n ga n ds e r v e d ) a r ec l e a r e df r o mt h es y s t e m a n dl o s t ar e p a i rp r o c e s st h e ns t a r t si m m e d i a t e l y , t h es y s t e mw i l lb a c kt o t h en o r m a ls i t u a t i o na f t e rar e p a i rt i m ew h i c hi se x p o n e n t i a l l yd i s t r i b u t e d w h e nt h es y s t e mi sd o w n ，i n o p e r a t i o n ，a n du n d e r g o i n gar e p a i rp r o c e s s ， n e wa r r i v a l sb e c o m ei m p a t i e n t ：e a c hi n d i v i d u a lc u s t o m e r , u p o na r r i v a l ， a c t i v a t e sar a n d o m d u a r a t i o nt i m e i ft h et i m ee x p i r e sb e f o r et h es y s t e mi s r e p a i r e d ，t h ec u s t o m e rl e a v e st h eq u e u en e v e rt or e t u m w ea n a l y z et h e m o d e la n dg e tv a r i o u sp a r a m e t e r sb e l o w ：m e a ns o jo u r nt i m eo fas e r v e d c u s t o m e r ；p r o p o r t i o no fc u s t o m e r ss e r v e d ；r a t eo fl o s tc u s t o m e r sd u et o d i s a s t e r s ；a n dr a t eo fa b a n d o n m e n t sd u et oi m p a t i e n c e t h et h r e em o d e l sa r es t u d i e di nt h i sp a p e r ：f i r s t l y , m m 1m o d e l ： t h ei n p u tp r o c e s si sp o i s s o nd i s t r i b u t i o n ，h a so n l yas e r v e r , t h es e r v i c e t i m ei sn e g a t i v ee x p o n e n t i a ld i s t r i b u t i o n ，a n dt h ec a p a c i t yo ft h es y s t e mi s l i m i t e dw h e ni ti sd o w n s e c o n d l y , m m cm o d e l ：t h ei n p u tp r o c e s si s p o i s s o nd i s t r i b u t i o n ，h a s c s e r v e r s ，t h e s e r v i c et i m ei s n e g a t i v e e x p o n e n t i a ld i s t r i b u t i o n ，a n dt h ec a p a c i t yo ft h es y s t e mi sl i m i t e dt o o w h e ni ti sd o w n t h i r d l y , m 7 m m o d e l ：t h ei n p u tp r o c e s si sp o i s s o n d i s t r i b u t i o n ，h a s 。s e r v e r s ，t h es e r v i c et i m ei sn e g a t i v ee x p o n e n t i a l d i s t r i b u t i o n b ea i m e da tt h et h r e em o d e l sw h i c hm e n t i o n e da b o v e ，w e s t u d yb o t ht h es i t u a t i o nw h e r ef a i l u r e sm a y o c c u ri na n y t i m ea n dt h ec a s e w h e r ef a i l u r e sm a yo c c u ro n l yw h e nt h es y s t e mi s f u n c t i o n i n ga n d s e r v i n gc u s t o m e r s k e yw o r d s s y s t e m s u f f e r sb r e a k d o w n ，i m p a t i e n c e ，p r o b a b i l i t y g e n e r a t i n gf u n c t i o n ，s o j o u r nt i m e s ，a b a n d o n m e n t s 目录 摘要i a 1 3 s t r a c t i i 第一章绪论1 1 1 问题提出的背景与研究现状1 1 2 论文的结构3 第二章预备知识5 2 1 排队论概述5 2 2 排队系统的描述5 2 3 排队模型的符号表示与分类6 2 4 负指数分布与泊松过程7 2 5 李特尔( l i t t l e ) 公式9 2 6 生灭过程和平衡方程1 0 2 7 马尔可夫过程1 3 2 8 连续时间马尔可夫链1 4 第三章m m 1 模型18 3 1 模型1 8 3 2 平衡方程和产生的函数l8 3 3 逗留时间2 3 3 4 顾客被服务率2 5 3 5 只有当f 常工作时才能发生故障2 6 3 5 1 平衡方程和产生的函数2 6 3 5 2 逗留时间2 8 3 5 3 顾客被服务率2 9 第四章m m c 模型3 0 4 1 平衡方程和产生的函数3 0 4 2 逗留时间3 3 4 3 顾客被服务率3 5 4 4 只有当正常工作时才能发生故障3 5 4 4 1 平衡方程和产生的函数3 5 4 4 2 逗留时间3 7 第五章m m c x ) 模型3 9 5 1 平衡方程和产生的函数3 9 5 2 逗留时f j 矛u 放弃率4 0 5 3 只有当正常工作时才能发生故障4 l 第六章结论4 4 参考文献4 5 致谤 4 9 攻读学位期间主要研究成果5 0 硕士学位论文第一章绪论 第一章绪论 1 1 问题提出的背景与研究现状 排队论产生于上个世纪初，迄今为止，排队论已有百年的历史，它的发展主 要分两个阶段。 在第一阶段，排队论从诞生迅速发展到高峰时期这一发展阶段又分为三个 时期第一个时期是先行者时期。像e r l a n g ，m o l i n a ，c r i n s t e d 和e n g s e t ( 见参考 文献 2 3 】， 2 5 】) 等都是这一时期的代表。他们的工作大多丌始于1 9 2 0 1 9 3 9 年 之间。在此期间提出了许多新的思想和研究方法。例如，p a l m ( 1 9 0 7 1 9 5 1 ) 的工作 为再生过程的现代理论打下了坚实的理论基础，他的工作被称p a l m 概率。f e l i x p o l l a c z e k 从上个世纪三十年代开始发表论文，他是第一次得到了g 1 g s 排队模 型的整体解，还有c r o m m e l i n 的延迟系统( 1 9 3 2 1 9 3 4 ) ，k h i nt c h i n e 的m g 1 排 队( 1 9 3 2 ) ，k o s t e n 的补充变量法( 1 9 3 7 ) 等等( 见参考文献 2 6 ， 2 7 ，【2 8 】) 。 随机过程理论的应用标志着第二个时期的开始。这一时期是排队论的成长 期，时间大约从上个世纪4 0 年代持续到6 0 年代。1 9 3 9 年被认为是一个转折点， 因为正是在这一年，f e l l e r 提出了一个后来被认为是排队论的丌创性工作的生灭 过程( 见参考文献 2 8 ) 。1 9 5 0 年前后，英国科学家g k e n d a l 创对排队论做了系 统的研究，他用嵌入m a r k o v 链研究排队论，使排队论得到了进一步的发展。排 队论的应用也推广到实际生活中的许多领域这一时期的另一些重要工作有： 1 9 4 2 年b o r e l 的等待问题，1 9 4 8 年f o r t e t 的损失系统( 见参考文献 2 8 】) 。值得 一提的是l i t t l e l 9 6 1 年发表的一篇短文，该文后来被称作l i t t l e 公式( 见文献 2 9 1 ) 。 第三个时期始于上个世纪7 0 年代初，这是一个深入研究的时代，也是一个成熟 的时期。在这一发展时期，排队论从以前的单纯研究某一个系统转向了研究一类 系统，如随机过程罩面的一些问题，对一些原理的公式推导，或者能够适用于相 当一部分系统的一般性方法( 见参考文献 2 8 】) 。 第二个阶段是排队问题的抽象化和复杂系统的使用分析阶段。点过程，马尔 可夫过程，再生过程和鞅理论等新方法使排队论再一次进入了快速发展阶段。计 算机的发展和广泛应用给排队论带来了新的课题。这个阶段不但理论上有所发 展，而且在实际问题研究中也取得了不少进展。理论结果应用到实际可以说是此 阶段的特征( 见参考文献 2 8 】) 。 在中国，排队论的研究工作是5 0 年代未期开始发展起来的。越民义，吴方， 徐光辉，曹晋华，程侃，林元烈等教授们对中国排队论的发展做了重要的贡献( 见 参考文献 3 0 】， 3 l 】， 3 2 】， 3 3 1 ) 。 硕七学位论文第一章绪论 起初是为了解决电话交换台系统的问题，而提出了排队论。排队模型是包含 更新过程与生灭过程机制的，且更为复杂的概率模型。 简单的排队过程是在两个相互独立的流作用下形成的，其中一个是要求服务 的“顾客流”，这时假定顾客是一个一个地到达的，其时间间隔组成一个更新流。 另一个是当顾客进入服务线后，接受服务的服务时问流。服务不一定一个接着一 个地发生，在两次服务之间可能有空隙，所以虽然各顾客接受服务独立统分布的 时间流，但它不具有更新流的特点。这些服务的空隙成为排队系统的闲期。两个 闲期之间的随机时间称为忙期。平均闲期长度与平均忙期长度是排队系统设计中 的重要指标。如果无视闲期的存在，而虚拟地把服务流一个接着一个接成更新流， 那么，有服务时间流可以生成一个虚拟的更新过程。 最简单的排队系统只有一条服务线，采取先到的顾客先接受服务的原则，并 且有足够大的空间( 无限制) 容纳等待服务的顾客。在时刻t 等待服务与j 下接受 服务的顾客数，是一个去非负整值的随机变量，记为置。整值随机过程 x t ；f 三= o ) 称为排队过程，它是连续时间状态离散的随机过程。顾客流与服务时间都是 p o i s s o n 流( 即指数流) 的排队过程式最简单的排队过程，只有此种情形的排队 过程才可能是连续时间的m a r k o v 链。 排队模型广泛地出现在各个领域，如交通运输、服务系统、通信系统、电脑 中信息流的存取、以及商品物流等。 排队系统的一般框图如下： 鱼盟幽堕监r 1 蕊鬲产堕盟墼避越 i：一 值得注意的是，输入过程就是顾客流生成的更新过程，但是输出过程却不是服务 时间流生成的虚拟的更新过程。因为输出过程是输入过程与服务时间流共同作用 的结果。 2 0 世纪5 0 年代，k e n d a l l ，y u e 等学者找到了一些排队过程是m a r k o v 链。 例如：m g 1 和m m ，l 排队过程的队长l ( f ) 的嵌入链l ( r 。) ( = o ，l 1 ) 为 第n 个顾客的到达时间) ，还有g i m 1 排队过程的队长三d ) 的嵌入链 l ( d 。) ( d o = 0 ，d 。1 ) 为第n 个顾客的离丌的时间) 都是具有上面所说的性质的。 m a r c e ln e u t s 发现一些排队过程并不是m a r k o v 链，但是可以通过扩大它们 的p h a s e 空间，使它们变换成一m a r k o v 链，也有很多这一类排队过程，如： 朋p h n 排队过程的队长，如上的p h g 1 和g i p h n 的嵌入链。还有很多 具有类似性质的过程都属于这一类过程。 在现实生活中，越来越多的排队系统渗透在我们的同常生活当中，去医院看 病、买车票、购物结帐、去银行办理业务、手机交费、甚至是我们学生去食掌打 2 硕士学位论文第一章绪论 饭等等都要排队。虽然随着科技发展的日新月异，这些排队系统一般都能正常运 行，但各个领域的服务工具总难免会有碰上故障的时候，比如由于停电，设备老 化，操作失误导致的系统瘫痪等等。因此，对发生故障以后的排队系统的情况进 行分析也是很有现实意义的。 本文研究的便是几类可修的排队系统。在排队系统故障的讨论中有一个可考 虑的问题：在早期的研究资料中，系统在发生故障崩溃后，系统中原有的顾客并 没有全部离开，而在最近的研究资料中主要研究的是简单的服务模型，即当系统 故障发生后，系统中原有的顾客马上全部失去。排队模型中顾客失去耐心的情形 在过去很多不同的作者都有研究过，失去耐心的原因有可能是顾客已经在队伍中 等了很长时间，也有可能是顾客到达的时候发现已经排了一条很长的队伍便自动 放弃。最近研究的模型多为因为眼务者不在或者服务者不能提供服务而使顾客失 去耐心的情况。m m 1 ，m g 1 ，m m c 和m m o o 排队模型都有被研究过。对 于这种失去耐心的行为可以举个例子：比如有一个想要从电脑信息中心获得信息 的用户，然而该信息中心不能运行或者对用户的要求没有回应。在本文中我们研 究发生重大故障的系统( 导致所有当前的顾客立即失去) ，并且在故障修理的时 候会有顾客因为失去耐心而放弃的情况。 1 2 论文的结构 本文主要研究m m c ( c = l ，l t ) = 卜f ( t ) = e - 射 负指数分布有一个重要的性质，即无记忆性。它的直观意义是，如果把x 解 释为寿命，已知寿命已过了t 年，从t 算起再活y 年的概率与已生活过的年龄t 无关，而且剩余的寿命还服从原来的分布，用概率公式表示为 p ( x f + y l z f ) = p ( x y ) 负指数分布具有无记忆性。即设x 是随机变量，服从负指数分布，参数2 o ， 设t 、y 0 ，则 p ( x f + y i x f ) = p ( x y ) = e “ 从而，可以得到如下定理t 定理2 4 1 ：假设随机变量x 是非负的连续型变量，它的分布具有无记忆性， 则x 服从负指数分布。 负指数分布的无记忆性给排队问题的数学处理带来了很大的方便，如果输入 分布或服务分布是负指数分布，则不管实际排队过程己进行多长时间，要研究从 现在起以后的情况，就好像过程刚开始一样，只要知道当前系统处的状态就够了， 在此以前的经历可以不考虑。这种无记忆性也叫做无后效性，也叫马尔可夫性。 泊松过程的定义： 定义2 4 2 ：若离散随机变量x 的概率分布为： 只= p x = f ) = 了a - p ，i = 0 ，1 ，2 ，。 其中旯( o ) 为常数，则称x 服从参数兄的泊松分布，其期望平均值e x 】- 五， d x 】= 五。 考虑单个到达的输入过程，令n ( t ) 表示在时间( 0 ，t 】内到达的顾客数，则 n ( t ) 2 0 是连续时间参数的随机过程( 计数过程) ，如果满足： 1 n ( 0 ) = o 2 n ( t ) 0 有独立增量 3 n ( t ) o ) 有平稳增量，且对任意t 0 与s 0 ，有 尸 ( f + j ) 一( f ) ：尼) ：翌堕三g 沁，k ：o ，1 ，2 k ! 其中见( 0 ) 为常数，则称 n ( t ) o ) 是泊松过程，也称p o i s s o n 流或最简单流。 硕士学位论文第二章预备知识 泊松过程具有如下特点： 1 平稳性。在任何一段长度为t 的时间区间内，出现任意数量事件的概率只 与t 有关，而与t 所处的位置( 或与起始时刻) 无关。所以记参数a 为平稳流的强 度。 2 到达过程具有无后效性，即在不相交的时间区间内到达的顾客数是相互独 立的。在 t ，什a t 】内到达的顾客数只与区间长度有关，而与起点无关，而且服 从泊松分布。 3 普通性。在同一瞬间，多于一个事件出现的概率( 或同时到达系统有两个或 两个以上顾客的概率) 可忽略不计。 泊松过程与负指数分布的关系： 定理2 4 2 ： n ( t ) o ) 是参数五的p o i s s o n 流的充分必要条件是 t n ，z 1 ) 独 立，同参数五的负指数分布。其中 丁。，胛1 j 为到达的问隔时间序列。 定理2 4 3 ：设 n ( t ) 0 ) 是参数五的p o i s s o n 流，每一到达顾客以概率 p ( o 0 ，均为常数，则称随机过程 ( f ) ，t 0 ) 为有限状态e = 0 ， 1 ，2 ，k ) 上的生灭过程。 当系统状态为可列无限状态e = 0 ，1 ，2 ，) 时，则称为无限状态的生灭 过程。 令p ( f ) = p n ( t ) = ) ，j e ，则由全概率公式，有： p ( t + a t ) = p n ( t + a t ) = 川( f ) = f ) e ( f ) = e ( f ) g ( a t ) = p ( t ) 1 一l a t p ，f + d ( f ) 】- 卜e l ( f ) 一i f + d ( f ) 】+ e + 。( f ) p ，+ 。f + o ( f ) 】+ p ( f ) o ( f ) j ；- j j _ 2 = e ( f ) 1 一l a t 一z ，a t l - t - a j l e 一。( t ) a t + t t j + i e + i ( o a t + o ( a t ) 于是： p ( t + f a t ) - p ( t ) = ( f ) 一( + 以) 删+ 州f ) + 警 令f 一0 + ，得生灭过程的微分差分方程为： 1 当e = 0 ，l ，2 ，k ) 时，有 i p o t ( t ) = - a o p o ( t ) + # 墨( f 形( f ) = 一。e 一。( f ) 一( + 以) e ( f ) + p ，+ 。e + ，( f ) ，j = l ，2 ，k - 1 1 爿o ) = 一九一。最一。o ) + 地层( f ) 2 当e = o ，1 ，2 ，) 时，有 i瞅f ) = - a o p o ( t ) + # 。8 ( 0 l 耿f ) = 一。e 一。( f ) 一( + 一) e ( f ) + 竹+ 。e + ，( f ) ，= l ，2 ， 定理2 6 1 ：在e ( f ) = ，l 。i m 。e ( f ) 存在的条件下，j c e ，有毁0 亿) = o ，e 。 证明：因为微分差分方程组等式右边的极限存在，于是l i m p j ，( f ) 存在，j e 。 若存在一个状态厶ee ，使得，l 。i m 。乞7 ( t ) - - d ：0 ， 硕士学位论文第二章预备知识 不妨设d o ，则对所有的，( o ”1 上! 入入一。 r ， 特别地，当九= 入= = 一。= a ，地= 心= = 地= p 时， 1 2 三、 一y l 一入p = 一1i 产。川 ， ， 一+ 、， ：与p | i ，- ，o 叫 昂 e 硕士学位论文第二章预备知识 只要垒 1 ，则 p ，：0 ，1 ，2 ，) 存在，而且 “ 。 2 7 马尔可夫过程 p ：( 1 - 查) ( 垒) 7 ，：0 ，1 ，2 ，。 弘弘 马尔可夫过程是一类很重要的随机过程。这一类过程的特点是：当过程在时 亥 j t o 所处状态已知时，气以后过程所处的状态与f 0 以前所处状态无关。这个特性 叫做无后效应，也叫马尔可夫性。通俗的说，就是“已知现在，将来和过去无关。 定义2 7 1 ：设 x ( f ) ，t n 为一随机过程。t ，f = l ，2 ，n ，且 t 2 乙。 如果对状态空间s 中的任意状态五，x 2 ，吒_ ，x ( t ，) 的条件分布函数满足： p x ( t ) xix ( t 1 ) = x - i ，x ( q 一2 ) = 一2 ，x ( t i ) = 五) = p x ( t ) x i x ( t 。一1 ) = 吒一1 ) ，x r 则称 x o ) ，t t ) ，具有无后效应性或马氏性，并称 x ( f ) ，t t ) 为马尔可夫过程， 简称为马氏过程。 一般记p x ( 乙) 引x ( t 一，) = x 一。) 为f ( t 小x 一。；乙，x ) ，即 f ( t - l ，吒一l ；f 。，x ) = p x ( t ) x x ( t 川) = x i ) 称它为马氏过程的转移概率分布。它满足切普曼柯尔莫哥洛夫( c h a p m a n k o l m o g o r o v ) 方程： + 哩 f ( s ，x ；t ，y ) = if ( u ，z ；t ，y ) df ( s ，x ；u ，z ) ，s u t t 其中df ( s ，x ；u ，z ) 表示对f ( s ，x ；u ，z ) 关于变量z 微分。 证明：由全概率公式得 f ( s ，x ；t ，y ) = p x ( t ) yx ( s ) = x ) = ，尸 x ( f ) y x ( “) = z ，x ( s ) = x 矽= p x ( “) zx ( s ) = z ) = ，p x ( t ) y l x ( ) = z 埏p x ( “) z i x ( s ) = x ) = ，f ( u , z ；t ，y ) d ：f ( s ，石；“，z ) 硕士学位论文 第二章预备知识 定义2 7 2 ：设随机过程 工( f ) ，f t ) 的状态空间s 为r 中的可列集。如果对 t 中任意n 个 乞 0 的状 态s ，k = 1 ，2 ，l 一1 ，与状态s 均有 p x ( ) = ix ( 厶一。) = ，x ( t o 一：) = 一：，+ ，x ( ) = f 1 ) = 尸 x ( 乙) = 乇i x ( 厶一。) = 一，) 则称 x ( f ) ，t et ) 为马尔可夫链，简称马氏链。如果t 还是可列离散集，则称 x ( f ) ，t t ) 为离散参数马氏链。如果t 是连续参数集，则称 x ( f ) ，t t ) 为连续 参数马氏链。 2 8 连续时间马尔可夫链 考虑取值在非负整数集e 上的随机过程x = 鼍，t t = o + o u ) ) ，如果对一 切t 中的时刻0 t t 乞 o 时，称 弓( s ，t ) = p 置= i x s = 磅 ( s t ) ( 2 - 2 ) 为系统x 在s 时刻处于状态i 条件下，t 时刻转移到i 的转移概率。它表示在时 刻m 时x 。耿i 值的条件下，在下一时刻m + l 时以+ 。取j 值的概率。上式的直观 意义是，给定状态x 。，则系统的将来状态与过去状态是条件独立的。即已知系 统的现在状态，则系统的将来与过去历史无关，称这种特性为无后效性或马尔可 夫性。这罩乞( m ) 具有以下两个性质： 1 0 弓( ，z ) 1 ( i ，j e ) 2 p o ( m ) = 1 ( i e e ) ， 当式( 2 2 ) 只与t - s 有关时，则称它为x 的齐次转移概率函数，这时马氏链x 为连续时间齐次马氏链。容易验证下述的k c 方程成立 乞( 件s ) = p i k ( t ) p k j ( s ) ( 2 3 ) 1 4 硕士学位论文第二章预备知识 并且弓( f ) 0弓( f ) = l ， 称p ( t ) = ( 弓( f ) ) 为与氏链x 的开次转移矩阵。 如果她还满足下述的标准性条件 ，l 。i m 。只，o ，= 毛= 爱翥：三； 则称p ( t ) 是x 的标准转移矩阵。对于标准转移矩阵有如下引理： 引理2 8 1 ：设马氏链x 的转移矩阵p ( t ) 是标准的，则有 ( 1 ) 川l i m + 半- - q i = - p ：，( o ) ( ) ( 2 ) 牌半鸹= ( 0 ， p + o 。，z 从而由k c 方程知 只心) ( 既( 三) ) 一 0 ，z 于是，对一切t 0 ， f ( t ) = - l o g p ，如) 有定义且非负有限，注意到 只，o + t ) p i i ) p ，o ) 故有f ( s + f ) f ( s ) + f ( t ) ( 2 7 ) ( 2 8 ) 由数论知，对任恿t 0 ，h 0 ，必存在整数n ，便t = n h + ，0 h ，由( 2 - 7 ) 知 盟 o ，有 盟 l i m 趔 t 一o + h 因此 而巡 s u p 地 jt 一o + h 若置s u p 掣：g ， 则有l i m 掣：吼 ( 2 - 9 ) 晶后由式( 2 7 ) ，( 2 9 ) 得到： 1 5 硕士学位论文第二章预备知识 幽：| - - e - f ( h ) ： 1 + 0 ( 1 ) f ( h - - - 堕) _ 吼( j j l _ o + ) hh。h 1 1 、7 即得证( 1 ) 。对( 2 ) 类似可证。 因为f 鱼盟：生型，两边令f _ o + ，得到： i ft o g f g ，= 一( o ) 在劬= q i 时，称马氏链是保守的。 当e 只含有限多个状态时，显见，此时的马氏链必是保守的。 由k c 方程知 或者 彰( f ) = z , q 可p i k ( t ) - q j p u ( t ) 幽h= 喜趔h 业一幽h 删 智 “” 令h - 0 + ，得到 l i m + 掣h= 哿喜螋h 趔嘲 一o + 一o + ：三 有如下定理： 引理2 8 2 ：( k 氏向后方程) 如果( 既( f ) ) 是标准的，那么，对一切i j 及f 0 有： 岛亿) = q ，k p o ( t ) - q i p o ( t ) ( 2 - 1 0 ) 有： 引理2 8 3 ：( k 氏向前方程) 如果( 既( f ) ) 是标准的，那么，对一切i j 及f 0 乃亿) = q 可p i k ( t ) - q ，岛( d ( 2 - 1 1 ) 若采用矩阵记号，令q = ( 乳) ，p 缸) = ( 岛亿) ) ，那么式( 2 - 1 0 ) 和( 2 1 1 ) - 7 分别写成( q 为密度矩阵) p 缸) = q p ( t ) ( 向后方程) p ，( f ) = p ( t ) q ( 向前方程) 由此可得矩阵指数形式的解 1 6 硕十学位论文第二章预备知识 其中q o 为单位矩阵i 。 黔肚喜争” 1 7 硕士学位论文第三章i v l m 1 模型 3 1 模型 第三章m m 1 模型 在一个l v l l v l 1 排队模型中，服务台数量为一个，顾客的到达服从参数为五的 泊松分布，服务时间b 服从参数为1 的负指数分布。系统在正常服务状态时发 生故障的概率服从参数为7 7 的负指数分布，也就是说，系统维持正常工作状态的 概率服从参数为l r 的负指数分布。当系统发生故障时所有当前的顾客全部丢 失，并且系统马上进入修理状态。修理时间服从参数为y 的负指数分布。系统处 于不能工作状态时到达的顾客变的没有耐心：每个顾客有他独立的“失去耐心时 间 t ，服从参数为f 的负指数分布，即如果在时间t 到达的时候系统仍然没有 恢复正常，顾客就会放弃并且不会再回来。 上述过程产生了如下的一个二维连续时间马尔可夫过程。我们令j 表示系统 的状态：j = o 表示系统发生了故障，处在修理当中，此时如果系统中已经有n 个 顾客，新到达的顾客就会自动离丌，即系统的容量为n ，系统以m m 1 n 1 排 队模型运行( 因为系统在修理当中时，新来的顾客看到等待的人到达一定的数量， 会自动放弃等待) ；j = l 表示系统在正常工作中，正在服务顾客，此时系统以 m m 1 o o 排队模型运行，表示系统的容量为无穷。 3 2 平衡方程和产生的函数 令厶= p j _ j ，l - - n ( j = o ，1 ；n = o ，1 ，2 ，) 表示系统处于该状态的概率。 其中j 为系统所处的状态，是正常工作还是发生了故障。l 表示此时系统中 的顾客数。 令弓= 厶表示系统处于状态j ( j 2 0 ，1 ) 的概率。 n = o 假设系统是可以达到平稳状态的，则在平稳状态时，可以得出如下的平衡方 程： i 以：o ( a + 7 ) p o o = 昂- + 7 7 n = o 只一= 专只- + 叼只 j = o l l ，z n ， ( 入+ p + 叩) 片。= a p , ，。一l + 肛月，。+ i 将( 3 1 ) 式累加 昂+ 露= 1 a 焉+ r p o o = 异i + 叩日 a 昂。+ ，y 异。+ 异。= 入民+ 2 p o ： a r 2 + 7 + 2 p 0 2 = 入r i + 3 昂3 7 只+ 联r = a 昂一， ( 3 - 3 ) 含a 和的项容易看出左右全部可以抵消掉，其余项累加，再利用 髟= 厶可得到： n = o 7 p o = 7 7 日 结合( 3 - 3 ) ，( 3 - 4 ) 可以解出： p o - 熹耻南7 十叩一y 十叩 ( 3 4 ) ( 3 5 ) 当然，观察这个状态过程本身，不管这个系统处于哪种状态，都是关于时问 分布概率r 和日的一个交互式更新过程。 定义q ( z ) = p i n z ” ( j = o ，1 ) 为状态j 的p g f ( p r o b a b i l i t yg e n e r a t i n g n = o f u n c t i o n 概率发生函数) 。 由( 3 1 ) 变形得以下方程组： a + ，y 异。= 蜀。+ 7 7 弓 z a p o i + z - y p o l + z r 1 = z 入异o + 2 z p 0 2 ； z - 1 入昂， ，一l + z 一 r p o ，一l + ( 一1 ) z - 1 乌，一l = z u - l a p o ，一2 + 胞一昂，一i z 7 昂+ z v 咒= z a r ，一l 将上式累加得 1 9 硕士学位论文 第三章m m 1 模型 入( 民+ z 昂l + z 2 昂2 + + z 一t o 一i ) + 7 ( p o o + z 昂l + z 2 岛+ + z 昂) + ( z p o o + z 2 昂l + + z 昂一1 ) = 卵日+ ( 昂i + 2 州+ + 胞p o ) + 入( z 岛o + z 2 异l + + z 昂一1 ) 根据定义： g o ( z ) = + z p o l + z 2 昂2 + + z 昂 ， g 0 7 0 ) = p o l + 2 z 昂2 + + z _ 1 昂 则( 3 6 ) 式可写为： 入( g o ( z ) 一z e o v ) + ，y g o ( z ) + f z g o ( z ) = 们+ 毒g 0 7 ( z ) + 沁g o ( z ) 一a z + 1 p o 整理得： 毒( 1 一z ) g 0 7 ( z ) = ( a - a z + 7 ) g o ( z ) - n p , 一入只 ，z ( 1 - z ) 利用平衡方程( 3 - 2 ) ，第n 个方程乘以z ”一， a p , o + 7 7 卑o = ) ，p o o + u p , i z 入只i + z p 日l + z , t p , l = z 入异o + z p 只2 + z ，y 只l z 入日。v + l + z 肛只， ，+ l + z 叩暑，+ i = z 入口+ z u p , ，+ 2 ： 然后累加，再利用 得： 整理得： g l ( z ) = 日o + z p , l + z 2 名2 + + z # + 入g l ( z ) + 7 7g i ( z ) + p ( g l ( z ) 一p o o ) ：7 c o ( z ) + p 鱼丛互盥+ 入zg l ( z ) z ( 3 - 6 ) ( 3 7 ) ( a z - u ) ( 1 - z ) + r z g l ( z ) = y z g o ( z ) 一p ( 1 - z ) p , o ( 3 - 8 ) 由前面( 3 1 ) 可得 ” p o o + + p o ，= _ r 7 十叩 ( ，y + n ) p o v = 入昂_ l ( 3 - 9 ) 1 n 1 ，( 入+ p + 叩) # 。= 入日，。一l + p 眉，。+ i 由上式易知 7 民+ t p o 。= 7 7 彳 又由暑+ e o = 1 ，可得： 结合 p o o + 耻熹 一v 异= 高 卫切战 7 = i | i ( 1 i 一 印 鸲 o ， 民 n 一 k 硕士学位论文第三章m m 1 模型 易解出 气= 高黯 又由g ( z ) ，目乞】的定义可知： 耻万犏 g o ( 垆心一再热+ 万丽a z 磐g 0 ，( 垆弛】= 只。= 雨磊丽 由j = l 时的平衡方程同样可以求出： ( a z 一肛) ( 1 一z ) + 叩z g l ( z ) = y zg ! 。( z ) 一p ( 1 一z ) 只。 对上式在z = l 处微分可得： n e 厶 + 肛( 0 一只o ) = 入片+ 7 e l o 】 由前面介绍的方法可解出 p i o 焉) 其中 一一( a + p + 叩) 一( 入+ p + 叩) 2 - 4 a # o 一 2 a 显然曰，昂，e l o 均已经计算出来了，则可以求出研厶】。 3 3 逗留时间 令s 表示任意一个该系统中的顾客的总逗留时间，不管他是否完成了服务。 利用l i u l e 公式有： 1 e s 】= e l o p o + e 厶 只】 ( 3 - 1 5 ) a 令s m 是系统中一个完成服务的顾客的总逗留时间，他到达该系统时系统的 状态为( j ，n ) 。因为以后到达的顾客不会影响之前顾客的逗留时间，我们有： 研s 。】- 圭( 士) ( 3