排队论基础及模型(8)[行业知识]

1、 排队论排队论 教学目的教学目的：了解排队论的经济含义；了解排队论的经济含义； 排队系统的一般概念和简单的排队系排队系统的一般概念和简单的排队系 统；了解排队问题的计算机仿真。统；了解排队问题的计算机仿真。 1 学习内容学习内容 大纲内容大纲内容知识要点知识要点 基本概念基本概念 排队系统排队系统 泊松分布、负指数分布泊松分布、负指数分布 排队系统排队系统排队系统的一般指标排队系统的一般指标 排队模型的运用排队模型的运用M/M/1、M/M/C 排队问题的仿真排队问题的仿真Excel 仿真仿真 2 引导案例引导案例-1 银行排队系统银行排队系统 3 引导案例引导案例-2 医院排队系统医院排队系统

2、 4 形形色色的排队系统形形色色的排队系统 达到的顾客达到的顾客要求服务的内容要求服务的内容服务的机构服务的机构 出故障的机器出故障的机器 修理技工修理技工 病人病人 电话呼叫电话呼叫 进港货船进港货船 入水库河水入水库河水 达到机场上空的飞机达到机场上空的飞机 刑事案件刑事案件 达到路口的车辆达到路口的车辆 来犯敌机来犯敌机 修理修理 领取修配零件领取修配零件 诊断（或治疗）诊断（或治疗） 通话通话 装（卸）货装（卸）货 放水、调整水位放水、调整水位 降落降落 侦破侦破 通过路口通过路口 截击截击 修理技工修理技工 发放发放修配零件修配零件的管理员的管理员 医生（或治疗设备）医生（或治疗设备

3、） 交换台交换台 装（卸）货码头（泊位）装（卸）货码头（泊位） 水闸、管理员水闸、管理员 跑道跑道 刑侦部门刑侦部门 交通信号灯交通信号灯 我防空部队我防空部队 5 为什么会出现排队现象？为什么会出现排队现象？ 假定每小时平均有假定每小时平均有4位顾客到达，服务人员为每位顾客的位顾客到达，服务人员为每位顾客的 平均服务时间为平均服务时间为15分钟。如果顾客到达的间隔时间正好是分钟。如果顾客到达的间隔时间正好是15分分 钟，而服务人员为每位顾客的服务时间也正好是钟，而服务人员为每位顾客的服务时间也正好是15分钟，那么，分钟，那么， 就只需要一名服务人员，顾客也根本用不着等待。就只需要一名服务人员

4、，顾客也根本用不着等待。 在以下情况将出现排队现象：在以下情况将出现排队现象： 平均到达率高于平均服务率平均到达率高于平均服务率 顾客到达的间隔时间不一样（随机）顾客到达的间隔时间不一样（随机） 服务时间不一样（随机）服务时间不一样（随机） 顾客离开顾客离开 顾客顾客 顾客排队顾客排队 服务设施服务设施 6 到达数量到达数量 时时 间间 普通能力普通能力 排队问题并不是系统的固定状态，它与系统设计与排队问题并不是系统的固定状态，它与系统设计与 管理的控制有很大关系。如快餐店只允许很短的队管理的控制有很大关系。如快餐店只允许很短的队 长，也可为特定的顾客留出特定的时间段；也可以长，也可为特定的顾

5、客留出特定的时间段；也可以 通过使用更快的服务人员、机器或采用不同的设施通过使用更快的服务人员、机器或采用不同的设施 布局和政策来影响顾客的到达时间和服务时间。布局和政策来影响顾客的到达时间和服务时间。 7 1 排队论的基本问题排队论的基本问题 1.1 排队论的主要研究内容排队论的主要研究内容 数量指标数量指标 u研究主要数量指标在瞬时或平稳状态下的概率分研究主要数量指标在瞬时或平稳状态下的概率分 布及其数字特征，了解系统的基本运行特征。布及其数字特征，了解系统的基本运行特征。 统计推断统计推断 u检验系统是否达到平稳状态；检验顾客达到间隔检验系统是否达到平稳状态；检验顾客达到间隔 的独立性；

