排队论基础及模型(8)

1、1,排队论,教学目的：了解排队论的经济含义；排队系统的一般概念和简单的排队系统；了解排队问题的计算机仿真。,2,学习内容,3,引导案例-1 银行排队系统,4,引导案例-2 医院排队系统,5,形形色色的排队系统,6,为什么会出现排队现象？,假定每小时平均有4位顾客到达，服务人员为每位顾客的平均服务时间为15分钟。如果顾客到达的间隔时间正好是15分钟，而服务人员为每位顾客的服务时间也正好是15分钟，那么，就只需要一名服务人员，顾客也根本用不着等待。 在以下情况将出现排队现象： 平均到达率高于平均服务率 顾客到达的间隔时间不一样（随机） 服务时间不一样（随机）,7,排队问题并不是系统的固定状态，它与

2、系统设计与管理的控制有很大关系。如快餐店只允许很短的队长，也可为特定的顾客留出特定的时间段；也可以通过使用更快的服务人员、机器或采用不同的设施布局和政策来影响顾客的到达时间和服务时间。,8,1 排队论的基本问题1.1 排队论的主要研究内容,数量指标 研究主要数量指标在瞬时或平稳状态下的概率分布及其数字特征，了解系统的基本运行特征。 统计推断 检验系统是否达到平稳状态；检验顾客达到间隔的独立性；确定服务时间分布及参数。 系统优化 系统的最优设计和最优运营问题。,9,1.2 排队论的经济含义,排队问题的核心问题实际上就是对不同因素做权衡决策。管理者必须衡量为提供更快捷的服务（如更多的车道、额外的降

3、落跑道、更多的收银台）而增加的成本和相应的等待造成的费用之间的关系。,10,服务成本与等待成本的权衡（成本效益平衡）,排队分析的目的是使顾客等待成本与服务能力成本这两项成本之和最小,11,2 排队论概述2.1 基本概念,概念 在队列中，等待服务的顾客（customer）和服务台（server）就构成了一个排队系统（queuing system）。 本质 研究服务台与顾客之间服务与接收服务的效率问题。 总体目标 以最少的服务台满足最多的客户需求。,12,2.2 排队系统的一般形式,排队可以是有形的队列，也可以是无形的队列。排队可以是人，也可以是物。,13,3 排队问题的特征,总体来源 到达与服务

4、模式 排队纪律（服务顺序） 服务员数量（通道）,14,3.1 总体来源,分析排队问题所用方法取决于潜在顾客数量是否有限。,本章讨论的重点,15,3.2 顾客到达与服务模式,常用的模型假定顾客到达速度服从泊松分布，服务时间服从指数分布。,16,3.2.1 泊松分布,定义：设 N（t）为时间 0，t 内达到系统的顾客数，如果满足下面三个条件： 平稳性：在 t ，t + t 内有一个顾客达到的概率与t无关； 独立性：在任意两个不相交时间区间内顾客达到相互独立； 普通性：在 t ，t + t内多于一个顾客达到的概率极小，为 ( t )，可以忽略。 则称 N（t），t 0 为Poisson 过程，其对应

5、的分布为泊松分布（ Poisson 分布）。,17,泊松分布的形式,18,泊松分布的概率密度函数,如果一个系统的平均到达率是每分钟有3个顾客到达（ =3），求1分钟内有5个人到达的概率,19,3.2.2 指数分布,当顾客以完全随机的方式到达服务实施时，相邻到达间隔时间服从指数分布，但平均到达率不变； 随机服务时间服从指数分布，但平均服务率不变；,20,（负）指数分布的形式,21,（负）指数分布的概率密度函数,22,表 下一个到达的顾客的时间间隔的概率,23,3.2.3 泊松分布和指数分布的关系,泊松分布与指数分布可以互相推导得到。泊松分布的期望值和方差相等，都为 ；指数分布期望值为1/ ,方差

6、为1/ 2 。 相邻顾客到达时间间隔服从指数分布，单位时间段内到达的顾客数服从泊松分布。,24,3.3 排队纪律/排队规则/服务顺序,排队规则的3种类型,25,等待制的四种类型,26,3.4 服务员数量,排队系统中的常见变形,排队系统,27,排队系统的四种变形-1,单通道 多阶段,服务台,单通道，单阶段,排队,单通道、单阶段排队系统,单通道、多阶段排队系统,排队,服务台,服务台,28,多通道 单阶段,多通道 多阶段,多通道、单阶段排队系统,多通道、多阶段排队系统,排队系统的四种变形-2,29,4 排队模型4.1 排队问题的一般表达方式,一般形式： X / Y / C X 顾客相继达到时间间隔的

