第14章 排队论.ppt

第十四章 排队论,一、问题引入与分析,二、排队论的基本概念,三、几类排队论模型,四、模型的建立与求解,1.2001年全国数学竞赛的B题“公交车调度”,某条公交线路上行方向共14站，下行方向共,13站.公交公司配给该线路同一型号的大客车，每,辆标准载客100人，据统计客车在该线路上运行的,平均速度为20公里/小时.运营调度要求，乘客候车,时间一般不要超过10分钟，早高峰一般不要超过,是这样的：,一、问题引入与分析,5分钟，车辆满载率不应超过120%，一般也不要,低于50%.,试根据这些材料和要求，为该线路设计一个,便于操作的全天（工作日）的公交车调度方案,包括两个起点站的发车时刻表；一共需要多少,辆车；这个方案以怎样的程度照顾到了乘客和,公交公司双方的利益；等等.,2.问题分析：,对于第一个问题，关于公交车的调度方案，,可以利用各种的不同的方法，比如多目标规划，,去求得在一定原则下的最优方案，得到一个满足,实际情况的分配方案，但要建立具体的明确、完,整的数学模型，以及求解模型的方法，如何采集,运营数据是关键的.在实际中，公交车具有随机,性，特别是顾客的到来是随机的，是无法精确预,测的，这就决定了公交车的数量并不是完全确定,的固定不变的，而是随着不同时段顾客的多少而,变化.因此顾客和公交车之间存在随机因素.,很明显，顾客和公交车是一个服务和被服务,的关系.如果公交车数量过多，也就是已有的资,源大于需求，虽然公交车的数量能够满足顾客,需求，减少了顾客排队等待的时间，公交车提供,的服务使顾客的满意度很高，却会造成公交车公,司的浪费，比如某一时段某一线路所发公交车上没,有顾客或很少的顾客，个别时段个别线路如此，公,交车公司也许可以接受，但长时间的空跑或入不敷,出，最终会使公交车公司不堪重负，甚至倒闭；另,一方面，如果公交车数量较少，很多顾客得不到服,务，或者很多顾客花了很长的时间去排队等候，造,成顾客的不满意度提高，这样公交车公司会失去顾客.,如何考虑随机因素，设计合理方案，建立数学模,型，一方面提供服务的服务机构即公交公司的线,路设计合理，能够赢得顾客，获得利益；另一方,面被服务的顾客能够在被服务的过程中，排队等,候的时间最短，这都是上述问题要解决的，也是,排队论的主要研究内容.,二、排队论的基本知识,2.排队系统描述,3.基本组成部分,4.数量指标,5.排队模型的记号,1.背景介绍,1.背景介绍,排队论是研究排队现象的理论和应用的学科，是,专门研究由于随机因素影响而产生的拥挤现象的科学.,20世纪初丹麦数学家、电气工程师爱尔朗把概率论应,用于电话通话问题，从而开创了这门应用数学科学.,20世纪30年代中期，费勒引进了生灭过程，排队论,才被数学界承认为一门重要的学科.20世纪40年代排,对论在运筹学这个新领域中成了一个重要的部分.20,世纪50年代初肯德尔对排对论作了系统的研究，他用,马尔科夫链方法研究排队论，使排队论得到进一步发,展.20世纪60年代起排队论研究的课题日趋复杂，很,多问题很难求得精确解，因此开始了近似方法的研究.,排队论应用范围很广，它适用于一切服务系统.尤,其在通信系统、交通系统、计算机存储系统和生产管理,系统等方面应用的最多.,排队是日常生活和工作中常见的现象.例如等公共,汽车排队，到商店购物排队，交款排队，到医院看病,等待排队，买火车票排队，托运行李排队，取货排队，,这是人的排队.还有另一种排队，例如文件等待打印或,发送，报告等首长批示，路口红红灯下的汽车、自行车,等待通过路口，这是物或设备排队.,总之，凡是具有公共服务性质的事业和工作，凡,是出现拥挤现象的领域，都是排队论的用武之地.,2.排队系统描述,排队系统又称为随机服务系统，是研究服务,请求服务的人或者物顾客；,排队系统的共同特征：,顾客到达系统的时刻是随机的，为每一位顾客,有为顾客服务的人或者物，即服务员或服务台；,过程和拥挤现象的随机模型.,提供服务的时间是随机的，因而整个排队系统,的状态也是随机的.,排队系统的几种形式：,基本排队过程：,从图66可知，每个顾客由顾客源按一定方式,到达服务系统，首先加入队列排队等待接受服务，,然后服务台按一定规则从队列中选择顾客进行服,务，获得服务的顾客立即离开.,排队论所要研究解决的问题：,面对拥挤现象，人们通常的做法是增加服务设施,但是增加的数量越多，人力、物力的支出就越大，甚,至会出现空闲浪费，如果服务设施太少，顾客排队等,待的时间就会很长，这样对顾客会带来不良影响.如,何做到既保证一定的服务质量指标，又使服务设施费,用经济合理，恰当地解决顾客排队时间与服务设施费,用大小这对矛盾，就是随机服务系统理论排队论,所要研究解决的问题。,3.排队系统的基本组成部分,排队系统是由输入过程、排对规则和服务机构组成.,(1).输入过程 指要求服务的顾客是按怎样的规律,(i)顾客总体数.又称顾客源、输入源.这是指顾客,(ii)顾客到达方式.这是描述顾客是怎样来到系统,到达排队系统的过程，有时也把它称为顾客流.一,般可以从3个方面来描述个输入过程.,的来源.顾客源可以是有限的，也可以是无限的.,的，是单个到达，还是成批到达.,(iii)顾客流的概率分布.或称相继顾客到达的时间,间隔的分布.这是求解排队系统有关运行指标问题,时，首先需要确定的指标.顾客流的概率分布一般,有定长分布、二项分布、泊松流(最简单流)、爱尔,朗分布等若干种.,(2).排对规则 指服务台从队列中选取顾客进行,(i)损失制 指如果顾客到达排队系统时，所有,服务的顺序.一般可以分为损失制、等待制和混,合制等3大类.,服务台都被先到的顾客占用，那么他们就自动,离开系统永不再来.,(ii)等待制 指当顾客来到系统时，所有服务台,a.先到先服务 按顾客到达的先后顺序对顾客,b.先到后服务,c.随机服务 即当服务台空闲时，不按照排队,d.优先权服务,都不空，顾客加入排队行列等待服务.等待制中，,服务台在选择顾客进行服务时常有如下四种规则：,进行服务.,序列而随意指定某个顾客接受服务.,(iii)混合制 这是等待制与损失制相结合的一种服,a.队长有限.当排队等待服务的顾客人数超,b.等待时间有限.即顾客在系统中的等待时,c.逗留时间(等待时间与服务时间之和)有限.,务规则，一般是指允许排队，但又不允许队列无限,长下去.具体说来，大致有三种：,过规定数量时，后来的顾客就自动离去，另,求服务，即系统的等待空间是有限的.,间不超过某一给定的长度T，当等待时间超,过T时，顾客将自动离去，并不再回来.,(3).服务机构,(i)服务台数量及构成形式.从数量上说，服务台有单,(ii)服务方式.这是指在某一时刻接受服务的顾客数，,(iii)服务时间的分布.在多数情况下，对每一个顾客的,服务台和多服务台之分.从构成形式上看，服务台有：,单队一-单服务台式；单队一-多服务台并联,式；多队一-多服务台并联式；单队一-多服,务台串联式；单队一-多服务台并串联混合式，,以及多队多服务台并串联混合式等等.,它有单个服务和成批服务两种.,服务时间是一随机变量.,4.排队系统的主要数量指标,排队论主要研究系统的性态，即与排队有关,(1).排队系统主要数量指标,等待时间、忙期、队长.,的数量指标的概率规律性；系统的优化问题；统,计推断，根据资料合理建立模型.目的是正确设,计和有效运行各个服务系统，使之发挥最佳效益.,所以必须确定判断系统运行优劣的基本数量指标.,(i).等待时间 从顾客到达时刻起到他开始接受服务止这,(ii).忙期 忙期是指从顾客到达空闲着的服务机构起，到,(iii).队长 队长是指系统中的顾客数(排队等待的顾客数与,段时间称为等待时间.等待时间是个随机变量.从顾客,到达时刻起到他接受服务完成止这段时间称为逗留时,间，也是随机变量.,服务机构再次成为空闲止的这段时间，即服务机构连续忙,的时间.这是个随机变量，是服务员最为关心的指标，因,为它关系到服务员的服务强度.与忙期相对的是闲期,即,服务机构连续保持空闲的时间.在排队系统中，忙期和闲,期总是交替出现的.,