（概率论与数理统计专业论文）mxmc→mr1k排队系统概率分析.pdf

顺l j 沦义m “) m c m o ) i k 州1 j 人系统概率分析 摘要 本文一i - 婴研究彳限弈l j l - i l z j 两级小联排队系统m u ) i m i c 专i m p ) 1 1 1k ，对于串联 f i z j - j l l ! 队模型u 经绀剑i l l ：多学析的研究，并儿状得了不少成果，但是对于成批到达、成 批服务的小f f ) - j - i i ! l a 系统f 内研究并不多见。本文用矩阵几何解方法得到系统模型的状念 转移概率知i 阵、稳态队长及典算法。通过嵌入马尔科夫链方法求出：i 缴服务系统受 m 时问及典分斫j 、受6 l 【概率、“笫一类成批等待的时问和“第二类成批等待的时问” 及乓他们的分斫j 、逗刚l i , j l , j 的分斫i 、以及i 级服务系统与系统的忙期分布。 关键词：爿j 联- t ：i i ! i a成批到达成批服务矩阵几何解 a b s t r a c t 硕士论文 a b s t r a c t t h e t w o s t a g e t a n d e m q u e u e i n gs y s t e mm ( 。) m c 一m ( 7 ) 1 ki sm a i n l y s t u d i e di nt h i sp a p e r m a n ys c h o l a r sr e s e a r c h e dt h et a n d e mq u e u e i n gs y s t e m ，a n dr e c e i v e d al o to f c o n s e q u e n c e s ，b u tf o rt h ed i s c u s s i o no ft h ec u s t o m e r sa r r i v i n gi nb a t c ha n ds e r v e d i nb a t c hi sl i t t l e t h es u f f i c i e n t n e c e s s a r yc o n d i t i o n sf o rt h es y s t e m s t a b i l i t yw e r e p r e s e n t e db ym e a n so 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 ，a n dt h ed i s t r i b u t i o n o fs t a t i o n a r yq u e u el e n g t ha n di t sa l g o r i t h mw e r eo b t a i n e d a tt h es a m et i m e ，t h ep a p e r i n t r o d u c e st h ed e f i n i t i o n so ft h es t a g e is e r v i c eb l o c k e dt i m e ，t h ef i r s t c l a s sa n dt h e s e c o n d - c l a s sb a t c ho fw a i t i n gt i m e s ，t h eb a t c ho fs o j o u r nt i m e ，a n do b t a i nt h e i r d i s t r i b u t i o n sr e s p e c t i v e l y w ec a na l s og e tb u s yt i m ed i s t r i b u t i o n so ft h es t a g e ia n dt h e w h o l es y s t e m k e yw o r d s ：t a n d e mq u e u e i n g ，a r r i v i n gi nb a t c h ，s e r v e di nb a t c h ，m a t r t i x g e m e t r i c s o l u t i o n s i i 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本学 位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或公布 过的研究成果，也不包含我为获得任何教育机构的学位或学历而使用过的 材料。与我一同工作的同事对本学位论文做出的贡献均已在论文中作了明 确的说明。 研究生签名：4 刨掣 、1 知洚石月矽日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或上 网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并授权 其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密论文， 按保密的有关规定和程序处理。 研究生签名：乏翌望兰訇 q 年6 旯哆b 倾i j 论义 m “) m c m i i k 州| j 人系统概；卒，分析 1 引言 奉章我们将简，n 的来介绍排队论的发展历程和f | j 联排队例络系统，成批到达 和成批j j 技务的：f i i i l s a 系统的研究内密、背景和现状，同时指小本文的丛本结构和i 主 要内容。 1 1 排队论及应用 1 1 1 排队论发展简介 排队v e l 2 p = l r - - 队理论，它是运筹学的一个重要方向，它主要的是研究由于顾客 的到达和离丌以及服务台的工作和休假，而引起的排队队伍的积累和消散问题。 二十世纪初期，一位丹麦的数学家、电气工程师爱尔朗( a k e r l a n g ) 用概率的 方法对f t i 话通话问题做了深入的研究，从而开创了这门新学科，并且建立了包括 先到先j j i i 务等许多丛本规则。在3 0 年代中期，当费勒( w f e l l e r ) 引进了生灭 过私! 时，排队沦才被数学界承认为- 1 3 重要的学科。在二战期间和以后，排队论 越米越多的被人研究，在运筹学这个新领域中成为一个必不可少的重要内容。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 ) 采用的表示排队系统的方法，一个排队过程通常采用符 号m n p x y 其中m 代表顾客到达间隔时间分布的类型，n 代表服务台服务时间 分布的类型，p 表示服务台的台数，x 表示队伍的容量，y 表示排队规则。如m m c 表示顾客按泊松分布到达，服务时间服从负指数分布、有c 个服务台、无限等待 空间的排队系统。 分布 排队规则 符号解释 符号l 解释 1 引言 硕士论文 m 指数分布 f c f s先来先服务 e n e r l a n g 分布 l c f s 后来先服务 pp a r e t o 分布r o s 随机服务 p h p h 分布 p r 优先权服务 g 一般分布 g 1 ) 一般规律 表1 1 1 排队常用记号 一个排队系统要从两方面考虑，即服务机构和顾客的利益来考虑，顾客希望 的等待时间越短越好，那就需要服务机构的服务台越多越好，而服务机构要想获 得很高的利益就必须限制服务台的个数。综合考虑排队的几个指标：队长、等待 时间、和服务台的忙期，成为排队论的主要研究内容。 1 1 2 排队论的应用 随着研究的深入，排队理论日益得到广泛应用。人们发现通信系统、网络设 计、计算机存储、交通系统、物流调度等各种现象都可以通过排队模型来描述， 同时应用相应排队理论的研究成果，可以指导各种策略设计，给国民经济的发展 带来巨大的贡献。 比如银行的排队问题：“我算过一笔账，工商银行现在每天平均办理4 3 0 0 万笔业务，电子银行的代率( 电子银行代替人工完成交易的比率) 为3 0 ，扣除 这1 3 0 0 万笔经由电子银行办理的业务，以1 7 0 0 0 个网点计算，一线柜员每人每 天需办理2 0 0 笔业务。以8 小时工作日计，平均每笔的办理速度是2 分4 0 秒不 到。从工作效率和处理速度上看，确实值得肯定。工商银行办公室新闻处处长 谢泰峰告诉记者：“对银行排队问题，工商银行上至行长下到基层柜员，没有一 个不在殚精竭虑，不在冥思苦想 。不断梳理和改造服务流程，也有利于提高服 务效率，缓解排长队严重现象。据了解，不少银行目前正在加快现有网点综合化 建设进程，使对公业务和个人业务能在同一个电子平台进行，预计网点综合化后 将使工作效率提高三分之二。银行排队现象：是个管理问题。排队，事实上就是 等待。对于到窗口办事的客户来说，等待，恐怕是最让人难以忍受的事了。在我 国的大城市，在银行营业网点排队超过一个小时以上几乎成为家常便饭，对大多 数客户而言，排队是他们别无选择的，只能忍受。 有研究企业管理和行为科学的专家曾经对客户在银行长久排队后的心理承 受力进行调查，研究结果的数据表明，在银行排队以3 分钟和3 分钟以后为界， 客户对排队时间和实际排队时间的感知有很大的差距。通常情况下，排队等待2 分钟后，客户感觉比较接近实际，感觉就是等了2 分钟。但等待5 分钟后，客户 会感觉就像是等了1 0 分钟。这就是说，5 分钟的排队时间是满意与否的临界点。 倾j ：论义 m “m c m ( r l i k 州队系统概率分析 美罔一家分门研究顾客行为的公i 对惜钊对积i 饿行嘲点等候的鬻，1 进行凋研， = i e i i l9 0 的受访杆表示，他们能够接受的蜮长等待时问足5 分钟、能够接受的最 长交易时| 、i j j 足3 5 分钟、) 以能够接受的队伍长度最多为5 人。4 i 少银行为了解决 这个5 分钟的心理临界点，采取了叫号机j j 陵务措施，hf 内就足为改善客户的满意 度进行努力。显然，排队问题，真的不是一个简单的服务问题。专家说，这是一 个管理问题。表面j ：n 勺排队问题背后，实际上隐藏着银行改善管理的”大文章”。 在西方发达国家，也曾经历过银行排队的难题。国外那些老牌的商业银行，早就 通过引入技术和管理创新来解决这个难题，比如通过调查社区人员流量，合理设 计网点布局，来减少客户排队等待时间。 1 2 排队论的经典研究方法 自从排队论这门学科形成以来，逐渐出现了许多新的研究方向和研究方法。 大景的科研工作辑在此领域取得了丰硕的成果。排队论方面的专家田乃硕等将矩 阼解析法引入到g i m 1 型的休假排队模型，并研究了部分服务台同步的休假排 队理论模型，极大私度上丰富了排队模型的理论；经典的排队理论主要是建立在 模型满足马尔科夫盹的占 i j j 卜，研究平稳状态下系统的等待队长、等待时问等统 计特征量。一般来说，经 j i 丰- i i 队理论的求解方法主要有以下几种： 一、1 茨入马氏链法( e m b e d d e dm a r k o vc h a i n ) ，现在已经被发展至马氏更新法。 这种方法的关键是通过寻找过程的马氏点或再生点，运用马氏链的特性或建立更 新方程来得到排队系统的统计特征量。由于该方法较多地用到排队模型的概率意 义解释，从而需要较多的概率论知识作为基础，并且各指标的求解比较复杂。 二、补充变量法。该方法通过增加变量，构造向量马氏过程( v m p ) 从而建立密 度演化方程，并求解各种统计特征量。该方法将随机性的、不确定的排队论问题 转化为确定性的方程来求解，极大地降低了求解过程的复杂程度，但对方程求解 的技巧要求较高且通常仅可得到解的拉普拉斯变换，而且关注的只是过程的状态 概率而非转移概率。具体方法精髓可参考徐光辉 1 1 三、n n e u t s 教授提出的拟生灭过程理论，他将生灭过程的方法加以推广和引申， 逐渐形成了一套可以处理一系列相关于p h 、m a p ( 马氏到达) 及b m a p ( 批马氏到达) 分布所构成的排队模型。尤其值得提出的是拟生灭过程理论已形成了完整的算法 程序，为排队论模型的研究提供了较好的实证结果。其余的还有国内侯振挺教授 提出的马氏骨架方法 2 1 、国外b r i l l 教授提出的水平穿越方法 5 1 等。 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 个编号为1 ，2 ，m 的服务点所 组成，其中第f 个服务点包括朋，个服从独立同分布的指数分布服务时间的服务 台，第f 个服务点的外部顾客输入服从参数为无的泊松流，各服务点的外部顾客 输入与各服务时间为相互独立。顾客在第f 个服务点接受完服务后立即以概率p ；， 沿路径转移到第j 个服务点进行排队等待，而以概率g ，= 1 一二p ，离开该系 统，对于j a c k s o n 开网络，容易证明它具有乘积型解，也即网络的平稳分布等于 各服务点平稳分布的乘积。如果在指数开网络中令所有z = 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 ( 1 9 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 输出这种性质，记为 mjm ，证明了服务点具有m m 性质的网络是具有乘积型解的，同时该网 络也具备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 证明了在非指数服务的情形，具 有乘积型解的网络的排队规则必须是立刻服务规则，即顾客在到达时刻必须立刻 开始接受服务。因此，像优先权服务、先来先服务等非立刻服务规则不能产生乘 积型解。n o e t z e t ( 1 9 7 9 ) 4 3 提出了一种更为一般的排队规贝j j 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 则考虑了包括多种路径方式，多种排队规则在内的多类顾客， 一般服务分布的网络，利用可逆性得出了一种乘积型解。 最近，s e r f o z o ( 1 9 8 9 ) 4 5 研究了路径与服务速度依赖于系统顾客等待长度 的m a r k o v 网络，它把通常所考虑的各顾客选择路径相互独立、各服务点的服务相 4 倾i ：论义 m “) m c m ( 7 j k 栅队系统概率分析 = f 独立f j 网络包含和! 内作为特例，而儿现和：n 勺模型更易。卜姚述：并行处理，避免 拥挤而改变路径、容呲| - i - 行i 驳的转移掰i 塞、和增加或绗f 减处列! 速度以适应后而路径 的拥挤等现缘。他j i 进了批写符服务点顾祥数的一般网络过程，导出了它的平稳 概率分和，此分f l i - j ：有向：餍函数的乘积型解。v a nd i j k & r a m a s e w i c z ( 1 9 9 1 ) 4 6 考虑了具有般服务需求的网络，其路径依赖j ：顾客在下圳! i 务点所需的服务时 间，求得了非标准的乘积型解。 服务点容量有限的网络一般都没有乘积型解，除非路径可逆( 见k e l l y ( 1 9 7 9 ) 4 7 ) ，或者遇到服务点的容量达到饱和时顾客会越过此服务点，如同此时的服 务速度等于0 0 对后面这种情形，以前文献中的证明都是直观的，而v a n d i j k ( 1 9 8 8 ) 3 6 则给出了简单、严格的证明。 对于有阻塞的非指数网络，v a n di j k ( 1 9 9 1 ) 4 8 研究了顾客遇到阻塞时服 务“重复”或“停止 两利，类型。在一定条件下，两种类型被证明是等价的，而 且可导出乘积型解。 串联排队网络系统在海港、航空港运输、计算机通讯、交通控制、存储系统、 柔性制造系统、生产箭耻、生产流程等领域中的应用非常广泛，特别是有限容量 的排队系统网络。对于有限容适的串联排队网络系统，人们研究得较多的是用逼 近的方法，求系统指标的近似数值解。如：a l t i o k 2 3 ( 1 9 8 9 ) ， 1 3 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 1 专m i k ，用复分析的方法给 出了系统平稳的充要条件及平稳概率分布；l a t o u c h e n e u t s ( 1 9 8 0 ) 用矩阵分析 理沦给出了系统，m m r 专m c k o h 平稳队长分布。贾波、周家良 8 在p h 型 级串联反馈开排队网络系统分析中研究了朋型级串联反馈开排队网络系 统，采用递推方式给出了马尔可夫过程的转移矩阵，并利用矩阵分析方法进行求 解，得到了该系统的稳态解和相应的忙期长度；周家良 1 7 基于朋型级串联 反馈开排队网络系统分析中对队长和忙期的研究方法，在册朋1 n 反馈排 队系统的逗留时间的文章中，接着给出了逗留时间稳态分布。周家良 3 ( 1 9 9 8 1 ) 在上述排队模型的基础上又增加了闭锁规则，研究了有阻塞的多级串联排队系 统，得到了该系统的队长、忙期长度、逗留时间等分布的简明精确显式解；周家 良、贾波 1 3 研究了具有n 个有限容量服务节点的j a c k s o n 网络，运用马尔可夫过 程的状态空间及q 矩阵的递推表示方法，富有技巧性的给出了相应的稳态显式精 确解。 1 4 成批到达与成批服务的排队系统的探讨 l 引言硕：l 二论文 成批到达、服务排队模型常用于港口、铁路等装运系统此时，以成批到达的 货物为顾客，大型装载车辆为服务台。为了降低成本，每次需尽量满足车辆的装 载能力，当待运的货物太少时，大车或或取消此次运输，等待新的货物到来，运 输过程延迟或中断后重新启动，需增加设备的调配、准备时间。以此类实际问题 为背景。 对于批量到达的排队系统，在排队论基础上就有讨论，在这本书上，共讨论 了这样几种批到达的排队模型：彰m 1 、m f g 1 、g 1 ，用嵌入马尔 科夫过程得到了他们的平稳分布，队长分布以及等待时间分布等：苏时光、陈薇 1 4 研究了m 工m c 专p h l l k 的有限容量两级串联开排队系统，并给出了 排队平稳条件以及用矩阵迭代法得到了平稳队长分布和受阻概率分布。 对于批量服务系统，许多学者做了研究。l e o n a r dk l e i n r o c k 5 2 3 给出了一种特 11 殊的批量服务系统m m 置1 的平稳概率分布：= ( 1 一二) ( 二) ，其中z 0 满足 z oz o 允r 一( 旯+ ) z x + = 0 以及 2 0 | 1 的解。徐光辉也对m m k 1 坐了探讨，给出 了类似的结果；j m e d h i c s 5 3 给出了这类服务系统概率母函数的形式，但未 能进一步探讨母函数中未知数的求法。j w c o h e n e t 在其经典著作t h es i n g l e s e r v e rq u e u e ) ) 中给出批量服务系统各项指标的精确数学表达形式， j w c o h e n 5 4 在求解中使用了大量艰涩难懂的数学工具，因此所得结果也仅 有理论上的意义。在2 0 0 0 年周志中、周亚平给出了一类批量服务的排队系统求解， 这是一个比较特殊的批量服务排队系统一公交系统的稳态概率分布的求解过程， 并在此基，础上给出这类服务系统平均队长的算法。 徐光辉、袁学明 7 更为一般地推广了有限容量的成批到达成批服务的两级 串联排队网络系统模型，用矩阵分析理论对系统m ( 。) m c 寸跗( 7 ) 1 k 进行 了研究，得到了其状态过程的q 一矩阵，给出了系统平稳的充要条件、平稳队长分 布及其算法等系统的平稳性态指标。 1 5 本文的主要研究内容和结构 本文是在m m 1 哼m m 1 的基础上进行改进，将顾客的到达改为成批 到达，并且i 及服务系统有c 个服务台，i i 级服务系统是成批服务，用矩阵几何 解方法得到系统模型的状态转移概率q 一矩阵、稳态队长及其算法，通过嵌入马 尔科夫链方法求出：i 级服务系统受阻时间其分布及受阻概率、“第一类成批等 待时间”和“第二类成批等待的时间 及其他们的分布、逗留时间的分布、以及 6 颂j ：论文m “) m c m “) i l k 排队系统概牢分析 l 级服务系统与i i 级服务系统的柏：期分斫j 。 小义的结构： 第一章足弓i 苦。主要介绍论文的选题背乌及研究现状，以及本文的研究内容和结 构。 第二章是预备知识。只要介绍生灭过程、拟生灭过程、矩阼解析法、概率守恒原 理等。 第三章是m ( 。i mi coi m ( 7 li i l k 系统分析，主要是介绍状念转移的q 矩阵、稳 态队长及其算法、i 级服务系统受阻时间其分布及受阻概率、“第一类成批等待 时间 和“第二类成批等待的时间 及其他们的分布、逗留时问的分布、以及i 级服务系统与系统的忙期分布。 第四章是总结与展望 7 2 预备结论 硕士论文 2 预备结论 2 1p h 分布的相关定义 2 1 1 连续型朋分布 我们考虑系统状态集 1 ，2 ，m ，m + l 上的m a r k o v 过程，状态l ，l 都是非 常返的，状态所+ 1 是吸收态状态过程的无穷小生成元是 q = l ：卅 肌阶方阵丁= ( 乃) 满足毛 o ，乃o ，j j f t o 是非负列向量， t o = ( 互o ，露) 。，t e + t o = o ，过程的初始概率向量是 ( 口，+ 1 ) ，口= ( ，o c m ) ，口口+ + l = 1 引理l 状态过程o 以初始概率向量 ，+ 。) 出发直到吸收于状态m + l 为止的 时间有分布函数 f ( x ) = 1 - a e x p ( t x ) e ，x 0 ( 2 1 ) 定义1 f o ，) 上的概率分布，( ) 称为朋分布，当且仅当它是一个有 m a r k o v 过程的吸收时间分布，有分布函数( 2 1 ) ，位，丁) 称为它的m 阶表示 2 1 2 离散型阳分布 对于离散型p h 分布，与连续时间m a r k o v 过程相似，考虑状态集 1 , 2 ，m ，m + l 上的离散时间m a r k o v 链仍设m + l 是吸收状态转移概率矩阵为 肚h 0 1 l， ii 瓦。是随机子阵，元素巧0 , 9 精t e e 列向量? o = ( j t ) e ，j t 是非奇异的 定义2 非负整值上的离散分布 见 称为跗分布，当且仅当它是上述m a r k o v 链 达到吸收状态时的转移步数的分布。 若m a r k o v 链的初始概率向量是 ，+ 。) ，则 p o2a ，肼+ 1 ， 仇= a t 一1 t o , k 1 ，t ) 称为它的m 阶的阳表示。 2 2 生灭过程 2 2 1 生灭过程的定义 埘 i j 沦艾 m ( “) m c m ( ) il k 州：队系统概水分析 改m a r k o v 链x = ( ，) ，o ，状态空1 1 i js = o ，1 ，2 ，) ，特转移概率矩阵 p q ) = ( 岛( ，) ) 满足： 当h 允分d x l l i - ， 只，+ l ( 五) = 五 + d ( ) ， 届，1 ( 办) = p i h + o ( h ) ， 只，( 庇) = 1 一( 丑+ “) 矗+ d ( 厅) ， n ( 办) = d ( 办) ， i 一，j 2 2 丑0 ，i 0 ， “0 ，i 1 ， 觞= o ，i 0 f 0 称x 为生灭过程 2 2 2 生灭过程的微分方程组 设只( f ) 为系统在时刻f 处于状态f 的概率，即 只( f ) = 以( f ) = f ) 系统在时刻f + f 处于f ( 有限状态时0 i k ：可数状态时0 i ) 这一事件 可以在下列互斥情形下发生： ( 1 ) 当系统在时刻f 处于状态i ，而在时刻o + & ) 内没有变化。其概率为 只( t ) ( 1 一五出- a ，a t ) + o ( m ) ( 2 ) 当系统在时刻f 处于状态f 一1 ，而在( f + a t ) 内由f 一1 转移到i ，其概率 为 e l ( f ) 丑一i a t + d ( f ) ( 3 ) 当系统在时刻f 处于状态i + 1 ，而在o + 出) 内由i + 1 转移到i ，其概率 为 + l ( t ) 1 t + la t + o ( a t ) ； ( 4 ) 当系统在( ，+ a t ) 内发生两次或两次以上转移，其概率为o ( a t ) 。 故由全概率定理，在有限状态时， 只o + a t ) = 只 ) ( 1 一乃f 一，a t ) + 只一l o ) 丑一l a t + 气l ( f ) f + l a t + o ( m ) ，0 i k ， 移项后，两端都除以出得 p j ( t + a _ t ) _ - p 一，( t ) ： 一1 只一lo ) 一( + ，) 只( f ) 忑_ 一= 一l 一l u j l + ，) u j + m e + l ) + o ( a t ) ，0 f k ， 令岔一0 即得 只。= 以一1 只一l ( r ) 一( 乃+ f ) o ) + t f + l + l ( f ) + o ( a t ) ，0 f 0 ( 2 7 ) 存在，且与初始条件无关。 2 3 矩阵解析法与拟生灭过程 2 3 1 矩阵解析法 在这十多年来，n e u t s 研究的矩阵解析法得到空前的发展，他的两本专著 ( 1 9 8 1 ，1 9 8 9 ) 3 5 就是关于这一方法的理论基础和应用领域的代表作。这两本专 著分别讨论了拟生灭过程于m g 1 型马尔科夫过程的基本周期( 特别包括忙期 在内) ，以及它们的矩公式。以朋分布为基础，n e u t s 引进了g i m 1 型与 m g i 型两类m a r k o v 过程，使得原来在指数分布假定下才能分析的很多随机模 型推广到朋分布的情形。由于朋分布可以逼近任意非负随机变量的分布，从 而使一般分布假定下的随机模型能够得到易于计算的逼近。 2 3 2 拟生灭过程 拟生灭过程( q u a s ib i r t ha n dd e a t hp r o c e s s ) 是经典生灭过程( 王梓坤， 1 9 8 0 2 2 ) 从一维状态空间到多维状态空间的推广，是经典生灭过程的最新发展。 正如生灭过程的生成元具有三对角形式一样，拟生灭过程的生成元是分块的三对 1 0 f ! i i j 论义 m x ) l m i c m i 。) i k4 | | ：队系统概率分析 角甜i 阵。近二十年l 二成为分析复杂随机模型的亟安工具 ，：。- ，血1 2 一个二维胁砌v 过私! ( ，) j ( 讲，状念空i 、j i j 是 q = ( 后，歹) ，k 0 , i j ， ， 称口( 吐，( 班是一个拟生灭过程，如果其生成元可写成下列分块三对角形式 q = 玩t 1 民a i( 2 1 4 ) a 2a ia ol i 其中所有子块都是m 阶方阵，满足 ( a o + c o ) g = ( b l + a + c ) e = ( a + b + c ) e = 0 a 。和a 有负的对角元素和非负的非对角元素，其余子块均是非负阵，称状态集 ( 七，1 ) ，( 后，2 ) ，( j | ， ) 为水平k 。若过程是正常返的，以( x ，j ) 表示过程( r ) ，( 讲的极限变量，并记 = l i m e x ( t ) = 七，( f ) = = 尸似= 七，j = ， 其中k 0 ，1 j m 为适应q 的分块形式，将稳态概率按水平写成分段形式 巩2 ( 以，以：，) ，k 0 我们直接引j 玎下列结果， 设连续时f n j 马氏过程 令 q = f b 。l 1 研刚2 i 羔尺扣t b k 。妻尺扛- 反。l = l k = l 其中r 是方程罗x a i = 0 的最小非负解。 ，鼠1 分别是。面l - m ) x ( m 1 - m ) 、( 聊l - m ) x m 阶矩阵，b o 是m x ( m i m ) 阶矩阵， 反l 、以一l 均为m 阶方阵，且b 0 0 、b l l 、彳l 均为非奇异矩阵，聊l m ，k = 1 ，2 ，。 类似于n e u t s 3 5 ( 1 9 8 1 ) 关于离散时间马氏链的引理1 5 。1 和定理1 5 1 ，并采 用类似于定理1 7 1 的证明，我们有下面两个定理。 定理2 3 1 若印( r ) 1 ，贝l j m ，阶方阵研r 】为一生成子。 定理2 3 2 不可约马氏过程q 是正常返的充要条件为印( r ) 0 ，使得 也 ) l a 色； 磊4 4 ；历届历历； m o 加 m 踟耶励踟； 2 预备结论 硕士论文 ( r o ，彳1 ) b 【r 】= 0 此时q 有平稳向量( k ，x l ，x l r ，x l r 2 ，) ，且k e ( 埘r 册) + 置( i - r ) e m = 1 。 我们记e ，= ( 1 ，l ，1 ) r 为i 维列向量，f - 1 , 2 ， 令a = ya ，朋维行向量7 满足： n a = o ：茄。：1 ，显然向量万、矩阵r 均与马氏过程q 的边界条件有关，从而， 由n e u t s 3 5 ( 1 9 8 1 ) 的定理3 1 1 有： 定理2 3 3 拟生灭过程( q b d ) q = 若a = a o + 4 + 么2 不可约，则印( 固 1 ，的充要条件为z a o 口肿 鹏p 朋。 2 4m i m l l j m m 1 的讨论 假设随机服务系统是由两个串联的等待制服务台构成，顾客输入是参数为名 的泊松流，顾客到达后在i 级服务台接受服务，然后进入i i 级服务台等待接受服 务，在i i 级服务台服务完后顾客离开系统。两个服务台的服务时间分别是参数为 “，鸬的负指数分布，而且两个服务台的服务时间和到达时间间隔是相互独立的。 设随机服务系统在时刻t 的状态为n ( t ) = 似力，若此时i 级服务台前等待的 顾客数和正在被服务的顾客数之和为i ，i i 级服务台前等待的顾客数和正在被服 务的顾客数之和为j ，状态空间为 ( f ，) ，i ，j = o ，1 ，) ，令 p ( i ，f i t ) = p n ( t ) = ( f ，) ) 容易证明n ( t ) 为一马尔科夫过程，利用马尔科夫的极限定理，可以得到 l i m p ( i , j ；t ) = p g ) 是存在的，且与初始条件无关。 定理2 4 1 统计平衡下，两个等待空间为无限的串联排队系统i 级服务台 前等待的顾客数和正在被服务的顾客数之和为i ，i i 级服务台等待的顾客数和正 在被服务的顾客数之和为j 的平稳概率为 p ( i ，) = ( 1 一p 1 ) ( 1 一岛) 爿 其中序：三且辟 0 ，使得 x a = o ，石= 1 定理3 3 1系统m “) l m i c 专m 7 i i i k 的状态过程q 是正常返的充要条件为 万a e 刀4 e ， 其中p 为p 砌的略写， 证明：设 勾阶方阵r 为方程y 2 4 十m + 以= 0 的最小非负解， es p ( r ) l 时， 为一生成子 又矩阵 玩。1 骂。+ 鲍j 为不可约矩阵，矩阵月及4 均为非负矩阵，故研r 】为不可约的。因而存在正向 似忸 ，。l = 1 j 足 口 形 | 论义 m “) m c m “9 i k 排队系统概率分析 蜓jz i ( 饩，x ) ，使( x o ，x i ) 研尺】2 0 。由定理2 2 2 、定理2 2 3 即得证。 推论1系统肘( j m c 一m 7 i i l k 的状念过程是f 常返的充要条件是 p 0 满足万o b = o ，万o = 1 ，其中b = 研+ 毯+ 名， 则系统m ( 。m c 一m ( 7 ) i i l k 的状态过程q 是正常返的充要条件是： p y 万? 证明：由于彳= 4 + 4 + 4 ，将其代入我们得到 b p + j l p n i q 鼋。+ 名所一l 九p n 2 i q 2 p l l q a = 五 + + 耳“a p 。a p ： 鼋。耳。 名p 。 砭。耳。 2 p , i q 即+ 九p n l q 硅+ a 肌一l 九p iq oo 九p 2 i q 久p l l q 畔+ 九p n l q 九p i l 3 厶 a p n l 五p _ 2 九p n - 3 l q 硅。+ 见肌一l 2 p u 一2 2 p 一3 j 耳“+ 2 p 1 9 孵 h = 、，伍 e 中其 0 o o ；卧 一 一 一； 一 0 o 卧；oo肌趾；o詈趾跏；o 9 q q q硝蛄； q ； 铲 明 铲； ” 0 0 0 0 m m m 祥 驴 铲； 0 0 0 0 x x 吣峥；岫 3m ( x ) m c m “ i k 排队系统概率分析 硕士论文 其中 所以 ( 万。万o ，万o ) 彳= ( 口，口，口) 。 k 。 口= 刀。( 硝“+ 2 p + 鼋。+ 兄肌一l 厶+ 2 p 一2 + + 2 p l 厶) = 万o 厨+ 硅+ 2 ( p i + p 2 + + p ) 厶】 - n o ( 科+ 鼋。+ 名厶) = 万o b = o 所以( n o , 万o ，万o ) 彳= 0 、。i _ 。、，。， ， 从而亩协。，万。，力。) 为矩阵a 的左平稳概率向量，由定理1 有： q 正常返 营专( 万。，万。，刀。) 4 口 专( 矿，矿，万。) 鸣e ( 万o ，万o ，万o ) a o e ( 万o ，刀o ，万o ) 鸣e 营名城 c 朋矿 p 群 结论比较直观，我们知道在系统m ( 。m c 寸i m ( 7 1 k 中，去掉i i 级服务系统， 即考虑排队系统m ”m c ，由经典排队论知：p 1 即为排队系统m ( 。i m i c 平 稳的充要条件，从而对系统m 。) m c _ m l k ，平稳的充要条件为：p 小 于一个小于1 的常数，这是很自然的。 3 4 平稳队长分布及其算法 由第三节的定理3 3 1 或者定理3 3 2 ，：芷n - a o e 万4 p ，或p m ( 7 ) 1 k 平衡状态下，i 级服务系统的 忙期9 的l s t + ( s ) = r ( b p + 名一五y ( 护( s ) ) ) 证明：由于c 个服务台独立工作，每个服务台的服务时间相互独立且都服从 参数为“的负指数分布，所以当c 个服务台都进入工作时，这c 个服务台可以看 成服务时间为m i p 哆 的一个服务台，其中e 表示笫f 个服务台的服务时间，由 指数分布的性质知： 靶啦 e ) 一r ( 1 ，c , u 1 ) i s ，s 一 这样当c 个服务台都进入工作时，i 级服务系统m 7 m c 可以看成m p m 1 系统。 对于m ( 。m c 来说。忙期由两种不同的含义，第一种含义是：由一批( i 个) 顾客引出的忙期。它是指：系统本来处于闲期，从系统开始到达一批顾客时起一 直到系统中又没有顾客时止这段时间，用 表示其长。o 是m ( 一m c 系统的 颂i ：沦义 m “) l m i c m c 7 ) i k 排队系统概率分析 忙期，到达的i 个顾客分别记为4 ，4 ，4 。由于忙期与服务的顺序无关，所以 在讨论忙期时，有时依先来后服务的规则处理，l j i 】先为4 服务，然后为在服务a ， 期间到达的顾客( 这些顾客可以视为a 。的第一代“子女) 服务，然后为a ，的第 一代“子女”服务期问到达的顾客( 这些顾客可以视为a 的第二代“子女”) 服 务，如此等等，当a 。及其各代“子女 都服务完时，再为4 及其各代“子女” 服务，以此类推。由此又引出第二种忙期，它是指：从开始为一个顾客服务时起 一直到该顾客以及各代“子女都服务完时止这段时间，用0 表示其长。 用矿( j ) ， ( s ) 表示0 ， 的l s t ，有： = 岛 其中日，0 2 ，绣，相互独立且均与0 同分布，从而有 o 0 ) = x o o ) 】( 其中x ( z ) 为x 的p g f ) 又 0 = b + o l + 0 2 + + o ( 历， = u + o i + 2 + + ( u ) 其中 。， ：，o ，相互独立均与。同分布，u = 马，马，b 2 ，岛，相互独立均与 i = 1 b 同分布，( 功为在占中到达的批数所以有 口+ 0 ) = e 一卵) = e e 一。b + e l + e 2 + 。+ 。川j ，1 ) = f e - e p 一5 m l + 咿伯蒯) 咖 召 ，) = f p 一耐兰e 和叫肼q + 岛+ + 们1in ( t ) ：硒p p ) = 后 劫 曰 吩 = p 鼢叫吣+ e 2 + + 刚，警p 础掷叫 = p 驴 等p 确椰叫 = c 0 8 一e - 耐o ) 1 f d p b m i c 寸膨( ，l 五系统，我们定义从某批顾客到 达i 级服务系统开始，到该批第一个顾客接受服务这期间的时间为第一类成批等 待时间。 3 7 1 先到先服务规则的第一类成批等待时间 对于m