运筹学导论教学课件PPT 排队系统教学PPT.ppt

1 第12章排队系统 2 agnerkraruperlang1878 1929丹麦电信工程师 排队论之父 研究人们打电话的方式 发展出人们需要等待多久的公式 并于1909年出版了关于排队理论的第一篇论文 3 ucla leonardkleinrock1934 互联网之父 影响本世纪的50人 ucla jamesr jackson1924 2011排队网络之父 排队论焕发了新的生命力 影响巨大 4 生活在城市中的居民在生产 生活以及学习消费的过程中 存在大量的排队现象 例如 食堂打饭 图书馆借还书 超市收银台 医院等待看病 车辆在信号灯控制路口排队等待通过 在银行柜台前很多顾客等待办理业务 城市中随时可能有急诊病人等待救护车的救援 港口外多艘万吨级船舶等待进港装卸货物 等待加工的零部件 等待装配的汽车等等 排队现象无处不在 12 1为什么要研究排队系统 5 排队现象的特征是 顾客以某种随机方式到达一个服务设施 之后在队列中等待 直到他们接受服务 一旦服务结束 通常离开系统 不花费极大的成本 等待现象是不可能完全消除的 我们的目标是要把他的不利影响减小到 可以忍受的 程度 6 7 为什么会产生排队现象 泛泛地说 是由于顾客需求量大于设施能提供的服务量 究竟又是什么原因导致服务设施的服务不足 原因很多 例如缺少服务点 提供的更多服务则经济上不可行 空间限制无法容纳更多的服务台 一般来说 当然可以通过增加投资建设更多的服务设施消除上述因素 但这需要分析 应该再增加多少服务台才可以消除排队 这就需要回答诸如 一个顾客必须要等待多久 排队长度会有多长 等很多问题 8 例mcburger是一家快餐店 有3个服务柜台 该店的经理委托他人调查顾客对服务速度慢的投诉 调查结果显示 服务台数量与服务等待时间之间有着如下关系 仔细观察这些数据 在3个柜台的情况下 平均等待时间要7分钟 需要5个柜台才能把等待时间减少到3分钟 排队分析的结果可以用在费用优化模型中 即求两种费用 服务费用和等待费用 之和的最小值 如下图 9 顾客等待时间成本 服务时间成本 总费用 服务水平 费用 最优服务水平 上图显示了一个典型的费用模型 使用费用模型的主要障碍就是很难估计可靠的等待费用 特别是当人的行为成为操作的有机组成部分时 10 分析排队系统的最终目的是为了对排队等待的顾客提供满意的服务 排队论主要研究服务设施的需求与用户延误之间的关系 其在分析和规划城市服务设施扮演重要角色 例如地铁闸机的设置 消防站及消防车的配置以及医疗救护点配置等等 在工业上的用途包括生产线的设计及布置 加工设备的配置 服务业中服务人员 柜台的设置及调配 研究排队论的目的 11 排队论 作为运筹学的重要分支 并不是一种优化理论 而是用于度量排队系统的性能指标 如队列的平均等待时间和服务设施的效率 这些度量指标可以用来设置服务设施 排队论的重点在于实际中排队分析结果的实施 为了充分理解排队系统的实际问题 就需要了解相当的基础理论背景 为此 首先介绍下构成排队系统的基本要素 然后介绍两个重要分布 泊松和指数分布 的 完全随机 性质 12 一个排队系统中的主要参与者是顾客和服务台 顾客从某个输入源产生 到达一个服务设施 他们可以立即得到服务 假如服务设施繁忙 也可能在队列中等待 当一个设施完成一次服务 如果有顾客等待的话 自动地 拉出 一个等待顾客 假如队列为空 设施就变成空闲 直到一个新的顾客到达 从分析队列的角度 我们用连续两个顾客之间的到达时间间隔表示顾客的到达 用对每个顾客的服务时间来描述服务 12 2排队模型的要素 13 组成排队系统的要素至少包括 顾客输入源 队列以及服务台 而服务台可以是单个的 也可以是多个并行联接的 如果要全面而准确的描述一个排队系统 则需要有如下6个要素 1 顾客到达模式 顾客发生源类型 2 服务台服务模式 服务台服务方式 3 排队规则 4 排队系统容量 5 服务通道数量 6 服务阶段数量 14 12 2 1顾客到达模式 排队系统的顾客输入源常常以单位时间内到达顾客的平均数量 meanarrivalrate 两个连续顾客之间的平均到达间隔时间 meaninterarrivaltime 来描述 进入排队系统的顾客流可以是确定型的 此时完全可以用平均到达率或者平均间隔时间来表示 如果进入排队系统的顾客流存在不确定性 此时用平均到达率或者平均间隔时间 仅能描述输入顾客的随机过程的集体趋势 如果要进一步完整地描述顾客到达模式 则需要顾客到达随机变量的概率分布 顾客到达模式可能不是一次到达一个顾客 而是一批一批到达的 此时相邻批次到达的间隔时间可能是随机的 每批次的顾客数量也是随机的 15 不同类型的顾客对于进入排队系统有不同的反应有些顾客将一直在队列中等待直到获得服务才离开 有些顾客会认为队列太长而不进入排队系统直接离开 有些顾客则是到了排队系统临时决定不参加排队 有些顾客则参与排队 但是失去耐心后决定离开系统 而有时候在服务台前有两列或更多的队列 则有些类型的顾客在不同队列之间来回排队 以缩短期望排队时间 后4种情况被认为是急躁型的顾客 如果顾客到达模式不随时间改变 随机型到达模式的参数不随时间变化 则认为是平稳的 反之则为非平稳的 16 服务率以单位时间内服务的顾客数量以服务一个顾客需要的时间当讨论服务台服务时间 总假定排队系统是存在顾客要服务 确定型随机型 在系统非空条件下服务台的概率分布服务设施中服务台个数单个 每次只能服务一个顾客多个 可以同时服务多个顾客 12 2 2服务台服务模式 17 先到先服务 firstcome firstserved 先进先出 firstin firstout 后到先服务 lastcome firstserved 库存系统 随机顺序服务 serviceinrandomorder siro 该规则不考虑顾客到达先后顺序 随机地选择顾客进行服务 优先权排队规则绝对抢先式 具有最高优先级的顾客即刻获得服务非绝对抢先式 具有最高级别的顾客即刻在队列的最前端排队 但不能马上接受服务 直到当前顾客 即使其级别较低 服务结束以后才能接受服务 12 2 3排队规则 在出现顾客排队的情况下 选择顾客进行服务的选择机制 18 在有些排队系统中 其排队等候区域受到物理空间限制 当队列达到一定长度时 后续的顾客无法进入等待区 除非当前接受服务的顾客接受服务后离开系统 后续新到顾客才被允许进入排队区等待 对于有限队列长度的排队系统 其到达的顾客可视为其到达数量必须累积到排队容量以后的成批的排队 这是最简单成批到达情况 原因在于顾客的批量是固定值 12 2 4排队系统容量 19 只有1个服务台的系统为单通道服务系统 在服务设施内设置多个并行的服务台是多通道服务系统 两类不同的多通道服务系统 一般来说 在排队论中都假设服务台是相互独立运作的多个服务台共同为一个队列服务每个服务台仅为本队列提供服务 12 2 5服务通道数量 在同一时刻能为顾客提供服务的并行服务台数量 20 排队系统中 许多服务设施提供的服务级数包括两类单级的 例如高速公路收费站 车站检票口等 多级的 例如医院的体检系统 多级服务也可能是循环的 例如在含有产品质量跟踪控制功能的产品生产线中 一旦零部件经过检测不合格 则需要重新送到生产线再进行处理 下图是带有循环 有时候也称之为反馈 服务的排队系统 12 2 6服务级数 21 上述6个排队系统基本特征元素 一般的可以充分的描述各种排队过程 从上述介绍也可以看出排队过程无处不在 排队模型的要素的总结 必须充分理解排队系统的这6个特征元素 以清楚掌握排队系统的运作过程 具体包括排队通道和服务设施之间是如何相互连接和影响的 顾客又是如何被分配到排队通道中的 22 12 3指数分布的作用 在大多数排队情况中 顾客的到达是完全随机的 这里的随机意味着 一个事件的发生 如一个顾客的到达或一项任务的完成 不受上一个时间发生以后所经过的时间长度的影响 排队模型中 随机到达间隔时间和服务时间用指数分布来定量描述 定义为 对于指数分布 exponentialdistribution 为单位时间内产生事件的速率 23 为什么指数分布是完全随机的 如何理解 假定现在是上午8 20 上一个顾客到达时间是8 02 下一个到达发生在8 29之前的概率只是8 20 8 29这一区间的函数 与上一个事件的发生 8 02 8 20 以来所流逝的时间长度完全无关 这个结果称之为指数分布的无记忆性 memoryless 8 02 8 20 8 29 24 令指数分布f t 表示相继事件之间的时间t的概率分布 如果s为上一个事件发生以来的时间区间 则遗忘性意味着 而 0 s s t s t t 证明 注意到对于平均值为1 的指数函数 我们有 p ab p b a p a 25 指数分布的无记忆性很重要 因为它意味着如果我们希望知道下次到达的时间概率分布 那么自上次到达以后流逝的时间长短不具有影响 我们假设到达时间间隔服从 6的指数分布 那么无记忆特性意味着自上次到达以后不管经过多长时间 那么下一次到达时间的概率分布仍然为6e 6t 这意味着要观测未来到达模式 我们不需要跟踪上一次到达之后经过了多长时间 这种观测可以简化排队系统的分析 26 例假设在银行花费的时间以均值为10分钟指数地分布 即 1 10 问一个顾客在此银行中花费15分钟的概率是多少 给定一个顾客10分钟以后仍旧在银行中 她在银行中将花费超过15分钟的概率是多少 解如果x表示顾客在这个银行中花费的时间 那么第一个概率正是第二个问题 由于指数分布 所以这个顾客已经在银行中花费10分钟是没有记忆的 这就意味着这个已经等待10分钟的顾客还要等5分钟 其概率正好是 27 12 4生灭模型 排队系统中 任意时间它的状态用这个时间在系统中的人数表示 则该状态取决于各个时刻进入和离开人数的速率 这样的系统称之为生灭过程 生灭过程例子很多 地区的人口增减 细菌或细胞的繁殖与死亡 服务台前的顾客数量变化等等 为了简化 只考虑只有到达的纯生模型和只有离开的纯灭模型 纯生模型的例子如为新生婴儿制作出生证明 纯灭模型的例子如一家商店对其库存货物的随机提货 28 12 4 1纯生模型 定义p0 t t时期内没有到达的概率已知到达时间间隔是指数分布的 并且每单位时间顾客到达率为 则 对于一个充分小的时间区间h 0 根据泰勒级数展开 有 指数分布基于假设 在充分小的h 0期间 最多有一个事件能够发生 因此 当h 0 这一结果表示 h期间一次到达的概率与h成正比例 到达率 为比例常数 29 定义某期间t内到达数目的分布pn t pn t t期间内有n个到达的概率在t期间内有n个顾客的组合 包括以下两种情况 对于充分小的h 0 根据互不相容的全概率公式 有 30 重新安排各项并取当h 0的极限 得到 其中是pn t 关于t的一阶导数 求解上述差分 微分方程 得到 这正是t期间平均有e n t t个到达的泊松分布 poissondistribution 上面的结果说明 若到达时间间隔服从平均值为1 的指数分布 则指定期间t内的到达数服从平均值 t的泊松分布 反之亦然 31 指数分布与泊松分布之间的关系 32 例某人口稀少州的出生率为每12分钟出生一个新生婴儿 出生间隔时间服从指数分布 求下列各值 1 每年出生的平均数 2 任何一天内无新生儿出生的概率 3 假设在3个小时时间内前2小时已经发出了40份出生证明 求这3个小时内发出50份出生证明的概率 每天的出生率为该州每年出生人口为任意一天没有新生儿出生的概率可以用泊松分布计算为 假设在3个小时内的前2小时已经发出了40份出生证明 计算3小时内发出50份出生证明的概率 相当于1小时 3 2 内出生10 50 40 个新生儿 因为出生数的分布是泊松的 33 12 4 2纯灭模型 在纯灭模型中 系统在0时刻开始时有n个顾客 后面没有新的顾客到达 离开的发生率为每单位 个顾客 为了建立t时间单位后剩下n个顾客的概率pn t 的差分 微分方程 根据出现n个顾客的情况 依据不相容的全概率公式 有 当h 0 得到 这组方程的解得到下面的截尾泊松 truncatedpoisson 分布 经过t时间还剩下n个顾客的概率 35 例某杂货店鲜花柜台每周初库存18打玫瑰花 平均情况下 鲜花柜台每天卖出去3打 一次一打 但实际需求量服从泊松分布 一旦库存水平剩下5打 就再订货补充到18打 下周一送货 由于鲜花商品的特性 周末没有卖出的玫瑰花就要扔掉 求下列值 1 该周内任何一天订货的概率 2 周末扔掉的玫瑰花的平均数量 36 因为购买的发生率为每天 3打 t日结束前订货的概率为 输出结果如下 周末 t 7 扔掉的玫瑰花平均数为e n t 7 为了计算这个值 我们需要用到pn 7 n 1 2 18 计算结果为 37 12 5广义泊松排队模型 本节利用生灭模型 建立一个通用的排队模型 再根据到达间隔和服务时间服从指数分布 推导出基于泊松分布的排队论模型 广义模型的建立是基于排队情形的长期行为 或平稳状态行为 这种状态在系统经过充分长时间的运行后得到的 这种分析和系统初期运行期间所常见的瞬时 transient 行为完全不同 本章不讨论瞬时行为的一个原因是由于对它的解析过于复杂 另一个原因是由于对大多数排队系统都是在平稳状态下来研究的 38 广义模型假设 到达率和离开率都是与状态相关的 statedependent 也就说系统的状态以服务设施中的顾客数量来度量的 例如 在高速公路收费口 在高峰时间收费员通常会提高收费速度 道路交通网络上的信号灯控制系统会依据交通流量的变化 信号配时作出变化 此时道路网络的状态也是依赖于状态的 定义n 系统中的顾客总数 排队 正在接受服务的 n 已知系统中有n个顾客的到达率 n 已知系统中有n个顾客的离开率pn 系统中有n个顾客的平稳状态概率广义模型中 pn作为 n和 n的函数 利用这些概率求出系统行为中的度量指标 例如平均队长 平均等待时间和设备利用率 39 如果以系统中的顾客数量来表示系统的状态 那么令排队系统中有n个用户的概率为pn 那么概率pn可以用下图的状态转移关系图来得到 根据第3小节的解释 在一个时间间隔h里多于1个事件发生的概率随着h 0而趋于0 这就意味着 对于n 0 状态n只能变成两种可能的状态 当以离开率离开时变成n 1 当按照到达率到达时变成n 1 状态0按照到达率到达时只能变成状态1 注意到 假如系统为空时 因为没有离开发生 没有定义 40 当系统处于平稳状态条件下 转入率等于转出率 也就说单位时间进入该状态的平均次数和单位时间内离开状态的平均次数要相等 所以 状态n只能变成状态 n 1 和状态 n 1 因此有类似地 系统平稳状态下 单位时间内转入和转出次数要相等 对于n 0的平衡方程为 n 1 n n 1 41 从p0开始递归求解平衡方程如下 对于n 0 有 接下来 对n 1 有 用替换并化简 得到 用归纳法可以得到如下广义稳态概率公式 从p0的值可以从等式求出 42 解得 43 例b k食品店有3个收款台 经理根据店内顾客数量 按照下列安排决定提供服务的收款台个数 顾客按照平均10位 小时的泊松分布来收款区 每位顾客的平均收款时间为指数分布 平均为12分钟 求n个顾客在收款区的平稳状态概率pn 根据本题的信息 有 44 因此 p0的值从下面的等式求出 利用几何级数得到 45 因此 p0 1 55 知道了p0 就可以求出pn 进而可以计算出系统中使用不同收款台个数的概率 例如使用一个收款台的概率就是最多出现3个顾客的概率 p1 p2 p3 46 12 6特殊泊松排队 12 6 1排队系统的kendall lee的符号表示 下图显示带有c个并行服务台的特殊泊松排队情形 系统中的顾客数定义为正在接受服务的顾客加队列中等待服务的顾客 服务台1 服务台1 服务台1 服务台1 服务台1 服务台1 47 为了方便表示上图排队的情形的特性 采用下面的格式 a b c d e f 其中 a 到达分布 b 离开 服务时间 分布 c 并行服务台个数 d 排队规则 e 系统中最大运行容纳的顾客数 f 顾客输入源的多少 有限或无限 表示到达和离开分布 a和b 的标准记号有m 马尔科夫或泊松分布 d 常数 确定型 时间 ek 参数为k的埃尔朗或 分布 等价于独立指数分布和 gi 到达间隔时间的一般性 通用分布 g 服务时间的一般性 通用分布排队规则 符号d 包括fcfs 先到先服务 lcfs 后到先服务 siro 随机秩序服务 gd 一般 任意规则 m d 10 gd 20 m e2 8 fcfs 10 48 12 6 2队列行为的平稳状态度量 ls 系统中顾客的期望数量lq 队列中顾客的期望数量ws 系统中的期望等待时间wq 队列中的期望等待时间 繁忙服务台的期望数 最常用的队列行为度量指标有 系统包括队列加上服务设施 下面说明如何利用系统的状态n及其平稳状态概率pn得到上述的度量指标 49 首先根据数学期望得到 系统中期望的顾客数 队列中期望的顾客数 平均队长 而ls与ws 以及lq与wq 之间的关系称为little公式 littleformula 具体关系包括如下 系统中平均顾客数量与驻留系统的时间之间满足 队列中期望的顾客数 平均队长 与排队时间满足 上述关系在相当一般的条件下成立 参数 eff是系统的有效到达率 当所有到达的顾客都可能加入时 就为 如果系统满了 存在容量限制系统 则顾客不能加入 eff 清华版p319不准确 50 ws和wq之间也存在直接的关系 由定义希望系统驻留时间 期望排队时间 期望服务时间可以写成 对上式两边乘以 eff 建立ls与lq的关系 结合little公式 得到 根据定义 系统的平均顾客数与队列中平均的顾客数的差值等于繁忙服务台的平均数 因此有 因此 得到了设施利用率 51 例ozark学院来访者的停车位只有5个 使用这些停车位的车辆以泊松分布到达 每小时到达6辆车 停车时间服从均值为30分钟的指数分布 到达后找不到空泊位的来访者可以在停车场边临时停车位等待 直到有停着的车辆离开 临时车位只能放3辆车 而停不了也找不到临时停车位的车辆必须去别的地方停车 求 1 系统中有n辆车的概率 2 实际使用停车场的车辆的有效到达率 3 停车场平均的停车数量 4 一辆车在停车场内等待停车位的平均时间 5 占据停车位的平均车辆数 6 停车场的平均使用率 注意到 一个停车位就是一个服务台 这样 系统共有c 5个并行的服务台 另外 系统的最大容量为5 3 8辆车 可以按照之前介绍的pn计算 52 将 n和 n代入下面的公式 得到 p0 0 04812 53 有了p0 可以计算p1到p8如下 实际使用停车场的车辆的有效到达率的计算取决于停车场是否满了 有效到达率可以通过如下示意图计算车辆可以以 eff进入停车场或者以 lost离开 假如8辆车已经在停车场 则到达的车便不能进入停车场的概率为p8 因此 54 停车场内车辆的平均数等于系统内车辆的平均数ls 我们可以用pn计算出ls 在临时车位等待的车辆实际上就是队列中的车辆 因此 等待找到车位的等待时间就是wq 为确定wq 用 因此 占用了车位的平均车辆数就与繁忙服务台的平均数相等 55 12 6 3单服务台模型 本节介绍仅有一个服务台到达率为 服务率为 的排队服务系统 首先讨论系统容量无穷大的情形 再讨论系统容量有限情形 之前介绍的各种排队系统的性能指标与具体的排队规则没有关系 所以我们用一般排队规则gd m m 1 gd 基本假设如下 与排队系统状态无关 56 令 将其称之为服务强度或业务密度 则广义模型中pn的表达式简化为 为了求p0的值 用等式 设 1 利用几何级数求和公式有 所以 所以 pn的数学推导将用到条件 1或者 如果 则几何级发散 平稳态概率不存在 这个结果有直观的意义 除非服务率大于到达率 否则队列长度将不断增长 不可能到达平稳状态 57 排队系统的性能度量指标ls可以按照下面的方式得到 因为对于本情形 剩下的系统性能度量指标用6 2节的关系来计算 因此有 58 例automata洗车房只运行一个清洗位 车辆按照泊松分布到达 平均每小时4辆车 如果清洗位忙 则到达的车辆等在洗车房的停车场 一辆车的清洗时间服从指数分布 平均值为10分钟 不能进停车场的车辆可在洗车房的路边等待 这意味着从实际上来说 系统是没有容量限制的 为洗车房确定出停车场合适的停车泊位数量 该例中 4辆车 小时 60 10 6辆车 小时 因为 1 系统可以按照平稳状态运行 一般来说 不建议只用ls来计算停车位数 因为从某种意义上 停车位代表了要保证最大可能的队列长度 59 例如 停车场的设计要使得来到的车在至少90 的时候能找到停车位 为了做到这一点 令s表示停车位数 有s个停车位等价于系统中有s 1个位置 假如系统中最多有s个停车位 则到达的车辆90 的时候都能找到位置 这个条件等价于下面的概率条件 即 根据有限项的几何技术求和公式 有 所以 两边取对数 注意到ln x 0 0 x 1 不等式变号 60 m m 1 gd 的等待时间分布 广义模型中得到的pn与排队规则完全无关 这意味着 排队系统性能的平均度量指标 ws wq ls lq 可以用于所有排队规则 虽然平均等待时间与排队规则无关 但它的概率密度函数却不然 我们基于fcfs规则的m m 1模型导出等待时间的分布来说明 令 为刚刚到达的一位顾客为了获得服务必须驻留在系统的时间 根据fcfs规则 假如一个刚刚到达的顾客前面还有n个顾客在系统中 则其中是当前在接受服务的顾客所需要的完成服务的时间 t2 t3 tn为队列中的n 1个顾客的服务时间 时间tn 1表示刚刚到达的这个顾客的服务时间 61 定义为已知系统中有n个顾客在刚刚到达的顾客之前的条件下 的条件密度函数 因为服务时间的分布是指数的 指数分布的遗忘性质表明 也是指数的 服从相同的分布 因此 等于 n 1 个同分布的独立指数随机变量之和 由概率论可知 服从带有参数和 n 1 的 分布 因此有 因此 为一指数分布 平均值为 62 例automata洗车房只运行一个清洗位 车辆按照 4辆车 小时泊松分布到达 该服务根据fcfs规则进行的 一辆车的清洗时间 60 10 6辆车 小时 如果清洗位忙 则到达的车辆等在洗车房的停车场 不能进停车场的车辆可在洗车房的路边等待 评价用ws作为估计系统中等待时间的可靠性 回答这个问题的一个方法是 估计顾客中等待时间超过ws的比例 注意到 我们得到 在fcfs规则下 大约37 的顾客的等待时间比ws要长 我们注意到所计算的概率e 1与任何 m m 1 fcfs 的到达率和服务率都无关 这意味着它的值不能减少 这样 如果我们以ws来设计系统的话 将有36 8 的顾客的等待时间长于平均等待时间 63 m m 1 gd n 模型 这个模型和 m m 1 gd 不同之处在于 系统最多容纳的顾客数 最大队列长度为n 1 为n 例如流水线上放置工件的空间是有限的 当系统中的顾客数达到n时 不允许再有到达 因此有 利用 根据广义模型的稳态概率公式 可以从等式求出p0的值 这将得到 64 或 因此有 在这个模型中 的值不需要小于1 因为系统的到达受到系统顾客上限n的限制 这意味着在这种情况下 重要的是到达率 eff而不是 由于系统中有n个顾客 再来的顾客就不再进入系统 此时 系统中期望顾客数可以计算为 当时 ls n 2 同样从ls 利用 eff求出ws wq lq 66 m m 1 gd m 模型 这个模型和 m m 1 gd 不同之处在于 系统的顾客源的顾客总数为m 例如最常见的是机器发生故障停机待修的问题 此时总共有m台机器 机器发生故障即表示顾客 到达 修理工人是服务员 类似的问题还有m个打字员共有一台打字机 虽然顾客有m个 但每个顾客到达并经过服务以后 仍然回到原来的发生源中 所以仍然会到达 顾客源总数达到m时 此时顾客单位时间内的到达次数依赖于当前尚未到达系统的顾客数 假设每个顾客进入系统的到达率为 进入系统的顾客为n 0 n m 则系统外的顾客为m n 所以系统的到达率 而系统的离开率取决于服务台数量为1 此时有 67 根据广义模型 有 根据根据 有 注意 此时不要求成立 68 根据little公式以及系统期望公式 有 69 12 6 4多服务台模型 本节考虑有多个并行服务台的3个排队模型 前两个是上一节介绍的单服务台的多服务台版本 第三个模型针对自助服务的情况 等价于无限个并行服务台情形 m m c gd 模型 在这个模型中有c个并行的服务台 到达率为 每个服务台的服务率为 因为对系统中的排队人数没有限制 所以 使用并行服务台的效果使得设施的服务率成比例的增加 根据广义模型 第五节 70 因此 根据广义稳态概率计算公式 p0的值可以从求出 得到 71 系统的运行指标如下 72 例某社区由两家出租车公司提供服务 每家公司有2辆出租车 且两家公司平等分享市场 事实上 叫车电话到达每家公司的派车办公室的到达率为每小时8次 每次乘车的平均时间为12分钟 叫车电话按照泊松分布到达 乘车时间服从指数分布 最近这个两家公司被一个投资商购买了 他打算把这两个派车办公室合成一个 以便为顾客提供更为优质的服务 请分析老板的建议 从排队论角度来看 出租车是服务台 乘坐出租车就是服务 每家公司都可以表示为 8次 小时 出租车 60 12 5次 小时乘坐的 m m 2 gd 模型 合并以后得到 m m 4 gd 模型 其参数为 16次 小时 5次 小时 73 根据参数 利用排队系统运行性能指标计算公式得到下表 可以看到 等待乘车的时间在两台出租车情况下为0 356 合并后情况为0 149小时 明显减少了50 多 公司合并以后效果非常明显 以上的结论是 共同分担服务总是一种更加有效的运作模式 74 m m c gd n c n模型 这个模型与 m m c gd 模型不同之处在于 系统上限是有限的并且等于n 这就意味着 最大队列长度是n c 到达率和服务率分别是 和 因为系统上限是n 因此有效到达率小于 按照广义模型 当前模型的 将上述代入稳态概率 第五节 的公式 得到 75 p0的值可以从求出 得到 排队系统的运行指标如下 76 例在合并的出租车公司问题中 假设没有新的经费来购买更多出租车 又一个咨询专家向老板建议 有一种减少等待时间的办法是 一旦有6个顾客在等待用车 就让派车办公室通知新的顾客 告诉他们等待时间可能会很长 这种举动定会让新的顾客去寻求别的公司的服务 但将会减少等式顾客的等待时间 请评价这位专家的建议 将等待的顾客数限制在6个以内就等价于设定n 6 4 10个顾客 因此专家建议的排队模型为 m m 4 gd 10 其中 16次 小时 5次 小时 77 77 在设置系统能力上限之前的平均等待时间为wq 0 149小时 大约是新的平均等待时间0 075小时的两倍 等待时间的大幅度减少的代价是流失了大约3 6 的潜在顾客 p10 0 03574 这个结果还不能反映顾客对公司经营印象的损害效果 78 m m gd 自助服务模型 在这个模型中 因为顾客本身也是服务台 因此服务台数量无限 该模型的一个典型例子是参加进入系统选课的学生人数 在某个行业的公司数量 这个模型假设稳定的到达率和服务率分别为 和 按照前面的广义排队模型 有 因此有 p0的值可以从求出 得到 79 排队系统的运行指标如下 例一个投资者每月平均投入1000美元购买一种股票市场的债券 因为这个投资者必须要等待好的 买入 机会 实际发生的购买时间是完全随机的 该投资者平均要把债券保留3年 但是当好的 卖出 机会来了 他会在随机的时间把它卖掉 根据过去的统计表明 这个投资家大约25 的债券每年下跌20 左右 其余的75 每年上涨12 左右 请估算这个投资者在股票市场的 长期 平均资产净值 80 从实际情况看 这位投资者并不需要排队等待债券的买入或者卖出 买卖间隔的平均时间是1个月 因此每年有 12只债券 债券的销售率为每年 1 3只债券 此时每只债券就是就是服务台本身 有多少债券就有多少服务台 这一情形符合 m m gd 模型 已知 和 得到 该投资者的预计 长期 平均年度净值为 81 机器伺服模型 m m r gd k k r k 这个模型的背景是有k台机器的车间 当1台机器出现故障时 就呼叫r个有时间的修理工之一来进行修理 每台机器的故障率为每单位时间 次故障 每个修理工修理故障及其的服务率为每单位时间 台机器 所有的故障和服务假定都服从泊松分布 这个模型类似于前面介绍的 m m 1 gd m 模型 区别在于 本模型中有r个修理工 82 本模型有有限个输入源 原因在于 此时总共有k台机器 机器发生故障即表示顾客 到达 修理工人是服务员 虽然有k台机器 但每个发生故障的机器经过维修以后回到良好状态 但是容易再次发生故障 所以仍然会有 顾客 到达 顾客源总数达到k时 此时顾客单位时间内的到达次数依赖于当前尚未到达系统的顾客数 假设每个顾客进入系统的到达率为 进入系统的顾客 即等待维修的机器 为n 0 n m 则此时有机器出现故障的发生率取决于完好状态的机器数量k n 即 83 根据广义排队模型 根据广义排队模型的稳态概率计算公式 可以得到 84 遗憾的是 在 m m r gd k k 模型 r k 中 没有计算ls lq ws和wq的简单的 封闭型的表达式 必须用下面的基本定义来计算 其中 例toolco公司经营一家22台机床的工厂 已知每台机床平均每2小时发生一次故障 修理工作平均需要12分钟 故障间隔时间均服从指数分布 toolco想要确定修理工数量 以保证工厂能 平稳的 运转 85 要分析该情况 考察作为修理工数的函数的机床生产率 这一生产率的度量可以定义为 该情形属于 m m r gd k k 模型 其中 0 5 5 r 1 2 3 4 系统上限 22 输入源 22 根据前面的计算公式得到 86 上述结果说明 用1个修理工时 生产率很低 45 44 把修理工增加到2个时 生产率增加到80 15 上升了34 71 当雇用3个修理工时 生产率只增加了8 64 提高到88 79 而4个修理工只把生产率增加很小量1 66 提高到90 45 从这些结果可以判断出 用2个修理工最划算 用3个修理工的效果不明显 因为生产率只提高了8 64 当然我们可以用经费上的比较来确定是否划算 这需要对第三个修理工的成本和8 64 的生产率提高所带来的收入进行比较 至于雇用第4个修理工 生产率的微量增长1 66 不支持这样的计划 87 12 7如何断定泊松分布和指数分布 之前介绍的各种排队模型均要求到达和服务间隔时间服从指数分布 也就是到达个数服从泊松分布 在实际中 有时不能预知总体服从什么类型的分布 那么 如何判断到达的顾客是服从泊松分布或者是指数分布的 这就需要根据样本来检验关于分布的假设 本节介绍最常见的方法 88 根据样本x1 x2 xn来检验关于总体分布的假设h0 总体x的分布函数为f x h1 总体x的分布函数不是f x 这里被择假设h1可以不需要写出 注意 如果总体x为离散型则假设 1 相当于h0 总体x的分布律为p x ti pi i 1 2 如果总体x为连续型 则假设 1 相当于h0 总体x的概率密度函数为f x 在用检验假设h0时 若在假设h0下f x 的形式已知 当其参数值未知 这需要用极大似然估计法估计参数 然后做检验 1 2 3 89 将随机试验可能结果的全体 分为k个互不相容的事件于是在假设h0下 我们可以计算在n次试验中 事件ai出现的频率fi n与往往有差异 但一般来说 若h0为真 且试验的次数有较多的时 则这种差异应该不是很大 基于这种想法 皮尔逊使用 90 定理若n充分大 n 50 则当h0为真时 不论h0中的分布属于什么分布 统计量 4 总是近似地服从自由度为于是 若在假设h0下算得 4 有则在显著性水平下接受h0 否则就拒绝h0是基于上述定理得到的 所以在使用时必须注意n要足够大 以及npi不太小 根据实践 要求样本容量不小于50 以及每一个npi都不小于5 而且npi最好是在5以上 否则应适当地合并ai 以满足这个要求 91 例在一个实验中 每隔一定时间观察一次由某种铀所反射的到达计数器上的 粒子数x 共观察了100次 结果如下表所示 其中fi是观察到有i个 粒子的次数 从理论上考虑x应该服从泊松分布是否符合实际 取 0 05 92 即在水平0 05下检验假设h0 总体x服从泊松分布 应在h0中 参数 未给出具体值 所以先估计 由极大似然估计法得到如上表中将试验可能结果的全体分为两两不相容的事件a0 a1 a12 则p x i 有估计 93 94 计算结果如上表所示 其中有些的组予以适当合并 使得每组均有 如表中第4列合并处所示 此处 合组后k 8 但因在计算概率时 估计了一个参数 故的自由度为8 1 1 6 因为故在水平0 05下接受h0 即认为样本来自泊松分布总体 也就是说认为理论上的结论是符合实际的 95 例自1965年1月1日至1971年2月9日共2231天中 全世界记录到里氏震级4级和4级以上的地震共162次 统计如下表 试验相继两次地震间隔的天数x服从指数分布 0 05 解 按照题意需要检验假设h0 x的概率密度为 96 在这里 h0中未给出参数 的值 先有极大似然估计法求出 的估计值为x为连续型随机变量 我们将x可能取值的区间 0 分为k 9个互不重叠的子区间 ai ai 1 i 1 2 9 如下表的第二列所示 取ai ai x ai 1 i 1 2 9 若h0为真 x的分布函数的估计为 由上式可得概率pi p ai 的估计 例如而 97 因为故在水平0 05下接受h0 认为x服从指数分布 98 分布检验的步骤根据实际问题的要求 提出原假设h0及备择假设h0根据极大似然估计 确定检验分布的参数将样本值放到互不相容的事件区间上 确定各事件的发生频次根据统计量的计算结果 与结果比较根据比较结果 确定接受还是拒绝h0 99 12 8一般服务时间m g 1模型 前面讨论的排队模型到达时间和服务时间均服从指数分布 这类系统的主要特征是markov特性 即未来状态仅由当前系统的状态决定 但是当到达时间间隔和服务时间间隔至少至少有一个不服从负指数分布时 仅靠当前状态不足以推断未来状态 这样的排队模型称为非马氏排队模型 这类排队模型非常复杂 对于这类情形的分析 我们将在以后介绍采用模拟方法来研究 100 m g 1 gd 排队模型 本节介绍一个很少出现的具有解析结果的非泊松排队 它所描述的情况是 服务时间t服从任何概率分布 平均值为e t 方差为var t 这个模型的结果包括系统性能的基本指标ls lq ws和wq 由于公式非常复杂 这个模型没有pn的封闭型表达式 令 为单服务台设施的到达率 已知服务时间分布的e t 和var t 并且 e t 1 我们可以通过复杂的概率论 马尔可夫链分析来证明 这就是著名的pollaczek kbintchine p k 公式 101 服务设施为空闲的概率可按照下面公式求出 由 eff 根据little公式可以从ls求出来 102 例automata洗车房只运行一个清洗位 车辆按照泊松分布到达 平均每小时4辆车 如果清洗位忙 则到达的车辆等在洗车房的停车场 现在安装了新的洗车系统 对所有车辆的服务时间均为10分钟 该系统有何影响 eff 4辆车 小时 服务时间为常数 这样e t 1 6小时 方差var t 0 因此 103 有意思的是 虽然到达率和离开率与前面p58的泊松分布情况相同 4辆车 小时 6辆车 小时 但是这个模型的期望等待时间要少 因为服务时间为常数 如下表 因为常数服务时间表示该设施的运行更加确定 所以这个结果是合理的 104 m d 1 gd 排队模型 m d 1 gd 排队模型中 服务时间服从定长分布 其平均服务时间为1 方差为0 这时可以将p k公式改为 其余指标为 上式中的lq是m m 1模型排队长的1 2 即md1模型排队长更短 可以证明在一般的服务时间分布中 定长分布的排队最小 即服务时间的不确定性越小 方差越小 等候时间越短 105 m ek 1 gd 排队模型 m ek 1 gd 排队模型中的服务时间服从k阶erlang分布 多个服务台串联式 每个服务台的服务时间相互独立且服从相同的参数k 的负指数分布 这就是总服务时间服从k阶erlang分布 根据p k公式改写为 1 2 k k k k 106 例某单人裁缝店做西服 每套西服经过4个不同的工序 4个工序完成以后才开始做另外一套 每一工序的时间服从负指数分布 期望值为2小时 顾客来到服从泊松分布 平均订货率为5 5套 周 设一周6天 每天8小时 问顾客为等到做好一套西服期望时间要多长 解顾客到达 5 5套 周 设 平均服务率 单位时间做完的套数 1 平均每套所需要的时间 1 4 平均每道工序所需要的时间 由题设1 4 2小时 1 8 套 小时 6 套 周 5 5 6 107 12 9排队系统最优化 排队吸引的最优化问题有两类 系统设计的最优化 静态问题 目的在于使得设备达到最大效益 在一定质量指标下要求机构最为经济系统控制最优化 动态问题 对给定的控制系统 如何运营可使得某个目标函数得到最优 本课程仅仅讨论静态问题 108 在一般情况下 提高服务水平会降低顾客等待费用 但增加服务机构的成本 优化的目的是使得顾客等待费用和机构服务费用之和最小 决定到达这个最优目标的最优服务水平 使得纯收入或者使得利润 服务收入减去服务成本 为最大 顾客等待时间成本 服务时间成本 总费用 服务水平 费用 最优服务水平 109 各种费用在稳态情形下 都是按单位时间来考虑的 一般情形 服务费用是可以确切计算的 但是顾客等待费用存在很多情形 比如机械故障等待费用 病人就诊等待费用 队列过长失掉潜在的顾客的损失 只能依赖于调查和历史数据 服务水平也可以由不同形式来表示 主要是平均服务率 代表服务机构的服务能力和经验 服务台个数c 以及排队系统容量 服务水平也可以以服务强度 来表示 常用的方法 离散变量常用边际分析法 对于连续变量常用经典的微分法 对于复杂问题还可以用非线性规划和动态规划的方法 110 m m 1模型中最优服务率 1 m m 1模型取目标函数z为单位时间服务成本与顾客在系统逗留费用之和的期望值z cs cwls其中cs为当 1时服务机构单位时间的费用 cw为每个顾客在系统停留单位时间的费用 将上式代入ls之值代入得为了求极值 先求 然后令其为0 111 2系统容量为n的情形系统如果已经有n个顾客 则后来的顾客即被拒绝 则pn 被拒绝的概率 损失率 1 pn 能接受服务的概率 1 pn 单位时间进入服务系统的平均顾客数量 在稳态下 它等于单位时间内实际服务完成的平均顾客数 设每服务1人能收g元 则单位时间收入的期望为 1 pn g元 纯利润 为了求极值 先求 然后令其为0 得 求解 通常非常困难 可以通过数值计算的办法来求解 或者对n做 的函数曲线 对于给定的g cs 根据曲线求出 112 3顾客源为有限的情形仍然按照机械故障问题来考虑 设共有m台机器 各台连续运转时间服从负指数分布 有1个修理工人 修理时间服从负指数分布 当服务率 1时的修理费用cs 单位时间每台机器运转可得g元 平均运转台数为m ls 所以单位时间纯利润为 对上式直接求解 通常非常困难 通常的办法是 在服务率上依次增加一定单位的值 进而计算出不同服务速度下的 进而代入上式来计算纯利润 通过比较确定 113 m m c gd 模型中最优服务台个数c 在稳态条件下 单位时间的费用 成本 利润或者成本 等待费用 函数的期望函数为g为每服务1人的收入 为单位服务成本 为顾客等待费用 则根据问题性质 两种方法确定最优服务台数 1 可以运用边际分析方法 即在每次增加1个服务台 即计算排队长度 根据上述公式计算目标函数结果 再计算每增加一个服务台的的目标函数与前一次的目标函数的差值 这个差值即为边际收入 边际收入最大的那个服务台数即为最优服务台个数 2 每次增加1个服务台 直接计算目标函数结果 选择合适的函数目标所对应对应的服务台个数为最优值 114 一家有多个员工的工具库 交换工具的请求按照泊松分布发生 每小时有17 5个请求 每个员工每小时平均办理10个请求 工具库雇用1名新员工的工资是 12 每小时每台等待车床的生产损失为 50 求该工具库最优的员工数量 上述问题对应着m m c模型 要确定c的最优值 费用模型为 每小时 17 5个请求和每小时 10个请求 注意到当c 时 排队系统处于稳态 依次增加服务台个数 计算ls及成本 结果表明 最优员工数为4 115 12 10排队网络 当一组资源由一组顾客共享时形成了排队网络 每个资源表示一个可能有多个服务台并行工作的服务中心 如果一个到达的顾客发现一个特定的中心繁忙 他可能加入该中心的队列等候服务 也可能离开该队列去寻找其他类型的服务 在一站服务结束后 该顾客可能转入另一个服务中心 或者重新进入同一个中心 或者离开系统 116 在下图的串连队列中 一旦一个顾客进入系统 他将必须留在系统中直到接受了全套服务 通常 每个服务台前都运行等候 前面讨论的m ek 1模型是这种串连模型的特例 在m ek 1模型中除了第一个服务台前可以有等候队列 其他的服务台是不允许有等候的 在这种情况下 必须是n个服务项目都结束以后 一个新的顾客才运行进入系统接受服务 12 10 1开放排队系统 串联系统或序贯系统 117 服务网络行为由输出分布 各服务台的服务时间分布以及输入分布和各种排队规则共同确定 在一个串连网络中 由于一个服务台的输出是下一个服务台的输入 网络的稳态性质由队列的输出分布共同规定 在这个方面 burke已经证明 在一个m m r队列中 稳态时的离开时间间隔是独立的随机变量 而且 这样一个队列的输出构成了一个泊松过程 其