目录 第4章M/G/1排队模型 41嵌入马尔柯夫链 42转移概率 43系统平均顾客数 44系统中顾客数的概率分布 4.5等待时间的概率分布
目 录 第 4 章 M / G / 1排队模型 4.1 嵌入马尔柯夫链 4.2 转移概率 4.3 系统平均顾客数 4.4 系统中顾客数的概率分布 4.5 等待时间的概率分布
第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 以后，二维随机过程Nt，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 进行服务期间到达系统的顾客数
以上qn、vn、xn三个量在后面的分析中非常重要,务必记住它们表示的意义。 定义状态间的一步转移概率为: Iqn,=jIa,=i] (42) P2的意义是:在前个状恋值为的条件下状态转移到j的概率即在第n个顾客C 离开时系统中有个顾客的条件下,转移到第n+1个顾客C高开时系统中有j个顾客 的概率。 为此,定义一个转移概率矩阵P=[Pn],(i,j=0,1,2,…),可以证明P的形 式为: Poo Po Po2 po3 ae aa P10P1P12P13 P=-pm=/--|0"pp P32 p P 其中a4=PIvn1=k] (4.3) 即a4表示在对第n+1个顾客Cn1进行服务的时间(即xn1)内有k个顾客到达的概 注意:矩阵P中的行表示C离开系统时剩下的顾客数qn(即i),矩阵中的列表示 Cn离开系统时剩下的顾客数qn1(即j)。 证明: 状态的转移只发生在顾客离开系统的瞬时,由于在两次顾客离开之间可能有多个顾 客到达,故有qn1≥qn-1(即:j≥i-1,等号对应于两火顾客离开之间没有顾客到达) 也就是说qn1<qn-1(即:j<1-1)是不可能的。因此,转移概率矩阵P中的元素为: P中第1行元素说明C离开系统时剩下的顾客数为0,这表明Cn1还没有进入系统, 若在Cn1进入系统后,其服务时间内没有顾客到达(其概率为a0),则当Cn离开系统 时剩下的顾客数应为0,这对应着矩阵的第1列;若有一个顾客到达(其概率为a1), 则当C离开系统时剩下的顾客数应为1,对应着第2列;若有两个顾客到达(其概率 为a2),则当Cn离开系统时剩下的顾客数应为2,对应着第3列;以此类推。 512
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个顾客Cn1离开时系统中有 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个顾客Cn1进行服务的时间（即 n 1 x ）内有k 个顾客到达的概 率。 注意：矩阵 P 中的行表示Cn 离开系统时剩下的顾客数qn （即i ），矩阵中的列表示 Cn1离开系统时剩下的顾客数qn1（即 j ）。 证明： 状态的转移只发生在顾客离开系统的瞬时，由于在两次顾客离开之间可能有多个顾 客到达，故有qn1 qn 1（即：j i 1，等号对应于两次顾客离开之间没有顾客到达）， 也就是说qn1 qn 1（即： j i 1）是不可能的。因此，转移概率矩阵 P 中的元素为： P 中第 1 行元素说明Cn 离开系统时剩下的顾客数为 0，这表明Cn1还没有进入系统， 若在Cn1进入系统后，其服务时间内没有顾客到达（其概率为0 ），则当Cn1离开系统 时剩下的顾客数应为 0，这对应着矩阵的第 1 列；若有一个顾客到达（其概率为1 ）， 则当Cn1离开系统时剩下的顾客数应为 1，对应着第 2 列；若有两个顾客到达（其概率 为 2），则当Cn1离开系统时剩下的顾客数应为 2，对应着第 3 列；以此类推