《排队系统分析》PPT课件.ppt

排队系统分析 QueueingSystemsAnalysis 第一节排队的基本概念第二节到达与服务的规律第三节M M 1排队模型第四节M M C排队模型第五节M G 1排队模型第六节排队系统优化 排队论所要研究解决的问题 面对拥挤现象 人们通常的做法是增加服务设施 但是增加的数量越多 人力 物力的支出就越大 甚至会出现空闲浪费 如果服务设施太少 顾客排队等待的时间就会很长 这样对顾客会带来不良影响 如何做到既保证一定的服务质量指标 又使服务设施费用经济合理 恰当地解决顾客排队时间与服务设施费用大小这对矛盾 就是随机服务系统理论 排队论所要研究解决的问题 第一节排队的基本概念 排队也称为随机服务系统理论性态问题 排队系统的概率规律性 队长分布 等待时间分布 忙期分布最优化问题 静态优化和动态优化 前者指最优设计 后者指排队系统的最优运营排队系统的统计推断 判断给定的排队系统属于哪种类型 以便使用相应理论进行分析研究 第一节排队的基本概念 一 排队系统的组成 第一节排队的基本概念 排队系统的三个基本组成部分 输入过程 顾客按照怎样的规律到达 排队结构与排队规则 顾客按照一定规则排队等待服务 服务机构与服务规则 服务机构的设置 服务台的数量 服务的方式 服务时间分布等 1 输入过程 顾客源 总体 有限 无限 顾客到达方式 逐个 逐批 仅研究逐个情形 顾客到达间隔 随机型 确定型 顾客前后到达是否独立 相互独立 相互关联 输入过程是否平稳 平稳 非平稳 仅研究平稳性 2 排队结构与排队规则 顾客排队方式 等待制 即时制 损失制 排队系统容量 有限制 无限制 排队队列数目 单列 多列 是否中途退出 允许 禁止 是否列间转移 允许 禁止 仅研究禁止退出和转移的情形 3 服务机构与服务规则 服务台 员 数目 单个 多个 服务台 员 排列形式 并列 串列 混合 服务台 员 服务方式 逐个 逐批 研究逐个情形 服务时间分布 随机型 确定型 服务时间分布是否平稳 平稳 非平稳 研究平稳情形 排队模型与系统参数 一 排队模型 一 排队模型表示方法 1 D G Kendall 1953 表示法X Y Z 依据排队系统3个主要特征 1 X顾客到达间隔时间分布 2 Y服务台 员 服务时间分布 3 Z服务台 员 个数 单个或多个并列 2 国际排队论标准化会议 1971 表示法X Y Z A B C 1 A系统容量限制 2 B顾客源 总体 数目 3 C服务规则 FCFS LCFS等 略去后三项 即指 X Y Z FCFS 这里仅研究FCFS的情形 二 到达间隔和服务时间典型分布 1 泊松分布M 2 负指数分布M 3 k阶爱尔朗分布Ek 4 确定型分布D 5 一般服务时间分布G M M 1 M D 1 M Ek 1 M M c M M c m M M c N 三 排队模型示例 二 系统参数 一 系统运行状态参数 1 系统状态N t 指排队系统在时刻t时的全部顾客数N t 包括 排队顾客数 和 正被服务顾客数 系统状态的可能值如下 1 系统容量无限制 N t 0 1 2 2 系统容量为N时 N t 0 1 2 N 3 服务台个数为c 损失制 N t 0 1 2 c 一般 系统状态N t 是随机的 2 系统状态概率 1 瞬态概率Pn t 表示时刻系统状态N t n的概率 2 稳态概率Pn Pn Pn t 一般 排队系统运行了一定长的时间后 系统状态的概率分布不再随时间t变化 即初始时刻 t 0 系统状态的概率分布 Pn 0 n 0 的影响将消失 二 系统运行指标参数 评价排队系统的优劣 1 队长与排队长 1 队长 系统中的顾客数 n 期望值Ls n Pn 2 排队长 系统中排队等待服务的顾客数 期望值Lq Lq Ls E 正被服务的顾客数 2 逗留时间与等待时间 1 逗留时间 指一个顾客在系统中的全部停留时间 期望值 记为Ws 2 等待时间 指一个顾客在系统中的排队等待时间 期望值 记为Wq Ws Wq E 服务时间 3 其他相关指标 1 忙期 指从顾客到达空闲服务机构起到服务机构再次空闲的时间长度 2 忙期服务量 指一个忙期内系统平均完成服务的顾客数 3 损失率 指顾客到达排队系统 未接受服务而离去的概率 4 服务强度 c 6 3排队系统时间参数分布规律 一 顾客到达时间间隔分布 一 泊松流与泊松分布 如果顾客到达满足如下条件 则称为泊松流 1 在不相互重叠的时间区间内 到达顾客数相互独立 无后效性 2 对于充分小的时间间隔内 到达1个顾客的概率与t无关 仅与时间间隔成正比 平稳性 3 对于充分小的时间间隔 2个及以上顾客到达的概率可忽略不计 普通性 称具有上述特征的输入为泊松流 其在t时段内到达n个顾客的概率为 即参数为的泊松分布 由概率论知识可知 泊松分布的参数即其均值 因此 的含义是单位时间到达系统的平均顾客数 即到达率 下面考察 当顾客按泊松流到达时 其到达的间隔时间T是服从什么分布呢 因为到达为泊松流 所以 t时段内没有来顾客的概率为 所以 t时段内有顾客到来 即间隔Tt 的概率为 而这正是负指数分布的分布函数 说明T服从负指数分布 且参数同为 可证反之也成立 于是得到关于到达规律的重要性质 到达数为泊松流到达间隔服从负指数分布 同参数 由概率论知识可知 负指数分布的表达式 密度函数 为参数即其均值的倒数 因此 的含义是平均间隔时间 这与为单位时间到达系统的平均顾客数的含义一致 负指数分布有一个有趣的性质 无记忆性 即 事实上 直观上看 在已知T t0的条件下估计T t的概率 与无条件时估计T t的概率相同 把以前的t0时间给忘了 假若T表示某种电子元件的寿命 则当元件已使用了t0时间后估计它还能再使用t时间的概率 与刚开始用时的概率一样 说明这种元件是高度耐磨损的 二 顾客服务时间分布 一 负指数分布 主要讨论服务时间v服从负指数分布的情形 参数为 即 参数的含义 服务率 即单位时间平均服务完人 由于v的均值为 即平均对每位顾客的服务时间为 可得 注 负指数分布的一般化 爱尔朗分布 可用于描述由k道程序组成的1个服务台的服务时间的分布 二 爱尔朗 Erlang 分布 1 设v1 v2 vk是k个相互独立的随机变量 服从相同参数1 k 的负指数分布 则 T v1 v2 vk的概率密度为称T服从k阶爱尔朗分布 2 E T 1 Var T 1 k 2 3 T的意义之一 k个串联服务台的总服务时间 二 排队系统的状态转移方程 一 排队系统状态的概率及其分布 1 瞬态概率Pn t 表示时刻系统状态N t n的概率 2 稳态概率Pn Pn Pn t 一般 稳态概率Pn的分布 是分析计算排队系统运行优劣的基础 二 排队系统状态概率的微分差分方程 二 排队系统状态概率的微分差分方程 二 排队系统状态概率的微分差分方程 二 排队系统状态概率的微分差分方程 二 排队系统状态概率的微分差分方程 求解可得瞬态概率Pn t 三 排队系统状态转移方程 求解可得稳态概率Pn 令 则 排队系统状态转移方程 四 排队系统状态转移图 第三节M M 1排队模型 一 标准的M M 1模型 M M 1 1 问题的一般提法设 泊松输入 负指服务 单服务台 系统无限制 顾客源无限制求 1 系统状态概率Pn 2 系统运行指标Ls Lq Ws Wq 2 系统状态概率 1 利用状态转移图列出平衡方程状态转移图是处理稳态M M C系统的一种工具 设到达与服务率分别为 则 由此列出平衡方程 由平衡方程 2 由平衡方程解得状态概率 由平衡方程 可解得状态概率 记 称为服务强度 规定 为什么 则 2 由平衡方程解得状态概率 3 系统运行指标 1 Ls与Lq 因为是均值 2 Ws与Wq 3 上述4个指标之间的关系 里特公式 例2某修理店只有一个修理工人 来修理的顾客到达数服从泊松分布 平均每小时4人 修理时间服从负指数分布 平均需6分钟 求 1 修理店空闲的概率 2 店内有3个顾客的概率 3 店内至少有1个顾客的概率 4 店内顾客的平均数 5 顾客在店内的平均逗留时间 6 等待服务的顾客平均数 7 平均等待修理时间 二 系统容量有限的M M 1模型 M M 1 1 与 M M 1 的区别 2 状态概率 由此列出平衡方程 3 系统运行指标 例3某修理站只有1个修理工 且站内最多只能停放3台待修理的机器 设待修理的机器按泊松流到达 平均每小时到达1台 修理时间服从负指数分布 平均每1 25小时可修理1台 试求 1 站内空闲率 2 顾客损失率 3 有效到达率 4 站内平均队长 5 机器为修理而需等待的平均时间 例4 为开办一个小型汽车冲洗站 必须决定提供等待汽车使用的场地大小 设要冲洗的汽车到达服从泊松分布 平均每4分钟1辆 冲洗的时间服从负指数分布 平均每3分钟洗1辆 试计算当所提供的场地仅能容纳 a 1辆 b 3辆 c 5辆 包括正在被冲洗的1辆 时 由于等待场地不足而转向其它冲洗站的汽车的比例 三 顾客源有限的M M 1模型 M M 1 1 与 M M 1 的区别 说明 进入率与状态有关 如m 5 n 3 如下图所示 进入的或甲或乙或丙 故 由此列出平衡方程 2 状态概率 3 系统运行指标 问题 的直观意义为何 平均故障台数 例5 某车间有5台机器 每台机器的连续运转时间服从负指数分布 平均连续运转时间为15分钟 有1个修理工 每次修理时间服从负指数分布 平均每次需12分钟 求 1 修理工空闲的概率 2 5台机器都出故障的概率 3 出故障机器的平均台数 一 前提 单队 并列C台 第四节M M C排队模型 我们仅讨论标准的M M C 二 M M C 系统 服务率与服务强度 1 与 M M 1 的区别 2 状态概率 由此列出平衡方程 先解得 3 运行指标 注 C 服务台数C C 1 C 2 C 3 C 4 0 3 0 2 0 1 3 M M C指标有表可查 4 单队C台与C个单队单台系统比较 显然 单队C台效率高 第五节M G 1排队模型 以上讨论了M M 1和M M C系统 其前提均为泊松输入和负指数服务处理 这类系统的工具是生灭工程状态转移图 在实际中 有时到达仍为泊松过程 但服务时间并不服从负指数分布 即M G 1系统这时不能用生灭过程处理 而主要依据布拉切克 钦辛公式 P K公式 一 M G 1 系统 二 M D 1 G 系统 定长服务时间 可见 内部越有规律越省时间 三 M 1 G 系统 k阶爱尔郎服务时间 注 对于到达与服务均为任意分布的情况 可采用随机模拟的方法求近似解 可见 k 1时即 M M 1 k时即 M D 1 由P K公式 由里特公式 第六节排队系统最优化 我们主要研究静态优化 目标 费用 损失 最小 一 标准的M M 1系统的最优服务率