排队论模型-PPT

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,排队论模型,排队论是,20,世纪初由丹麦数学家,Erlang,应用数学方法在研究电话话务理论过程中而发展起来的一门学科，排队论也称随机服务系统理论，它涉及的是建立一些数学模型，以对随机发生的需求提供服务的系统预测其行为，它已应用于电讯、纺织、矿山、交通、机器维修，可靠性，计算机设计和军事领域，都已取得了显著的成绩。,一、排队论简介,二、实例分析,一、排队论简介,（一）基本概念,1,排队系统,排队是指在服务机构处要求服务对象的一个等待队列,排队系统是指一个具有排队等待现象的服务系统,排队论是指定量的研究排队问题，寻找系统内在规律，寻找供求关系平衡的最优方案。,现实世界中排队的现象比比皆是，但有如下共同特征,:,(1),有请求服务的人或物，如候诊的病人，请求着陆的飞机等，我们将此称为“顾客”。,(2),有为顾客提供服务的人或物，如医生、飞机跑道等，我们称为“服务员”。由顾客和服务员就组成服务系统。,(3),顾客随机地一个一个,(,或者一批一批,),来到服务系统每位顾客需要服务的时间不一定确定的，服务过程的这种随机性造成某个阶段顾客排长队，而某些时间服务员又空闲无事。,2,排队系统的特征,为了描述一个给定的排队系统，必须规定系统的下列组成,(1),输入过程,顾客陆续来到的过程，设,N(t):(0,，,t),时间内来到的顾客数,(,非负整数值,),是随机过程，又设,第,i,个顾客到达的时间，从,随机变量序列，,时间间距,(,隔,),一般假设顾客来到时间间隔,相互独立与随机变量,有相同的；,可以根据原始资料，由顾客到达的规律、作出经验分布，,检验法,),确定服从哪种理论分布，并,概率分布为负指数分布,(,另外有定长分布,D,，,k,阶爱尔兰分布,，一般独立分布,GI,等,),而,分布,然后按照统计学的方法,(,如,估计它的参数值。我们主要讨论,(2),服务机构,服务员对顾客服务过程，服务机构可以是一个服务员或多个服务员的。对顾客可以单独进行服务，也可以对成批顾客进行服务，在我们这儿介绍对顾客单独进行服务。设,C,为服务机构服务员个数，当,C=1,时，为单服务系统，当,C2,，为多服务系统。和,输入过程一样，服务时间都是随机的，且我们假设，设,表示服务员为,n,个顾客提供服务所需的时间，则服务,服从相互独立的且与某一随机,有相同分布，其中,根据原始资料判断得到的，主要有的分布为负指数分布,(,定长分布，一般独立分布等,),(3),排队与服务规则,顾客排队和等待的规则，排队规则一般有等待制，消失制和混合制。所谓等待制,(,系统容量,就是当一个顾客到达时，若所有服务台均被占用时，该顾客便排队等待服务；消失制也称即时制,(,系统容量,D=C),就是服务台被占用时顾客便即时离去；混合制也,时间所构成的序列,变量,的概率分布是已知的可以,),有限制,(,系统容量,D:CD0,有。,(1),到达,(,生,):,在,(t,，,t+,t,),内系统出现一个新的到达的概率为,的常数；没有发生新的到达的概率,；出现多于一个以上的新的到达概率,的常数，没有消失的概率为,消失多于一个以上的概率为,0(,t),则称系统状态随时间而,变化的过程,X(t,),为一个生灭过程。,为,为,0(t),。,(2),消失,(,灭,):,在,(t,，,t+t,),内，系统消失一个的概率的,2.,生灭过程微分差分方程组,设,表示系统在时刻,t,的状态,X(t,)=n,的概率即,，,状态为,n,的概率近似于以下四个概率之和。,(1)P,系统在时刻,t,时为,n,，而在,t,内没有到达也没有,消失,=,(2)P,系统在,t,时为,n-1,而在,t,内有一个到达并且没有一,个消失,=,(3)P,系统在,t,时为,n+1,，而在,t,内没有到达而有一个,消失,=,则系统在时刻,t+t,的,(4)P,系统在,t,内发生多于一个的到达或消失,=0(,t),即应用全概率公式有,当 时,类似地，当,S,为有限集时，对 有,令,t0,得,当系统状态,S,为有限集时，生灭过程的微分差分方,程组为,当系统状态,S,为可数集时，生灭过程微分差分方程组为,(9.2),若能求解这组方程，则可得到在时刻,t,系统状态概率分布 称为生灭过程的瞬时解，一般这种瞬时解是难以求得的,3.,统计平衡下的极限解,实际应用中，关心的是 时，方程的解称为生灭过程微分差分方程组的极限解。,令 及,(9.1)(9.2),式得当,S,为有限状态集时，,(9.1),式变为,(9.3),当,S,为可数状态集时,(9.2),式变为,(9.4,从而可以求得概率分布列,（五）、典型排队模型和理论结果,下面给出满足生灭过程典型排队,M/M/1,与,M/M/C,的结果,(,一,),单服务台等待制,M/M/1,排队模型,1.M/M/1/,顾客来到的时间间隔 服从参数 的负指数分布，服务员为顾客服务时间 服从参数 的指数分布，且 与 相互独立，,1,个服务台，系统容量为 的等待制排队模型。,可理解为,:,单位时间平均到达的顾客数,-,平均到达率,可理解为,:,单位时间平均服务完的顾客数,-,平均服务率,(1),顾客输入过程,是平均率为,的,Poisson,过程即,设,M(t,),为,(0,，,t),内容去顾客数，则,的,Poisson,分布即,(2)X(t):,时刻,t,系统中的顾客数,则,L(t,):,时刻,t,排队等待顾客数,则,研究,X(t,),的分布模型,令,当 依赖于,t,时，称 是瞬时解,如果 则称 是稳定解。,此系统的状态转移图,图,1,0 1 2,n-1 n n+1,从而在生灭过程中取,(9.5),记 ，称为服务强度,当 时，模型不稳,(,时达不到统计,),当 ,1,时，模型稳定，有稳定解,(3)X(t),的分布律,由,(9.12),，,(1.15),式得此模型的微分差分方程组,(9.6),当 时，稳态解满足,(9.7),求解,(9.7),式差分方程，得,(9.8),(4),结论,平均队长,(9.9),平均等待队长,(9.10),系统中顾客数的方差,(9.11),顾客不须等待概率,(9.12),可以证明，顾客在系统中逗留时间,T,服从参数为的指数 分布，从而顾客在系统平均逗留时间,(9.13),顾客在系统平均等待时间,(9.14),从上结论可以看出，各指标之间有如下关系,(9.15),(9.16),(9.15),(5),简单例子,例,1(,病人候诊问题,),某单位医院的一个科室有一位医生值班，经长期观察，每小平均有,4,个病人，医生每小时平均可诊,5,个病人，病人的到来服从泊松分布，医生的诊病时间服从负指数分布，试分析该科室的工作状况，如果满足,99%,以上的病人有座，此科室至少应设多少座位,?,如果该单位每天,24,小时上班，病人看病,1,小时因耽误工作单位要损失,30,元，这样单位平均每天损失多少元,?,如果该科室提高看病速度，每小时平均可诊,6,个病人，单位每天可减少损失多少,?,可减少多少座位,?,解,:,由题意知，从而排队系统的稳态概率为,该科室平均有病人数为,该科室内排队候诊病人数为,看一次病平均所需的时间为,排队等候看病的平均时间为,为满足,99%,以上的病人有座，设科室应设,m,个座位，则,m,应满足,所以该科室至少应设,20,个座位,如果该单位,24,小时上班，则每天平均有病人,244=96,人，病人看病所花去的总时间为,961=96,小时，因看病平均每天损失,3096=2880,元，如果医生每小时可诊,6,个病人，则,这样单位每天的损失费为,960.530=1440,元，因而单位每天平均可减少损失,2880-1440=1440,元，这时为保证,99%,以上的病人有座，应设座位数个比原来减少了,9,个。,2.M/M/1/k,顾客来到的时间间隔服从参数的负指数分布，服务员为顾客服务时间服从参数的指数分布，且相互独立，,1,个服务台，系统容量为,k,的等待制排队模型,.,因为是单服务台，系统容量为,k,，即排队等待的顾客最多为,k-1,，在某时刻一顾客到达时，如系统中已有,k,个顾客，那么这个顾客就被拒绝进入系统，所以为,在生灭过程差分微分方程组,(9.1),式中取,从而得此排队模型微分差分方程组,(9.17),在稳态情形下，式,(9.3),变为,(9.18),在条件 下解,(9.18),式得到,虽然当 注意到，这里，不假设,条件，由于系统容量有限的限制,下面类似地给出系统的各种指标的计算结果,(9.19),(9.20),(9.21),(9.22),应该指出，的导出过程中不采用平均达到率 ，而是采用有效到达率 ，这主要是由于当系统已满时，顾客的实际到达率为零，因为正在被服务的顾客的平均数为 ，于是,(9.21),(,二,),多服务台等待制,M/M/C,排队模型,1.M/M/C/,顾客来到的时间间隔服从参数的负指数分布，服务员为顾客服务时间服从参数的指数分布，,C,个服务台，系统容量为的等待制排队模型。,(1),稳态的概率分布,M/M/C/,模型系统状态图为,0 1 2,c-1 c c+1,2,图,2,因此在生灭过程微分差分方程组,(9.2),式中，令,得到,此模型微分差分方程组,(9.23),显然当,有稳态解，类似地,(9.4),式演变,(9.24),解,(9.24),式差分方程得,:,（,9.25),其中,(9.26),(2),主要结果,(9.27),(9.28),(9.29),（,9.30),2.M/M/c/k,顾客来到的时间间 隔服从参数 的负指数分布服务员为顾客服务时间 服从参数的指数分布，,C,个服务台，系统容量为,k,的等待制排队模型,.,因为是多服务台，系统容量为 ，即系统状态为 时，当 时，个服务台空闲。当 时，服务台正忙着，有 个正等候着，在某一时刻一顾客到达时，系统中已有 个顾客，那么这个顾客就被拒绝进入系统。,根据此模型的特点，在生灭过程微分差分方程组,(9.1),式中取,得此模型微分差分方程组,(9.31),稳态情况差分方程为,(9.32),由,，解式,(9.32),差分方程组得,(9.33),其中,(9.34),(9.35),(9.36),(9.37),(9.38),(9.39),二、实例分析,机器维修服务,（一）问题提出,机器发生故障后排队等待修理，队伍越长因停产造成的损失越大。提高维修工人和设备的服务速度或增加其数量可以减少队长，但将使修理费用上升选择怎样的服务速度，或者确定几个维修工人和设备使损失和修理的总费用最小。,（二）建模与分析,模型,最优服务率,假设,:,(1),发生故障机器维修服务服从,M/M/1,，平均到达率,(,单位时间发生故障的机器数,),为,，平均服务率,(,单位,时间平均修理数,),为,，且,。,(2),每台故障机器单位时间的损失费 为，一台机器平均修理费 为。,由,(1),、,(2),假设，可得单位时间损失和修理的总费用为 模型即为,(9.40),由,(9.41),令 得 而 ，于是 即为最优服务率，这就说明 随着发生故障机器数,和损失费的 增加而增加，随着修理费 的增加而减少，合乎情理。,的增加而减少，合乎情理。,由于模型,是单服务台系统，得到最优服务率为 的理论值，但在实际操作中，设备与工人强度限制达不到此值，所以要讨论模型,，根据能达到服务率来确定最佳服务台数。,模型,最佳服务台数,假设 发生故障机器维修服务服从,M/M/C,，平均到达率为 ，平均服务率为 ，且 。,每台故障机器单位时间的损失费为 ，单位时间每个服务员的服务成本一名维修工人及设备的费用,),为 。,。,。,由假设 、可得模型,(9.42),其中 由,(9.28),式给出,因为,C,只取整数值，所以不能用微分法求,的最小值，利用边际分析方法，当 取最小值应满足,(9.43),将,(9.43),式代入式,(9.42),并化简得,(9.44),对于,C=1,，,2,，,依次计算,及,当已知数,满