第五章 非马尔可夫排队模型.pptVIP

第五章 非马尔可夫排队模型 非马尔可夫排队模型 排队系统中的顾客数变化不具有马尔可夫性 顾客服务时间分布、服务时间分布其中之一或两者都不是负指数分布的（时间分布不具有无记忆性），则此排队模型为非马尔可夫排队模型 例如 一条流水线，每2分钟到达一个半成品，加工一个半成品的时间服从负指数分布，D/M/1 电话网中，20％的用户需要拨号上网，上网时间为平均30分钟的负指数分布，如何设计交换机？M/H2/m/m 第一节 M/Ek/1排队模型 顾客到达间隔时间——负指数分布 顾客服务时间——k阶爱尔兰分布 单个服务窗 等待制排队模型 爱尔兰分布与负指数分布的密切关系 类似的我们可以表示k阶爱尔兰分布的服务时间 因此，如果一个顾客正在接受服务，他可能处于k个相位中的任意一个相位。 一个相位的服务时间服从负指数分布。 服务完一个相位，就接着进入下一个相位进行服务。 一个顾客服务完全部相位才离开服务窗，这时候下一个顾客进入服务窗开始服务。 虽然顾客数的减少不具有无记忆性，但是相位数的减少具有无记忆性 M/Ek/1排队模型 相位法： 把系统中当前所有顾客全部被服务完毕离开系统应通过的相位数作为系统状态。 正在服务的顾客通过一个相位，则相位数减1 到达一个顾客，则相位数加k 因此系统增加k个相位和减少一个相位所需时间都是负指数分布的，系统相位数的变化是马尔可夫链 M/Ek/1排队模型 相位法分析 在足够短时间?t内，能够发生的事件只有两种 到达一个顾客，相位数加k，概率为??t+o(?t) 如果有顾客在接受服务，服务完一个相位，概率为k??t+o(?t) 因此得到Q矩阵： M/Ek/1排队模型 画出状态流图（现在的状态是系统内相位数） 例如一个M/E3/1排队模型 M/Ek/1排队模型 相位数与顾客数的对应关系 假定相位数的平稳分布为 ,而系统顾客数的平稳分布为 则 例如，M/E3/1 系统中有同样多顾客 对应有3种不同的相位数 M/Ek/1排队模型 求平稳分布 当 时，平稳分布存在， 若j0, pj=0 列出平衡方程 利用母函数把线性方程组化为一个线性方程，并求解 M/Ek/1排队模型 相位平稳分布的母函数： 将母函数展开成s的幂级数，则sj项的系数就是pj 如何将母函数转换为直观的平稳分布的表达式？ 将母函数拆分成部分分式，形如 的和 将各个分式转换为s的幂级数 将各个部分分式的幂级数相加 M/Ek/1排队模型 可以确定 分母中，s=1是它的一个根，另外还有k个不同的实根，假设为s1,s2,…,sk 将母函数拆分成部分分式： 最终得到相位的平稳分布： M/Ek/1排队模型 目标参量 设一顾客到达时，系统中已有j个相位，且一个相位平均需要服务时间为 。于是，j个相位平均需服务时间为 ，故新到达系统的顾客平均等候服务的时间为 M/Ek/1排队模型 可见，k?时，Ws?，Wq?， Ls?，Lq?， 当k＝1时，为M/M/1排队系统 当k??时，为M/D/1排队系统 M/M/1、M/D/1排队模型对比 M/M/1 M/D/1 M/Ek/1例题1 某半成品检验站设一名检验员进行质量检查。假定半成品以每小时75件的平均速率按泊松分布到达，检验员检验每件半成品的时间平均为0.75分钟，且服从k=25阶爱尔兰分布，试回答： 在检验站前等候检验的半成品的平均件数 分别采用以下措施时，等候检验的半成品数各降低到多少？ 降低生产速率，使半成品到达的时间间隔服从平均值为1.2的负指数分布 更换一名更熟练的检验员，使对每件半成品的检验时间缩短为服从均值0.72分钟、k＝2的爱尔兰分布； 配备两名检验员，每名检验员检验一件半成品时间为0.75分钟，且服从负指数分布。 M/Ek/1例题2 设某电话间只有一部公用电话，顾客按泊松流到达，平均每小时到达6人，每次通话时间平均为8分钟，方差为16平方分钟，通话时间服从爱尔兰分布。试求： 平均等候排队长度 顾客平均等候时间 怎么确定爱尔兰分布的阶数 第二节 Ek/ M/ 1排队模型 分析 单个服务窗的等待制排队模型 顾客到达间隔时间——爱尔兰分布 服务时间——负指数分布 平均到达间隔时间—— 平均服务时间—— 到达与服务相独立，假定 Ek/ M/ 1排队模型 将爱尔兰分布的顾客到达时间看作是k个相互独立的负指数分布的时间段之和 每个负指数分布的时间段视作一个“相位” 这样，下一个顾客通过一个相位所需的时间是负指数分布的，是具有无记忆性的 Ek/ M/ 1排队模型 将某时刻所有顾客已经通过的相位数之和看作系统状态（