排队论大学课件7-MM排队模型.ppt

18 46 23 1 M M 排队模型综述 18 46 23 2 排队模型回顾 顾客到达排队系统请求服务如果排队系统中顾客数没有满 则进入排队系统如果有空闲的服务窗 则直接到服务机构接受服务如果服务窗全部被占用 则排队等候 排队机构 服务机构 18 46 23 3 M M 排队系统的几种可能状态 7 7 3 假如此系统容量为7 M M 3 7 7 0 7 3 18 46 23 4 排队模型 Kendall记号 18 46 23 5 M M 的排队模型 考虑整个排队系统中顾客数的变化有顾客到达 系统中顾客数加1有顾客服务完毕 系统中顾客数减1总之 顾客的到达和离开致使系统顾客数有变化M M 的排队系统顾客数变化有什么特点 顾客到达间隔与顾客服务时间均服从负指数分布因为顾客到达间隔时间是相互独立的 顾客接受服务也是相互独立的 因此 之前的顾客到达情况 服务情况不影响当前顾客数变化概率因为到达间隔时间和服务时间都具有无记忆性 因此 下一个顾客的到达间隔时间已经过去了多久 当前正在服务的顾客的服务时间已经过去了多久不影响当前顾客数的变化概率 18 46 23 6 M M 的排队模型 M M 的排队系统 系统中顾客数变化是一种生灭过程0状态代表系统有0个顾客1状态代表系统中有1个顾客2状态代表系统中有2个顾客 生灭过程的增长率和消亡率怎么确定 增长率取决于到达率 和当前系统状态消亡率取决于服务率 和当前系统状态 18 46 23 7 增长率和消亡率的分析 假定顾客到达为强度为 的泊松流 服务窗的服务率为 服务时间服从负指数分布 考察在 t 极短 时间内 若顾客到达间隔时间服从参数为 的负指数分布 则在 t 极短 时间内有1个顾客到达的概率为 t o t 没有顾客到达的概率为1 t o t 若服务时间服从参数为 的负指数分布 则在 t 极短 时间内有1个正在忙的服务窗服务完当前顾客的概率是 t o t 1个正在忙的服务窗没有服务完的概率是1 t o t 18 46 23 8 增长率和消亡率的分析 i状态下 i状态代表排队系统中有i个顾客 假定此时有j个顾客正在接受服务 j i 若m为服务窗个数 j i当i m时 j m当i m时 18 46 23 9 增长率和消亡率的分析 18 46 23 10 增长率和消亡率的分析 由此 M M 型排队模型 在状态时的增长率和消亡率为 j i i m系统顾客数少于等于服务窗数时 所有顾客都在接受服务j m i m系统顾客数大于服务窗个数时 所有服务窗都在服务 正在接受服务的顾客数 服务窗个数 18 46 23 11 第三章单服务窗排队模型 第一节损失制M M 1 1第二节等待制M M 1第三节混合制M M 1 m第四节可变服务率的M M 1第五节可变输入率的M M 1第六节具有不耐烦顾客的M M 1第七节单服务窗闭合式M M 1 m m第八节有差错服务的M M 1 18 46 23 12 第一节单服务窗损失制排队模型M M 1 1 18 46 23 13 排队模型分析 M M 1 1顾客到达间隔时间为负指数分布 参数为 服务窗服务时间为负指数分布 参数为 系统最大顾客数1决定了系统状态为 0 1 状态0 系统中顾客数为0 服务窗空闲状态1 系统中有1个顾客 此顾客正在接受服务 系统顾客满 服务窗忙 18 46 23 14 求解平稳分布 根据马氏链 生灭过程求平稳分布的公式 列出平衡方程 本书从现在开始用 p0 p1 p2 表示平稳分布 18 46 23 15 M M 1 1的各个目标参量 单位时间内损失的顾客数单位时间内平均进入系统的顾客数相对通过能力Q 即单位时间内被服务完的顾客数与请求服务顾客数之比值 绝对通过能力A 单位时间内被服务完顾客的均值 书44页 18 46 23 16 M M 1 1例题 设某条电话线 平均每分钟有0 6次呼唤 若每次通话时间平均为1 25分钟 求相应的Q A与P损 电话业务我们通常采用M M 排队模型 18 46 23 17 M M 1 1例题 设某条电话线 平均每分钟有0 6次呼唤 若每次通话时间平均为1 25分钟 求相应的Q A与P损解 按题意知 18 46 23 18 补充 系统负载 业务强度 trafficintensity 业务负载 trafficload a 单位时间内的业务到达量 offeredload 单位时间内到达系统的平均呼叫数 平均通话时间长度 b 单位时间内的业务承载量 carriedload 单位时间内得到服务的平均呼叫数 平均通话时间长度 如果通话时间长度的单位为 小时 的话 则话务量单位为 小时 呼 也叫 爱尔兰 erl 话务量总是针对一段时间而言 如 一天或一小时 18 46 23 19 补充 系统负载举例 例如 某电话用户10 12点之间共拨打电话5次 总通话时间为30分钟 求此用户线平均每小时的业务量解 5 2 60 5 30承载的业务量为a 30 2 60 0 25erl一个服务窗每小时最多提供1erl的业务承载量传统电话网 普通用户0 1 0 2erl集团交换机0 1 0 6erl 18 46 23 20 补充 关于业务负载的几个典型参数 分组交换网 考虑两个路由器之间的一条传输线路 假定每秒钟平均传输10个数据包 数据包平均长度400字节 线路传输速度为64kbps 10 64 000 400 8则业务强度为 10 400 8 64 000 0 5 50 如果线路速度为150Mbps 则 10 400 8 150 000 000 0 0002 0 02 18 46 23 21 服务强度 资源利用率 utilizationratio 服务强度 承载业务量 线路数 服务窗个数 就是服务窗忙的概率 通信中就是输出线路有数据传输的概率或者通话线路被占用的概率 18 46 23 22 Little公式 考虑一个能够达到平稳的排队系统 为到达率 W为每个顾客在系统中耗费的平均时间 L为系统中的平均顾客数 则有L W证明 假设在一段比较长的时间区间 0 t 内 系统一直处于统计平衡状态 L W都存在 表示单位时间进入到系统中的顾客数全部顾客一共耗费在系统中的时间 到达的顾客数 平均等待时间 t W 系统中的平均顾客数 t L t 18 46 23 23 Little公式的直观理解 在统计平衡状态下 某一顾客离开排队系统时 回头看到的队列长度的平均值 L 应该等于此顾客在排队等待过程中平均进入排队系统的顾客数 W 18 46 23 24 Little公式的普遍性 Little公式成立的条件只有一个 那就是排队系统要达到统计平衡状态 在此条件下 它适用于任何排队系统 它关心的只是排队系统的三个统计平均量 对顾客到达的间隔时间和服务时间的分布以及排队规则不作任何要求但值得注意的是 Little公式中的三个统计平均量必须是针对同一顾客群而言 Ls sWsLq qWqL服 服W服 18 46 23 25 用M M 1 1排队系统的结论验证Little公式 18 46 23 26 Little公式的物理意义 L是一个时间 timeaverage 平均的概念 是不同时刻队列长度在很长一段时间内的平均W是顾客平均的概念 是许许多多个不同顾客等待时间的平均一般来讲W比较容易从统计中获得 L比较容易从理论分析中获得 18 46 23 27 Little公式应用 一个没有等待位置的餐厅 平均每小时服务完30人 平均就餐时间为30分钟 请问平均就餐人数 30W 0 5L W 0 5 30 15 人