重庆大学：《通信网络中的排队论基础》研究生课程（讲义）第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。 其次考虑0<j≤i+1的情形。 注意到j>0意味着当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 的任意性，并根据概率的可加性我们得到：