重庆大学：《通信网络中的排队论基础》研究生课程讲义_第5章 GMm排队模型

目录 第5章G/M/m排队模型 51嵌入马尔柯夫链的转移概率 52G/M/1系统中的顾客数分布 53G/M/1系统的等待时间分布 54G/M/m排队系统

目 录 第 5 章 G / M / m 排队模型 5.1 嵌入马尔柯夫链的转移概率 5.2 G / M / 1系统中的顾客数分布 5.3 G / M / 1系统的等待时间分布 5.4 G / M / m 排队系统

第5章G/M/m排队模型 在第4章中我们研究了属于非马尔柯夫过程的M/G/1排队系统,它具有泊松过程 到达和服从任意概率分布的服务时间。这一章我们研究与M/G/l系统相对应的G/M/1 排队系统。在G/M/1系统中,服务时间服从负指数分布,而到达间隔时间的概率分布 可以为任意分布。我们把这个间隔时间分布记作a(),其平均到达率仍用表示。 对G/M/1系统的研究可以很容易地直接推广到G/M/m,即多服务者系统。研究 方法仍然采用嵌入马尔柯夫链。 51嵌入马尔柯夫链的转移概率 G/M/排队系统的分析与M/G/排队系统的分析非常类似。系统的状态描述也必 须是一个二维向量[N(),x0(O),其中N()说明系统中的顾客数,而x0()说明从上一 次顾客到达到现在已经过去了多少时间,因为我们给定的a()不再是无记忆的,故下 个顾客的到来与X0()是有关的。 为了把这个二维状态描述转换为一维状态描述,我们仍然采用嵌入马尔柯夫链的方 法。这里,关键问题是要选择适当的一组观察系统状态的时间点,即嵌入点,使得我们 在说明系统中的顾客数N()的同时,就隐含说明了X0() 我们选择顾客到达系统的瞬时作为嵌入点,在这些点上观察系统的变化,或者说, 我们只有在这些点上才考虑状态的转移。很明显,在这些时间点上X0()等于0,即上 次顾客到达到现在已经过去了的时间为0,因为该顾客才刚刚到达。这样,只要在嵌入 点上说明了系统中的顾客数,就隐含地说明了X0()。因此,我们定义 qn:第n个顾客到达前的瞬时系统中的顾客数 vn:在Cn和Cn的到达间隔时间内系统服务完毕的顾客数。 由定义可知,qn序列形成了一个离散马尔柯夫链,状态的转移发生在Cn到达的瞬 时,此时系统中的顾客数不包括Cn。在Cn与C1的到达间隔内,接受服务完毕并离开 系统的顾客数为vn图1给出了描述qn、Cn和vn之间关系的时间图 529

529 第 5 章 GMm / / 排队模型 在第 4 章中我们研究了属于非马尔柯夫过程的M / /1 G 排队系统，它具有泊松过程 到达和服从任意概率分布的服务时间。这一章我们研究与M / /1 G 系统相对应的G M/ /1 排队系统。在G M/ /1系统中，服务时间服从负指数分布，而到达间隔时间的概率分布 可以为任意分布。我们把这个间隔时间分布记作a t  ，其平均到达率仍用 表示。 对G M/ /1系统的研究可以很容易地直接推广到GMm / / ，即多服务者系统。研究 方法仍然采用嵌入马尔柯夫链。 5.1 嵌入马尔柯夫链的转移概率 G M/ /1排队系统的分析与M / G /1排队系统的分析非常类似。系统的状态描述也必 须是一个二维向量   0   Nt X t ,   ，其中 N t  说明系统中的顾客数，而 X  t 0 说明从上一 次顾客到达到现在已经过去了多少时间，因为我们给定的t不再是无记忆的，故下一 个顾客的到来与 X  t 0 是有关的。 为了把这个二维状态描述转换为一维状态描述，我们仍然采用嵌入马尔柯夫链的方 法。这里，关键问题是要选择适当的一组观察系统状态的时间点，即嵌入点，使得我们 在说明系统中的顾客数 N t  的同时，就隐含说明了 X t 0 。 我们选择顾客到达系统的瞬时作为嵌入点，在这些点上观察系统的变化，或者说， 我们只有在这些点上才考虑状态的转移。很明显，在这些时间点上 X  t 0 等于0 ，即上一 次顾客到达到现在已经过去了的时间为0 ，因为该顾客才刚刚到达。这样，只要在嵌入 点上说明了系统中的顾客数，就隐含地说明了 X t 0 。因此，我们定义： n q ：第n 个顾客到达前的瞬时系统中的顾客数。 n 1 v  ：在Cn 和Cn1的到达间隔时间内系统服务完毕的顾客数。 由定义可知， n q 序列形成了一个离散马尔柯夫链，状态的转移发生在Cn 到达的瞬 时，此时系统中的顾客数不包括Cn 。在Cn 与Cn1的到达间隔内，接受服务完毕并离开 系统的顾客数为 n 1 v  。图 5.1 给出了描述 n q 、Cn 和 n v 之间关系的时间图

离去 服务 排队 图5.1嵌入马尔柯夫链 根据 的定义我们立即可以写出 (5.1) 我们关心的是这个嵌入马尔柯夫链的转移概率,首先定义: P=P (52) B的意义是:在C到达时发现系统中有个顾客的条件下,Cn1到达时发现系统中 有j个顾客的概率。显然,这个概率也就等于在这两次到达之间系统完成对i+1-j个 顾客服务的概率。 G/M/系统的状态概率图如图52所示。 P1-1 P 图52G/M/1系统的状态转移概率图 注意图52画的是转移概率图,而不是转移图。图中我们仅仅把状态的转移过程画 出来了,而没有画出其它状态的转移。 现在的任务是要计算P。首先注意到,在两次状态转移之间系统中到达的顾客数多 增加了一个,在两次到达之间有顾客服务完毕离开排队系统,j肯定比i+1小,即j>i+1 是不可能的。只有当在Cn与Cn1到达间隔时间内没有顾客的服务完成时才有j=+1

530 排队 Cn  Cn1 qn qn1 服务 Cn1 n1 v t t 离去 图 5.1 嵌入马尔柯夫链 根据 n q 、 n 1 v  的定义我们立即可以写出： 1 1 1 nn n qq v      （5.1） 我们关心的是这个嵌入马尔柯夫链的转移概率，首先定义： P P q jq i ij n n  1      （5.2） Pij 的意义是：在Cn 到达时发现系统中有i 个顾客的条件下，Cn1到达时发现系统中 有 j 个顾客的概率。显然，这个概率也就等于在这两次到达之间系统完成对i 1 j 个 顾客服务的概率。 G M/ /1系统的状态概率图如图 5.2 所示。 i 0 p  ii2 p i1 p pii ii1 p  ii1 p 图 5.2 G / M /1系统的状态转移概率图 注意图 5.2 画的是转移概率图，而不是转移图。图中我们仅仅把状态的转移过程画 出来了，而没有画出其它状态的转移。 现在的任务是要计算 Pij 。首先注意到，在两次状态转移之间系统中到达的顾客数多 增加了一个，在两次到达之间有顾客服务完毕离开排队系统，j 肯定比i 1小，即 j  i 1 是不可能的。只有当在Cn 与Cn1到达间隔时间内没有顾客的服务完成时才有 j  i 1

因此,P=0,j>i+1。 其次考虑00意味着当C到达系统时系统中至少还有一个顾客,因而在Cn到Cn1的 到达间隔时间内服务者始终处于忙状态。根据前面我们对生灭过程的研究可知,服务时 间服从负指数分布、而服务者始终处于忙状态等效于一个“纯灭”过程,该过程服从泊 松分布。我们知道,对于“纯灭”过程来讲,在时间(0,)内离开系统的顾客数为的概率 n.=()c (53) k! 系统在状态转移中由状态i转到状态j,状态转移是在顾客的到达时间点上发生的, 在这个间隔时间内共有i+1-j个顾客接受了服务并离开系统,这个间隔时间分布密度函 数为a(t) 根据全概率定律,我们可以把P写成 P=[p+1-个顾客服务完毕,服务时间为 (54) 再根据条件概率公式可得 P=[p+1-个顾客服务完毕服务时间为 (5.5) 其中 吨+1-)个顾客服务完毕服务时间为]=(my" (56) 将(56)式代入(55)式,得: lat 0<j≤i+1 (57) j=0的情况比较复杂,它意味着当Cn到达时,系统中没有顾客。这就是说,在Cn 与Cn的到达间隔时间以内,系统已经将所有+1个顾客的服务进行完毕。必须注意到, 系统完成对i+1个顾客所用的时间并不恰好就是C和Cn1的到达间隔时间,而可能小于 这个时间,这样在这个间隔时间的后半段时间内,服务者可能是空闲的。因此,系统在 这个间隔时间中的特性并不能用“纯灭”过程来描述,而必须考虑更多的因素,由于数

531 因此， 0 Pij  ， j  i 1。 其次考虑0 1   j i 的情形。 注意到 j  0 意味着当Cn1到达系统时系统中至少还有一个顾客，因而在Cn 到Cn1的 到达间隔时间内服务者始终处于忙状态。根据前面我们对生灭过程的研究可知，服务时 间服从负指数分布、而服务者始终处于忙状态等效于一个“纯灭”过程，该过程服从泊 松分布。我们知道，对于“纯灭”过程来讲，在时间0,t内离开系统的顾客数为的概率 为：   ! k t k t p e k    （5.3） 系统在状态转移中由状态i 转到状态 j ，状态转移是在顾客的到达时间点上发生的， 在这个间隔时间内共有i j  1 个顾客接受了服务并离开系统，这个间隔时间分布密度函 数为a t  。 根据全概率定律，我们可以把 Pij 写成：        0 P P i 1 j t dt ij 个顾客服务完毕，服务时间为 （5.4） 再根据条件概率公式可得：          0 P p i 1 j | t t dt ij 个顾客服务完毕 服务时间为  （5.5） 其中       t i j e i j t p i j t          1 ! 1 | 1 个顾客服务完毕 服务时间为 （5.6） 将（5.6）式代入（5.5）式，得：               0 1 1 ! e t dt i j t P t i j ij    0 1  j  i （5.7） j  0 的情况比较复杂，它意味着当Cn1到达时，系统中没有顾客。这就是说，在Cn 与Cn1的到达间隔时间以内，系统已经将所有i 1个顾客的服务进行完毕。必须注意到， 系统完成对i 1个顾客所用的时间并不恰好就是Cn 和Cn1的到达间隔时间，而可能小于 这个时间，这样在这个间隔时间的后半段时间内，服务者可能是空闲的。因此，系统在 这个间隔时间中的特性并不能用“纯灭”过程来描述，而必须考虑更多的因素，由于数

学推导比较复杂,而且在以后的分析中我们也不使用这个结果,因此对于j=0时的P我 们不作推导,只给出最后的表达式 P (1-e"t-m)ud a()dr (58) 0(-1) 如果我们定义 bil- 0<j≤i+1 (59) 则B4表示:在两次到达间隔时间内有k个顾客服务完毕离开系统且服务者始终处于 忙状态的概率。 在(57)式中令1+1-j=k,则有: B a(t (5.10) 转移概率矩阵P=IP],(i,j=0,1,2,…)可写成为 P0B00000 Po Pl P200 0 Pio B. Bo0 0 0 P P20P21P2P200 P20B2B1B000 Po P3I P2 P3 P34 0.P3o B3 B2 P. Bo 0 Pal P2 P P4 Pt P40 B4 B, B2 B. Bo 52G/Mn系统中的顾客数分布 现在我们来推导G/M/排队系统中顾客数的概率分布。与前面几章一样,我们也 只考虑系统的平衡解,即系统经过很长时间的工作达到平衡状态后的概率分布,为此, 首先定义: =lim Plam =il (5.11) r:当Cn到达系统时发现系统中有个顾客的概率。 我们先推导一个顾客数的平衡概率分布与转移概率的关系式。 如果当Cn到达系统时系统中有i个顾客,而当Cn1到达系统时系统中有k个顾客, 根据条件概率公式,我们有: P[qn1=kn=小=P[qn=kn=]P[9n=小 (5.12) 注意到i的任意性,并根据概率的可加性我们得到:

532 学推导比较复杂，而且在以后的分析中我们也不使用这个结果，因此对于 j  0 时的 Pij 我 们不作推导，只给出最后的表达式：           1 0 0 0 1 1 ! i t y t y i y P e e dy a t dt i                     （5.8） 如果我们定义： i j ij  1  P 0 1  j  i （5.9） 则 k 表示：在两次到达间隔时间内有k 个顾客服务完毕离开系统且服务者始终处于 忙状态的概率。 在（5.7）式中令i jk   1 ，则有：   1   0 ! k k ii k t P a t dt k         （5.10） 转移概率矩阵 [ ] P p  ij ，（i ， j  0，1，2，）可写成为：                                                                      40 4 3 2 1 0 30 3 2 1 0 20 2 1 0 10 1 0 00 0 40 41 42 43 44 45 30 31 32 33 34 20 21 22 23 10 11 12 00 01 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0                P P P P P P P P P P P P P P P P P P P P P P P P P P Pij 5.2 G M/ /1系统中的顾客数分布 现在我们来推导G M/ /1排队系统中顾客数的概率分布。与前面几章一样，我们也 只考虑系统的平衡解，即系统经过很长时间的工作达到平衡状态后的概率分布，为此， 首先定义： r Pq i n n i    lim （5.11） ir ：当Cn 到达系统时发现系统中有i 个顾客的概率。 我们先推导一个顾客数的平衡概率分布与转移概率的关系式。 如果当Cn 到达系统时系统中有i 个顾客，而当Cn1到达系统时系统中有k 个顾客， 根据条件概率公式，我们有： P q kq i P q kq i P q i  n n nn n   1 1        ,      （5.12） 注意到i 的任意性，并根据概率的可加性我们得到：

qn=k]=∑P[qn ∑P[qn=kn=]P[9= ∑PP[qn=小 (5.13) 在上式中令n→∞,得: =∑P (5.14) (514)式说明了r与P的关系,如果我们令 r (5.15) P (5.16) 则(5.14)式可用矩阵形式表示为: (5.17) 现在来求r: ∑ 由于当k>1+1时P=0,故 =∑P (5.18) 将(57)式用于(5.18)式,得 i+1-k () ( dt 0(+1-k) (n) Fn+ (5.19) n! 直接求解(519)式是比较困难的,我们可以采用试凑的方法寻找满足(519)式 的表达式。 假设:F 代入(5.19)式,得 533

533    1 1 0 , n nn i Pq k Pq kq i         1   0 nn n i P q kq i P q i              0 ik n i PPq i      （5.13） 在上式中令n  ，得： 0 k ik i i r Pr     （5.14） （5.14）式说明了 kr 与 Pik 的关系，如果我们令 r rr r   1 2 ,, ,,  k  （5.15） P pij      （5.16） 则（5.14）式可用矩阵形式表示为： r rP  （5.17） 现在来求 kr ： 0 k ik i i r Pr     由于当k i  1时 0 Pik  ，故 1 k ik i i k r Pr      （5.18） 将（5.7）式用于（5.18）式，得：       1 0 1 1 ! i k t k i i k t r r e a t dt i k                 1   0 0 ! n t n k n t r e a t dt n            （5.19） 直接求解（5.19）式是比较困难的，我们可以采用试凑的方法寻找满足（5.19）式 的表达式。 假设： k 1 kr C   （5.20） 代入（5.19）式，得：

Co2=∑co" Ar (odr (521) 两边同时消去Ca-1后,上式成为 O nso 由此得 ()dt=∫ Do a( e-tw-wo)dt= a(u-Hoo) 其中: A(s)=a(t)e"dt A(s)为到达间隔时间的概率分布密度函数a()的拉普拉斯变换式。 为确定(5.20)式中的常数C,利用概率的归一化条件∑=1得: 因而 C=(1-) (525) 最后,我们得到了r的表达式: k=(1-o)o (526) 例:对于M/M/排队系统有a(t)=e 对应的拉普拉斯变换式为 A(s) 用(522)式求O,得:

534     1 2 0 0 ! n k nk t n t C C e a t dt n                  1 1 0 0 ! n kn t n t C e a t dt n             （5.21） 两边同时消去 k 1 C  后，上式成为：     0 0 1 1 ! n n t n t e a t dt n            由此得 ：     0 0 ! n t n t e a t dt n             0 t t e e a t dt           0 t a t e dt          A    即   A     （5.22） 其中：    0 st A s a t e dt     （5.23） A s  为到达间隔时间的概率分布密度函数a t  的拉普拉斯变换式。 为确定（5.20）式中的常数C ，利用概率的归一化条件 0 1 k k r     得：   1 0 1 1 k k C C          （5.24） 因而 C  1 （5.25） 最后，我们得到了 kr 的表达式： 1  k kr    （5.26） 例：对于M M/ /1排队系统有   t at e     对应的拉普拉斯变换式为： A s  s     用（5.22）式求 ，得：

A(4-) -O+2 或 =0 该方程有两个根:=1和O=,根据前面的讨论可知:0<O<1,故仅有O=二是 合理的根。 由此有:对于M/M/1系统, 53G/M/系统的等待时间分布 对于G/M/1排队系统,其服务时间分布为负指数分布,分布密度函数表达式为 b(x) x≥0 (527) 现在我们研究一个到达顾客在得到服务以前的等待时间分布密度函数(y)。 当一个顾客到达系统时,若系统中已有k个顾客,则它必须在前k个顾客均离开系 统后才能得到服务。它的等待时间就是前k个顾客的服务时间的总和。若令Z为该顾客 的等待时间,X为第i个顾客的服务时间,则有 z=∑X 我们已经知道,X为独立同分布的随机变量,且分布函数服从负指数分布。因而zk 的概率密度函数为k个负指数分布概率密度函数的卷积 设等待时间Z的概率分布密度函数为二4(y) 为计算方便起见,我们在s域内进行推导 令 Z:(s)==(v)e""dy B(s)=b(x)e"dx (5.30) 因为b(x)=ue

535 A             或   2         0 该方程有两个根： 1和     ，根据前面的讨论可知：0 1   ，故仅有     是 合理的根。 由此有：对于M M/ /1系统，         1 k kr     5.3 G M/ /1系统的等待时间分布 对于G M/ /1排队系统，其服务时间分布为负指数分布，分布密度函数表达式为：   x bx e     x  0 （5.27） 现在我们研究一个到达顾客在得到服务以前的等待时间分布密度函数 z y  。 当一个顾客到达系统时，若系统中已有k 个顾客，则它必须在前k 个顾客均离开系 统后才能得到服务。它的等待时间就是前k 个顾客的服务时间的总和。若令Zk 为该顾客 的等待时间， Xi为第i 个顾客的服务时间，则有：   k i Zk Xi 1 （5.28） 我们已经知道，Xi为独立同分布的随机变量，且分布函数服从负指数分布。因而Zk 的概率密度函数为k 个负指数分布概率密度函数的卷积。 设等待时间Zk 的概率分布密度函数为 z y k 。 为计算方便起见，我们在s 域内进行推导。 令    0 sy Zk k s z y e dy     （5.29）   0 sx B s b x e dx     （5.30） 因为   x bx e     x  0

所以B(s) (5.31) S+ 由于时域内的卷积等于S域内的乘积,故 (5.32) 其中下标k表示当系统中有k个顾客时,到达顾客的等待时间概率分布密度为 因而 2()=4()=s-0)b =(-o)-c2 (533) 求反变换,得: )=(1-) (534) 这就是G/M/排队系统的等待时间分布密度函数 54G/M/m排队系统 对于G/M/排队系统的分析可以很容易地推广到G/M/m排对系统,即多服务者 系统。对于这样一个系统,我们往往更关心系统中排队等待的顾客数和顾客等待时间 因此,在这一节中,我们只推导在某种条件下排队等待顾客数和顾客等待时间的概率分 布。给定的条件是:当顾客到达系统时,发现系统中的m个服务者均处于忙状态,该顾 客必须排队等待,而不能直接得到服务,顾客的等待时间必大于0。 令 Q:排队等待的顾客数;W:顾客的等待时间 我们需要求的概率分布是: 排队等待的顾客数的概率分布P=k>刂 顾客等待时间的概率分布密度函数wy>0)=pbvs>] 以下我们分几个步骤来推导这两个条件概率分布。 1、首先从P的计算开始。我们只计算与后面的分析有关的那部分P表示式,即只

536 所以 B s  s     （5.31） 由于时域内的卷积等于Ｓ域内的乘积，故   k k Z s Bs k s                （5.32） 其中下标 k 表示当系统中有 k 个顾客时，到达顾客的等待时间概率分布密度为 z y k   。 因而，   1 k k k Z s rZ s       1 1 k k k s                   1 s         （5.33） 求反变换，得：     1  1 y zy e         （5.34） 这就是G M/ /1排队系统的等待时间分布密度函数。 5.4 GMm / / 排队系统 对于G M/ /1排队系统的分析可以很容易地推广到GMm / / 排对系统，即多服务者 系统。对于这样一个系统，我们往往更关心系统中排队等待的顾客数和顾客等待时间。 因此，在这一节中，我们只推导在某种条件下排队等待顾客数和顾客等待时间的概率分 布。给定的条件是：当顾客到达系统时，发现系统中的m 个服务者均处于忙状态，该顾 客必须排队等待，而不能直接得到服务，顾客的等待时间必大于 0。 令 Q ~ ：排队等待的顾客数；W ：顾客的等待时间。 我们需要求的概率分布是： 排队等待的顾客数的概率分布  0 ~ P Q  k W  ； 顾客等待时间的概率分布密度函数 zyW  0  Pw  yW  0。 以下我们分几个步骤来推导这两个条件概率分布。 1、首先从 Pij 的计算开始。我们只计算与后面的分析有关的那部分 Pij 表示式，即只

考虑m≤j≤i+1 注意到j≥m意味着在两次顾客到达的间隔时间内m个服务者均处于忙状态。由于 每个服务者的服务时间分布都是负指数分布,因而在这个间隔时间内,系统的特性与 个具有服务率为m的纯灭过程完全相同。这样一个纯灭过程在时间区间(0,1)内完成k 个顾客服务的概率为: Pk 在两次顾客到达的间隔区间中,共有+1-j个顾客完成了服务。这个间隔时间分布 密度函数为a()。 采用(5.3)到(57)式完全相同的推导,我们可得 (mut) emga(o) m<j≤i+1 (536) (+1-) 2、下一步推导G/Mm系统的顾客数概率表达式,即求r。显然,对于多服务者 系统,(5.17)式仍然是成立的,即有 (538) 或 =∑P 将P的表达式(536)代入上式,得 m a10(+1- "(mut) +1-k a(tdt 仍然采用试凑法,假设 k≥m-1 (541) 代入(540)式中,经推导后可得到O的计算式 537

537 考虑m ji  1。 注意到 j  m 意味着在两次顾客到达的间隔时间内m 个服务者均处于忙状态。由于 每个服务者的服务时间分布都是负指数分布，因而在这个间隔时间内，系统的特性与一 个具有服务率为m 的纯灭过程完全相同。这样一个纯灭过程在时间区间  0，t 内完成k 个顾客服务的概率为：   ! m t k m t p e k     （5.35） 在两次顾客到达的间隔区间中，共有i j 1 个顾客完成了服务。这个间隔时间分布 密度函数为a t  。 采用（5.3）到（5.7）式完全相同的推导，我们可得：       1 0 1 i j m t ij m t P e a t dt i j           m ji   1 （5.36） 2、下一步推导GMm / / 系统的顾客数概率表达式，即求 kr 。显然，对于多服务者 系统，（5.17）式仍然是成立的，即有： r rP  （5.38） 或 0 k ik i i r Pr     （5.39） 将 Pij 的表达式（5.36）代入上式，得：       1 0 0 1 ! i k m t k i i m t r r e a t dt i k                    1 0 1 1 ! i k m t i i k m t r e a t dt i k                 1   0 0 ! n m t n k n m t r e a t dt n            k m 1 （5.40） 仍然采用试凑法，假设 k m rk C    k m 1 （5.41） 代入（5.40）式中，经推导后可得到 的计算式：