（概率论与数理统计专业论文）离散时间smkphkc（c12）fcfs排队系统的年龄过程.pdf

摘要 本文是研究这样一个离散时间的排队系统；顾客有着多种类型，成批到达，到 达过程是个半马尔可夫过程，按照先来先服务的服务准则，并且每一个顾客的服 务时间服从各自的尸日分布 文章开始部分是引言，对当前有着多种类型顾客的离散时间的排队模型的研 究做了介绍和分析第一章是对这篇文章的一些知识点和计算工具的介绍第二 章是对s m k i p h k i 1 f c f s 排队系统的描述，以及对其年龄过程做了详细分 析，并引进一些附加变量构造个关于年龄过程的马尔可夫链，从而计算出年龄过 程的转移矩阵第三章是本文的重点，首先还是对s m k p h k 2 f c f s 排队 系统的描述，接着分析了年龄过程为了降低计算的复杂，我们巧妙地选取了系统 中某一个顾客批的年龄作为系统的年龄，并引进一些附加变量构造一个关于年龄过 程的马尔可夫链，最后对这个马尔可夫链的转移矩阵进行了详细计算第四章是对 s m k p h k 2 f c f s 排队系统的年龄过程的甲稳分布的分析，在计算出甲稳 分布的假定下。对排队系统的另外一些信息做了初步推导 关键词：排队系统，半马尔可夫过程，j 口h 分布，马尔可夫链，年龄过程 i i 摘 要 a b s t r a c t i n t h i st h e s i s ，w es t u d yad i s c r e t et i m eq u e u e i n gs y s t e mw i t hm u l t i p l et y p e s o fc u s t o m e r sa n daf i r s t - c o m e - f i r s t - s e r v e d ( f c f s ) s e r v i c ed i s c i p l i n e c u s t o m e r sa r - r i v ea c c o r d i n gt oas e m i - m a r k o va r r i v a lp r o c e s sa n dt h es e r v i c et i m e so fi n d i v i d u a l c u s t o m e r sh a v ep 日d i s t r i b u t i o n s i nt h i st h e s i sa tf i r s ti st h ei n t r o d u c t i o n ，w h i c hi n t r o d u c e sa n da n a l y s e st h es t u d y n o w a d a y so fd i s c r e t et i m eq u e u i n gm o d e l sw i t hm u l t i p l et y p e so fc u s t o m e r s t h e f i r s tc h a p t e rg i v c * a ni n t r o d u c t i o na b o u tt h ek n o w l e d g eo ft h i st h e s i sa n dc m c u l p t i o n a lm e t h o d s t h es e c o n dc h a p t e rd e s c r i b e ss m k p h k 1 f c f s q u e u ea n d a n a l y s e si t sg e n e r a l i z e da g ep r o c e s sp a r t i c u l a r l y w ei n t r o d u c es o m ea u x i l i a r yv a r i - a b l e st oc o n s t r u c tam a r k o vc h a i na s s o c i a t e dw i t ha 9 ( ) a n do b t a i nt h et r a n s i t i o n p r o b a b i l i t ym a t r i xo ft h i sm a r k o vc h a i n t h ep i v o to ft h i st h e s i si st h et h i r dc h a p t e r w h i c ha tf i r s td e s c r i b e ss m k p h k 2 f c f sq u e u ea n dt h e na n a l y s e si t sg e n - e r a l i z e da g ep r o c e s s ，w ec h o o s et i l ea g eo fs o n i cb a t c hi nq u e u e i n gs y s t e ma st h ea g e o ft h i ss y s t e ms k i l l f l l l l yt or e d u c et h ec a l c u l a t i o n a lc o m p l e x i t y w ei n t r o d u c es o m e a t t x i l i a r yv a r i a b l e st oc o n s t r u c tam a r k o vc h a i na s s o c i a t e dw i t ha 9 ( ) a n df i n dt h e t r a n s i t i o np r o b a b i l i t ym a t r i xo ft h i sm a r k o vc h a i ni nd e t a i l t h ef o u r t hc h a p t e ra n a l y s e st h es t e a d ys t a t ed i s t r i b u t i o no ft h ea g ep r o c e s so fs m k j p h k 2 f c f s q u e u e g i v e nt h es t e a d ys t a t ed i s t r i b u t i o n ，w eh a v ep i l o ts t u d yo fo t h e ri n f o r n m t i o n i naq u e u e i n gs y s t e m k e yw o r d s ：q u e u e i n gs y s t e m s ，s e m i - m a r k o vp r o c e s s ，尸日一d i s t r i b u t i o n ，m a r k o v c h a i n ，a g ep r o c e s s 首都师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导1 - ，独立进行研究工 作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体 已经发表或撰写过的作品成果对本文的研究做出重要贡献的个人和集体，均已在 文中以明确方式标明本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名 。幻藓 日期：问年朗j a 日 首都师范大学学位论文授权使用声明 本人完全了解苒都师范大学有关保留，使用学位论文的规定，学校有权保留学 位论文并向国家主管部门或其指定机构送交沦文的电子版和纸质版。有权将学位论 文用于非赢利目的的少量复制并允许沦文进入学校图书馆被查阅。有权将学位论文 的内容编入有关数据库进行检索。有权将学位论文的标题和摘要汇编出版。保密的 学位论文在解密后适用本规定。 学位论文作者签名： 南藓 日期：j 司年耻月2 渊 引言 现代通讯网络需要处理各类数据，这些数据在容量等方面是各不相同的现代 供应链的设计也是要满足顾客的不同需要这相当于在排队系统中顾客是有类型 的又在现实生活中我们还经常遇到成批到达的现象，例如在生产制造系统中需要 加工的部件成批到达加工车问。再如在库存系统中，顾客的需求按照复合泊松过程 到达系统以上这些现象都可以描述成成批到达的排队系统。而多服务台问题由于 其应用的广泛而也备受关注，很多排队论的著作中都有多服务台的内容，尤其是在 呼叫中心的设计方面多服务台排队模型更是必不可少的，但现在呼叫中心的设计多 采用单个到达的多服务台模型，而随着呼叫中心应用的越来越广泛，单个到达在实 际应用中渐显不足，因此引入了批量到达模式，使得模型更加贴近实际情况由于 这些随机系统的设计和功能分析的需要，在这篇论文中，我们将研究一类有着多种 类型顾客的离散时问的排队模型，其顾客是批到达，且有两个服务台 因为各种实际应用以及可用于连续时间排队系统逼近问题的研究，所以对于离 散时间排队模型的研究很广在那些经典的论文中，很多对离散时间排队的研究都 集中在单一类型或者多类型的顾客，并且有着不同的服务先后顺序的情况顾客的 到达过程通常假定为独立的泊松过程在刘【1 3 中，主要讨论了离散时间状态下的 批量到达排队系统，推广了经典的离散时问排队模型，考虑单个服务台的情形，假 设顾客批的到达服从几何分布每批到达的顾客数服从一般的离散分布，顾客的服 务时间也服从几何分布，使用嵌入马尔可夫链的方法，分析得到了该随机排队系统 的队长、等待队长等待时间以及忙期等关键指标的母函数这些结论与经典排队 系统中相对应的结论在形式上十分相似，并且将经典排队系统作为其特例，从而推 广了随机排队系统的研究框架 对于有标记转移( 即顾客有各种类型) 的马尔可夫到达过程( m m a p k 1 ) 的研究，在h e 2 1 中，详细介绍了从不同类型的顾客观点出发的排队系统，并给出 了到达时刻不同类型顾客的队长和等待时间在【2 】中引出了m m a p g 1 排队系 2 引言 统，并得到了一个能给出在m m a p c 1 排队系统的忙期服务的顾客数的期望值 的新的公式【2 】还将这一结果在m m a p ( k ) g k 1 排队系统中进行了概括在 h e 3 】，h e 4 】中也都给出了有标记转移的马尔可夫到达过程的介绍在 4 】中， 与【2 不同的是，【4 】在m m a p k 】模型的问题上给出了更详细的讨论并且f 2 】 讨论的是每一个顾客批只有一个顾客的情形，而【4 】是通常的顾客批 4 】考虑了每 个顾客批中顾客的服务顺序，这是其他论文中很少讨论到的问题另外， 【4 】中用 了很正式的方式给出了 2 】中的一些证明【4 给出了一些关于忙期和虚等待时问 的l a p l a c e s t i e l t j e s 变换的结论，并研究了每一类顾客的实等待时间 有了这些介绍，那么对于有多种类型的顾客的复杂排队也就变得可以解决了 比如在h e 5 】和h e 6 中都给出了很好的结果在这篇论文中，我们用的是有标记 转移的半马尔可夫到达过程，这比m m a p k 1 显然要更普遍我们假定在不同类 型的顾客间是没有服务优先权的，这样的排队模型仍然是可以解决的 对于多种类型的顾客没有服务优先权的排队系统来说，我们叮以根据顾客个体 的服务顺序进行分类在h e 5 1 和h e 6 1 中排队系统就足按照后来先服务的服务 顺序进行研究的在【5 中，研究了一个这佯的排队系统：有标记转移的马尔可夫 到达过程，对每一类型顾客的服务时问都服从各自的p h 分布根据每一仑顾客的 类型，采取后来先服务的优先服务准则重点研究了系统忙期时队长的稳态分布， 给出了汁算队长稳态分布，忙期服务的顾客甲均数、忙期的乎均长度效率高的汁算 方法在h e 2 和h e 4 1 中每个类型的顾客的等待时间就是按照先来先服务顺序 进行研究的但是，对于先来先服务的排队模型来说，队长却屉很难分析的，因为 得记住队内顾客的类型在t a k i n e 7 】中，通过利用等待时问的信息而得到队长 然而通常对于一些有趣的排队系统，不像在一些经典的排队系统中分析等待时间那 样，在等待时间的分析中对于队长足没有信息可利用的幸运的是，构造一个与正 在服务中的顾客批的年龄有关的马尔可夫链，从而能够分析等待时间，逗留时间， 这篇论文中正是运用了这种方法 等待时间和逗留时问在排队模型中是很重要的，并且关于对它们的研究也是很 引言 3 深的s e n g u p t a 在【8 】、 9 】和【1 0 】中证明了在连续时间g i i p h l l 排队的等待时 间和逗留时间有矩阵指数分布a s m u s s e n 和0 c i n n e i d e 在【1 1 】中将s e n g u p t a 的结论扩展到了连续时间a x l p h i c 排队中现在，又有一些人研究离散时间有 着多种类型顾客的排队系统的等待时间和逗留时间在v a n h o u d t 和b l o n d i a 1 2 l 中，构造了一个类似在这篇论文中用到的用年龄过程得到的马尔可夫链，从年龄过 程的稳态分布得到逗留时间的分布当然在【1 2 】中的到达过程是马尔可夫过程， 这是与这篇论文最大的不同之处因此，这篇论文我们考虑的是一个离散时间的更 普遍的排队模型我们构造一个广义的年龄过程，这个过程是没有水甲0 这个边 界的在一个服务台的情形下我们可以从这个年龄过程的平稳分布得到等待时间和 逗留时间的分布而【1 2 】提供了一个研究两个服务台的很好的方法，就是研究系 统中在服务的顾客批中年龄较小的顾客批的年龄这篇论文就是依据这个思路对 s m k p h i 引2 f c f s 进行研究的 在h e 1 1 中，研究的是一个离散时间的排队系统，有着多种类型的顾客并且按照 先来先服务的服务准则顾客到达是一个半马尔可夫过程，并且每一个顾客的服务时 间服从p h 分布引进一个由顾客批的年龄过程构造的g 1 m 1 型的马尔可夫链这 个g i m 1 型的马尔可夫链的稳态分布可以精确计算出来，从而正在服务的顾客批 的年龄。系统总的工作量，等待时间，不同批不同类型的顾客的逗留时间等这些变量 的稳态分布也可以得到并且【1 证明出广义的年龄过程和广义的总的工作量过程有 相同的稳态分布，等待时间和逗留时间的分布为p h 分布并得到这些p h 分布的矩 阵表示【1 】还将到达过程深入到更特殊的情况：有标记转移的马尔可夫到达过程，从 而构造一个年龄过程和总的工作量过程的q b d 过程( 拟生灭过程) ，由这个q b d 过程的稳态分布得到了顾客批和顾客个体的等待时间和逗留时间的稳态分布 1 】 对s m k i p h k i 1 f c f s 和m m a p i k i p h k 1 f c f s 这两类型的排队系 统做出了很详细的分析，也得到了一些很好的结果并且对s m k p h k c ( c 2 ) f c f s 这类型的排队系统也作了简要分析，认为对于个服务台的排队系统的 使用方法能够推广到多个服务台的排队系统中，这也为多个服务台的排队系统提供 4 引言 了工具和证明了可行性 这篇论文的基本思想就是采用 1 】的方法，对于s m k p h k 1 f c f s 型 的排队系统，我们构造的与顾客批的年龄过程相关的马尔可夫链与 1 】稍有不同，不 同在于附加变量的定义但最后结果一样，从而对于年龄过程的稳态分布以及后面 其他变量的稳态分布的分析都是不受影响的对于s m k p h i k 2 f c f s 型的 排队系统，我们参照 1 】1 的方法，将一个服务台的情况扩展到两个服务台的情况 在这个过程中难点在于由顾客批的年龄过程怎么去构造一个马尔可夫链，尤其当年 龄是负数的时候这篇论文得到了由年龄过程构造的马尔可夫链的转移矩阵，可以 看到矩阵的结果很复杂，从而给后面稳态分布的求解带来了困难后面关于排队系 统的其他信息，我们都是在已知年龄过程的稳态分布的前提下推导的 这篇论文的余下部分足这样组织的：第一章，我们对一些预备知识作简要介绍 第二章，是对s m i k p h k 1 f c f s 型的排队系统的分析及由其年龄过程构造 的马尔可夫链的转移矩阵的计算第三章，对s m k i p h k 2 f c f s 型的排队 系统的分析及由其年龄过程构造的马尔可夫链的转移矩阵的计算第四章，在假定 第三章构造的年龄过程的马尔可夫链的甲稳分布已经求出的情况下，能得到的一些 排队系统的有用的信息 第一章预备知识 1 1g i m 1 型马尔可夫链( 过程) 在排队论中矩阵解析方法很好的利用了g r ，m 1 型马尔可夫链和m a a 型 马尔可夫链，在这我们只介绍g u m a 型马尔可夫链 定义1 若状态空间e = ( t ，j ) ：t 0 ，1sjsm ) 上的马尔可夫链 ：n o 的概率转移矩阵具有如下形式； p = 玩a o0 b la 1a o j 岛a 2a l 鼠a 3a 2 00 00 a o 0 a 1 , 4 0 其中a k ，b k ( k 0 ) 均为m m 阶非负矩阵，则称马尔可夫链 ：n 0 ) 为 g i m 1 型马尔可夫链。有时，也称p 为g x m 1 型马尔可夫链状态集 ( ，j ) ： i 0 ，1 j m ) 称为水平i 1 2离散型p 日分布 文中排队系统的服务过程是一个尸日分布，我们简单地介绍一下离散型p h 分布 考虑状态集1 ，2 ， l + 1 上的m a r k o v 过程，状态1 ，2 ，m 都是非常返 的，状态m + 1 是吸收的状态概率阵是 p = tt o 01 ，m 。是随机子阵，元素20 ，并有t ese 列向量t o = ( i t ) e ，i t 是 非奇异的 6 第一章预备知识 定义2 非负整值上的离散分布p k ：k 0 称为p 日分布，当且仅当它是上述 m a r k o v 链达到吸收时的转移步数的分布 若m a r k o v 链的初始概率向量是( o ，o z 。+ 1 ) ，则 p o = o t 。+ l ，p a = o t 一1 t o ( k 2 1 ) 离散p 日分布p k ：k 0 的母函数为：p ( z ) = q 。+ 1 + z o ( 一z t ) 一1 t o ； 离散p h 分布p k ：k 0 的阶乘矩为：p ( ( 1 ) = k ! a t k 一1 ( ，一t ) 一e ，k 0 1 3k r o n e c k e r 乘积 在涉及p h 分布时，经常发生不同阶数矩阵的运算，它们是通过k r o n e c k e r 乘积实现的设有k 1x 如，k ：砬矩阵a 和b ，其k r o n e c k e r 乘积定义为 a 固b = ( 4 u b ) a l l ba 1 2 b a l k 2 b a 幻l ba k l 2 b a k l 乜b 可以，爵出a o b 的维数为( - ：) ( 乜k ：) k r o n e c k e r 乘积有如下性质： 1 p ( a 8 b ) = ( p 4 ) 8 b = a o ( 肛b ) ；2 ( a + b ) o c = a c + b o g ； 3 a o ( b c ) = ( a b ) o e ；4 ( a o b ) t = a t b t ； 5 ( a 口) ( g 圆d ) = ( a c ) 圆( b d ) ；6 a _ 1 g b 川= ( a 圆b ) _ 1 ； 7 a ，堤列向量，b a 7 = a t 圆b = b oa t ； 对于以上的性质的证明，我们只需按照k r o n e c k e r 乘积的定义很容易得到 在这我们不给出证明，在文中直接加以应用 第二章s m k p h 网1 f c f s 排队系统 2 1系统介绍 排队系统有k 个类型的顾客( 其中k 为正整数) ，所有的顾客都加入一个队列， 采取“先到先服务。的规则由一个服务台进行服务 2 1 1顾客的到达过程 顾客的到达过程是一个离散的半马尔可夫过程顾客分成k 个类型，并且成批 到达( 我们暂且称为顾客批) 为了描述顾客批的性质，先定义一个整数串的集合； n = j k ：矗= j 1 如矗。，1s 置1 i s 竹k ，1 k s 册 其中，是集合r 中不同整数串的总数，n k 是第k 个批中顾客总数我们假 定是有限的对于一个到达过程，一个串j 一l j 2 靠r 表示一个有n 个顾 客的批，这n 个顾客分别为类型，矗矗我们称j 为这个批的串表示因此， 一共有个不同的批表示 考虑一个有m 。个位相的半马尔可夫链 ( 矗，h ) ，n o ) ，其中矗指第n 个 批到达瞬间半马尔可夫链的位相，是第n 一1 个批和第n 个批到达之间的时间 ( 即转移时问间隔) 顾客批的到达与下面方式的半马尔可夫过程的转移联系在一 起令 为与第r t 次转移相联系的顾客批的串表示，即：一个顾客批厶在转移时 刻到达定义： p 岛= j ，t n = t ，厶= ，i 矗一1 = i ) = p 却j ( ) ，1 t ，j m 。，礼1 ，r ， 其中t 是个正整数，变量以臼( t ) 是在位相为i 的条件上，从上一个批到达后经过 时问t ，顾客批j n 达，并且半马尔可夫过程的位相变为j 的条件概率令现，j ( t ) 是个( i ，j ) 元素为p j , i d ( ) 的m 。m a 矩阵于是，矩阵序列 d d ，j ( ) ，t 1 ，j 杖) 提供了关于有标记转移半马尔可夫到达过程的所有信息定义： d o ( t ) = 拒r 取，j ( t ) ，t 1 ，眈，= b o o l 玩，j ( ) ，t ，k ； 现= e 倒见j = 墨。见( t ) 8 笙三皇兰丝【丝! ! 里【丝! 兰里! 兰堡坠墨丝 于是，矩阵坟为半马尔可夫链“靠，h ) ，n2o ) 的嵌入马尔可夫链在转移时 刻的转移矩阵我们假定坟是不可约的靠是随机矩阵见的不变概率向量，即 有：以玩= 以，口。e = 1 ，其中e 是一个元素全都为1 的列向量 在稳定状态，半马尔科夫链的转移间隔时间( 即顾客批的到达间隔) 可以通过 下式计算； 玩( r ) = 以( t d 。( t ) ) e = l 那么顾客批的到达速率为a = ( e o o ( r ) ) 一，即每个时刻到达的顾客批平均数任意 一个顾客批类型为了的的概率为以d 口、e ，j r 类型为，的顾客批的到达速率 为b = a d 。j e ，即每时刻到达的类型为j 的顾客批的个数类型为k 的顾客 的到达速率为 a ( 的= ( z ) a ，1 k s k d e n 其中( zk ) 指类型为j 的顾客批中类型为k 的顾客的个数注意：k 为类型为 k 的顾客批的到达速率， 1 为类型为k 的顾客的到达速率不失一般性，我们假 定a ， b ，j r ， a ( ) ，1 k k ) 都足正的并且有限 2 1 2 顾客的队列过程 个顾客批到达后，所有的顾客根据在批中的顺序加入队列中所有的批采取 。先来先服务”的方式由两个服务台服务对每一批顾客来说，顾客按他们在批中 的顺序依次服务令g ( ) 为t 时刻队列中顾客类型的数列串，它可以由在t 一1 时刻 可能完成服务的顾客和到达的顾客得到如果q ( t ) = j l j ：矗，那么系统中在t 时 刻有n 个顾客， 类型顾客在接受服务，而j z 类型顾客为第一个在排队等候的顾 客，j 。类型顾客为最后一个排队等候的顾客这n 个顾客将按照扎如，j 。 的顺序接受服务。如果接着一个j 类型的顾客批到达，那么队列将变为g ( ) + j 如果接着一个顾客完成了服务，那么队列将变为，2 ，j 3 ，j并且五开始接受服 务。在这我们不对某类型顾客在其顾客批中拥有优先服务权的情况进行讨论 2 1 3 服务时间 墨三塞兰坐【丝j ! 星l 丝! ! ! 旦兰兰堡坠墨丝 9 每个顾客的服务时间服从离散的p 分布，它们相互独立并且与其到达过程 相互独立对一个类型为k 的顾客来说，它的服务时间矶服从p 日分布，其矩阵 表示为 m k ，o l k ，t k ) ，其中”i 是p h 分布的位相个数，o k 是初始概率向量，孔 是个次随机矩阵我们假定任意一个顾客的服务时问至少为1 这是因为对于离 散p h 分布来说，一个位相的转移的时间为1 。而o z k e = 1 ( 1 ksk ) ，所以顾 客不能一接受服务就被服务完记露= ( i 一孔) e ，其中，是单位矩阵我们假定 每个p h 分布矩阵表示都是不可约的，即死+ 霹a k 是不可约的那么一个顾客 批的服务时间就是这个顾客批中所有顾客的服务时问的总和由于p h 分布的结 构在卷积作用下是闭的，故一个类型为t ，的顾客批的服务时间8 j 也有离散时问的 p h 分布，矩阵表示为 l j ，o t j ，t j ) ，其中对j = j l 如矗，有 n m j = ：。； o c j = ( o f 9 l ，0 ，o ) ； t j = 乃。壤 喂 一，豫一； 乃。 刀= o 0 臻 由离散p h 分布的性质有，一个类型为k 的顾客的平均服务时间为e ( s k ) = n ( j 一死) - 1 e 那么一个类型为，的顾客批的甲均服务时间：e ( s j ) = i j ie ( ) ， 其中川是类型为j 的顾客批的顾客数类型为，的顾客批的服务速率为= ( e ( s j ) ) 根据顾客批的到达速率和服务速率，排队系统的交通强度为 i j i耳 p = b = e o j , ) = b ) e ( s k ) j 6 m7 ” 。1 o “ 2 1 ( 2 1 ) = b n ( j , k ) e ( s k ) = a ( 耐鲰 1 0 篓三童兰坐【丝! ! 堡【丝! ! 兰竺! 兰堡坠墨丝 我们知道排队系统稳定当且仅当p 1 ，于是我们为了系统的稳定性假定p 可定义为： a g ( ) = w n ( t ) + 8 j n 一7 i ( t ) + l + t 一7 7 n ( t ) ，( 2 3 ) 其中n ( t ) 为在t 时刻或t 时刻之前最后一个服务完的顾客批的标号， 仉m 是 指第n ( ) 批顾客离开系统的时段于是，在t 时刻若有一个顾客批离开，那么 n ( ) ，w 。( t ) ，( t ) 这些值就会发生改变，其中( c ) 可通过( 2 2 ) 计算得到 广义的年龄过程 ( ) ，t 0 ) 分析如下：在一个顾客批的服务时间里， a g ( t ) 每过一个时刻增加1 ；当第n 个顾客批完成服务，则要服务的顾客批的等待时问 笙三兰兰丝! 坚! 兰丝【丝1 ! ! 兰堡坠墨丝 1 1 可以通过计算这个得到；+ s j = 一+ 1 当+ 3 一+ 1 是非负的，那么 这就是正要接受服务的顾客批的等待时间，也是它在这个时刻的年龄，即这个时刻 a g ( t ) 的值在第n + 1 个顾客批的服务期间，( t ) 每过一个时刻增加1 ，一直持 续8 矗+ ，个时刻到结束服务这种情况下，a g ( t ) 为正在服务的的顾客批的年龄当 + 8 厶一钆 l 是负数，那么表明下一个要接受服务的顾客批还没有到来，还需要 一o 。( ) = 一( 。+ 8 厶一+ 1 ) 个时刻才能到达在( ) 为负的这段时闻内，系统为 空的，还剩一( ) 长的闲期总之，如果时刻t 有a g ( t ) 0 ，那么变量a g ( t ) 记录 的是正在接受服务的顾客批的年龄；如果a g ( t ) 0 ，那么一n ，( t ) 记录的是闲期的 剩余时问我们称a g ( t ) 为服务中顾客批的广义年龄方程( 2 2 ) 和( 2 3 ) 表明了过 程 ，n20 ) 是 n 口( t ) ，t o 在顾客批离开点的嵌入过程 在一个顾客批离开的时刻，下个接受服务的顾客批的逗留时问可由方程( 2 2 ) 可得为；+ 5 对于a g ( t ) 20 来说，如果+ 5 厶一 r n + 1 0 ，则需5 个 时刻完成一个循环在这8 个时刻中，每过一个时刻，a g ( t ) 的值就增加1 基于以上分析，很容易看出a g ( ) 满足以下方程； r ia g ( t ) + 1 ，如果t + l 时刻服务继续进行； a a ( t + 1 ) = ia g ( t ) + 1 一( t + 1 ) + l ，如果t + 1 时刻服务完成 、 为了构造一个与a g ( ) 有关的的马尔可夫链，我t f g l 进一些与到达位相和服务过程 相关的附加变量引进附加变量分情况i - i - i 仑如下： ( 1 ) a g ( t ) 0 时，我们引进三个附加变量l ( ) ，j ( ) ，l ( t ) 我们由a g ( t ) 0 可得，此时系统为空，下一个顾客批还需要一a g ( t ) 个时刻才能到达我们由马尔 可夫链 矗，n2o ) 来定义厶( ) ，l ( t ) = 矗，如果第n 个顾客批为将要接受服 务的顾客批，那么l ( t ) 表示将要达到的顾客批到达系统时半马尔可夫链的状态， j ( t ) ，l ( ) 则分别表示这个顾客批的类型和其初始服务位相。 ( 2 ) a g ( t ) 20 时，我们仍引进三个附加变量：l ( ) ，( ) ，厶( t ) 因为这个时 候系统中有顾客存在，那么1 0 ( t ) = 矗，如果第n 个顾客批为正在接受服务的顾客 1 2 笙三皇兰丝【丝丝【丝! 里! 堕壁坠墨竺 批，那么厶( ) 表示正在接受服务的那个顾客批到达系统时半马尔可夫链的状态， j ( t ) ，l ( t ) 则分别表示正在接受服务的那个顾客批的类型和在t 时刻的服务位相 可以看到，虽然在 z + 1 时， 这个概率是零根据从一个年龄到另一个年龄的转移，以及每一个年龄马尔科夫链的 附加变量的取值范围，可得矩阵只的每个矩阵块元素都为( m 。m “) ( m 。m “) 维 ( 1 ) 当a g ( t ) = z ，z s 一1 时，此时系统中为空，下一批顾客还要经过一z 个 时刻才能到达，在t - f1 时刻，顾客批要么还没有到达，要么刚到达系统开始接受 服务，但至少能肯定这个顾客批没有服务完离开系统那么应该有( ) 随时间应 该增加1 ，而厶( t ) ，l 0 + 1 ) 都是指将要到达的这个顾客批到达系统时半马尔可夫 链的状态，j ( ) ，j ( t + 1 ) 都是表示这个顾客批的类型，h ( 0 ，l 0 + 1 ) 也都表示其 1 4 第二章 s m k p h k i 1 f c f s 排队系统 初始服务位相于是，当( t ) = z ，zs - 1 时 p a 9 ( + 1 ) = ，d 0 + 1 ) = j 7 ，j ( t + 1 ) = ，l o + 1 ) = i i ( ) = 一1 ，l ( t ) = j ，j ( t ) = z 厶( t ) 一磅 r i1 ，如果= 。+ 1 ，j = j 7 ，j = ，i = i = 10 ，否则 、 于是，由状态按字典排序以及只有当y = z + 1 ，j = j ，j = j 7 ，i = i 7 时概率为1 ， 则b = 厶。) 。( 。) ，而从( ) = z 转到其他年龄的概率都为零 ( 2 ) 当a g ( t ) = 墨z 三0 时，此时系统中至少有一个顾客批在接受服务，在 t + 1 时刻，这个顾客批可能继续接受服务，也可能服务完毕离开系统 如果t 时刻接受服务的顾客批在t + 1 时刻继续接受服务，此时转移矩阵块为 ao ，那么应该有： a g ( + 1 ) = z + 1 ，而厶( z ) ，i o ( t + 1 ) 都是指这个顾客批到达系统 时半马尔可夫链的状态，j ( ) ，j ( t + 1 ) 都足表示这个顾客批的类型，但是厶( t ) 表 示t 时刻的服务位相，l 0 + 1 ) 表示t + 1 时刻的服务位相，这两者的变化由服务 位相的转移矩阵决定于是， p ( ( + 1 ) = z + 1 ，i a ( t + 1 ) = j 7 ，d ( t + 1 ) = j ，l ( + 1 ) = i ( t ) = z ，厶( ) = j ，j ( t ) = z 厶( ) = z = h n 篓：2 ，j = 了7 z 4 a o = a j 1a j ” a ：1 m 。 a i 1a ：一a i ”。 a 孑“，1a ：2 - - a 孑。”。 簦三皇兰丝! 丝! ! 丝l 丝j ! ! 竺兰兰堡坠墨堡 1 5 其中鸯( 1s ，jsm 。) 为维数为m t “m 的矩阵子块分析每个a ，由( 2 4 ) 以及2 k 定义有： a 扩： 忙工1 一 s 以 d 吃 o 0 n d m l | a 第三章 s m k i p h k i 2 f c f s 排队系统 3 1系统介绍 跟前面一个服务台一样，排队系统有k 个类型的顾客( 其中k 为正整数) ，所有 的顾客都加入个队列，采取“先到先服务。的规则但由两个服务台进行服务， 并且假定同一批中的顾客由同一个服务台进行服务 3 1 1 顾客的到达过程 两个服务台的排队系统的到达过程与一个服务台是一样的，过程分析见2 1 i 3 1 2顾客的队列过程 一个顾客批到达后，所有的顾客根据在批中的顺序加入队列中所有的批采取 “先来先服务”的方式由两个服务台进行服务并且假定同一批顾客由同一个服务 台进行服务，对每一批顾客来说，顾客按他们在批中的顺序依次服务令q ( t ) 为t 时刻队列中顾客类型的数列串，它可以由在t 一1 时刻可能完成服务的顾客和到达 的顾客得到如果q ( t ) = j 。如矗，那么系统中在t 时刻有n 个顾客， 类型顾 客在一个服务台接受服务，两另一个服务台的情况分析有： ( 1 ) 若口( ) 正好为一个批的顾客，则另一个服务台为空五类型顾客为第一个 在排队等候的顾客，矗类型顾客为最后一个排队等侯的顾客这n 个顾客 将按照j - ，如，a 的顺序接受服务 ( 2 ) 若q ( ) 中顾客所属批的个数大于1 ，即：j - 如五为一个批，扎1 j 冲2 a 为第二个批，则盔+ l 类型的顾客在另个服务台接受服务并且第个服务 台按照j - 如五的顺序服务，第二个服务台按照 + - 五+ 2 靠的顺序服务 如果接着一个。，类型的顾客批到达，那么队列将变为g ( ) + j 如果接着一个 顾客完成了服务，假定为类型为j t 的顾客，那么队列将变为五，矗，- 一，矗，并且虎 类型顾客开始接受服务此时，五必须与j l 同属一个批否则这个服务台将对如 后面第1 个与矗不同属一个批的顾客进行服务，当然，如果如后面的顾客与如都 同属一个批，则这个服务台此时为空 1 8 笙三皇兰! ! i 丝! 里 丝3 丝旦兰壁坠墨丝 3 1 3服务时间 两个服务台的排队系统的服务时间与一个服务台是一样的，分析见2 1 3 那么根据顾客批的到达速率和服务速率，两个服务台排队系统的交通强度为 1 1 1 1 1 p = 沁( 2 p ，) = ；a ，e ( ) = ；( z 南) e ( 轧) j e r j r2 2 l。j rk 。1 f 3 1 ) = ；h j n c j , k ) e ( 船) = ；a 一k = lj k一七= 1 为了系统的稳定性我们假定p 1 3 1 4服务时间顾客批的实等待时间 令为第n 个顾客批到达后第个服务台的剩余工作时间( 即第k 个 服务台在第n 个顾客批到达后还需多长时闻轮到第n 个顾客批服务) 记w n = ( w 蚶，“k ，2 ) ，其中w n ，l 。，2 ，则服务台的标记1 ，2 是可以改变的，随着其剩 余工作时间的变化而变化那么，我们应有： 叫。+ l = o ( ( 叫。1 + 8 一+ 1 ) + ，( w n ，2 7 k + 1 ) + ) ，n 0 其中，矿= m a x o ，。1 ，o ( y ) 表示将n i l l9 的两个元索按非降的顺序重新排列得到 的新的向量，+ i 表示第n 个顾客批和第n + 1 个顾客批到达的间隔时间，。厶是 第n 个顾客批的类型，5 上是第”个顾客批的服务时间于是，”n l 为第n 个顾 客批的实等待时问，并且有 w n + 1 1 = m i n ( w n ，1 + s 一7 k + 1 ) + ，( w n 2 一十1 ) + ) 3 ，2广义的年龄过程的分析 对于两个服务台，年龄分析比一个服务台显然要复杂一些，每个服务台都可能 有个顾客批，每个顾客批都有一个年龄当然分析每个正在接受服务的顾客批的 年龄肯定能像一个服务台那样能分析系统的其他指标，但足那样会增加计算的复杂 性，关于年龄过程的马尔可夫过程维数很高，所以我们必须对系统分析清楚，从中 找出一个有利于分析系统其他指标的年龄过程，降低计算的复杂性 苎三兰兰丝i 丝! ! 里【丝j 丝! 竺! 兰堡坠墨丝 1 9 参考【12 】，我们可以考虑正在服务的两个顾客批中年龄较小的那个顾客批，记 t 时刻的它为系统的年龄a g ( t ) 那么当a g ( t ) 20 ，系统出于繁忙期( 即两个服务台 都有顾客批接受服务) ，此时系统中至少有两个顾客批当a g ( t ) 0 时，那么系统 中至少有一个服务台为空，即系统中至多有一个顾客批，那么a g ( t ) 为t 时刻之后 第个到达系统的顾客批的年龄这个顾客批还要一( ) 个时刻才能到达系统 我们记n ( t ) = n 为t 时刻a g ( t ) 为第n 个顾客批的年龄 我们来分析一下这个年龄过程 ( ) ，t 之o ) ： 当a g ( t ) 0 ，那么在t + 1 时刻 1 当两个顾客批都未完成服务，则有n ( t + 1 ) = u ( t ) ，于是a g ( t + 1 ) = ( ) + 1 ； 2 当有一个顾客批完成服务，另一个顾客批继续接受服务， ( a ) 等待的一个顾客批开始接受服务，则有( + 1 ) = n ( t ) + 1 ，于是 ( + 1 ) = a g ( t ) + 1 一t w ( t ) + 1 ； ( b ) 系统中没有等待的顾客批，则有( f + 1 ) = n ( t ) + 1 ，于是a g ( t + 1 ) = a g ( t ) + 1 一 r n ( o + i ； 3 当两个顾客批都完成服务离开了系统， ( a ) 系统中等待的两个顾客批开始接受服务，则有n ( t + 1 ) = l v ( t ) + 2 ， 于是a g ( t + 1 ) = a g ( t ) + 1 一r c t ) + l t n c t ) + 2 ； ( b ) 等待的一个顾客批接受服务，而另一个顾客批还未到达系统，则有0 + 1 ) = n ( t ) + 2 ，于是a g ( t + 1 ) = ( ) + 1 一r n ( o + l 一1 ( t ) + 2 ； ( c ) 系统中没有等待的顾客批，此时顾客批都还没有到达系统，则有( t + 1 ) = ( ) 4 - 1 ，于是a g ( t + 1 ) = a g ( t ) + 1 一r n ( o + 1 当a g ( t ) 0 且系统中只有个顾客批时，那么在+ 1 时刻： 2 0 笙三童兰! ! 丝! 坚f 丝! ! ! g 兰兰篓坠墨篓 1 当t 时刻接受服务的顾客批未完成服务，则有n ( t + 1 ) = n ( t ) ，于是 + 1 ) = ( ) + 1 ； 2 当t 时刻接受服务的顾客批完成服务离开系统， ( a ) 第n ( t ) 个顾客批还没有到达系统，则有p + 1 ) = n ( t ) ，于是a g ( t + 1 ) = ( ) + 1 ； ( b ) 第g ( t ) 个顾客批正好到达系统，则有n ( t + 1 ) = n ( t ) + 1 ，于是 ( t + 1 ) = a g ( t ) + 1 一r ( t ) + 1 当( ) 0 且系统中没有顾客批时，那么在t + 1b f 麴j ： 1 第n ( t ) 个顾客批正好到达系统，则有( + 1 ) = ( ) + 1 ，于是( + 1 ) = ( ) + 1 一t n ( t ) q - 1 ； 2 第n ( t ) 个顾客批还没有到达系统，则有( + 1 ) = n ( t ) ，于是( + 1 ) = ( t )