（应用数学专业论文）串联开排队网络系统分析.pdf

摘要 在本文中，我们主要研究了两类服从指数分布的有限容量的级串联排队系统模 型，分别采用递推的方式给出了高维马尔可夫过程的转移矩阵，在本文模型二的 假设下利用矩阵分析方法进行求解，得到了该系统的稳态解及其系统各级队长的 稳态联合分布，系统忙期长度分布等其它指标，且给出了求稳态解的m a r l a b 程序。 在本文模型三假设下利用矩阵分析方法得到了系统这至0 稳态所应满足的充分必要 条件。由于矩阵及递推的运算在计算机上容易实现，因此本文的结论便于应用。 关键词：运筹学，稳态概率分布， 程，p h 分布，生灭过程，拟生灭过程， j a c k s o n 排队网络，串联排队网络，m a r k o v 过 矩阵分析 a b s t r a c t t w ok i n d so fn - - n o d et a n d e mo p e nq u e u i n gn e t w o r ks y s t e mw i t he x p o n e n t i a ld i s t r i b u t i o na x ea n a l y z e di nt h i sp a p e r t h e g e n e r a t e rm a t r i x e so fm a x k o vp r o c e s sa r e 百v e n i nr e c u r r e n c ef o r m u l a t e s e p e r a t e l y , t h es o l u t i o no ft h es y s t e ms t a b i l i t y , t h es t a t i o n a r y c o m b i n a b l ed i s t r i b u t i o no fe a c hn o d eq u e u el e n g t ha n dt h eb u s yt i m ed i s t r i b u t i o ni s o b t a i n e db ym e n , i so fm a t r i xa n a l y s i si nt h es e c o n dm o d e l m o r e o v e rw e g a v eo u tt h e m a t l a bp r o g r a mf o rs l o v i n gt h es y s t e ms t a b i l i t ys o l u t i o n 。t h es u f f i c i e n t - n e e e s s i t y c o n d i t i o nf o rt h es y s t e ms t a b i l i t ya n dt h ed i s t r i b u t i o no fs t a t i o n a r yq u e u el e n g t ha r e o b t a i n e db ym e a n so fm a t r i xa n a l y s i si nt h et h i r dm o d e l s i n c et h eo p e r a t i o no fm a t r i x a n dr e c u r s i o na r ee a s yt op e r f o r mo n c o m p u t e r s ，t h ec o n c l u s i o n so ft h i sp a p e rc a nb e c o n v e n i e n t l ya p p l i e d k e y w o r d s ：o p e r a t i o nr e s e a r c h i n g ，s t a t i o n a r yp r o b a b i l i t yd i s t r i b u t i o n ，j a c k s o n q u e u e i n gn e t w o r k ，t a n d e mo p e nq u e u e i n gn e t w o r k ，m a x k o vp r o c e s s e s ，p hd i s t r i b u - t i o n ，b i r t ha n dd e a t hp r o c e s s e s ，q u a s ib i r t ha n dd e a t hp r o c e s s e s ，m a t r i xa n a l y s i s 硕士论文串联排队网络系统分析 引言 排队论是运筹学的重要组成部分。二十世纪初丹麦数学家、电气工程师 a k e r l a n g 把概率论应用于电话通话问题，从而开创了这门科学。2 0 世纪3 0 年代 中期，当w f e l l e r 3 i 进了生灭过程时，排队论才被数学界承认为一门重要的学科。 2 0 世纪4 0 年代排队论在运筹学这个领域中成了一个重要的组成部分。2 0 世纪5 0 年代 初dgk e n d a l l 对排队论作了系统的研究。他用嵌入马尔可夫( a m a r k o v ) 链方法研 究排队论，使排队论得到进一步的发展。2 0 世纪6 0 年代起排队论研究的课题口趋复 杂，出现了排队网络的研究。 排队网络是指由一些服务点和联结它们的路径所构成的总体，其中每个服务 点相当于一个单台或多台的排队系统，顾客在一个服务点接受完服务后按照一定 的规律沿着路径到下一个服务点接受服务。 最早考虑的排队网络模型是j a c k s o n ( 1 9 5 7 ) 提出的网络，后称j a c k s o n 网络，或 j a c k s o n 开网络，或指数开网络，它由m 个编号为1 ，2 ，肘的服务点所组成，其中 第i 个服务点包括 个独立同分布的指数分布服务时间的服务台，第i 个服务点的外 部输入是参数为九的p o i s s o n 流，各服务点的外部输入与各服务时间为相互独立。 在第i 个服务点接受服务后的顾客立即以概率p 沿路径转移到第j 个服务点排队等 待服务，而以概率q l = 1 一墨l 肋离开系统，对于指数开网络，容易证明它具有 乘积型解，也即网络的平稳分布等于各服务点平稳分布的乘积。菪在j a c k s o n 网络 中令所有k = 0 ，即没有外部输入；令所有吼= 0 ，即没有输出；且假定系统中顾客总 数为固定的n ，便得到指数闭网络，或j a c k s o n 闭网络，或g o r d o n - n e w e l l 网络( g o r d o n & n e w e l l ( 1 9 6 7 ) ) 对于指数闭网络，平稳分布仍然是乘积型的，此时各乘积项可以 看成是带有p o i s s o n 输入的各服务点单独存在时的平稳分布，但并非是网络中各服 务点的边缘分布，也就是说，这些服务点中的顾客数相互不独立。各服务点中顾 客数的不独立性是显而易见的，因为此网络中顾客总数固定。此后，逐渐开始研 究非指数网络是否能具有乘积型解。 m u n t z ( 1 9 7 2 ) 研究了p o i s s o n 输入蕴涵p o i s s o n 输出这种性质，记为m 辛m ，证明 了服务点具有m 号m 性质的网络具有乘积型解，同时该网络也具有m 净m 性 质。b a s k e t t 等( 1 9 7 5 ) 证明对一般服务分布的多类顾客网络，只要排队规则为处理机 分享( p r o c e s s o r - s h a r i n g ) ，后来先服务的强占继续型( l a s t c o m e - f i r s t - s e r v e d p r e e m p t i v e r e s u m e ) 、或无穷多个服务台，平稳分布仍为乘积型的。c h a n d y 等( 1 9 7 7 ) 证明了在 非指数服务情形，具有乘积型解的网络的排队规则必须是即刻服务规则，也即顾 客在到达时刻必须立即开始接受服务。因此，像先来先服务、优先权服务等非即刻 服务规则不能产生乘积型解。n o e t z e t ( 1 9 7 9 ) 提出了一种更一般的排队规则l b p s ( 末 硕士论文 串联排队网络系统分析 2 批分享处理机，l a s t - b a t c h p r o c e s s o r - s h a r i n g ) ，它包括上述处理机分享、后来先服务 的强占继续型、和无穷多个服务台为特例，证明了在一类更广泛的对称排队规则 中，l b p s 类是唯一的对所有服务分布都能产生乘积型解的类。另外，k e l l y ( 1 9 7 6 ) 与 b a r b o u r ( 1 9 7 6 ) 1 0 考虑了包括多种路径方式，多种排队规则在内的多类顾客，般 服务分布的网络，利用可逆性给出了一种乘积型解。 最近，s e r f o z o ( 1 9 8 9 ) 研究了路径与服务速度依赖于系统拥挤长度的m a r k o v 网 络，它把通常考虑的各服务点的服务相互独立、各顾客选择路径相互独立的网络 包含在内作为特例，而且现在的模型更便于描述并行处理，由于容量受限的转移 阻塞、避免拥挤而改变路径、以及增加或缩减处理速度以适应后面路径的拥挤等 现象。他引进了描写各服务点顾客数的一般网络过程，导出了它的平稳分布，此 分布具有向量函数的乘积型。v a nd i j k & r a m a s e w i c z ( 1 9 9 1 ) 考虑了具有一般服务需 求的网络，其路径依赖于顾客在下一服务点所需的服务时间，求得了非标准的乘 积型解。 服务点容量有限的网络一般没有乘积型解，除非路径可逆( 见k e l l y ( 1 9 7 9 ) ) ，或遇 到服务点容量饱和时顾客会越过此服务点，如同此时的服务速度等于o 。对后面这 种情形，以前文献中的证明都是直观的，而v a nd i j k ( 1 9 8 8 ) 贝l j 给出了简单、严格的 证明。 对有阻塞的非指数网络，v a nd i j k ( 1 9 9 1 ) 研究了顾客遇到阻塞时服务“停止”或 “重复”两种类型。在某种条件下，两种类型被证明是等价的，而且可导出乘积型 解。 串联排队网络系统在港口( 海港，航空港) 运输、计算机通讯、交通控制、存 储系统、生产管理、柔性制造系统、生产流程等领域中的应用十分广泛，特别是 有限容量的排队系统网络更是如此。有限容量的串联排队网络系统，人们研究得 较多的是用逼近的方法，求系统指标的近似数值解。如：a l t i o k 2 ( 1 9 8 9 ) 、b r a n d w a j n & j o w 4 ( 1 9 8 8 ) 、g e r s h w i n 3 ( 1 9 8 7 ) 、h i l l i e r & b o l i n g 5 ( 1 9 6 7 ) 等，这些方法在 计算上具有不同程度的精确性和复杂性。关于有限容量的串联排队网络系统指标 的精确求解，这方面的工作不多，而且大多考虑比较简单的系统，如：k o n h e i m r e i s e r 1 5 ( 1 9 6 7 ) 考虑了系统m m 1 一肘1 ，用复分折的方法给出了系统平稳的 充要条件及平稳概率分布；l a t o u c h e & n e u t s ( 1 9 8 0 ) 用矩阵分析理论给出了系统 m m r m c k 的平稳队长分布。徐光辉【27 ( 1 9 9 2 ) 更为一般地推广了有限容量 的的两级串联排队网络系统模型。用矩阵分析理论对系统m 忙) t m c p h ( 7 ) 1 k 进行了研究，得到了其状态过程的q 一矩阵，给出了系统平稳的充要条件、平稳队 长分布及其算法等系统的平稳性态指标；在本文中，我们研究了有限容量的级串 联排队网络系统模型，得到了其状态过程的q 一矩阵，得到了该系统的稳态解及其 硕士论文串联排队网络系统分析 3 系统各级队长的稳态联合分布，系统忙期长度分布等其它指标。给出了系统平稳 的充要条件、平稳队长分布等系统的平稳性态指标。 1 1 生灭过程 第一章基本理论和方法 1 ，生灭过程的定义假设有一系统，该系统具有有限个状态o ，1 ，k 威可数 个状态0 ，1 ，令( t ) 为系统在时n t 所处的状态在任一时刻t ，若系统处于状态i ，则 在( ，t + a t ) 内系统由状态i 转移到状态i 十1 ( 有限状态时0si k ；可数状态时0 i o 为一常数丽由状态i 转移到状态t l ( 有限状态 时l i ；可数状态时1 i o 为一常数；并且 在( ，t + a t ) 内发生两次或两次以上转移的概率为o ( ) 这样一个系统状态随时间变 化的过程( ) 就称为一个生灭过程 2 生灭过程的微分方程组令只( t ) 为系统在时刻披e 于状态i 的概率，即 只( t ) = p n ( t ) = f 系统在时刻t + a t 处于i ( 有限状态时0 i ，可数状态时0 i o o ) 这一事件可以 在下列互斥情形下发生： ( 1 ) 系统在时刻域b 于i ，而在( t ，t + t ) 内没有变化它的概率为 只( t ) ( 1 一九一z | i a t ) + d ( ) ； ( 2 ) 系统在时刻处于i 一1 ，而在( ，t 十t ) 内由i - 1 转移到e 它的概率为 只一l ( t ) a 一1 t + o ( t ) ； ( 3 ) 系统在时n t 处于i + 1 ，而在( ，t 十a t ) 内由i + 1 转移到i 它的概率为 只+ 1 ( t ) # i + l a t + d ( t ) ； ( 4 ) 系统在( t ，t + a t ) 内发生两次或两次以上转移，它的概率为d ( ) 故由全概率定理，在有限状态时， r 0 + a t ) = 只( t ) ( 1 一九t 一z a t ) 十p i 一1 ( t ) ，x a t + 只+ l ( t ) m a t + o ( a t ) ，0 t k 硕士论文水联排队网络系统分析 移项后，两端都除以t ，得 雎垒a ! 挫t k a ，一lp 一l ( ) 一( 九+ “) p i ( ) 十肌+ lp f + 1 ( t ) + o ( t ) ，o i k 0 令a t 一0 ，即得 爿( t ) = a i - 1 只一l ( t ) 一( a 。+ m ) p f ( t ) + 肛件1 只+ 1 ( ) ，0 i o ，j o ， ( 17 ) i 4 且与初始条件无关 现在来看方程组( 11 ) ，( 12 ) 与( 1 3 ) ，由于t o 。时右端极限存在周而左端极限也 存在，即 1 ) n 只( t ) ，i 0 存在，因而必有 l i m 只( t ) = 0 ，i 0 ( 1 8 ) 事实上，若有某i ，使 ：l 。i m 。( t ) 3c 0 ， 不妨假设q o ( q o 。 o ，则存在一个t o ，当t o 时，p i ( t ) 啦撒 l i r a 。p i ( ) = l i m 。【r ( t o ) + 爿( u ) d u 】 只o o ) + l i m t 。丘，d u = 只( t o ) + l i r a 。m ( t t o ) = 0 ( 3 此：t - p ( t ) l 矛盾，因而必有( 1 8 ) 式 - t 点! e ( i 1 ) ，( 1 2 ) 与( 1 3 ) o o z e t o 。，l i b ( 1 7 ) 、( 1 8 ) e p 得 fo = 一1 p 一1 一# k p k 0 = 九1 p i 一1 一( 九+ m ) p i + # t + l p i + l ，0 t k ， o = 一 。p 。+ 肛l p l ( 当可数状态时，只需将第一式划去，并将第二式中的k 改成o 。即可) 由此得 fa k l p k 一1 一 2 k p k = 0 ， a i p 一肛t + i p i + l = a l 一1 p 一1 一p p i ，0 i k ( 当可数状态时，只需将上述第一式中2 _ i j k 换成j 1 ，并划去第二式即可) 其 功= 1 ( 1i l ) 1 1 十羔t 等等 ( 当可数状态时，只需将上式中的换成o 。即可m ( i 5 ) ，此级数是收敛的) 1 2 矩阵解析法 ( 11 2 ) 由n e u t s 发展的矩阵解析法在这十多年来得到空前的进展，他的两本专著( 1 9 8 1 ， 1 9 8 9 a ) 是关于这一方法的理论基础和应用领域的代表作。他的两本专著分别讨论 了拟生灭过程与m a i 型m a r k o v 过程的基本周期( 特别，包括忙期在内) ，以及它 们的矩公式。以p h 分布为基础，n e u t s 弓i 进了a l m 1 型与m g 1 型两类m a r k o v 过 程，使得原来在指数分布假定下才能分析的很多随机模型推广至t p n 分布的情形。 由于p h 分布可以逼近任意非负随机变量的分布，从而使一般分布假定下的随机模 型能够得到易于计算的逼近。 1 2 1 拟生灭过程 拟生灭过程( q u a s ib i r t ha n dd e a t h p r o c e s s ) 是经典生灭过程的最新发展，是经 典生灭过程( 王梓坤，1 9 8 0 ) 从一维状态空间到多维状态空问的推广。正如生灭过 程的生成元具有三对角形式一样，拟生灭过程的生成元是分块三对角矩阵。近二 十年已成为复杂随机模型分析的重要工具。 硕士论文 串联排队网络系统分析 考虑一个二维m a r k o v 过程 x ( ) ，l ，( t ) ) ，状态空间是 f 2 = “ ，j ) ，k 0 ，l j r n ) ， 称 x ( t ) ，i ，( ) 是一个拟生灭过程，如果其生成元可写成下列分块三对角形式 a o 岛 ib 1 ag q = ibag ibag 8 ( 1 1 3 ) 其中所有子块都是1 1 1 阶方阵，满足 ( a o + c o ) e = ( b i + a + c ) e = ( a + b 十e ) e = 0 ， 月。和a 有负的对角元素和非负的非对角元素，其余子块均是非负阵，称状态集 ( ，1 ) ，( k ，2 ) ，( k ，m ) 为水平。若过程是正常返的，m ( x ，l ，) 表示过程( x ( t ) ，l ，( ) ) 的极限变量，并记 啊2 恕尸体( ) = ，( ) 一j ) = p x = ，l ，= j ) 其中0 ，1 茎j 墨m 为适应q 的分块形式，将稳态概率按水平写成分段形式 7 r k = ( 7 r k l ，7 t k 2 ，一，7 ( k 。) ，女0 我们直接引用下列结果，证明见文献 1 】第三章。 定理1 2 1 过程q 正常返，当且仅当矩阵方程 月2 b + r a + c = 0 的最小非负解r 的谱半径s p ( r ) j嚣只。路r 吼 i j 【e 倒弓= 1 第二章杰克逊串联开排队模型 2 1 两级杰克逊串联开排队模型 假定随机服务系统由串联的两个等待制的服务台组成，输入是参数为a 的最简 单流，顾客到达后先由第一台服务，之后再进入第二台服务，第二台服务完后，顾 客离去。设第一台与第二台的服务时间相互独立，分别是参数为p l 与肛2 的负指数 分布，并且与到达间隔独立。 我们说系统在时刻t 的状态n ( t ) = ( i ，j ) ，若此时第一台前等待的顾客数与被服 务的顾客数之和为i ，而第二台前等待的顾客数与被服务的顾窖数之和为j ，状态空 间为 ( ，j ) ，i ，j = 0 ，l ，) 令 r ，j ( t ) ep i n ( t ) = ( i ，j ) ) ( 21 7 ) 定理2 1 1 ( t ) 为一马尔可夫过程，极限 l i mb ，a t ) = p ，j 是存在的，且与初始条件无关。 2 1 1 微分方程组 首先写出状态转移方程组 p 0 ，0 0 + a t ) = ( 1 一a t ) p o ，o ( t ) 十# 2 a t p o ，l ( t ) + o ( a t ) 只，o ( + a t ) =a a t 只一l ，o ( t ) + ( 1 一 t p l t ) p i ，o ( t ) - p # 2 t t 只。1 ( t ) + o ( a t ) ，i o ； p o z ( t + a t ) = p 1 t p l ，j l ( t ) 十( 1 一a t 一# 2 a t ) p o a t ) + # 2 a t p o j + l ( t ) + o ( t ) ，j 0 ； p i ，( t + a t ) =a a t 只一1 ，j ( t ) 十( 1 一a 一“1 t 一# 2 a t ) p i ，j ( t ) + # l a t p i + 1 p 1 ( ) + 肛2 蝎口+ 1 ( t ) + o ( a t ) ，i ，j 0 硕士论文半联排队网络系统分析 1 2 移项后除以，在令tl0 ，即得微分方程组 a 尸0 ，o ( t ) 十2 p 0 ，l ( ) a 只一1 ，o ( ) 一( a + f 1 ) 只，o ( t ) 十卢2 只1 ( t ) ，i 0 p lp l j 一1 ( 亡) 一( a + 肛2 ) 尸0 ，( ) + 肛2 p 0 ，j + 1 ( 亡) ) ，j o ； ( 21 8 ) p i l ，j ( ) 一( + p l + p 2 ) 尸 ，j ( z ) + 肛l r + l ，j l ( ) 2 1 2 求极限解 假定 以 0 ) p o j = p lp l ，j 一1 + p 2 p o ，j + l ， 0 ； + 肛2 ) p i ，j = a 只一1 ，+ 肛1 只+ 1 j 一1 + 肛2 只，j + l ，i ，j 0 我们说，方程组( 22 1 ) 满足正则性条件 p 。j = 1 i , j = o 的解为 p 坷= ( 1 一p i ) ( 1 一m ) p i 厉 这由直接验算即可证明。 2 1 3 一些讨论 推论1 由( 2 2 3 ) ，第一台中等待与被服务的顾客总数等于 的概率为 。 肌i p 幻= ( 1 一p - ) ( 1 一p 2 ) 店岛= ( 1 一p ，) 店 j = oj = o ( 2 1 9 ) ( 2 2 0 ) ( 2 2 1 ) ( 22 2 ) ( 22 3 ) ( 2 2 4 ) 删脚删 玮，r j伟，巴 2l = 一 令 淳p 硕士论文 半联排队网络系统分析 推论2 第二台中等待与被服务的顾客总数等于j 的概率为 1 3 o o p ，；巩，= ( 1 一p ) ( 1 一p 2 ) p i 以= ( 1 一p 2 ) 店； ( 22 5 ) i = 0t = o 由此可见，第一台与第二台的顾客数是独立的，1 y 的分布都与参数 的p o i s s o n 输 入的单服务台系统的结果相同。 2 2 m 级杰克逊串联开排队模型 假设有一个有m 个节点，节点i 有m i 个服务台的串联排队网络系统，其中 = l ，2 ，m 。在串联排队网络中设所有节点的服务相互独立，节点 的m 1 个服务台 的服务时间均服从参数为地的负指数分布，i = 1 ，2 ，m 。顾客按参数，为a 的泊 松过程到达系统，并依次在第一个节点，第二个节点，第m 个节点分别任选一 个空着的服务台接受服务在第m 个节点接受完服务后离开整个系统，并设每个节 点前面的排队空间无限，对此网络，令 p f = 二l( = 1 ，2 ，m ) p t 2 磊“2 1 ，2 埘j 若p 0 ，宄 e ，且 p ( 元) ) 构成分布。下面先假设所有的p ( 宄) o ，也即假定网络系统平稳分布存 在，并记( t ) 弱收敛的极限为n ，即尸 = 研= p ( 固，由此就可列出 p ( 存) ，元 e ，所满足的平衡方程组： 【竺1 ( a t ( 毗) p 。十 矿( t ) ) p ( 矗) = d ( n 1 ) p 何一e 1 ) 4 - 竺i 16 ( 竹t + 1 ) 口。( m + 1 ) m p ( 元4 - e ，一e 件1 ) ( 2 2 7 ) + t t m a m ( n m4 - 1 ) p ( 元+ e m ) 元e 硕士论文串联排队嘲络系统分析 其中e i 为第i 个分量为1 ，其余为零的m 维向量 1 5 a c n ，； ；。n 5 。m ；i 。，；0 ：! ： 等式左边为所有离开元状态的发生率= 等式右边为所有进入宄状态的发生率；a i ( n d m + a 口( t ) 为队列在队长为时的离去率。o c i ( n i + 1 ) “就是当队列为 的长度为n 十1 时有 元+ e i e i + l 状态进入元状态的发生率。a m ( “m + 1 ) a m 就是当队列为m 的长度3 b r i m + l 时有元+ 8 m 状态进入谢犬态的发生率；6 ( n 1 ) a 就是队列为1 的长度为n l 时有再一e l 状 态进入亓状态的发生率且n l l ；令 品蝴- 1 ) 艰删1 2 ， ( 2 2 8 ) 【凤( n ) 。( n ) 凤( n 一1 ) = n l m n = ， 并作代换 p ( 元) 由( 2 2 8 ) 可知： ，( n f + 1 ) 阿1 ( 礼；十1 ) = p _ 1 ( n 。) 笞1 ( 一1 ) = ( 嘞) 再1 ( 码) 则由( 22 7 ) 即得： 再假定 f 2 2 9 1 筌。( q 。( n ；) 肛i + a 0 ) ) 0 ( 商) = 6 ( n 1 ) a q ( 开一e - ) d l ( n ) + 兰 1 啦( m + 1 ) 胁q ( 开+ 岛一e l + 1 ) ( 23 0 ) 十p m q ( 再+ e m ) 元e 其中b 为常数，则得 ( 2 3 1 】 h i d ( 啦) ( m d o 一1 ) “一l z i l 而) 一a 口o ) q ) + a p m 。 彳= 0 ( 2 3 2 ) t = i 在( 2 3 2 ) 中取行= ( 0 ，0 ，o ) e p 得 a = # m x m ( 2 3 3 ) _ n 盯 村m e_ n n i z m n b l | _ n 0 预士论文 书联排队网络系统分析 将( 23 3 ) 代入( 2 3 2 ) ，再取齐= e 坝0 得： ，。z 。= j 0 1 ) m 一1 z ：一1 十a o ( i )l 兰i m 再由( 2 3 3 ) 解得： x i = a 加。1 i m 将( 23 4 ) 代x ( 2 3 1 ) 与( 22 9 ) ，得到( 2 2 7 ) 的解： 跗垂锵 现假定 a 0 所以( ，oa n ) 可逆是 显然的。 性质2 矩阵( 礤一。十碥一，b n 一- ) o ( - - a n ) 是可逆矩阵。 证明矩阵( 碍一l + 碍一。b n 一1 ) o ( - - a n ) j 邑上- - n 矩阵，且是对角占优矩阵，所以 可逆。 1 、l ， 、1 ， )：又)：卫矿 0 、0 、o 邺)：父)：卫即矿 汪磋 堡主堡皇 坐壁整丛堕垫墨篓坌堑 2 l 3 3 串联开排队网络系统的稳态结果 如果系统已运行了相当长的时间，使得在任何时刻各项数量指标的变化规律 都已相同，且不再受初始条件的影响，我们就称此时系统已处于统计平衡，系统 的状态就称平稳性态，用数学语言来说，就是一0 0 时极限概率分布存在，且与初 始条件无关。 定理3 , 3 1 设y = ( y o ，h ，k ，琢。) ，k r m , v ，i = 而是级串联排队系统 的状态稳态概率解，则k = y o r i ，l isk n 而k 是由下列线性非奇次方程组确 定： 其中： ( 俨u t ) 埽 o 机一，11 t | ) + 嘴一。 + r k ， i o a + ( 礤一l + 碍一1 b ，一1 ) o ( 一a ) 】 k ，n v = e 0 + r e l ( e o ，e 1 分别是与碥，h 维数相同的全l 列向量) = l r i = 凰+ 璐一1 c g i ，l i 尺一1 口= ， ( 一h ) j _ 1 。r 蛳= 一r k , , - 1 碟一1 【( 碥一1 + 碟一1 b 一1 ) o ( 一a ) - 1 l = 0 ， f 2 = 昂一l gg 1 = ，g 2 = 磲一lo ( 一a ) 】g h ”l = 趣一1 礤一1 c 十吼【碍一1o ( 一a ) g 1 i k n 一1 g 件1 = g i 一1 _ p 寿一1 c + g 。i 尸盎一lo ( 一 ) g 1 i k n 一1 证明记y = ( k ，k ，m ，幺k ) 是级串联排队系统的状态稳态概率解，则有平 衡条件知y p n = 0 即y 满足以下线性非奇次方程组： o 一嗡 + ，r 吣h 十 一 | | 矿 硕士论文半联排队网络系统分析 2 2 碥礤一1 + m ( ， a n ) = 0 礤一1 + h ( 碍一l e ( 一a n ) ) + k ( ，oa ) = 0 一1 礤一l + m ( 臻一l o ( 一a r ) ) + m + 1 ( 1 0a r ) = 0 2 茎i 茎k n 一1 1 - 碍一，+ 坛。【( 礤一，+ 礤一。鼬一- ) o ( 一a ) 】= 0 k n k e o + m e ，= 1 以下对此方程组求解： 由( 3 3 ) 式得： m + 1 = m l 碍一1 【io ( 一 ) - 1 + m p g 一，o ( 一a n ) l i to ( - a ) l _ 1 或 m + l = 一1 碍一1 c + m 尸品一lo ( 一a n ) 】g 由( 3 2 ) 式得：k = y o 碍一l c + m 碍一1o ( 一a ) 】g 由( 3 1 ) 式得：h = k p 品一。c 解( 36 ) ，( 3 7 ) ，( 3 8 ) 式可给出以下递推形式的系数矩阵：令 h 1 = o ，h z = p l , 一l c ，g 1 = ，g 2 = f 碍一lo ( 一a ) 】g 皿+ 1 = 皿一1 碟一l c + 皿 碍一1o ( 一a ) 】g ， 1 i k _ 一1 g 冲1 = g 一1 p ，z ，一1 c 十g ，f p g 一1 0 ( 一 ) g ， 1 i 一1 所以：m = y o 风+ m g i 1s 耳一1 将( 3 8 ) 式代n ( 3 9 ) 式得：k = y o ( u , + 尸品一l c g i ) 于是令：r = 凰+ 礤一l c g i ， 1 i k n 一1 由( 3 4 ) 式直接得：坛。= 一碥r 鼬一l 礤一l 【( 碍一l + 礴一l b n 一1 ) o ( 一h ) _ 1 f 31 1 ( 3 2 ) ( 3 3 ) ( 3 4 ) ( 3 5 ) ( 3 6 ) ( 3 7 ) ( 3 8 ) ( 3 9 ) 硕士论文串联排队网络系统分析 再令：r k 。= 一j r 耳，一尸寻一1 ( 尸爵一1 + 尸寻一1 b n 一1 ) o ( 一a ) 】一1 所以有：= k