重庆大学：《通信网络中的排队论基础》研究生课程（讲义）第4章 MG1排队模型.pdf_大学文库

第4章M/G/排队模型在第2章中我们讨论了各种各样的排队系统,它的基本特点是:系统的状态描述非常筒单,一旦说明了系统中的顾客数目,则整个过去的历史信息都已经被包含说明了。其服务时间的概率分布服从负指数分布,由于负指数分布的无记忆性,使我们不必说明当前正在接受服务的顾客已经花费了多少时间。同时我们还知道,系统的状态变量是个离散状态变量,它只能取有限个或可数个状态值。在第3章爱尔朗排队系统中,对于M/E/1排队系统,把服务时间服从r阶爱尔朗分布的服务过程分解为r个负指数“服务装置”,用扩大状态空间的方式,以系统中每个顾客需要经过“服务装置”级数总和作为随机变量,仍然使服务过程用一个马尔柯夫过程描述,这主要是通过每一个“服务装置”服从负指数分布的无记忆性所保证的。对于E/M/排队系统,把到达间隔时间服从r阶爱尔朗分布的到达过程分解为r个到达间隔时间服从负指数分布的到达过程,用扩大状态空间的方式,以系统所有顾客已经通过的总到达级数为随机变量,仍然使顾客到达过程用一个马尔柯夫过程描述,这主要是顾客通过每一个服从负指数分布的“到达装置”的无记忆性所保证的。现在我们将要研究另外一类排队系统,它们不再具有马尔柯夫特性,而只能用非马尔柯夫过程来描述,这种系统的状态描述比马尔柯夫系统更困难,我们必须寻找新的方法来处理。本章我们研究的排队系统是M/G/1排队系统模型,它的到达规律仍然是泊松过程 (即顾客相继到达系统的间隔时间服从参数为λ的负指数分布),但服务时间分布不再是负指数分布或r阶爱尔朗分布,而可以是任意形式的概率分布函数,即 Ja(t)=he-in t≥0 (4.1) lb(x)任意下面我们讨论M/G/1系统的状态描述方法。假定在某个时刻,我们希望概括出系统在t以前的全部历史,则必须首先说明在时刻t系统中的顾客数N(t),除此以外,还需说明当前正在接受服务的顾客已经接受服务的时间x(t),因为此时服务时间分布不再具有无记忆性,x()的值将会对下一次状态变化产生影响(注意:由于到达过程是马尔柯夫过程,故不必说明从最后一次顾客到达至时刻t已经过了多少时间)。因此,我们看到,随机过程N(t)不是一个马尔柯夫过程,因为它不能概括系统的全部历史,只有在附加说明了x()以后,二维随机过程N(tx1(才能概括系统的全部历史,所以这个二维

509 第 4 章 M /G /1排队模型在第 2 章中我们讨论了各种各样的排队系统，它的基本特点是：系统的状态描述非常简单，一旦说明了系统中的顾客数目，则整个过去的历史信息都已经被包含说明了。其服务时间的概率分布服从负指数分布，由于负指数分布的无记忆性，使我们不必说明当前正在接受服务的顾客已经花费了多少时间。同时我们还知道，系统的状态变量是一个离散状态变量，它只能取有限个或可数个状态值。在第 3 章爱尔朗排队系统中，对于 / /1 M Er 排队系统，把服务时间服从r 阶爱尔朗分布的服务过程分解为r 个负指数“服务装置”，用扩大状态空间的方式，以系统中每个顾客需要经过“服务装置”级数总和作为随机变量，仍然使服务过程用一个马尔柯夫过程描述，这主要是通过每一个“服务装置”服从负指数分布的无记忆性所保证的。对于 / /1 E M r 排队系统，把到达间隔时间服从r 阶爱尔朗分布的到达过程分解为r 个到达间隔时间服从负指数分布的到达过程，用扩大状态空间的方式，以系统所有顾客已经通过的总到达级数为随机变量，仍然使顾客到达过程用一个马尔柯夫过程描述，这主要是顾客通过每一个服从负指数分布的“到达装置”的无记忆性所保证的。现在我们将要研究另外一类排队系统，它们不再具有马尔柯夫特性，而只能用非马尔柯夫过程来描述，这种系统的状态描述比马尔柯夫系统更困难，我们必须寻找新的方法来处理。本章我们研究的排队系统是 M / G /1排队系统模型，它的到达规律仍然是泊松过程（即顾客相继到达系统的间隔时间服从参数为 的负指数分布），但服务时间分布不再是负指数分布或r 阶爱尔朗分布，而可以是任意形式的概率分布函数，即：          b x 为任意 a t e t  t  0 （4.1）下面我们讨论 M / G /1系统的状态描述方法。假定在某个时刻，我们希望概括出系统在t以前的全部历史，则必须首先说明在时刻t系统中的顾客数N(t)，除此以外，还需说明当前正在接受服务的顾客已经接受服务的时间X t 0 ，因为此时服务时间分布不再具有无记忆性，X   t 0 的值将会对下一次状态变化产生影响（注意：由于到达过程是马尔柯夫过程，故不必说明从最后一次顾客到达至时刻t已经过了多少时间）。因此，我们看到，随机过程N(t)不是一个马尔柯夫过程，因为它不能概括系统的全部历史，只有在附加说明了X0   t 以后，二维随机过程Nt，X0 t才能概括系统的全部历史，所以这个二维

随机过程才是一个马尔柯夫过程。现在,我们已经从初级排队论中的单变量状态描述过渡到中级排队论中的双变量状态描述,它们之间的差别是:在初级排队论中,只要给出在时刻t系统中的顾客数N(t)就可以完全描述该系统,且本身N(t)是有限的或可数的。而在M/G/1系统中,N(t)虽然是有限的或可数的,但X(t)的状态是一个连续函数,因此状态空间成了一个连续空间, 这就增加了分析的复杂性。 4.1嵌入马尔柯夫链 1、选取每个顾客离开系统的瞬时作为观察点为了简化M/G/排队系统的分析,我们希望寻求某种方法把系统的二维状态描述 N(tx(t)转化为一维状态描述,并且把连续状态空间转化为离散状态空间。可以设想这样一种方法:我们不明确给出在某个时刻t顾客已经接受到的服务时间,而是采用隐含的方式,在说明系统中顾客数Nt)的时候,把x。(t)的值隐含地包含在N(t)中。为此,我们不再在任意时刻t观察系统的状态,而在某些有选择的时间点上进行观察。这组有选择的时间点必须满足这样一个性质:若在这样一个时间点上我们说明了系统中的顾客数,并且提供了系统在这个点以后的顾客到达规律,则在下一个这种时间点上我们就可以直接计算出系统中的顾客数,因而实际上就隐含地给出了系统在这个时间点以前的全部历史信息这组时间点的选取方法可能有多种,最方便地一种是选取每个顾客离开系统的瞬时作为观察点。很明显,如果我们说明了当某个顾客离开系统的瞬时留在系统中的顾客数, 也就说明了系统中正在接受服务的顾客已经接受到的服务时间,此时X0(t)=0。因为系统只有一个服务者,上一个顾客离开系统的瞬间,下一个顾客刚刚进入服务,所以他已经接受服务的时间X0t)=0 2、每个顾客离开系统时系统内的顾客数定义为嵌入马尔柯夫链尽管M/G/1排队系统在时刻t系统中的顾客数N(t)不具有马尔柯夫过程的特性, 这是因为服务时间不具有无记忆性,顾客的剩余服务时间与原来服务时间分布不同,即剩余服务时间具有记忆性,从而系统未来的进程受以前状态的影响。但 Kendall经研究发现,对于M/G/1排队系统中t时刻的顾客数N(t)这一随机过程,存在一些特殊的时刻,在这些时刻上系统具有无记忆性。换言之,将这些特殊的时刻找出来,形成一个点

510 随机过程才是一个马尔柯夫过程。现在，我们已经从初级排队论中的单变量状态描述过渡到中级排队论中的双变量状态描述，它们之间的差别是：在初级排队论中，只要给出在时刻 t 系统中的顾客数 N(t)就可以完全描述该系统，且本身 N(t)是有限的或可数的。而在 M / G /1系统中， N(t)虽然是有限的或可数的，但X  t 0 的状态是一个连续函数，因此状态空间成了一个连续空间，这就增加了分析的复杂性。 4.1 嵌入马尔柯夫链 1、选取每个顾客离开系统的瞬时作为观察点为了简化 M /G /1排队系统的分析，我们希望寻求某种方法把系统的二维状态描述   N  t，X t0 转化为一维状态描述，并且把连续状态空间转化为离散状态空间。可以设想这样一种方法：我们不明确给出在某个时刻t 顾客已经接受到的服务时间，而是采用隐含的方式，在说明系统中顾客数 N(t)的时候，把X t 0 的值隐含地包含在 N(t)中。为此，我们不再在任意时刻t观察系统的状态，而在某些有选择的时间点上进行观察。这组有选择的时间点必须满足这样一个性质：若在这样一个时间点上我们说明了系统中的顾客数，并且提供了系统在这个点以后的顾客到达规律，则在下一个这种时间点上我们就可以直接计算出系统中的顾客数，因而实际上就隐含地给出了系统在这个时间点以前的全部历史信息。这组时间点的选取方法可能有多种，最方便地一种是选取每个顾客离开系统的瞬时作为观察点。很明显，如果我们说明了当某个顾客离开系统的瞬时留在系统中的顾客数，也就说明了系统中正在接受服务的顾客已经接受到的服务时间，此时X (t) 0 0  。因为系统只有一个服务者，上一个顾客离开系统的瞬间，下一个顾客刚刚进入服务，所以他已经接受服务的时间X (t) 0 0  。 2、每个顾客离开系统时系统内的顾客数定义为嵌入马尔柯夫链尽管M / G /1排队系统在时刻t系统中的顾客数N(t)不具有马尔柯夫过程的特性，这是因为服务时间不具有无记忆性，顾客的剩余服务时间与原来服务时间分布不同，即剩余服务时间具有记忆性，从而系统未来的进程受以前状态的影响。但 Kendall 经研究发现，对于 M / G /1排队系统中t 时刻的顾客数N(t)这一随机过程，存在一些特殊的时刻，在这些时刻上系统具有无记忆性。换言之，将这些特殊的时刻找出来，形成一个点

列t,t2,…,t,…,则离散参数的随机变量序列{N(n),n∈N={0.2,,}为一个马尔柯夫链。由于对于这种时刻,系统就好像重新开始一样,其未来状态完全由此时刻系统所处的状态决定,且与以前系统处于什么状态无关,因此,称这种时刻为再生点, 而称离散参数的随机变量序列{(4,n∈N={02,}为嵌入马尔柯夫链。再生点就是各个顾客服务结束离开系统的瞬时。实际上,我们描述的是一个半马尔柯夫过程,它的状态转移仅发生在顾客离开系统的瞬时,在这样一些时间点上,系统的特性是符合马尔柯夫特性的,而在其余时间点上, 系统又具有非马尔柯夫特性。我们把每个顾客离开系统时系统内的顾客数定义为嵌入马氏链,状态的转移只在这些嵌入点上进行且状态空间为离散空间。两次状态转移的间隔时间分布为:若前次顾客离开系统时系统内至少还有一个顾客,则间隔时间分布为服务时间分布;若前次顾客离开系统时系统为空,则间隔时间为到达间隔时间(注意它的无记忆性)加上服务时间,故状态转移的间隔时间分布为到达间隔分布与服务时间分布的卷积以下各节,我们将对嵌入马尔柯夫链的性质作进一步的研究,求出M/G/系统的状态转移概率、系统平均顾客数、系统顾客数的概率分布、系统时间的概率分布和等待时间的概率分布 42转移概率这一节我们计算系统在两次顾客离开系统的嵌入点上由状态E,转移到状态E的转移概率P,注意到这里并不仅限于在相邻状态之间进行转移,i和j可以为任意整数。首先说明以下符号表示: Cn:进入系统的第n个顾客 r:C的到达时刻 tn:tn=n-xn,Cn与Cn之间的到达间隔时间 xn:C的服务时间; qn:第n个顾客C离开系统时系统中的顾客数(或者说Cn高开系统时系统中所剩的顾客数); vn:在对第n个顾客C进行服务期间到达系统的顾客数

511 列t1，t2 ，，tn ，，则离散参数的随机变量序列Nt n N  n , 0,1,2,       为一个马尔柯夫链。由于对于这种时刻，系统就好像重新开始一样，其未来状态完全由此时刻系统所处的状态决定，且与以前系统处于什么状态无关，因此，称这种时刻为再生点，而称离散参数的随机变量序列Nt n N   n , 0,1,2,       为嵌入马尔柯夫链。再生点就是各个顾客服务结束离开系统的瞬时。实际上，我们描述的是一个半马尔柯夫过程，它的状态转移仅发生在顾客离开系统的瞬时，在这样一些时间点上，系统的特性是符合马尔柯夫特性的，而在其余时间点上，系统又具有非马尔柯夫特性。我们把每个顾客离开系统时系统内的顾客数定义为嵌入马氏链，状态的转移只在这些嵌入点上进行且状态空间为离散空间。两次状态转移的间隔时间分布为：若前次顾客离开系统时系统内至少还有一个顾客，则间隔时间分布为服务时间分布；若前次顾客离开系统时系统为空，则间隔时间为到达间隔时间（注意它的无记忆性）加上服务时间，故状态转移的间隔时间分布为到达间隔分布与服务时间分布的卷积。以下各节，我们将对嵌入马尔柯夫链的性质作进一步的研究，求出M /G /1系统的状态转移概率、系统平均顾客数、系统顾客数的概率分布、系统时间的概率分布和等待时间的概率分布。 4.2 转移概率这一节我们计算系统在两次顾客离开系统的嵌入点上由状态Ei 转移到状态 Ej 的转移概率 Pij ，注意到这里并不仅限于在相邻状态之间进行转移，i 和 j 可以为任意整数。首先说明以下符号表示： Cn ：进入系统的第n 个顾客； n  ：Cn 的到达时刻； nt ： n nn 1 t      ，Cn 1与Cn 之间的到达间隔时间； n x ：Cn 的服务时间； qn ：第n 个顾客Cn 离开系统时系统中的顾客数（或者说Cn 离开系统时系统中所剩的顾客数）； n v ：在对第n 个顾客Cn 进行服务期间到达系统的顾客数

512 以上qn 、 n v 、 n x 三个量在后面的分析中非常重要，务必记住它们表示的意义。定义状态间的一步转移概率为： [ ] 1 p P q j q i ij  n  n  （4.2） pij 的意义是：在前个状态值为i 的条件下状态转移到 j 的概率，即在第n 个顾客Cn 离开时系统中有i 个顾客的条件下，转移到第n 1个顾客Cn1离开时系统中有 j 个顾客的概率。为此，定义一个转移概率矩阵 [ ] P p  ij ，（i ， j  0，1，2，），可以证明 P 的形式为：                                                                        0 0 1 0 1 2 0 1 2 3 0 1 2 3 43 32 33 21 22 23 10 11 12 13 00 01 02 03 1 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 q j q i ij n n 其中 1 [ ] k n Pv k    （4.3）即 k 表示在对第n 1个顾客Cn1进行服务的时间（即 n 1 x  ）内有k 个顾客到达的概率。注意：矩阵 P 中的行表示Cn 离开系统时剩下的顾客数qn （即i ），矩阵中的列表示 Cn1离开系统时剩下的顾客数qn1（即 j ）。证明：状态的转移只发生在顾客离开系统的瞬时，由于在两次顾客离开之间可能有多个顾客到达，故有qn1  qn 1（即：j  i 1，等号对应于两次顾客离开之间没有顾客到达），也就是说qn1  qn 1（即： j  i 1）是不可能的。因此，转移概率矩阵 P 中的元素为： P 中第 1 行元素说明Cn 离开系统时剩下的顾客数为 0，这表明Cn1还没有进入系统，若在Cn1进入系统后，其服务时间内没有顾客到达（其概率为0 ），则当Cn1离开系统时剩下的顾客数应为 0，这对应着矩阵的第 1 列；若有一个顾客到达（其概率为1 ），则当Cn1离开系统时剩下的顾客数应为 1，对应着第 2 列；若有两个顾客到达（其概率为 2），则当Cn1离开系统时剩下的顾客数应为 2，对应着第 3 列；以此类推

513 P 中第 2 行元素说明Cn 离开系统时剩下的顾客数为 1，这表明Cn1已经进入系统，若在Cn1的服务时间内没有顾客到达（其概率为0 ），则当Cn1离开系统时剩下的顾客数也就为 0，这对应着矩阵的第 1 列；若有一个顾客到达（其概率为1 ），则当Cn1离开系统时剩下的顾客数也就为 1，对应着第 2 列；若有两个顾客到达（其概率为 2），则当Cn1离开系统时剩下的顾客数也就为 2，对应着第 3 列；以此类推。 P 中第 3 行元素说明Cn 离开系统时剩下的顾客数为 2，当Cn1离开系统时剩下的顾客数不可能是 0（即 j 不可能取 0），这对应着矩阵的第 1 列；若在Cn1的服务时间内没有顾客到达（其概率为0 ），则当Cn1离开系统时剩下的顾客数为 1，这对应着矩阵的第 2 列；若有一个顾客到达（其概率为1 ），则当Cn1离开系统时剩下的顾客数为 2，对应着第 3 列；若有两个顾客到达（其概率为 2），则当Cn1离开系统时剩下的顾客数为 3，对应着第 4 列；以此类推。 P 中第 4 行及其以下各行元素按照上面分析方法类推，就得转移概率矩阵 P 。与转移概率矩阵 P 相对应的状态转移率图，如图 4.1 所示。 0 0 0 0 1 1  ji1  2  2  2 3    图 4.1 M / G /1嵌入马尔柯夫链的状态转移图为了求得 pij ，只需要求出 k ，现在我们来推导 k 的表达式。首先注意到，Cn1的服务时间 n 1 x  仅决定于服务时间分布密度b(x)，而与n 无关，故我们可以把服务时间 n 1 x  记为 x ~ ，它是一个连续型随机变量。把在服务时间内到达的顾客数 n 1 v  记为v ~ ，而求 ] ~ P[v k  k   。令v  k ~ 这一事件为 A，而把发生这一事件的条件 x  x ~ 记为 B ，根据全概率定律： P(A)  P(AB1 )  P(AB2 )  （4.4）由于服务时间 x 可以为任意值，事件 Bi有无穷多个，并且 x 为连续变量，故（4.4）式将成为一个积分表达式：