排队论大学课件10-非马尔科夫排队模型

1、第五章 非马尔可夫排队模型1非马尔可夫排队模型排队系统中的顾客数变化不具有马尔可夫性顾客到达间隔时间分布、服务时间分布其中之一或两者都不是负指数分布的（时间分布不具有无记忆性），则此排队模型为非马尔可夫排队模型例如一条流水线，每2分钟到达一个半成品，加工一个半成品的时间服从负指数分布，D/M/1电话网中，20的用户需要拨号上网，上网时间为平均30分钟的负指数分布，如何设计交换机？M/H2/m/m2第一节 M/Ek/1排队模型顾客到达间隔时间负指数分布顾客服务时间k阶爱尔兰分布单个服务窗等待制排队模型不具有无记忆性采用相位法解决3爱尔兰分布与负指数分布的密切关系22服务时间为：一个负指数分布服务

2、时间为：两个独立负指数分布时间的和4类似的我们可以表示k阶爱尔兰分布的服务时间kkkk顾客服务时间是k阶爱尔兰分布，相当于k个同参数的负指数分布的时间阶段之和，称每一个负指数分布的时间阶段为一个相位。返回5因此，如果一个顾客正在接受服务，他可能处于k个相位中的任意一个相位。一个相位的服务时间服从负指数分布。服务完一个相位，就接着进入下一个相位进行服务。一个顾客服务完全部相位才离开服务窗，这时候下一个顾客进入服务窗开始服务。虽然顾客数的减少不具有无记忆性，但是相位数的减少具有无记忆性kkkk单个相位：服务率k平均服务时间1/k6M/Ek/1排队模型相位法：把系统中当前所有顾客全部被服务完毕离开系

3、统应通过的相位数作为系统状态。正在服务的顾客通过一个相位，则相位数减1到达一个顾客，则相位数加k因此系统增加k个相位和减少一个相位所需时间都是负指数分布的，系统相位数的变化是马尔可夫链7M/Ek/1排队模型相位法分析在足够短时间t内，能够发生的事件只有两种到达一个顾客，相位数加k，概率为t+o(t)如果有顾客在接受服务，服务完一个相位，概率为kt+o(t)因此得到Q矩阵：8M/Ek/1排队模型画出状态流图（现在的状态是系统内相位数）例如一个M/E3/1排队模型012jkk+1j-kj+1012345678k3kkkkkkkkkk333333339M/Ek/1排队模型相位数与顾客数的对应关系假定

4、相位数的平稳分布为 ,而系统顾客数的平稳分布为则例如，M/E3/1系统中有同样多顾客对应有3种不同的相位数10M/Ek/1排队模型求平稳分布当 时，平稳分布存在，若j0, pj=0列出平衡方程利用母函数把线性方程组化为一个线性方程，并求解11M/Ek/1排队模型相位平稳分布的母函数：将母函数展开成s的幂级数，则sj项的系数就是pj如何将母函数转换为直观的平稳分布的表达式？将母函数拆分成部分分式，形如 的和将各个分式转换为s的幂级数将各个部分分式的幂级数相加12M/Ek/1排队模型可以确定 分母中，s=1是它的一个根，另外还有k个不同的实根，假设为s1,s2,sk将母函数拆分成部分分式：最终得到

5、相位的平稳分布：13M/Ek/1排队模型目标参量设一顾客到达时，系统中已有j个相位，且一个相位平均需要服务时间为 。于是，j个相位平均需服务时间为 ，故新到达系统的顾客平均等候服务的时间为14M/Ek/1排队模型可见，k时，Ws，Wq， Ls，Lq，当k1时，为M/M/1排队系统当k时，为M/D/1排队系统15M/M/1、M/D/1排队模型对比M/M/1M/D/116M/Ek/1例题1某半成品检验站设一名检验员进行质量检查。假定半成品以每小时75件的平均速率按泊松分布到达，检验员检验每件半成品的时间平均为0.75分钟，且服从k=25阶爱尔兰分布，试回答：在检验站前等候检验的半成品的平均件数分别