7、概率分布； Y 服务时间的概率分布； C服务台的个数；,30,4.2 一些特殊排队模型,指数分布,常数分布,31,4.3 模型符号定义（无限顾客源）,32,系统利用率 正在接受服务的顾客平均数 系统中的平均顾客数 系统中等待的平均顾客数 顾客平均逗留时间 顾客平均等待时间,4.4 模型参数计算-1（ M/M/1）,33,三种重要的关系,“管道原理”: 稳定系统中平均输出= 平均输入（率）= 时间的可加性 在系统中逗留的时间等于服务时间加排队 利特尔法则,34,4.4 模型参数计算-2（ M/G/1 ）,系统利用率 正在接受服务的顾客平均数 系统中等待的平均顾客数 系统中的平均顾客数 顾客平均逗

8、留时间 顾客平均等待时间,常数服务时间能将系统的平均顾客数砍掉一半,35,4.4 模型参数计算-3（ M/M/C）-1,系统利用率 正在接受服务的顾客平均数 系统中等待的平均顾客数 系统中的平均顾客数 顾客平均逗留时间 顾客平均等待时间,36,4.4 模型参数计算-3（ M/M/C）-2,37,例1,一个码头，设待卸货船到达时间间隔服从负指数分布，平均到达 2 艘/小时；服务台是1台吊车，卸货时间服从负指数分布，平均每 20 分钟可卸一艘货船，当被占用时，新到货船只能停在码头等待。求在平稳状态下码头上货船的平均数；等待卸货船只的平均数；每艘货船在码头的平均停留时间；货船平均需等待多长时间可以开

9、始卸货。,38,解：,这是一个典型的M/M/1排队问题,39,例2,某医院手术室根据病人就诊和完成手术时间的记录，任意抽查100个工作小时，每小时来就诊的病人数n的出现次数如表6所示。又任意抽查了100个完成手术的病例，所用时间t出现的次数如下表所示。试分别用公式、excel和仿真求解：,40,到达病人数,手术时间,41,解：,这也是一个M/M/1排队问题 （1）计算平均到达率,平均手术时间,平均服务率,42,（2）取=2.1，=2.5，通过统计检验方法认为病人到达数服从参数为2.1的泊松分布，手术时间服从参数为2.5的指数分布。,（3）服务设备利用率,这说明服务机构（手术室）有84%的时间是

10、繁忙的（被利用），有16%的时间是空闲的。,43,（4）依次带入公式，算出各指标得：,44,单通道仿真视频,45,排队系统仿真软件Flexsim-1,Flexsim是建立在系统理论、控制理论、数理统计、信息技术和计算机技术等理论基础之上的仿真软件，它是系统模型规范化和数字化相结合的过程。,46,排队系统仿真软件Flexsim-2,Flexsim在排队系统中的应用主要是利用仿真模型来研究排队系统，首先通过仿真模型的运行，便于更好的观测排队系统过程中出现的一系列复杂变化和动态过程；其次通过仿真模型稳定后的相关值与排队系统理论值的比较，得出他们的值正好相等。 Flexsim在排队系统中的应用有助于我

11、们进一步理解排队系统的相关概念和加深对排队系统的全面认识，从而对改进排队系统做出正确的举措。,47,单通道Excel求解,48,例3-1,Robot公司在全美经营把加油和汽车冲洗合并在一起的业务。Robot公司对加满油的车辆提供免费冲洗，对于不加油只冲洗的车收费0.5美元。以往的经验表明：加油并且洗车的顾客数和单独洗车的顾客数大致相等。平均加一次油可盈利0.7美元，洗一次车的成本是0.1美元，公司每天营业14小时。 Robot有三档功率和清洗组合不同的设备。选择I档功率时，可以每5分钟洗1辆车，每天的成本是12美元。II档功率高于I档，每4分钟洗1辆车，但每天的成本是16美元；选择III档功率

12、时，每洗1辆车需3分钟，但每天的成本是22美元。,49,例3-2,Robot公司估计，每个顾客洗1辆车不愿等待的时间不超过5分钟，若等待的时间过长，公司将失去顾客。 若估计每小时有10名顾客前来洗车，那么该选择哪档功率的设备？,50,解：,这是一个典型的M/G/1排队问题 （1）选择功率I时,顾客平均等待时间,51,（2）选择功率II时,顾客平均等待时间,如果等待时间是唯一标准，则应选择功率II的设备，但在我们做出最后结论之前，还必须看一下二者的利润差异。,52,(3)对于功率I，由于等待时间为12.5分钟，部分顾客会放弃接受服务。尽管这将使数学分析复杂化，我们仍可以估计出选择功率I时营业额的

