排队理论模型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,从而在生灭过程中取,(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/模型系统状态图为,012c-1cc+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)令得而，于是即为最优服务率，这就说明随着发生故障机器数和损失费的增加而增加，随着修理费的增加而减少，合乎情理。,的增加而减少，合乎情理。,由于模型是单服务台系统，得到最优服务率为的理论值，但在实际操作中，设备与工人强度限制达不到此值，所以要讨论模型，根据能达到服务率来确定最佳服务台数。模型最佳服务台数假设发生故障机