第六章--排队网络系统

第六章,排队网络系统简介在排队论中,一个排队模型是一个实际排队系统的数学近似模拟.排队网络系统是由任意多个,通常是由有限个,单个排队系统构成的.来自不同类型或系统的顾客们已不同的方式或线路访问并通过网络,并被服务于访问的服务站(节点),各个服务站提供的服务不同,这种服务可以是真正的服务,也可以是仅仅通过而已.例如,某个顾客访问银行,有的人直接走到出纳员那里取钱或存钱,有人则需要先由接待员服务,然后再由出纳员服务,如果涉及的资金多,则还需要部门经理服务.那么,接待员,出纳员,经理,还有无人自动存储机,均为节点,而整个银行就是一个排队网络系统.如果我们模拟的是三峡船闸系统,那么,不同水平的船闸开起及关闭,及不同船只通过的路线也是一个排队网络系统.许多工厂,公司都要面临设备维修保养,零件配件的供货订货,生产流水线的管理等等都可以构成排队网络系统,利用排队网络系统模型去模拟实现.在排队网络系统顾客可以从一个排队系统进入另一个排队系统,这种转移可以是随机的,服从某一概率分布,也可以是固定的6.1开放Jackson网络系统定义6.1:一个排队网络系统被定义为Jackson网络,那么它满足:1.所有的系统外的访问者,不论首先访问哪一个服务站,均服从泊松分布2.不论哪一个服务站,所有的服务时间,,均服从指数分布3.所有的服务站,均可接待无限数量的顾客4.当一个顾客被完成了一个服务以后,其转移到另一个服务站的概率,与该顾客已经接受的服务过程无关,与其它的服务所在的服务站无关.Jackson网络系统可以是开放的,也可以是闭合的.开放的Jackson网络系统接受系统外顾客的来访顾客也可以离开.闭合的Jackson网络系统不接受系统外顾客的来访,也没有顾客离开.机器维修保养系统,可以看做是闭合的,机器工作时机器处于一种状态,机器不工作时,机器处于另一种状态,当机器修好,机器回到第一中第一种工作状态.6.2开放Jackson网络系统我们使用例子开始讨论开放Jackson网络系统,演示如何求出解答.例6.1某工作站有三种服务:加工,细加工,装饰,顾客访问该工作站,首先要进行加工,然后80%的顾客进行细加工,再被装饰,其余1/5的顾客直接被装饰.工作站内有一台机器进行加工,平均加工时间为5分钟,有两台机器进行细加工,每台每次平均加工时间为15分钟,有一台机器进行装饰,平均加工时间为6分钟,全部服从指数分布.顾客到工作站访问的个数为泊松分布,平均7.5分钟一个新顾客到来.整个工作流程如图6.1所示工作流程图solution首先可以确定这是一个Jackson网络系统,根据陈述,我们写出其转移矩阵:这里节1为加工,节2为细加工,节3为装饰出站.解决Jackson网络系统的步骤为首先确定每个节点的顾客访问率,然后对每个节点按照独立的M/M/c系统处理.VisitRate那么我们首先计算三个节点的事件发生率:很明显,对于节点1:λ1=1/7.5*60=8/小时对于节点2:λ2=λ1*0.8=6.4/小时对于节点3:λ3=λ1*0.25+λ2=8*0.2+6.4=8/小时下面我们计算服务率,根据陈述,显然μ1=60/5=12/小时,μ2=60/15=4/小时,μ3=60/6=10/小时.Solution对于节点1和节点3,M/M/1系统,使用第四章的稳定状态下系统中顾客数目的平均值确4.6ρ1=λ1/μ1=8/12=0.667,ρ3=λ23/μ3=8/10=0.8,因此L1=0.667/(1-0.667)=2L3=0.8/(1-0.8)=4对于节点2,它是M/M/2系统,见图2那么,我们首先设p0为n=0的概率,明显λn=λ,对任意n=0,1,2…成立.服务时间稍有变化,只有一个顾客和有两个或两个以上的顾客的服务效率不同.只有一个顾客时,一个服务器工作,另一个服务器工作等待,系统具有两个或两个以上的顾客时,两个服务器均工作,因此服务率为:那么我们可以得到这里γ=λ/μ,ρ=γ/2.那么,由于於是:对于节点2:ρ2=6.4/8=0.8,因此p02=0.2/1.8=1/9,可以证明,M/M/2系统的平均顾客数目为平均排队等待数目为因此L2=2*0.8/(1-0.82)=4.44.可以得到,节点1没有顾客的概率为p01=1-ρ01=1-2/3=1/3,节点2没有顾客的概率为p02=1/9,节点3没有顾客的概率为p03=1-ρ03=1-0.8=0.2.节点总访问率现在最困难的地方是计算估计每个节点(服务器)的顾客访问率.我们使用λi代表节点i的总访问率.在一个稳定系统中每个节点总顾客访问率与总输出率应该相等,因此λi应该等于从所有其它节点的来访率及系统外来访率的总和.因此我们有这里,γi为网络系统外访问节点外的访问率,P(k,i)为由节点k直接传到节点i的概率.对于网络系统中的任一节点都有一个方程,因此我们可以得到性质如下:性质6.1性质6.1:假设矩阵P为Jackson网络系统各节点之间的转换概率γ为由网络系统外顾客访问每个节点的访问率所构成的向量,那么各个节点实际访问率构成的向量λ=(λ1,λ2,…λm)T满足λ=γ(I-P)-16.2这里m为由网络系统节点的总数.性质6.2:假设Jackson网络系统具有m个节点,每个节点的服务效率均服从指数分布,其相应的指数参数为μi,假设随机变元Ni为节点i访问顾客的个数,那么m个节点的联合分布概率为P{N1=n1,N2=n2,…,Nm=nm}=P{N1=n1}*P{N2=n2}*,…*P{Nm=nm}6.3式中任何一个概率,P{Ni=ni},ni=0,1,2…,均可以用M/M/C排队系统概率公式求出.顾客数目的期望值研究网络系统的特性,通常关注的是:通过系统服务的顾客数目期望值,在系统中接受服务的期望值,以及顾客在系统中停留时间的期望值.由于我们研究的系统是稳定的,因此通过系统服务的顾客数目期望值应该等于外界到系统访问的数目总数的期望值,∑γi.,在系统中接受服务顾客数目的期望值等于每个节点中接受服务顾客数目期望值之和.顾客在系统中停留时间的期望值可以使用Little定律解决,于是我们有:性质6.3:考虑Jackson一个拥有m个节点的,Nnet为代表在系统中停留的顾客总数,Tnet代表任一个顾客在系统停留时间,γ是由各个节点外界顾客访问率所构成的向量.Li为M/M/C系统中得到的节点i中的顾客数目的期望值,那么我们有,例6.2某工作站有三种服务:加工,细加工,装饰,顾客访问该工作站,首先要进行加工,然后4/5的顾客进行细加工,再被装饰,其余1/5的顾客直接被装饰.在所有被细加工的顾客有10%的顾客需要退回到第一种状态重新加工.在所有被装饰的顾客也有10%的顾客需要退回到第一种状态重新加工.工作站内有一台机器进行加工,平均加工时间为5分钟,有两台机器进行细加工,每台每次平均加工时间为15分钟,有一台机器进行装饰,平均加工时间为6分钟,全部服从指数分布.顾客到工作站访问的个数为泊松分布,平均7.5分钟一个新顾客到来.解:首先可以确定这是一个Jackson网络系统,根据陈述,我们写出其转移矩阵:这里节1为加工,节2为细加工,节3为装饰出站.使用6.1,λ1=8+0.1λ2+0.1λ3λ2=0.8λ1λ3=0.2λ1+0.9λ2解这个方程组,由第三式我们得到λ3=0.92λ1,与第二式一起代入第一式,λ1=9.662,λ2=7.729,λ3=8.889,其相应的服务率为μ1=60/5=12/小时,μ2=60/15=4/小时,μ3=60/6=10/小时.那么ρ1=λ1/μ1=9.662/12=0.8052,ρ2=λ2/(2μ2)=7.729/8=0.9661ρ3=λ3/μ3=8.889/10=0.8889,对于节点1和节点3,M/M/1系统,使用第四章的稳定状态下系统中顾客数目的平均值因此L1=0.8052/(1-0.8052)=4.1326L3=0.8889/(1-0.8889)=8.0009对于节点2,M/M/2系统的平均顾客数目为因此顾客在整个网络系统停留数目的期望值为L=L1+L2+L3=41.124.在节点1,没有顾客访问的概率为p01=(1-ρ1)/(1+ρ1)=(1-0.8052)/(1+0.8052)=0.1079,在节点2,没有顾客访问的概率为p02=(1-ρ2)/(1+ρ2)=(1-0.9661)/(1+0.9661)=0.0172,在节点3,没有顾客访问的概率为p03=(1-ρ3)/(1+ρ3)=(1-0.8889)/(1+0.8889)=0.0588.因此,在整个网络系统没有顾客访问的概率为p=p01*p02*p03=0.0001.顾客在系统中的平均时间为E(Tnet)=41.124/(8+0+0)=2.35小时.6.2封闭Jackson网络系统所谓的封闭Jackson网络系统并不是真正封闭的.而是当系统饱和后,进出系统的个数相同,一个顾客被完成服务后,下一个顾客才被容许进入,因此系统的顾客总数是固定的.系统永远处于稳定状态,因此我们可以把系统看成是封闭的.下面我们使用例子来具体讨论例6.3,某加工厂需要三道程序对产品进行加工:1.机工车间,2.组装车间3.电力车间.在机工车间加工的产品,70%需要到组装车间组装,30%直接到电力车间.在组装车间的产品,10%被发现质量问题,需要返回到加工车间,90%的产品到电力车间.在电力车间完成的产品,离开系统,因此一个新的产品进入网络系统,以保持系统总产品数目不变假设系统最多可以容纳5个产品.有关各个车间的时间信息如下,所有的加工时间均服从指数分布,在机工停留时间时间,其均值为80分钟,在组装停留时间时间,其均值为120分钟,在电力停留时间时间,其均值为60分钟.系统的转移矩阵(I-P)是不满秩矩阵外界输入变量(产品进入各个节点的访问向量)r为0向量.因此不可能解出,进入每个节点的实际输入率.仅能求出相对访问向量,因此我们可以假设第一行第一列的取值为1,然后求出其它行列相对外界对输入率为γ0=(1,0.7,0.3)τ,出去第一个数值,接点1的输假设输入率,那么γ=(0.7,0.3)τ可以被看做为由节点2,3构成的网络系统的外界输入向量,使用6.1性质6.4假设P代表一个具有m个节点的封闭网络系统的转移矩阵,Q代表移去第一行,第一列的P的子矩阵,γ为由P的第一行,移去第一个分量所构成的向量γ=(p12,p13,…,p1m)τ,第二到m个节点的相对输入向量ξ可以由下式估计ξ=γτ(1-Q)-1此为性质6.1的推论估计系统内产品所花的时间•但是我们最关心的是如何估计系统内产品所花的时间,系统在每一个节点上所需要的时间,但是这些量是与封闭网络系统的水平有关部门,所谓的水平是与网络所同时服务的顾客数目决定的,容许进入系统的个数越多,那么每个顾客在系统内停留时间越长.显然,同时也与顾客实际的访问率有关均值分析策略性质6.5:均值分析考虑一个封闭的具有m个节点的网络系统,最多服务于wmax个工作.节点i的服务时间服从均值为μi的指数分布i=1,2,…,m.使用性质6.4估计出的相对节点访问率,ξi.我们可以使用下面步驺计算在每个节点平均停留时间.1.设w=1,Wk(w)=1/μk,k=1,2,…,m2.setw=w+1,3.4.当w=wmax停止,否则回到2每个节点的平均顾客访问率例:6.3(继续)在网络系统停留时间的计算过程列在表6.1中的第1-5行当w=5时,我们得到产品在机工车间平均停留时间为289.3分钟,在组装车间平均停留时间为471.6分钟,在电力车间平均停留时间为108.6分钟.wW1(w)W1(w)W3(w)∑ξiWi(w)18012060219.82109.12165.8671.46291.683149.94231.8883.72390.114207.57328.3696.30526.975289.32471.58108.62720.446405.51687.65120.08998.54表6.1网络系统内平均逗留时间计算(w=5或者6)系统特征(容许量)