《排队论及其模型精选PPT.ppt》由会员分享，可在线阅读，更多相关《排队论及其模型精选PPT.ppt（171页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、n关于排队论及其模型1第1页，讲稿共171张，创作于星期一2排队论排队论排队论排队论(queuing theory)(queuing theory)也称随机服务系统理论(RandomServiceSystemTheory)，是为研究和解决具有拥挤现象的问题而发展起来的一门应用数学的分支。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。第2页，讲稿共171张，创作于星期一3排队论排队论排队论是1909年由丹麦工程师爱尔朗(A.KErlang)在研究电活系统时创立的，几十年来排队论的应用领域越来越广泛，理论也日渐完善。特别是自二十世纪60年代以来，由于
2、计算机的飞速发展，更为排队论的应用开拓了宽阔的前景。第3页，讲稿共171张，创作于星期一4排队论排队论排队论排队论(queuing theory)(queuing theory)研究内容包括三个部分：n(1)(1)排队系统的性态问题排队系统的性态问题n (2)(2)排队系统的最优化问题排队系统的最优化问题n (3)(3)排队系统的统计推断问题排队系统的统计推断问题性态问题，即研究各种排队系统的概率规律性，主要性态问题，即研究各种排队系统的概率规律性，主要研究队长分布、等待时间分布和忙期分布等。研究队长分布、等待时间分布和忙期分布等。最优化，又分静态最优和动态最优，前者指最优设计，最优化，又分静
3、态最优和动态最优，前者指最优设计，后者指现有排队系统的最优运营。后者指现有排队系统的最优运营。统计推断，即判断一个给定的排队系统符合哪种统计推断，即判断一个给定的排队系统符合哪种模型，以便根据排队理论进行研究。模型，以便根据排队理论进行研究。解排队问题的目的，是研究排队系统运行的效率，估计服务质量，确定系统参数的最优值，以决定系统结构是否合理，研究设计改进措施等。第4页，讲稿共171张，创作于星期一5排队论排队论n第1节基本概念n第2节到达间隔的分布和服务时间的分布n第3节单服务台负指数分布排队系统的分析n第4节多服务台负指数分布排队系统的分析n第5节一般服务时间M/G/1模型n第6节经济分析
4、系统的最优化n第7节分析排队系统的随机模拟法第5页，讲稿共171张，创作于星期一6第第1节节 基基 本本 概概 念念 v1.1排队过程的一般表示v1.2排队系统的组织和特征v1.3排队模型的分类v1.4排队问题的求解第6页，讲稿共171张，创作于星期一7 不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入队列排队等待接受服务，然后服务台按一定规则从队列中选择顾客进行服务，获得服务的顾客立即离开系统。1.1 排队过程的一般表示排队过程的一般表示第7页，讲稿共171张，创作于星期一81.1 排队过程的一般表示排队过程的一般表示v各个
5、顾客由顾客源(总体)出发，到达服务机构(服务台、服务员)前排队等候接受服务，服务完成后离开。v排队结构指队列的数目和排列方式，排队规则和服务规则是说明顾客在排队系统中按怎样的规则、次序接受服务的。排队过程的一般模型排队过程的一般模型第8页，讲稿共171张，创作于星期一91.1 排队过程的一般表示排队过程的一般表示到达的顾客到达的顾客要求服务内容要求服务内容服务机构服务机构1.不能运转的机器2.修理技工3.病人4.电话呼唤5.文件稿6.提货单7.到达机场上空的飞机8.驶入港口的货船9.上游河水进入水库10.进入我方阵地的敌机修理领取修配零件诊断或动手术通话打字提取存货降落装(卸)货装(卸)放水，
6、调整水位我方高射炮进行射击修理技工发放修配零件的管理员医生(或包括手术台)交换台打字员仓库管理员跑道货码头(泊位)水闸管理员我方高射炮形形色色的排队系统 第9页，讲稿共171张，创作于星期一10 实际的排队系统虽然千差万别，但是它们 有以下的共同特征：(1)有请求服务的人或物顾客；(2)有为顾客服务的人或物，即服务员或服务台；(3)顾客到达系统的时刻是随机的，为每一位顾客提供服务的时间是随机的，因而整个排队系统的状态也是随机的。排队系统的这种随机性造成某个阶段顾客排队较长，而另外一些时候服务员(台)又空闲无事。1.2 排队系统的组成和特征排队系统的组成和特征 第10页，讲稿共171张，创作于星
7、期一111.2 排队系统的组成和特征排队系统的组成和特征 v排队系统由三个基本部分组成：输入过程输入过程 排队规则排队规则 服务机构服务机构第11页，讲稿共171张，创作于星期一121.2 排队系统的组成和特征排队系统的组成和特征 输入过程输入过程v输入即指顾客到达排队系统。输入过程是指要求服务的顾客是按怎样的规律到达排队系统的过程，有时也把它称为顾客流。v一般可以从以下几个方面来描述个输入过程(1)顾顾客客的的总总体体数数，又又称称顾顾客客源源、输输入入源源。这这是是指指顾顾客客的的来源。来源。顾客源可以是有限的，也可以是无限的。顾客源可以是有限的，也可以是无限的。例例如如，到到售售票票处处
8、购购票票的的顾顾客客总总数数可可以以认认为为是是无无限限的的，而某个工厂因故障待修的机床则是有限的。而某个工厂因故障待修的机床则是有限的。第12页，讲稿共171张，创作于星期一131.2 排队系统的组成和特征排队系统的组成和特征 输入过程输入过程(2)顾顾客客到到来来的的方方式式。这这是是描描述述顾顾客客是是怎怎样样来来到到系系统统的的，他们是单个到达，还是成批到达。他们是单个到达，还是成批到达。病病人人到到医医院院看看病病是是顾顾客客单单个个到到达达的的例例子子。在在库库存存问问题题中中如如将将生生产产器器材材进进货货或或产产品品入入库库看看作作是是顾顾客客，那那么么这这种顾客则是成批到达的
9、。种顾客则是成批到达的。第13页，讲稿共171张，创作于星期一141.2 排队系统的组成和特征排队系统的组成和特征 输入过程输入过程(3)(3)顾顾客客流流的的概概率率分分布布，或或称称相相继继顾顾客客到到达达的的时时间间间间隔隔的的分分布布。这这是是求求解解排排队队系系统统有有关关运运行行指指标标问问题题时时，首首先先需需要要确确定定的的指指标标。这这也也可可以以理理解解为为在在一一定定的的时时间间间间隔隔内内到到达达K K个个顾客顾客(K K=1=1、2 2、)的概率是多大。的概率是多大。顾顾客客相相继继到到达达的的间间隔隔时时间间可可以以是是确确定定型型的的，也也可可以以是是随随机机型的
10、。型的。顾顾客客流流的的概概率率分分布布一一般般有有定定长长分分布布、二二项项分分布布、泊泊松松流流(最简单流最简单流)、爱尔朗分布等若干种。、爱尔朗分布等若干种。第14页，讲稿共171张，创作于星期一151.2 排队系统的组成和特征排队系统的组成和特征 输入过程输入过程(4)顾客的到达可以是相互独立的。顾客的到达可以是相互独立的。(5)输输入入过过程程可可以以是是平平稳稳的的，或或称称对对时时间间是是齐齐次次的的，即即描描述述相相继继到到达达的的间间隔隔时时间间分分布布和和所所含含参参数数(如如期期望望值值、方方差等差等)都是与时间无关的。都是与时间无关的。第15页，讲稿共171张，创作于星
11、期一161.2 排队系统的组成和特征排队系统的组成和特征 排队规则排队规则v这是指服务台从队列中选取顾客进行服务的顺序。一般可以分为损失制、等待制和混合制等3大类。v(1)损失制。这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来。典型例子是，如电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新拔号，这种服务规则即为损失制。第16页，讲稿共171张，创作于星期一171.2 排队系统的组成和特征排队系统的组成和特征 排队规则排队规则(2)等待制。这是指当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。例如，排队等待售票，故障设
12、备等待维修等。对于等待制，为顾客进行服务的次序可以采用下列各种规则：先到先服务先到先服务(FCFS)后到先服务后到先服务(LCFS)随机服务随机服务(RS)有优先权的服务有优先权的服务第17页，讲稿共171张，创作于星期一181.2 排队系统的组成和特征排队系统的组成和特征 排队规则排队规则(2)等待制。对于等待制，为顾客进行服务的次序可以采用下列各种规则：先到先服务。按顾客到达的先后顺序对顾客进行服务，这是最普遍的情形。后到先服务。仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。随机服务。即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是一例
13、。优先权服务。如老人、儿童先进车站；危重病员先就诊；遇到重要数据需要处理计算机立即中断其他数据的处理等，均属于此种服务规则。第18页，讲稿共171张，创作于星期一191.2 排队系统的组成和特征排队系统的组成和特征 排队规则排队规则(3)混合制这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种：队长有限。当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。例如最多只能容纳K个顾客在系统中，当新顾客到达时，若系统中的顾客数(又称为队长)小于K，则可进入系统排队或接受服务；否则，便离开系统，并不再回
14、来。如水库的库容是有限的，旅馆的床位是有限的。第19页，讲稿共171张，创作于星期一201.2 排队系统的组成和特征排队系统的组成和特征 排队规则排队规则(3)混合制 队长有限。等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。如易损坏的电子元器件的库存问题，超过一定存储时间的元器件被自动认为失效。又如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐。第20页，讲稿共171张，创作于星期一211.2 排队系统的组成和特征排队系统的组成和特征 排队规则排队规则(3)混合制 队长有限。等待时间有限。逗留时间(等待时间与服务时间
15、之和)有限。例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为t时，若在这个时间内未被击落，也就不可能再被击落了。不难注意到，损失制和等待制可看成是混合制的特殊情形，如记s为系统中服务台的个数，则当K=s时，混合制即成为损失制；当K=时，混合制即成为等待制。第21页，讲稿共171张，创作于星期一221.2 排队系统的组成和特征排队系统的组成和特征 排队规则排队规则（续）v从允许排队的空间看队列可以排在具体的处所，也可以是抽象的。队列可以排在具体的处所，也可以是抽象的。排队空间可以有限，也可以无限。排队空间可以有限，也可以无限。v从排队的队列数目看，可以是单列单列，也可以是多列多列。在多
16、列的情形，各列间的顾客有的可以互相转移，有的不能。在多列的情形，各列间的顾客有的可以互相转移，有的不能。有的排队顾客因等候时间过长而中途退出，有的不能退出，必须坚持到被服有的排队顾客因等候时间过长而中途退出，有的不能退出，必须坚持到被服务为止。务为止。第22页，讲稿共171张，创作于星期一231.2 排队系统的组成和特征排队系统的组成和特征 服务机构服务机构(服务台情况)服务台可以从以下3方面来描述：(1)服务台数量及构成形式。服务机构可以没有服务员，也可以有一个或多个服务员(服务台、通道、窗口等)。从数量上说，服务台有单服务台和多服务台之分。在有多个服务台的情形中，可以是平行排列的，也可以是
17、前后排列的，或混合排列的。第23页，讲稿共171张，创作于星期一241.2 排队系统的组成和特征排队系统的组成和特征 服务机构服务机构(服务台情况)服务台可以从以下3方面来描述：(1)服务台数量及构成形式。从构成形式上看，服务台有：单队单服务台式；如(a)图 单队多服务台并联式；如(c)图 多队多服务台并联式；如(b)图 单队多服务台串联式；如(d)图 单队多服务台并串联混合式；多队多服务台并串联混合式等等。服务台的各种服务台的各种排列方式排列方式第24页，讲稿共171张，创作于星期一25单队列S个服务台并联的排队系统S个队列S个服务台的并联排队系统1.2 排队系统的组成和特征排队系统的组成和
18、特征 第25页，讲稿共171张，创作于星期一26单队多个服务台的串联排队系统多队多服务台混联、网络系统1.2 排队系统的组成和特征排队系统的组成和特征 第26页，讲稿共171张，创作于星期一271.2 排队系统的组成和特征排队系统的组成和特征 服务机构服务机构(服务台情况)(2)服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。如公共汽车一次就可装载一批乘客就属于成批服务。(3)服务时间的分布。服务时间可分为确确定定型型和随随机机型型。一般来说，在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K级爱尔良分布、一般分布(所有顾客的服务时间
19、都是独立同分布的)等等。v服务时间的分布通常假定是平稳的。第27页，讲稿共171张，创作于星期一281.3 排队模型的分类排队模型的分类 排队模型分类方法排队模型分类方法D.G.Kendall，1953构成排队模型的三个主要特征指标构成排队模型的三个主要特征指标o(1)相继顾客到达间隔时间的分布；相继顾客到达间隔时间的分布；o(2)服务时间的分布；服务时间的分布；o(3)服务台的个数。服务台的个数。根据这三个特征对排队模型进行分类的根据这三个特征对排队模型进行分类的Kendall记号：记号：X/Y/ZoX：表示相继到达间隔时间的分布；：表示相继到达间隔时间的分布；oY：表示服务时间的分布；：表
20、示服务时间的分布；oZ：并列的服务台的数目。：并列的服务台的数目。第28页，讲稿共171张，创作于星期一291.3 排队模型的分类排队模型的分类 表示相继到达间隔时间和服务时间的各种分布符号表示相继到达间隔时间和服务时间的各种分布符号表示相继到达间隔时间和服务时间的各种分布符号表示相继到达间隔时间和服务时间的各种分布符号vM负指数分布负指数分布(M是是Markov的字头，因为负指数分布具有的字头，因为负指数分布具有无记忆性，即无记忆性，即Markov性性)vD确定型确定型(deterministic)vEkk阶爱尔朗阶爱尔朗(erlang)分布分布vGI 一般相互独立一般相互独立(genera
21、l independent)的时间间隔的分布的时间间隔的分布vG 一般一般(general)服务时间的分布服务时间的分布第29页，讲稿共171张，创作于星期一301.3 排队模型的分类排队模型的分类vKendall符号的扩充 X/Y/Z/A/B/C其中前三项的意义不变，后三项的意义分别是：其中前三项的意义不变，后三项的意义分别是：oA：系统容量限制：系统容量限制N，或称等待空间容量。如系统有，或称等待空间容量。如系统有N个等待位子，则个等待位子，则 0 N 0为一常数，此种的平均服务时间为：K=1时爱尔朗分布化归为负指数分布当K时，得到长度为1/的定长服务。例子：例子：串列的串列的k个服务台，
22、每台服务时间相互独立，服从相同的负指个服务台，每台服务时间相互独立，服从相同的负指数分布数分布(参数参数k)，那么一顾客走完这，那么一顾客走完这k个服务台总共所需要服务时间就服个服务台总共所需要服务时间就服从从k阶爱尔朗分布。阶爱尔朗分布。2.2.3 服务时间的爱尔朗分布服务时间的爱尔朗分布第62页，讲稿共171张，创作于星期一63n第1节基本概念n第2节到达间隔的分布和服务时间的分布n第3节单服务台负指数分布排队系统的分析n第4节多服务台负指数分布排队系统的分析n第5节一般服务时间M/G/1模型n第6节经济分析系统的最优化n第7节分析排队系统的随机模拟法排队论排队论第63页，讲稿共171张，
23、创作于星期一64排队论排队论n排队论研究的首要问题是排队系统主要数量指标的概率规律，即研究系统的整体性质，然后进一步研究系统的优化问题。与这两个问题相关的还包括排队系统的统计推断问题。n(1)通过研究主要数量指标在瞬时或平稳状态下的概率分布及其数字特征，了解系统运行的基本特征。n(2)统计推断问题，建立适当的排队模型是排队论研究的第一步，建立模型过程中经常会碰到如下问题：检验系统是否达到平稳状态；检验顾客相继到达时间间隔的相互独立性；确定服务时间的分布及有关参数等。第64页，讲稿共171张，创作于星期一65n(3)系统优化问题，又称为系统控制问题或系统运营问题，其基本目的是使系统处于最优或最合
24、理的状态。n系统优化问题包括最优设计问题和最优运营问题，其内容很多，有最少费用问题、服务率的控制问题、服务台的开关策略、顾客(或服务)根据优先权的最优排序等方面的问题。n对于一般的排队系统运行情况的分析，通常是在给定输入与服务条件下，通过求解系统状态为n(有n个顾客)的概率Pn(t)，再进行计算其主要的运行指标：排队论排队论第65页，讲稿共171张，创作于星期一66系统中顾客数(队长)的期望值L或Ls；排队等待的顾客数(排队长)的期望值Lq；顾客在系统中全部时间(逗留时间)的期望值W或Ws；顾客排队等待时间的期望值Wq。排队系统中，由于顾客到达分布和服务时间分布是多种多样的，加之服务台数。顾客
25、源有限无限，排队容量有限无限等的不同组合，就会有不胜枚举的不同排队模型，若对所有排队模型都进行分析与计算，不但十分繁杂而且也没有必要。下面拟分析几种常见排队系统模型。排队论排队论第66页，讲稿共171张，创作于星期一67v3.1标准的M/M/1模型(M/M/1/)v3.2系统容量有限的情况(M/M/1/N/)v3.3顾客源有限的情形(M/M/1/m)第第3节节 单服务台负指数分布排队系统的分析单服务台负指数分布排队系统的分析本节讨论输入过程服从普阿松分布过程、服务时间服从负本节讨论输入过程服从普阿松分布过程、服务时间服从负指数分布单服务台的排队系统。指数分布单服务台的排队系统。第67页，讲稿共
26、171张，创作于星期一68v标准的M/M/1模型(1)输入过程输入过程顾客源是无限的，顾客单个到来，相互独立，一定时间顾客源是无限的，顾客单个到来，相互独立，一定时间内的内的到达数服从泊松分布到达数服从泊松分布，到达过程是平稳的。，到达过程是平稳的。(2)排队规则排队规则单队，且对队长没有限制，先到先服务。单队，且对队长没有限制，先到先服务。(3)服务机构服务机构单服务台，各顾客的单服务台，各顾客的服务时间相互独立，服从相同的负指数分布服务时间相互独立，服从相同的负指数分布。此外，还假定到达间隔时间和服务时间是相互独立的。此外，还假定到达间隔时间和服务时间是相互独立的。3.1 标准的标准的M/
27、M/1模型模型(M/M/1/)即已知条件：v：顾客进入系统的平均速度，即单位时间到达的顾客数。v：顾客离开系统的平均速度，即单位时间能被服务完成的顾客数。第68页，讲稿共171张，创作于星期一69v首先要求出：系统在任意时刻t的状态为n(即系统中有n个顾客)的概率，它决定了系统运行的特征。因因已已知知到到达达规规律律服服从从参参数数为为 的的泊泊松松过过程程，服服务务时时间间服服从从参参数数为为 的的负负指指数数分分布，所以在布，所以在 时间区间内分为：时间区间内分为：(1)有有1个顾客到达的概率为个顾客到达的概率为 没有顾客到达的概率就是没有顾客到达的概率就是 (2)当当 有有 顾顾 客客
28、在在 接接 受受 服服 务务 时时，1个个 顾顾 客客 被被 服服 务务 完完 了了(离离 去去)的的 概概 率率 是是 ，没有离去的概率就是，没有离去的概率就是 。(3)多于一个顾客的到达或离去的概率是多于一个顾客的到达或离去的概率是 ，可以忽略。，可以忽略。3.1 标准的标准的M/M/1模型模型(M/M/1/)第69页，讲稿共171张，创作于星期一703.1 标准的标准的M/M/1模型模型(M/M/1/)v在时刻，系统中有n个顾客(n0)存在下列四种情况(到达或离去是2个以上的没列入)：表示发生表示发生(1个个)；表示没有发生。表示没有发生。nn(D)nn-1(C)nn+1(B)nn(A)
29、离去离去到达到达在在时时刻刻 顾顾客数客数在区间在区间在在时时刻刻t顾顾客数客数情况情况第70页，讲稿共171张，创作于星期一71第71页，讲稿共171张，创作于星期一72v这四种情况是互不相容的，所以应是这四项之和，即即v令，得关于的微分差分方程3.1 标准的标准的M/M/1模型模型(M/M/1/)所有的高阶无所有的高阶无穷小和并穷小和并第72页，讲稿共171张，创作于星期一73v当，则只有上表中(A)(B)情况，且方式(A)中无离去的概率为1，即v同理求得v它们的概率分别是o情况情况(A)o情况情况(B)o情况情况(C)o情况情况(D)nn(D)nn-1(C)nn+1(B)nn(A)离去离
30、去到达到达在在时时刻刻 顾顾客数客数在区间在区间在在时时刻刻t 顾顾客数客数情况情况3.1 标准的标准的M/M/1模型模型(M/M/1/)第73页，讲稿共171张，创作于星期一74v研究稳态的情况。这时与时间t无关，可写成，它的导数为0。由(12-15)式和(12-16)式可得v这是关于的差分方程，它表明了各状态间的转移关系：状态0转移到状态1的转移率为，状态1转移到状态0的转移率为。3.1 标准的标准的M/M/1模型模型(M/M/1/)这这种种系系统统状状态态(n)随随时时间间变变化化的的过过程程就就是是生生灭灭过过程程（Birth and Death Process）。）。方程方程(12-
31、15)、(12-16)解是瞬态解，无法应用。解是瞬态解，无法应用。第74页，讲稿共171张，创作于星期一753.1 标准的标准的M/M/1模型模型(M/M/1/)v对状态0必须满足以下平衡方程v同样对任何的状态，可得如(12-18)所示的平衡方程。由(12-17)式可得v将它代入(12-18)式，令，得到v同理依次推得v今设(否则队列将排至无限远)，又由概率的性质知将的关系代入，得到第75页，讲稿共171张，创作于星期一76v对的实际意义的解释/，是平均到达率与平均服务率之比，即在相同时区内顾客到达，是平均到达率与平均服务率之比，即在相同时区内顾客到达的平均数与被服务的平均数之比。的平均数与被
32、服务的平均数之比。若将若将表示为表示为(1/)/(1/)，它是一个顾客的服务时间与到达间隔时间之，它是一个顾客的服务时间与到达间隔时间之比，称比，称为服务强度为服务强度(traffic intensity)，或话务强度。，或话务强度。由由(12-19)式可知，式可知，=1-P0，它刻画了服务机构的繁忙程度，所以，它刻画了服务机构的繁忙程度，所以又称为服务机构的利用率。又称为服务机构的利用率。3.1 标准的标准的M/M/1模型模型(M/M/1/)系统处于空闲状态的概率：系统处于空闲状态的概率：系统处于繁忙状态的概率：系统处于繁忙状态的概率：第76页，讲稿共171张，创作于星期一77v根据平稳分布
33、，求排队系统的有关运行指标(1)系统中的平均顾客数系统中的平均顾客数（平均队长）（平均队长）或或 (2)在队列中等待的平均顾客数在队列中等待的平均顾客数 3.1 标准的标准的M/M/1模型模型(M/M/1/)期望期望第77页，讲稿共171张，创作于星期一78顾客在系统中的逗留时间W(为一个随机变量)在M/M/1情形下，服从参数为的负指数分布，即分布函数概率密度 于是，得到于是，得到(3)在系统中顾客逗留时间的期望值在系统中顾客逗留时间的期望值 (4)在队列中顾客等待时间的期望值在队列中顾客等待时间的期望值 3.1 标准的标准的M/M/1模型模型(M/M/1/)平均逗留时间减去平均逗留时间减去平
34、均服务时间。平均服务时间。第78页，讲稿共171张，创作于星期一79v将以上结果归纳如下：v它们的相互关系如下：上式称为Little公式。3.1 标准的标准的M/M/1模型模型(M/M/1/)第79页，讲稿共171张，创作于星期一803.1 标准的标准的M/M/1模型模型(M/M/1/)Ls,L q,Ws,Wq之间的关系：几何解释：稳态时，一个顾客，进入系统后，每单位时间，平均到达顾客。进入时刻离开时刻总时间Ws队长Ls由时间段内个组成的Ls=Ws同理：Lq=WqWs=Wq+（1/）-Ws与Wq只相差一段平均服务时间1/第80页，讲稿共171张，创作于星期一81例例例例1 1：考虑一个铁路列车
35、编组站。设待编列车到达时间间隔服考虑一个铁路列车编组站。设待编列车到达时间间隔服考虑一个铁路列车编组站。设待编列车到达时间间隔服考虑一个铁路列车编组站。设待编列车到达时间间隔服从负指数分布，平均每小时到达从负指数分布，平均每小时到达从负指数分布，平均每小时到达从负指数分布，平均每小时到达2 2列；服务台是编组站，编组时列；服务台是编组站，编组时列；服务台是编组站，编组时列；服务台是编组站，编组时间服从负指数分布，平均每间服从负指数分布，平均每间服从负指数分布，平均每间服从负指数分布，平均每2020分钟可编一组。已知编组站上共有分钟可编一组。已知编组站上共有分钟可编一组。已知编组站上共有分钟可编
36、一组。已知编组站上共有2 2股道，当均被占用时，不能接车，再来的列车只能停在站外或股道，当均被占用时，不能接车，再来的列车只能停在站外或股道，当均被占用时，不能接车，再来的列车只能停在站外或股道，当均被占用时，不能接车，再来的列车只能停在站外或前方站。前方站。前方站。前方站。求在平衡状态下系统中列车的平均数；求在平衡状态下系统中列车的平均数；求在平衡状态下系统中列车的平均数；求在平衡状态下系统中列车的平均数；每一列车的平均逗留时间；每一列车的平均逗留时间；每一列车的平均逗留时间；每一列车的平均逗留时间；等待编组的列车平均数。等待编组的列车平均数。等待编组的列车平均数。等待编组的列车平均数。如果
37、列车因站中如果列车因站中如果列车因站中如果列车因站中2 2股道均被占用而停在站外或前方站时，每股道均被占用而停在站外或前方站时，每股道均被占用而停在站外或前方站时，每股道均被占用而停在站外或前方站时，每列车每小时费用为列车每小时费用为列车每小时费用为列车每小时费用为a a元，求每天由于列车在站外等待而造成的损元，求每天由于列车在站外等待而造成的损元，求每天由于列车在站外等待而造成的损元，求每天由于列车在站外等待而造成的损失。失。失。失。3.1 标准的标准的M/M/1模型模型(M/M/1/)第81页，讲稿共171张，创作于星期一82解：本例可看成一个解：本例可看成一个M/M/1/排队问题，其中排
38、队问题，其中 =2，=3，=/=2/32=W1-P0 0-P1-P-P2=W1-(=W1-(l-)-(l-l-)1 1-(l-l-)2 2=1*=1*3=3=(2/3)=(2/3)3 3=0.296=0.296（小时）（小时）（小时）（小时）故每天列车由于等待而支出的平均费用故每天列车由于等待而支出的平均费用故每天列车由于等待而支出的平均费用故每天列车由于等待而支出的平均费用E=24E=24 WW0 0a=24*2*0.296*a=14.2aa=24*2*0.296*a=14.2a元元3.1 标准的标准的M/M/1模型模型(M/M/1/)第83页，讲稿共171张，创作于星期一84例例例例2：某
39、修理店只有一位修理工，来修理的顾客到达过程为某修理店只有一位修理工，来修理的顾客到达过程为某修理店只有一位修理工，来修理的顾客到达过程为某修理店只有一位修理工，来修理的顾客到达过程为PoissonPoisson流，平均每小时流，平均每小时4人；修理时间服从负指数分人；修理时间服从负指数分人；修理时间服从负指数分人；修理时间服从负指数分布，平均需要布，平均需要布，平均需要布，平均需要6 6分钟。分钟。试求：修理店空闲的概率；店内恰有试求：修理店空闲的概率；店内恰有试求：修理店空闲的概率；店内恰有试求：修理店空闲的概率；店内恰有3 3位顾客的概率；店位顾客的概率；店位顾客的概率；店位顾客的概率；店
40、内至少有一位顾客的概率；在店内平均顾客数；每位内至少有一位顾客的概率；在店内平均顾客数；每位内至少有一位顾客的概率；在店内平均顾客数；每位内至少有一位顾客的概率；在店内平均顾客数；每位在店内平均逗留时间；等待服务的平均顾客数；每位在店内平均逗留时间；等待服务的平均顾客数；每位在店内平均逗留时间；等待服务的平均顾客数；每位在店内平均逗留时间；等待服务的平均顾客数；每位顾客平均等待服务时间；顾客在店内等待时间超过顾客平均等待服务时间；顾客在店内等待时间超过顾客平均等待服务时间；顾客在店内等待时间超过顾客平均等待服务时间；顾客在店内等待时间超过10分钟的概率。分钟的概率。分钟的概率。分钟的概率。3.
41、1 标准的标准的M/M/1模型模型(M/M/1/)第84页，讲稿共171张，创作于星期一85解：本例可看成一个解：本例可看成一个M/M/1/排队问题，其中排队问题，其中 =4，=1/0.1=10(人人/小时），小时），=/=2/510=e-10(1/6-1/15)=e-1=0.3677PTt=e-(-)tt=10分钟分钟,=10人人/小时小时=10/60=1/6 =4人人/小时小时=4/60=1/153.1 标准的标准的M/M/1模型模型(M/M/1/)第88页，讲稿共171张，创作于星期一89v例3某医院手术室根据病人来诊和完成手术时间的记录，任意抽查了100个工作小时，每小时来就诊的病人数
42、n的出现次数如下表所示；又任意抽查了100个完成手术的病历，所用时间v(单位：小时)出现的次数如下表所示。到达的病人数n出现人数0101282316410566以上以上1合计合计100为病人完成手术时间v(小时)出现人数0.00.2380.20.4250.40.6170.60.890.81.061.01.251.2以上以上0合计合计1003.1 标准的标准的M/M/1模型模型(M/M/1/)第89页，讲稿共171张，创作于星期一90v(1)每小时病人平均到达率(人/小时)每次手术平均时间(小时/人)每小时完成手术人数(平均服务率)(人/小时)v(2)取，可以通过统计检验的方法，认为病人到达数服
43、从参数为2.1的泊松分布，手术时间服从参数为2.5的负指数分布。v(3)说明服务机构(手术室)有84%的时间是繁忙的，有16%的时间是空闲的。v(4)依次代入(12-21)式，算出各指标：在病房中病人数在病房中病人数(期望值期望值)(人人)排队等待病人数排队等待病人数(期望值期望值)(人人)病人在病房中逗留时间病人在病房中逗留时间(期望值期望值)(小时小时)病人排队等待时间病人排队等待时间(期望值期望值)(小时小时)3.1 标准的标准的M/M/1模型模型(M/M/1/)第90页，讲稿共171张，创作于星期一91v如果系统的最大容量为N，对于单服务台的情形，排队等待的顾客最多为N-1，在某时刻一
44、顾客到达时，如系统中已有N个顾客，那么这个顾客就被拒绝进入系统。v当N=1时为即时制的情形；当N时为容量无限制的情形。3.2 系统的容量有限制的情况系统的容量有限制的情况(M/M/1/N/)第91页，讲稿共171张，创作于星期一92泊松输入负指数分布服务的排队系统的一般决策过程：根据已知条件绘制状态转移速度图；依据状态转移速度图写出各稳态概率之间的关系；求出 P0 及 Pn；计算各项数量运行指标；用系统运行指标构造目标函数，对系统进行优化。3.2 系统的容量有限制的情况系统的容量有限制的情况(M/M/1/N/)第92页，讲稿共171张，创作于星期一933.2 系统的容量有限制的情况系统的容量有
45、限制的情况(M/M/1/N/)v稳态情形下各状态间概率强度的转换关系图v状态概率的稳态方程 第93页，讲稿共171张，创作于星期一943.2 系统的容量有限制的情况系统的容量有限制的情况(M/M/1/N/)v稳态情形下各状态间概率强度的转换关系图v状态概率的稳态方程其中(12-23a)也可写成，则有第94页，讲稿共171张，创作于星期一953.2 系统的容量有限制的情况系统的容量有限制的情况(M/M/1/N/)由 N(/)nP0=1n=0 NP0=1/(/)n=n=0(1-(1-/)/)/(1-(1-(/)N N+1+1 1/(1/(N N+1)+1)=Pn=1/(N+1)=(1-(1-/)(
46、)(/)n n/(1-(/(1-(/)N N+1+1 第95页，讲稿共171张，创作于星期一96vM/M/1/N/排队系统的各项指标：v(1)队长(期望值)v(2)队列长(期望值)v(3)顾客逗留时间(期望值)v(4)顾客等待时间(期望值)v(5)有效到达率3.2 系统的容量有限制的情况系统的容量有限制的情况(M/M/1/N/)v令，得到第96页，讲稿共171张，创作于星期一97(1,(1,nN)nN)(1)平均队长平均队长Ls：(1)试证试证=1=1时时,Ls=N/2,Ls=N/23.2 系统的容量有限制的情况系统的容量有限制的情况(M/M/1/N/)第97页，讲稿共171张，创作于星期一9
47、8?vM/M/1/N/排队系统的各项指标：v(1)队长(期望值)v(2)队列长(期望值)v(3)顾客逗留时间(期望值)v(4)顾客等待时间(期望值)v(5)有效到达率3.2 系统的容量有限制的情况系统的容量有限制的情况(M/M/1/N/)v令，得到返回返回P98第98页，讲稿共171张，创作于星期一99 (2)有效到达率有效到达率e 系统容量有限，当满员（系统容量有限，当满员（n=N）时时，顾客将被拒绝，实际的顾客到达率与，顾客将被拒绝，实际的顾客到达率与不一样，不一样，还可验证：还可验证：此种情况的公式与前类似此种情况的公式与前类似,只有只有Ls不同不同,e与与 不同。求不同。求e必须先求得
48、必须先求得P0或或PN才行。才行。有效到达率为有效到达率为e 可以证明：可以证明：LsLs3.2 系统的容量有限制的情况系统的容量有限制的情况(M/M/1/N/)第99页，讲稿共171张，创作于星期一100vM/M/1/N/排队系统各项指标的归纳(当时)：3.2 系统的容量有限制的情况系统的容量有限制的情况(M/M/1/N/)第100页，讲稿共171张，创作于星期一101例例2某某单单人人理理发发馆馆共共有有六六把把椅椅子子接接待待顾顾客客排排队队，无无座座时时将将离离去去，顾客平均到达率为顾客平均到达率为3人人/h，理发时间平均为，理发时间平均为15分钟，求：分钟，求：(1)求某一顾客到达就
49、能理发的概率求某一顾客到达就能理发的概率;(2)求需要等待的顾客数的期望值求需要等待的顾客数的期望值;(3)求有效到达率求有效到达率;(4)求一顾客在系统中的逗留时间和排队时间平均值求一顾客在系统中的逗留时间和排队时间平均值;(5)在可能到来的顾客中，有百分之几不等待就离开？在可能到来的顾客中，有百分之几不等待就离开？3.2 系统的容量有限制的情况系统的容量有限制的情况(M/M/1/N/)第101页，讲稿共171张，创作于星期一102(1)求某一顾客到达就能理发的概率求某一顾客到达就能理发的概率:(2)求需要等待的顾客数的期望值求需要等待的顾客数的期望值:(3)求有效到达率求有效到达率:(4)
50、求一顾客在系统中的逗留时间和排队时间平均值求一顾客在系统中的逗留时间和排队时间平均值:3.2 系统的容量有限制的情况系统的容量有限制的情况(M/M/1/N/)第102页，讲稿共171张，创作于星期一103P0=0.27780P1=0.20836P2=0.15627P3=0.11720 =0.9629=96.29%1-0.9629=3.71%P4=0.08790P5=0.06593P6=0.04944(5)在可能到来的顾客中，有百分之几不等待就离开？在可能到来的顾客中，有百分之几不等待就离开？顾客为何不等待顾客为何不等待就离去？就离去？因为系统已因为系统已经满员经满员3.2 系统的容量有限制的情