6、确定服务时间分布及参数。的独立性；确定服务时间分布及参数。 系统优化系统优化 u系统的最优设计和最优运营问题。系统的最优设计和最优运营问题。 8 1.2 排队论的经济含义排队论的经济含义 排队问题的核心问题实际上就是对不排队问题的核心问题实际上就是对不 同因素做权衡决策。管理者必须衡量同因素做权衡决策。管理者必须衡量 为提供更快捷的服务（如更多的车道、为提供更快捷的服务（如更多的车道、 额外的降落跑道、更多的收银台）而额外的降落跑道、更多的收银台）而 增加的成本和相应的等待造成的费用增加的成本和相应的等待造成的费用 之间的关系。之间的关系。 9 服务成本与等待成本的权衡（成本效益平衡）服务成本

7、与等待成本的权衡（成本效益平衡） 总成本总成本 成本成本 最佳能力最佳能力 等待成本等待成本 服务成本服务成本 最小值最小值 排队分析的目的是使顾客等待成本与服务能力成本排队分析的目的是使顾客等待成本与服务能力成本 这两项成本之和最小这两项成本之和最小 10 2 排队论概述排队论概述 2.1 基本概念基本概念 概念概念 u在队列中，等待服务的顾客（在队列中，等待服务的顾客（customer）和服务台）和服务台 （server）就构成了一个排队系统（）就构成了一个排队系统（queuing system）。）。 本质本质 u研究服务台与顾客之间服务与接收服务的效率问题。研究服务台与顾客之间服务与接

8、收服务的效率问题。 总体目标总体目标 u以最少的服务台满足最多的客户需求。以最少的服务台满足最多的客户需求。 11 2.2 排队系统的一般形式排队系统的一般形式 排队可以是有形的队列，也可以是无排队可以是有形的队列，也可以是无 形的队列。排队可以是人，也可以是形的队列。排队可以是人，也可以是 物。物。 顾客源顾客源排队结构排队结构 服服 务务 机机 构构 顾客到来顾客到来 排队规则排队规则 服务规则服务规则顾客离去顾客离去 服务系统服务系统 12 3 排队问题的特征排队问题的特征 总体来源总体来源 到达与服务模式到达与服务模式 排队纪律（服务顺序）排队纪律（服务顺序） 服务员数量（通道）服务员

9、数量（通道） 13 有限顾客源有限顾客源 例如：公司只有例如：公司只有 三台机器时，需三台机器时，需 要维修的数量要维修的数量 潜在顾客数量潜在顾客数量 无限顾客源无限顾客源 例如：排队等候例如：排队等候 公共汽车的乘客公共汽车的乘客 人数人数 3.1 总体来源总体来源 分析排队问题所用方法取决于潜在顾分析排队问题所用方法取决于潜在顾 客数量是否有限。客数量是否有限。 本章讨论的重点本章讨论的重点 14 3.2 顾客到达与服务模式顾客到达与服务模式 常用的模型常用的模型假定假定顾客到达速度服从顾客到达速度服从泊泊 松分布松分布，服务时间服从，服务时间服从指数分布指数分布。 15 3.2.1 泊

10、松分布泊松分布 定义：设定义：设 N（t）为时间）为时间 0，t 内达到系统的内达到系统的 顾客数，如果满足下面三个条件：顾客数，如果满足下面三个条件： u平稳性：在平稳性：在 t ，t + t 内有一个顾客达到的概率与内有一个顾客达到的概率与t 无关；无关； u独立性：在任意两个不相交时间区间内顾客达到相互独立性：在任意两个不相交时间区间内顾客达到相互 独立；独立； u普通性：在普通性：在 t ，t + t内多于一个顾客达到的概率极内多于一个顾客达到的概率极 小，为小，为 ( t )，可以忽略。，可以忽略。 则称则称 N（t），），t 0 为为Poisson 过程，其对过程，其对 应的分布为

11、泊松分布（应的分布为泊松分布（ 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.00 泊松分布泊松分布 （比率）（比率） 每单位时间顾客数每单位时间顾客数 图图 泊松分布泊松分布 17 泊松分布的概率密度函数泊松分布的概率密度函数 () ( ) ! nT T T e P n n T n ：单位时间段； :到达率 ：单位时间段内到达的人数 如果一个系统的平均到达率是每分钟有如果一个系统的平均到达

