服务台由N个部件串联的M_G_1_E_MV_可修排队系统的平稳分布

服务台由N个部件串联的M_G_1_E_MV_可修排队系统的平稳分布 服务 台由 个部件 串 联 的, , N M /G /1E ,M V 可修 排队 系统的 平稳 分布 魏 瑛 源 ,734000 ,河西学院数学系,甘肃 张掖 摘 要:文章考虑到服务台是由N个不同型部件串联组成的M /G/1,E, MV,可修排队系统,其中服务台工 作当且仅当N个部件都工作,假定每个部件的寿命服从指数分布,故障部件的修理时间服从一般分布,通过引 入顾客的“广义服务时间”和队长过程的嵌入 Markov 链,得到了嵌入 Markov 链的平稳分布的递推达式以 及平均队长, 关键词:M/G/1,E, MV,可修排队系统,顾客的“广义服务时间”,嵌入 Markov 链,平稳分布,平均队长 中图分类号:O213.2;O226 文献标识码:A 文章编号:1672 , 0520(2006)02 , 0006 , 05 1 引言 对于可修休假排队系统的研究，目前大多数文献都假设服务台为单部件(我们在这里假设服务员具有空竭服务多重休 假，且服务台是由N个不同型部件串联组成的M/G/1 可修系统，其中服务台工作当且仅当N个部件都工作(假定每个部 件的寿命服从指数分布，而故障部件的修理时间服从一般分布，通过引入顾客的“广义服务时间”和队长过程的嵌 入 Markov 链，得到了嵌入 Markov 链的平稳分布的递推公式以及平均队长( 模型的描述与假定2 χ, n ? λ > 0考虑一个MG排队系统，假设顾客的到达服从参数 的Poisson流;顾客实际所需的服务时间序列 {//1 () n ? Gt ,t ? 0 独立同一般分布 ()，且 (0 < 1 μ = tdG t < ? () 1} 0 系统有一个服务台，容量为无穷大(服务台由N个不同型部件串联组成，服务台工作当且仅当 N 个部件都工作;部 ? α(0 ? α< 的负指数分布件 k 的寿命 X服从参数k k k ?αt k ?) X t = PX ? t= 1 ? e, t ?0 , k = 1, 2,L, () {} k k N. 任何一个部件故障后立即进行修理，而其他部件停止工作，不再发生故障，此时服务台处于失效状态(部件k 的修理时 ? Yt = PY? t, t ? (部件修复如新(间 Y服从任意分布() {}，且tdYt < ?, k = 1, 2,L, N0 ? β= k () k k k k 0 0 同时还假定在该系统中，服务员具有空竭服务多重休假规则(服务员的休假时间列 V, n ? 1独立、服从相同的一{} n ? ? 0 ? γ = tdV t < ? V t 般分布 ()，且 () (进一步? 0 1)在服务台空闲期间，组成服务台的部件既不发生故障也不变坏，即不影响部件的使用寿命; 假定 2)当一个部件故障后，正在接受服务的顾客需要等待其修复再继续接受服务，已服务过的时间仍然有效，即累计 计 算;顾客按先到先服务的顺序接受服务，服务完毕后就离开系统; )初始时刻 t = 0，系统中无顾客时，服务员不去进行休假(但平稳结果与此假定无关);3() )上述所有变量相互独立;4 ——————————————— 收稿日期:2005-11-11 作者简介:魏瑛源,1970 —,,女,甘肃古浪人,讲师,硕士,主要从事排队论、可靠性和保险风险模型的研究, - 6 - 魏瑛源,服务台由N个部件串联的 M/G /1 ,E,M V,可修排队系统的平稳分布 3 队长的嵌入 Markov 链 3.1 服务台的寿命U和修理时间Z N α = 令U 表示服务台的寿命，U表示服务台的第 i 次寿命，则 U = min X , X , , X ，于是U服从参数 Li ( ) i ?i 1 2 N αk 的负指数分布k =1 ?α t U t = P U ?t = 1 ? e ? α < ?t , , 0 ( ){} (1) i i 0? 与 i 无关，令U (t) ,U(t)( i 如果令Z表示服务台从失效的时刻起直到被修复为止的这段时间，把Z称为服务台的“修理时间”，令 Z表示服务台 i 第 i 次失效后的修理时间，则Z的分布函数为 i N Zt = P Z?t = P min X, X ,L, X = X ,Y? () {} ( ) {i i ? 1 2 N k k t} k =1 N N 1 = α Y = P X < X ,L, X < X , X < X ,L, X < X,Y ?t {} ( ) (2) ?? ?1 k k +1k k k k 1 k N k α k =1k t k =1与 i 无关，令Z (t) ,Z(t)，且 i N ? 1 ? st αy z s = edZ t = s () () () (3) ? k ? 0α k =1 N k? 1 β = E Z = tdZ t = α [] () ?k k (4) ? α k =1 β 类似(2)式的推导，得 0 N P U ? t, Z ? t= P min X, X ,L, X = X , X ?t ,Y? t= P U ? tPZ {} ( ) {} {{} ? 1 2 N k k k ? t} 则服务台的寿命U 和修理时间Z 相互独立( k =1 (m)注:本文一律采用g(s), g*(s) 分别表示相应的G(t) 的LS变换和L变换，G(t) 表示相应的G(t) 的m重卷积，且 N N 0() % Gt = 1,α α ,α μ α β , ρ = λ 1 + (() ? ? k k =1 β =. αβ )= k k 3.2 顾客的广义服务时间 k =1 % χ令表示第 n个顾客从开始接受服务的时刻起直到服务结束的时刻为止的这段时间，其中包括了在该顾客的服务时 n % χ间内，因服务台可能多次发生失效而进行修理的时间，我们把 称为 第 n个顾客的“广义服务时间”(对 t ? 0， n %G t = P ? t() } 令 ，则n n [1]m %χ{ ? t α x () ( m ) ?α x %%G t = P χ ?t = Z t ?x edG (5) () {} () n n? ?m! m=0 x ( ) % % 0与 n无关，令 Gt = Gt ，() () n 且% gs = g s + α ? α z () ((6) s ()) 1 % = E χ= 1 + αμ [] (n (7) %μ β )%由于负指数分布的“无记忆性”性质，可知服务台的剩余寿命仍服从负指数分布，可以推证 相互独立χ, n ? 1{} n 同 [2]% 分布 Gt ，因此得到如下引理:() % %χM G1引理 如果我们把直接理解为第 n个顾客的“服务时间”，则所研究的系统等价于具有空竭服务多重休假的 n - 7 - 河西学院学报2 00 6 年第 2 期 % %排队系统，其中输入过程是参数 λ > 0的流，顾客的服务时间序列 χ, n ? 1独立同分布 ，服务员() Poisson{} Gt () n 的 休 V, n ? 1假时间序列 {} 独立，同一般分布Vt(()n + + T假定令N(t) 表示时刻 t 系统中的顾客数(队长)，表示第 n个顾客服务完毕离开系统的时刻，N表示第 n个顾客服务3.3 嵌入 Markov 链 n n + 完毕离开系统时留在系统中的顾客数，n? 1，则下面定理表明 N , n ? 1是 Markov 链，被称为队长过程N t , t ?0 (){}{} n 的嵌入 Markov 链( + n ? N,1定理 3.1 {} 为一不可约的、非周期的齐次 Markov 链 , 其一步转移概率为 n e ,i = 0,? 0j ? j ?j ?i ?i ? 1 ++ 1= P N= j N= i=P() g ,(8) ?{} ij n+ 1 n ? + j i 1 1, ? i ? 10, ?? j < i ?1, j +1+1j ? ? λ λ t 1 (() ?λt ? λt % e = edV t edG t , j ? 0其中 () () ? l?lj ?? 0 0 l ! 1 ? v j + 1 ? t ( ) l = 1 λ l !()) k ? λ ( ?λt % g edGt , k ? ()k 0 t )k ! = 0 ? γ η 证明令表示在第 n， 1 个顾客的广义服务时间内到达的顾客数，表示在休假期间到达的第一个顾客 n+1 n+1 %χ n+1γ , n ? 1{} 的等待时间和服务时间内到达的顾客数(则 相互独立同分n k 布: ?? λ ( ?λt % %%g P γ= tdP χ, = P γ= k== k χ?t =e dG t k ? 0{} } () {}{ (9) k n +1n +1n +1n+1 ? ? k ! t ) 00η, n ? 1{} 相互独立同分n 布: j +1? e = Pη= j{} j n+1 = P { 前 m , 1 次休假期间无顾客到达，第 m 次休假期间到达 l 个顾?? 客， m=1 l =1 %χ休假期间到达的第一个顾客在其服务时间 内到达 ， ,l 个顾客 j 1 }1j +1+1j ?λ ?λ t 1 (() ?λ?λ% = dV t dGt , j ? 0() ()(10) ? l?l??tt 0 0 1? v l ! j + 1 ? l t !(() ) ) l =1 eλ e 而且 ++ ?N?1 + γ > 0N n n ?+ = N(11) ? n+1, n+1 + ?, ηN= 0 n n+1? η, n ? 1γ , n ? 1{}γ = γ ,η= η , n 由于 {} 相互独立同分布，且 相互独立同分布，令 n n n n ? 1，则++ ?> 0NN?1 + n n ? + N= (12) ? γ ,n+1 + ?, ηN= 0 n ? + ++ +++ N, n ? 1NN, N,, NL从 (12) 看到，当已知N时， 只与到达过程有关，而与 无关，所以 {是 } n+1 n1 2 n?1 n 链，其状态空间为 E, {0, 1, 2, „ }(又一步转移概率为 Markov - 8 - 魏瑛源,服务台由N个部件串联的 M/G /1 ,E,M V,可修排队系统的平稳分布 , i = 0? P η = {? ++ p1= P N= j N= i= () ?{} ij n 1 n + j} P γ = j ? i + 1, i ? 1 ?{} ? p1, i, j = 0,1, 2,L()所以 (8) 成立(从一步转移概率表达式知， 与时间的起点无关，而且任意两个状态是互通的 ， ij + 又 p1> 0, i = 0,1, 2, ，故 N, n ? 1为一不可约的、非周期的齐次 链(L() Markov {} ii n + N , n ? 1定理 3.2 嵌入 Markov 链 为正常返的充分必要条件是{} n % ρ< 1 (14) % ρ< 1 证明 充分性 设 ，定义 j y = ? 0 , j = 0,1, 2,L(15) j %1 ?ρ 则当 i? 1 时，有 ?? j i p 1y = g= ?1 = y ?1 , i ? () ??i j ij j ?i +1 % 1 ? ρ1 ? j =i ?1j =0 1 %ρ ?? j λγ p y e = ?1 < ?1= () ? 0 j j j % % 1 ? ρ1 ? ρ1 ? v λ ()()()j =0j =0 ? + [2]N , n ? 1则得嵌入 链 为正常返的(Markov {}n + N, n ? 1 必要性设嵌入 Markov 链 为正常返，则{} n ++ lim P N= j= p > 0 ,j = 0,1, 2,L{} n j n?? ++ p , j ? 0N , n ? 1存在，且 {} 是 唯一的平稳分布，满足式{} j n ?? 子 +++ p = pp1, j ?0 ; p () ? ? j i ij j i =0j =0 = 1 根据一步转移概率表达式，进一步有 j +1 + ++ p = pe + pg , j ? (16) ? j 0 j i j ?i +1 i =1 0 引入母函数? + + jz pPz =( ) V ? j =0 j j 这样，用 Z乘()的两端，然后对 j 从 到?求和，得 160 + j ? + ? % pgλ ? λ z ?v λ ? % () (gλ ?λ ( 0 + ++j j ?+? 1 e z += z z z =g+pPp P( )( ) ? ?? 0 i j i V ? +1 z λ z ?1z ??1 ? v z ) ) j =0j =0 i =1 ?j 于是λ ?() ?+ % p gλ ? λ z 1 ? v λ (() ) 0 + P z =?( ) V (17) % ? 1λ zgλ ? λ z ?? v λ ?()() ? ? + ?z P1= 1, 由于 () 用洛必塔法则得 V + + % p gλ ?λ z 1 ?v λ ?λ z pλ() () ? 0 01 = lim P z =lim ?lim=( ) V ??? γz ?1z ?1z ?1 % 1 ? v λ gλ ? λ z ? v λ 1 1 () () () %? z?ρ 所以 % 1 ?ρ 1 ?v ()(+ p= (18) 0 λλ ()) ? γ ?λt ?λt + % λ > 0, 有e < 1t ?0 , 那么v λ = e dV t < 1 > 0ρ<1 而当 ()() () ， 得 ( 0 ? 0 p则由 - 9 - 河西学院学报2 00 6 年第 2 期 + 推论 对于嵌入 链 N , n ? 13.1 Markov {} n % ρ? 1 时，此 链是零常返的或非常返的，n 步转移概率的极)当 1Markov 限 lim pn = 0 ,i, j = 0,1, 2,L() ij n?? 且不存在平稳分布( )当 % 时， 此 链是正常返的，n 步转移概率的极限存在2ρ< 1 Markov ++ lim pn= lim PN= j= p > 0, i, j = 0,1, 2,L() {} ij n j n??n?? + 进一步 为唯一的平稳分布，有递推表达式:p , j ? 0{} j 1 ? ? + p= 1 ? v (( )) 0 ? λ%ρλ? γ ? j ?1 ??1 ? ++ ++ p = ? 1j p ? pe ? pg ? j ? j ?1 0 j ?1 i j ?i ? gi =1 ??0 ? ,? k 其中当 (k ? 0时, = 0 ? i =1 [2]证明 由定理 3.2 与(16)易证( + 推论 3.2 若 % ，则平稳分布 的母函数ρ< 1 p , j ?0 {} j ? 为%% 1 ?ρ 1 ?z gλ ?λ z 1 ?v λ ?λ z ()() () ()+ + j==?, z< 1P z p z ( ) ? V j % gλ ? λ z λ 1 ?z E () () j =0 ?z V [] 证明 将(18)代入(17)即得证( % 推论 3.3 当 ρ< 1 时，系统在统计平衡下的平均队长为 2 2 ?2 % λ σ + μλ () V % +N = ρ+ 2 2 2γ2 1 ? (σ + γ () ?? 2 ?2 2 22 % % ρ) 其中 % t dGt ? μ,σ = t dV t σ = () () V ? 0 0 2? γ ? 参考文献: [1] //1 198252113~127曹晋华，程凯(服务台可修的 排队系统(应用数学学报，，():(MG [2] 2000唐应辉，唐小我(排队论——基础与应用(成都:电子科技大学出版社，( [3]Yingyuan Wei, Yinghui Tang. A Two-Unit Cold Standby Repairable System With One Replaceable Repair Facility And Delay Repair (I) -Some Reliability Problems. Journal of Electronic Science and Technology of China.Dec.2004,2(4):68~71( [4] //1 20042411106~110魏瑛源，唐应辉(个不同部件串联而成的 可修排队系统(系统工程的理论与实践(，():(NMG [5] //1/ (, ) 200521210~12魏瑛源(,策略 ? 排队系统的一个递推公式(河西学院学报，，():(NMGEMV [6] //1/ (, ) 200519415~17魏瑛源(? 排队系统的注记(甘肃联合大学学报，，():(MGEMV Equilibrium Distribution of Repairable Queueing System with Units Series Structure WEI Ying-yuan (Department of Mathematies, Hexi University, Zhangye, Gansu 734000, China) Abstract: In this article, we consider repairable queueing system with N dissimilar units series structure, it operates if and only if all of the N units operate, assuming that each unit has exponential distribution and its repair time has arbitrary distribution. By introducing "the generalized service time" of the customer and the embedded Markov chains of queue length, we obtained the recursive expression of equilibrium distribution of embedded Markov chains and average queue length. Key words: reparable queueing system; the generalized service time; embedded Markov chains; equilibrium distribution; average queue length ,责任编辑 晏兴学,- 10 -