排队论基础及模型(8)讲诉

《排队论基础及模型(8)讲诉》由会员分享，可在线阅读，更多相关《排队论基础及模型(8)讲诉（85页珍藏版）》请在金锄头文库上搜索。

1、 排队论 教学目的：了解排队论的经济含义 ；排队系统的一般概念和简单的排 队系统；了解排队问题的计算机仿 真。 1 学习内容 大纲内容知识要点 基本概念 排队系统 泊松分布、负指数分布 排队系统排队系统的一般指标 排队模型的运用M/M/1、M/M/C 排队问题 的仿真Excel 仿真 2 引导案例-1 银行排队系统 3 引导案例-2 医院排队系统 4 形形色色的排队系统 达到的顾客要求服务的内容服务的机构 出故障的机器 修理技工 病人 电话 呼叫 进港货船 入水库河水 达到机场上空的飞机 刑事案件 达到路口的车辆 来犯敌机 修理 领取修配零件 诊断（或治疗） 通话 装（卸）货 放水、调整水位

2、降落 侦破 通过路口 截击 修理技工 发放修配零件的管理员 医生（或治疗设备 ） 交换台 装（卸）货码头 （泊位 ） 水闸、管理员 跑道 刑侦部门 交通信号灯 我防空部队 5 为什么会出现排队现象？ 假定每小时平均有4位顾客到达，服务人员为每位顾客 的平均服务时间为15分钟。如果顾客到达的间隔时间正好是 15分钟，而服务人员为每位顾客的服务时间也正好是15分钟 ，那么，就只需要一名服务人员，顾客也根本用不着等待。 在以下情况将出现排队现象： 平均到达率高于平均服务率 顾客到达的间隔时间不一样（随机） 服务时间不一样（随机） 顾客离开 顾客 顾客排队 服务设施 6 到达数量 时 间 普通能力 排

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

4、管理者必须 衡量为提供更快捷的服务（如更多 的车道、额外的降落跑道、更多的 收银台）而增加的成本和相应的等 待造成的费用之间的关系。 9 服务成本与等待成本的权衡（成本效益平衡） 总成本 成本 最佳能力 等待成本 服务成本 最小值 排队分析的目的是使顾客等待成本与服务能力成本 这两项成本之和最小 10 2 排队论概述 2.1 基本概念 概念 u在队列中，等待服务的顾客（customer）和服务台 （server）就构成了一个排队系统（queuing system ）。 本质 u研究服务台与顾客之间服务与接收服务的效率问题 。 总体目标 u以最少的服务台满足最多的客户需求。 11 2.2 排队系

5、统的一般形式 排队可以是有形的队列，也可以是 无形的队列。排队可以是人，也可 以是物。 顾客源排队结构 服 务 机 构 顾客到来 排队规则 服务规则 顾客离去 服务系统 12 3 排队问题的特征 总体来源 到达与服务模式 排队纪律（服务顺序） 服务员数量（通道） 13 有限顾客源 例如：公司只有 三台机器时，需 要维修的数量 潜在顾客数量 无限顾客源 例如：排队等候 公共汽车的乘客 人数 3.1 总体来源 分析排队问题所用方法取决于潜在 顾客数量是否有限。 本章讨论的重点 14 3.2 顾客到达与服务模式 常用的模型假定顾客到达速度服从 泊松分布，服务时间服从指数分布 。 15 3.2.1 泊

6、松分布 定义：设 N（t）为时间 0，t 内达到系统 的顾客数，如果满足下面三个条件： u平稳性：在 t ，t + t 内有一个顾客达到的概率与 t无关； u独立性：在任意两个不相交时间区间内顾客达到相互 独立； u普通性：在 t ，t + t内多于一个顾客达到的概率 极小，为 ( t )，可以忽略。 则称 N（t），t 0 为Poisson 过程，其 对应的分布为泊松分布（ Poisson 分布）。 16 泊松分布的形式 相对 频度 0 1 2 3 4 5 6 7 8 9 10 11 12 0.20 0.18 0.16 0.14 0.12 0.10 0.08 0.06 0.04 0.02 0