12、率是每分钟有3个顾个顾 客到达（客到达（ =3），求），求1分钟内有分钟内有5个人到达的个人到达的 概率概率(5,1)nT 53 153 3 1 (3 1)3 (5)2.0250.101 5!120 ee Pe 18 3.2.2 指数分布指数分布 当顾客以完全随机的方式到达服务实当顾客以完全随机的方式到达服务实 施时，相邻到达间隔时间服从指数分施时，相邻到达间隔时间服从指数分 布，但布，但平均到达率不变平均到达率不变； 随机服务时间服从指数分布，但随机服务时间服从指数分布，但平均平均 服务率不变服务率不变； 19 （负）指数分布的形式（负）指数分布的形式 图图 负指数分布负指数分布 指数分布指

13、数分布 （时间）（时间） 相对频率相对频率 0时间时间 20 （负）指数分布的概率密度函数（负）指数分布的概率密度函数 t f(t)e t ：单位时间段内到达的顾客数量 ：时间间隔 21 （1）（2）（3） t（分钟）（分钟）下一个顾客在大于等于下一个顾客在大于等于t 分钟内到达的概率分钟内到达的概率 下一个顾客在小于等于下一个顾客在小于等于t 分钟内到达的概率分钟内到达的概率 01.000 0.50.610.39 1.00.370.63 8 2.00.140.86 1备注：设 表表 下一个到达的顾客的时间间隔的概率下一个到达的顾客的时间间隔的概率 22 3.2.3 泊松分

14、布和指数分布的关系泊松分布和指数分布的关系 泊松分布与指数分布可以互相推导得泊松分布与指数分布可以互相推导得 到。泊松分布的期望值和方差相等，到。泊松分布的期望值和方差相等， 都为都为 ；指数分布期望值为；指数分布期望值为1/ ,方差方差 为为1/ 2 。 相邻顾客到达相邻顾客到达时间间隔时间间隔服从指数分布，服从指数分布， 单位单位时间段内时间段内到达的顾客数服从泊松到达的顾客数服从泊松 分布。分布。 23 3.3 排队纪律排队纪律/排队规则排队规则/服务顺序服务顺序 排队规则的排队规则的3种类型种类型 损失制损失制 等待制等待制 排队规则排队规则 混合制混合制 24 等待制的四种类型等待制

15、的四种类型 最短处理时间最短处理时间 SPT 随机服务随机服务 RS 后到先服务后到先服务 LCFS 先到先服务先到先服务 FCFS 25 3.4 服务员数量服务员数量 排队系统中的常见变形排队系统中的常见变形 Title in here 多通道多通道 单阶段单阶段 Title in here 单通道单通道 多阶段多阶段 Title in here 单通道单通道 单阶段单阶段 Title in here 多通道多通道 多阶段多阶段 排队系统排队系统 26 排队系统的四种变形排队系统的四种变形-1 单通道单通道 多阶段多阶段 服务台服务台 单通道，单阶段单通道，单阶段 排队排队 单通道、单阶段排

16、队系统单通道、单阶段排队系统 单通道、多阶段排队系统单通道、多阶段排队系统 排队排队 服务台服务台 服务台服务台 27 多通道多通道 单阶段单阶段 多通道多通道 多阶段多阶段 多通道、单阶段排队系统多通道、单阶段排队系统 多通道、多阶段排队系统多通道、多阶段排队系统 排队系统的四种变形排队系统的四种变形-2 28 4 排队模型排队模型 4.1 排队问题的一般表达方式排队问题的一般表达方式 一般形式：一般形式： X / Y / C uX 顾客相继达到顾客相继达到时间间隔时间间隔的概率分布；的概率分布； uY 服务时间的概率分布；服务时间的概率分布； uC服务台的个数；服务台的个数； 29 4.2

17、 一些特殊排队模型一些特殊排队模型 模型模型分布分布 服务服务 阶段阶段 顾客源顾客源 到达到达 分布分布 排队排队 规则规则 服务时服务时 间分布间分布 队列队列 长度长度 典型例子典型例子 模型表模型表 示示 1单通道单通道 单一单一无限无限泊松泊松 FCFS指数指数无限无限 只有一个出只有一个出 口的收费桥口的收费桥 M/M/1 2单通道单通道 单一单一无限无限泊松泊松 FCFS常数常数无限无限 游乐园的游乐园的 过山车过山车 M/G/1 3多通道多通道 单一单一无限无限泊松泊松 FCFS指数指数无限无限 银行柜台银行柜台 服务服务 M/M/C 4多通道多通道 单一单一有限有限泊松泊松

