《排队论模型》PPT课件.ppt

排队论模型 朱建青 苏州科技学院信息与计算科学系 排队论模型 一 排队论的基本概念 二 单通道等待制排队问题 M M 1排队系统 三 多通道等待制排队问题 M M c排队系统 一 排队论的基本概念 一 排队过程1 排队系统 排队 是指在服务机构处要求服务对象的一个等待队列 而 排队论 则是研究各种排队现象的理论 在排队论中 我们把要求服务的对象称为 顾客 而将从事服务的机构或人称为 服务台 在顾客到达服务台时 可能立即得到服务 也可能要等待到可以利用服务台的时候为止 排队系统队列除了有形的还有无形的 排队系统中的 顾客 与 服务台 这两个名词可以从不同的角度去理解 在上述顾客 服务台组成的排队系统中 顾客到来的时刻与服务台进行服务的时间一般来说是随不同的时机与条件而变化的 往往预先无法确定 因此 系统的状态是随机的 故而排队论也称随机服务系统 各式各样的排队现象呈现的基本特征 排队系统由输入过程 排队规则及服务机构三部分组成 1 输入过程输入过程就是顾客按怎样的规律到达 它首先应包括顾客总体数 是有限的还是无限的 其次应说明顾客到达的方式 是成批到达 每批数量是随机的还是确定性的 还是单个到达 最后应说明相继到达的顾客 或批或单个 之间的时间间隔的分布是什么 2 排队系统的组成和特征 排队规则是指到达的顾客以怎样的规则接受服务 1 损失制 顾客到达 服务台不空立即离去 另求服务 2 等待制 顾客到达 排队等待 对等待制服务可分为 先到先服务 后到先服务 优先服务 随机服务 成批服务等 3 混合制 在现实生活中 很多服务系统介于损失制和等待制之间 当顾客到达时 服务台不空就排队 若排队的位置已满就离去 2 排队规则 服务机构主要指服务台的数目 多个服务台进行服务时 服务方式是并联还是串联 服务时间服从什么分布等 3 服务机构 1 排队模型的分类D G Kendall引进了排队模型分类符号 现已广泛采用 这里仅针对并列的服务台 记X 顾客到达的时间间隔分布 Y 服务时间的分布 Z 服务台数 则排队模型 X Y Z 常用的记号 M 负指数分布 D 确定型 Ek k阶爱尔朗 Erlang 分布 GI 一般相互独立的随机分布 G 一般随机分布 这里主要讨论M M 1 M M C 二 排队模型的分类及数量指标 1 队长队长是指系统中的顾客数 包括排队等候和正在接受服务的顾客数 等待队长是指系统中等待服务的顾客数 无论是队长还是等待队长 都是顾客和服务机构最关心的数量指标 特别是对系统设计者来说 尤为重要 因为它涉及到系统等待空间的大小 2 排队模型的数量指标 逗留时间是指一顾客从进入系统起一直到接受服务后离开系统为止所花费的时间 等待时间是指一顾客从进入系统起到接受服务时所花费的时间 显然 一个顾客的逗留时间等于其等待时间与接受服务的时间之和 逗留时间与等待时间对顾客来说是最关心的 因为每个顾客都希望自己用于排队等待的时间愈短愈好 2 逗留时间 忙期是指从顾客到达空闲服务机构起到服务机构再次为空闲为止的这段时间 即服务机构连续繁忙的时间长度 这是服务机构最关心的数量指标 因为它直接关系到服务员的工作强度 与忙期相对应的是闲期 即为服务机构连续保持空闲的时间长度 显然 在排队系统中 忙期与闲期是交错出现的 3 忙期 1 最简单流与Poisson过程记随机过程 x t t 0 为时间 0 t 内流 事件 发生的次数 例如对于随机到来某电话交换台的呼叫 以x t 表示该交换台在 0 t 这段时间内收到呼叫的次数 若是服务机构 可以用x t 表示该机构在 0 t 时间内来到的顾客数 三 Poisson流与指数分布 定理1设是最简单流 则对任何和都有我们把满足这一分布规律的随机过程称为Poisson过程 最简单流亦称Poisson流 特别取得故参数 表示单位时间内事件发生次数的平均数 2 Poisson流的发生时间间隔分布 当流 过程 构成Poisson过程时 就称为Poisson流 设流发生的时刻依次为 发生的时间间隔记为 其中 定理2事件流为Poisson流的充要条件是的流发生时间间隔相互独立 且服从相同的负指数分布 即 3 负指数分布的Markov特性 定理3设T为连续型随机变量 且T 0 那么 T服从负指数分布的充要条件是 对任何 都有上式可改写为 对任何 都有如果把T解释为寿命 上式表明 如果已知年龄大于岁 则再活x年的概率与以前的 年 无关 所以有时又风趣地称指数分布是 永远年轻 上面两式表明连续型随机变量T的Markov特性当且仅当非负随机变量服从负指数分布时才具有 例1设某一服务系统的输入流是Poisson流 平均每3分钟进入5名顾客 试计算 1 12分钟内进入15名顾客的概率 2 输入时间间隔大于1分钟的概率 解 1 由于 在 0 t 内进入k名顾客的概率于是12分钟内进入15名顾客的概率 2 由于输入时间间隔 服从参数为 的指数分布则所求概率为 对于单通道等待制排队问题主要讨论输入过程为Poisson流 服务时间服从负指数分布 单服务台的情形 即M M 1排队系统 一 标准模型即为M M 1 排队系统 所谓标准模型 就是顾客的输入流是参数为 的Poisson流 每个顾客的服务时间是相互独立的且服从参数为 的负指数分布 单个服务台且系统的容量无限 排队模型分类第四个表示系统中允许的最大顾客数 二 单通道等待制排队问题 M M 1排队系统 1 系统的Markov特性 考虑随机过程 其中为时刻时排队系统中的顾客数 对于任何条件概率由于输入为Poisson流 服务时间服从负指数分布 则无论在处取何值 上式条件概率仅依赖于的值和区间的长度 即 直观地说 如果知道现在时刻时系统的顾客数状况 那么从概率意义上来说 将来时刻时系统的顾客数状况 与过去时刻时顾客数的状况无关 这个特性就是随机过程的Markov特性 我们把系统在某一时刻的顾客数看做系统在这个时刻的状态 根据系统状态的Markov特性 容易研究在时间区间内系统状态的转移概率 为研究系统在任一时刻的状态分布提供工具 对于系统的稳定状态情形 与t无关 故 记 从而有对于上述差分方程 利用归纳法不难求得 记为排队系统的来往强度 当时 由可得 由于构成概率分布 则 从而级数必须收敛 故有 M M 1 系统的数量指标 例2 病人候诊问题 某单位医院的一个科室有一位医生值班 经长期观察 每小时平均有4个病人 医生每小时平均可诊断5人 病人的到来服从Poisson流 诊病时间服从负指数分布 试分析该科室的工作状况 如要求99 以上的病人有座 该科室至少设多少座位 如果该单位每天24小时上班 病人因看病1小时而耽误工作单位要损失30元 这样单位平均损失多少元 如果该科室提高看病速度 每小时平均可诊6人 单位每天可减少损失多少 可减少多少座位 为了满足99 以上的病人有座 设科室应设m个座位 即 P 医务室病人数 m 0 99故该设20个座位 该单位24小时上班 平均每天有4 24 96人看病 看病所占的总时间为1 96 96小时 所以因看病平均每天损失30 96 2880 元 若医生诊病速度提高到每小时6人 即 6 2 3 类似于上面的计算 有以下结果 人 人 小时 小时 这样单位每天损失 30 0 5 96 1440 元 比原来减少1440元 此时只需座位 即11个座位 比原来减少9个座位 二 系统容量有限的模型 即满足微分方程在稳态情况下 则 则由 可得 系统的各项指标 由于有容量的限制 顾客实际进入系统的速率不是 而是 有效到达率 因而Little公式成立 三 多通道等待制排队问题 M M c排队系统 多通道就是多服务台 这里主要讨论M M c 排队系统问题 即输入 输出与M M 1 相同 这里有c个相互独立工作 且服务速率相同的服务台 这时整个系统的服务能力为c 当时 系统有稳定解 系统指标 因而Little公式成立 例3某火车站售票处有三个窗口 顾客的到达服从Poisson分布 平均每分钟0 9人到达 服务时间服从负指数分布 每个窗口每分钟可售票0 4人 现假设排成一队 依次向空闲的窗口购票 试分析该排队系统 若排成三队 与前面的情形比较 解假设排成一队 如图 由题意可知 c 3 0 9 0 4 则 即整个售票处空闲的概率为0 0743 图7 2假设排成一队示意图平均等待队长 1 7 人 平均队长