1、系统模拟 第10讲授课教师:左德承排队论基础排队论基础nM/G/1排队模型排队模型顾客到达间隔时间序列顾客到达间隔时间序列Jn,n1是相互独立是相互独立的随机变量序列的随机变量序列Jn(1,)，系统输入过程，系统输入过程N(t),t 0为强度为强度为为的泊松流的泊松流各顾客的服务时间序列各顾客的服务时间序列Bn,n1是相互独立是相互独立同分布的随机变量序列同分布的随机变量序列E(Bn)=1/，D(Bn)=1/2服务时间的分布函数为服务时间的分布函数为B(t)排队论基础排队论基础nM/G/1排队模型排队模型服务机构只有一个服务台服务机构只有一个服务台服务规则为先来先服务服务规则为先来先服务(FC
2、FS)等待机制等待机制Jn,n1与与Bn,n1相互独立相互独立排队论基础排队论基础n嵌入马尔可夫链嵌入马尔可夫链泊松过程的到达时间间隔具有指数分布泊松过程的到达时间间隔具有指数分布如果服务时间也服从指数分布如果服务时间也服从指数分布系统中的系统中的n时刻顾客数与时刻时刻顾客数与时刻n-1以前的顾客以前的顾客数无关数无关故系统状态故系统状态(系统中的顾客数系统中的顾客数)可以形成一个可以形成一个马尔可夫链马尔可夫链排队论基础排队论基础n对于对于M/G/1排队模型排队模型因为服务时间为任意分布，所以不具有无记忆因为服务时间为任意分布，所以不具有无记忆性的特点性的特点因此系统状态不能形成马尔可夫链因
3、此系统状态不能形成马尔可夫链对一般时刻对一般时刻n的随机变量的随机变量Xn不能形成马尔可不能形成马尔可夫链夫链如果在一些特殊的时间点上的随机变量如果在一些特殊的时间点上的随机变量Xnk可以形成马尔可夫链可以形成马尔可夫链该马尔可夫链称为嵌入马尔可夫链该马尔可夫链称为嵌入马尔可夫链形成马尔可夫链的时间点成为再生点或嵌入点形成马尔可夫链的时间点成为再生点或嵌入点排队论基础排队论基础nM/G/1排队模型排队模型服务时间为一般分布服务时间为一般分布无后效性的优点不能从服务时间方面获得无后效性的优点不能从服务时间方面获得不能在任意的一个时间点考察系统中的人数不能在任意的一个时间点考察系统中的人数变化变化
4、如果选择顾客服务完离开系统的时刻考察系如果选择顾客服务完离开系统的时刻考察系统中的人数变化统中的人数变化系统中的人数变化完全取决于到达的分布系统中的人数变化完全取决于到达的分布排队论基础排队论基础nM/G/1排队模型排队模型设设Qn为第为第n个顾客被服务完离开系统时系统个顾客被服务完离开系统时系统中的顾客数中的顾客数(队长队长)Yn为在第为在第n个顾客服务时间个顾客服务时间Bn内到达系统中内到达系统中的顾客数的顾客数Yn=N(Bn)排队论基础排队论基础nM/G/1排队模型排队模型记记由前面的条件可知，由前面的条件可知，Yn+1与与Qn相互独立相互独立0,00,1)(xxx1 ,)(11nYQQ
5、Qnnnn排队论基础排队论基础n随机序列随机序列Qn,n1是齐次马尔可夫链是齐次马尔可夫链对任意非负整数对任意非负整数k1,k2,kn+1,111111kQkQkQkQPnnnnnn,)(111111kQkQkQkYQQPnnnnnnnn)(11nnnnkkkYP11nnnnkQkQP排队论基础排队论基础nY1,Y2,Y3,相互独立同分布相互独立同分布设设当当i j+1时时kYPpik01)1,(11ijYPiQjQPnpnnnij排队论基础排队论基础n当当i=0时时n当当0 i j+1时时jnnnijpjYPiQjQPnp)1,(111111)1,(ijnnnijpijYPiQjQPnp排队
6、论基础排队论基础n上述的转移概率与上述的转移概率与n无关无关故故Qn,n1是齐次马尔可夫链是齐次马尔可夫链一步转移矩阵为一步转移矩阵为1021032104321043210000000pppppppppppppppppppP排队论基础排队论基础n从一步转移矩阵可以看出从一步转移矩阵可以看出该马尔可夫链是遍历的的该马尔可夫链是遍历的的存在极限分布存在极限分布P),(210排队论基础排队论基础n前式等价于下面的方程组前式等价于下面的方程组利用归一化条件利用归一化条件0jjkjkp01ii排队论基础排队论基础nM/G/1排队模型排队模型存在唯一稳定分布存在唯一稳定分布的充分必要条件是的充分必要条件是
7、),(2101排队论基础排队论基础nM/G/1排队模型稳定分布的解排队模型稳定分布的解根据模型为嵌入马尔可夫链，其一步转移概根据模型为嵌入马尔可夫链，其一步转移概率为率为其他情况 ,00,0 ,0,0 ,1jipjippijjij排队论基础排队论基础nM/G/1排队模型稳定分布的解排队模型稳定分布的解一步转移矩阵为一步转移矩阵为1021032104321043210000000pppppppppppppppppppP排队论基础排队论基础nM/G/1排队模型稳定分布的解排队模型稳定分布的解根据马尔可夫链稳定分布解的公式，其稳定根据马尔可夫链稳定分布解的公式，其稳定分布满足下面的方程组分布满足下面
8、的方程组0iijijp1110jiijijpp排队论基础排队论基础nM/G/1排队模型稳定分布的解排队模型稳定分布的解对于强度为对于强度为的泊松流的泊松流在时间在时间(0,t内出现内出现k个质点个质点(顾客顾客)的概率为的概率为所以所以tkkekttP!)(),0(01)(!)(tdBektkYPptknk排队论基础排队论基础n平均队长平均队长当当00，i i(n n)0)0排队网络模型排队网络模型n服务站的服务速率的类型服务站的服务速率的类型单个服务员固定速率单个服务员固定速率(single server fixed rate,SSFR)ui(n)=i无限服务员无限服务员(IS)u一个延时节
9、点，没有排队一个延时节点，没有排队ui(n)=ni队列长度相关队列长度相关(queue length dependent,QLD)u服务速率为服务速率为i(n)排队网络模型排队网络模型n一个简单的排队网络模型一个简单的排队网络模型每个节点是一个每个节点是一个M/M/1排队模型排队模型排队网络的输入为强度为排队网络的输入为强度为的泊松流的泊松流排队网络模型排队网络模型n一个简单的排队网络模型一个简单的排队网络模型每个服务器的稳定状态到达速度每个服务器的稳定状态到达速度，为什么？，为什么？每个服务器的资源利用率为每个服务器的资源利用率为一个一个M/M/1，队伍中的人数分布为，队伍中的人数分布为ii
10、/1 ,)1(0kkkk排队网络模型排队网络模型n一个一个M/M/1系统，其输出为为一强度为系统，其输出为为一强度为的泊松流的泊松流求系统输出一个顾客的等待时间分布函数求系统输出一个顾客的等待时间分布函数分两种情况：分两种情况：u系统中有顾客，服务时间服从参数为系统中有顾客，服务时间服从参数为的指数分的指数分布布u系统中无顾客，等待时间为：两个指数分布的叠系统中无顾客，等待时间为：两个指数分布的叠加加-参数为参数为的到达分布及参数为的到达分布及参数为的服务时间分的服务时间分布布排队网络模型排队网络模型n一个一个M/M/1系统，系统中有顾客的概率系统，系统中有顾客的概率为：为：，没有顾客的概率为
11、，没有顾客的概率为1-n系统输出一个顾客的等待时间分布为：系统输出一个顾客的等待时间分布为：)1)(1()1()(tttWeeetFtWetF1)(排队网络模型排队网络模型n一个简单的排队网络模型一个简单的排队网络模型网络的状态描述网络的状态描述用系统中的总人数和每个服务器的人数来描用系统中的总人数和每个服务器的人数来描述述MnMMnnMnnnP)1()1()1(),(21221121排队网络模型排队网络模型n对于一般的乘积形式的排队网络对于一般的乘积形式的排队网络其状态可以表示为其状态可以表示为其中其中fi(n)为第为第i个系统节点队长的分布个系统节点队长的分布G(N)为一个关于系统中总人数
12、为一个关于系统中总人数N的常数的常数MiiiMnfNGnnnP121)()(1),(排队网络模型排队网络模型n开环排队网络开环排队网络前面的例子是一个最简单的开环排队网络前面的例子是一个最简单的开环排队网络系统由一系列的节点系统由一系列的节点i=1,2,M组成组成顾客流在节点顾客流在节点1到达，从节点到达，从节点M离开离开进一步推广为树型结构进一步推广为树型结构属于前反馈网络，没有顾客会访问一个节点属于前反馈网络，没有顾客会访问一个节点多于多于1次次反馈对系统的性能至关重要，反馈对系统的性能至关重要，Jackson网络网络排队网络模型排队网络模型nJackson 网络网络一个系统具有一个系统具
13、有M个节点个节点(标记为标记为i=1,2,M)u节点节点i的服务速率是队列长度相关的，当队列中的服务速率是队列长度相关的，当队列中有有n个顾客服务速率是个顾客服务速率是i(n)，每个节点具有相互每个节点具有相互独立的指数分布的服务时间独立的指数分布的服务时间u网络是开环的，从系统外到达系统任何节点网络是开环的，从系统外到达系统任何节点i的的输入是泊松到达输入是泊松到达u顾客在节点上得到一次服务后，进行一次概率选顾客在节点上得到一次服务后，进行一次概率选择，要么离开网络要么进入另外一个节点。选择择，要么离开网络要么进入另外一个节点。选择与过去的历史无关与过去的历史无关排队网络模型排队网络模型n一
14、个具有一个具有M个节点的个节点的Jackson网络网络其状态空间可以刻划为其状态空间可以刻划为ni是节点是节点i的队列长度的队列长度队列长度向量的随机变量队列长度向量的随机变量(N1,N2,NM)定义网络在状态定义网络在状态n的稳定分布状态概率的稳定分布状态概率0),(21iMnnnnS,),()(1121MMMnNnNPnnnn排队网络模型排队网络模型n顾客在网络中的选道概率矩阵顾客在网络中的选道概率矩阵选道概率矩阵由顾客在一个节点接收完服务选道概率矩阵由顾客在一个节点接收完服务后到达下一个节点的选道概率组成后到达下一个节点的选道概率组成如果选道概率是状态相关的，则为自适应选如果选道概率是状态相关的，则为自适应选道道在在Jackson网络中，选道概率为常数网络中，选道概率为常数),1,(MjiqQij