18、FCFS指数指数无限无限 工厂里故障工厂里故障 机器的维修机器的维修 指数分布指数分布 常数分布常数分布 30 4.3 模型符号定义（无限顾客源）模型符号定义（无限顾客源） 符号符号代表代表 顾客到达速度（到达率）；顾客到达速度（到达率）；1/ 代表相邻到达平均时间间隔代表相邻到达平均时间间隔 ,u服务速度（服务率）；服务速度（服务率）； 1/ 代表平均服务时间代表平均服务时间 系统利用率，即到达率与服务率的比值系统利用率，即到达率与服务率的比值 Lq等候服务的顾客平均数等候服务的顾客平均数 Ls系统中的顾客平均数（正在等候的正在接受服务的）系统中的顾客平均数（正在等候的正在接受服务的） Wq

19、顾客排队等候的平均时间顾客排队等候的平均时间 Ws顾客在系统中花费的平均时间（排队等候时间服务时间）顾客在系统中花费的平均时间（排队等候时间服务时间） r正在接受服务的顾客平均数正在接受服务的顾客平均数 n系统中的平均顾客数系统中的平均顾客数 C服务台（通道）数量服务台（通道）数量 P0系统系统0个顾客概率个顾客概率 Pn系统有系统有n个顾客的概率个顾客的概率 Lmax队列中等候的最大期望值队列中等候的最大期望值 31 系统利用率系统利用率 正在接受服务的顾客平均数正在接受服务的顾客平均数 系统中的平均顾客数系统中的平均顾客数 系统中等待的平均顾客数系统中等待的平均顾客数 顾客平均逗留时间顾客

20、平均逗留时间 顾客平均等待时间顾客平均等待时间 r ss LW u qsqs LLWLr 1Lq WqWs u 1Ls Ws u 4.4 模型参数计算模型参数计算-1（ M/M/1） 0 1P(1)(1) n n Pn 32 三种重要的关系三种重要的关系 “管道原理管道原理”: u稳定系统中平均输出稳定系统中平均输出= 平均输入（率）平均输入（率）= 时间的可加性时间的可加性 u在系统中逗留的时间等于服务时间加排队在系统中逗留的时间等于服务时间加排队 利特尔法则利特尔法则 1 WsWq u ss LW qq LW LW 33 4.4 模型参数计算模型参数计算-2（ M/G/1 ） 系统利用率系

21、统利用率 正在接受服务的顾客平均数正在接受服务的顾客平均数 系统中等待的平均顾客数系统中等待的平均顾客数 系统中的平均顾客数系统中的平均顾客数 顾客平均逗留时间顾客平均逗留时间 顾客平均等待时间顾客平均等待时间 1C C ， L sL qr 2 2 () q L u u Lq Wq Ls Ws r u常数服务时间能将系统的平均顾客数砍掉一半常数服务时间能将系统的平均顾客数砍掉一半 34 4.4 模型参数计算模型参数计算-3（ M/M/C）-1 系统利用率系统利用率 正在接受服务的顾客平均数正在接受服务的顾客平均数 系统中等待的平均顾客数系统中等待的平均顾客数 系统中的平均顾客数系统中的平均顾客

22、数 顾客平均逗留时间顾客平均逗留时间 顾客平均等待时间顾客平均等待时间 C L sL qr 0 2 !(1) c q r Lp c Lq Wq Ls Ws r 35 4.4 模型参数计算模型参数计算-3（ M/M/C）-2 1 1 0 0 !(1) nc c n rr P nc n P 0 ! n r p n (0)nc 0 1 ! n nc r p cc g ()nc 36 例例1 一个码头，设待卸货船到达时间间隔服从一个码头，设待卸货船到达时间间隔服从 负指数分布，平均到达负指数分布，平均到达 2 艘艘/小时；服务台小时；服务台 是是1台吊车，卸货时间服从负指数分布，台吊车，卸货时间服从负

