排队理论模型.ppt

《排队理论模型.ppt》由会员分享，可在线阅读，更多相关《排队理论模型.ppt（40页珍藏版）》请在三一文库上搜索。

1、 排排队论模型模型 排排队论是是20世世纪初由丹麦数学家初由丹麦数学家Erlang应用数学用数学方法在研究方法在研究电话话务理理论过程中而程中而发展起来的一展起来的一门学学科，排科，排队论也称随机服也称随机服务系系统理理论，它涉及的是建立，它涉及的是建立一些数学模型，以一些数学模型，以对随机随机发生的需求提供服生的需求提供服务的系的系统预测其行其行为，它已，它已应用于用于电讯、纺织、矿山、交通、山、交通、机器机器维修，可靠性，修，可靠性，计算机算机设计和和军事事领域，都已取域，都已取得了得了显著的成著的成绩。一、排一、排队论简介介二、二、实例分析例分析编辑编辑pptppt一、排一、排队论简介介

2、一）基本概念（一）基本概念 1排排队系系统 排排队是指在服是指在服务机构机构处要求服要求服务对象的一个等待象的一个等待队列列 排排队系系统是指一个具有排是指一个具有排队等待等待现象的服象的服务系系统 排排队论是指定量的研究排是指定量的研究排队问题，寻找系找系统内在内在规律，律，寻找找供求关系平衡的最供求关系平衡的最优方案。方案。现实世界中排世界中排队的的现象比比皆是，但有如下共同特征象比比皆是，但有如下共同特征:(1)有有请求服求服务的人或物，如候的人或物，如候诊的病人，的病人，请求着求着陆的的飞机等，机等，我我们将此称将此称为“顾客客”。(2)有有为顾客提供服客提供服务的人或物，如医生、的

3、人或物，如医生、飞机跑道等，我机跑道等，我们称称为“服服务员”。由。由顾客和服客和服务员就就组成服成服务系系统。(3)顾客随机地一个一个客随机地一个一个(或者一批一批或者一批一批)来到服来到服务系系统每位每位顾客客需要服需要服务的的时间不一定确定的，服不一定确定的，服务过程的程的这种随机性造成某个种随机性造成某个阶段段顾客排客排长队，而某些，而某些时间服服务员又空又空闲无事。无事。编辑编辑pptppt2 排排队系系统的特征的特征 为了描述一个了描述一个给定的排定的排队系系统，必，必须规定系定系统的下列的下列组成成 (1)输入入过程程 顾客客陆续来到的来到的过程，程，设N(t):(0，t)时间内

