排队论模型ppt课件

排队论模型 排队论是20世纪初由丹麦数学家Erlang应用数学方法在研究电话话务理论过程中而发展起来的一门学科 排队论也称随机服务系统理论 它涉及的是建立一些数学模型 以对随机发生的需求提供服务的系统预测其行为 它已应用于电讯 纺织 矿山 交通 机器维修 可靠性 计算机设计和军事领域 都已取得了显著的成绩 一 排队论简介 二 实例分析 一 排队论简介 一 基本概念1 排队系统排队是指在服务机构处要求服务对象的一个等待队列排队系统是指一个具有排队等待现象的服务系统排队论是指定量的研究排队问题 寻找系统内在规律 寻找供求关系平衡的最优方案 现实世界中排队的现象比比皆是 但有如下共同特征 1 有请求服务的人或物 如候诊的病人 请求着陆的飞机等 我们将此称为 顾客 2 有为顾客提供服务的人或物 如医生 飞机跑道等 我们称为 服务员 由顾客和服务员就组成服务系统 3 顾客随机地一个一个 或者一批一批 来到服务系统每位顾客需要服务的时间不一定确定的 服务过程的这种随机性造成某个阶段顾客排长队 而某些时间服务员又空闲无事 2排队系统的特征为了描述一个给定的排队系统 必须规定系统的下列组成 1 输入过程顾客陆续来到的过程 设N t 0 t 时间内来到的顾客数 非负整数值 是随机过程 又设 第i个顾客到达的时间 从 随机变量序列 时间间距 隔 一般假设顾客来到时间间隔 相互独立与随机变量 有相同的 可以根据原始资料 由顾客到达的规律 作出经验分布 检验法 确定服从哪种理论分布 并 概率分布为负指数分布 另外有定长分布D k阶爱尔兰分布 一般独立分布GI等 而 分布 然后按照统计学的方法 如 估计它的参数值 我们主要讨论 2 服务机构服务员对顾客服务过程 服务机构可以是一个服务员或多个服务员的 对顾客可以单独进行服务 也可以对成批顾客进行服务 在我们这儿介绍对顾客单独进行服务 设C为服务机构服务员个数 当C 1时 为单服务系统 当C 2 为多服务系统 和 输入过程一样 服务时间都是随机的 且我们假设 设 表示服务员为n个顾客提供服务所需的时间 则服务 服从相互独立的且与某一随机 有相同分布 其中 根据原始资料判断得到的 主要有的分布为负指数分布 定长分布 一般独立分布等 3 排队与服务规则顾客排队和等待的规则 排队规则一般有等待制 消失制和混合制 所谓等待制 系统容量 就是当一个顾客到达时 若所有服务台均被占用时 该顾客便排队等待服务 消失制也称即时制 系统容量D C 就是服务台被占用时顾客便即时离去 混合制也 时间所构成的序列 变量 的概率分布是已知的可以 有限制 系统容量D C D k 就是一顾客到达若系统中顾客 称队长 包括排队等待和正在接受服务的 数目小于k则他排队等待 否则他即时离去 等待制服务的次序规则有先到先服务随机服务 有优先权的先服务等 我们主要讨论先到先服务的系统 3 排队系统的主要指标研究排队问题的目的 是研究排队系统的运行效率估计服务质量 确定系统参数最优值 以决定系统的结构是否合理 设计改进措施等 所以必须确定用来判断系统运行优劣的基本数量指标 这些数量指标通常是 1 队长 是指系统中顾客 包括排队等待和正在接受服务的 的数目 它的期望值为 排队等待的顾客数 其期望记为 队长 等待服务的顾客数 正被服务的顾客数 所以 越大 排队长度则仅指在队列中 系统中的顾客数 说明服务效率越低 2 等待时间 是指从顾客到达时间算起到他开始接受 顾客到达时刻算起到他接受服务完毕为止所需要的时间 逗留时间 等待时间 服务时间 3 忙期 是指服务台连续繁忙的时间 即顾客从到达空闲服务台算起到服务台再次变为空闲时止的这段时间 这是服务台最关心数量指标 它直接关系到服务员工作强度 与忙期相对应的是闲期 这是指服务台连续保持空闲的时间长度 显然 在排队系统中忙期与闲期 是交替出现的 服务时止的这段时间 其期望值记 逗留时间则指从 即是顾客在系统中所花费的总时间 其期望值记 排队系统除了上述三个主要数量指标外 另外服务台的利用率 即服务员忙碌的时间在总时间中所占比例 在排队论的研究中也是很重要的指标 二 排队模型的符号表示与几种重要排队模型1 排队模型的符号一般表示法一般表示法A B C D E FA 顾客来到时间间隔的分布类型B 服务时间的分布类型C 服务员个数D 系统容量E 顾客源个数F 服务规则先来先服务的等待排队模型主要由三参数法即A B C例 M M 1 k 时间均服从负指数分布 一个服务台 系统至多容纳k个顾客潜在的顾客数不限 先来先服务的排队系统 F1F0 表示顾客到达间隔时间和服务 M M c 即Poisson输入负指数服务时间分布C个服务台的等待制排队模型 M G 1 即Poisson输入 一般服务时间分布 单个服务台的等待制排队模型 00 00 服务机构 2 几种重要的排队模型 1 单服务台系统 2 多服务台的平衡系统 3 串联排队系统 4 排队网络模型 5 匹配排队模型 另外还有 6 优先权的排队系统 7 成批排队模型 8 有限源排队模型我们讨论 1 2 两种 三 建立排队模型步骤1 确定表达排队问题各个变量并建立它们之间的相互关系 2 根据现有的数据 运用适当的统计检验 假设检验有关分布 3 应用已得到的概率分布 确定描述整个系统的运行特征 4 根据系统的特征 通过应用适当的决策模型 改进系统的功能 四 生灭过程的差分微分方程组当顾客到达时间间隔为负指数分布 即输入过程具有Poisson特征 N t 服从Poisson分布 服务时间为负指数分布 则系统的排队过程是Markov 马尔科夫 过程 而且它具有一类特殊Markov过程的特征 通常称这类随机过程的生灭过程 1 生灭过程的定义设有一个系统 具有有限个状态 其状态集s 0 1 2 k 或有可数个状态 状态集s 0 1 2 令X t 为系统在时刻t所处的状态 若在某一时刻t系统的状态数为n 如果对 t 0有 1 到达 生 在 t t t 内系统出现一个新的到达的概率为 的常数 没有发生新的到达的概率 出现多于一个以上的新的到达概率 的常数 没有消失的概率为 消失多于一个以上的概率为0 t 则称系统状态随时间而变化的过程X t 为一个生灭过程 为 为0 t 2 消失 灭 在 t t t 内 系统消失一个的概率的 2 生灭过程微分差分方程组设 表示系统在时刻t的状态X t n的概率即 状态为n的概率近似于以下四个概率之和 1 P 系统在时刻t时为n 而在 t内没有到达也没有消失 2 P 系统在t时为n 1而在 t内有一个到达并且没有一个消失 3 P 系统在t时为n 1 而在 t内没有到达而有一个消失 则系统在时刻t t的 4 P 系统在 t内发生多于一个的到达或消失 0 t 即应用全概率公式有 当时类似地 当S为有限集时 对有令 t 0得当系统状态S为有限集时 生灭过程的微分差分方程组为 当系统状态S为可数集时 生灭过程微分差分方程组为 9 2 若能求解这组方程 则可得到在时刻t系统状态概率分布称为生灭过程的瞬时解 一般这种瞬时解是难以求得的 3 统计平衡下的极限解实际应用中 关心的是时 方程的解称为生灭过程微分差分方程组的极限解 令及 9 1 9 2 式得当S为有限状态集时 9 1 式变为 9 3 当S为可数状态集时 9 2 式变为 9 4从而可以求得概率分布列 五 典型排队模型和理论结果下面给出满足生灭过程典型排队M M 1与M M C的结果 一 单服务台等待制M M 1排队模型1 M M 1 顾客来到的时间间隔服从参数的负指数分布 服务员为顾客服务时间服从参数的指数分布 且与相互独立 1个服务台 系统容量为的等待制排队模型 可理解为 单位时间平均到达的顾客数 平均到达率可理解为 单位时间平均服务完的顾客数 平均服务率 1 顾客输入过程 是平均率为 的Poisson过程即 设M t 为 0 t 内容去顾客数 则 的Poisson分布即 2 X t 时刻t系统中的顾客数则 L t 时刻t排队等待顾客数则 研究X t 的分布模型令 当依赖于t时 称是瞬时解如果则称是稳定解 此系统的状态转移图图1 从而在生灭过程中取 9 5 记 称为服务强度当时 模型不稳 时达不到统计 当 1时 模型稳定 有稳定解 3 X t 的分布律由 9 12 1 15 式得此模型的微分差分方程组 9 6 当时 稳态解满足 9 7 求解 9 7 式差分方程 得 9 8 4 结论平均队长 9 9 平均等待队长 9 10 系统中顾客数的方差 9 11 顾客不须等待概率 9 12 可以证明 顾客在系统中逗留时间T服从参数为的指数分布 从而顾客在系统平均逗留时间 9 13 顾客在系统平均等待时间 9 14 从上结论可以看出 各指标之间有如下关系 9 15 9 16 9 15 5 简单例子例1 病人候诊问题 某单位医院的一个科室有一位医生值班 经长期观察 每小平均有4个病人 医生每小时平均可诊5个病人 病人的到来服从泊松分布 医生的诊病时间服从负指数分布 试分析该科室的工作状况 如果满足99 以上的病人有座 此科室至少应设多少座位 如果该单位每天24小时上班 病人看病1小时因耽误工作单位要损失30元 这样单位平均每天损失多少元 如果该科室提高看病速度 每小时平均可诊6个病人 单位每天可减少损失多少 可减少多少座位 解 由题意知 从而排队系统的稳态概率为 该科室平均有病人数为该科室内排队候诊病人数为看一次病平均所需的时间为排队等候看病的平均时间为为满足99 以上的病人有座 设科室应设m个座位 则m应满足 所以该科室至少应设20个座位如果该单位24小时上班 则每天平均有病人24 4 96人 病人看病所花去的总时间为96 1 96小时 因看病平均每天损失30 96 2880元 如果医生每小时可诊6个病人 则 这样单位每天的损失费为96 0 5 30 1440元 因而单位每天平均可减少损失2880 1440 1440元 这时为保证99 以上的病人有座 应设座位数个比原来减少了9个 2 M M 1 k顾客来到的时间间隔服从参数的负指数分布 服务员为顾客服务时间服从参数的指数分布 且相互独立 1个服务台 系统容量为k的等待制排队模型 因为是单服务台 系统容量为k 即排队等待的顾客最多为k 1 在某时刻一顾客到达时 如系统中已有k个顾客 那么这个顾客就被拒绝进入系统 所以为在生灭过程差分微分方程组 9 1 式中取 从而得此排队模型微分差分方程组 9 17 在稳态情形下 式 9 3 变为 9 18 在条件下解 9 18 式得到虽然当注意到 这里 不假设条件 由于系统容量有限的限制下面类似地给出系统的各种指标的计算结果 9 19 9 20 9 21 9 22 应该指出 的导出过程中不采用平均达到率 而是采用有效到达率 这主要是由于当系统已满时 顾客的实际到达率为零 因为正在被服务的顾客的平均数为 于是 9 21 二 多服务台等待制M M C排队模型1 M M C 顾客来到的时间间隔服从参数的负指数分布 服务员为顾客服务时间服从参数的指数分布 C个服务台 系统容量为的等待制排队模型 1 稳态的概率分布M M C 模型系统状态图为 012 c 1cc 1 2 图2 因此在生灭过程微分差分方程组 9 2 式中 令得到此模型微分差分方程组 9 23 显然当 有稳态解 类似地 9 4 式演变 9 24 解 9 24 式差分方程得 9 25 其中 9 26 2 主要结果 9 27 9 28 9 29 9 30 2 M M c k顾客来到的时间间隔服从参数的负指数分布服务员为顾客服务时间服从参数的指数分布 C个服务台 系统容量为k的等待制排队模型 因为是多服务台 系统容量为 即系统状态为时 当时 个服务台空闲 当时 服务台正忙着 有个正等候着 在某一时刻一顾客到达时 系统中已有个顾客 那么这个顾客就被拒绝进入系统 根据此模型的特点 在生灭过程微分差分方程组 9 1 式中取 得此模型微分差分方程组 9 31 稳态情况差分方程为 9 32 由 解式 9 32 差分方程组得 9 33 其中 9 34 9 35 9 36 9 37 9 38 9 39 二 实例分析机器维修服务 一 问题提出机器发生故障后排队等待修理 队伍越长因停产造成的损失越大 提高维修工人和设备的服务速度或增加其数量可以减少队长 但将使修理费用上升选择怎样的服务速度 或者确定几个维修工人和设备使损失和修理的总费用最小 二 建模与分析模型 最优服务率假设 1 发生故障机器维修服务服从M M 1 平均到达率 单位时间发生故障的机器数 为 平均服务率 单位 时间平均修理数 为 且 2 每台故障机器单位时间的损失费为 一台机器平均修理费为 由 1 2 假设 可得单位时间损失和修理的总费用为模型即为 9 40 由 9 41 令得而 于是即为最优服务率 这就说明随着发生故障机器数和损失费的增加而增加 随着修理费的增加而减少 合乎情理 的增加而减少 合乎情理 由于模型 是单服务台系统 得到最