6、采用以下措施时，等候检验的半成品数各降低到多少？降低生产速率，使半成品到达的时间间隔服从平均值为1.2的负指数分布更换一名更熟练的检验员，使对每件半成品的检验时间缩短为服从均值0.72分钟、k2的爱尔兰分布；配备两名检验员，每名检验员检验一件半成品时间为0.75分钟，且服从负指数分布。17M/Ek/1例题2设某电话间只有一部公用电话，顾客按泊松流到达，平均每小时到达6人，每次通话时间平均为8分钟，方差为16平方分钟，通话时间服从爱尔兰分布。试求：平均等候排队长度顾客平均等候时间怎么确定爱尔兰分布的阶数18第二节 Ek/ M/ 1排队模型分析单个服务窗的等待制排队模型顾客到达间隔时间爱尔兰分布服

7、务时间负指数分布平均到达间隔时间平均服务时间到达与服务相独立，假定19Ek/ M/ 1排队模型将爱尔兰分布的顾客到达时间看作是k个相互独立的负指数分布的时间段之和每个负指数分布的时间段视作一个“相位”这样，下一个顾客通过一个相位所需的时间是负指数分布的，是具有无记忆性的kkkk通过每个相位的平均时间：1/k通过全部k个相位的平均时间：1/20Ek/ M/ 1排队模型将某时刻所有顾客已经通过的相位数之和看作系统状态（所有顾客包括的是排队系统内的全部顾客和下一个即将到达的顾客）则，系统中的顾客已经通过了k个相位即将到达的顾客已经通过了0k-1个相位下一个到达的顾客通过一个相位相位总数加1正在服务的

8、顾客服务完毕相位数减k相位数的变化是一个马尔可夫链21Ek/ M/ 1排队模型画出状态流图（现在的状态是系统内相位数）例如一个E3/M/1的排队模型012jkk+1j-kj+1kkkkkkkkkk012345678kkkkkkkkk22Ek/ M/ 1排队模型相位数与顾客数的对应关系假定相位数的平稳分布为 ,而系统顾客数的平稳分布为 则例如系统中有3个顾客时的相位数就有可能是：已经通过的相位数为3已经通过的相位数为123Ek/ M/ 1排队模型求平稳分布当 时，平稳分布存在列出平衡方程利用母函数把线性方程组化为一个线性方程，并求解24Ek/ M/ 1排队模型相位平稳分布的母函数：经过整理得：其

9、中s0是方程 的一个在单位圆外的根25Ek/ M/ 1排队模型相位的平稳分布系统内顾客数的平稳分布:26Ek/ M/ 1排队模型目标参量平均系统队长系统队长方差平均等候队长27Ek/ M/ 1排队模型目标参量28Ek/ M/ 1排队模型例题在一个E3/M/1排队模型中，已知服务窗的利用率为0.8，服务窗服务一个顾客所需的平均时间为10分钟。试求顾客的平均等候队长Lq，平均等候时间Wq以及29相位法综述1是否相位法只能使用在M/Ek/1和Ek/M/1两种排队模型中呢？回顾爱尔兰分布：如果采用服务率不同的相位串连，则得到的变量其变异系数也1的分布，则用超指数分布（并联的相位）例如一个2个并联相位的

10、服务窗：12121231相位法综述2M/H2/1的状态流图使用ki表示系统中有k个顾客，而正在服务的顾客所在的是i (i=1,2)号相位01112212212221112212132相位法综述3为了继续拓宽相位法的适用范围，我们可以看看把相位串并组合后的结果。如果每个串连相位的服务率也可以不同的话，就可以产生更复杂的分布。r11ri21i11rR21Rr11ri222rR22r11ri2r1rR2rirR33相位法综述4已经证明，任何一种分布，都可以把这种分布拆分成串联-并联的相位组合。使用这种发法。首先，描述系统状态必须包括3个量：系统中的顾客数下一个到达的顾客所在的相位正在接受服务的顾客所

11、在的相位然后我们可以画出状态流图（往往非常复杂的图）然后通过研究分析，写出平稳方程（往往非常罗嗦的公式）最后，使用计算机求解我们需要的结果这种方法的求解排队模型，结果虽然不是像前面学习过的一样可以预先得出，但这的确是一种理论上可行的方法。34补：M/M排队系统的输出过程输出是与输入同强度的泊松流设排队系统为M/M/n/m(1nm )，设到达的顾客流是参数为的泊松流（在等待制时，进入系统的流是参数为的泊松流；在混合制与损失制时，进入系统的流是参数为(1-pm)的泊松流），如果把混合制与损失制时的损失流也看作系统的输出，则系统的输出是参数为的泊松流。证明略35队长分布与顾客到达时刻看到的队长分布的

