非马尔可夫排队模型

1、12l排队系统中的顾客数变化不具有马尔可夫性排队系统中的顾客数变化不具有马尔可夫性l顾客服务时间分布、服务时间分布其中之一或两顾客服务时间分布、服务时间分布其中之一或两者都不是负指数分布的（时间分布不具有无记忆者都不是负指数分布的（时间分布不具有无记忆性），则此排队模型为非马尔可夫排队模型性），则此排队模型为非马尔可夫排队模型l例如例如一条流水线，每一条流水线，每2分钟到达一个半成品，加工一个半分钟到达一个半成品，加工一个半成品的时间服从负指数分布，成品的时间服从负指数分布，D/M/1电话网中，电话网中，20的用户需要拨号上网，上网时间为的用户需要拨号上网，上网时间为平均平均30分钟的负指数分

2、布，如何设计交换机？分钟的负指数分布，如何设计交换机？M/H2/m/m3l顾客到达间隔时间顾客到达间隔时间负指数分布负指数分布l顾客服务时间顾客服务时间k阶爱尔兰分布阶爱尔兰分布l单个服务窗单个服务窗l等待制排队模型等待制排队模型不具有无记忆性不具有无记忆性采用采用相位法相位法解决解决422服务时间为：一个负指数分布服务时间为：一个负指数分布服务时间为：两个独立负指数分布时间的和服务时间为：两个独立负指数分布时间的和2( )11tf teETDT22( )2 (2)11212tf tt eETDTDTET5l类似的我们可以表示类似的我们可以表示k阶爱尔兰分布的服务时间阶爱尔兰分布的服务时间kk

3、kk122()( )(1)!11()()kk tkk tf tektD tktkD t服服服服概率密度：顾客服务时间是顾客服务时间是k阶爱尔兰分布，相当于阶爱尔兰分布，相当于k个同参数的负指数分布的个同参数的负指数分布的时间阶段之和，称每一个负指数分布的时间阶段为一个时间阶段之和，称每一个负指数分布的时间阶段为一个相位相位。返回6l因此，如果一个顾客正在接受服务，他可能处于因此，如果一个顾客正在接受服务，他可能处于k个相位中的任意一个相位。个相位中的任意一个相位。l一个相位的服务时间服从负指数分布。一个相位的服务时间服从负指数分布。l服务完一个相位，就接着进入下一个相位进行服服务完一个相位，就

4、接着进入下一个相位进行服务。务。l一个顾客服务完全部相位才离开服务窗，这时候一个顾客服务完全部相位才离开服务窗，这时候下一个顾客进入服务窗开始服务。下一个顾客进入服务窗开始服务。l虽然顾客数的减少不具有无记忆性，但是相位数虽然顾客数的减少不具有无记忆性，但是相位数的减少具有无记忆性的减少具有无记忆性kkkk单个相位：服务率k平均服务时间1/k7l相位法：相位法：把系统中当前所有顾客全部被服务完毕离开系统把系统中当前所有顾客全部被服务完毕离开系统应通过的相位数作为系统状态。应通过的相位数作为系统状态。正在服务的顾客通过一个相位，则相位数减正在服务的顾客通过一个相位，则相位数减1到达一个顾客，则相

5、位数加到达一个顾客，则相位数加k因此系统增加因此系统增加k个相位和减少一个相位所需时间个相位和减少一个相位所需时间都是负指数分布的，系统相位数的变化是马尔可都是负指数分布的，系统相位数的变化是马尔可夫链夫链8l相位法分析相位法分析在足够短时间在足够短时间 t内，能够发生的事件只有两种内，能够发生的事件只有两种l到达一个顾客，相位数加到达一个顾客，相位数加k，概率为，概率为t+o( t)l如果有顾客在接受服务，服务完一个相位，概率为如果有顾客在接受服务，服务完一个相位，概率为kt+o( t)因此得到因此得到Q矩阵：矩阵：,1,001()0 其他i ii i kiii jqkiqQqkqq9l画出

6、状态流图（现在的状态是系统内相位数）画出状态流图（现在的状态是系统内相位数）l例如一个例如一个M/E3/1排队模型排队模型012jkk+1j-kj+1012345678 k 3 k k k k k k k k k k 3 3 3 3 3 3 3 3 10l相位数与顾客数的对应关系相位数与顾客数的对应关系假定相位数的平稳分布为假定相位数的平稳分布为 ,而系统顾客数的平而系统顾客数的平稳分布为稳分布为则则例如，例如，M/E3/1系统中有同样多顾客系统中有同样多顾客对应有对应有3种不同的相位数种不同的相位数jpnp(1)1001,2,.j nknjjnkppnpp11l求平稳分布求平稳分布当当 时，

