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

摘要n 级串联开排队网络系统分析 摘要 串联排队网络系统在实际生产生活中的应用是相当广泛的，而且近几年来串 联排队模型得到了许多学者的研究，获得了不少成果。本文对此作了进一步的推 广，在多级串联排队系统中分别加入了反馈和启动，使之更符合实际生产生活的 需要。 针对上述情况，本文主要研究了两个模型，第一个为具有反馈的多级串联休 假排队模型，其中采用递推方式给出了马尔可夫过程的转移矩阵，并利用矩阵分 析方法进行求解，得到了该系统的稳态解及其它相关指标。第二个模型是在多级 串联排队系统的基础上引入了启动策略，也采用了递推的方式，给出了它的转移 矩阵，并求出了它的稳态概率解，顾客的稳态逗留时间，忙期长度等。由于矩阵 及其递推的运算在计算机上容易实现，因此本文的结论便于应用 关键词：串联排队，反馈，休假，启动策略，p h 分布 a b s t r a c tn 级串联开排队网络系统分析 a b s t r a c t t h et a n d e mo p e nq u e u e i n gn e t w o r ks y s t e mh a saw i d ea p p l i c a t i o ni na c t u a l p r o d u c t i o na n dl i v i n g i th a sb e e ns t u d i e db ym a n yr e s e a r c h e r sa n dal o to fr e s u l t s h a v eb e e no b t a i n e di nr e c e n ty e a r s i nt h i sp a p e rw em a k eaf u r t h e rr e s e a r c ho nt h i s s y s t e m w es t u d yt h em u l t i n o d et a n d e mo p e nq u e u e i n gn e t w o r ks y s t e m 、航t l l f e e d b a c ka n ds e t - u pt i m e i nt h i sc a s ei tw i l ls a t i s f yt h en e e do fa c t u a lp r o d u c t i o na n d l i v i n gb e t t e r f o rt h i sr e a s o n ，t h i sp a p e rm a i n l ys t u d i e st w ok i n d so fq u e u e i n gm o d e l s t h ef i r s t i sn n o d et a n d e mo p e nq u e u e i n gn e t w o r ks y s t e mw i mf e e d b a c ka n ds e r v e rv a c m i o n t h eg e n e r a t o rm a t r i xo fm a r k o vp r o c e s si sg i v e ni nr e c u r r e n c ef o r m u l a t i o n t h e s t e a d y s t a t ed i s t r i b u t i o na n do t h e rr e l a t i v ei n d e xo f t h es y s t e ma r eo b t a i n e db ym e a n s o fm a t r i xa n a l y s i st h e o r ya n dp r o b a b i l i t yt h e o r y t h eo t h e ri sn - n o d et a n d e mo p e n q u e u e i n gn e t w o r ks y s t e mw i t hs e t u pt i m e w eg e tt h eg e n e r a t o rm a t r i xi nr e c u r r e n c e f o r m u l a t i o no ft h es y s t e mt o o ，a n dg a i nt h ep r o b a b i l i t ys o l u t i o no ft h es y s t e m ，t h e d i s t r i b u t i o no fs t a y - t i m ea n dt h eb u s yt i m ed i s t r i b u t i o na n ds oo n s i n c et h eo p e r a t i o n o fm a t r i xa n dr e c u r s i o na r ee a s yt op e r f o r mo nc o m p u t e r s ，t h ec o n c l u s i o n so ft h i s p a p e rc a nb ec o n v e n i e n t l ya p p l i e d k e yw o r d s ：t a n d e mq u e u e i n g ，f e e d b a c k ，v a c a t i o n ，s e t - u pt i m e ，p hd i s t r i b u i t i o n i l 声明尸明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注矛暾谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 年7 月2 日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的全部或部分内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的全部或部分内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名：三墼建纠年 7 月2 日 硕上学位论文n 级串联开排队网络系统分析 第一章引言 本章对排队论的发展，串联开排队网络系统的研究内容、背景和现状作一些 简单介绍，同时阐明本文的主要研究内容和文章的结构。 1 1 排队论发展简介 排队论是运筹学的一个重要分支，它主要研究由于顾客的到达和离开以及服 务台的工作和休假，而引起的队伍的积累和消散问题。它起源于2 0 世纪初的电 话通话，二十世纪初丹麦数学家、电气工程师爱尔朗( a k e r l a n g ) 用概率论方 法研究电话通话问题，从而开创了这门新学科，并建立了许多基本规则。3 0 年 代中期，当费勒( w f e l l e r ) 引进了生灭过程时，排队论才被数学界承认为一门 重要的学科。在二战期间和二战以后，排队论在运筹学这个新领域中成为一个必 不可少的重要内容。2 0 世纪5 0 年代初肯德尔( d g k e n d a l l ) 对排队论作了系统 的研究，他用嵌入马尔可夫链( a m a r k o v ) 方法研究了排队问题，使排队论得 到了进一步发展。从此，随着研究的深入，排队理论日益得到广泛应用。人们发 现通信系统，网络设计、计算机存储、交通系统、物流调度等各种现象都可以通 过排队模型来描述，同时应用相应排队理论的研究成果，可以指导各种策略设计， 给国民经济的发展带来巨大的贡献。 排队系统尽管千差万别，但都可以抽象为由顾客和服务台构成，它有三个组 成部分：输入过程、排队规则和服务机构。输入过程是描述顾客的来源和顾客是 按怎样的规律到达排队系统的；排队规则一般分为等待制、损失制和混合制，在 等待制和混合制中通常又可分为先来先服务、后来先服务、随机服务、优先非抢 占服务、优先抢占服务等；服务机构主要是指服务台的数目，可以分为单服务台、 有限个服务台和无限多个服务台。进行服务时服务的方式可分为并联和串联，接 受服务的顾客可以是成批的也可以是单个的，服务时间可以服从不同的分布，一 般分为定长分布、指数分布、几何分布与一般分布等。 沿用k e n d a l l ( 1 9 5 1 ) 采用的表示方法，一个排队过程通常采用符号a b c x y 其中a 表示顾客到达间隔时间分布的类型，b 代表服务台服务时间分布的类型， c 表示服务台的台数，x 表示队伍的容量，y 表示排队规则。如m m c 表示泊 松到达，服务时间服从指数分布、c 个服务台、无限等待空间的排队系统。 第一章引言硕十学位论文 分布排队规则 符号解释符号解释 m 指数分布 f c f s先来先服务 e n e r l a n g 分布 l c f s后来先服务 p p a r e t o 分布 r o s随机服务 p hp h 分布p r优先权服务 g一般分布g d一般规律 表1 1 1 排队常用记号 一个排队系统要从两方面考虑，即服务机构和顾客的利益来考虑，顾客希望 的等待时间越短越好，那就需要服务机构的服务台越多越好，而服务机构要想获 得很高的利益就必须限制服务台的个数。综合考虑排队的几个指标：队长、等待 时间、和服务台的忙期，成为排队论的主要研究内容。 1 2 排队论的经典研究方法 自排队论这门学科形成以来，新的研究方向和研究方法层出不穷。大量的科 研工作者在此领域取得了丰硕的成果。排队论专家田乃硕等把矩阵解析法引入 g i m 1 型休假排队系统，并研究了部分服务台同步的休假排队模型，极大的丰 富了排队模型的理论；史定华将频度转移法用于可修服务系统并且对可靠性作了 大量工作；g e l e n b e 将负顾客引入排队系统。当前，排队论的研究主要集中在排 队网络、矩阵解析法、数值计算、极限定理以及特殊模型等方面。 经典的排队理论主要是建立在模型满足马氏性的基础上，探讨平稳状态下系 统的队长、等待时间等统计特征量。一般来说，经典排队理论的求解方法主要有 以下几种：一为嵌入马氏链法( e m b e d d e dm a r k o vc h a i n ) ，今被发展至马氏更新 法。这种方法关键通过寻找过程的再生点或马氏点，运用马氏链的技巧或建立更 新方程来得到系统的统计特征量。由于该方法较多地用到模型的概率意义解释， 从而需要较多的概率论知识作为基础并且比较复杂。二为补充变量法。该方法通 过增加变量，构造向量马氏过程( v m p ) 从而建立密度演化方程，并求解各种 统计特征量。这种方法将随机性的排队论问题转化为确定性的方程求解，极大地 降低了求解过程的复杂程度，但对方程求解的技巧要求较高且通常仅可得到解的 拉氏变换，而且关注的只是过程的状态概率而非转移概率。具体方法精髓可参考 徐光辉【l1 】三为n n e u t s 教授提出的q b d 过程理论，他将生灭过程的方法加以推 广和引申，逐渐形成了一套可以处理一系列相关于p h 、m a p ( 马氏到达) 及 b m a p ( 批马氏到达) 分布所构成的排队模型。尤其值得提出的是q b d 理论已形成 了完整的算法程序，为排队论模型的研究提供了较好的实证结果。其余的还有国 2 硕上学位论文 n 级串联开排队网络系统分析 内侯振挺教授提出的马氏骨架方法 2 1 】、国外b r i l l 教授提出的水平穿越方法 5 l 】 等。 1 3 串联开排队网络系统的研究内容、背景和现状 1 3 1 串联开排队网络系统的研究内容、背景 排队网络是指由一些服务点和联结它们的路径所构成的总体，其中每个服务 点相当于一个单台或多台的排队系统，顾客在一个服务点接受完服务后按照一定 的规律沿着路径到下一个服务点接受服务。 最早考虑的排队网络模型是j a c k s o n ( 1 9 5 7 ) 2 8 提出的网络，后称j a c k s o n 网 络，或称是j a c k s o n 开网络，或指数开网络，它由m 个编号为l ，2 ，m 的服务点 所组成，其中第f 个服务点包括m ，个独立同分布的指数分布服务时间的服务台， 第f 个服务点的外部输入是参数为a 的p o i s s o n 流，各服务点的外部输入与各服务 时间为相互独立。在第f 个服务点接受服务后的顾客立即以概率p ，沿路径转移到 第歹个服务点排队等待服务，而以概率q ，= 1 一：l p 离开系统，对于指数开 网络，容易证明它具有乘积型解，也即网络的平稳分布等于各服务点平稳分布的 乘积。若在j a c k s o n 网络中令所有五= 0 ，即没有外部输入：令所有q ，= 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 ( 19 6 7 ) 3 9 ) 对于指数闭网络，平稳分布仍然 是乘积型的，此时各乘积项可以看成是带有p o i s s o n 输入的各服务点单独存在时的 平稳分布，但并非是网络中各服务点的边缘分布，也就是说，这些服务点中的顾 客数相互不独立。各服务点中顾客数的不独立性是显而易见的，因为此网络中顾 客总数固定。此后，逐渐开始研究非指数网络是否能具有乘积型解。 m u n t z ( 1 9 7 2 ) 4 0 】研究了p o i s s o n 输入蕴涵p o i s s o n 输出这种性质，记为 mjm ，证明了服务点具有mjm 性质的网络具有乘积型解，同时该网络也 具有mjm 性质。b a s k e t t 等( 1 9 7 5 ) 4 1 证明对一般服务分布的多类顾客网络， 只要排队规则为处理机分享( 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 ) 4 2 i i 明了在非指数服务情形，具有乘积型解的网络的 排队规则必须是即刻服务规则，也即顾客在到达时刻必须立即开始接受服务。因 此，像先来先服务、优先权服务等非即刻服务规则不能产生乘积型解。 n o e t z e t ( 1 9 7 9 ) 4 3 】提出了一种更一般的排队规则l b p s ( 末批分享处理机 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 ) 4 4 】与 第一章引言硕士学位论文 b a r b o u r ( 1 9 7 6 ) 2 9 贝j j 考虑了包括多种路径方式，多种排队规则在内的多类顾客， 一般服务分布的网络，利用可逆性给出了一种乘积型解。 最近，s e r f o z o ( 1 9 8 9 ) 4 5 研究了路径与服务速度依赖于系统拥挤长度的 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 ) 4 6 考虑了具有 一般服务需求的网络，其路径依赖于顾客在下一服务点所需的服务时间，求得了 非标准的乘积型解。 服务点容量有限的网络一般没有乘积型解，除非路径可逆( 见k e l l y ( 1 9 7 9 ) 4 7 】) ，或遇到服务点容量饱和时顾客会越过此服务点，如同此时的服务速度等于 o 。对后面这种情形，以前文献中的证明都是直观的，而v a nd i j k ( 1 9 8 8 ) 3 6 】则给出 了简单、严格的证明。 对有阻塞的非指数网络，v a l i di j k ( 1 9 9 1 ) 4 8 研究了顾客遇到阻塞时服务“停 止”或“重复”两种类型。在某种条件下，两种类型被证明是等价的，而且可导出 乘积型解。 1 3 2 串联开排队网络系统的研究现状 串联排队网络系统在港口( 海港，航空港) 运输、计算机通讯、交通控制、存 储系统、生产管理、柔性制造系统、生产流程等领域中的应用十分广泛，特别是 有限容量的排队系统网络更是如此。有限容量的串联排队网络系统，人们研究得 较多的是用逼近的方法，求系统指标的近似数值解。如：a n i o k 【2 3 】( 1 9 8 9 ) ， b r a n d w a l n & j o w 2 5 ( 1 9 8 8 ) ，g e r s h w i n 2 4 ( 1 9 8 7 ) ，h i l l i e r & b o l i n g 【2 6 】( 1 9 6 7 ) 等，这 些方法在计算上具有不同程度的精确性和复杂性。关于有限容量的串联排队网络 系统指标的精确求解，这方面的工作不多，而且大多考虑比较简单的系统， 如：k o n h e i m & r e i s e r 3 1 ( 1 9 7 6 ) 考虑了系统m m i 专m 1 k ，用复分析的方法给出 了系统平稳的充要条件及平稳概率分布；l a t o u c h e & n e u t s ( 1 9 8 0 ) 用矩阵分析理论 给出了系统，m 伦厦r 寸m c k 的平稳队长分布。 国内方面，徐光辉、袁学i j f j 7 更为一般地推广了有限容量的两级串联排队 网络系统模型，用矩阵分析理论对系统m o ) m c 专p h ( ，) i l l k 进行了研究， 得到了其状态过程的q 矩阵，给出了系统平稳的充要条件、平稳队长分布及其 算法等系统的平稳性态指标；贾波、周家良【8 在朋型级串联反馈开排队网 络系统分析中研究了明型级串联反馈开排队网络系统，采用递推方式给出了 马尔可夫过程的转移矩阵，并利用矩阵分析方法进行求解，得到了该系统的稳态 4 硕士学位论文 n 级串联开排队网络系统分析 解和相应的忙期长度；周家良【1 7 】基于朋型级串联反馈开排队网络系统分析 中对队长和忙期的研究方法，在朋阳l 反馈排队系统的逗留时间的文章 中，接着给出了逗留时间稳态分布。周家良 3 】( 1 9 9 8 1 ) 在上述排队模型的基础 上又增加了闭锁规则，研究了有阻塞的多级串联排队系统，得到了该系统的队长、 忙期长度、逗留时间等分布的简明精确显式解；周家良、贾波 1 3 】研究了具有n 个有限容量服务节点的j a c k s o n 网络，运用马尔可夫过程的状态空间及q 矩阵的 递推表示方法，富有技巧性的给出了相应的稳态显式精确解。苏时光、陈薇 1 4 】 研究了m x m c p h l k 的有限容量两级串联开排队系统，并给出了排队 平稳条件以及用矩阵迭代法得到了平稳队长分布和受阻概率分布；聂盼红【1 】 ( 2 0 0 4 ) 在串联开排队网络系统分析中主要研究了两类服从指数分布的有限容量 的级串联开排队网络系统模型，分别采用递推的方式给出了高维马尔可夫过 程的转移矩阵，在其模型二的假设下得到了其状态过程的q 矩阵，以及该系统 的稳态解及其系统各级队长的稳态联合分布，并在其模型三中研究了第一级容量 为的级串联开排队系统并给出了系统达到稳态所应满足的充分必要条件； 最近童金英、李清贵 1 6 】等( 2 0 0 6 ) 在二级c h a r k e s 串联排队系统中，运用马尔 可夫骨架过程得到了瞬时状态分布；基于上述级串联排队系统，郭志芳 2 】 ( 2 0 0 6 ) 把休假理论与之相合，研究了级串联休假开排队网络，得到了稳态 队长，忙期长度和逗留时间分布，并把计算机模拟和彷真应用到串联排队系统的 研究。 1 4 本文的主要研究内容和结构 本文主要研究了两个模型，第一个模型为在郭志芳在文献【3 】引入休假的基础 上，加入反馈的思想，运用矩阵解析的方法对有限容量的级串联反馈休假开 排队网络系统模型进行分析，得到了其状态的q 矩阵；其次分析了这个系统的 运行特征：稳态概率解，忙期，系统的各级队长的稳态联合分布等；第二个模型 为郭志芳在文献【3 】引入休假的基础上，把其模型的休假策略作了一个推广，引 入了启动策略，并把休假的位相推广到m 个。其中也是运用矩阵解析的方法对有 限容量的级串联休假排队网络系统模型进行分析，得到了其状态的q 矩阵； 并分析了这个系统的运行特征：稳态概率解，顾客的稳态逗留时间，忙期，系统 中顾客因不能进入系统而消失的概率等。 第二章预备知识硕：仁学位论文 2 1 生灭过程 第二章预备知识 2 1 1 6 1 生灭过程的定义 设马尔可夫链x = x ( ，) ，t 0 ) ，状态空间s = o ，l ，2 ，) ，若转移概率矩阵 p ( t ) = ( 胁( ，) ) 满足： 当h 充分小时， fb ，f + l ( 厅) = 无办+ d ( 办) ， 五o ，f 0 ， ip s ，f l ( 办) = 鸬办+ d ( 办) ， 鸬o ，f 1 ， 1 b ，( 办) = 1 一( 五+ “) 办+ d ( 办) ， t o = o ，f 0 l p o ( h ) = d ( 办) ， i o l l ，一，l 2 称x 为生灭过程 2 1 2t 1 1 】生灭过程的微分方程组 令p j ( t ) 为系统在时刻，处于状态f 的概率，即 只p ) = 尸 ( ，) = 母 系统在时刻，+ 缸处于f ( 有限状态时0 i k ；可数状态时0 ， o o ) 这一事件 可以在下列互斥情形下发生： ( 1 ) 系统在时刻，处于状态f ，而在时刻“+ a t ) 内没有变化。它的概率为 只( r ) ( 1 2 , a t 一f a t ) + o ( a t ) ； 。 ( 2 ) 系统在时刻，处于状态f 1 ，而在o + 出) 内由f 1 转移到i 。它的概率为 一l ( ，) 一l a t + o ( a t ) ； ( 3 ) 系统在时刻f 处于状态i + 1 ，而在o + a t ) 内由i + 1 转移到f 。它的概率 为足l ( 0 6 + l a t + d ( 出) ； ( 4 ) 系统在o + a t ) 内发生两次或两次以上转移，它的概率为o ( m ) 。 故由全概率定理，在有限状态时， 只o + a t ) = o ) ( 1 一x , a t 一j ，) + 一l o ) 五一l a t + 匕l ( t ) u 川a t + o ( a t ) ，0 f k ， 移项后，两端都除以缸得 p j ( t + a 忑t ) _ - 一p j ( t ) = 以一。一。( r ) 一( 五+ 鸬) ( f ) + 鼻+ l o ) + o ( a t ) ，0 f k ， 令，_ 0 即得 只= 一1 只一lo ) 一( + 。) 鼻( r ) + j u f + 1 只+ l ( ，) + d ( f ) ，0 o ，o ， ( 2 7 ) 且与初始条件无关。 现在来看方程组( 2 1 ) ，( 2 2 ) ，( 2 3 ) ，由于r 专o o 时右端极限存在，因而左 端极限也存在，即 l i m p , ( r ) ，i 0 存在，因而必有 l i m p ( ，) = 0 ，i 0 t - - - o o 事实上，若有某i 使 ( 2 8 ) 7 第二章预备知识 硕士学位论文 l i m 只( f ) = c ，0 ， 不妨假设q 0 ( c f a ， 0 ，则存在一个f o ，当f 时只( f ) q ，故 l i m p , ( f ) = 1 i m p , ( r o ) + i ( u ) a u 】 i - - - o ol - - o oo 只( ，o ) + 烛卜d u = 只( ，o ) + l i m 口jo t o ) = 0 0 此与只( ，) 1 矛盾，因而必有( 2 8 ) 式 于是在( 2 1 ) ，( 2 2 ) 与( 2 3 ) 中令，一0 0 ，由( 2 7 ) ，( 2 8 ) 即得 1 0 = 以一l p 置一l 一r p 置 0 = 五一l p h 一( + a ，) p i + 川p m ，0 i t o p o + l p l ( 当可数状态时，只需将第一式划去，并将第二式中的k 改成0 0 即可) 由此得 1 名r l p r l 一足p r = 0 ， 以p f 一j + l p = 一i p f _ l 一f p f ，0 ， 称 x ( ，) ，j ( ，) 是一个拟生灭过程，如果其生成元可写成下列分块三对角形式 q = 么og b i a c ba c b彳 ( 2 1 3 ) 其中所有子块都是m 阶方阵，满足 ( 么o + c o 弦= ( b i + a + c ) e = ( 么+ b + c ) e = 0 4 和彳有负的对角元素和非负的非对角元素，其余子块均是非负阵，称状态集 ( 后，1 ) ，( 七，2 ) ，( 七，聊) 为水平k 。若过程是正常返的，以( x ，) 表示过程忸( f ) ，( f ) 的极限变量，并记 万材= ! i m ，尸似o ) = 后，j ( t ) = = p x = j | ，j = j ) ， 。 f 其中k 0 ，1 j m 为适应q 的分块形式，将稳态概率按水平写成分段形式 尹 死= ( ，) ，k 0 我们直接引用下列结果，证明见文献 3 5 第三章。 定理2 2 1 1 2 1 过程q 正常返，当且仅当矩阵方程 r 2b + r a + c ：0 9 第二章预备知识 硕士学位论文 的最小非负解r 的谱半径s e ( r ) 1 ，并且线性齐次方程组 万o ( 彳o + r b l ) = 0 有正解。 定理2 2 2 t 1 2 1 若矩阵g = a + b + c 不可约，率阵r 满足s p ( r ) 7 + c e ， 这里万是生成元g 的平稳概率向量，满足 万g = o 万e = 1 定理2 2 3 1 2 1 当过程q 正常返时，稳态概率向量可用矩阵几何解表为 以= 7 1 o r 。，k = 0 ，l ， 其中万。是方程组7 1 。( 彳。+ r b i ) = 0 的解，满足正则化条件 7 o ( j r ) e = 1 。 2 3p h 分布的相关定义 2 3 1 1 5 连续型朋分布 考虑状态集 1 ，2 ，m ，m + l 上的m a r k o v 过程，状态1 ，m 都是非常返的，状态 m + 1 是吸收的过程的无穷小生成元是 q = k ：l 朋阶方阵丁= ( 乃) 满足瓦 0 ，休假结束后，若服务 台仍没有顾客，则可以开始另一个休假。 服务阻塞：由于每级服务台服务容量有限，当第f 级的队长小于k ，时，第 f 1 级服务台处于可工作状态，一旦第f 1 级服务完的顾客进入第f 级使它 的队长达到k ，时，第f 1 级服务台马上停止工作，直到f 级服务完一个顾 客使队长降为k ，1 时，第f 1 级服务台又恢复工作。 所有顾客到达的时间间隔，各级服务台的服务时间，休假时间，都彼此相 互独立。 顾客在第级服务台服务完成以后，以概率g 离开系统，以概率p ，反馈 到第f 级系统，f = 1 ，；若第f 级队长等于k ，则离开系统，江1 ，。 其中 1 3 ) ) ) ) ) ) ) ) 1 2 3 4 5 6 7 8 ( ( ( ( ( ( ( ( 第三章n 级串联休假反馈开排队系统模型 硕士学位论文 j q + p f = 1 ；q 0 ；p j o ，i = 1 ，n 。 i = 1 3 2 状态描述 设厶( f ) 表示f 时刻系统中第鸸受服务台的队长( 包括正在接受服务台服务的 顾客) ，江l ，以( f ) 定义如下 f o ，时刻f ，胡艮务台处于服务状态 1 v7 1 1 ，时刻，朗艮务台处于休假状态。 则由它们构成的随机过程 三( f ) ，( f ) ，厶o ) ，以o ) ，厶o ) ，以( f ) ，f o 是一个2 维的m a r k o v 随机过程，其状态空间为 峨= ( k ，歹，l ， ) ，f = o ，k 。，f _ 1 ，n ，j ，= o ，1 ) ) ， 各状态按字典序排列，“共有h ( 2 k 。+ 1 ) 个状态。为方便于下面应用分析，给 出状态空间的递推表达形式如下： e 表示系统仅有前i 级服务台时的状态空间，1 f n e = ( 0 ，1 ，彩h ) ，( 1 ，0 ，c o f - 1 ) ，( 1 ，l ，彩) ，( k ，0 ，c 0 i 一1 ) ，( k l ，1 ，国“) ，缈h e 1 ) 2 f n 置= ( o ，1 ) ，( 1 ，o ) ，( 1 ，1 ) ，( k ，o ) ，( k ，1 ) 3 3 状态空间的转移密度矩阵 此系统是一个2 维的m a r k o v 随机过程。相应于上面的状态空间的表示方 法可以得出：对于f 级串联排队系统而言，f 1 级串联排队系统的输出过程即是 其第f 级服务台的输入过程。该高维马氏过程的转移矩阵q 可由以下递推方式给 出： q = 1 4 只：。圆( 01 ) q 。( 矧 p 2 1 q 、l，n叫吖 叭v 0 0，以0 0 ( 0 2 o o e 匕 一、i叭叫叫 们u 0 0 1 o 。 丑0 ，l 2 q ( p 2 一 一 年 雌 、，_、 丑0 ， 磋p t 硕士学位论文 n 级串联开排队网络系统分析 2 is 其中 q ，：! 。f ，一( 1 一只) o 、1 i l l i i l l i 虿训- 咒) 。p 叩j 丑o 、1 2 i n 尸f 一j q f 为兀( 2 k + 1 ) 阶矩阵 e l = ql qi oi o ( e 一。与一。同阶，两矩阵对应的分块方式相同) q 表示仅有f 级服务台时的转移矩阵 只为只有鸸受服务台且没有反馈时的转移矩阵 只= 只3 = h h 0 1 日i o 么c b a c 2 f ba c b h 1 1 h h o l 彳c 彳c 么c 日l l f ，p 为兀( 2 k j + 1 ) 阶矩阵 j f l 只2 = 只一只3 其中 h 0 0 = ! l h o 。= ! l 圆( 01 ) h l o = i 。( 2 0 ) ( ，于一。的阶数相同) 1 5 第三章n 级串联休假反馈开排队系统模型 硕上学位论文 砜嘏蝉。( z 一2 。) 么= ：lo f f c = p , 2 lo f b ：i 圆h lo e l = 其中： 丑= 一 o 、i p tp i ) 1 0 、 i o 1 j 0， 0 三 c ，于p 一。的阶数相同， q1 0 ( e 一。与一。同阶，两矩阵对应的分块方式相同) ( 弋公袖也：川)( 吉三) ( ( 公钔也o + m 三) ( ( j 一2 。) e 为2 k l + 1 阶矩阵 只3 = 一九( 0 厶) ( 一公钔一。0 砧) e 2 = 墨一e 3 1 6 o 、1 l l一1 o、 o 一，一 硕士学位论文 n 级串联开排队网络系统分析 甲l = 一= g ( 0p 1 ) q ip l i q in l ( g + p 1 ) ， o ) 0 ) 。 ( q j ，- i + p j i ，p 口 2 f n 一1 一与只同阶，两矩阵对应分块矩阵同阶，2 f n - 1 3 4 平稳队长分布及其算法 本节给出t 模型的稳态概率解； 引理1 【3 5 1 设拧阶方阵a 的特征值和相应的特征向量分别为五，参，f _ l ，z ，m 阶方 阵b 的特征值和特征向量分别是，7 7 ，j = 1 ，m ，则 1 ) a o b 的特征值和特征向量分别为丑，缶o q j ； 2 ) 彳ob 的特征值和特征向量分别为五+ ，毒 巧，。 引理2 【”1a ，b 均可逆，则么o b ，a b 也都可逆。 性质- 羁。卅。堪川。( ：三 可逆 证明：p t 3 1 + p i _ 2 。忍一。为上三角阵，且对角占优，所以可逆而( ：三 可逆，引理可 得证 性质2 州扣( ：一珈道 3 4 1 平稳队长分布及其算法 设y = ( k ，e ，砭，乓。) ，z r m u - i , 待币i ( = 兀( 2 墨+ 1 ) ) 是级串联休假 排队系统的状态稳态概率解，则r = k r ，1 i k ，而k 可由下列线性非齐 次方程细 1 7 1 0 ：1 、厂 一， p o ， d a d 叭v 0 1 o 九v厂- p p ， d p 以 第三章n 级串联休假反馈开排队系统模型 硕士学位论文 阱u ! r = l f m u 哦。脚州。 u ：= 露一。c 。，+ r 。c q + 焉一，圆( 三： ，+ 篙1 r ，c 一。( 台3 ) + q + 焉一。圆(