12、关系设统计平衡条件下，顾客到达时看到的队长为ls-（不包括到达的这个顾客）， ls-与平稳队长ls的分布相同吗？平稳分布记做：排队系统36队长分布与顾客到达时刻看到的队长分布的关系举例D/D/1排队系统假定顾客到达间隔时间=服务时间=并且到达的间隔时间大于服务时间到达的顾客不需要等待，所以有：到达的顾客看到的队长分布系统中最多有一个顾客，所以有：系统队长分布：看到D/D/1排队系统中：37到达与离开时的队长分布的关系下面我们研究三种时刻队长分布的关系pn-=P(顾客到达时系统中已有n个顾客)pn=P(N=n)=平稳分布=系统队长为n的概率pn+=P(顾客离开系统时系统还留下n个顾客的概率)38

13、到达与离开时的队长分布的关系能达到平稳的G/G系统pn- =pn+ ,顾客在极短时间内只能到达一个，或离开一个N(t)tn+1n跟踪N(t)实际走过的一条路线39到达与离开时的队长分布的关系假定从状态n上跳到状态n+1的次数为An(t)从状态n+1下跳到状态n的次数为Dn(t)由于到达与离去是一个一个发生的，并且n-n+1与n+1-n是交错发生的。所以到t时刻为止，An(t)与Dn(t)至多相差1设A(t)、D(t)为从任何状态开始上跳一步的总次数和下跳一步的总次数，在统计平衡条件下，有：40到达与离开时的队长分布的关系41M/G系统顾客到达时刻看到的的队长分布与队长分布的关系M/G系统有pn

14、-(t)= pn(t)，即任意时刻，到达的顾客看到的队长分布等于系统队长的分布证明令A(t, t+t)表示在t, t+t)时间内到达了一个顾客，则 因为输入流是泊松流，所以A(t, t+t)发生的概率是 t+o(t)，与N(t)=n这个事件无关。所以42结论G/G排队系统pn- =pn+ 即到达的顾客与离开的顾客所看到的队长分布是相等的M/G排队系统中pn- =pn+ =pn即在顾客为泊松流到达的排队系统中，到达的顾客与离开的顾客看到的队长分布与系统的队长分布都相等 43第三节 M/G/1排队模型嵌入式马氏链的来源在任何时候，如果总结排队系统状态的”历史”,必须使用二维的状态X(t),X0(t

15、)，其中X(t)是t时刻系统中的顾客数， X0(t)是t时刻正在服务的顾客已经服务了的时间。我们希望还是采用一维变量X(t)来描述系统状态，并且希望去掉X0(t)这个连续变量。因此，我们不要关注时间轴上的每一个点，而是选择一系列我们需要的点。我们选择的就是“顾客离开时刻”这一系列时间点t，在这些点上X0(t)=0。而X(t)则是在刚服务完的顾客离开时，留在排队系统中的顾客数44M/G/1排队模型对于时间点的选择，使我们关注的目标变成了一系列间隔不定的离散的点。关注的问题这一系列时间点上，顾客数变化是不是马尔可夫链？这一系列时间点的平稳分布是不是整个系统的顾客数的平稳分布？tn-1tntn+1t

16、n+2XnXn1空Xn0Xn=045M/G/1排队模型单服务窗等待制排队模型顾客到达间隔时间负指数分布顾客服务时间一般分布Xn：第n个顾客刚离开系统的瞬间，系统内留有的顾客数Tn：第n1个顾客的服务时间Yn：第n1个顾客的服务期间到达的顾客数 Yn0tn-1tntn+1tn+2XnXn1空Xn0Xn=046M/G/1排队模型系统状态Xn可以看到Xn的变化与Xn-1，Xn-2，没有关系，因此Xn的变化具有无记忆性，是一个嵌入式马尔可夫链，而且发现此嵌入式马氏链的分布就是系统内顾客数的分布。下面开始分析嵌入式马氏链的转移矩阵假定47M/G/1排队模型一步转移概率：一步转移矩阵：48M/G/1排队模型i+1i+2ii-1ji-2a0a1a2a3aj-i+1a2a3a0120ja0a0a1aja049M/G/1排队模型Tn为第n1个顾客的服务时间，Tn是独立同分布的随机变量序列，记其公共分布函数为G(t)=P(Tnt)求aj，即一个服务时间期间到达j个顾客的概率书P170 5.3-650M/G/1排队模型平衡方程（离散马尔可夫链的公式）接下来可以根据求平稳分