（系统工程专业论文）多服务台可修排队系统.pdf

江苏大学硕士毕业论文 摘要 本课题主要研究了三类多服务台可修排队系统，分别是带有优先 权的多服务台可修排队模型、批量到达的m 1 m n 以及一类特殊的带 有负顾客且等待容量有限的多服务台可修排队系统对于带有非强占 型优先权的多服务台可修排队模型，在画出系统状态转移图的基础上 得到系统的稳态平衡方程，并分析得到系统稳态指标的求解思路，使 用m a t h e m a t ic a 软件编程实现了稳态概率值的求解过程，并给出了一 个具体实例：对于批量到达的m 5 m n 可修排队模型，在画出系统状态 转移图的基础上得到系统的稳态平衡方程，并分析得到系统稳态指标 的求解思路，使用m a t h e m a t i c a 软件编程实现了稳态概率值的求解过 程，也给出了一个具体实例：对于负顾客的m m s k + m 可修排队模型， 运用矩阵几何解求解，得到系统的解析解和稳态性能指标，并通过数 值实例分别得到了服务率、到达率与总顾客损失率等变量之间的关系， 为更好地优化呼叫中心性能提供了一定的理论依据 关键词：多服务台，可修，优先权，批量到达，负顾客，呼叫中心，矩阵几 何解 江苏大学硕士毕业论文 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 so fr e p a i r a b l eq u e u e sw i t h m u l t i p l es e r v e r s ，t h eo n ek i n di st h em m nr e p a i r a b l eq u e u es y s t e mw i t h n o n p r e e m p t i v ep r i o r i t y , t h e o t h e ro n ei st h em 1 m n r e p a i r a b l eq u e u e s y s t e mw i t hb a t c ha r r i v a l ，a n dt h el a s to n ei st h em m s k + mr e p a i r a b l e q u e u ew i t hn e g a t i v ec u s t o m e r s f o rt h em m nr e p a i r a b l eq u e u es y s t e m w i t hn o n p r e e m p t i v ep r i o r i t y , t h ed i f f e r e n t i a le q u a t i o n so ft h i ss y s t e ma r e o b t a i n e d b yr e c e i v i n g t h es t a t et r a n s i t i o n d i a g r a m ，a n dt h e no b t a i n s t e a d y 。s t a t eb a l a n c e de q u a t i o n s b ya n a l y s i n gt h et 1 1 i n k i n go ft h ek e y s t e a d yp r o b a b i l i t y , w ep r o g r a ma n dd e r i v et h es t e a d yp r o b a b i l i t yb yu s i n g m a t h e m a t i c a ，a n dw e a l s o g i v e an u m b e f i c a l e x a m p l e s i m i l a r l y , w e r e s e a r c ht h em x m nr e p a i r a b l e q u e u es y s t e m a st ot h em m s k + m r e p a i r a b l eq u e u ew i t hn e g a t i v ec u s t o m e r s ，b yu s i n gt h em a t r i x a n a l y t i c m e t h o d s ，a na n a l y t i cs o l u t i o na n ds o m es y s t e mm e a s u r e si ns t a b i l i t ya r e o b t a i n e d a n d a l s o ，a n u m b e r i c a le x a m p l ea n ds o m ec o n c l u s i o n sa r e g i v e n ，w h i c hc a np r o v i d et h et h e o r e t i ce v i d e n c e sf o ro p t i m i z i n gt h ec a l l c e n t e r k e yw o r d s ：m u l t i p l e s e r v e r s ，r e p a i r a b l eq u e u e ，n o n p r e e m p t i v e p r i o r i t y , b a t c ha r r i v a l ，n e g a t i v ec u s t o m e r , c a l lc e n t e r , m a t r i xa n a l y s i s 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权江苏大学可以将本学位论文的全部内容或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 保密口，在年解密后适用本授权书。 不保密团。 学位论文作者签名：鲍噬绞 仂卯8 年i 乙月，占日 指导教师签名： 以粕年f 月i 多 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已注明引用的内容以外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均己在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：鲍嫩 日期：7 嘿年，月7 多e t 江苏大学硕士毕业论文 大战以后，排队论在运筹学这个新领域中变成了一个重要的内容2 0 世纪5 0 年代 初，堪道尔( d g k e n d a l l ) 对排队论作了系统的研究，他用嵌入马尔科夫链 ( a a d a r k o v ) 方法研究排队论，使排队论得到了进一步的发展近期，f 只乃硕等把 矩阵解析法引入g i m 1 型休假排队系统，并研究了部分服务台同步以及异步的 休假排队系统，极大地丰富了排队模型的理论：史定华将频度转移法用于可修排 队系统并对可靠性进行了大量研究：g e l e n b e 将负顾客引入排队系统当前，排队 论的研究主要集中在矩阵解析法、数值计算、排队网络以及特殊模型等方面，其 中特殊模型主要是研究具有实际应用背景的、有一定假设前提的排队模型，比如 休假、可修、重试以及优先权等排队以及由它们衍生出来的服务台具有多种性能 的排队模型关于排队论的研究方法，主要有：史定华的向量马氏过程和频度转移 法、n e u t s 的矩阵几何解法、k e n d a l l 的嵌入马氏链法、k o s t e n 和c o x 的补充变 量法正是由于上面提到的排队论研究课题的日趋复杂，使得很多问题或者是很 难求得其精确解，或者是求得的解非常复杂，不便于应用因而开始了近似方法以 及利用软件进行数值计算的研究本课题所要研究的就是这么一类特殊的排队模 型，而且由于得到的解析解非常复杂，本文选用了m a t h m a t i c a 软件进行编程，从 而对这一排队模型进行研究下面首先介绍一下多服务台可修排队模型的发展以 及研究现状 1 1 多服务台可修排队模型的发展及研究现状 经典排队系统都是假定服务台是不会发生故障的，但在实际生活中却经常碰 到服务台发生故障而不能为顾客服务的情形，此时需要修理工人对发生故障的服 务台进行修理或者更换，修理完成后再继续为顾客服务，我们将这类服务台可能 发生故障且可修复的排队系统称为可修排队系统。可修排队系统是从服务台的性 能角度提出来的，早在1 9 6 2 年a v i i t z h a k , b 和n a o r , p 1 、1 9 6 3 年t h i r u v e n g d a n ，k 2 】 就研究了服务台易坏的一些排队问题，利用补充变量的方法讨论一些有用的排队 指标。在随后的二十年罩关于服务台可能发生故障的文章也有很多3 6 1 。 目前，可修排队系统已经被广泛的应用于计算机集成制造系统、通讯网络、 柔性制造等领域，为设计和控制这类系统提供了理论依据。根据输入规则、服务 时间分布、服务台数目以及服务台故障率等多种原因的变化，可修排队模型有着 2 江苏大学硕士毕业论文 不同的性态近几年，不同形态的可修排队系统得到了深入地研究，获得了很多 的成果关于单服务台可修排队系统的研究有很多，文献【7 】- 【1 1 】将休假与可修结 合起来，研究了休假可修排队系统，并进行了相关的可靠性分析；文献 1 2 1 一 1 5 】 将重试与可修结合起来，研究了重试可修排队系统；文献1 1 6 1 1 8 1 研究了具有不 同服务速度以及不同服务方式的可修排队系统；文n 1 9 1 将负顾客引入了m g 1 可修排队系统，得到了系统稳态指标以及可靠性指标。关于多服务台可修系统的 文献主要有：文献2 0 1 研究了m m n 并联可修排队系统；文献【2 1 】运用递归的方法 得到多服务台可修排队系统稳态时的平衡方程；文献 2 2 1 t i 弱：究了一类m p h n 可 修排队系统并得到了稳态概率值；文献 2 3 1 1 i ! i 过综合考虑可修排队系统的效率和 可靠性，得到了系统最佳的服务台数：文献2 4 1 研究了有一个修理工，且忙时与 闲时故障率相同的m m n 可修排队系统，给出了多服务台可修系统稳态分布存 在的条件；文献 2 5 n 文献 2 6 i 开究了有一个修理工，且忙时与闲时故障率不相同 的m 胁r 可修排队系统，并给出了这类多服务台可修系统稳态分布存在条件的 一种新形式通过分析不难看出，现有的关于无限状态的朋删可修排队系统 的文献都有一个特点，就是仅给出了多服务台可修排队系统稳态概率值简要的求 取过程以及n 2 时稳态概率值的解析表达式，由于n 2 时系统稳态概率值手 工求取的复杂性，没有给出其相应的解析表达式，没有真正的解决这类系统为现 实生活中这类问题提供一个较好的工具，寻找一个方法对这一问题进行解决有很 大的现实意义。 同时，现实生活中存在许多有限状态的此洌r 可修排队系统的实例，例如： 在呼叫中心模型中，由于系统容量有限，因此可基于m m n k 排队系统进行呼 叫中心性能分析，因此研究这种有限状态的m m n 可修排队系统有很大的实际 意义。近期，关于不同形式的有限状态的m m n 可修排队系统的研究有很多， 取得了很多成果。2 0 0 2 年w a n gk u o - h s i u n g 2 7 砂f 究不耐烦、有限状态的m m n 可修排队系统，运用矩阵几何解法得到系统的稳态概率值：文献 2 8 1 将可变服务 率以及可修引入删s k + m 排队模型，在成功对模型进行求解的基础上，进一 步给出了系统的稳态性能指标 3 江苏大学硕士毕业论文 1 2 本课题的研究内容及解决问题的方法 本课题研究的内容是三类特殊形式的多服务台可修排队系统，其中前两类是 无限状态的多服务台可修排队系统，而最后一类是有限状态多服务台可修排队系 统，研究其在呼叫中心性能分析中的应用。前两种的研究思路是借助于研究排队 模型常用的方法“矩阵几何解法 分析得到了各系统排队指标的求解思路，运用 m a t h e m a t i c a 软件对该求解过程进行编程，实现n 2 时系统稳态概率值的求解； 后一种关于有限状态的多服务台可修排队系统，由于生成元矩阵q 的表达式不复 杂，直接运用矩阵几何解的方法表达出了解的解析表达式。 首先是研究的带有非强占型优先权的多服务台可修排队模型，在画出系统状 态转移图的基础上得到系统的稳态平衡方程，并分析得到系统稳态指标的求解思 路，使用m a t h e m a t i c a 软件编程实现了稳态概率值的求解过程，并给出了一个具 体实例 其次，研究了批量到达的m z i m i n 可修排队模型，运用与上述模型相同的 方法，得到了系统的近似解以及系统的稳态指标 最后，研究的是负顾客的m m s k + m 可修排队模型，运用矩阵几何解 求解，得到系统的解析解和稳态性能指标，并通过数值实例分别得到了服务率、 到达率与总顾客损失率等变量之间的关系，为更好地优化呼叫中心性能提供了一 定的理论依据 4 江苏大学硕士毕业论文 第二章研究排队模型的方法 研究排队模型的方法有很多，为了成功的研究排队模型，针对不同排队模型 的不同特点，要选用不同的研究方法，本文所选用的是n e u t s ( 1 9 8 1 ) 等系统发展 了的处理q b d 的矩阵分析方法，为了更好地介绍矩阵分析法，很有必要首先介绍 一下此方法的基础，也就是马尔科夫链及经典生灭过程。 2 1 马尔科夫链及经典生灭过程 马尔科夫链是一类重要的随机过程，他的状态空间是有限的或可数有限的。 经过一段时间系统从一个状态转到另一个状态这种进程只依赖于当前出发时的 状态而与以前的历史无关，以连续时间马尔科夫链为例。 1 连续时间参数的马尔科夫链【凋 定义：设弘( f ) 是一个随机过程，t 表示时间可以去一切实数值，其状态空 间为8 = 0 ，1 2 ，s 可以是有限集或无限集。如果对任取的一组时间数值 0 h t 2 乙 u t 及任取的一组状态值，之，乙，f ，j ，x ( t ) 得条件概率满 足下式， p ( x ( t ) = j i x “) = ，x 化) = i 2 ，x 纯) = 屯，x ) = i ) = 以x o ) = jx ( u ) = f ) 即已知x ) = f 时，x ( t ) 的条件概率与在时刻u 以前系统所处的状态无关，而只 与u 时刻处的状态有关，则称弘( ) ) 是一个连续时间的马尔科夫链，上式表示的 性质成为马尔科夫性。 2 齐次马尔科夫链 连续时间马尔科夫链中应用最多的齐次马尔科夫链的定义如下： 定义：设【x ( f ) ) 是一个随机过程，若条件概率p ( x ( f ) = j l x ( u ) = f ) o ，p ，= 1 j = o l i p p j ，j = o ，1 ，k ) 为平稳分布。 ( 2 ) 对无限状态e = 0 ，1 ，2 ，万， 的生灭过程，若有条件 1 + 妻墨尘生 o ，p j = 1 ，即 i = o p j ，= 0 ，1 2 ，为平稳分布。 2 2 拟生灭过程与矩阵几何解 1 拟生灭过程p 1 】： 定义：考虑一个二维m a r k o v 过程t x ( f ) ，y ( f ) ) ，有状态空间 q = ( 七，j ) ；七0 ，j = l 2 ，m ，状态集 ( 七，1 ) ，( 七，2 ) ，( 七，所) ) 称为水平七，k 0 ， 如果将状态按字典顺序排列后，其生成元可写成下列分块三对角形式： q = ag 日ac 1 岛ac 2 b ，a ，c ， 则称t x ( f ) ，y ( f ) 是一个拟生灭过程( q u a s ib i r t ha n dd e a t hp r o c e s s ，简记q b d ) ， 其中所有子块是m 阶方阵，a ( 七o ) 有负的对角线元素，并且行和非正，b k 和 c k 都是非负阵，满足( a + c 0 弘= 他+ 嘎+ c ) e 七1 。 7 江苏大学硕士毕业论文 q b d 是经典生灭过程从一维状态空间n - 维状态空间的推广，经典生灭过 程的状态x ( t ) = k ，现在被分解成m 个子状态 ，1 ) ， ，2 ) ， ，胧) 。这一结构 顺应了刻画过程在多层次、多相位及变动参数情况下演化的要求。e v a n s ( 1 9 6 7 ) 首先在排队论分析中使用这类过程，w a l l a c e ( 1 9 6 9 ) 在计算机系统研究中也遇 到了这类过程，并由他引入了“拟生灭过程 这一术语。2 0 世纪7 0 年代以来， n e u t s ( 1 9 8 1 ) 等系统地发展了处理q b d 的矩阵分析方法，有力地推动了q b d 过程在随机模型分析中的广泛应用。迄今为止应用最广泛的是一类生成元形式特 殊的q b d ，即生成元q 中的子块从某一个水平开始不再发生变化的情形。这时， 过程生成元形如： q = ac o 且ac 1 忍q4 qe q ba c bac 为了讨论的方便，假设过程的稳态分布存在，记 2 ：骢掣( f ) = 七，( d = n ， ，j ) q n k = ( 以1 ，) ，k 0 万= ( ，n - 1 ，死，一) 2 定理：q b d 正常返当且仅当矩阵方程r 2 曰+ 融+ c = 0 的最小非负解r 满 足s p ( r ) o 1 0 江苏大学硕士毕业论文 图3 1 状态转移图 ( 2 ) 0 j n 时 ( 丢+ j + 五+ a “0 ) e o “t ) = 日“f ) + o p o 小。( f ) + ( ，+ 1 ) 昂小。( f ) f = o ，d 【- 5 7 + l 口2 口i 魍卜1 ( f ) + ( 歹一f ) q + 五+ 五+ 口+ f 】日，j ( f ) = + ( 五+ 名7 ) 只- l ，j o ) + ( i + 1 ) + 1 ，o ) + 【f 口2 + ( j + 1 一f ) 】鼻，j + 1 ( f ) i | + 名+ z ，) 蜀，o ) = 鸠，) + 睨。- 1 ( f ) i = 0 【丢+ f + f 吃+ o v f ) q + 允+ 名】只，( f ) = ( 元+ 兄) 丑一l ( f ) + 犯，一，( f ) + ( f + 1 ) 只+ 1 o ) o i 1 1 呸 时 斗 卢秀 、，3 江苏大学硕士毕业论文 3 2 系统稳态条件分析及稳态平衡方程 由于系统瞬时状态概率密度满足的微分方程组求解的复杂性以及研究系统 稳态情况具有较大的意义，故下面主要研究系统稳态存在条件以及求出系统稳态 平衡方程 根据上述状态转移图，可以得到 x ( f ) ，y ( f ) ；f 0 】这一个二维马尔科夫过程的 生成元矩阵q ，表示如下： q = q 的每个分块都是n + i 阶方阵，设i 为n + i 阶单位阵，则通过分析，得到 其中，当i = o 时， 当i = n 时， 当o i n 时， a f = 口f o 0 包la f l 口 b i n la w l 0 b 哪口哪 b i j = j a t 1s jsn f一五一名一口 j = 0 口j2 t 一允一彳一口一包，o j n 包，j = j a 2 1 j n l 一兄一五一0 f = 0 口u2 1 一五一肛0 包厂j 0 j b i , j - - 弋羔2 j 0 一_ 兑l ：专 量二 i 一名一名一0j = 0 q 厂1 一a 叫- o - b f 厂_ o j f c q a 。“丑 2 c b q 如。 o 1 2 c a 召 瓜崩 江苏大学硕士毕业论文 a 2 a m b i = d i a g m i n ( i ，j ) t u ，0 _ ) ，1 i n b = b = d i a g o ，2 , u ，肼 c o = c l = = c = c = ( 五+ 兄) j 由于此二维马尔科夫过程的生成元矩阵为上述的分块三对角形式，故该过程 为一拟生灭过程( 简记为q b d ) 从而我们便可得到此过程的稳态条件，见下述 定理 引理1 上述拟生灭过程正常返当且仅当矩阵方程r 2 曰+ r a + c = 0 的最小非负解 r 的谱半径s p ( r ) 0 ( 2 ) p q 时 0 q + 五+ 刃+ 6 峨，= 心j + 鳃一+ u + 1 ) 喁m i = 0 o g + u 一懈+ 五+ 名+ 秒+ 憾2 f ， d + + 0 嗳i j + a + 1 ) 声暖气j + 【哇+ u + 1 一姚圪j h 。 c 心+ 力+ 秒+ 五回置j = 螈，+ 日d + q + 砜+ ( 1 恐+ q y 乙q 2 歹 ( 五砭+ 名+ 钟z 均吃j = j z 2 m , ，+ _ i + 嘎，+ u + 】q 缓m 。 ( 3 ) ，= n 时 ( n a l + a + 名) e o ，= 异，+ o e o ，一1 【f + f 口2 + ( 一f ) 口1 - i - 五4 - 五】= ( 五+ 名7 ) _ 1 ，- i - 秒，一1 - i - ( f + 1 ) + 1 ( 口2 + n , u + 兄) = o p , ，一l + ( 五+ z ) 只一1 ，+ + 1 ， ( n a 2 + n t - i - 五) = o p , ，- 14 - 五_ 1 + n v p , “ f = 0 0 f 江苏大学硕士毕业论文 得到系统稳态平衡方程的目的是求出系统各个状态的稳态概率值，并进一步表示 出可以反映系统性能的指标量，从而可以有效地优化系统本文将重点求解两类 性能指标：系统有效服务台数的稳念分布以及稳态队长的母函数 3 3 系统性能指标的求解思路 设g ，( z ) = z 最，g ( z ) = g j ( z ) ( o j ，i z i 1 ) ，则g ( z ) 即为系统队 i - - oj ；o 长的母函数，g ，( 1 ) = 只，即为系统中有j 个服务台处于有效状态的稳态概率 i - - - o 首先分析有效服务台数稳态分布的求解思路对相同j 值的稳态平衡方程关 于i 求和，得到+ j 个关于g j ( 1 ) ，j = 0 ，1 n 的方程，如下： 瞩( 1 ) = 啊q ( 1 ) + ( q 一吃玩 ( 心+ 够( 1 ) + ，l ( q 一吃屹刮= 鸭一。( 1 ) + ( j + 1 ) 嚼h ( 1 ) + 以q 一吃喝q 训钉( 1 j 忉 m = lm - - 1 懈( 1 ) + ，l ( q 一呸爆训= 6 g n q ( 1 ) 0 0 又由于置j = 1 ，则可知 r g ( 1 ) = 1 i = o ( 3 1 ) 上述方程组中的+ 1 个方程是相似的，可化简成个独立的方程，再与式( 3 1 ) 组成关于g ，( z ) ，歹= 0 ，l n 的含有n + 1 个独立方程的方程组，见下： o g o ( 1 ) 一口2 g l ( 1 ) = ( q 一口2 ) p o j f + 1 o g ，( 1 ) 一( j + 1 ) 口：g m ( 1 ) = m ( 一a ：) 易h 一。j h ( 1 j ) ( 3 2 ) m = 1 g ，( 1 ) = 1 可以发现，式( 3 2 ) 中含有( + 1 ) 2 个未知概率值 1 4 江苏大学硕士毕业论文 j 昂。：丑，z 昂。，巳，3 ； 昂日 昂- 1 ， 利用系统的稳态平衡方程以及条件兰羔，j ：1 ，这些概率值可归结为个 j - - oi = o 概率值昂j = 1 n 的求值问题因此，如能求得晶，j ，j = 1 ，这个概率值， 即可求得系统有效服务台数的稳态分布g ，( 1 ) ，j = 0 ，1 ，n 下面的关键就是求 昂j = l n 接下来，分析系统队长母函数的求解关键对j 取相同值的系统稳态平衡方 程两边分别乘以z + i 再对i 求和得到+ 1 个关于g ，( z ) ，j = 0 ，1 ，n 的方程，如下 酩+ z + 舡一p + 五矽稀国一鹕国= 心一呸) 即 - - 1 9 9 g 1 _ l ( z ) + 【( + l 吃+ a + 句| z 一五一一j z g j ( 2 ) 一( j + 1 ) z 呸g j + 1 ( z ) = 茎姒呸+ 一q ) 一们刮一刊+ 敛q 一呸挥诅喝，d 一枷一茎) ，鹕刮一+ 圭碱如o ， 叼 - o 峪n a ( z ) + 【( 0 + + 固i z 一五z 2 一 懈( z ) = ! ：k 吃+ 一q ) 一五1 昂训z 1 “一乏鹇吨1 + 彳霉剞 然后运用与文献【2 5 】相似的方法，可以得到a ( z ) 亭( z ) = b c z ) 其中，a ( z ) = 兀( z ) 一吃z 000 一o z 正( z ) 一2 z 0 0 0 0 00 0 一如厂- 1 ( z ) 一吃z 00 00一o z ，0 ) 兀( z ) = ( 名+ 见7 + 印z 一( 五+ 五) z z ，f ( z ) = ( j + j f 吃+ 兄+ 0 z 一缸2 一j ( j = 1 ，n 一1 ) 厶( z ) = ( n p + n c 5 + d z 一厄2 一n t b o ( z ) = ( a a 一) 蜀， 6 j ( z ) = e , m ( o q + p - ) - i 1 弓_ m , j z j - m + l + 肼( q 一) 弓+ 1 ，j + 1 z 一+ 2 m = lm - 1 f， 一聊心，。j z 一+ 旯e 矿+ 1 ( o 0 1 1 2 8 5 5 ， 气2 一o 0 8 8 7 9 9 9 , p o ，3 一o 1 2 8 6 8 4 , 也一o 0 9 5 0 6 6 , 昱，3 一o 0 3 5 3 5 2 9 ， 昂，4 专0 1 1 5 2 3 4 ，日，4 0 0 7 9 7 0 1 3 , 乞4 一o 0 2 7 6 6 5 8 ，弓，4jo 0 0 6 4 5 9 3 6 根据以上求出的概率值，由式( 3 2 ) 可求得g ，( 1 ) ，j = 0 ，1 ，n ，进而可求得系 统的稳态可用度，系统中共有个服务台，则系统的稳态可用度为 a = g j ( 1 ) j = 1 同理可求得g ，( z ) ，j = 0 ，1 ，n ，进一步可得到系统队长的概率母函数 g ( z ) = g ，( z ) j = o 再由母函数的性质，系统统计平衡下的平均队长为 e 阳一d g 出( z ) 旧 本文分析了一个带有两个优先权，且忙时与闲时故障率不同的m m n 可修 排队系统，根据系统的状态转移情况，得出了系统稳态概率值满足的平衡方程， 并在分析了稳态概率值求解的过程后，利用m a t h e m a t i c a 软件编程实现了n 2 时稳态概率值的求解，在此基础上得出了系统的有效服务台数的稳态分布和统计 平衡条件下的平均队长 1 8 江苏大学硕士毕业论文 第四章m x m n 可修排队系统 关于故障率可变的多服务台可修排队系统的研究正在起步，而对批量到达的 多服务台可修排队系统的研究尚未见诸于文献，鉴于此本文在讨论了批量到达且 故障率可变的多服务台可修排队系统的基础上，将通过使用m a t h e m a t i c a 软件编 程实现n 2 时稳态概率值的求解过程，并给出了一个具体实例，为现实生活中 这一多服务台可修系统的研究提供一个简便的工具 4 1 模型描述 考虑一个m 。m 可修排队系统系统中有个服务台，一个修理工顾客 成批到达，每批到达的人数x 是一个随机变量，批到达流是泊松流，参数为兄， x 的分布为p _ 瞵= f = ，；，i = 1 ，2 ，e r , = 1 且e ( x ) 0 用置，表示系统处于状态o ，j ) 的稳态概率，即 = 产州力d 。0 - 裂。0 办一 分析这一模型的各个状态的具体情况，可以画出这一系统的状态转移图，根据状 态转移图，我们可以写出系统所满足的稳态平衡方程，如下 ( 1 ) f = 0 时 ( 五+ 0 3 p 0 ，o = 缶日。o j = 0 ( 兄+ 昂，：幺号，j + 艺织乒。t j o ( 2 ) o i l ( 3 ) i = n 时 “v 缶+ 五) 昂，o = 万晶- 1 0 + 昂，l j = 0 【j + j 炙+ “v j ) 缶+ 见】晶，j ：万昂1 j + ( j + 1 ) 解，j h + 艺元昂乒。o j n ( 磊+ n + 名) 晶，：j p m - i , i + n p p m 川+ 兰碣乒。t j 4 3 模型求解思路 o o o o 设q ( z ) = z 最，g ( z ) = g ( z )( o f ，i z i 1 ) ，则有g ( 1 ) = 置， j = o i = o j = o 也即系统中有f 个服务台处于有效状态的稳态概率 下面对相同i 值的稳态平衡方程关于j 求和，得到n + 1 个关于 q ( z ) ，江0 ，1 的方程，如下 a g o ( 1 ) = 白g 1 ( 1 ) + ( 缶一色嵋。 a 岛+ d g ( 1 ) + 珑( 缶一岛心。= 崛q ( 1 ) + o + 1 ) 岛g ! f h ( 1 ) + m ( 缶一乞皿铘h ，( 1 f ) m = 1 m = l 卫 白g ( 1 ) + m ( 缶一乞) b 珂= 8 g h q ( 1 ) r 又由于只，= 1 ，则可知 j = oj = o ( 4 1 ) 将上述方程组中的+ 1 个方程化简，再与式( 4 1 ) 组成关于g f ( 1 ) ，i = 0 ，1 n 的含 1 = 、- 、og 瑚 江苏大学硕士毕业论文 有+ 1 个独立方程的方程组 瞩( 1 ) 一乞g 1 ( 1 ) = ( 白一幺) 置o i + 1 6 g , 0 ) 一( f + 1 ) 乞q h ( 1 ) - - 2 小( 缶一乞) 只h - 艚( 1 f ) ( 4 2 ) m = 1 v g i ( 1 ) = 1 可以发现，式( 4 2 ) 中含有n ( n + i ) 2 个未知概率值 号o e ，o 罡，1 只，o b ，1 弓，2 晶，o 昂，1 昂，2 昂- 1 l q 利用系统的稳态平衡方程以及条件霉，= 1 ，这些概率值可归结为n 个 i = 0j - - 0 概率值鼍o ，i = 1 ，n 的求值问题。如能求得，i = 1 ，n 这个概率值，即可求 得系统有效服务台数的稳态分布q ( 1 ) ，i = 0 ，1 ，下面的关键就是求 最o ，i = 1 ，n 我们首先对i 取相同值的系统稳态平衡方程两边分别乘以z ，再对j 求和得 到+ 1 个关于g l ( 力，i = 0 ，1 ，的方程，如下 ( 五十万一勰( 砌z g o ( z ) 一乞g 1 0 弦= ( 缶一色) 置o z j z g i _ 1 ( 力+ 【u + f 岛+ 见+ 万一z r ( z ) ) z i z l g j ( 力一( f + 1 ) z 乞g ：+ 1 ( 力= m ( 乞+ 一缶) 霉，一1 + 1 + 优( 缶一乞) 只蛳，。z 1 + 2 一m 晦，z 1 一崛1 ( 力+ 【a v + 岛+ 兄一x a ( z ) ) z 一，靠( z ) = 优( 乞+ z 一缶) 昂，z - m + 1 一m z p j v ，, b - - m z 1 然后运用与文献 2 5 】相似的方法，可以得到 a ( z ) 虱力= 易( 力 江苏大学硕士毕业论文 其中，a ( 力= f o ( z ) 一乞z 00 0 一沈五( 力- 2 ( z z 0 0 ： 0 00 一沈厂。( z ) o0o0 一如 z ( z ) = o + l 乞+ 旯+ 万一五定( 砌z i pa = o ，1 ，n 一1 ) ，( z ) = ( + 色+ a 一膪( z ) ) z 一 2 ( 缶一 z 避o z 魏( 力：窆m ( 乞+ 一矗) 巳。? 一+ 1 + i + 1m ( 缶一色) 一z i - - m + 2 _ 窆m 弘已，- 掰 ( 0 f o 时，i a ( z ) i 在( o ，1 ) 内恰有n 一1 个不同的实根瞄1 ，设 z i , j = l 2 , - - , 一l 为陋( z ) l 在( o 1 ) 内的一1 个不同的实根，把z = 乙代入到式( 4 3 ) 中得 1 4 ( z 川= o ，( j = 1 ，2 ，n - 1 ；i = 0 ，卜，) 于是，对每一个巧有+ 1 个关于未知概率置。，i = 1 n 的线性方程，但是这+ 1 个方程是同解的，每一个z ，只产生一个独立的关于只0 i = 1 n 的方程，于是由 i a ( z ) i 的( o ，1 ) 内的一1 个不相同的实根就得到一1 个独立的方程，而第个相 应的独立线性方程可以用如下的方法得到把陋( z ) l 的第一行直到第n 行全加到 3 。篇 江苏大学硕士毕业论文 最后一行，则最后一行产生公因式( z - 1 ) ，有 陋( z ) i = 0 1 ) f o ( z ) 一乞z 0000 一6 z 五( z )- 2 乞z 000 0 00 一b z 厶q ( z )- 彩i 一2 z 一龙+ 一2 z + 2 p 一屁+ ( 一2 ) 一厄+ ( i v 一1 ) j u 一2 z + n i 【j i 在此，将上式简记为 l a ( z ) l = 0 1 ) 日( 力 ( 4 4 ) 再将h ( z ) i ，i = o ，1 ，n 的各列求和后，有公因式0 1 ) ，表示为 h ( z ) i = ( z - 1 ) h ，( z )( 4 5 ) 将式( 1 1 ) 与式( 1 2 ) 代入式( 1 0 ) ，得 日( z ) q ( z ) = 日；( z ) ，i = o ，1 ，n( 4 6 ) 将z = l 代入( 1 3 ) 式，则有 日( 1 ) g f ( 1 ) = 日；( 1 ) ，i = 0 ，1 ，n( 4 7 ) 由前面的分析知道，g f ( 1 ) ，f - 0 ，1 ，n 可由只。，扛1 ，n 表出，因此式( 1 4 ) 是关 于最。，i = 1 ，n 的方程，同样式( 4 7 ) q p 的n + 1 个方程也是同解的，可用其中任 一个作为独立于前n 一1 个方程的第个方程，这样就得到了个关于 ，0 ，f = 1 ，n 的相互独立的方程，从而就可以求得只o ，i = 1 ，n ，进而求得 n ( n + i ) 2 个概率值 4 4 编程实现 由于n 2 时，手工计算这些稳态概率值较为复杂，已有的文献仅给出了 = 1 时系统稳态概率值的表达式，对n 2 时仅给出了解的存在性证明以及求解 的过程，并没有实现过。本文在已有文献的基础上，通过使用m a t h m a t i c a 软件 编程实现了n 2 时本文所讨论的这一类可修系统稳态概率值的求解过程，程序 的主体部分见附录b 为了检验程序的准确性，将= 1 ，吒= 1 代入程序，此时系统中仅有一个未知 9 4 江苏大学硕士毕业论文 变量号，0 ，通过程序计算的结果为号，。= 一望专鲁篆箸，得到的这一结果与手工 计算的结果致，从而验证了程序的准确性由于本问题编程主要是集中在关于 几个矩阵的构造，计算复杂性不大，通过计算得到该算法的时间复杂度为线性阶 ( o ( n ) ) ，故而得到该算法比较有效 由于服务台数较多以及该系统包含的自变量众多，因而得到的包含这些变量 的稳态概率值的解析表达式非常巨大，在此就不再一一显示这些包含变量的稳态 概率值的解析表达式，仅就一具体实例进行计算并显示最终结果。 令n = 4 ；2 = 2 ；3 = 4 ；缶= 1 ；乞= 2 ；= 8 ，将其代入到程序中，得出结果如下： 置oj0 0 9 4 5 6 2 3 ，e ，o 专o 1 8 2 6 4 2 ，j 一0 0 4 8 81 4 3 ，忍，o o 2 3 0 7 9 2 ， e 1 0 0 5 7 1 7 1 3 ，弓，2 - - ) 0 0 0 8 2 8 7 5 3 ，只，o 0 2 2 2 2 9 7 ，只，1 0 0 5 1 3 2 6 6 ，