排队论基础及模型.ppt

1 排队论 教学目的 了解排队论的经济含义 排队系统的一般概念和简单的排队系统 了解排队问题的计算机仿真 2 学习内容 3 引导案例 1银行排队系统 4 引导案例 2医院排队系统 5 形形色色的排队系统 6 为什么会出现排队现象 假定每小时平均有4位顾客到达 服务人员为每位顾客的平均服务时间为15分钟 如果顾客到达的间隔时间正好是15分钟 而服务人员为每位顾客的服务时间也正好是15分钟 那么 就只需要一名服务人员 顾客也根本用不着等待 在以下情况将出现排队现象 平均到达率高于平均服务率顾客到达的间隔时间不一样 随机 服务时间不一样 随机 7 排队问题并不是系统的固定状态 它与系统设计与管理的控制有很大关系 如快餐店只允许很短的队长 也可为特定的顾客留出特定的时间段 也可以通过使用更快的服务人员 机器或采用不同的设施布局和政策来影响顾客的到达时间和服务时间 8 1排队论的基本问题1 1排队论的主要研究内容 数量指标研究主要数量指标在瞬时或平稳状态下的概率分布及其数字特征 了解系统的基本运行特征 统计推断检验系统是否达到平稳状态 检验顾客达到间隔的独立性 确定服务时间分布及参数 系统优化系统的最优设计和最优运营问题 9 1 2排队论的经济含义 排队问题的核心问题实际上就是对不同因素做权衡决策 管理者必须衡量为提供更快捷的服务 如更多的车道 额外的降落跑道 更多的收银台 而增加的成本和相应的等待造成的费用之间的关系 10 服务成本与等待成本的权衡 成本 效益平衡 排队分析的目的是使顾客等待成本与服务能力成本这两项成本之和最小 11 2排队论概述2 1基本概念 概念在队列中 等待服务的顾客 customer 和服务台 server 就构成了一个排队系统 queuingsystem 本质研究服务台与顾客之间服务与接收服务的效率问题 总体目标以最少的服务台满足最多的客户需求 12 2 2排队系统的一般形式 排队可以是有形的队列 也可以是无形的队列 排队可以是人 也可以是物 13 3排队问题的特征 总体来源到达与服务模式排队纪律 服务顺序 服务员数量 通道 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过程 其对应的分布为泊松分布 Poisson分布 17 泊松分布的形式 18 泊松分布的概率密度函数 如果一个系统的平均到达率是每分钟有3个顾客到达 3 求1分钟内有5个人到达的概率 19 3 2 2指数分布 当顾客以完全随机的方式到达服务实施时 相邻到达间隔时间服从指数分布 但平均到达率不变 随机服务时间服从指数分布 但平均服务率不变 20 负 指数分布的形式 21 负 指数分布的概率密度函数 22 表下一个到达的顾客的时间间隔的概率 23 3 2 3泊松分布和指数分布的关系 泊松分布与指数分布可以互相推导得到 泊松分布的期望值和方差相等 都为 指数分布期望值为1 方差为1 2 相邻顾客到达时间间隔服从指数分布 单位时间段内到达的顾客数服从泊松分布 24 3 3排队纪律 排队规则 服务顺序 排队规则的3种类型 25 等待制的四种类型 26 3 4服务员数量 排队系统中的常见变形 排队系统 27 排队系统的四种变形 1 单通道多阶段 服务台 单通道 单阶段 排队 单通道 单阶段排队系统 单通道 多阶段排队系统 排队 服务台 服务台 28 多通道单阶段 多通道多阶段 多通道 单阶段排队系统 多通道 多阶段排队系统 排队系统的四种变形 2 29 4排队模型4 1排队问题的一般表达方式 一般形式 X Y CX 顾客相继达到时间间隔的概率分布 Y 服务时间的概率分布 C 服务台的个数 30 4 2一些特殊排队模型 指数分布 常数分布 31 4 3模型符号定义 无限顾客源 32 系统利用率正在接受服务的顾客平均数系统中的平均顾客数系统中等待的平均顾客数顾客平均逗留时间顾客平均等待时间 4 4模型参数计算 1 M M 1 33 三种重要的关系 管道原理 稳定系统中平均输出 平均输入 率 时间的可加性在系统中逗留的时间等于服务时间加排队利特尔法则 34 4 4模型参数计算 2 M G 1 系统利用率正在接受服务的顾客平均数系统中等待的平均顾客数系统中的平均顾客数顾客平均逗留时间顾客平均等待时间 常数服务时间能将系统的平均顾客数砍掉一半 35 4 4模型参数计算 3 M M C 1 系统利用率正在接受服务的顾客平均数系统中等待的平均顾客数系统中的平均顾客数顾客平均逗留时间顾客平均等待时间 36 4 4模型参数计算 3 M M C 2 37 例1 一个码头 设待卸货船到达时间间隔服从负指数分布 平均到达2艘 小时 服务台是1台吊车 卸货时间服从负指数分布 平均每20分钟可卸一艘货船 当被占用时 新到货船只能停在码头等待 求在平稳状态下码头上货船的平均数 等待卸货船只的平均数 每艘货船在码头的平均停留时间 货船平均需等待多长时间可以开始卸货 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 的时间是繁忙的 被利用 有16 的时间是空闲的 43 4 依次带入公式 算出各指标得 44 单通道仿真视频 45 排队系统仿真软件Flexsim 1 Flexsim是建立在系统理论 控制理论 数理统计 信息技术和计算机技术等理论基础之上的仿真软件 它是系统模型规范化和数字化相结合的过程 46 排队系统仿真软件Flexsim 2 Flexsim在排队系统中的应用主要是利用仿真模型来研究排队系统 首先通过仿真模型的运行 便于更好的观测排队系统过程中出现的一系列复杂变化和动态过程 其次通过仿真模型稳定后的相关值与排队系统理论值的比较 得出他们的值正好相等 Flexsim在排队系统中的应用有助于我们进一步理解排队系统的相关概念和加深对排队系统的全面认识 从而对改进排队系统做出正确的举措 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档功率时 每洗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时营业额的减少量 我们可以通过假设Wq 5分钟 1 12小时 并从中解得 这将是最有效的顾客到达率 53 因此 既然 的最初估计是10人 小时 则每小时将失去2名顾客 每天的损失 S 而选择功率II 成本只增加了4美元 天 显然 相比较于损失的15 4美元 我们都会选择功率II设备 功率II能满足最初设定的5分钟等待最大限度 因而功率III可不予考虑 除非 变大 54 例4Disneyland乐园中的排队 在游乐园中的频频排队会极为扫兴 Disneyland中的FastPass QuickPass 系统就是想解决这个问题的 其工作原理如下 到达的顾客将自己的票插入FastPass的slot中 FastPass计算出建议顾客返回的时间间隔或时间点或时间窗 顾客无需排队 在指定的时间返回就可持票进入 55 思考 QuickPass对排队系统的那些特征参数做了改变 改变顾客到达模式 是如何影响系统绩效 56 解 57 Disneyland问题解决了吗 如果游客不按时间返回 是否让游客等待时间太久了 过山车是按时间开还是人数一够就开 http www stanford edu yaoxie Pubs 2 htm 58 例5 某售票所有三个窗口 顾客的到达服从泊松分布 平均到达速率 0 9人 min 售票时间服从负指数分布 平均服务速率 0 4人 min 现设顾客到达后排成一队 依次向空闲的窗口购票 如图所示 试分别用公式 excel和仿真求解 1 整个售票所空闲概率 2 平均队列长和平均队长 3 平均等待时间和逗留时间 4 顾客到达后必须等待的概率 n 3 59 顾客到达和服务图 60 解 这是一个典型的M M C排队问题 1 整个售票所空闲概率 61 2 平均排队长度和平均队列长 3 平均等待时间和逗留时间 62 4 顾客到达后必须等待的概率 n 3 63 M M 3仿真视频 64 M M 3Excel求解 65 例6银行取号系统有用吗 就例5 如果其他条件不变 顾客到达后在每个窗口前各排一队 且进入队列后坚持不换 就形成3个队列 如下图所示 试分别用公式 excel求解 1 整个售票所空闲概率 2 平均队列长度和平均队长 3 平均等待时间和逗留时间 4 顾客到达后必须等待的概率 n 3 66 顾客到达和服务图 67 解 这是3个M M 1同时服务的排队问题 1 整个售票所空闲概率 每个窗口空闲 4 顾客到达必须等待的概率 每个窗口n 1 68 2 平均排队长度和平均队列长 3 平均等待时间和逗留时间 69 3个M M 1Excel求解 70 结论 银行取号系统是有效的 71 结论 银行取号系统是有效的 从这两个系统的主要指标比较可以看出混合排队比独立排队具有显著的优越性 这一点是在排队系统的排队方式的设计时应该注意的 72 普遍结论 集中使用优于分散使用 将资源组合在一起为所有的顾客提供服务 可以在等待时间不变的条件下 减少所需要的资源总量 如果是两列独立排队 那么客户可能要等那位指定的服务人员提供服务 这位服务人员可能当时正忙得抽不开身 而另一位服务人员却闲着没事干 在集中使用的系统中就不会出现这种现象 大规模制造或服务设施的规模经济学在保持同样利用率的情况下减少平均等待时间在保持同样平均等待时间的情况下提高利用率 73 5排队系统最优设计 成本分析5 1概述 排队系统的最优设计和最优控制 即排队系统的最优化问题 其目的在于使排队系统达到最大效益或者说在一定指标下使排队系统最为经济 74 服务成本与等待成本的权衡 成本 效益平衡 排队分析的目的是使顾客等待成本与服务能力成本这两项成本之和最小 75 5 2M M 1模型中的最优服务率u 1 最佳服务能力是使总成本最小化 总成本 顾客等候成本 服务能力成本 76 5 2M M 1模型中的最优服务率u 2 所以M M 1模型的最优服务率为 77 例7 设某服务机构 单服务台 顾客到达率为每小时12位顾客 假定每位接受顾客的顾客其等待费用为每小时5元 服务成本为每位顾客2元 欲使总平均费用最小 服务率应为多少 78 解 这是一个标准的M M 1排队问题 79 5 3 Lq Ls三者的关系 1 当系统利用率增加时 队列平均等候数与顾客排队等候的平均时间呈指数增长 80 5 3 Lq Ls三者的关系 2 81 5 3 Lq Ls三者的关系 3 平均队长 和平均等待时间 与服务台利用率之间的关系不是线性的关系 资产利用率太高会造成服务质量急速下降 因而要权衡利弊 要保证服务质量 就必须保持 过剩的 生产或服务能力 82 6解决排队问题的方法6 1理论方法 减少平均服务时间减少服务时间的可变性增加服务人员减少平均到达人数通过顾客预约等办法来减少到达的可变性集中使用服务资源更好地计划和调度 83 6解决排队问题的方法6 2其他方法 服务场所提供娱乐设施医生等候室放报纸杂志自动维修间用收音机或电视航空公司提供空中电影等候电梯处放镜子超级市场把冲动性商品摆放在收款台附近 84 6解决排队问题的方法6 3掌握客户的感受 等待心理学 客户所感受到的等待可能与实际的等待有很大的差别 研究结果表明 服务越有价值 人们就越愿意多等一会儿 服务开始之前的等待感觉要比服务过程中的等待要长 心急会让人觉得等待的时间很长 不公平的等待比公平的等待要长 不确定的等待比已知的等待要长 不明情况的等待要比知情的等待要长 没事干的时候会让人觉得比有事干的时候要长 独自等待会让人觉得比大家一起等待要长 85 结束