7、平稳分布存在，时，平稳分布存在，若若j0, pj=0l列出平衡方程列出平衡方程l利用母函数把线性方程组化为一个线性方利用母函数把线性方程组化为一个线性方程，并求解程，并求解1011()1jj kjpkpkppkpj12l相位平稳分布的母函数：相位平稳分布的母函数：将母函数展开成将母函数展开成s的幂级数，则的幂级数，则sj项的系数就是项的系数就是pj如何将母函数转换为直观的平稳分布的表达式？如何将母函数转换为直观的平稳分布的表达式？l将母函数拆分成部分分式，形如将母函数拆分成部分分式，形如 的和的和l将各个分式转换为将各个分式转换为s的幂级数的幂级数l将各个部分分式的幂级数相加将各个部分分式的幂

8、级数相加1(1)(1)( )()kksP sksks1AsB13l可以确定可以确定 分母中，分母中，s=1是它是它的一个根，另外还有的一个根，另外还有k个不同的实根，假设为个不同的实根，假设为s1,s2,skl将母函数拆分成部分分式：将母函数拆分成部分分式：l最终得到相位的平稳分布：最终得到相位的平稳分布：1(1)(1)( )()kksP sksks111( )(1)1/1/1kkllljlljj llAP sAs sssAkl =1且1(1)kjjlllpAs14l目标参量目标参量设一顾客到达时，系统中已有设一顾客到达时，系统中已有j个相位，且一个个相位，且一个相位平均需要服务时间为相位平均

9、需要服务时间为 。于是，。于是，j个相位平个相位平均需服务时间为均需服务时间为 ，故新到达系统的顾客平均，故新到达系统的顾客平均等候服务的时间为等候服务的时间为1 1k kj jk k0011(1)(1)(1)2(1)(1)2(1)qjjjjjWpjpPkkkkkkk15可见，k时，Ws，Wq， Ls，Lq，当k1时，为M/M/1排队系统当k时，为M/D/1排队系统22211(1)(1)2(1)(1)(1)12 (1)2 (1)(1)2 (1)sqssqqkWWkkkLWkkkLWk16lM/M/1lM/D/121(1)(1)11qsqsWWLL2222 (1)2 (1)22(1)2(1)qs

10、qsWWLL17l某半成品检验站设一名检验员进行质量检查。假某半成品检验站设一名检验员进行质量检查。假定半成品以每小时定半成品以每小时75件的平均速率按泊松分布到件的平均速率按泊松分布到达，检验员检验每件半成品的时间平均为达，检验员检验每件半成品的时间平均为0.75分分钟，且服从钟，且服从k=25阶爱尔兰分布，试回答：阶爱尔兰分布，试回答：在检验站前等候检验的半成品的平均件数在检验站前等候检验的半成品的平均件数分别采用以下措施时，等候检验的半成品数各降低分别采用以下措施时，等候检验的半成品数各降低到多少？到多少？l降低生产速率，使半成品到达的时间间隔服从平均值降低生产速率，使半成品到达的时间间

11、隔服从平均值为为1.2的负指数分布的负指数分布l更换一名更熟练的检验员，使对每件半成品的检验时更换一名更熟练的检验员，使对每件半成品的检验时间缩短为服从均值间缩短为服从均值0.72分钟、分钟、k2的爱尔兰分布；的爱尔兰分布；l配备两名检验员，每名检验员检验一件半成品时间为配备两名检验员，每名检验员检验一件半成品时间为0.75分钟，且服从负指数分布。分钟，且服从负指数分布。18l设某电话间只有一部公用电话，顾客按泊设某电话间只有一部公用电话，顾客按泊松流到达，平均每小时到达松流到达，平均每小时到达6人，每次通话人，每次通话时间平均为时间平均为8分钟，方差为分钟，方差为16平方分钟，通平方分钟，通

