排队论模型.ppt

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