什么是排队网络n排队网络包含一组节点，每个节点有若干服务 器单个节点可以被视为一个排队系统n客户可以在从任何节点进入排队网络当客户 在某个节点排队获得服务以后，它们可以离开 网络，也可以去另外的节点，甚至回到原来的 节点11.一个排队网络有k个节点，节点i（i=1,2,…,k ）上有ci个服务器，服务器服务单个客户的时 间服从指数分布，平均为1/μi单个节点可以 被视为 一个M/M/c/∞排队系统2.客户到达是泊松过程，以速率γi到达节点i3.当一个客户在节点i的服务器上完成服务，它 以概率rij进入节点j；以概率ri0离开排队网络n满足以上3条被称为Jackson网络n对任意i，若 γi=0， ri0=0，被称为闭合Jackson网络 （没有客户进入和离开）n否则被称为开放Jackson网络2n闭合Jackson网络例子：n修理工模型，存在两个节点，正常工作和故障修 理i=1,2 j=0,1,2 r12=r21=1 并且其余rij=0n开放Jackson网络，如果满足则这个排队网络被称为串联(Series)n客户从第一个节点进入网络n客户依次经历节点1，2，3，...，直到离开网络3串联（Series）排队网络n例子：n医院看病：挂号、诊断开药、划价、缴费、拿药n每个节点可以被视为一个M/M/c/∞，前一个节点的输 出是下一个节点的输入4n客户到达节点1服从泊松过程，速率为λ。
节点 i有ci个服务器，是一个M/M/ci排队系统n问题：客户从节点离开是怎样一个随机过程？ 离开时间间隔服从何种分布?n结论：稳态下排队网络节点的离开过程=到达 过程离开时间间隔服从指数分布n直观解释：“时间倒流”，客户到达和客户离开 互换，得到一个完全一样的稳态下的排队网络 （队列长度，等待时间等指标均一样）5理论证明n系统中有N(t)=n个客户的概率nT表示客户离开事件的时间间隔（类比于到达时间间 隔）n系统中有n个客户，且距离上次客户离开超过t的概率n离开时间间隔分布6n考虑在时间t+Δt有n个客户的概率n令Δt→∞，有n边界条件 7n求解微分方程，得到8离开时间间隔服从指数分布例子：超市n某超市改进了结帐系统当所有结帐柜台忙时，顾 客获得一个号码并等待，当一个结帐柜台空闲，最 小号码的顾客去柜台结帐超市很大，可以容纳很 多顾客顾客到达超市服从泊松过程，平均每小时 到达40位；每位顾客购物平均花费3/4小时，购物时 间服从指数分布每位顾客结帐平均需4分钟，结帐 时间也服从指数分布问：n超市至少需要多少个结帐柜台？n如果设置比最少要求多一个的结帐柜台，求顾客的平均等 待结帐时间，平均有多少顾客等待结帐，多少顾客在超市 的逗留。
9n两个节点的串联排队网络n节点1：购物，M/M/∞/∞ ，λ=40，μ1=4/3n节点2：结帐，M/M/c/∞ ， λ=40， μ2=15n问题1： ρ2=λ/cμ21，ri=λi/μin其中， ，p0i满足n再次，开放Jackson网络的状态概率等于k个独 立M/M/c的状态概率的联合，但是这并不意味 着开放Jackson网络的节点是相互独立的M/M/c21n讨论：n由于开放Jackson网络的“内部流量”可能不服从泊松过程， 因此很难求解等待时间概率分布等复杂的性能指标n回馈网络和非回馈网络：如果排队网络中有回馈，即客户 可以回到之前访问过的节点，这个排队网络被称为带回馈 的，否则是非回馈的n非回馈网络：进入各节点的客户仍然可视为一个泊松过程 ，进一步分析队列或者节点的等待时间概率分布是可能的n回馈网络：破坏了客户到达的泊松性质，非常难以分析n我们之前获得的结果限于均值分析，适用于上述两种网络22例子：800免费n某公司800免费服务如下：当用户拨号，在获得语音提示 以后，可以按“1”进入产品介绍，按“2”进入问题咨询。
用户用 于听取语音提示并决定按“1”还是“2”的时间平均为30秒，指数 分布一次只能有一名用户听取语音提示大约55%的用户 选择产品介绍，产品介绍有三名客服人员负责，产品介绍平 均6分钟，指数分布；45%的用户选择问题咨询，有7名客服 人员负责问题咨询，问题咨询平均耗时20分钟，指数分布 大约有2%的用户在听完产品介绍以后转到问题咨询，1%的用 户在咨询完问题以后转到产品介绍每小时平均有35名用户 拨打，泊松过程当用户不能获得服务时，他们在 里听到音乐并且等待23n问：n每个环节平均有多少用户等待？n用户拨打800的平均通话时间n三个节点的开放Jackson网络，节点为：1语音 提示、2产品介绍、3问题咨询n节点转移概率矩阵 到达速率24n可得n对M/M/1, M/M/3, M/M/725n应用M/M/c关于队列长度的结果26客户分类的开放Jackson网络n客户被分为不同类型，具有不同的到达速率和节点 转移矩阵n求解：n第一步：分别求解 ，并计算λ=Σtλ(t)n第二步：运用M/M/c排队模型求解节点内的平均客户数Li ，客户逗留时间Win第三步：计算每一种类型客户在节点内的平均数目，逗留 时间27例子：n上面800的例子中，客户在听完产品介绍并完成 问题咨询以后仍然可能进入产品介绍，而客户在完 成问题咨询并听完产品介绍以后仍然可能进入问题 咨询。
显然这不符合常理考虑一个更精确的模型 ：客户被分为两类，类型1客户选择产品介绍，并且 其中2%在听完产品介绍后选择问题咨询；类型2客户 选择问题咨询，其中1%完成咨询后进入产品介绍28n求解29与上例不同30闭合Jackson网络n在开放Jackson网络中，如果对任何节点，γi=0，ri0=0 ，即任何节点既无客户进入，也无客户离开，称为 闭合Jackson网络n固有的N个客户在闭合Jackson网络中流动31n考虑ci=1的情况，根据开放Jackson网络的稳态 平衡方程，对闭合Jackson网络，稳态平衡方 程如下（γi=0, ri0=0）n对闭合Jackson网络，状态概率可以写为，其中32nρi满足 ，且 ，对ρi有n考虑i=1,2,…,k获得变量ρi的方程组n方程组存在一个冗余方程，不能解出ρi的确切 值（k个未知变量，k-1个不同等式）33n可以假设任意一个ρi =1，求出其它ρjn闭合网络中总共有N个客户，根据全概率公式n通常把C写为C(N)，显示它与N相关，或者写 为34n如果节点上有多个服务器， ci≥135例子：机器-修理工-修理专家n某实验室有两台计算服务器保持一直工作的状态。
服务器以λ 的速率发生故障；若仅有系统故障，实验室管理员可以修理 ，修理速率μ2，系统故障发生概率r12；服务器以概率(1-r12)发 生硬件故障，这时服务器必须送专家修理，修理速率为μ3 有时，当服务器经管理员修理以后，服务器仍然需送专家修 理，这种情况发生的概率r23其它情况服务器都可以立即开 始工作问：1）两台机器均正常工作的概率；2）至少一台 机器正常工作的概率n闭合Jackson网络： 节点1，正常工作，c1=2，M/M/2；或者认为是M/M/∞但客户 数最大为2 节点2，管理员修理，c2=1，M/M/1； 节点3，专家修理， c3=1，M/M/136n求解n转移矩阵n稳态方程n令ρ2=1，37n如果λ=2, μ2=1, μ3=3, r12=3/4, r23=1/3n考虑所有(n1,n2,n3)的情况，一共有6种：n(2,0,0), (0,2,0), (0,0,2), (1,1,0), (1,0,1), (0,1,1)n可以解出数值解38计算G(N)：Buzen算法n上例中，N=2，k=3，计算G(2)显得不复杂n如果N和k较大，计算G(N)非常复杂n把N个客户分配到k个节点，有 种方案n1973年，Buzen设计出一种算法，较为高效地 计算G(N)：n令 ，则有n定义辅助函数39显然n对gm(n)，考虑nm=i的情况n由于g1(n)=f1(n)，gm(0)=1， gm(n)可以递归求解n特别地，对于节点k（最后一个节点），n个客 户在节点k的概率为40例子n在“机器-修理工-修理专家”例中，令ρ2=1，可 以解出n令λ=2，μ2=1， μ3=3，r12=3/4，r23=1/341n由递归关系n计算42n 43闭合Jackson网络的均值分析n求出 ，若需计算节点i上的平均客户个数 Li，平均消耗时间Win另外一种分析闭合Jackson网络的方法是均值分析， 不需要计算G(N)和441. 计算G(N)很麻烦 2. 考虑所有的n1,n2，…,nk组合n两个原则n原则1：回忆M/M/1系统的分析，有W=(1+L)/μ。
对 于闭合Jackson网络（假设所有节点上1个服务器） ，nWi(N)：一个包含N个客户的排队网络，客户一次访问在节 点i上的平均消耗时间nμi：节点i上服务器的服务速率nLi(N-1)：一个包含N-1个客户的排队网络，节点i上的平均 客户个数45n原则2：根据Little’s law，nλi(N)：包含N个客户的排队网络中节点i上的客户 到达速率n如果得到λi(N)，使用以上关系，可以递归计 算Li(N)和Wi(N)（注意Li(0)=0， Wi(1)=1/μi ）n令Di(N)表示N个客户的排队网络中客户访问 节点i的平均间隔，则有n前面已知 ，令则有46n上式组成的方程组存在一个冗余方程任选一 个 ，可以求解所有vin求出来的vi是一个相对值，即节点i上客户到达 速率对节点l上的客户到达速率之比， n节点l上的客户平均访问间 隔n即一个客户两次访问节 点l的间隔是它经历网络 中所有节点（包括节点l）的时间的加权和节点 i的权重就是节点i对于节点l的客户到达速率比 47n完整算法1.求解方程组 ，设置任意一个 ，求 出所有2.初始化3.For n=1 到 N，计算a. b. c. d. 48例子n在“机器-修理工-修理专家”例中，假设只有一台服务 器。
且 λ=2, μ2=1, μ3=3, r12=3/4, r23=1/3n第一步，求解vi49n第二步a，i=1,2,3，n=N=1n第二步b，n第二步c，n第二步d，50n在M/M/1排队系统中，有n对闭合排队网络，有其中 是在一个包含N个客户的排队网络 中，节点i上有n个客户的概率pi(0,0)=1n对上例，有51循环排队网络n闭合Jackson网络，转移概率矩阵如下称这种闭合网络为循环排队网络(Cycle Queues)n修理工模型就是一种2节点的循环排队网络52n应用闭合Jackson网络的结果且 n将转移矩阵代入，有进而有n任选l，令ρl=153n循环排队网络的状态概率n其中G(N)可以穷举所有(n1,n2,…,nk)的组合计算 ，或者采用Buzen算法求出。