4、来到的内来到的顾客数客数(非非负整数整数值)是随机是随机过程，又程，又设第第i个个顾客到达的客到达的时间，从，从随机随机变量序列，量序列，时间间距距(隔隔)一般假一般假设顾客来到客来到时间间隔隔相互独立与随机相互独立与随机变量量有相同的；有相同的；可以根据原始可以根据原始资料，由料，由顾客到达的客到达的规律、作出律、作出经验分布，分布，检验法法)确定服从哪种理确定服从哪种理论分布，并分布，并概率分布概率分布为负指数分布指数分布(另外有定另外有定长分布分布D，k阶爱尔兰分布分布，一般独立分布，一般独立分布GI等等)而而分布分布然后按照然后按照统计学的方法学的方法(如如估估计它的参数它的参数值。我

5、我们主要主要讨论 (2)服服务机构机构 服服务员对顾客服客服务过程，服程，服务机构可以是一个服机构可以是一个服务员或多个服或多个服务员的。的。对顾客可以客可以单独独进行服行服务，也可以，也可以对成批成批顾客客进行服行服务，在我在我们这儿介儿介绍对顾客客单独独进行服行服务。设C为服服务机构服机构服务员个数，个数，当当C=1时，为单服服务系系统，当，当C2，为多服多服务系系统。和。和编辑编辑pptppt输入入过程一程一样，服，服务时间都是随机的，且我都是随机的，且我们假假设，设表示服表示服务员为n个个顾客提供服客提供服务所需的所需的时间，则服服务服从相互独立的且与某一随机服从相互独立的且与某一随

6、机有相同分布，其中有相同分布，其中根据原始根据原始资料判断得到的，主要有的分布料判断得到的，主要有的分布为负指数分指数分布布(定定长分布，一般独立分布等分布，一般独立分布等)(3)排排队与服与服务规则 顾客排客排队和等待的和等待的规则，排，排队规则一般有等待制，一般有等待制，消失制和混合制。所消失制和混合制。所谓等待制等待制(系系统容量容量就是当一个就是当一个顾客到达客到达时，若所有服，若所有服务台均被占用台均被占用时，该顾客便排客便排队等待服等待服务；消失制也称即；消失制也称即时制制(系系统容量容量D=C)就是服就是服务台被占用台被占用时顾客便即客便即时离去；混合制也离去；混合制也 时间所构

7、成的序列所构成的序列变量量的概率分布是已知的可以的概率分布是已知的可以)有限制有限制(系系统容量容量D:CD0有。有。(1)到达到达(生生):在在(t，t+t)内系内系统出出现一个新的到达的概一个新的到达的概率率为的常数；没有的常数；没有发生新的到达的概率生新的到达的概率；出；出现多于一个以上的新的到达概率多于一个以上的新的到达概率的常数，没有消失的概率的常数，没有消失的概率为消失多于一个以上的概率消失多于一个以上的概率为0(t)则称系称系统状状态随随时间而而变化的化的过程程X(t)为一个生一个生灭过程。程。为为0(t)。(2)消失消失(灭):在在(t，t+t)内，系内，系统消失一个的概率的消

8、失一个的概率的编辑编辑pptppt 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(

9、t)即即应用全概率公式有用全概率公式有编辑编辑pptppt 当当当当 时时 类类似地，当似地，当似地，当似地，当S S为为有限集有限集有限集有限集时时，对对 有有有有 令令令令t0t0得得得得 当系当系当系当系统统状状状状态态S S为为有限集有限集有限集有限集时时，生，生，生，生灭过灭过程的微分差分方程的微分差分方程的微分差分方程的微分差分方 程程程程组为组为 编辑编辑pptppt 当系当系当系当系统统状状状状态态S S为为可数集可数集可数集可数集时时，生，生，生，生灭过灭过程微分差分方程程微分差分方程程微分差分方程程微分差分方程组为组为 (9.2)(9.2)若能求解若能求解若能求解若能求解这

10、组这组方程，方程，方程，方程，则则可得到在可得到在可得到在可得到在时时刻刻刻刻t t系系系系统统状状状状态态概概概概率分布率分布率分布率分布 称称称称为为生生生生灭过灭过程的程的程的程的瞬瞬瞬瞬时时解，一般解，一般解，一般解，一般这这种瞬种瞬种瞬种瞬时时解是解是解是解是难难以求得的以求得的以求得的以求得的编辑编辑pptppt 3.3.统计统计平衡下的极限解平衡下的极限解平衡下的极限解平衡下的极限解 实际应实际应用中，关心的是用中，关心的是用中，关心的是用中，关心的是 时时，方程的解称，方程的解称，方程的解称，方程的解称为为生生生生灭过灭过程微分差分方程程微分差分方程程微分差分方程程微分差分方程

11、组组的极限解。的极限解。的极限解。的极限解。令令令令 及及及及(9.1)(9.2)(9.1)(9.2)式式式式得当得当得当得当S S为为有限状有限状有限状有限状态态集集集集时时，(9.1)(9.1)式式式式变为变为 (9.3)(9.3)当当当当S S为为可数状可数状可数状可数状态态集集集集时时(9.2)(9.2)式式式式变为变为 (9.4 (9.4 从而可以求得概率分布列从而可以求得概率分布列从而可以求得概率分布列从而可以求得概率分布列编辑编辑pptppt（五）、典型排（五）、典型排（五）、典型排（五）、典型排队队模型和理模型和理模型和理模型和理论结论结果果果果 下面下面下面下面给给出出出出满

12、满足生足生足生足生灭过灭过程典型排程典型排程典型排程典型排队队M/M/1M/M/1与与与与M/M/CM/M/C的的的的结结果果果果 (一一一一)单单服服服服务务台等待制台等待制台等待制台等待制M/M/1M/M/1排排排排队队模型模型模型模型 1.M/M/1/1.M/M/1/顾顾客来到的客来到的客来到的客来到的时间间时间间隔隔隔隔 服从参数服从参数服从参数服从参数 的的的的负负指数分布，服指数分布，服指数分布，服指数分布，服务员为顾务员为顾客服客服客服客服务时间务时间 服从参服从参服从参服从参数数数数 的指数分布，且的指数分布，且的指数分布，且的指数分布，且 与与与与 相互独立，相互独立，相互独

13、立，相互独立，1 1个服个服个服个服务务台，系台，系台，系台，系统统容量容量容量容量为为 的等待制排的等待制排的等待制排的等待制排队队模型。模型。模型。模型。可理解可理解可理解可理解为为:单单位位位位时间时间平均到达的平均到达的平均到达的平均到达的顾顾客数客数客数客数-平均到平均到平均到平均到达率达率达率达率 可理解可理解可理解可理解为为:单单位位位位时间时间平均服平均服平均服平均服务务完的完的完的完的顾顾客数客数客数客数-平均平均平均平均服服服服务务率率率率编辑编辑pptppt(1)顾客客输入入过程程是平均率是平均率为的的Poisson过程即程即 设M(t)为(0，t)内容去内容去顾客数，客

14、数，则 的的Poisson分布即分布即 (2)X(t):时刻刻t系系统中的中的顾客数客数 则 L(t):时刻刻t排排队等待等待顾客数客数 则 研究研究X(t)的分布模型的分布模型 令令 编辑编辑pptppt当当 依依赖于于t时，称，称 是瞬是瞬时解解 如果如果 则称称 是是稳定解。定解。此系此系统的状的状态转移移图 图1 0 1 2 n-1 n n+1 从而在生从而在生灭过程中取程中取 (9.5)编辑编辑pptppt记 ，称，称为服服务强度度 当当 时，模型不，模型不稳(时达不到达不到统计)当当 1时，模型，模型稳定，有定，有稳定解定解 (3)X(t)的分布律的分布律 由由(9.12)，(1.

15、15)式得此模型的微分差分方程式得此模型的微分差分方程组 (9.6)当当 时，稳态解解满足足编辑编辑pptppt (9.7)求解求解(9.7)式差分方程，得式差分方程，得 (9.8)(4)结论 平均平均队长 (9.9)平均等待平均等待队长 (9.10)系系统中中顾客数的方差客数的方差 (9.11)编辑编辑pptppt顾客不客不须等待概率等待概率 (9.12)可以可以证明，明，顾客在系客在系统中逗留中逗留时间T服从服从参数参数为的指数的指数 分布，从而分布，从而顾客客在系在系统平均逗留平均逗留时间 (9.13)顾客在系客在系统平均等待平均等待时间 (9.14)从上从上结论可以看出，各指可以看出，

16、各指标之之间有如下关系有如下关系 (9.15)(9.16)(9.15)编辑编辑pptppt(5)(5)简单简单例子例子例子例子 例例例例1(1(病人候病人候病人候病人候诊问题诊问题)某某某某单单位医院的一个科室有一位医位医院的一个科室有一位医位医院的一个科室有一位医位医院的一个科室有一位医生生生生值值班，班，班，班，经长经长期期期期观观察，每小平均有察，每小平均有察，每小平均有察，每小平均有4 4个病人，医生每个病人，医生每个病人，医生每个病人，医生每小小小小时时平均可平均可平均可平均可诊诊5 5个病人，病人的到来服从泊松分布，个病人，病人的到来服从泊松分布，个病人，病人的到来服从泊松分布，个

17、病人，病人的到来服从泊松分布，医生的医生的医生的医生的诊诊病病病病时间时间服从服从服从服从负负指数分布，指数分布，指数分布，指数分布，试试分析分析分析分析该该科室的工科室的工科室的工科室的工作状况，如果作状况，如果作状况，如果作状况，如果满满足足足足99%99%以上的病人有座，此科室至少以上的病人有座，此科室至少以上的病人有座，此科室至少以上的病人有座，此科室至少应设应设多少座位多少座位多少座位多少座位?如果如果如果如果该单该单位每天位每天位每天位每天2424小小小小时时上班，病人看上班，病人看上班，病人看上班，病人看病病病病1 1小小小小时时因耽因耽因耽因耽误误工作工作工作工作单单位要位要位

18、要位要损损失失失失3030元，元，元，元，这样单这样单位平均位平均位平均位平均每天每天每天每天损损失多少元失多少元失多少元失多少元?如果如果如果如果该该科室提高看病速度，每小科室提高看病速度，每小科室提高看病速度，每小科室提高看病速度，每小时时平均可平均可平均可平均可诊诊6 6个病人，个病人，个病人，个病人，单单位每天可减少位每天可减少位每天可减少位每天可减少损损失多少失多少失多少失多少?可减可减可减可减少多少座位少多少座位少多少座位少多少座位?解解解解:由由由由题题意知，意知，意知，意知，从而排，从而排，从而排，从而排队队系系系系统统的的的的稳态稳态概率概率概率概率为为 编辑编辑pptppt

19、 该科室平均有病人数科室平均有病人数为 该科室内排科室内排队候候诊病人数病人数为 看一次病平均所需的看一次病平均所需的时间为 排排队等候看病的平均等候看病的平均时间为 为满足足99%以上的病人有座，以上的病人有座，设科室科室应设m个个座位，座位，则m应满足足 编辑编辑pptppt 所以所以该科室至少科室至少应设20个座位个座位 如果如果该单位位24小小时上班，上班，则每天平均有病人每天平均有病人244=96人，病人看病所花去的人，病人看病所花去的总时间为961=96小小时，因看病平均每天，因看病平均每天损失失3096=2880元，如果医生每小元，如果医生每小时可可诊6个病个病人，人，则 编辑编

20、辑pptppt 这样单这样单位每天的位每天的位每天的位每天的损损失失失失费为费为960.530=1440960.530=1440元，因元，因元，因元，因而而而而单单位每天平均可减少位每天平均可减少位每天平均可减少位每天平均可减少损损失失失失2880-1440=14402880-1440=1440元，元，元，元，这时这时为为保保保保证证99%99%以上的病人有座，以上的病人有座，以上的病人有座，以上的病人有座，应设应设座位数个比原来减座位数个比原来减座位数个比原来减座位数个比原来减少了少了少了少了9 9个。个。个。个。2.M/M/1/k2.M/M/1/k 顾顾客来到的客来到的客来到的客来到的时间

21、间时间间隔服从参数的隔服从参数的隔服从参数的隔服从参数的负负指数分布，服指数分布，服指数分布，服指数分布，服务员为顾务员为顾客服客服客服客服务时间务时间服从参数的指数分布，且相互独服从参数的指数分布，且相互独服从参数的指数分布，且相互独服从参数的指数分布，且相互独立，立，立，立，1 1个服个服个服个服务务台，系台，系台，系台，系统统容量容量容量容量为为k k的等待制排的等待制排的等待制排的等待制排队队模型模型模型模型.因因因因为为是是是是单单服服服服务务台，系台，系台，系台，系统统容量容量容量容量为为k k，即排，即排，即排，即排队队等待的等待的等待的等待的顾顾客最多客最多客最多客最多为为k-

22、1k-1，在某，在某，在某，在某时时刻一刻一刻一刻一顾顾客到达客到达客到达客到达时时，如系，如系，如系，如系统统中已有中已有中已有中已有k k个个个个顾顾客，那么客，那么客，那么客，那么这这个个个个顾顾客就被拒客就被拒客就被拒客就被拒绝进绝进入系入系入系入系统统，所以，所以，所以，所以为为 在生在生在生在生灭过灭过程差分微分方程程差分微分方程程差分微分方程程差分微分方程组组(9.1)(9.1)式中取式中取式中取式中取编辑编辑pptppt 从而得此排从而得此排队模型微分差分方程模型微分差分方程组 (9.17)在在稳态情形下，式情形下，式(9.3)变为 (9.18)编辑编辑pptppt 在条件在条

23、件 下解下解(9.18)式得到式得到 虽然当然当 注意到，注意到，这里，不假里，不假设 条件，由于系条件，由于系统容量有限的限制容量有限的限制 下面下面类似地似地给出系出系统的各种指的各种指标的的计算算结果果 (9.19)编辑编辑pptppt (9.20)(9.20)(9.21)(9.21)(9.22)(9.22)应该应该指出，指出，指出，指出，的的的的导导出出出出过过程中不采用平均达程中不采用平均达程中不采用平均达程中不采用平均达到率到率到率到率 ，而是采用有效到达率，而是采用有效到达率，而是采用有效到达率，而是采用有效到达率 ，这这主要是主要是主要是主要是由于当系由于当系由于当系由于当系统

24、统已已已已满时满时，顾顾客的客的客的客的实际实际到达率到达率到达率到达率为为零，因零，因零，因零，因为为正在被服正在被服正在被服正在被服务务的的的的顾顾客的平均数客的平均数客的平均数客的平均数为为 ，于是，于是，于是，于是 (9.21)编辑编辑pptppt (二二)多服多服务台等待制台等待制M/M/C排排队模型模型 1.M/M/C/顾客来到的客来到的时间间隔服从参隔服从参数的数的负指数分布，服指数分布，服务员为顾客服客服务时间服服从参数的指数分布，从参数的指数分布，C个服个服务台，系台，系统容量容量为的等待制排的等待制排队模型。模型。(1)稳态的概率分布的概率分布 M/M/C/模型系模型系统状

25、状态图为 0 1 2 c-1 c c+1 2 图2编辑编辑pptppt 因此在生因此在生灭过程微分差分方程程微分差分方程组(9.2)式中，式中，令令 得到得到 此模型微分差分方程此模型微分差分方程组 (9.23)显然当然当 有有稳态解，解，类似地似地(9.4)式演式演变(9.24)编辑编辑pptppt 解解(9.24)式差分方程得式差分方程得:（9.25)其中其中(9.26)(2)主要主要结果果 (9.27)(9.28)(9.29)（9.30)编辑编辑pptppt 2.M/M/c/k 顾客来到的客来到的时间间 隔服从参数隔服从参数 的的负指数分布服指数分布服务员为顾客服客服务时间 服服从参数的

26、指数分布，从参数的指数分布，C个服个服务台，系台，系统容量容量为k的等待制排的等待制排队模型模型.因因为是多服是多服务台，系台，系统容量容量为 ，即系，即系统状状态为 时，当，当 时，个服个服务台空台空闲。当。当 时，服，服务台正台正忙着，有忙着，有 个正等候着，在某一个正等候着，在某一时刻一刻一顾客到达客到达时，系，系统中已有中已有 个个顾客，那么客，那么这个个顾客就被拒客就被拒绝进入系入系统。根据此模型的特点，在生根据此模型的特点，在生灭过程微分差分程微分差分方程方程组(9.1)式中取式中取 编辑编辑pptppt得此模型微分差分方程得此模型微分差分方程组(9.31)稳态情况差分方程情况差分

27、方程为(9.32)由由，解式，解式(9.32)差分方程差分方程组得得编辑编辑pptppt(9.33)其中其中(9.34)(9.35)(9.36)(9.37)(9.38)(9.39)编辑编辑pptppt二、二、实例分析例分析 机器机器维修服修服务 （一）（一）问题提出提出机器机器发生故障后排生故障后排队等待修理，等待修理，队伍越伍越长因停因停产造成造成的的损失越大。提高失越大。提高维修工人和修工人和设备的服的服务速度或增加其速度或增加其数量可以减少数量可以减少队长，但将使修理，但将使修理费用上升用上升选择怎怎样的服的服务速度，或者确定几个速度，或者确定几个维修工人和修工人和设备使使损失和修理的失

28、和修理的总费用最小。用最小。（二）建模与分析（二）建模与分析模型模型最最优服服务率率 假假设:(1)发生故障机器生故障机器维修服修服务服从服从M/M/1，平均到达，平均到达率率(单位位时间发生故障的机器数生故障的机器数)为，平均服，平均服务率率(单位位时间平均修理数平均修理数)为，且，且。编辑编辑pptppt(2)(2)每台故障机器每台故障机器每台故障机器每台故障机器单单位位位位时间时间的的的的损损失失失失费费 为为，一台机器，一台机器，一台机器，一台机器平均修理平均修理平均修理平均修理费费 为为。由由由由(1)(1)、(2)(2)假假假假设设，可得，可得，可得，可得单单位位位位时间损时间损失

29、和修理的失和修理的失和修理的失和修理的总费总费用用用用为为 模型即模型即模型即模型即为为 (9.40)(9.40)由由由由 (9.41)(9.41)令令令令 得得得得 而而而而 ，于是，于是，于是，于是 即即即即为为最最最最优优服服服服务务率，率，率，率，这这就就就就说说明明明明 随着随着随着随着发发生故障机器数生故障机器数生故障机器数生故障机器数 和和和和损损失失失失费费的的的的 增加而增加，随着修理增加而增加，随着修理增加而增加，随着修理增加而增加，随着修理费费 的增加而减少，合乎情理。的增加而减少，合乎情理。的增加而减少，合乎情理。的增加而减少，合乎情理。的增加而减少，合乎情理。编辑编辑

30、pptppt 由于模型由于模型是是单服服务台系台系统，得到最，得到最优服服务率率为 的理的理论值，但在，但在实际操作中，操作中，设备与工人与工人强度限制达不到此度限制达不到此值，所以要，所以要讨论模模型型，根据能达到服，根据能达到服务率来确定最佳服率来确定最佳服务台台数。数。模型模型 最佳服最佳服务台数台数 假假设 发生故障机器生故障机器维修服修服务服从服从M/M/C，平均到达率，平均到达率为 ，平均服，平均服务率率为 ，且，且 。每台故障机器每台故障机器单位位时间的的损失失费为 ，单位位时间每个服每个服务员的服的服务成本一名成本一名维修工修工人及人及设备的的费用用)为 。编辑编辑pptppt 由假由假设 、可得模型可得模型 (9.42)其中其中 由由(9.28)式式给出出 因因为C只取整数只取整数值，所以不能用微分法求，所以不能用微分法求 的最小的最小值，利用，利用边际分析方法，当分析方法，当 取取最小最小值应满足足 (9.43)将将(9.43)式代入式式代入式(9.42)并化并化简得得编辑编辑pptppt(9.44)对于于C=1，2，依次依次计算算及及当已知数当已知数满足足(9.45)时即可确定最即可确定最优值。，编辑编辑pptppt