7、.00 泊松分布 （比率） 每单位时间顾客数 图 泊松分布 17 泊松分布的概率密度函数 如果一个系统的平均到达率是每分钟有3个 顾客到达（ =3），求1分钟内有5个人到达 的概率 18 3.2.2 指数分布 当顾客以完全随机的方式到达服务 实施时，相邻到达间隔时间服从指 数分布，但平均到达率不变； 随机服务时间服从指数分布，但平 均服务率不变； 19 （负）指数分布的形式 图 负指数分布 指数分布 （时间） 相对频率 0时间 20 （负）指数分布的概率密度函数 21 （1）（2）（3） t（分钟）下一个顾客在大于等于t 分钟内到达的概率 下一个顾客在小于等于t 分钟内到达的概率 01.000

8、 0.50.610.39 1.00.370.63 1.50.220.78 2.00.140.86 表 下一个到达的顾客的时间间隔的概率 22 3.2.3 泊松分布和指数分布的关系 泊松分布与指数分布可以互相推导 得到。泊松分布的期望值和方差相 等，都为 ；指数分布期望值为1/ ,方差为1/ 2 。 相邻顾客到达时间间隔服从指数分 布，单位时间段内到达的顾客数服 从泊松分布。 23 3.3 排队纪律/排队规则/服务顺序 排队规则的3种类型 损失制 等待制 排队规则 混合制 24 等待制的四种类型 等待制等待制 最短处理时间 SPT 随机服务 RS 后到先服务 LCFS 先到先服务 FCFS 25

9、 3.4 服务员数量 排队系统中的常见变形 Title in here 多通道 单阶段 Title in here 单通道 多阶段 Title in here 单通道 单阶段 Title in here 多通道 多阶段 排队系统 26 排队系统的四种变形-1 单通道 多阶段 服务台 单通道，单阶段 排队 单通道、单阶段排队系统 单通道、多阶段排队系统 排队 服务台 服务台 27 多通道 单阶段 多通道 多阶段 多通道、单阶段排队系统 多通道、多阶段排队系统 排队系统的四种变形-2 28 4 排队模型 4.1 排队问题的一般表达方式 一般形式： X / Y / C uX 顾客相继达到时间间隔的概

10、率分布； uY 服务时间的概率分布； uC服务台的个数； 29 4.2 一些特殊排队模型 模型分布 服务 阶段 顾客源 到达 分布 排队 规则 服务时 间分布 队列 长度 典型例子 模型表 示 1单通道 单一 无限泊松FCFS指数无限 只有一个出 口的收费桥 M/M/1 2单通道 单一 无限泊松FCFS常数无限 游乐园的 过山车 M/G/1 3多通道 单一 无限泊松FCFS指数无限 银行柜台 服务 M/M/C 4多通道 单一 有限泊松FCFS指数无限 工厂里故障 机器的维修 指数分布 常数分布 30 4.3 模型符号定义（无限顾客源） 符号代表 顾客到达速度（到达率）；1/ 代表相邻到达平均时

11、间间隔 ,u服务速度（服务率）； 1/ 代表平均服务时间 系统利用率，即到达率与服务率的比值 Lq等候服务的顾客平均数 Ls系统中的顾客平均数（正在等候的正在接受服务的） Wq顾客排队等候的平均时间 Ws顾客在系统中花费的平均时间（排队等候时间服务时间） r正在接受服务的顾客平均数 n系统中的平均顾客数 C服务台（通道）数量 P0系统0个顾客概率 Pn系统有n个顾客的概率 Lmax队列中等候的最大期望值 31 系统利用率 正在接受服务的顾客平均数 系统中的平均顾客数 系统中等待的平均顾客数 顾客平均逗留时间 顾客平均等待时间 4.4 模型参数计算-1（ M/M/1） 32 三种重要的关系 “管