23、指数分布， 平均每平均每 20 分钟可卸一艘货船，当被占用分钟可卸一艘货船，当被占用 时，新到货船只能停在码头等待。求在平时，新到货船只能停在码头等待。求在平 稳状态下码头上货船的平均数；等待卸货稳状态下码头上货船的平均数；等待卸货 船只的平均数；每艘货船在码头的平均停船只的平均数；每艘货船在码头的平均停 留时间；货船平均需等待多长时间可以开留时间；货船平均需等待多长时间可以开 始卸货。始卸货。 37 解：解： 这是一个典型的这是一个典型的M/M/1排队排队问题问题 2 1 3 r 2 60 3 20 u 2 2() 3 2 s L u 艘 24 2 33 qs LLr(艘) 4 2 3 ()

24、 23 Lq Wq 小时 2 1() 2 Ls Ws 小时 38 例例2 某医院手术室根据病人就诊和完成手某医院手术室根据病人就诊和完成手 术时间的记录，任意抽查术时间的记录，任意抽查100个工作个工作 小时，每小时来就诊的病人数小时，每小时来就诊的病人数n的出的出 现次数如表现次数如表6所示。又任意抽查了所示。又任意抽查了100 个完成手术的病例，所用时间个完成手术的病例，所用时间t出现出现 的次数如下表所示。试分别用公式、的次数如下表所示。试分别用公式、 excel和仿真求解：和仿真求解： 39 到达病人数到达病人数 n 出现次数出现次数 f n 010 128 229 316 410 5

25、6 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）计算平均到达率）计算平均到达率 2.1(/) 100 n nf 人 时 平均手术时间平均手术时间 0.4() 100 t tf T 时/人 平均服务率平均服务率 1 2.5() 0.4 u 人/时 41 （2）取）取=2.1，=2.5，通过统计检验方法认为，

26、通过统计检验方法认为 病人到达数服从参数为病人到达数服从参数为2.1的泊松分布，手的泊松分布，手 术时间服从参数为术时间服从参数为2.5的指数分布。的指数分布。 （3）服务设备利用率服务设备利用率 2.1 0.84 2.5 这说明服务机构（手术室）有这说明服务机构（手术室）有84%的时间的时间 是繁忙是繁忙的的（被利用），有（被利用），有16%的时间是空的时间是空 闲的。闲的。 42 0.84r u 2.1 2.5u 2.1 5.25() 2.5 2.1 s L u 人 5.250.844.41 qs LLr(人) 4.41 2.1() 2.1 Lq Wq 小时 5.25 2.5() 2.1

27、Ls Ws 小时 （4）依次带入公式，算出各指标得：依次带入公式，算出各指标得： 43 单通道仿真视频单通道仿真视频 44 排队系统仿真软件排队系统仿真软件Flexsim-1 Flexsim是建立在系统理论、控制理是建立在系统理论、控制理 论、数理统计、信息技术和计算机技论、数理统计、信息技术和计算机技 术等理论基础之上的仿真软件，它是术等理论基础之上的仿真软件，它是 系统模型规范化和数字化相结合的过系统模型规范化和数字化相结合的过 程。程。 45 排队系统仿真软件排队系统仿真软件Flexsim-2 Flexsim在排队系统中的应用主要是利用仿真在排队系统中的应用主要是利用仿真 模型来研究排队

28、系统，首先通过仿真模型的模型来研究排队系统，首先通过仿真模型的 运行，便于更好的观测排队系统过程中出现运行，便于更好的观测排队系统过程中出现 的一系列复杂变化和动态过程；其次通过仿的一系列复杂变化和动态过程；其次通过仿 真模型稳定后的相关值与排队系统理论值的真模型稳定后的相关值与排队系统理论值的 比较，得出他们的值正好相等。比较，得出他们的值正好相等。 Flexsim在排队系统中的应用有助于我们进一在排队系统中的应用有助于我们进一 步理解排队系统的相关概念和加深对排队系步理解排队系统的相关概念和加深对排队系 统的全面认识，从而对改进排队系统做出正统的全面认识，从而对改进排队系统做出正 确的举措

29、。确的举措。 46 单通道单通道Excel求解求解 47 例例3-1 Robot公司在全美经营把加油和汽车冲洗合并在公司在全美经营把加油和汽车冲洗合并在 一起的业务。一起的业务。Robot公司对加满油的车辆提供免公司对加满油的车辆提供免 费冲洗，对于不加油只冲洗的车收费费冲洗，对于不加油只冲洗的车收费0.5美元。美元。 以往的经验表明：加油并且洗车的顾客数和单独以往的经验表明：加油并且洗车的顾客数和单独 洗车的顾客数大致相等。平均加一次油可盈利洗车的顾客数大致相等。平均加一次油可盈利 0.7美元，洗一次车的成本是美元，洗一次车的成本是0.1美元，公司每天美元，公司每天 营业营业14小时。小时。

