排队论方法讲解课件.ppt

排队论方法讲解简单讲解,排队论方法讲解,服务系统,排队日常生活常见的一种现象,共同特点：在一个排队系统中，进入系统的顾客不能立即得到服务，出现了排队现象。,如：医院病人，商店柜台顾客，公交车乘客,由于被服务者到达系统的时间不确定，故“排队论”又称为“随机服务系统理论”,无形的排队：网络用户，租车方顾客,排队主体是物：生产线产品，维修工待修机器，卫星信息，跑道飞机,排队论方法讲解,1.基本概念,1.排队过程的一般模型,顾客服务过程分为四个步骤：,顾客接受服务后立即离开系统，因此输出过程可以不用考虑,输入过程,排队规则,服务机构,输出过程,排队论方法讲解,IV.顾客到达相互关系,输入过程：,I.顾客总体（顾客源）,II.顾客到来方式,III.顾客到达时间间隔,V.时间间隔分布,有限,无限,一个一个,一批一批,确定型,随机型,相互独立,相互关联,与时间无关（平稳）,与时间有关（非平稳）,排队论方法讲解,III.队列数,排队规则：,I.排队方式,等待制：,II.形状,先到先服，,后到先服，,随机服务，,有优先权服务,损失制,等待制,混合制,有形,无形,容量有限,容量无限,单列,多列,可以互相转移,不能互相转移,即时制,排队论方法讲解,V.服务时间分布,服务机构,I.服务台数目,II.服务台形式,III.服务方式,IV.服务时间,一个,多个,并联,串联,一个一个,一批一批,确定型,随机型,平稳,非平稳,排队论方法讲解,如D/M/10/1000/F,1.2排队论模型的标准形式,标准形式：X/Y/Z/A/B/C,相继到达时间间隔,服务时间的分布,服务台个数,系统容量限制,顾客源数目,服务规则,其中,M,负指数分布,D,确定型分布,Ek,GI,一般相互独立的时间间隔分布,k阶爱尔朗分布,G,一般服务时间的分布,X：,Y：,Z：,A：,B：,C：,FCFS：先到先服,LCFS：后到先服,排队论方法讲解,Q：相对通过能力,1.3排队系统的运行指标,Ls：,队长,Lq：,排队长,Ln：,正在接受服务的顾客数,Ls=Lq+Ln,Ws：,逗留时间,Wq：,排队时间，,服务时间,Ws=Wq+,Tb：,忙期服务机构连续工作时间长度,P损：,损失率，顾客被拒绝服务而使服务部门受损失的概率,服务强度：,A：,平均服务率（绝对通过率）,单位时间内完成服务的顾客数均值,系统中顾客数的期望,系统中等待服务的顾客数,排队论方法讲解,且通常在经过某一时段后即可到达稳态，,1.4系统状态的概率,系统的状态,系统中的顾客数,Ls无限制：,n0，1，2，3，,Ls有限制：,n0，1，2，3，N,服务台个数为c，且服务为即时制，,则n0，1，2，c,Pn(t)=t时刻，状态为n的概率,若,，称为稳态解。,实际中，多数问题都属于稳态情况，,而不需要t,排队论方法讲解,下面分别介绍一下以上3个常用分布：,1.5到达时间的间隔分布和服务时间的间隔分布,常见分布：,1.泊松分布；,2.负指数分布；,3.爱尔朗分布：,排队论方法讲解,若Pn(t1,t2)满足以下三个条件,则称顾客的到达形成泊松流：,1.5.1泊松分布,设N(t)=在时段0,t)内到达的顾客数,Pn(t1,t2)=在时段t1,t2)内有n个顾客到达的概率,则Pn(t1,t2)=PN(t2)-N(t1)=n,排队论方法讲解,(1)无后效性：,在不相交的时间区间内,顾客到达数相互独立，即在t,t+t时段内到达的顾客数，与时刻t之前到达的顾客数无关；,(2)平稳性：,对于充分小的t，在t,t+t内有个顾客到达的概率，只与t有关，而与无关，且,表示单位时间内有一名顾客到来的概率,排队论方法讲解,对于充分小的t，在t,t+t内有2个或多个顾客到达的概率极小,可以忽略不计,即,如果取时间段的初始时刻为t=0.则记,由于,(3)普通性：,排队论方法讲解,故,则在时间段0,t+t)内到达n个顾客的概率为,将0,t+t)分为0,t)和t,t+t),排队论方法讲解,即,令t0,则,特别的,当n=0时,有,排队论方法讲解,解上述两个方程组,可得,其中期望、方差为,由上结果可知,在长度为t的时间段内到达n个顾客的概率,服从泊松分布.,排队论方法讲解,1.5.2负指数分布,当顾客流为泊松流时,用T表示两顾客相继到达的时间间隔,则T是一个随机变量,其分布函数为,排队论方法讲解,类似的,设系统对一个顾客的服务时间v服从负指数分布,分布函数为,密度函数为,则期望值,的泊松流等价,表示平均一个顾客的服务时间,因此v服从负指数分布,与概率强度为,表示平均服务率,即单位时间内的服务人数,2019/12/13,19,可编辑,排队论方法讲解,则称,当k=1时，即为负指数分布,其密度函数为,1.5.3爱尔朗分布,设有如下的顾客流，记k个顾客到达时间间隔序列为v1,v2,v3vk(为相互独立的随机变量),都服从于参数为的负指数分布，,服从k阶爱尔朗分布,因此k阶爱尔朗分布比负指数分布更为广泛,排队论方法讲解,（推导过程略）令,（1）系统状态为n的概率为,2.排队论基本模型,2.1单服务台的排队模型,(1)标准型：M/M/1/,(2)系统容量有限：M/M/1/N/,(3)顾客源有限：M/M/1/m,2.1.1标准型：M/M/1,排队论方法讲解,（2）系统运行指标,（3）运行指标之间的关系,排队论方法讲解,2.1.2系统容量有限M/M/1/N/,（2）系统运行指标,（1）系统状态概率,排队论方法讲解,2.1.3顾客源有限M/M/1/m,（2）运行指标,（1）系统状态平衡方程,排队论方法讲解,2.2多服务台模型,（1）系统状态概率,2.2.1标准型M/M/c/,排队论方法讲解,（2）系统运行指标,排队论方法讲解,2.2.2系统容量有限制M/M/c/N/,系统容量为N，则当系统状态n时，状态平衡方程：,各台服务时间负指数分布，工作相互独立，平均服务率,c个服务台，顾客为Poission流，平均到达率为，,排队论方法讲解,可利用上述方程求解，,其中,更为特殊的M/M/c/c/,排队论方法讲解,2.2.3顾客源有限：M/M/c/m,（2）运行指标,（1）状态平衡方程,排队论方法讲解,3.排队系统的最优化问题,(2)系统控制最优化，,(1)系统设计最优化，,3.1.1最优化问题的分类,3.1一般排队系统的最优化问题,是指在服务系统设置以前，根据一定的质量指标,找出参数的最优值，从而使系统设计最经济。,也称静态最优化,例如服务机构的规模大小，服务台的个数，系统容量的大小；,对已有的排队系统，需求某一最优运营机制，使某目标函数最优,也称动态最优化,排队论方法讲解,3.1.2费用模型,目标函数：,3.2.1标准型：M/M/1,3.2模型M/M/1中的最优服务率,一般说来，提高服务水平自然会降低等待费用，最优化目标之一是使二者的费用之和最小，另一个目标是使服务机构的纯收入最大。,通常所说的费用是指服务机构的服务费和顾客等待的费用。,排队论方法讲解,则，可得到最优解,3.2.2系统容量有限：M/M/1/N/,为单位时间内实际进入服务系统的顾客数,则系统的纯利润为,如果系统中已有N名顾客，PN为被拒绝的概率，1-PN为接受服务的概率，,设系统服务1名顾客收入为G元，于是单位时间收入的期望值为,排队论方法讲解,，求得最优解,最后，将所有已知数值带入，利用数值法求解出,3.2.2顾客源有限的：M/M/1/m,服务机构成本费为Cs,排队论方法讲解,设顾客数为m，单个服务台、服务时间服从负指数分布，当服务率,纯利润为,单位时间内服务完的顾客数为m-Ls，,单位时间内服务完一位顾客收入为G,排队论方法讲解,最优解为,给定Cs，G，m，后，利用泊松分布表和数值法进行计算。,排队论方法讲解,3.2模型M/M/C中的最优服务台数,仅对标准的模型进行讨论。,在稳态的假设下，单位时间内每服务台的成本费为Cs,每个顾客在系统中停留单位