运筹学课件第11章排队论.ppt

第11章排队论 重庆三峡学院关文忠 教学目标与要求 教学目标 1 理解下列基本概念 排队系统构成 特征 分类 主要性能指标及相互关系2 掌握以下三种排队系统主要性能指标的计算 M M C M M C N M M C m 3 了解M G 1 M D 1的主要指标计算公式 知识结构 导入案例 主任医师招聘问题 某三甲医院肝胆内科有主任医师1名 由于他的存在而使前来诊疗的患者大增 根据一个月的统计 平均每h到达医院的患者6名 并对各时间段统计 经回归符合泊松分布 该医生每h可诊疗4名 但患者病情不同 分布也不是均匀的 对每位患者就诊时间的统计 经回归 符合指数分布 医院配备有电子回馈信息系统 及时观察到已挂号排队等候的患者数量 当排队等候人数少于5人时 挂号系统可以挂号 当前来就诊的患者挂上号若医生空闲则可直接就诊 否则排队等候 医生采取先到先服务的规则 若前来就诊的患者挂不上号 则立即到邻近的一家医院就诊 经统计 经该主任医师诊疗的患者 其诊疗费 检验费 医药费等医院可获纯收入100元 主任医师可高薪聘请 其薪金及住房和各种福利年均25万元 医院实行每周5天工作制 年工作日250天 平均每天支付1000元的成本 当医生过少 由于患者得不到服务离去而产生的损失增加 当医生过多 由于医生空闲时间的增加也使医院的成本增加 问 医院应招聘多少名肝胆内科主任医师可使得盈利最大 导入案例 主任医师招聘问题 此类排队现象在日常生活中经常遇到 如客户到银行排队办理存贷款业务 出纳员为客户提供服务 汽车到加油站排队 加注系统为汽车提供加油服务 超市顾客到收银台前排队 收款员为顾客提供交款服务 旅客到公交车站排队 公交车为旅客提供位移服务 排队论的基本思想是1910年丹麦电话工程师A K 埃尔朗在解决自动电话设计问题时开始形成的 当时称为话务理论 他在热力学统计平衡理论的启发下 成功地建立了电话统计平衡模型 并由此得到一组递推状态方程 从而导出著名的埃尔朗电话损失率公式 自20世纪初以来 电话系统的设计一直在应用这个公式 20世纪30年代前苏联数学家欣钦把处于统计平衡的电话呼叫流称为最简单流 瑞典数学家巴尔姆又引入有限后效流等概念和定义 美国数学家费勒 W Feller 关于生灭过程的研究 20世纪50年代初 英国数学家D G 肯德尔提出嵌入马尔可夫链理论 以及对排队队型的分类方法 为排队论奠定了理论基础 20世纪70年代以来 人们开始研究排队网络和复杂排队问题的渐近解等 成为研究现代排队论的新趋势 本章主要内容 11 1基本概念11 1 1排队系统的一般表示11 1 2排队系统的三个特征11 1 3排队系统模型的分类11 1 4排队系统的主要性能指标11 1 5排队系统的输入和输出11 2生死过程11 3单服务台排队系统模型11 3 1M M 1 标准系统 11 3 2M M 1 N 系统容量有限 11 3 3M M 1 m 顾客源有限 11 4多服务台排队系统模型11 4 1M M s 系统11 4 2M M s N 系统11 4 3M M s m系统 11 5其他排队系统模型11 5 1一般服务时间M G 1模型11 5 2定长服务时间M D 1模型11 5 3埃尔朗服务时间M Ek 1模型11 5 3具有优先服务权的排队模型11 6排队系统的优化11 6 1M M 1模型中的最优服务率11 6 2M M s模型中的最优服务台数本章小结 11 1 1排队系统的一般表示 11 1 2排队系统的三个特征 排除系统的三个特征是指 输入过程 排队规则 服务机构 1 输入过程输入是指顾客到达服务系统的情况 可能有下列情况 但并不相互排斥 1 按顾客源总数划分为有限和无限两大类 如工厂需要检修的机器是有限的 准备进京观光旅游的游客是无限的 2 按顾客到达的人数可以划分为单个到达和成批到达 如到超市购买商品的顾客是单个的 到港国际航班等待安检的旅客是成批的 3 按顾客到达时间间隔是否固定可以划分为确定型和随机型 如定期运行的班车 班轮 班机是确定的 到加油站加油的汽车是随机的 对随机的顾客到达需要知道单位时间到达的顾客数或时间间隔的概率分布 4 按接受过服务的顾客对顾客到达数是否有影响 划分为相互独立到达和非相互独立到达 如提供优质服务的餐饮业所产生了大量 回头客 就属于非相互独立到达 我们只讨论独立到达情况 5 按顾客相继到达间隔时间的分布及其数字特征是否与时间有关可分为平稳与非平稳的 相继到达的间隔时间分布及其数学期望 方差等数字特征都与时间无关 称为平稳的 否则是非平稳的 一般非平稳情况的数学处理很困难 我们只讨论平稳状况 11 1 2排队系统的三个特征 2 排队规则排队规则指到达排队系统的顾客按怎样的规则排队等待 1 按顾客到达排队系统时发现服务设施已被占用是否离去可分为损失制 等待制和混合制三种 当顾客到达时 所有的服务台均被占用 顾客随即离去 称为损失制 或称即时制 消失制 当顾客到达时 所有的服务台均被占用 顾客就排队等待 直到接受完服务才离去 称为等待制 例如出故障的机器排队等待维修就是这种情况 介于损失制和等待制之间的是混合制 对于等待制 有下列服务规则 先到先服务 FCFS 先到后服务 LCFS 带优先服务权 PR 随机服务 SIRO 等 在后面研究的问题中均假设采取FCFS服务规则 2 按队列长度是否有限 可分为队长有限和队长无限两种情况 在限度以内就排队等待 超过一定限度就离去 3 按排队方式分为单列 多列 对于多列排队的顾客有的可以相互转移 有的则不能 用栏杆等隔开 有的排队顾客因等候时间过长而离开 有的则不能 如在高速公路行驶的汽车必须坚持到高速出口 我们所讨论的问题限制在队列间不能相互转移 中途不能退出的情形 11 1 2排队系统的三个特征 3 服务机构从机构形式和工作情况来看有以下几种 1 服务机构可以没有服务员 也可以有一个或多个服务员 服务台 窗口 如超市的货架可以没有服务员 但交款时可能有多个服务员 2 多个服务台的情况中 可以是平行排列的 并联 也可以是前后排列的 串联 也可以是混合的 3 服务方式可以对单个顾客进行 也可成批进行 我们只讨论单个服务情况 4 服务时间可分为确定型的和随机型的 如旅客列车对乘客的服务是按列车时刻表进行位移服务的 是确定型的 因患者病情不同 医生诊断的时间不是确定的 是随机型的 5 服务时间的分布总假定是平稳的 即分布的期望值 方差等参数不受时间的影响 11 1 3排队系统模型的分类 肯德尔 Kendall 于1953年提出了排队服务系统的分类记号 输入 输出 并联的服务站数1971年国际排队符号标准会上肯德尔将上述分类记号扩充到六项 记为 输入 输出 并联的服务站数 系统容量 队长 系统状态 顾客源数 服务规则 11 1 4排队系统的主要性能指标 求解排队问题的目的 是研究排队系统运行的效率 估计服务质量 确定系统参数的最优值 以决定系统结构是否合理 研究设计改进措施等 因此必须确定用以判断系统运行优劣的基本数量指标 1 常用指标 1 队长 Ls 和排队长 Lq 队长指系统内顾客数 包括正在接受服务的顾客与排队等待服务的顾客数 排队长 即系统中的顾客数 排队等候服务的顾客数 正在接受服务的顾客数 2 逗留时间 Ws 和等待时间 Wq 逗留时间指顾客在排队服务系统中从进入到服务完毕离去的平均逗留时间 等待时间指顾客排队等待服务的平均等待时间 这对顾客来讲是最关心的 每个顾客希望逗留时间或等待时间越短越好 3 服务机构工作强度 指服务机构累计的工作时间占全部时间的比例 是衡量服务机构利用效率的指标 即 11 1 4排队系统的主要性能指标 2 指标间的关系设 表示单位时间内顾客的平均到达数 则1 表示相邻两个顾客到达的平均间隔时间 表示单位时间内被服务完毕离去的平均顾客数 则1 表示对每个顾客的平均服务时间 s表示服务系统中并联的服务台数 Pn t 在时刻t系统中恰好有n个顾客的概率 则有下列关系 Little公式 11 1 5排队系统的输入和输出 排队系统的输入和输出是指顾客到达流和服务时间流 它们的分布一般都是非负的随机变量 最常见的是泊松分布 指数分布和埃尔朗分布 然而在研究具体问题时 究竟是服从哪种分布呢 通常抽取到达时间间隔和服务时间样本 统计其分布 经验分布 并按照统计学的方法进行检验 如检验 以确定服从哪种理论分布 为此 我们先介绍常用的泊松分布 指数分布和埃尔朗分布 之后介绍经验分布检验的Excel操作 1 泊松分布 最简单流 2 指数分布3 埃尔朗分布4 经验分布 1 最简单流 泊松分布 所谓最简单流 是指在t这段时间内有k个顾客来到服务系统的概率服从泊松 Poisson 分布 故也称为泊松流 即 1 最简单流 泊松分布 最简单流需要满足以下三个条件 1 平稳性指在一定时间间隔内 来到服务系统有k个顾客的概率仅与这段时间间隔的长短有关 而与这段时间的起始时刻无关 2 无后效性指在不相交的时间区间内到达的顾客数是相互独立的 或者说在区间 a a t 来到k个顾客的概率与时间a之前来到多少个顾客无关 3 普通性指在足够小的时间区间内只能有一个顾客到达 不可能有两个以上顾客同时到达 1 最简单流 泊松分布 最简单流的一些性质 1 参数 代表单位时间内到达顾客的平均数证由于考虑单位时间 取t 1 其数学期望为 2 在 t t t 没有顾客到达的概率为1 t o t 证在时间 t没有顾客到达的概率为 将右端展开为麦克劳林级数有 当 t 0时 从第3项开始为 t的高阶无穷小 故结论得证 3 在 t t t 内恰好有1个顾客到达的概率为 t o t 证在 t t t 内恰好有1个顾客到达的概率为 将的麦克劳林级数代入 结论得证 2 指数分布的服务时间 指数分布的性质 3 阶埃尔朗 Erlang 分布 4 经验分布 例 大连港1979年500吨以上非定期进港航班 数据见下页 1 统计频数分布 2 检验符合泊松分布吗 1979年大连港非定期500万吨以上货船进港航班 第1步 求相关参数 AVERAGE B2 M32 求平均值 STDEV B2 M32 求标准差 MAX B2 M32 求最大值第2步 统计频数由最大值列出区间点由 frequency B2 M32 N6 N16 统计频数 Ctrl Shift Enter 由 365 poisson O6 N 3 0 求泊松律第3频 假设检验由 Q6 Q16 O17 P17 Q17求理论频数由 chitest O6 P16 R6 S16 求卡方检验的P值推断 当P值 0 05不拒绝泊松分布的原假设 数据文档 双击打开讲解演示 11 2生死过程 n n 1 n 1 t期间 t后 1 生0死0n 2 生1死0n 1 3 生0死1n 1 4 生1死1n 生死过程的平衡方程 11 3 1标准的M M 1 系统 1 M M 1 模型需要满足的条件标准的M M 1 模型是指满足下列条件的排队系统 1 输入过程 顾客源无限 单个到来 相互独立 到达平均数为常数 且服从泊松分布 到达过程是平稳的 2 排队规则 单队 队长不受限制 先到先服务 3 服务机构 单服务台 平均服务率为常数 对各顾客服务时间相互独立 服从相同的指数分布 服务过程也是平稳的 2 M M 1 系统运行指标由于到达平均数和服务平均数均为常数 即 案例11 1 请阅读教材案例11 1 到达率3台 天 服务率4台 天 150台设备 顾客源150可视为无限 问题 等待时间过长 要求 顾客的平均等待时间不应超过2h 现问 应如何对问题进行分析 分析每个地区只有一个技术服务代表 为单服务台 该地区用户150户 可近似于无穷大 采用M M 1 排队系统模型 可见 当每天维修电话从3个减少到2个时 顾客平均等待时间为8h的0 25倍 即2h 满足管理层的要求 排队等待的顾客数也从平均2 25减少到0 5 决策维修量与顾客总体成正比例 目前每个服务代表负责150个顾客总体 减少到100个 可增加技术服务代表 每个负责有100个用户的区域 11 3 2系统容量有限的M M 1 N 系统 M M 1 N 模型 由于系统容量有限 当n N 顾客不再进入系统 其他条件同M M 1 模型 其速率图如下 由于有状态转移差分方程 所以M M 1 模型是M M 1 N 的特例 M M 1 N 主要指标的计算 Little公式是否还适用 答案是肯定的 但由于队长受限 真正进入服务系统的顾客要小于到达率 我们称为有效到达率 eff 由前所述 例11 1 某单人美发店有3把椅子以备顾客休息等待 后来的顾客发现3把椅子都坐满时就不进店等待而离开 顾客平均到达3人 h 理发时间平均15min 人 要求 1 某顾客一到达就能理发的概率 2 有效到达率 3 排队等待顾客的平均数 4 顾客在理发店平均等待时间 5 顾客一到就离开的概率 11 3 3顾客源有限的M M 1 m系统 M M 1 m系统除顾客源有限制外 其余条件与M M 1 系统相同 设顾客源数 设备数 m 系统中顾客数 等待维修和正在维修的设备数 n 故障率 平均服务率 主要指标计算过程 例11 2 一名工人负责看管10台自动机床 在加料或刀具更换时就自动停车 等待工人照管 设平均每台机床两次停车间隔时间2h 需要工人照管的平均时间为12min 设以上两项时间均服从指数分布 计算该系统的各项指标 解单台平均停车间隔时间2h 则每台单位时间停车率为0 5 0 5 对每台停车的机床平均照管时间12min 单位时间照管的台数为5 5 0 5 5 0 1 11 4 1标准的M M s 系统 1 模型需满足的前提条件标准的多服务设施排队系统规定的条件 1 顾客到达率为常数 n 服从泊松分布 2 每台服务率为常数 服从指数分布 3 单队排队 队长不受限制 排队规则FCFS 4 各服务台相互独立 不搞协作 11 4 1标准的M M s 系统 2 模型指标的计算设服务台数为s 则有 例11 3 有2个油泵的加油站 平均加注一辆汽车需要1 2min 平均每h有80台汽车前来加油 到达时间服从泊松分布 服务时间间隔服从指数分布 要求确定 1 预期在加油站的汽车数 2 预期汽车在加油站停留多长时间 3 某个油泵空闲的概率 解每个油泵服务率50辆 h 到达率80辆 h 11 4 1标准的M M s 系统 3 1个M M s 系统与多个M M 1 系统运行指标的比较 11 4 2系统容量有限的M M s N 系统 对于容量有限的M M s N 系统 由于多于N个时不允许进入服务系统 故有 11 4 3顾客源有限的M M s m系统 如m台设备 s个工人看管 故障率相同 维修水平一样 可以