30、 Robot有三档功率和清洗组合不同的设备。选择有三档功率和清洗组合不同的设备。选择I 档功率时，可以每档功率时，可以每5分钟洗分钟洗1辆车，每天的成本是辆车，每天的成本是 12美元。美元。II档功率高于档功率高于I档，每档，每4分钟洗分钟洗1辆车，但辆车，但 每天的成本是每天的成本是16美元；选择美元；选择III档功率时，每洗档功率时，每洗1 辆车需辆车需3分钟，但每天的成本是分钟，但每天的成本是22美元。美元。 48 例例3-2 Robot公司估计，每个顾客洗公司估计，每个顾客洗1辆车不辆车不 愿等待的时间不超过愿等待的时间不超过5分钟，若等待分钟，若等待 的时间过长，公司将失去顾客。的时

31、间过长，公司将失去顾客。 若估计每小时有若估计每小时有10名顾客前来洗车，名顾客前来洗车， 那么该选择哪档功率的设备？那么该选择哪档功率的设备？ 49 解：解： 这是一个典型的这是一个典型的M/G/1排队排队问题问题 （1）选择功率）选择功率I时时 22 10 2.08333( 2 ()2 12 (12 10) q L u u 小时) 10 1 12 r 10 12u 顾客平均等待时间顾客平均等待时间 2.08333 0.208() 10 Lq Wq 小时 ，即12.5(分钟) 50 （2）选择功率）选择功率II时时 22 10 0.667( 2 ()2 12 (15 10) q L u u

32、小时) 10 1 15 r 10 15u 顾客平均等待时间顾客平均等待时间 0.667 0.0667() 10 Lq Wq 小时 ，即4(分钟) 如果等待时间是唯一标准，则应选择功率如果等待时间是唯一标准，则应选择功率II 的设备，但在我们做出最后结论之前，还必的设备，但在我们做出最后结论之前，还必 须看一下二者的利润差异。须看一下二者的利润差异。 51 (3)对于功率对于功率I，由于等待时间为，由于等待时间为12.5分钟，部分钟，部 分顾客会放弃接受服务。尽管这将使数学分顾客会放弃接受服务。尽管这将使数学 分析复杂化，我们仍可以估计出选择功率分析复杂化，我们仍可以估计出选择功率 I时营业额的

33、减少量。我们可以通过假设时营业额的减少量。我们可以通过假设 Wq=5分钟（分钟（1/12小时），并从中解得小时），并从中解得 ， 这将是最有效的顾客到达率。这将是最有效的顾客到达率。 2 /2 () 2 () Lqu u Wq u u 2 2 1 2()(12) 2 12 8(/) 1 12 12()(12) 12 q q W u W u 人 小时 52 因此，既然因此，既然 的最初估计是的最初估计是10人人/小时，则每小时，则每 小时将失去小时将失去2名顾客。名顾客。 每天的损失每天的损失(S)： 1 2 14(0.70.4)15.4(/) 2 S 美元 天 而选择功率而选择功率II，成本只

34、增加了，成本只增加了4美元美元/天，显天，显 然，相比较于损失的然，相比较于损失的15.4美元，我们都会选美元，我们都会选 择功率择功率II设备。设备。 功率功率II能满足最初设定的能满足最初设定的5分钟等待最大限分钟等待最大限 度，因而功率度，因而功率III可不予考虑，除非可不予考虑，除非 变大。变大。 53 例例4 Disneyland乐园中的排队乐园中的排队 在游乐园中的频频排队会极为扫兴，在游乐园中的频频排队会极为扫兴， Disneyland中的中的FastPass (QuickPass)系统就系统就 是想解决这个问题的。其工作原理如下：是想解决这个问题的。其工作原理如下： 到达的顾客

