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

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

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

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

4、j-k,j+1,0,1,2,3,4,5,6,7,8,k,3,k,k,k,k,k,k,k,k,k,k,3,3,3,3,3,3,3,3,10,M/Ek/1排队模型,相位数与顾客数的对应关系 假定相位数的平稳分布为 ,而系统顾客数的平稳分布为 则 例如，M/E3/1 系统中有同样多顾客 对应有3种不同的相位数,11,M/Ek/1排队模型,求平稳分布 当 时，平稳分布存在， 若j0, pj=0 列出平衡方程 利用母函数把线性方程组化为一个线性方程，并求解,12,M/Ek/1排队模型,相位平稳分布的母函数： 将母函数展开成s的幂级数，则sj项的系数就是pj 如何将母函数转换为直观的平稳分布的表达式？ 将

5、母函数拆分成部分分式，形如 的和 将各个分式转换为s的幂级数 将各个部分分式的幂级数相加,13,M/Ek/1排队模型,可以确定 分母中，s=1是它的一个根，另外还有k个不同的实根，假设为s1,s2,sk 将母函数拆分成部分分式： 最终得到相位的平稳分布：,14,M/Ek/1排队模型,目标参量 设一顾客到达时，系统中已有j个相位，且一个相位平均需要服务时间为 。于是，j个相位平均需服务时间为 ，故新到达系统的顾客平均等候服务的时间为,15,M/Ek/1排队模型,可见，k时，Ws，Wq， Ls，Lq， 当k1时，为M/M/1排队系统 当k时，为M/D/1排队系统,16,M/M/1、M/D/1排队模

6、型对比,M/M/1 M/D/1,17,M/Ek/1例题1,某半成品检验站设一名检验员进行质量检查。假定半成品以每小时75件的平均速率按泊松分布到达，检验员检验每件半成品的时间平均为0.75分钟，且服从k=25阶爱尔兰分布，试回答： 在检验站前等候检验的半成品的平均件数 分别采用以下措施时，等候检验的半成品数各降低到多少？ 降低生产速率，使半成品到达的时间间隔服从平均值为1.2的负指数分布 更换一名更熟练的检验员，使对每件半成品的检验时间缩短为服从均值0.72分钟、k2的爱尔兰分布； 配备两名检验员，每名检验员检验一件半成品时间为0.75分钟，且服从负指数分布。,18,M/Ek/1例题2,设某电

7、话间只有一部公用电话，顾客按泊松流到达，平均每小时到达6人，每次通话时间平均为8分钟，方差为16平方分钟，通话时间服从爱尔兰分布。试求： 平均等候排队长度 顾客平均等候时间 怎么确定爱尔兰分布的阶数,19,第二节 Ek/ M/ 1排队模型,分析 单个服务窗的等待制排队模型 顾客到达间隔时间爱尔兰分布 服务时间负指数分布 平均到达间隔时间 平均服务时间 到达与服务相独立，假定,20,Ek/ M/ 1排队模型,将爱尔兰分布的顾客到达时间看作是k个相互独立的负指数分布的时间段之和 每个负指数分布的时间段视作一个“相位” 这样，下一个顾客通过一个相位所需的时间是负指数分布的，是具有无记忆性的,通过每个

8、相位的平均时间：1/k,通过全部k个相位的平均时间：1/,21,Ek/ M/ 1排队模型,将某时刻所有顾客已经通过的相位数之和看作系统状态（所有顾客包括的是排队系统内的全部顾客和下一个即将到达的顾客） 则，系统中的顾客已经通过了k个相位 即将到达的顾客已经通过了0k-1个相位 下一个到达的顾客通过一个相位相位总数加1 正在服务的顾客服务完毕相位数减k 相位数的变化是一个马尔可夫链,22,Ek/ M/ 1排队模型,画出状态流图（现在的状态是系统内相位数） 例如一个E3/M/1的排队模型,0,1,2,j,k,k+1,j-k,j+1,k,k,k,k,k,k,k,k,k,k,0,1,2,3,4,5,6

9、,7,8,k,k,k,k,k,k,k,k,k,23,Ek/ M/ 1排队模型,相位数与顾客数的对应关系 假定相位数的平稳分布为 ,而系统顾客数的平稳分布为 则 例如系统中有3个顾客时的相位数就有可能是：,已经通过的相位数为3,已经通过的相位数为1,24,Ek/ M/ 1排队模型,求平稳分布 当 时，平稳分布存在 列出平衡方程 利用母函数把线性方程组化为一个线性方程，并求解,25,Ek/ M/ 1排队模型,相位平稳分布的母函数： 经过整理得： 其中s0是方程 的一个在单位圆外的根,26,Ek/ M/ 1排队模型,相位的平稳分布 系统内顾客数的平稳分布:,27,Ek/ M/ 1排队模型,目标参量

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

11、1的状态流图 使用ki表示系统中有k个顾客，而正在服务的顾客所在的是i (i=1,2)号相位,33,相位法综述3,为了继续拓宽相位法的适用范围，我们可以看看把相位串并组合后的结果。如果每个串连相位的服务率也可以不同的话，就可以产生更复杂的分布。,34,相位法综述4,已经证明，任何一种分布，都可以把这种分布拆分成串联-并联的相位组合。 使用这种发法。首先，描述系统状态必须包括3个量： 系统中的顾客数 下一个到达的顾客所在的相位 正在接受服务的顾客所在的相位 然后我们可以画出状态流图（往往非常复杂的图） 然后通过研究分析，写出平稳方程（往往非常罗嗦的公式） 最后，使用计算机求解我们需要的结果 这种

12、方法的求解排队模型，结果虽然不是像前面学习过的一样可以预先得出，但这的确是一种理论上可行的方法。,35,补：M/M排队系统的输出过程,输出是与输入同强度的泊松流 设排队系统为M/M/n/m(1nm )，设到达的顾客流是参数为的泊松流（在等待制时，进入系统的流是参数为的泊松流；在混合制与损失制时，进入系统的流是参数为(1-pm)的泊松流），如果把混合制与损失制时的损失流也看作系统的输出，则系统的输出是参数为的泊松流。 证明略,36,队长分布与顾客到达时刻看到的队长分布的关系,设统计平衡条件下，顾客到达时看到的队长为ls-（不包括到达的这个顾客）， ls-与平稳队长ls的分布相同吗？ 平稳分布记做

13、：,排队系统,37,队长分布与顾客到达时刻看到的队长分布的关系,举例D/D/1排队系统 假定顾客到达间隔时间= 服务时间= 并且到达的间隔时间大于服务时间 到达的顾客不需要等待，所以有： 到达的顾客看到的队长分布 系统中最多有一个顾客，所以有： 系统队长分布： 看到D/D/1排队系统中：,38,到达与离开时的队长分布的关系,下面我们研究三种时刻队长分布的关系 pn-=P(顾客到达时系统中已有n个顾客) pn=P(N=n)=平稳分布=系统队长为n的概率 pn+=P(顾客离开系统时系统还留下n个顾客的概率),39,到达与离开时的队长分布的关系,能达到平稳的G/G系统pn- =pn+ ,顾客在极短时

14、间内只能到达一个，或离开一个,N(t),t,n+1,n,跟踪N(t)实际走过的一条路线,40,到达与离开时的队长分布的关系,假定从状态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)为从任何状态开始上跳一步的总次数和下跳一步的总次数，在统计平衡条件下，有：,41,到达与离开时的队长分布的关系,42,M/G系统顾客到达时刻看到的的队长分布与队长分布的关系,M/G系统有pn-(t)= pn(t)，即任意时刻，到达的顾客看到

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

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

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