（运筹学与控制论专业论文）服务台修理有延迟的mg1∞可修排队系统.pdf

电子科技大学硕士学位论文 摘要 本文研究了服务台修理有延迟的mi gl 1 / ，可修排队系统，通过对系统的详 细分析，得到了系统一系列重要的排队论指标和可靠性指标。具体情况如下: ( 1 )利用更新过程理论和全概率分解技术， 讨论了从任意初始状态出发队长 分布的瞬态解和稳态解，并得到了队长平稳分布的递推表达式: p 。 二 1 一 p p ，一 l (a (as ，一 ,6)f 1一 g (t)黔一场 i-k=i p j _ k 1 一 艺a ; ) , l ， 并进一步求得了系统的稳态队长分布的母函数 p ( z ) ( 1 一 户 ) ( 1 一 z ) 9 ( .1 ( 1 一 z ) ) 万 ( a ( 1 一 z ) ) 一 z !: 卜1 ( z )讨论了系统的等待时间分布，求得了平均等待时间和平均逗留时间: w p 2 + a 2 a 2 v 一 2 a ( 1 一 p ) w ,3 + a 2 c 2 2 .1 ( 1 一 万 ) ( 3 )讨论了系统的输出过程， 了1.jwe. - 1 .m,( t ) k l m ， 冲国r 求得了长期单位时间内离去顾客的平均数: 元p1 ( 4 ) 讨论了服务台的不可用度，得到了稳态不可用度: a a ( 1 + 脚) y + a ( 1 + 介) p y ( a + y 十 a 8 y ) p( 1 l i m (d ; ( r ) = a l l + 脚) a+ y + a f y , p_ 1 ( 5 ) 论 了 ( 0 , 刁 内 服 务 台 平 均 故 障 次 数 ， 求 得 了 长 期 单 位 时 间 内 的 平 均 故 障 次 数: lim m ,p ) , - a . t 1 p之1 ( 6 )讨论了服务台的平均首次故障时间: 电子科技大学硕士学位论文 f o f ; (t ) - 生 +b ( a ) a兄 一 7 b ( a ) ( 7 )讨论了广义忙期中服务台的平均故障次数: a l 风卜p ) . 户_ 1 !、.、 一- n 凡 ( 8 ) 讨 论 了 服 务 台 的 失 效 时 间 ， 并 进 一 步 得 到 了 当 ， 充 分 大 的 时 候 ， (0 , 月 内 服务台的平均失效时间的近似表达式: a a ( i + 脚 ) y + a p+ 汤) ,u y ( a+ y + a o ) , ) t , 万 1 关键词:修理延迟，队长，广义忙期，离去过程，等待时间，停时，逗留时间， 故障次数，不可用度 电子科技大学硕士学位论文 a b s t r a c t i n t h i s p a p e r , t h e m/ g/ l / o o r e p a i r a b l e q u e u e i n g s y s t e m w i t h r e p a i r d e l a y t i m e i s s t u d i e d . s o m e i m p o r t a n t q u e u e i n g q u a n t i t i e s a n d r e l i a b i l i t y q u a n t i t i e s a r e i n d e t a i l d i s c u s s e d a s f o l l o w s : ( 1 ) b y u s i n g t h e r e n e w a l p r o c e s s t h e o r y a n d t h e t o t a l p r o b a b i l i t y d e c o m p o s i t i o n t e c h n i q u e , w e o b t a i n t h e t r a n s i e n t a n d e q u i l i b r i u m d i s t r i b u t i o n s o f t h e q u e u e l e n g t h f r o m a n y i n i t i a l s t a t e n( 0 ) = i ， w e d e r i v e t h e r e c u r s i o n e x p r e s s i o n o f t h e e q u i l i b r i u m q u e u e l e n g t h: p 0 = 1 一 卢 ， ，= i wa , ，一 ; )f l，一 “ t )1兴产 一 dt l1e -dt+ i p i_k k=1，一 k 一 ),j ， a n d t h e g e n e r a t i n g f u n c t i o n o f e q u i l i b r i u m q u e u e l e n g t h d i s t r i b u t i o n p , , j ? o ) i s g i v e n b y p ( z ) =( 1 一 p ) ( 1 一 z ) 万 ( a ( 1 一 z ) ) a ( a ( 1 一 z ) ) 一 z iz i o o i s g i v e n s t u d i e d , a n d t h e m e a n v a l u e o f b y lim m ,(1 ) 口 冲.t p_ 1 ( 4 ) w e e q u i l i b r i u m d i s c u s s e d t h e u n a v a i l a b i l i t y o f t h es e r v i c e s t a t i o n t h e u n a v a i l a b i l i t y i s g i v e n b y a a ( 1 + 脚) 沙+ a ( 1 + 脚) lim (d , ( t ) ,u r ( a + y + a/3) a l l + fl y ) _ _ 一， f-1 a+ y十 a p y p 1 ( 6 ) t h e m e a n v a l u e o f t h e f i r s t f a i l u r e t i m e o f t h e s e r v i c e s t a t i o n i s g i v e n b y f ，( = 生 + 竺一 a 三 “ a 一 肋( a ) ( 7 ) w e d i s c u s s e d t h e a v e r a g e f a i l u r e n u m b e r o f t h e d u r i n g g e n e r a l b u s y p e r i o d . i t s m e a n v a l u e i s g i v e n b y s e r vi c e s t at i on e n a / 风1 一 句， 声1 !、.l - ( 8 ) t h e f a i l u r e o b t a i n e d t h e c l o s e t i m e o f s e r v i c e s t a t i o ni s s t u d i e d , e x p r e s s o f t h e a v e r a g e f a i l u r e t i m e o f f u r t h e r m o r e , w e s e r v i c e s t a t i o n d u r i n g (0 , t a s t e n o u g h l a r g e . a a ( l + / 6 y ) y + a ( 1 + ,6 y ) e d ( t ) i n (o)二 ” p 7 ( a + y + a 8 7 ) t , 万_ 1 k e y w o r d s : t h e r e p a i r d e l a y , q u e u e l e n g t h , g e n e r a l b u s y p e r i o d , d e p a r t u r e p r o c e s s , w a i t i n g t i m e , s t o p t i m e , d e l a y i n g t i m e , f a i l u r e n u m b e r , u n a v a i l a b i l i t y . w 独 创 性 声 明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。 据我所知， 除了文中特别加以标注和致谢的地 方外， 论文中不包含其他人己经发表或撰写过的研究成果， 也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签 名 :书 y -2-日 期 : 14 -0 s 年! 月 叮 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、 使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘， 允许论文被查阅和借阅。 本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索， 可以 采用影印、 缩印或 扫描等复制手段保存、 汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名 、 的 . j. g 9 、 可 il y ? 导师签名 日期: 电子科技大学硕十学位论文 第一章排队系统概述与预备知识 1 . 1排队系统概述 排队论又名随机服务系统，源于e r l a n g 关于电话服务的研究。第二次世界 大战以后得到迅猛发展。 二十世纪中期以来， 随着计算机通讯网络、 柔性制造系 统( f m s ) 、异步转移模式 ( a t m )等高新技术领域的发展， 排队论在军事、生产、 经济、管理、交通等领域得到广泛应用。 排队现象在生活中随处可见。 比如顾客到商店购物， 当服务员忙时须排队等 待; 病人到医院就诊， 当医生忙时须排队等待就诊: 上下班乘坐公共汽车须排队 上下车等等。 排队现象是排队论研究的对象， 它是由两个方面构成的， 一方面要求得到服 务，而另一方面提供服务。我们把要求得到服务的人或物 ( 设备)通称为顾客， 给予服务的服务人员或服务机构通称为服务员或服务台。 顾客和服务台就构成一 个排队系统。 1 . 1 . 1排队系统的基本组成 尽管排队系统形形色色， 但从决定排队系统进程的主要因素看， 它主要由三 部分组成:输入过程、排队规则和服务机构，下面分别加以说明。 1 ) 输入过程 输入过程是描述顾客来源是按怎样的规律抵达排队系统。a ) 顾客总体数: 顾客的来源可能是有限的， 也可能是无限的， 例如工厂内发生故障待修的机器是 有限的;到达窗口购票的顾客总体可以看成是无限的 因为不存在最大的限制 数) 。b ) 到达的 类型: 顾客是 单 个到达， 或是成 批到 达， 例如 工厂内 发生 故障 待 修的机器是单个到达: 在库存问题中， 进货看成顾客到达， 就是成批到达的例子。 c ) 相继顾客到达的间隔时间 服从什么样的概率分布， 分布的 参数是什么， 到达的 间隔时间之间是否独立。 2 ) 排队规则 电子科技大学硕十学位论文 排队规则是指服务允不允许排队， 顾客是否允许排队。 在排队等待的情形下 服务的 顺序可以 分为;a ) 损失 制: 顾客到达时， 若所有 服务台 均被占 服务机构 又不允许顾客等待， 此时， 该顾客就自 动离去。 例如通常使用的损失制电话系统: b ) 等待制:顾客到达时若所有服务台均被占，它们就排队等待服务。 在等待制 排队系统中，服务顺序又分为:先到先服务 ( f i f o ) ，即顾客按到达的先后顺序 接受服务;后到先服务 ( l i f o ) ，例如情报系统、天气预报资料总是后到的信息 越重要， 要先处理; 随机服务， 即 在等待的 顾客中随 机地挑选一个顾客进行服务， 例如电话员接线就是用这种方式工作: 有优先权的 服务， 即在排队等待的顾客中 某些类型的顾客具有特殊性， 在服务顺序上要给予特别待遇， 让他们先得到服务， 例如病危人先治疗; 带小孩的顾客先进站等。 优先权又分强拆型优先权和非强拆 型优先权。 强拆型优先权是指这类顾客到达时， 无论正在接受服务的顾客是否服 务完毕， 都必须立即终止服务而转为接受这类顾客并给予服务， 例如医院对病危 人的服务。 非强拆型优先权是指这类顾客到达时， 必须等待正在接受服务的顾客 服务完毕后才会得到服务。 c ) 混合制: 损失制与等待制的混合， 分为队长( 容量) 有限的混合制系统， 等待时间有限的混合制系统， 以及逗留时间有限制的混合制 系统。 3 ) 服务机构 研究服务机构的主要方面分为:a ) 服务台的 数目。 多个服务台的 情行下， 是 串 联还是并联;b ) 顾客所需要的 服务时间服从什么样的概率分布，每个顾客所 需要的服务时间是否独立， 是成批服务还是单个服务等。 常见顾客的服务时间分 布有:定长分布、负指数分布、超指数分布、k 阶爱尔朗分布、几何分布、一般 分布等。 由于输入过程、 排队规则和服务机构的复杂多样性， 形成了各种各样的排队 模型， 因此， 在研究一个排队系统之前， 首先要弄清这三部分的具体内 容和结构。 i . ， . 2 描述排队系统的主要指标 1 ) 队长与等待队长 队长是指在系统中的顾客数 ( 包括正在接受服务的顾客) ，而等待队长是指 在系统中排队等待的顾客数。 它们都是随机变量， 是顾客和服务机构双方都十分 关心的数量指标，应确定他们的分布和有关矩 ( 至少是期望平均值) ，显然，队 长等于等待队长加上正在被服务的顾客数。 电子科技大学硕士学位论文 2 )顾客在系统中的等待时间和逗留时间 顾客的等待时间是指从顾客进入系统的时刻起直到开始接受服务止的这段 时间。 而逗留时间是顾客在系统中的等待时间加上服务时间。 在假定到达与服务 是彼此独立的条件下， 等待时间与服务时间是相互独立的. 等待时间和逗留时间 是顾客最关心的数量指标，应用中关心的是统计平衡下它们的分布及期望平均 值。 3 )系统的忙期与闲期 从顾客到达空闲的系统， 服务立即开始， 直到系统再次变为空闲， 这段时间 是连续繁忙的时间，我们称为系统的忙期，它反映了系统中服务员的工作强度。 与忙期对应的是系统的闲期，即系统连续保持空闲的时间长度，在排队系统中， 统计平衡下忙期与闲期是交替出现的。 而忙期循环是指相邻的两次忙期开始的间 隔时间，显然它等于当前的忙期长度与闲期长度之和。 4 )输出过程 输出过程也称离去过程，是指接受服务完毕的顾客相继离开系统的过程.刻 画一个输出过程的主要指标是相继离去的间隔时间和在一段已知时间内离去顾 客的数目， 这些指标从一个侧面也反映了系统的工作效率。 此外， 在不同的排队 系统中， 还会涉及到其他数量指标， 在损失制和混合制排队系统中， 顾客的损失 率及单位时间内 损失的平均顾客数， 在多服务台并行服务的系统中， 某个时刻正 在忙的服务台数目，以及系统的利用率等. 1 . 2泊松过程与更新过程 1 . 2 . 1 泊松过程 定 义i ii考 虑 单 个 到 达 的 输 入 过 程 ， 令n ( t ) 表 示 时 间 (0 ， tl 内 到 达 的 顾 客 数 ， 则 n ( t ) ; t _ 0 1 是连续时间 参数的随机过程 ( 计数过程) ， 如果满足: 1 )n ( 0 ) = 0 2 ) n ( t ) ; t ? 0 有独立增量 变量n ( t , ) 一 n ( 0 ) , n ( t z ) 一 n ( t , ) , 即 对 任 意 取的n 个时 刻: 0 t ，t 2 _ o s _ 。 有 电子科技大学硕十学位论文 _、 、 ，、 ， 、 ( 1 s ) k_ j . _ f ; n(t+s ) 一i v ( t ) 二x ( =e一， k=u,1,/ k ! 其中a ( 0 ) 为常数，则称 n ( t ) ; i _ 0 ) 是泊松过程，也称p o i s s o n 流或最简单流。 上述定义中的第 2 )表示到达过程具有无后效性，即在不相交的时间区间内 到达的顾客数是相互独立的， 第3 ) 表示在( t , t + t o 内 到达的顾客数只与区间长 度有关，而与起点无关，而且服从泊松分布。 在随机服务系统的排队现象的研究中， 经常会自 然地引导到泊松过程模型的 应用， 例如，到达电话总机的呼唤数目和到达服务机构 ( 如商店、 车站等)的顾 客数目 常常都可以用泊松过程来模拟。 泊松过程与负指数分布有着密切的关系，下面定理鲜明地反映了这一关系。 定 理 1 ( i n ( t ) ; t _ 0 是 参 数a 的p o i s s o n流的 充 分 必 要条 件 是 t ， ， n in z 独 立、同参数a 的负指数分布， 其中 r , n ? 1 ) 为到达的间隔时间 序列。 1 . 2 . 2 更新过程 定 义2 (2 设 xx 2 , 是 独 立同 分 布 的 非 负 随 机 变 量 序 列 ， 它 们 的 分 布 函 数 为 f ( t ) ， 均值为f， 且满足p x n 0 ) 1 ， 令 s o = 0 ,s-x ,+ x, + x,+ - - - + x; n ” 1 ,2 创门 是 这 些随 机 变 量 的 部分 和， 显 然p s s t 卜f (0 )( 1 ) . n = 0, 1 ,2 , ， ， 其中f (n 1( 1 ) 是 f ( t ) 的n 重卷积，并有 f (0)(t， 一 1 z0 tu 令n ( t ) = s u p ( n :sx 2 ， 一 所 产 生 的 更 新 过 程 ， 称x ， 为 更 新 寿 命， s ， 为 更 新时 刻( 再 生 点 ) 。 显 然 n ( t ) 表 示 ( 0 , t 时 间 内 的 更 新 次 数 。 令 m ( t ) 一 e n ( t ) ) ， 则 m ( 1 ) 表 示( 0 , t 内 的 平 均 更 新 次 数 。 易 知 n ( t ) = k ) 等 价于 s , _ t s , ) ， 所以 m (r ) 一 艺 k p n (。 一 k ) 一 艺户切， 我 们 称 m ( t ) 为 更 新 函 数 。 电子科技大学硕士学位论文 对于上述定义的更新过程来说，更新函数可以完全确定该更新过程。 设分布函 数f ( t ) 有密度f ( t ) ， 则有如下定 理 定 理2 13 1设后( s ) , f ( s ) 分 别 表 示 更 新函 数 和 密 度函 数 的 拉 普 拉 斯 变 换， 则 f ( s ) s m( s ) 1 + s m( s ) 下面我们不加证明的给出如下定理: 定 理3 川( 基 本 更 新 定 理) 令f t = f td f (t) 0o ， 则 定 理4 14 1若f ( t ) 不 是 格点 分 布， 则 有 lim m (t + a ) 一 m (t ) 一 a 产 咔 .刀 注意:当u 二 ，时，以 上二个定理中的极限均为0 . 定 理5 111 ( 更新函 数的 渐 近展开) 设f ( t ) 是非 格的 分布函 数， 则 有 一 : ， 。 、 t , _ q 2_ , z 1 1 1 lj 1 . 1 , ) 一一 1 一- 侧 ， - ， r 一 份 。 -一 声 一2 p a 其 中 lu 一 f x d f (x ) oo ,q z= f x 2d f (x ) - ,u z 0 , f e - a (t )d t 是 收 敛 的 ， 且极限l i m a ( t ) 存在， l ima ( t ) = l i m s b e 一“ a (t) d t 3 . 4 关于拉普拉斯一司 梯阶变 换的阿贝尔定理6 1 设对t z o , a ( t ) 在每 一个有限 区间 上是有界 变差的， 的， 且极限l im a ( t ) 存在， 则 如 果 对 r (s ) 0 , f 。 一 ” d a ft ) 是 收 敛 l i ma ( t ) 一 li m f e d a (t) + a (0 )o* 3 . 5 关于拉普拉斯一司 梯阶变换的托贝尔 ( 7 a u b e r i a n )定理b 如 果 对 ， : 0 , a (t) 是 单 调 不 减 的 ， 对 ， (s ) 0 ,0 (s ) 一 e -sd a (t) 存 在 ， 且 对 ; : 0 , 有 (卜 共 ，一 。 a ( t ) 二 at i ( r + 1 ) , t -4 00 其中a 为常数，1 ( r ) 为r 一函 电子科技大学硕十学位论文 第二章排队系统的主要研究方法及研究现状 2 . 1 主要研究方法 作为随机运筹学和应用概率论中最有活力的研究课题一排队论， 它的发展经 历了近一个世纪， 形成了一系列比较成熟的研究方法， 并取得了丰硕成果。 下面 我们介绍一些常用的方法。 2 . 1 . 1 生灭过程法 对于输入过程为p o i s s o n 流， 顾客实际所需要的服务时间为负指数分布的排 队系统，它的排队过程就是一个生灭过程。顾客到达就是 “ 生” ，服务完成就是 “ 灭少 。通过建立微分差分方程和平衡方程可以求出系统任意时刻的瞬态和稳态 队长。生灭过程法在休假排队系统中也有应用，见 8 1 , 9 . 2 . 1 . 2 嵌入马尔可夫链法 对于顾客按照p o i s s o n 流到达与负指数服务时间的简单排队系统，系统在任 何时刻都具有良好的马尔可夫性质。 但对于一般服务或一般到达的排队系统， 并 不是在任何时刻系统都具有马尔可夫性质， 只是在某些特殊的随机时刻系统才具 有这种性质。 我们称这种随机时刻为系统的再生点。 利用再生点可将一般到达或 一般服务的排队系统化成马尔可夫链。 然后利用更新过程有关的知识来分析系统 的若干指标。这种方法称为嵌入马尔可夫链法。 例如: 对于mi g i i i 。 排队系统，由 于服务时间是一般分布， 系统的队长过程 n ( r ) , r ? 0 ) 并不是在任意时 刻都具有马尔可夫性质， 但当我们把注意力集中 在顾 客服务完毕离开 系统的 瞬间时， 该时 刻留 在系统中的 队 长过程 n ( r ) , r z 0 1 就具 有 马尔可夫性质。 嵌入马尔可夫链法也是研究休假排队 模型的有力工具， 例如在mi g i 1 空竭 服务多重休假和mi g i 1 空竭服务单重休假排队系统中，取服务完成和休假终结 时 刻为 嵌 入点 ， m。 表 示 嵌 入时 刻 系 统中 的 顾客 数， 去 ， 视 这些时 刻 为 服务 完 成 还 是 休假结 束而 取 值1 或。 。 ( m , j) 是队 长 过 程的 嵌入马 尔可 夫链 1 0 ) 。 在 休假排队中，文 1 1 指出嵌入马尔可夫链法对于非 p o i s s o n到达时往往很难构 造， 因此不便推广到一般情况。 文献 1 2 1 , 1 3 就负指数休假的g i i mi i 使用了 电子科技大学硕十学位论文 嵌入马尔可夫链法。 2 . 1 . 3 补充变量法 对于非马尔可夫型排队系统， 除了利用嵌入马尔可夫链的方法处理之外， 一 个最常用的方法是补充变量法， 通过引进补充变量， 使讨论的问题变为一个广义 的马尔可夫过程。 在排队论中，许多排队系统的队长过程 n ( t ) , t ? 0 ) 并非马氏 过程， 通过引进 变量， 将队长过程 n q ) , t _ 0 ) 嵌入在状态空间更复杂的多维过程中， 使新的多维 过程具有马氏性。例如:对于mi gi 1 排队系统，由于服务时间是一般分布，系 统未来队长的分布除了与时刻t 的队长有关外，还与时刻t 正在接受服务的顾客 己 经服务过的时间有关， 队长过程 n ( t ) , 1 ? 0 ) 不是任意时刻都具有马氏性。 引入 补充变量x ( t ) 表示时刻t 正在被服务的顾客已 经服务过的时间。则二维过程 ( ( n ( t ) , x ( t ) ) , t _ 0 为马氏 过程。 这是因为知道现在时刻过程 ( n ( t ) , x ( t ) ) , t ? 0 所 处的状态，系统未来的发展与时刻t 的以前历史无关。文献 1 4 使用了补充变量 法研究了mi g i i i n稳态下消失概率及队长分布。 除上述方法以外， 还有随机步行法， 见【 1 5 ， 修正的l i n d l e y 法， 见【 1 6 等等。 2 . 2 2 . 2 . 1 研究现状 可修排队系统的研究状况 在排队论的研究中， 经典的排队论文献所研究的排队系统几乎都假定服务台 是不发生故障的， 可在实际中却经常遇到服务台发生故障而不能为顾客服务的情 形， 此时需要对服务台进行修理， 服务台被修复后又继续为顾客服务。 对于这种 类型的排队系统， 无论是从排队论的角度还是从可靠性的角度讲， 都是具有实际 价值和理论研究价值的。 1 9 8 2 年， 曹晋华和程侃研究了服务台可修的mi g 1 1 排 队系统。 这篇文章不仅求得了该系统排队论的有关指标， 而且首次从可靠性的角 度获得了该系统服务台的各种可靠性数量指标。1 9 8 5年，曹晋华又讨论了 服务 设备可修的 机器服务模型，即带有限 顾客源情形的 服务台可修的mi g i i 排队系 统。文章既讨论了 排队指标，又讨论了 服务台的可靠性指标。1 9 8 9年， 史定华 详细地讨论了 服务台 可 修的mi g ( 凡l h ) l 1 排队 系 统的 统计平衡理论 1 7 , 1 9 9 0 年， 史 定华、 李 伟 研 究了 可 修 排队 系 统e 翩 g ( m i h ) i l 的 瞬 态 解 1 8 , 1 9 9 5 年， 电子科技大学硕士学位论文 史定华、f r 乃硕又讨论了 服务台 可修的g / i m( m i p h ) l 1 排队系统【 1 9 1 ， 首次讨 论了一个到达间隔为一般分布的可修排队系统。 在假定服务时间， 忙期服务台寿 命都服从指数分布，修复时间是p h变量的条件下，首次证明了 该系统可转化为 一个经典的g i i p hi i 排队模型，给出了系统在稳态下的各种排队论指标和可靠 性指标。 从而将可修排队系统的研究从到达时间由特殊的指数分布发展到到达时 间为一般分布的排队模型。 鉴于高维马尔可夫状态分析法的复杂性， 唐应辉、 唐 小我、 赵玮采用了一种简洁明了的分析方法研究了服务员具有单重延误休假的可 修排队系统， 把休假时间、 服务时间、 修理时间、 和延误休假时间都推广到任意 分布，讨论了队长的瞬态解和稳态解。 近年来， 服务台可修排队系统的研究又开始成为一个热点， 史定华、 唐应辉、 李伟等发表了一系列有关可修排队系统的文章。 至今， 国外研究可修排队系统的 文章仍然只从排队论的角度去讨论，而很少讨论系统的可靠性问题。 然而， 排队 模型和可靠性模型的有机结合是可修排队系统的基本结构， 忽视任何一方面都是 不完善的。 2 . 2 . 2 休假排队系统的研究状况 作为经典排队系统的推广一休假 ( v a c a t i o n ) 排队系统的研究产生于二十世 纪七十年代。 高新技术领域的迅猛发展， 提出了大量的复杂系统设计和控制问题， 经典的排队系统在处理这类问题时表现出极大的局限性， 于是休假排队系统研究 应运而生。 近年来， 休假排队系统的研究成果在众多领域得到了卓有成效的应用。 例如: 中心处理机时间表的设计与控制、 最优保养策略的拟定和实施及生产过程 的效应分析: 在电 子计算机系统和通讯网络中的应用; 数据通讯网络中终端设备 的定时询查系统 ( p o l l i n g s y s t e m )的分析等等。 所谓休假是指为了有效利用资源， 在系统闲期，或者是对服务设施进行调整 维修， 或者是服务员或做其他工作， 或从事辅助性工作， 在这段时间之内 到达的 顾客须等待服务员返回时才能得到服务。这段时间称为服务员休假。 休假行为的描述是由 休假时间分布和导致休假开始或终止的休假规则决定 的。下面介绍仅以 触发休假开始为基础的休假规则及其研究状况。 1 ) 空竭服务( e x h a u s t i v e s e r v i c e 休假规则 服务员一旦开始为顾客服务， 便一直持续到系统内无顾客， 休假只能在系统 电子科技大学硕十学位论文 内无顾客时开始。 在 经 典 的mi g i i 中120 1 , r 表 到 达 率， b s ) ,u - 表 服 务 时 间 的l s t 和 均 值， p = 彻一 ， 0 ) 的负指数分布 f ( t ) = 1 一 。 - , t 0 ， 即到 达是 参数为a 的p o i s s o n 流: 顾客实际 所需的 服务时间 序列 ( x, n _ 1 ) 是独立 同一般分布 g ( t ) , t - 0 ， 记平均服务 时间为 。 ， ， ; 一 f td g (t) o o , 系 统 中 有 一 个 服 务 台 ， 服 务 台 的 寿 命 为 x , 且 服 从 参 数为a ( 0 5 a cc ) 负指数分布 x ( t ) = p x _ 0 ;当 服务台失效时， 不是能马上得到修理，往往有一段修理延迟时间，设修理延迟时间w服从一般 分 布 w (t ) ，且 平 均 修 理 延 迟 时 间 为 “ 。 。 由 于 负 指 数 分 布的 “ 无 记 忆” 性， 可以 推 得行, , n ? 1 ) 相 互 独 立、 同 分 布g ( t ) a 因此我们容易得到下列引理: 3 1 理3 . 1 回如 果 我 们 把元直 接 理 解 为 第。 个 顾 客 的“ 服 务 时 间 ” ， 则 所 研究的系统等价于通常意义下的标准mi gl 1 / 。排队系统， 其中， 输入过程是参 数为a 的p o i s s o n 流， 顾 客 的 服 务时 间 序 列4 z , n ? 1 ) 独 立、 同 分 布g ( r) 。 为研究方便，我们给出 “ 系统闲期”和服务员的 “ 广义忙期，o 系统闲期:是指从系统刚变空的时刻起，直到第一个顾客到达的时刻为止这 一 段 时 间。 令z i 表 示 系 统 的 第j 个 闲 期 长 度， 由 于 顾 客 的 到 达 过 程 是 参 数 为 a ( a 0 ) 的p o i s s o n 流， 因 此， 系统闲 期的 分布函 数为 f ( t ) 二 pit 1 - o , j ? 1 服务员的“ 广义忙期” :是指从服务员开始为顾客服务的时刻起，直到系统再 次变空的时刻止的这一段时间， 其中包括了在顾客的服务期内， 服务台可能发生 失效而产生的修理延迟时间和其后进行的修理时间。 电子科技大学硕十学位论文 令 万 表 示 从 一 个 顾 客 开 始 的 服 务 员“ 广 义 忙 期 ” ， 且 令反 t ) = p 挤s t , t ? 0 b (s ) = e d b (t ),9 1 (s ) _ 0 ， p _ a ) 十 a l l + ,8 y ) fly ，则类似标准排队系统的忙期 讨论可得如下引理: 引 理3 . 2 叭 s ) 是 方 程: 二 k ( s + a 一 . z ) 在 : 1p 1 其中ro 是艺 = 一 u) 在 ( 0 , 1 )内的唯一解。 下面我们讨论队长的瞬态分布， 为此， 先讨论在服务员 “ 广义忙期”中的瞬 时队长分布。令 q , ( t ) = p ( b t _ o ; n ( t ) = j , j _ 1 表示在服务员的 “ 广义忙期”中时刻t 的瞬时队长分布，且在t = o 时只有一个顾 客 ， 服 务 员“ 广 义 忙 期” b 刚 刚 开 始 ， 即 q , ( 0 ) 二 i ,q ; ( o ) = o , j i 定 理 “ ， 令 q (si ) 二 f 。 一 q j (t)d t 为 q ; (t) 的 拉 普 拉 斯 l a p la c e 一 tr a n sf o r m ， 变 换 ， 则 对9 1 ( s ) z 0 , 如 ( s ) 有 如 下 的 递 推 式: b ( s ) i 一 9 ( s + r ) ( s + 几 ) 万 ( s + 几 ) 一b (s ) r r， 一 。 (t)1 t e 一一 )， 8 ( s + a ) -一 ( j 一 l y 、卫声、， sr 才、了 .1幸 q八 十 了 土 万 女 髻 一一 ) (、 (s ) 一 k f 一一 )， u h (s)t d d (t) i 、 ， g ( s + a ) 石 b ( s )高 司了 : 证 明 : 首 先 ， 考 虑 在 服 务 员 忙 期 b 中 第 一 个 被 服 务 的 顾 客 ， 令 x 表 示 这 个 顾 客的 “ 广义 服务 时 间” ， ， 表 示 在z 内 到 达 的 顾客 数， 设 这 些 顾客 数 为a ， , a , . . . 减 ， ， 电 子科技大学硕十学位论文 并称为 “ 第一类顾客” ，而在 “ 第一类顾客”以 后到达的顾客统称为 “ 第二类顾 客， 。因为服务员忙期长度和系统中的顾客数都与服务顺序无关，所以可把服务 顺序重新安排如下: 在 服务完 服务员 忙 期b 中 第一个 顾客以 后， 接 着 服务标 号 为a ， 的“ 第一 类 顾客” ，当 服务完该 顾客后， 紧接着服务除a 2 , . , a ， 外的 所有“ 第二类顾客” 及 其后新到达的 “ 第二类顾客” ，直到没有新到的 “ 第二类顾客”才开始服务标号 为a : 的“ 第 一 类 顾客” ， 记l , 为 从开 始 服务a ， 顾 客 起直到开 始 服务a 2 顾客为 止 的 这 段时 间: 当 服务 完a , 顾客 后， 服务员 接 着服 务除a . . ., a ， 外的 所有“ 第二 类 顾客” 及其后新到 达的“ 第二 类顾客” ， 直 到没 有“ 第二 类顾客” 才开 始服务a 3 顾客， 记 这段时间为l 2 . ， 依次类 推，当 服务 完a ， 顾客后， 接着服务 在场的 所有 “ 第二类顾客” 及其后新到的“ 第二类顾客” ， 记这段时间 为l，于是b 可 表示为 b 二 牙 十 l ， 十 l 2 + 十 入 其中 不 口 、 l , ，l , ， ，l ， ，( i = 1 , 2 ， 一 ， v ) ， 相互 独 立， 同 分 布b ( t ) ， 且 独 立于z 而且当v = 0 时， 有l , + l 2 + 一+ l = 0 。于是， 利用全概率分解技术，得 乌( t ) 一 尸 牙 + l , + 十 l ,. ) ， 列; n ( t ) 二 乃 一 p 份) : 。 ; 且 在 ( 0 , t 内 到 澎- 1 个 + 艺 p 和 = k ; x ! t ; x 十 l , + - 二 十 l , t ? 0 ; n ( t ) = 刀 由 于 到 达 是p o i s s o n 过 程， 因 此， 当 服务时 间分 结 束时 ， l , + l 2 十 十 或可 以 认 为 是 从v 个 顾客 开 始的 新 的 服 务 员 忙期， 而 且牙 与l , + l 2 + - 二 十 吞 ， 是 独 立的， 即x的结束时刻是一个更新时 刻点，所以 。 ， ( ， ) 一 尸 份 t ? 0 ; 且 在 ( o ,t 内 到 澎一 1 个 一 ” 尸 l , 十 ， 二 十 l , 卜x ; n q - x ) 一 j d d (x ) , j ? 1 电子科技大学硕士学位论文 = (l +)二 e _x ( j 一 1 ) ! l 1 一 g ( t ) 客 f ( )k ek! 一 峥仁 +. 二 十 l k t - x ; n ( t - x ) 一 对 d d ( x ) , j _ 1 根 据l ， 的 定 义，l ， 是以 标号为a ， 的“ 第一 类 顾客” 开 始 服务 的 服务 员 忙期 长度， 所以 每个l都与服务员忙期b 有相同的概率特性，于是也应有 p l , ， : 0 ; n (t) 一 ， 一 ， 替 ， : o ; n q ) = 、 一 q ; (t ) 也 就 是 说 在 l ; 中 ， 时 刻 ， 队 长 为 j 的 瞬 态 概 率 应 等 于 在 万 中 同 一 时 刻 ， 队 长 为 1 的 瞬态概率。 又根据上面服务顺序的重新安排，如果时刻t - x 落在l , k 一 r 个 “ 第一类顾客” 时刻的 “ 第一类顾客， ， 没有开始服务，所以系统在时刻卜x 中，则系统中还有 的顾客数应等于此 数加上此时刻的 “ 第二类顾客数”( 见图3 - 1 所示) 。 l , l z l , _ , l , l a i l k !一- - 平一一 - 州 ， 二 卜 - - 一 一 一 十-斗 一 - 一 一 一 - 州一卜一一 - 一 一 日 图 3 - 1 又由 于每 一 个l , _ ， 结 束时， 可以 认为l ， 是一 个新的 服务员忙期开 始， 所以 仍然利用全概率分解技术，得 p 仁 . 十 一 十 l k 卜二 ; n ( t - x ) 一 月 一 k 工 一水 t 一 x 一 y ; n ( t 一 x 一 y ) 一 ， 一 、 + r d b 一 ， (， ) 其中 ， n ( t - x - y ) 表 示 在l ， 中 在 该 时 刻的“ 第 二 类 顾 客” 数目( 注: 如 果 在 该 时 刻， a ， 未 被 服务 完， 该 数目 也 包 含a , 这 个顾 客) 。 由 于队 长分 布 只与 顾 客 数 有关，所以 p l , ， ， 一 二 一 y ;n (t - x 一 ， ) 一 ， 一 ， + r 卜 q j-,x+ . (t x 一 ， ) 于是 电子科技大学硕士学位论文 , ( t ) = ( 已。 ( l 一1 ) r 一 1 一 g ( t ) 一 客 f-.r; 一 卜 一 ， )db “一”(y )dg (x), j 取 乙 变换，经过整理即可完成定理 3 . 1 的证明。 令 p ;r (t ) = p n (t ) 二 ， n ( 0 ) = i) , p y* (s ) = f e - p (t) d t ,一， 0 定理 3 . 2 对9 1 ( s ) ? o , i _ 1 ， 有 p o o ( s ) = ( 3 ) s + 兄一 肋( s ) p ;o (