35、将自己的票插入到达的顾客将自己的票插入FastPass的的slot中；中； FastPass计算出建议顾客返回的时间间隔或时间计算出建议顾客返回的时间间隔或时间 点或时间窗；点或时间窗； 顾客无需排队，在指定的时间返回就可持票进入。顾客无需排队，在指定的时间返回就可持票进入。 54 思考思考 1. QuickPass对排队系统的那些特征参对排队系统的那些特征参 数做了改变？数做了改变？ 2. 改变顾客到达模式，是如何影响系改变顾客到达模式，是如何影响系 统绩效？统绩效？ 55 解：解： 泊松分布到达泊松分布到达常数分布到达常数分布到达 平均达到率平均达到率11人人/分钟分钟11人人/分钟分钟

36、平均服务率平均服务率12人人/分钟分钟12人人/分钟分钟 排队长度排队长度5.040 系统队长系统队长5.960 平均排队时间平均排队时间0.460 系统利用率系统利用率91.70%91.70% 56 Disneyland问题解决了吗？问题解决了吗？ 如果游客不按时间返回？如果游客不按时间返回？ 是否让游客等待时间太久了？是否让游客等待时间太久了？ 过山车是按时间开还是人数一够就开？过山车是按时间开还是人数一够就开？ /yaoxie/Pubs_2.htm 57 例例5 某售票所有三个窗口，顾客的到达服从泊某售票所有三个窗口，顾客的到达服从泊 松分布，

37、平均到达速率松分布，平均到达速率 = 0.9人人/min；售；售 票时间服从负指数分布，平均服务速率票时间服从负指数分布，平均服务速率= 0.4人人/min 。现设顾客到达后排成一队，。现设顾客到达后排成一队， 依次向空闲的窗口购票，如图所示。试分依次向空闲的窗口购票，如图所示。试分 别用公式、别用公式、excel和仿真求解：和仿真求解： u(1) 整个售票所空闲概率整个售票所空闲概率 u(2) 平均队列长和平均队长平均队列长和平均队长 u(3)平均等待时间和逗留时间平均等待时间和逗留时间 u(4)顾客到达后必须等待的概率（顾客到达后必须等待的概率（n3) 58 顾客到达和服务图顾客到达和服务

38、图 顾客离去 排队 = 0.9 顾客到达 窗口1 = 0.4 窗口2 = 0.4 窗口3 = 0.4 59 解：解： 这是一个典型的这是一个典型的M/M/C 排队排队问题问题 0.9 0.751 3 0.4C 0.90.4u (1) 整个售票所空闲概率整个售票所空闲概率 0.9 2.25 0.4 r 1 1 0 0 !(1) nc c n rr P nc 0123 1 52.251 0!1!2!3!10.75 0.0748 60 (2) 平均排队长度和平均队列长平均排队长度和平均队列长 0 2 !(1) c q r Lp c 3 2 2.250.75 0.07481.70

39、 3!(10.75) 1.702.253.95 sq LLr (3)平均等待时间和逗留时间平均等待时间和逗留时间 1.70 1.89 0.9 q q L W 11 1.894.39 0.4 sq WW u 61 (4)顾客到达后必须等待的概率（顾客到达后必须等待的概率（n3) 33 1 nn PP n P 0 ! n r p n (0)nc 0 1 ! n nc r p cc g ()nc 0 0.0748P 2 30 (1)(12.252.531) 0.07480.432 2 n r PrP 3 1 0.4320.568 n P 62 M/M/3仿真视频仿真视频 63 M/M/3 Excel

40、求解求解 64 例例6 银行取号系统有用吗？银行取号系统有用吗？ 就例就例5，如果其他条件不变，顾客到达后，如果其他条件不变，顾客到达后 在每个窗口前各排一队，且进入队列后坚在每个窗口前各排一队，且进入队列后坚 持不换，就形成持不换，就形成3个队列，如下图所示。个队列，如下图所示。 试分别用公式、试分别用公式、excel求解：求解： u(1) 整个售票所空闲概率整个售票所空闲概率 u(2) 平均队列长度和平均队长平均队列长度和平均队长 u(3) 平均等待时间和逗留时间平均等待时间和逗留时间 u(4)顾客到达后必须等待的概率（顾客到达后必须等待的概率（n3) 65 顾客到达和服务图顾客到达和服务