12、道原理”: u稳定系统中平均输出= 平均输入（率）= 时间的可加性 u在系统中逗留的时间等于服务时间加排队 利特尔法则 33 4.4 模型参数计算-2（ M/G/1 ） 系统利用率 正在接受服务的顾客平均 数 系统中等待的平均顾客数 系统中的平均顾客数 顾客平均逗留时间 顾客平均等待时间 u常数服务时间能将系统的平均顾客数砍掉一半 34 4.4 模型参数计算-3（ M/M/C）-1 系统利用率 正在接受服务的顾客平均 数 系统中等待的平均顾客数 系统中的平均顾客数 顾客平均逗留时间 顾客平均等待时间 35 4.4 模型参数计算-3（ M/M/C）-2 36 例1 一个码头，设待卸货船到达时间间

13、隔服 从负指数分布，平均到达 2 艘/小时；服 务台是1台吊车，卸货时间服从负指数分 布，平均每 20 分钟可卸一艘货船，当被 占用时，新到货船只能停在码头等待。 求在平稳状态下码头上货船的平均数； 等待卸货船只的平均数；每艘货船在码 头的平均停留时间；货船平均需等待多 长时间可以开始卸货。 37 解： 这是一个典型的M/M/1排队问题 38 例2 某医院手术室根据病人就诊和完成 手术时间的记录，任意抽查100个工 作小时，每小时来就诊的病人数n 的出现次数如表6所示。又任意抽查 了100个完成手术的病例，所用时间 t出现的次数如下表所示。试分别用 公式、excel和仿真求解： 39 到达病人

14、数 n 出现次数 f n 010 128 229 316 410 56 61 合计100 到达病人数 为病人完成手术 时间t/小时 出现次数 ft 0.00.238 0.20.425 0.40.617 0.6 1.89 0.81.06 1.01.25 1.20 合计100 手术时间 40 解： 这也是一个M/M/1排队问题 （1）计算平均到达率 平均手术时间 平均服务率 41 （2）取=2.1，=2.5，通过统计检验方法认为 病人到达数服从参数为2.1的泊松分布，手 术时间服从参数为2.5的指数分布。 （3）服务设备利用率 这说明服务机构（手术室）有84%的时间是繁 忙的（被利用），有16%的

15、时间是空闲的。 42 （4）依次带入公式，算出各指标得： 43 单通道仿真视频 44 排队系统仿真软件Flexsim-1 Flexsim是建立在系统理论、控制理 论、数理统计、信息技术和计算机 技术等理论基础之上的仿真软件， 它是系统模型规范化和数字化相结 合的过程。 45 排队系统仿真软件Flexsim-2 Flexsim在排队系统中的应用主要是利用仿 真模型来研究排队系统，首先通过仿真模 型的运行，便于更好的观测排队系统过程 中出现的一系列复杂变化和动态过程；其 次通过仿真模型稳定后的相关值与排队系 统理论值的比较，得出他们的值正好相等 。 Flexsim在排队系统中的应用有助于我们进 一步理解排队系统的相关概念和加深对排 队系统的全面认识，从而对改进排队系统 做出正确的举措。 46 单通道Excel求解 47 例3-1 Robot公司在全美经营把加油和汽车冲洗合并 在一起的业务。Robot公司对加满油的车辆提 供免费冲洗，对于不加油只冲洗的车收费0.5美 元。以往的经验表明：加油并且洗车的顾客数 和单独洗车的顾客数大致相等。平均加一次油 可盈利0.7美元，洗一次车的成本是0.1美元， 公司每天营业14小时。 Robot有三档功率和清洗组合不同的设备。选 择I档功率时，可以每5分钟洗1辆车，每天的 成本是12美元。II档功率高于I档，每4分钟洗1 辆车，但每天的成本是16美