12、话时间服从爱尔兰分布。试求：话时间服从爱尔兰分布。试求：平均等候排队长度平均等候排队长度顾客平均等候时间顾客平均等候时间怎么确定爱尔兰分布的阶数19l分析分析单个服务窗的等待制排队模型单个服务窗的等待制排队模型顾客到达间隔时间顾客到达间隔时间爱尔兰分布爱尔兰分布服务时间服务时间负指数分布负指数分布平均到达间隔时间平均到达间隔时间平均服务时间平均服务时间l到达与服务相独立，假定到达与服务相独立，假定1 11 111()( )(1)!kk tkk ta tek( )tb te20l将爱尔兰分布的顾客到达时间看作是将爱尔兰分布的顾客到达时间看作是k个相互独立个相互独立的负指数分布的时间段之和的负指数

13、分布的时间段之和l每个负指数分布的时间段视作一个每个负指数分布的时间段视作一个“相位相位”l这样，下一个顾客通过一个相位所需的时间是负指这样，下一个顾客通过一个相位所需的时间是负指数分布的，是具有无记忆性的数分布的，是具有无记忆性的k k k k 通过每个相位的平均时间：1/k 通过全部k个相位的平均时间：1/ 21l将某时刻所有顾客已经通过的相位数之和看作系将某时刻所有顾客已经通过的相位数之和看作系统状态（所有顾客包括的是排队系统内的全部顾统状态（所有顾客包括的是排队系统内的全部顾客和客和下一个即将到达的顾客下一个即将到达的顾客）则，系统中的顾客已经通过了则，系统中的顾客已经通过了k个相位个

14、相位即将到达的顾客已经通过了即将到达的顾客已经通过了0k-1个相位个相位l下一个到达的顾客通过一个相位下一个到达的顾客通过一个相位相位总数加相位总数加1l正在服务的顾客服务完毕正在服务的顾客服务完毕相位数减相位数减kl相位数的变化是一个马尔可夫链相位数的变化是一个马尔可夫链22l画出状态流图（现在的状态是系统内相位数）画出状态流图（现在的状态是系统内相位数）l例如一个例如一个E3/M/1的排队模型的排队模型012jkk+1j-kj+1k k k k k k k k k k 012345678 k k k k k k k k k 23l相位数与顾客数的对应关系相位数与顾客数的对应关系假定相位数的

15、平稳分布为假定相位数的平稳分布为 ,而系统顾客数的平而系统顾客数的平稳分布为稳分布为 则则例如系统中有例如系统中有3个顾客时的相位数就有可能是：个顾客时的相位数就有可能是：jpnp(1)10,1,2,.jnknjj nkppn已经通过的相位数为3已经通过的相位数为124l求平稳分布求平稳分布当当 时，平稳分布存在时，平稳分布存在l列出平衡方程列出平衡方程l利用母函数把线性方程组化为一个线性方利用母函数把线性方程组化为一个线性方程，并求解程，并求解10110()kjjj kjjj kkppkpkppjkkpkppjk25l相位平稳分布的母函数：相位平稳分布的母函数：l经过整理得：经过整理得：其中

16、其中s0是方程是方程 的一个在的一个在单位圆外的根单位圆外的根101(1)( )(1)1kkjjjkksp sP sk sks00(1)(1)( )(1)() kssP sk sss1(1)10 kkk sks26l相位的平稳分布相位的平稳分布l系统内顾客数的平稳分布系统内顾客数的平稳分布:10011100011(1)0(1)111()jjj kjjjkkspsjkk sss 0010(1)0nknknpssn27l目标参量目标参量平均系统队长平均系统队长系统队长方差系统队长方差平均等候队长平均等候队长000000(1)1kknksnknnsLnpsnss2200200(1)1( ).(1)k

17、kssnknssD ln pLs01qsskLLLLs服28l目标参量目标参量000(1)1(1)ksskqqkLsWsLWs29l在一个E3/M/1排队模型中，已知服务窗的利用率为0.8，服务窗服务一个顾客所需的平均时间为10分钟。试求顾客的平均等候队长Lq，平均等候时间Wq以及np30l是否相位法只能使用在是否相位法只能使用在M/Ek/1和和Ek/M/1两种排队模型两种排队模型中呢？中呢？l回顾爱尔兰分布：回顾爱尔兰分布：l如果采用服务率不同的相位串连，则得到的变量其变如果采用服务率不同的相位串连，则得到的变量其变异系数也异系数也1的分布，则用超指数分布（并的分布，则用超指数分布（并联的相

