运筹学标准服务系统MMn系统.pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第八章 标准服务系统,M/M/n 系统,鱼与熊掌兼得？,1,第1页,8.1 M/M/n 损失制,8.1.1 M/M/n,损失制，无限源,(M/M/n:,/n/FIFO),令从用户源来用户抵达率为,，每台服务率为,则有,j,=,j,=0,1,.,n,1;,n,=0，,j,=,j,j,=0,1,.,n,将,j,j,代入生灭方程，得,式中,=,/,称为,业务量,(,traffic,)，是无量纲量,；,表示单位时间内要求系统提供服务时间；,和,单位必须一致；因为纪念Erlang，用,爱尔兰,作单位(Erl),2,第2页,系统服务质量,系统质量用用户损失率来度量，有两种度量方法,按时间计算,损失率,p,n,，即单位时间内服务台全被占用时间,按用户计算,损失率,B,，即单位时间内损失用户数与抵达用户数之比,在本系统中有,B,=,p,n,=,E,n,(,)，称为,爱尔兰损失公式,不是全部系统都有,B,=,p,n,性质,工程上经常是已知,，给定,B,，求所需最少服务台,n,求,n,普通有三种方法：迭代计算，查图，查表,3,第3页,求所需服务台方法,1、查图，如书上262页,2、,迭代计算,无法由,E,n,(,)给出,n,逆函数，所以采取逐次试算方法,注意，,E,n,(,)有较简单递推公式,3、工程上经常采取查表方法,爱尔兰表最左边一列为服务台数,n,，最上面一行为服务质量不一样等级，即,B,爱尔兰表中元素值为,，表示服务台数为,n,，服务质量为,B,时，系统最大所能负担业务量；工程上经惯用,A,表示,，,A,是,加入话务量,4,第4页,爱尔兰损失表,n,=3,B,=0.01,查表得,=0.455,已知,n,和,怎样求,B,，,线性内插法,；例：,n,=3，,=2.5，由表可知,B,落在 0.20.3 之间，若假设在这区间所负担业务量与,B,成线性关系，则有,线性内插公式,B,2.5,=0.2+(0.3-0.2)(2.5-1.930)/(2.633-1.930)=0.281,5,第5页,例1,M/M/n 损失制无限源系统，已知,n,=3，,=5,人/小时，平均服务时长30分钟/人，试求：(1)系统中没有用户概率；(2)只有一个服务台被占用概率；(3)系统损失率,解,：由题意可知,=60/30=2人/小时，所以,=,/,=2.5Erl,(1),p,0,=(1+2.5+2.5,2,/2+2.5,3,/3!),1,=0.108,(2),p,1,=,p,0,=2.50.108=0.27,(3),B,=,E,3,(2.5)=,p,0,3,/3!=0.108 2.604=0.28,例,2,两市话局间忙时平均呼叫次数为240，每次通话平均时长为 5 分钟，要求两局间中继线服务等级为,B,0.01,问：(1)应配置多少条中继线？(2)中继线群,利用率,为多少？,解,：中继线群上加入话务量为,=240 5/60=,20Erl，,(1)查262页图，,n,=30条；,(2)查爱尔兰表可知：,n,=30，,B,=0.01时可负担 A=20.337，,B,=0.005 时可负担 A=19.034，所以，,E,30,(20)=0.005+0.005,(2019.034)/(20.33719.034)=0.008707,中继线群利用率,=,(1,B,)/,n,=20(1-0.008707)/30=0.660862,6,第6页,服务台利用率与服务台数量关系,n,图,当给定,n,和,B,后，系统所能负担业务量,能够经过爱尔兰公式求出，从而可计算出服务台利用率,；若保持,B,不变，不停增加服务台数,n,，,也会发生改变，就能够得到,n,图以下；经过观察，有几点结论：,1、,B,不变时，,随,n,增加；说明大电路群效率高,2、,n,不变时，,随,B,增加；说明效率与质量是矛盾；(高效路由),3、,含有,边际递减,规律,4、,越大，系统抗过负荷能力越差,7,第7页,系统过负荷特征,B,图,过负荷,是指系统加入业务量,A,超出给定服务质量所能负担业务量,A,过负荷用过载业务量与标准应负担业务量比值来表示，即,=(,A,A,)/,A,=,A,/,A,E,n,(,A,)=,B,E,n,(,A,)=,B,由图可见，在一样标准服务质量和一样过负荷率下，大系统质量劣化严重；说明效率与可靠性是矛盾,8,第8页,例3,某服务部门把用户分为两组，分别组成两个单独服务系统。各系统抵达率分别为,1,=4人/小时，,2,=8人/小时，每人平均占用时长都为 6 分钟；给定损失率为,B,0.01,，试求：(1)分组服务时每组应配置服务台数；(2)合并为一个服务系统时，各种条件不变，应配置服务台数；(3)比较两种组织方式服务台利用率。,解,：(1)分组时：,1,=4 0.1=0.4Erl,2,=8 0.1=0.8Erl,查爱尔兰表，得,n,1,=3台，,n,2,=4台，共需 7台。,B,1,=0.005+0.005(0.40.349)/(0.455 0.349)=0.0074,B,2,=0.005+0.005(0.80.701)/(0.869 0.701)=0.00795,=,1,(1,B,1,)+,2,(1,B,2,)/(,n,1,+,n,2,)=0.17,(2)合组时：,=12 0.1=1.2Erl,查爱尔兰表，得,n,=5台，节约了 2台。,B,=0.005+0.005(1.21.132)/(1.3611.132)=0.006485,=,(1,B,)/,n,=0.238,9,第9页,8.2.1 M/M/n,损失制，有限源,(M/M/n:,N,/,n,/FIFO),例,交换机内部有,n,条绳路，,N,条入中继线，,N,n,；,每条入中继线上呼叫抵达强度为,，且为波松分布，通话时长为负指数分布(参数为,m,)，,问入中继线上呼叫损失率为多少？,上述例子就是一个 M/M/n,损失制，有限源系统。当已经接收绳路服务中继线在通话中，该中继线上就不会有新呼叫。所以，整个系统呼叫抵达率是与系统中被服务中继线数相关。这就是有限源系统特点,显然，系统在各状态下抵达率和离去率分别为,j,=(,N,j,),j,=0,1,.,n,1,n,=0，,j,=,j,j,=1,.,n,将,j,j,代入生灭方程，得,10,第10页,当,j,=,n,时，,p,n,表示按时间计算损失率,下面分析按用户计算损失率,B,B,=单位时间平均损失用户数/单位时间平均抵达用户数,在有限源系统中，用户抵达率随系统状态改变，所以有,平均用户抵达率,，又称为,有效抵达率,11,第11页,可见，在有限源情况下，系统按时间计算损失率,p,n,和按用户计算损失率,B,是不相等；其原因就是输入过程随系统状态而变,从一个极端情况看，若,N,=,n,，则,B,=0，但,p,n,0,即使爱尔兰损失公式和恩格谢特损失公式都是在负指数服务时长假设下推导出来，但已证实服务时间是其它普通平稳分布，结论仍是正确,服务台利用率：,12,第12页,例4,有一电话查询服务处集中回复三个查询点全部查询事项。查询服务处与查询点之间用电话联络。查询服务处只有一名值班员回复全部查询。已知每个查询点平均每小时有两次查询，每次平均通话12分钟，问：(1)值班员空闲概率；(2)值班员打电话概率；(3)查询时值班员忙概率；(4)服务处查询电话平均抵达率；(5)值班员工时利用率。,解,：系统是有限源,M/M/1 损失制。,q,=,/,=(2/60)12=0.4Erl,(1),p,0,=1/(1+,Nq,)=0.4545,13,第13页,8.2 M/M/n 等候制，无限源，无限容量,(M/M/n:,/FIFO),8.2.1,系统稳态概率及,等候概率,令从用户源来用户抵达率为,，每台服务率为,则有,j,=,j,0;,j,=,j,j,n,；,j,=,n,j,n,将,j,j,代入生灭方程，得,14,第14页,当,n,时，则,p,0,中第二项不收敛，系统中队长将趋于无穷,当,0，但在很多情况下我们希望知道等候时长分布，即,P,W,t,系统中有,j,个用户，,j,n,时，新来用户要排队等候，采取FIFO规则；令新用户抵达时为 0 时刻，显然，只有服务台上离去,j,n,个用户时，新用户才排到队首,当,n,个服务台连续服务时，用户离去率为,n,，所以服务台空出过程是,波松流,，在(0,t,),内空出,i,次概率为,17,第17页,等候时长分布推导,18,第18页,例6,某储蓄所内，已知忙时用户抵达率,=40人/小时，窗口营业员服务率为,=16人/小时,，要求：(1)工时利用率不低于 60%；(2)用户平均等候时间不超出 5 分钟；问：设几个窗口适当。,解,：系统是无限源,M/M/,n,等候制。,=,/,=40/16=2.5Erl,(1),=,/,n,0.6，解出,n,4.17，故,n,可取值 3，4,(2),n,=3 时，,p,0,=(1+,+,2,/2!,+,(,3,/3!)(3/(3-2.5),1,=0.045,19,第19页,例7,兴建一座港口码头，只有一个装卸泊位，要求设计泊位生产能力，能力用日装卸船只数表示。已知单位装卸能力日平均生产费用为,a,=元；船只到港后若不能及时装卸，逗留一日要损失运输费,b,=1500元；预计船只平均抵达率为,=3 只/日。设船只抵达间隔时间和装卸时间都服从负指数分布，问港口生产能力设计为多大时，天天总费用最小？,解,：系统是无限源,M/M/1 等候制，生产能力用,(只/日)表示,目标函数：min,C,=,a,+,bL,d,20,第20页,例8,M/M/1 等候制系统,无限队长,用户抵达与队长相关,该系统仍为无限源，但考虑到用户对排队心理，假设用户抵达率与队长成反比关系 即,j,=,0,/(1+,j,)，,0,为队长为 0时用户抵达率,从而系统,j,和,j,为,将,j,和,j,代入生灭方程，得,21,第21页,