运筹学导论之排队论.ppt

《运筹学导论之排队论.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第12章排队系统1AgnerKrarupErlang1878-1929丹麦电信工程师，排队论之父研究人们打电话的方式，发展出人们需要等待多久的公式，并于1909年出版了关于排队理论的第一篇论文2UCLA,LeonardKleinrock1934—“互联网之父”，“影响本世纪的50人”UCLA,JamesR.Jackson1924—2011排队网络之父排队论焕发了新的生命力，影响巨大！3生活在城市中的居民在生产、生活以及学习消费的过程中，存在大量的排队现象，例如，食堂打饭、图书馆借还书、超市收银台、医院等待看病、车辆在信号灯控制路口排队等待通过、在银行柜台前很多顾客等待办理业务、城市中随时可能有

2、急诊病人等待救护车的救援、港口外多艘万吨级船舶等待进港装卸货物、等待加工的零部件、等待装配的汽车等等。排队现象无处不在！12.1为什么要研究排队系统4排队现象的特征是：顾客以某种随机方式到达一个服务设施，之后在队列中等待，直到他们接受服务。一旦服务结束，通常离开系统。不花费极大的成本，等待现象是不可能完全消除的，我们的目标是要把他的不利影响减小到“可以忍受的”程度。56为什么会产生排队现象？泛泛地说，是由于顾客需求量大于设施能提供的服务量。究竟又是什么原因导致服务设施的服务不足？原因很多，例如缺少服务点、提供的更多服务则经济上不可行、空间限制无法容纳更多的服务台。一般来说，当然可以通过增加投资

3、建设更多的服务设施消除上述因素，但这需要分析“应该再增加多少服务台才可以消除排队？”。这就需要回答诸如“一个顾客必须要等待多久？”、“排队长度会有多长？”等很多问题。7例McBurger是一家快餐店，有3个服务柜台。该店的经理委托他人调查顾客对服务速度慢的投诉。调查结果显示，服务台数量与服务等待时间之间有着如下关系：收款台数1234567平均等待时间16.210.36.94.82.91.91.3仔细观察这些数据，在3个柜台的情况下，平均等待时间要7分钟。需要5个柜台才能把等待时间减少到3分钟。排队分析的结果可以用在费用优化模型中，即求两种费用(服务费用和等待费用)之和的最小值。如下图8顾客等待

4、时间成本服务时间成本总费用服务水平费用最优服务水平上图显示了一个典型的费用模型，使用费用模型的主要障碍就是很难估计可靠的等待费用，特别是当人的行为成为操作的有机组成部分时。9分析排队系统的最终目的是为了对排队等待的顾客提供满意的服务。排队论主要研究服务设施的需求与用户延误之间的关系，其在分析和规划城市服务设施扮演重要角色，例如地铁闸机的设置、消防站及消防车的配置以及医疗救护点配置等等；在工业上的用途包括生产线的设计及布置、加工设备的配置；服务业中服务人员、柜台的设置及调配。研究排队论的目的10排队论，作为运筹学的重要分支，并不是一种优化理论。而是用于度量排队系统的性能指标，如队列的平均等待时间

5、和服务设施的效率，这些度量指标可以用来设置服务设施。排队论的重点在于实际中排队分析结果的实施；为了充分理解排队系统的实际问题，就需要了解相当的基础理论背景。为此，首先介绍下构成排队系统的基本要素，然后介绍两个重要分布(泊松和指数分布)的“完全随机”性质。11一个排队系统中的主要参与者是顾客和服务台。顾客从某个输入源产生，到达一个服务设施，他们可以立即得到服务；假如服务设施繁忙，也可能在队列中等待，当一个设施完成一次服务，如果有顾客等待的话，自动地“拉出”一个等待顾客；假如队列为空，设施就变成空闲，直到一个新的顾客到达。从分析队列的角度，我们用连续两个顾客之间的到达时间间隔表示顾客的到达，用对每

6、个顾客的服务时间来描述服务。12.2排队模型的要素12组成排队系统的要素至少包括：顾客输入源、队列以及服务台，而服务台可以是单个的，也可以是多个并行联接的。如果要全面而准确的描述一个排队系统，则需要有如下6个要素：（1）顾客到达模式（顾客发生源类型）；（2）服务台服务模式（服务台服务方式）；（3）排队规则；（4）排队系统容量；（5）服务通道数量；（6）服务阶段数量。1312.2.1顾客到达模式排队系统的顾客输入源常常以单位时间内到达顾客的平均数量（meanarrivalrate），两个连续顾客之间的平均到达间隔时间（meaninterarrivaltime）来描述。进入排队系统的顾客流可以是确

7、定型的，此时完全可以用平均到达率或者平均间隔时间来表示；如果进入排队系统的顾客流存在不确定性，此时用平均到达率或者平均间隔时间，仅能描述输入顾客的随机过程的集体趋势，如果要进一步完整地描述顾客到达模式，则需要顾客到达随机变量的概率分布。顾客到达模式可能不是一次到达一个顾客，而是一批一批到达的，此时相邻批次到达的间隔时间可能是随机的，每批次的顾客数量也是随机的。14不同类型的顾客对于进入排队系统有不