41、图 顾客离去 = 0.3 顾客到达 = 0.9 窗口1 = 0.4 窗口2 = 0.4 窗口3 = 0.4 = 0.3 = 0.3 66 解：解： 这是这是3个个M/M/1同时服务的同时服务的排队排队问题问题 0.3 0.751 0.4 r 0.3 0.4u (1) 整个售票所空闲概率整个售票所空闲概率(每个窗口空闲每个窗口空闲) 0 11 0.750.25p (4)顾客到达必须等待的概率（每个窗口顾客到达必须等待的概率（每个窗口n1) 10 11 0.250.75 n pP 67 (2) 平均排队长度和平均队列长平均排队长度和平均队列长 0.3 0.752.25 0.40.3 q L u 2

42、.250.753 sq LLr (3)平均等待时间和逗留时间平均等待时间和逗留时间 2.25 7.5 0.3 q q L W 3 10 0.3 s s L W 3 3 9 系统（3个窗口）队长 68 3个个M/M/1 Excel求解求解 69 结论：银行取号系统是有效的结论：银行取号系统是有效的 指标指标数值数值 排队长度排队长度1.70 系统队长系统队长3.95 平均排队时间平均排队时间1.89 服务台空闲概率服务台空闲概率0.075 顾客必须等待的概率顾客必须等待的概率0.57 指标指标数值数值 排队长度排队长度2.25 系统队长系统队长9 平均排队时间平均排队时间7.5 服务台空闲概率服

43、务台空闲概率0.25 顾客必须等待的概率顾客必须等待的概率0.75 70 结论：银行取号系统是有效的结论：银行取号系统是有效的 从这两个系统的主要指标比较可以看从这两个系统的主要指标比较可以看 出出混合排队比独立排队具有显著的优混合排队比独立排队具有显著的优 越性越性，这一点是在排队系统的排队方，这一点是在排队系统的排队方 式的设计时应该注意的。式的设计时应该注意的。 71 普遍结论：集中使用优于分散使用普遍结论：集中使用优于分散使用 将资源组合在一起为所有的顾客提供服务，将资源组合在一起为所有的顾客提供服务， 可以在等待时间不变的条件下，减少所需要可以在等待时间不变的条件下，减少所需要 的资

44、源总量。如果是两列独立排队，那么客的资源总量。如果是两列独立排队，那么客 户可能要等那位指定的服务人员提供服务，户可能要等那位指定的服务人员提供服务， 这位服务人员可能当时正忙得抽不开身，而这位服务人员可能当时正忙得抽不开身，而 另一位服务人员却闲着没事干。在集中使用另一位服务人员却闲着没事干。在集中使用 的系统中就不会出现这种现象。的系统中就不会出现这种现象。 大规模制造或服务设施的规模经济学大规模制造或服务设施的规模经济学 u在保持同样利用率的情况下减少平均等待时间在保持同样利用率的情况下减少平均等待时间 u在保持同样平均等待时间的情况下提高利用率在保持同样平均等待时间的情况下提高利用率

45、72 5 排队系统最优设计排队系统最优设计成本分析成本分析 5.1 概述概述 排队系统的最优设计和最优控制，即排队系统的最优设计和最优控制，即 排队系统的最优化问题，其目的在于排队系统的最优化问题，其目的在于 使排队系统达到使排队系统达到最大效益最大效益或者说在一或者说在一 定指标下使排队系统定指标下使排队系统最为经济最为经济。 73 服务成本与等待成本的权衡（成本效益平衡）服务成本与等待成本的权衡（成本效益平衡） 总成本总成本 成本成本 最佳能力最佳能力 等待成本等待成本 服务成本服务成本 最小值最小值 排队分析的目的是使顾客等待成本与服务能力成本排队分析的目的是使顾客等待成本与服务能力成本

46、 这两项成本之和最小这两项成本之和最小 74 5.2 M/M/1模型中的最优服务率模型中的最优服务率u -1 最佳服务能力是使总成本最小化：最佳服务能力是使总成本最小化： 总成本总成本=顾客等候成本顾客等候成本+服务能力成本服务能力成本 1 w s w ss Cu C uC L C z 为时服务机构单位时间的费用 为每个顾客在系统中逗 即： 留时间的费用 /1 S M ML u 模型中 sw zC uC u 所以： 75 5.2 M/M/1模型中的最优服务率模型中的最优服务率u -2 sw zC uC u 0 dz du 令 2 0 () sw CC u 即： 所以所以M/M/1模型的最优服务率为：模型的最