运筹学排队论2.pptx

第十章 排队论(Queuing theory)n引言n排队论的基本概念n顾客到达数及服务时间的理论分布n单服务台(M/M/1)排队模型n多服务台的排队模型n排队系统费用的优化模型1 引言 排队是日常生活和经济领域中常见的现象.如顾客在邮局,银行排队办理业务,病人在医院排队就医,工厂中等待维修的机床,港口内等候卸货或进港的轮船,机场内等候起飞或降落的飞机,等等.这都是有形的排队现象.打电话时占线,需要等待,这是无形的排队现象.排队是怎样产生的?首先,我们把上述现象中的人或物,看做是被服务队象,他们希望得到某种服务,如果在某个时刻,要求服务的对象超过了服务机构所能提供的服务数量时就产生了排队现象.要减少排队,可以增加服务设施,但是如果增加的太多,服务设施又会出现空闲浪费;如果服务设施少,顾客排队太长时,就会损失顾客也会造成很大损失.因此,决策者必须在服务对象和服务台之间取得平衡,达到一种最优配置.此外,在一些大型项目的设计中(港口泊位,机场跑道,电话线路等),也要根据排队理论作到超前设计,同时还要考虑费用的优化问题,这就是排队论研究的内容.排队论的创始人是丹麦哥本哈根市电话局的工程师爱尔朗(A.K.Erlang),他早期研究电话理论,特别是电话的占线问题,就是早期排队论的内容.2 排队论的基本概念一.排队现象的共同特征:为了获得某种服务而到达的顾客,如不能立即得到服务而又允许排队等候,则加入等待的队伍,获得服务后离开.我们把包含这些特征的系统称为排队系统.排队系统的几种情况:1.单服务台排队系统服务台2.C个服务台,一个公共队伍服务台1服务台2服务台C3.C个服务台,C个队伍服务台1服务台2服务台C二.排队系统的三个组成部分1.输入过程:指顾客按怎样的规律到达.顾客的总体数或顾客源:指可能到达服务机构的顾客总数.顾客总体数可以是有限的,也可以是无限的;顾客到达的类型:顾客是单个到达还是成批到达;顾客相继到达时间间隔的分布,如按泊松分布,定长分布还是负指数分布.2.排队规则:指顾客接受服务的先后次序问题损失制:顾客到达时,服务台被占用,顾客随即离去,不再接受服务;等待制:服务台被占用,顾客排队等候.根据服务台对顾客服务的先后顺序又分为.先到先服务;.后到先服务;.随机服务;.优先权服务.混合制:顾客起初排队,看到队伍太长又离去.3.服务机构:又称服务台服务台的数目:有单服务台,多服务台;任一时刻接受服务的顾客数;服务时间的分布:对每个顾客的服务时间是随机变量,但是其概率分布多按负指数分布来处理,也有的服从定长分布.二.排队系统的描述符号及分类n:排队系统中顾客的数目 :顾客到达的平均速率,即单位时间内到达 的顾客数 :系统的平均服务速率,即单位时间内可服务完的顾客数 :在时刻t时系统中有n个顾客的概率C:服务台的个数FCFS:先到先服务的排队规则LCFS:后到先服务的排队规则PR:优先权服务的排队规则M:到达过程为泊松过程或负指数过程D:定长型分布 :k阶爱尔朗分布a:顾客到达过程的概率分布(输入)b:服务过程的概率分布(输出)d:排队系统的最大容量e:顾客总体的数量f:排队规则1953年由K.D.Kendall提出了排队模型记号方案,由a/b/c/d组成,即输入/输出/并联服务台数/顾客总体数量如:M/M/1/表示:排队系统中顾客到达是泊松过程,服务时间服从负指数分布,单服务台,顾客源无限.1971年国际排队符号标准会上将上述符号扩充到六项,即a/b/c/d/e/f.如:M/M/1/FCFS)M/M/4/N/FCFS)3 顾客到达数及服务时间的理论分布 在排队服务过程中,单位时间内顾客到达数,顾客到达时间间隔,服务时间都是随机变量,因此必须了解它们的概率分布.一.泊松流现将上式参数 引入时间因素 ,即将换为 ,得到表示长为t的时间区间内到达n个顾客的概率为 ,且服从泊松分布.这称为泊松流或泊松过程或简单流.设t时间内到达的顾客数为随机变量N(t),则有二.负指数分布现在研究当输入过程是泊松流时,两顾客先后到达时间间隔T的概率分布.由可知,当n=0时即在0,t内没有顾客到达的概率为 则至少有一个顾客到达的概率分布函数为 相应的概率密度为三.服务时间v的概率分布一般总是假定顾客接受服务的时间v也服从负指数分布负指数分布的一个重要特征是“无记忆性”，也称无后效性或马尔科夫性。这个性质为排队轮问题的求解带来了方便。如果输入分布或服务分布为负指数分布，则不论实际排队过程进行了多长时间，要研究从现在起以后的情况，只要考虑当前排队所处的状况就可以了，在此以前的情况可以不考虑，就好像过程刚开始一样。例9.1 某仓库全天都可以进行发料业务，假设顾客到达的时间间隔服从均值为1的负指数分布现在有一位顾客正好中午12：00到达领料，试求：（1）下一个顾客将在下午1：00前到达的概率；（2）在下午1：00与2：00之间到达的概率：（3）在下午2：00以后到达的概率。解：因为顾客到达间隔时间T服从负指数分布，所以T 的概率密度为取时间起点为中午12:00，则相对时间为 。（1）下一个顾客在下午1：00前到达的概率为（2）顾客在下午1：00到2：00之间到达，则（3）顾客在下午2：00以后到达，则定义:称为服务强度(Traffic intensity).也称为话务强度,这是因为爱尔朗在早期研究排队论时是从研究电话理论开始的.是刻划服务效率和服务机构利用程度的重要标志.当 时,越小,表示单位时间内到达顾客的平均数比服务完的顾客平均数小得多,顾客到达后可及时得到服务,等待时间少,服务员空闲,服务设施利用率低;反之 越大,反映的事实与上述相反.注意:同时满足下面三个条件的流为泊松流无后效性:前面到达的顾客数并不影响后面到达的顾客数;平稳性:顾客到达的多少只与时间间隔有关,而与统计时的时刻无关;普通性:在很短的时间间隔内,到达两个或两个以上顾客的概率极小,可以忽略不计.4 单服务台(M/M/1)模型(M/M/1)模型是指适合下列条件的系统:1.输入过程:顾客源是无限的,顾客单个到达,相互独立,到达数服从泊松分布,到达过程是平稳的;2.排队规则:单队,队长无限制,先到先服务;3.服务机构:单服务台,各顾客服务时间是相互独立的,服从相同的指数分布.一.生灭过程在排队理论中,通常采用一种名为”生灭过程”的方法来描述.首先画出生灭图,它的特点是系统的所有状态看作一系列的点,用0,1,2,表示,并用正,反两方向的箭头线将左右状态连接起来,如下图012nn+1“生”表示顾客的到达,”灭”表示顾客离去.当系统运行一段时间达到平稳状态时,其状态的概率分布为 并标在各状态上.单位时间到达的顾客数为 (即泊松分布的参数 ),标在指向右方的箭头线上方.单位时间服务的顾客数为 (即负指数分布的参数 ),标在指向左方的箭头线下方.箭头线表示状态的转移关系.下面利用生灭图来推导该排队系统的状态概率 (表示系统中有n个顾客的概率).先考虑n=0的状态,状态0的稳定状态概率为而从状态0进入状态1的平均转换率为 ,因此从状态0进入状态1的输出率为 ,同理,状态1进入状态0的输入率为 .根据输出率等于输入率的原则,在系统平衡条件下,对状态0有以下的状态平衡方程 .二.排队系统运行指标1.在排队系统中顾客数的期望值 ,它包含排队等候的顾客和正在接受服务的顾客两部分;2.排队等候顾客数的期望值 ;3.顾客在排队系统中全部时间的期望值 ,它是指顾客排队等待时间与被服务时间之和的期望值;4.顾客排队等待时间的期望值 .三.1.系统状态概率 的计算(表示系统中有n个顾客的概率)2.系统运行指标的计算 的计算 在单服务台情形下,当系统中有顾客时排队等待的顾客数比系统中顾客总数减少1,因此 W的计算顾客在系统中的时间 是一个随机变量,可以证明,在该系统中它服从参数为 的负指数分布,其概率密度为 的计算顾客在队列中排队等待时间的期望值,应等于顾客在系统中全部时间的期望值,减去对顾客服务时间的期望值,注意到服务时间服从参数为 的负指数分布,因此服务时间的期望值为 系统内多于一个顾客的概率系统内多于m个顾客的概率(6)顾客停留时间大于t的概率是顾客在系统中平均排队时间超过t的概率是(7)服务台忙期当 时，忙期随 值得增加而增加，当 时，系统趋于饱和状态，服务台忙碌的均值为在一个忙期内完成服务的平均顾客数为小结:利特尔(J.D.C.Little)公式例9.2 小汽车作过境检查,到达速率为100辆/小时,是泊松流,检查一辆车平均需15秒,为负指数分布,试求稳态概率 及系统的各项指标.解:例9.3 某电话间来打电话的人服从泊松分布,平均每小时24人,每次通话时间为负指数分布,平均2分钟,求设备的各项指标并求电话间有6人(含6人)以上的概率.解:例9.4 虑一个铁路列车编组站，设待编列车到达时间间隔服从负指数分布，平均到达2列/小时；服务台是编组站，编组时间服从负指数分布，平均每20分钟可编一组。已知编组站上共有2股道，当均被占用时，不能接车，再来的列车只能在站外等候。求在平稳状态下系统中列车的平均数；每一列车的平均停留时间；等待编组的列车平均数。当列车在站外停留时，每列车的损失费为a元/小时，求每天由于列车在站外等待而造成的损失。解：看作一个M/M/1/FCFS模型例9.5 在某仓库卸货台装卸设备的设计方案中,有三个方案可供选择,分别记为甲,乙,丙,要求选取使总费用最小的方案.有关数据如下:方案每天固定费用(元)可变操作费(c元/天)平均卸货数(袋/小时甲 60 100 1000乙 130 150 2000丙 250 200 6000设货车按泊松流到达,平均每天(按10小时计算)到达15辆,每车平均装货500袋,卸货时间服从负指数分布,每辆车停留1小时的损失为10元,求总费用最小的方案.解:每个方案的费用综合如下:方案 固定费用可变费用/天停留费用/天总费用/天甲 601000.75=7521015=300300+75+60=435乙 1301500.37556.250.41015=60246.25丙 2502000.125250.0951015=14.25289.25最优决策:乙方案总费用最小.012N-1N四.系统系统特点:泊松输入过程,服务时间为负指数分布,单服务台,系统内只允许有N个顾客,客源无限,先到先服务.同前面的分析一样,系统处于平稳状态时,对于每个状态来说,转入率应等于转出率,在状态0处有在状态1处有 在状态N-1处有 在状态N处有综合以上的结果可推出:称为损失概率,当系统中有N个顾客时,新到的顾客就不进入系统了.因为所有的状态概率之和等于1,所以归纳为排队系统中各种指标的计算:设 表示有效到达率,即实际进入系统的顾客到达速率,则由利特尔公式补充当 时的公式例9.6 某汽车检测站有一条检测线，要求做检测的车辆按泊松流到达，平均每小时6辆，每辆车的检测时间服从负指数分布，平均每辆10分钟，用于等待检测的停车泊位有5个，当无停车泊位时，来检测的车辆自动离去。试计算试计算：1、某车辆一到达就可进行检测的概率；2、等待检测的平均车数；3、每辆车在检测线上等待的期望时间；4、在可能到来的车辆中，有百分之几不等待离开；5、如果车辆因停车泊位全部被占用而离去，每辆车损失a元，求每小时因车辆离去而造成的损失。（北方交大2003年研究生考题，20分）解：例9.7 某加油站只有一个加油管,接待等待加油的汽车.已知站内只能停泊5辆汽车(含正在加油的汽车),后来的汽车不进站而离去.汽车的平均到达速率为4辆/小时,是泊松流.加油时间平均为10分钟/辆,是负指数分布.求1.汽车一到达就能加油的概率;2计算 和 ;3.汽车在站内停留的全部时间的期望值 ;4.因客满而离开加油站的损失概率.解:五.模型 在这个模型中，顾客总数为 ，当顾客需要服务时，就进入队列等待；服务完以后就回到顾客中，如此循环往复。这是一种有限客源服务系统。典型问题是机器维修问题。设有 台机器在运转，单位时间内平均出现故障的机器数即为顾客的平均到达速率 ，修理工维修一台机器的平均时间就是平均服务时间 。不加证明，给出该模型的各种公式：1、系统状态概率的计算2、有限源系统的各项运行指标例9.8一位机修工负责3台机器的维修工作。设每台机器在修理之后平均运行5天，平均修理一台机器的时间为2天，修理时间服从负指数分布。求：1、机修工空闲的概率；2、3台机器都出故障的概率；3、出故障的平均台数及等待维修的平均机器数；4、平均停工时间；5、平均等待维修时间；6、评价这个系统的运行情况。解：5 多服务台排队模型特点:一个公共队伍,并列多服务台(c1).有三种模型.设顾客到达的速率为 ,每个服务台的服务速率均为 ,则整个服务系统的最大服务速率为 ,服务强度为 .各项指标的计算公式如下:一、例9.9 某售票处有三个窗口,顾客到达为泊松流,平均到达率为 服务时间服务负指数分布,平均服务率设顾客到达后排成一列,依次向空闲窗口购票,求各项指标.解:顾客到达后必须等待的概率为现在对(M/M/c)和c个(M/M/1)系统作一个比较,看看哪一个系统更好一些.0.40.40.40.40.40.4仍使用上题的条件,顾客到达后排成三个队,每个队的平均到达率为于是形成了三个(M/M/1)系统,计算出相关数据并与上题进行比较:M/M/3每个M/M/1服务台空闲的概率0.07480.25顾客必须等待的概率 0.570.75平均队长1.70人2.25人总队长3.95人9.00人总的停留时间4.39分10分排队等待时间1.89分7.5分结论:排一个公共队伍比排三个队伍优越.在物流领域中,对同类材料的仓库不应分散建立在各个车间,而应当建立集中的材料库或零件库,避免材料积压占用流动资金.二、模型设系统的容量为 且 ，当系统中的顾客数 时，到达顾客进入系统；当 时，到达的顾客就被拒绝。又设顾客到达速率为 ，每个服务台的服务速率均为 ，则务强度为 ，现在给出系统的状态概率和系统各项运行指标的计算公式。当 时，系统的队列最大长度为0，此时顾客到达时，如果服务台有空闲，则进入服务台接受服务，如果服务台没有空，顾客当即离去。这样的系统称为“即时制”。如旅馆、停车场都具有这种性质。（见P234例9.9）6 排队系统费用的优化模型研究排队系统及其有关参数,可看出排队系统的运行状况,还可以运用这些指标进行决策,排队系统的决策常常是确定服务率,服务台个数和排队规则.为了使顾客排队等待时间缩短,就要增加服务人员和设施,相应地就要增加服务机构费用;相反地,不增加服务人员和设施,就会使顾客排队过长,等待服务的消耗也会增加.因此,必须设计一种各种费用最少的排队系统.关于 系统的优化问题设该系统中服务速率可变,即总费用为例9.10 设汽车按泊松流到达加油站,平均每小时到达5辆,加油站每小时加油 辆汽车,加油时间服务负指数分布,如果汽车停留一小时的费用为1元,加油费为 元,其中求加油站的合理加油能力解:即每小时接待7辆汽车费用最小.7 用WinQSB 解排队论问题