（概率论与数理统计专业论文）关于多类顾客排队系统的综述.pdf

摘要 摘要 本文是关于多类顾客排队系统近年来发展的综述近年来关于多类顾客排队系 统的发展大概是分为两大支流，其中条是经典的排队如泊松输入，指数、p h 或一 般服务对多服务台情形得到了非常好的结果在对模型的处理方法和求解的思路 方面有很大的突破，我们将在第一章做比较详细的介绍另一条是新型排队自从马 尔可夫到达过程( m a p ) 提出以来，对排队论产生了很大的影响，使得排队模型更加 丰富，也更加贴近实际，特别是由m a p 推广得到的m m a p ( m a r k o v i a na r r i v a lp r - - o c e s sw i t hm a r k e da r r i v a l 8 ) 极大地促进了多类顾客排队系统的发展，取得了非 常重大的成果同时对相关的理论也有所成果对于这类排队为区别于经典的排队 模型，我们称之为“新型排队”对于这类排队模型的处理方法基本上是用矩阵分析 方法和拉普拉斯变换我们将在第二章对这类排队进行介绍 关键词t 多类顾客，多服务台，单服务台，优先排队，带标记转移的马尔可夫 到达过程 i i 摘要 a b s t r a c t t h i sp a p e ri s s u r v e yo nt h em u l t i c l a s sq u e u e i n gs y s t e m s i nr e c e n ty e a r s t h ed e v e l o p m e n to fm u l t i c l a s sq u e u e i n gs y s t e m sc a nb ep r o b a b l yd i v i d e di n t ot w o t r i b u t a r i e s ，o n eo fw h i c hi st h ec l a s s i c mq u e u e i n gs y s t e m ss u c ha sp o i s s o ni n p u t ， e x p o n e n t i a l ，p ho rg e n e r a ls e r v i c e i nt h i sr e a l m ，t h em u l t i - s e r v e rs i t u a t i o nh a s b e e nd e v e l o p e dv e r yg o o dr e s u l t s t h e r ei sg r e a tb r e a k t h r o u g hb o t hi nt h et r e a t m e n t o nt h em o d e l sa n dt h ei d e a w ew i l lb ei nt h ef i r s tc h a p t e rt od om o r ed e t a i l e d b r i e f i n g a n o t h e ri s “n e wq u e u e i n gs y s t e m s ”s i n c et h e1 9 9 0 s ，m a pa r i s e d ，t h e q u e u e i n gt h e o r yh a sb e e ng r e a t l yi n f l u e n c e d ，a n dq u e u e i n gm o d e l sb e c o m em o r e e x t e n s i v ea n dm o r ec l o s e rt ot h er e a l p a r t i c u l a r l y ，m u l t i c l a s sq u e u i n gs y s t e m s g a i ng r e a ta n de x t e n s i v ed e v e l o p m e n t a st h eg e n e r m i z a t i o n so fm a p ，b m a p ， m m a p ，d m a pa n dm o r eg e n e r a l l yt h es mw i t hm a pq u e u e i n gs y s t e m sh a sb e e n e x t e n s i v e l ys t u d i e da n dg r e a tr e s u l t sh a sb e e ns z h i e v e d a tt h es a n l et i m e ，r e l e v a n t t h e o r i e sa l s oh a v eb e e nd e v e l o p e d b a s i c a l l ym a t r i xa n a l y s i sm e t h o d sa r eu s e dt o s t u d ys u c hq u e u e i n gs y s t e m s a tt h es a l l l et i m e ，t h em a t r i xm m l y s i sm e t h o dh a s b e e nd e v e l o p e d w ew i l li nt h es e c o n dc h a p t e rt or e v i e wt h e s e k e yw o r d s ：m u l t i c l a s s ，m u l t i s e r v e r ，s i n g l e - s e r v e r ，p r i o r i t y , m m a p 首都师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工 作所取得的成果除文中已经注明引用的内容外，本论文不含任何其他个人或集体 已经发表或撰写过的作品成果对本文的研究做出重要贡献的个人和集体，均已在 文中以明确方式标明本人完全意识到本声明的法律结果由本人承担 学位论文作者签名t 首都师范大学学位论文授权使用声明 本人完全了解首都师范大学有关保留、使用学位论文的规定，学校有权保留学 位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版有权将学位论 文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅有权将学位论文 的内容编入有关数据库进行检索有权将学位论文的标题和摘要汇编出版保密的 学位论文在解密后适用本规定 学位论文作者签名。 b 承 嗍瓣q j 日 第一章多类顾客经典排队系统的发展 多类顾客排队系统，就是指到达排队系统的顾客有多个类型，不同类别的顾客 的到达时间以及服务时间分别服从不同的分布的排队系统经典的排队如泊松输 入，指数，p h 或一般服务由于一般我们都是通过构造马氏链( 或马氏过程) 来分 析排队系统在平稳状态下的各个性能指标，对于多类顾客排队系统要构造马氏链， 由于必须包含每一类顾客的信息，从而，其状态空间要比一类顾客排队系统的要复 杂得多! 这也是为什么多类顾客排队系统的研究没有经典的一类顾客排队进展的快 的主要原因。进几年来关于经典的多类顾客排队系统的研究取得了一些突破，主要 体现在以下三个方面。 ( 1 ) 顾客类型的数量上； ( 2 ) 服务台的个数； ( 3 ) 服务时间分布 当然也存在一些局限：到目前为止，研究经典的多类顾客排队都还是局限在泊松到 达 2 第一章多类顾客经典排队系统的发展 1 1优先排队 多类顾客经典的排队系统中人们最熟悉就是优先排队了在早期的排队论中， 人们就得到了非玫慕峁在c o x 和s m i t h ( 1 9 6 1 ) 的关于排队论专著中有这方面早 期工作的概要j a i s w a l 对6 0 年代后期的一些著名结果做了总结那时的大部分 结果都是针对于具有固定优先权的单服务台排队而言的，系统实施抢先和非抢先规 则优先权的排队系统有很非常广泛的应用自从上个世纪九十年代，已经对一个 服务台m g 1 类型的优先排队系统有了很好的结果但也仅限于单服务台情形 九十年代末，人们开始热衷于研究多个服务台的优先排队，由于不同类型的顾客可 能同时接受服务，使得问题变得非常的复杂分析多个服务台的优先排队系统的文 章很多，但大大多数文章都是针对m m k 优先系统，主要方法有以下三种： ( 1 ) 逼近，聚集或截断； ( 2 ) 矩阵分析法；( 3 ) 生成函数方法 基本上所有用来分析u u 后两个优先级排队系统的文章都用了马氏链，这样 的马氏链有两维是无穷的( 每维表示每个优先级的顾客数) ，为了克服这一点，研 究人员们用各种方法简化这个马氏链 k a o 和n a r a y a n a n 通过限制高优先级的 顾客数【3 3 】或低优先级的顾客数【3 2 】来截断原马氏链n i s h i d a 把状态合并得到 一个粗略的逼近【5 2 k a p a d i a ，k a z m i 和m i t c h e l l 给出一个有限排队系统的模型 f a 4 不幸的是，一般当p 接近1 时，聚合或是截断都不能把握系统的性能指标 尽管理论上矩阵分析方法能够直接分析两维无限的马氏链，但是矩阵分析方法对一 维无穷的马氏链分析时要比分析两维无穷时要简单得多大多数用矩阵分析方法的 文章，首先是把两维无穷降为一维无穷比如对顾客数加一个上界，从而截断马氏 链的状态空间，参看 3 2 ，3 3 ，5 1 n g o 和l e e 5 1 】是对状态空间按照高优先级的顾客 的数量进行分块，然后再对分块后的状态空间再分块然而当p 0 8 时数值结果 并不好另一种研究方法是利用指数工作量，写出显示的平衡方程然后求根一般 来说，这类文章得到复杂的数学表达式，当p 很大时，数值结果也不稳定 s l e p t c h e n k o 在这方面作了一些突破性的工作阻，5 5 1 这两篇文章延续了a v 第一章多类顾客经典捧队系统的发展 3 h a r t e n 和a s l e p t c h e n k o2 0 0 3 年【1 8 】中的思路( 我们将在下下一节进行详细的介 绍) ，直接考虑排队系统边缘的平稳分布，而不构造马氏链这两篇文章的突破性工 作在于他们对每个优先级的顾客中含有不止一类顾客的优先排队系统作了分析，而 到目前为止，就我们所知只有这两篇文章涉及到这个问题这两篇文章考虑了两个 优先级，多个服务台的排队系统，每一个优先级中可能有不同类别的顾客，因为每 一类顾客都有其自己的指数服务率，这等价于假定了一个超指数服务时间的两个优 先级的排队系统用联合生成函数和矩阵分析方法解决理论上，他们的技术可以 推广到p 日分布，但是由于p h 分布会加大难度，于是他们仅分析了超指数分布 的情形 对于两个以上优先级的排队系统，只有粗糙的逼近结果b o n d i b u z e n ( b b ) 在【4 】中的逼近结果简单可用，非常漂亮他的利用了一个非常直观的结果：k 个 服务台带优先级的排队系统相对于k 个服务台先到先服务的排队系统的改进与一 个服务台情况的改进是相似的： e d m g 似p 0 1 e f d m g 1 p r 叫 可扫丽两葡商可可l 啄羽而研j 。口 其中a 为常数，e d m g 七咖】表示k 个服务台、速度为v k 的优先系统的延迟时 间均值；e d m g 肚f c f s 】表示先到先服务排队的对应的量左边的m g 1 是指 个服务台速度为1 情形当所有类型的顾客的服务时间都是相同的指数分布时这 种关系是非常明确成立的，但是除了这种情况，结果又是如何还没有人研究 m i t r a n i 和k i n g 在【4 7 】用逼近方法研究了两个以上优先级、指数分布的排队 系统，n i s h i d a 5 2 1 也用了这种逼近，把前者关于两个优先级的分析推广到两个以上 ( m 2 ) 优先级的m m k 排队系统，我们把他们的逼近方法称为m k 一逼近和 b b 把所有的顾客都聚合为一类顾客不同，m k 一聚合为两类被聚合的顾客的服 务时间用个与原服务时间有相同一阶矩的指数分布逼近，这种逼近显然是不够精 确的在这种方法的基础上，m o th a r c h o l b a l t e r 和t a k a y u k io s o g a m i 在【2 】提 出了个新的分析方法，这个新方法提供了第个对具有两个以上优先级m p h k 4 第一章多类顾客经典排队系统的发展 排队的几乎精确分析这种新的方法被称为r d r ( r e c u r s i v ed i m e n s i o n a l i t yr e d u c t i a n ) r d r 的思想是延续了m i t r a n i 和k i n g 在 4 7 】以及n i s h i d a 在【5 2 】中的 聚类思想他们在降低维数的同时并没有截断，而是通过在马氏链中引入”忙期转 移”来降低维数r d r 使我们能够递归的把m 维无穷的状态空间降低为一维无 穷的状态空间其中唯一需要逼近的地方是必须用p 日分布来逼近“忙期转移”的 忙期理论上，r d r 方法能够解决任意多个服务台，任意多个优先级p 日服务时 间的系统另外，r d r 效率很高，计算时间非常的短下面介绍一下r d r 方法 r d r 方法是把多个优先级先归并为两类，最低优先级的顾客为一类，其他比 较高优先级的归并为一类考虑归并以后的排队，由较高优先级的顾客引起了忙期 开始状态( 设有m 个) 和这样的忙期的结束状态( 设有n 个) ，现在我们忽略。忙 期”的中间过程，把它仅看成从。忙期”开始状态到“忙期。结束状态的转移，称为 。忙期转移”，一共有m n 种转移再用p 日分布去逼近。忙期”分布这样处理 后，状态空间只有最低优先级的顾客数是无限维的，其他较高优先级的顾客的转移 被看作有限状态的转移，于是根据系统中最低优先级顾客数确定水平集，我们得到 了个拟生灭过程，再用矩阵几何的方法由于采用的是p 日分布逼近，使得结果 更加精确在文章中m a rh a r c h o l b a i t e r 和t a k a y u k io s o g a m i 在每一对“忙 期”开始状态到“忙期”结束状态中间又虚设了一个新的状态，这个新的状态与“开 始”和。结束”状态有关。开始状态到新状态，新状态到。结束”状态，。开始。 状态到“结束”状态的转移时间服从三个参数的指数分布，也就是2 相位的c o x i a n 分布他们发现当2 相位的c o x i a n 分布与忙期三阶矩都吻合时就能够得到比较好 的逼近效果，对从0 0 5 到0 9 5 ，以及从1 到1 2 8 做出的所有结果与仿真的误差都在 百分之二以内r d r 方法的精确性肯定还会因为更好的忙期逼近而更加精确 第一章多类顾客经典捧队系统的发展 1 2m m k 多类顾客排队系统 5 对于多类顾客没有优先级的经典排队系统中，大都是用逼近技术和渐进方法研 究，而且大多都是针对个服务台模型直接研究多服务台的文章就非常的少，上 个世纪八十年代d es m i t 和c o h e n 做了一些工作d es m i t 分析了多类顾客 g x i m i k 排队系统，其中不同的顾客服务率不同他用相位向量分析了该系统，利 用l s 变换和w i e n e r - h o p f 分解技术求解，得到了等待时间和队长平稳分布的显示 解，并且平稳等待时间符合混合指数分布，从而推广了对于m h m l 2 的结果，然 而所得到的结果只是理论上的后来d e s m i t 又得到了数值界，但是也仅限于两类 顾客的排队系统而已 研究这类排队系统的另一种途径就是利用逼近技术或渐进方法b e r t s i m a s 和 m o u r t z i n o u 考虑了这样的排队系统；一般到达，高负荷服务，然而他们得到的结果 仅限于个顾客的排队系统d i a z 和f t t 曾给出了关于一个服务台情况的逼近他 们逼近的理论基础就是平均等待时间与顾客类型无关，并且他们假设排在队列中等 待服务的顾客与正在接受服务的顾客之间的关系用一个简单的分数表示对于这类 排队系统，很少有精确解，对顾客的类型以及服务台个数上都有很大的限制，一般都 是两类顾客，单服务台或最多两个服务台幸运的是a v h a r t e n 和a s l e p t c h e n k o 在这方面得到了很好的结果2 0 0 3 年他们给出了泊松到达、指数服务的这类排队 系统的精确平稳解 1 8 】，同时也证明了排在队列中等待服务的顾客与正在接受服务 的顾客之间的关系的关系远没有d i a z 和f u 想的那么简单他们打破了传统的思 想，不是通过构造马氏链找平稳解，而是直接从平稳状态的边缘分布出发，找到边 缘分布的平衡方程，再求解这篇文章的突破在于 ( 1 ) 他们对顾客的类型数和服务台的个数都没有限制； ( 2 ) 打破传统，另辟途径； ( 3 ) 找到了精确解得特殊结构 并沿着这篇文章的思路，他们研究了强占优先的多类顾客、多服务台排队系统【5 5 】，a s l e p t c h e n k o 6 第一章多类顾客经典排队系统的发展 又独立研究了非强占优先情况【5 4 】可以说他们对人们研究多类顾客排队系统在思 想上提供了另一条道路下面详细的介绍一下他们的模型及方法 模型。 k 个服务台、类顾客排一队；第i 类顾的到达服从参数为九的泊松输入， 服务时间服从参数为胁的指数分布；实行先到先服务原则下面给出相关符号； a = 墨九， 锄= 妻， 丢= 鉴t 毒， p = 会， 胁= p ( 1 + 魂) ， p 2 历， 胁2p t l + 仉) ， s 、毗分别表示第i 类顾客接受服务和等待服务的顾客数，( i = 1 ，) ，面= ( 毗) ，畜= ( s i ) ，i 面l + i 苔| _ n ，6 ( s ) = 考s 反我们关心的是概率p ( 丽，动 当n k 时， p ( w ，_ ) = r ( - ) 当n 后时， 胞，动= r ( - ) l - | ! 筹 从而，求p ( 砜- ) 转化为求r ( - ) ，降低了维数也就降低了求解难度令 r = ( r ( _ ) ) 为d ( ，七) = 锱维列向量于是有如下的平衡方程： 当n 七时， ( ( 1 + p ) i + d ) r = p r 一1 + a r + l( 1 ) 当礼k 时， 仇r = p r r 一1 + 鼠r + i ( 2 ) 其中 蜓同= 6 ( 习同， a 【_ 】= 丢墨。甚。啦( 1 + 妨) ( 勺+ 1 一e 玎) 眵一百+ 醐， 风：焉一幺，仇【- 】= ( 警+ p + 6 ( 吾) ) f 同， 第一章多类顾客经典捧队系统的发展 7 r ：幺一1 一幺，r 同= 竺l 啦晦一瓦】， 最：幺+ l 一幺，吸毒阁= 妻竺1 ( 1 + 也) ( & + 1 ) 眵+ 司，n 七，并且文= 0 ，i = 1 ，时，他们发现要求的量可以由a 的特征向 量和特征根表示出来： r = ( 三) 一( n - k ) y p 一8 t 其中；为a 的特征值，y 【j = 七! n 竺。簧为a 的与之对应的特征向量 进一步如果令 乡= c r t ，r ，翻纩= 【；“l + ? ，+ 回一言a 那么由( 1 ) 有 织一澎吸+ l 他们找到了边缘平稳分布与说的特征向量和特征值之间的关系从而求出了r ( - ) 精确解，并在此基础上得到平均队长、平均等待时间，并且可以轻松的计算队长和 系统中各类顾客数的高阶矩，甚至可以得到系统中不同类型顾客数之间的相关系数 等等 他们的结果也存在一定的局限性；对于优先排队系统只考虑了两个优先级的排 队，对于两个以上优先级情况没有给出结果。 8 第一章多类顾客经典排队系统的发展 1 3多类顾客拟可逆排队系统 拟可逆排队最早由m u n t z 4 8 1 提出，由于这类排队系统具有很好的性质( 泊松输 入、泊松输出；具有乘积形式的平稳分布) ，于是很早就引起了非常广泛的关注，早在 上个世纪七、八十年代拟可逆排队就已经发展的非常成熟了，其中k e l l y 做了非常重 要的工作【3 5 ，3 6 ，3 7 】，关于拟可逆排队( 网络) 的参考文献有很多，但是一般建立在以 前的框架之上没有太大的突破由于互联网的广泛应用，人们一直也没有停止对这类 排队系统的研究，提出了一些新的拟可逆排队模型，如m s c c c ( t h em u l t i s e r v e rs t a 一托鳜w i t hc o n c u r r e n t d 8 s s e so c u s t o m e r s ) m s h c c ( t h em u l t i s e r v e rc e n t e r w i t hh i e r a r c h i c a lc o n c u r r e n t - c l a s s e sc o n s t r a i n t s ) ，以及比较新的o i ( o r d e ri n d e p - e n d e n t ) 排队d j 排队包括了对称排队的很大一部分，两且还包括了我们前面 提到的m s e d c 和m s 日9 d ，具有比较一般的性质，下面我们在【3 】的基础上介 绍一下d ，排队模型 q = 1 ，2 ，k ，第i 类顾客的到达间隔服从参数为的指数分布，也就是 泊松输入，服务时间服从参数为芦，的指数分布，歹= l ，k 每类顾客的到达和 服务都相互独立顾客按照他们到达系统的顺序排成一队令c = ( ，c 1 ) 表 示队长为住时的状态，其中色表示在第i 个位置的顾客类型，i = 1 ，n 系统 为空时，用0 表示则c 所在的状态空间为圣= o ) u u 甚l 舻) 当系统处于状态g = ( g l ，c 1 ) 时，服务台以速度k ，c 1 ) 进行服务， 并以比例m ( c r i ，c 1 ) 对第i 个位置上的顾客进行服务当第i 个位置上的顾客服 务完毕，则系统原来的i + 1 ，死位置上的顾客变为第i ，佗一1 位置上的顾 客这里并不要求是，( ，c 1 ) = 1 ，也就是说系统的一部分服务能力可能会 被浪费掉第i 个位置上的顾客离开系统的速率为 ( c ，l ，c 1 ) c t m ( c n ，一，e 1 ) 第一章多类顾客经典捧队系统的发展 系统减少一个人的速率为 如果对于任意的( c ，i ，c 1 ) 圣，和任意的i = 1 ，礼，都有 ( c n ，c 1 ) p q m ( c 。，c 1 ) = p ( 佗) 鼠( c n ，c 1 ) 9 丌( ，c 1 ) = 7 r ( 啊n = 1 雨a c , 七( ，c - ) p c n ，= l ， s t c c n ，q ，= ： ；二亍k ， p ( 佗) = 1 ，s i ( c n ，c i ) = p 丑i ( ，c 1 ) q椎 q pq k ：l 1 0 第一章多类顾客经典排队系统的发展 其中当第i 个位置上的顾客正在接受服务则 丑 ( c n ，e 1 ) = 1 ， 否则 亚i ( ，c 1 ) = 0 ， 则m s c c c 是o i 的，从而是拟可逆的，它是f c f s 排队系统的一个拟可逆推 广于是我们很容易就理解这个排队应该具有乘积形式的平稳解，而这在研究这类 排队系统的初期【4 ，7 】并没有得到合理的勰释，不仅如此【3 1 比他们分析起来要简单 得多 近年来由于计算机中的广泛应用，人们对p s ( p r o c e s s o rs h a r i n g ) 系统给与了 极大的关注，并由p s 系统有推广产生了g p s ( g e n e r a l i z e dp r o c e s s o rs h a r i n g ) 和 d p s ( d i s c r i m i n a t o r yp r o c e s s o rs h a r i n g ) 现代的c p u 都是依据工作的优先次 序来分配服务率的，为了描述这样的模型于是多类顾客、共享时间的系统就被提出 来了，其中g p s 和d p s 是主要的两大类g p s 模型保证每类顾客有一个最小 的服务速率，当类顾客空时，把剩余的的服务能力分给其他需要服务的别的类型的 顾客与g p s 不同，在d p s 模型中并不保证每一类顾客都能同时接受服务，对每类 顾客的服务分配取决与这类顾客在顾客总数中的占的比重带优先级的p s 其实就 是d p s 得一种特殊情况在d p s 系统中由一个权重向量 鲰 0 ，k = 1 ，k ， 决定分配给每一类顾客的服务速率，其中k 表示顾客的类型数，如果系统中有， 个第k 类顾客，则每个第k 类顾客的服务速率为； r k ( y l ，坛) 2 西g 两k 当所有的权重数都相同时，d p s 系统就是p s 系统通过改变权重向量可以有效 地控制不同类型顾客的瞬时服务率i a s n o g o r o d s k i 对d p s 系统做了非常重要的 工作，a i r m a n ，a v t a c h e n k o v 和a y e s t a 对d p s 系统所取得的研究成果做了比较 详细的总结 第一章多类顾客经典捧队系统的发展 1 4多类顾客带重试的排队系统 1 l 多类顾客带重试的排队系统的基本模型：到达过程与服务时间以及重试间隔分 布是独立的，到达过程、服务时间以及重试间隔分布依顾客的类型而定多类顾客 的重试排队分析起来远远要比一类顾客情况困难，我们必须处理多维的随机游动 这类系统的最简单模型是有n 个类型的顾客，第i 类顾客服从参数为九的泊松输 入，其重试率为地，服务服从一般分布b i ( z ) a = a l + + a 。， 佛= 九屈l ， 触= f o x k d b i ( z ) ， 反= 妻i = 1 缸 p = a 侥= 反 i = l p = 胁，i = 1 ，2 ，n 是一种比较简单的情况，h a m s c h k e 在【1 7 】中对该系统做了 分析 k o r n i s h o v 在【3 9 】中研究了服务时间服从指数分布情形，他得到了平稳状 态下系统的平均队长的一组线性等式： m = e 眦( t ) 对于两类顾客一般服务时间情形，k u l k a r n i 在【4 1 】中得到了l 、n 2 的显示表 达式对于一般的他类顾客情形，f a l i n 在【9 】中得到线性等式组： m = 志+ 龛尚戤 蔷篇俐2 戤1 + p ( 2 ) 并且他在【1 0 】中证明了过程( l ( ) ，眠( t ) ) 是矩闭的，即线性等式组对任意阶 矩成立例如二阶矩 k = e m ( t ) ( t ) 一国e 腿( t ) 1 2 第一章多类顾客经典排队系统的发展 幽+ 学蔫+ 等南 其中x i 满足( 6 3 ) 式，z j 满足以下关系 跏胁等等害= 一鲁鬻一等一警南警 一丢塾m 。( 鬻+ 而x j + x k ) 上个世纪八十年代末九十年代初，人们发现了批量到达的多类顾客重试排队系 统与分支过程的有很深的内在联系，于是开始用分支过程来分析原重试过程，这个 方法非常的巧妙，最开始是出现在g r i s h e c h k i n 的【1 5 】，下面我们根据 1 6 】介绍一 下它的大概思想 首先我们先介绍一下g r i s h e c h k i n 考虑的模型：个服务台，顾客到达是泊松 的，每次到达系统的顾客可能有n 种类型，其中每一类顾客数服从一个离散分布并 且相互独立如果到达的一批顾客发现服务台忙，则全部进入系统重试；如果到达 的一批顾客发现服务台空闲，则随机的挑选一类顾客中一名接受服务，其余顾客进 入系统重试每类顾客的服务时间服从个一般分布并且相互独立每类顾客的 重试间隔服从指数分布，并且相互独立到达过程、服务过程以及重试过程也都相 互独立 下面介绍如何把这个重试系统与分支过程建立联系在建立联系的过程中起最 重要作用的就是建立了。一个新的时间。：用个钟表来记录时间，当服务台忙时， 就让它停下来；当服务台空闲，让它走把这个钟表显示的记为t = 亡( t ) ，用t 表 示原来的时间，显然t t 新时间记录了顾客在系统中等待服务的时间新时间 下的批量到达的多类顾客带重试的排队就与带迁移的分支过程联系在一起：顾客相 当于分支过程中的个体，顾客z 到达系统认为是个体z 生；顾客z 离开系统认为 是个体z 死顾客的等待过程认为是个体存活过程当一批顾客到达系统时，系统 正忙，则这批顾客进入系统重试，系统中的顾客数增加，相当于分支过程个个体 死，新生了一批新的个体；当一批顾客到达系统时，刚好系统空闲，则在这批顾客 第一章多类顾客经典捧队系统的发展 1 3 中随机选一个顾客接受服务，剩余的顾客进入系统重试，相当于分支过程的迁移 个体z 的子代相当于是在顾客z 的服务时间内到达系统的顾客g r i s h e c h k i n 1 6 中证明了这个分支过程个体存活时间以及迁移间隔时间是服从指数分布的这样一 来，原重试过程的主要性能指标如：队长、等待时间、重试次数等都与相应的分支 过程中的量相对应，于是我们可以利用分支过程的已有结果来分析原重试过程，主 要结果参看【1 5 ，1 6 】 另一方面在电话、传真以及数字网络的实际应用中，当服务台忙时，输入和输 出并不是“平等的。不能输入，也就是拒绝输入信号，要输出的信号排队等待服 务，直到服务台不忙输入才被允许于是人们又开始研究带优先级的重试排队这 个问题最早由l e d e r m a n 提出，对这类系统做了最初步的分析，但并没有给出严格 的证明c h o i 和p a r k 也独立研究了贝努里机制的m i g l l 重试排队，该模型是这 样的s 服务台空时，到达的顾客立刻接受服务；当服务台忙时，顾客以概率p 留在 系统中排队，以概率q = 1 一p 退出系统重试直到服务台空为止排入队列的那些 顾客相当于具有较高的优先级这个模型相当于是具有相同服务时间分布的两类顾 客，其中一类顾客的重试率等于无穷大后来f a l i n 等人对这个问题又做了进一步 的研究，并提出了这类系统的最一般模型： 个服务台，有两类不同的顾客，每类顾客的输入是一个泊松输入，设第一类 顾客有优先权当服务台忙时第类顾客按照某种原则( 如先到先服务) 排队等待 接受服务，第二类顾客退出系统重试当服务台把排在队列中的顾客都服务完，并且 刚好有一个第二类顾客重试，则服务第二类顾客如果一个第一类顾客来看到服务 台正在服务第二类顾客，则排队等候服务，即实行非强占优先每类顾客的服务时 间服从一般分布设舶为第d 个离开时刻，a ( t ) 、c ( t ) 和n ( t ) 分别为t 时刻 正在接受服务的顾客类型、t 时刻的队长( 不包括正在接受服务的人) 和t 时刻进 行重试的第二类顾客数，x ( t ) = ( a ( 啦一o ) ，c ( u d o ) ，n ( y d o ) ) 构成了一个马氏链 【1 2 】中给出了该马氏链遍历的充要条件和平稳分布 近年来，对多类顾客的重试排队系统研究的不是很多，并且就我们所知人们对 1 4 第一章多类顾客经典排队系统的发展 多类顾客重试排队系统的研究仅限于一个服务台情形，而对于带优先级的重试排队 也仅限于两类优先 第一章多类顾客经典排队系统的发展 1 5b r i 算法 1 5 在这一章的最后我们还想介绍由史定华老师在【5 3 】给出一个新的算法。 b r i 算法这个算法使得我们能够对有特殊结构的多类顾客排队系统在很短的时间内得 到非常精确的数值解两类顾客排两队、两个服务台、相互支持的排队系统就是一 个很典型的例子 【5 3 】中新定义了个过程；t q b d 过程这个过程有以下两了特征：( 1 ) q 矩 阵的所有的子块都是无限维的q b d 过程( 每个水平都有无穷个相位) ；( 2 ) 其中 的每一个无限维子块都是三对角的这里我们只介绍最简单的一类t - q b d 过程： 与水平集无关其q 矩阵有如下形式： 其中 其骨架过程为 b o = q = p = b l ob o o 5 2 06 1 0 6 q 1 q o q 2 q l q o q 2q i 岛a c b a c b 6 2 0b l o6 0 0 ，a = a la o a 2a l a o 钇a l 1 6 第一章多类顾客经典排队系统的发展 b ，c 与a 有相同的结构和类似的记号 如果q 遍历，从而其骨架过程p 遍历于是对于任意给定的初始分布责( 0 ) 由 递推式 弁( n ) = 亓( n - 1 ) p ( 3 ) 得到的向量序列 靠( o ) ，弁( ，竟( m ， 收敛到p 的平稳分布7 f 也就是说，我们可以 用( 3 ) 式通过迭代近似计算p 的平稳分布，而通过这种迭代所计算出来的平稳分布 与真正的平稳分布之间的误差只在于迭代的次数，迭代的次数越多，所得到的结果 越精确，理论上只要我们不断的迭代下去就可以算出平稳分布，因而可以说我们找 到了一条找到p 的平稳分布的方法然而当转移概率矩阵p 为无限维时，这种方 法并不是可以直接应用的由于初始分布的任意性，于是我们可以取只有前k 个元 素不为0 ，其余全为0 ，( 特别地取k = 1 ) ，那么当转移概率矩阵有比较好的结构时 ，亓( n ) 的非零元素将会随n 变化有规律的增加，从而我们仍然可以通过( 3 ) 来近似 求出该过程的平稳分布把这种思想应用于t - q b d 过程，就得到了b r i 算法其 实质就是把无限的问题转化为有限问题，用有限问题去逼近当然需要些技巧在 里面 b r i 算法； ( 1 ) 给出停止条件，并置7 r ( o ) = ( 1 ) ，佗= l ； ( 2 ) 迭代：计算( a ) 7 r c n ) = i t ( n - 1 ) r ( b ) 如果满足停止条件，则输出，否则，佗= 佗+ 1 返回( o ) ( 3 ) 当n = n 停时，把 7 r = ( 7 ，7 r i ，7 r 妒) = ( 榔) ，搿，榴) ，( 捌，i r ( n ) ，榴) 作为平稳分布7 r 的近似 其中 r = ( b ( o 。，) 第一章多类顾客经典捧队系统的发展 磷1 ) = b l ob o o 马= ( 竺：三三a 。2 ，) f 一 鲋：卜 6 2 0 l f 胪) ：f 1 f 岛 6 0 0 6 0 ) k ( ，五1n o 、) ， 昆= ( ：三三三三a ) f 水) ：f 而 1 1 0 2 i f 萨) ：i 西 ie 2 i 醪= ( ：兰竺 b 。，= ( ：圣：6 0 c 1 l i 五l i 。卜 f f 西 伊k iq l 口la o a 2d 1 c ic o c l 1 7 、， 印 口 咖 咖 的 魄 0 ， 1 8 第一章多类顾客经典排队系统的发展 r 是南2 ( 凫+ 1 ) 2 的矩阵 b r i 算法可以在很短的时间内得到比较好的结果，但是遗憾的是这种算法对无 穷小生成元的结构要求太严格，因此对多类顾客排队系统的贡献足非常有限的下 面给出一个非常简单的例子做以说明 最初在 5 3 】的影响下，我们考虑了先到先服务机制下，多类顾客排队系统中最 简单的排队；单个服务台，两类顾客，到达分别服从参数为a l ，a 2 的泊松输入，服 务分别服从参数为p l ，p 2 指数服务，其中j 【l 2 b = ( 一a o b o ) 日 如 第一章多类顾客经典排队系统的发展 f f 瓦瓦 l i m l a 1 最= i 卜 m k 一1a k 一1b k i 7 r 伽) = 7 r 一1 r = ( 7 分，7 r i n ) ，万驴) 虽然在理论上我们最终可以迭代出结果，但是实际上是行不通的，对计算机内 存的要求太大，并且时间太长! 而这只是两类顾客，一个服务台的系统! 在下一章 我们将给出关于这个模型的有效算法 第二章多类顾客新型排队系统的发展 马尔可夫到达过程( m a p ) 的提出对排队论产生了很大的影响，使得人们可以 利用矩阵方法对随机环境下的排队系统进行分析，特别是极大的促进了多类顾客排 队系统的发展，给排队论注入了新的血液，极大的激发了研究人员对这类排队系统 的研究兴趣，从而促进了排队论的发展曾经一度有人认为排队论“死了”，事实证 明排队还是那么鲜活，而m a p 的提出特别是与多类顾客的结合更把排队论推向了 更高一级的发展阶段由m a p 又引出的一系列新的到达过程如批量到达的马尔可 夫到达过程( b m a p ) 、离散时间马尔可夫到达过程( d m a p ) 、带标记的马尔 可夫到达过程( m m a p k 】) 等，特别是m m a p k 】包含了b m a p 和d m a p ， 与多类顾客输入的排队有着天然的联系研究人员们对具有这类到达过程的排队系 统作了广泛的研究，取得了非常重大的成果同时对相关的理论也有所成果这类 排队为区别于经典的排队模型，我们称之为“新型排队”对于这类排队模型的处理 方法基本上是用矩阵分析方法和拉普拉斯变换，在研究过程中又提出了一些新的内 容如具有树型结构的矩阵、年龄过程等，同时也提出了一些新的方法本章的第一 节在【2 3 】的基础上详细的介绍m m a p k ，第二节对近年来具有m m a p k 输入 的排队系统所取得的成果作简要的介绍 第二章多类顾客新塑排队系统的发展 2 1m m a p k m m a p k 】是个连续时间或离散时间下，有多类顾客( 批量) 到达的随机点 过程n e u t s 给出了如下的定义； a f h ：h = h i h 。，1 k ，1 i 佗，1 n o 冗( j ) b ( j ) ( 4 ) 丌( o ) 是b 的左特征向量并且满足条件7 r ( o ) ( ，一r ) 1 e = 1 2 0 0 0 年，何启明利用这个结果研究了m m a p k p h k n l c f s 非抢占优 先的排队系统，并利用树形结构的拟生灭过程的结果给出了求每一个节点的平稳概 率的有效的算法，下面我们具体的介绍一下有树形结构的拟生灭过程 有树形结构的拟生灭过程是拟生灭过程的一个推广，我们这里仅给出离散时间 情形，连续时间类似考虑一个离散时间的两维马氏链 ( ，厶) ，n o ) ，其中 表示数的节点，厶为l 到m 之间的某个整数下面我们先定义k a r y 树除 了地下节点( 用1 表示) ，每一个节点有k 个孩子，地下节点1 与根部节点0 相 连，用由1 到k 这些整数构成的整数串来表示树的节点，例如根的第k 个孩子用 k 表示，k 的第z 个孩子用舰表示，削的第h 个孩子用k l h 表示，以此类推( 这 里没有考虑批量到达) 令 = ，= k l k 2 ，1 k ，1 i 礼，n o u o 中的每一个元素表示树的一个节点对于中的元素定义如下的运算： 加法：j = h k ，1 k k j + k = k l k 2 k 。k 第二章多类顾客新型排队系统的发展 减法。j ；k l k 2 k ，h = k ，一。= h 如k n l a f 马氏链 ( k ，厶) ，佗o 的状态空间为 l ，m ) ) u 一1 ) l ，m 1 ) ) 在( ，厶) = ( zi ) 的条件下 当j - i 时，以概率知，( ，i ，) ( 知) ，( + l ，厶+ 1 ) = ( j + 七，i ) ； 当j 0 时，以概率a l ，( i ) ( 七i ，i ) ，( + l ，厶+ 1 ) = ( zi 7 ) ； 当j = 0 时，以概率a l ，( t ，) ，( 五l + 1 ，厶+ 1 ) = ( z i ) ； 当j = 0 时，以概率6 2 ，( i ，r ) ，( k + l ，厶+ 1 ) = ( - i ，i 7 ) ； 当j = - 1 时，以概率b l ，( ，i ，) ，( x 。+ l ，厶+ 1 ) = ( - i ，i ) ； 当j = - i 时，以概率b o ，( 硒，) ，( + l ，厶+ 1 ) 一( 0 ，i ) ； 厶( 后) = ( a o ，( 坩“后) ) ，a x ( k ) = ( a l ，( ，t ，) ( 七) ) ，a 2 ( k ) = ( 眈，( i ) ( ) ) a i = ( a l ，( i ) ) ， 岛= ( 6 2 脚，) ) ，b 1 = ( b l ，( 谢，) ) ，岛= ( b o ，( 例) ) 令n ，( 七) = ；，磁：) ( ，眠，) ，l i ，i 7 m 表示( ，厶) 从( 以z ) 出发，中途 不经过j ，到达( j + k ，i ) 的概率；姨( 忌) 表示( x 。，厶) 从( j + k ，i ) 出发，以( z i ) 首次到达j 的概率r ( k ) = ( r i ，一( 七) ) ，c