13、减少量。我们可以通过假设Wq=5分钟（1/12小时），并从中解得 ，这将是最有效的顾客到达率。,53,因此，既然 的最初估计是10人/小时，则每小时将失去2名顾客。,每天的损失(S)：,而选择功率II，成本只增加了4美元/天，显然，相比较于损失的15.4美元，我们都会选择功率II设备。,功率II能满足最初设定的5分钟等待最大限度，因而功率III可不予考虑，除非 变大。,54,例4 Disneyland乐园中的排队,在游乐园中的频频排队会极为扫兴，Disneyland中的FastPass (QuickPass)系统就是想解决这个问题的。其工作原理如下： 到达的顾客将自己的票插入FastPass的

14、slot中； FastPass计算出建议顾客返回的时间间隔或时间点或时间窗； 顾客无需排队，在指定的时间返回就可持票进入。,55,思考,QuickPass对排队系统的那些特征参数做了改变？ 改变顾客到达模式，是如何影响系统绩效？,56,解：,57,Disneyland问题解决了吗？,如果游客不按时间返回？ 是否让游客等待时间太久了？ 过山车是按时间开还是人数一够就开？,/yaoxie/Pubs_2.htm,58,例5,某售票所有三个窗口，顾客的到达服从泊松分布，平均到达速率 = 0.9人/min；售票时间服从负指数分布，平均服务速率= 0.4人/mi

15、n 。现设顾客到达后排成一队，依次向空闲的窗口购票，如图所示。试分别用公式、excel和仿真求解： (1) 整个售票所空闲概率 (2) 平均队列长和平均队长 (3)平均等待时间和逗留时间 (4)顾客到达后必须等待的概率（n3),59,顾客到达和服务图,60,解：,这是一个典型的M/M/C 排队问题,(1) 整个售票所空闲概率,61,(2) 平均排队长度和平均队列长,(3)平均等待时间和逗留时间,62,(4)顾客到达后必须等待的概率（n3),63,M/M/3仿真视频,64,M/M/3 Excel求解,65,例6 银行取号系统有用吗？,就例5，如果其他条件不变，顾客到达后在每个窗口前各排一队，且进

16、入队列后坚持不换，就形成3个队列，如下图所示。试分别用公式、excel求解： (1) 整个售票所空闲概率 (2) 平均队列长度和平均队长 (3) 平均等待时间和逗留时间 (4)顾客到达后必须等待的概率（n3),66,顾客到达和服务图,67,解：,这是3个M/M/1同时服务的排队问题,(1) 整个售票所空闲概率(每个窗口空闲),(4)顾客到达必须等待的概率（每个窗口n1),68,(2) 平均排队长度和平均队列长,(3)平均等待时间和逗留时间,69,3个M/M/1 Excel求解,70,结论：银行取号系统是有效的,71,结论：银行取号系统是有效的,从这两个系统的主要指标比较可以看出混合排队比独立排

17、队具有显著的优越性，这一点是在排队系统的排队方式的设计时应该注意的。,72,普遍结论：集中使用优于分散使用,将资源组合在一起为所有的顾客提供服务，可以在等待时间不变的条件下，减少所需要的资源总量。如果是两列独立排队，那么客户可能要等那位指定的服务人员提供服务，这位服务人员可能当时正忙得抽不开身，而另一位服务人员却闲着没事干。在集中使用的系统中就不会出现这种现象。 大规模制造或服务设施的规模经济学 在保持同样利用率的情况下减少平均等待时间 在保持同样平均等待时间的情况下提高利用率,73,5 排队系统最优设计成本分析5.1 概述,排队系统的最优设计和最优控制，即排队系统的最优化问题，其目的在于使排

18、队系统达到最大效益或者说在一定指标下使排队系统最为经济。,74,服务成本与等待成本的权衡（成本效益平衡）,排队分析的目的是使顾客等待成本与服务能力成本这两项成本之和最小,75,5.2 M/M/1模型中的最优服务率u -1,最佳服务能力是使总成本最小化：,总成本=顾客等候成本+服务能力成本,76,5.2 M/M/1模型中的最优服务率u -2,所以M/M/1模型的最优服务率为：,77,例7,设某服务机构，单服务台，顾客到达率为每小时12位顾客。假定每位接受顾客的顾客其等待费用为每小时5元，服务成本为每位顾客2元，欲使总平均费用最小，服务率应为多少？,78,解：,这是一个标准的M/M/1排队问题,79,5