18、位）联的相位）l例如一个例如一个2个并联相位的服务窗：个并联相位的服务窗：12 1 2121122*121212( )( )ttb teeBxxx 1232lM/H2/1的状态流图的状态流图l使用使用ki表示系统中有表示系统中有k个顾客，而正在服务的顾客个顾客，而正在服务的顾客所在的是所在的是i (i=1,2)号相位号相位011122122 1 22 2 1 1 1 2 2 1 2133l为了继续拓宽相位法的适用范围，我们可以看看把相位串并组为了继续拓宽相位法的适用范围，我们可以看看把相位串并组合后的结果。如果每个串连相位的服务率也可以不同的话，就合后的结果。如果每个串连相位的服务率也可以不同

19、的话，就可以产生更复杂的分布。可以产生更复杂的分布。r11ri2 1 i11rR21 Rr11ri222rR22r11ri2r1rR2rirR*1( )()iRriiiiiirB xxr34l已经证明，任何一种分布，都可以把这种分布拆分成串已经证明，任何一种分布，都可以把这种分布拆分成串联联-并联的相位组合。并联的相位组合。l使用这种发法。首先，描述系统状态必须包括使用这种发法。首先，描述系统状态必须包括3个量：个量：系统中的顾客数系统中的顾客数下一个到达的顾客所在的相位下一个到达的顾客所在的相位正在接受服务的顾客所在的相位正在接受服务的顾客所在的相位l然后我们可以画出状态流图（往往非常复杂的

20、图）然后我们可以画出状态流图（往往非常复杂的图）l然后通过研究分析，写出平稳方程（往往非常罗嗦的公然后通过研究分析，写出平稳方程（往往非常罗嗦的公式）式）l最后，使用计算机求解我们需要的结果最后，使用计算机求解我们需要的结果l这种方法的求解排队模型，结果虽然不是像前面学习过这种方法的求解排队模型，结果虽然不是像前面学习过的一样可以预先得出，但这的确是一种理论上可行的方的一样可以预先得出，但这的确是一种理论上可行的方法。法。35l嵌入式马氏链的来源嵌入式马氏链的来源在任何时候，如果总结马氏链的在任何时候，如果总结马氏链的”历史历史”,必须必须使用二维的状态使用二维的状态N(t),X0(t)，其中

21、，其中N(t)是是t时刻系时刻系统中的顾客数，统中的顾客数， X0(t)是是t时刻正在服务的顾客已时刻正在服务的顾客已经服务了的时间。经服务了的时间。l我们希望还是采用一维变量我们希望还是采用一维变量N(t)来描述系统状态，并来描述系统状态，并且希望去掉且希望去掉X0(t)这个连续变量。因此，我们不要关注这个连续变量。因此，我们不要关注时间轴上的每一个点，而是选择一系列我们需要的点。时间轴上的每一个点，而是选择一系列我们需要的点。我们选择的就是我们选择的就是“顾客离开时刻顾客离开时刻”这一系列时间这一系列时间点，在这些点上点，在这些点上X0(t)=0。而。而N(t)则是在刚服务完则是在刚服务完

22、的顾客离开时，留在排队系统中的顾客数的顾客离开时，留在排队系统中的顾客数36l单服务窗等待制排队模型单服务窗等待制排队模型l顾客到达间隔时间顾客到达间隔时间负指数分布负指数分布l顾客服务时间顾客服务时间任意分布任意分布tn-1tntn+1tn+2Xn：第n个顾客刚离开系统的瞬间，系统内留有的顾客数XnXn1Tn：第n1个顾客的服务时间Yn：第n1个顾客的服务期间到达的顾客数 Yn0空Xn0Xn=037l系统状态系统状态Xn可以看到可以看到Xn的变化与的变化与Xn-1，Xn-2，没有关系，因此没有关系，因此Xn的变化具有无记忆性，是一个嵌入式马尔可夫链，而且的变化具有无记忆性，是一个嵌入式马尔可夫链，而且发现此嵌入式马氏链的分布就是系统内顾客数的分布。发现此嵌入式马氏链的分布就是系统内顾客数的分布。l下面开始分析嵌入式马氏链的转移矩阵下面开始分析嵌入式马氏链的转移矩阵假定假定11010nnnnnnYXXXYX1()jn+1(|)jnijnnijjaP YjpP Xj Xipa有 个顾客在第顾客服务期间到达的概率状态转移的概率与 有密切的关系38l一步转移概率：一步转移概率：l一步转移矩阵：一步转移矩阵：0111(|0)()(|)(1|)(1|)011jnnnjijnnnnnnj ipP Xj XP YjapP Xj XiP iYj XiP YjiXiijaij 012012