《系统模拟-第10讲课件.ppt》由会员分享，可在线阅读，更多相关《系统模拟-第10讲课件.ppt（51页珍藏版）》请在三一办公上搜索。
1、系统模拟,第10讲授课教师:左德承,排队论基础,M/G/1排队模型顾客到达间隔时间序列Jn,n1是相互独立的随机变量序列Jn(1,)，系统输入过程N(t),t 0为强度为的泊松流各顾客的服务时间序列Bn,n1是相互独立同分布的随机变量序列E(Bn)=1/，D(Bn)=1/2服务时间的分布函数为B(t),排队论基础,M/G/1排队模型服务机构只有一个服务台服务规则为先来先服务(FCFS)等待机制Jn,n1与Bn,n1相互独立,排队论基础,嵌入马尔可夫链泊松过程的到达时间间隔具有指数分布如果服务时间也服从指数分布系统中的n时刻顾客数与时刻n-1以前的顾客数无关故系统状态(系统中的顾客数)可以形成一
2、个马尔可夫链,排队论基础,对于M/G/1排队模型因为服务时间为任意分布，所以不具有无记忆性的特点因此系统状态不能形成马尔可夫链对一般时刻n的随机变量Xn不能形成马尔可夫链如果在一些特殊的时间点上的随机变量Xnk可以形成马尔可夫链该马尔可夫链称为嵌入马尔可夫链形成马尔可夫链的时间点成为再生点或嵌入点,排队论基础,M/G/1排队模型服务时间为一般分布无后效性的优点不能从服务时间方面获得不能在任意的一个时间点考察系统中的人数变化如果选择顾客服务完离开系统的时刻考察系统中的人数变化系统中的人数变化完全取决于到达的分布,排队论基础,M/G/1排队模型设Qn为第n个顾客被服务完离开系统时系统中的顾客数(队
3、长)Yn为在第n个顾客服务时间Bn内到达系统中的顾客数Yn=N(Bn),排队论基础,M/G/1排队模型记由前面的条件可知，Yn+1与Qn相互独立,排队论基础,随机序列Qn,n1是齐次马尔可夫链对任意非负整数k1,k2,kn+1,排队论基础,Y1,Y2,Y3,相互独立同分布设当i j+1时,排队论基础,当i=0时当0 i j+1时,排队论基础,上述的转移概率与n无关故Qn,n1是齐次马尔可夫链一步转移矩阵为,排队论基础,从一步转移矩阵可以看出该马尔可夫链是遍历的的存在极限分布,排队论基础,前式等价于下面的方程组利用归一化条件,排队论基础,M/G/1排队模型存在唯一稳定分布的充分必要条件是,排队论
4、基础,M/G/1排队模型稳定分布的解根据模型为嵌入马尔可夫链，其一步转移概率为,排队论基础,M/G/1排队模型稳定分布的解一步转移矩阵为,排队论基础,M/G/1排队模型稳定分布的解根据马尔可夫链稳定分布解的公式，其稳定分布满足下面的方程组,排队论基础,M/G/1排队模型稳定分布的解对于强度为的泊松流在时间(0,t内出现k个质点(顾客)的概率为所以,排队论基础,平均队长当1时，该嵌入马尔可夫链有稳定分布根据前面的结果平均队长为,排队论基础,平均队长根据泊松流在(0,t质点出现的平均数,排队论基础,平均队长求E(Qn)令n，得,排队论基础,平均队长根据前面的结果根据极限分布的含义,排队论基础,平均
5、队长将下面公式两边取平方，再取数学期望注意Yn+1与Qn相互独立，令n,排队论基础,平均队长根据前面的结果解上面的方程，得,排队论基础,平均队长现在只需求出Y的二阶原点矩就可以得出平均队长根据前面的过程,排队论基础,平均队长根据前面的结构，平均队长为,排队论基础,根据Little公式，平均逗留时间为平均等待时间为,排队论基础,根据Little公式，平均等待队长为服务台被占用的概率(顾客到达需要等待的概率),排队论基础,对于M/D/1排队模型服务时间固定，为1/，所以2=0,排队论基础,对于对于M/M/1排队模型服务时间均值为1/，方差为1/2,排队网络模型,排队网络基本概念在分布式环境中，孤立
6、排队的现象只是特例多个互连排队的问题/模型顾客流的分开与合并队列的串并组合,排队网络模型,一个简单的排队网络,排队网络模型,系统资源的工作负荷网络中每类任务或顾客的特性节点的服务时间节点的之间的选道概率(routing probability)顾客的类型单一类别顾客，顾客具有完全相同的特征不同类型顾客，在每个节点不同的顾客具有不同的请求及穿越网络的不同路由行为,排队网络模型,排队网络的类型开环网络(open network)闭环网络(closed network)混合网络(mixed network),排队网络模型,开环网络系统至少要有一个来自外部的输入弧和一个去往外部的输出弧闭环网络没有外部
7、弧，网络中的顾客数目为常数，所有顾客永远循环流动可以认为是输出弧和输入弧相连的特殊的开环网络,排队网络模型,开环网络,排队网络模型,闭环网络,排队网络模型,混合网络,排队网络模型,服务站的类型排队网络的节点由每类顾客的服务规则和服务时间分布定义当队列中共有n个顾客时每个节点有一个状态相关的服务速率i(n)i(0)=0，对于n0，i(n)0,排队网络模型,服务站的服务速率的类型单个服务员固定速率(single server fixed rate,SSFR)i(n)=i无限服务员(IS)一个延时节点，没有排队i(n)=ni队列长度相关(queue length dependent,QLD)服务速率
8、为i(n),排队网络模型,一个简单的排队网络模型每个节点是一个M/M/1排队模型排队网络的输入为强度为的泊松流,排队网络模型,一个简单的排队网络模型每个服务器的稳定状态到达速度，为什么？每个服务器的资源利用率为一个M/M/1，队伍中的人数分布为,排队网络模型,一个M/M/1系统，其输出为为一强度为的泊松流求系统输出一个顾客的等待时间分布函数分两种情况：系统中有顾客，服务时间服从参数为的指数分布系统中无顾客，等待时间为：两个指数分布的叠加-参数为的到达分布及参数为的服务时间分布,排队网络模型,一个M/M/1系统，系统中有顾客的概率为：，没有顾客的概率为1-系统输出一个顾客的等待时间分布为：,排队
9、网络模型,一个简单的排队网络模型网络的状态描述用系统中的总人数和每个服务器的人数来描述,排队网络模型,对于一般的乘积形式的排队网络其状态可以表示为其中fi(n)为第i个系统节点队长的分布G(N)为一个关于系统中总人数N的常数,排队网络模型,开环排队网络前面的例子是一个最简单的开环排队网络系统由一系列的节点i=1,2,M组成顾客流在节点1到达，从节点M离开进一步推广为树型结构属于前反馈网络，没有顾客会访问一个节点多于1次反馈对系统的性能至关重要，Jackson网络,排队网络模型,Jackson 网络一个系统具有M个节点(标记为i=1,2,M)节点i的服务速率是队列长度相关的，当队列中有n个顾客服务速率是i(n)，每个节点具有相互独立的指数分布的服务时间网络是开环的，从系统外到达系统任何节点i的输入是泊松到达顾客在节点上得到一次服务后，进行一次概率选择，要么离开网络要么进入另外一个节点。选择与过去的历史无关,排队网络模型,一个具有M个节点的Jackson网络其状态空间可以刻划为ni是节点i的队列长度队列长度向量的随机变量(N1,N2,NM)定义网络在状态n的稳定分布状态概率,排队网络模型,顾客在网络中的选道概率矩阵选道概率矩阵由顾客在一个节点接收完服务后到达下一个节点的选道概率组成如果选道概率是状态相关的，则为自适应选道在Jackson网络中，选道概率为常数,
