2013更新排队论讲座.ppt

2020 2 9 信息工程大学信息工程学院 1 一 CUMCM历年赛题的分析 近几年题目的特点 1 综合性 一题多解 方法融合 结果多样 学科交叉 2 开放性 题意的开放性 思路的开放性 方法的开放性 结果的开放性 3 实用性 问题和数据来自于实际 解决方法切合于实际 模型和结果可以应用于实际 4 即时性 国内外的大事 社会的热点 生活的焦点 近期发生和即将发生被关注的问题 5 数据结构的复杂性 数据的真实性 数据的海量性 数据不完备性 数据的冗余性 2020 2 9 信息工程大学信息工程学院 2 1 数学建模竞赛的竞争日趋激烈 二 数学建模竞赛的发展趋势 由于数学建模在创新人才培养中的地位和作用所在 数学建模受到了越来越多的人的重视和关注 特别是引起了更多领导们的重视 因为数学建模竞赛有很强的可比性和竞争性 竞赛成绩是反映能力和水平的一个实力型指标 也是高校评估的一个重要指标 2005年有795所高校的8492个队参赛 2006年达到864所院校 9985个队 增长17 6 可以称为是目前全国最大规模的科技竞赛活动 2020 2 9 信息工程大学信息工程学院 3 1 数学建模竞赛的竞争日趋激烈 二 数学建模竞赛的发展趋势 数学建模竞赛十九年来的发展情况 平均年增长量30 2020 2 9 信息工程大学信息工程学院 4 二 数学建模竞赛的发展趋势 2 数学建模竞赛题目的发展趋势 赛题的水平不断提高 难度在增加 实用性在增强 综合性和开放性也在增强 这是一大潮流 逐步走向国际化的趋势 同国际接轨是必然的 随着计算机技术和工具软件功能的增强 数据信息量也会逐步增大 从海量数据信息中获得真知 这也是现代应用的特点之一 2020 2 9 信息工程大学信息工程学院 5 二 数学建模竞赛的发展趋势 有人说 21世纪的社会是信息的社会 数据信息是已成为21世纪的基本特征 由全球经济一体化 社会管理的全球化 生命科学指数增长的数据 以及互联网数据的涌现 使得数据化社会已经形成 一方面人们都被数据的海洋所淹没 另一方面人们期望从数据的海洋中获得所需要的信息和知识 从而面向海量数据的计算与分析 通过建立数学模型用于指导决策 现已成为科学研究的一种最重要的方法 问题 我们应该怎么办 如何应对 2020 2 9 信息工程大学信息工程学院 6 根据全国大学生数学建模竞赛的发展趋势 那么建模竞赛题究竟向何处发展 2 数学建模竞赛题目的发展趋势 1 增强综合性 进一步体现创新意识和能力 2 增强开放性 逐步同国际接轨 3 增强即时性 扩大竞赛的社会效益 4 增强实用性 贴近生活和现代实际的科研工作 5 增强挑战性 吸引更多青年教师和学生的参与热情 二 数学建模竞赛的发展趋势 2020 2 9 信息工程大学信息工程学院 7 二 数学建模竞赛的发展趋势 3 全国评卷工作的变化 1 全国组委会不再提供参考答案 2 提倡相邻赛区间的联合阅卷 3 全国组委会改革评卷方法 4 全国组委会已出台了两个评卷规范 返回 2020 2 9 信息工程大学信息工程学院 8 三 对数学建模的几点想法与思考 1 积极创造条件 争取各级组织和领导的支持与帮助 2 加强宣传 充分调动广大学生参与的积极性和热情 学生是数学建模的主力军 3 务实工作 从基础抓起 基础永远是第一位的 4 学习新知识和新方法 研究新问题 提高自身的能力和素质 促进教学和科研水平的提高 1 几点启发性想法 2020 2 9 信息工程大学信息工程学院 9 5 扩大交流与合作 提高综合实力水平 6 加大投入力度 有效扎实工作 无私奉献 争取好成绩 成绩永远与投入成正比 7 增强建模意识 培养建模能力 将数学建模的思想和方法贯穿到实际教学 科研和生活中去 8 实事求是 相信学生 讲求实效 科学指导 三 对数学建模的几点想法与思考 1 几点启发性想法 2020 2 9 信息工程大学信息工程学院 10 1 以学生为主体 增强参与意识 2 以教师为主导 增强责任意识和奉献精神 3 转变观念 务实工作 增强竞争意识 4 加强学习 敢于实践 增强拚搏意识 5 解放思想 与时俱进 增强 建模意识 6 团结为本 合作为上 增强攻关意识 7 勤于思考 不断探索 增强超前意识 8 注重方法 掌握技巧 做到 自圆其说 2 几点应对建议 三 对数学建模的几点想法与思考 2020 2 9 信息工程大学信息工程学院 11 四 参加数学建模竞赛的技巧 1 对赛题的把握和理解问题 1 认真仔细地识题 2 明确条件和任务 3 通过关键词捕捉关键信息 4 分清是非 勿入陷井 2020 2 9 信息工程大学信息工程学院 12 四 参加数学建模竞赛的技巧 1 摘要是文章的重中之重 2 写好论文的关键环节 主要是说明你用什么方法 解决了什么问题 主要结果是什么 有什么特色和创新点 以及其它工作 摘要是整篇文章的高度压缩 注意摘要中不要出现公式和表格 文字精练 表达准确 2020 2 9 信息工程大学信息工程学院 13 四 参加数学建模竞赛的技巧 2 写好论文的关键环节 2 层次分明 重点突出 论文是你们所有工作的完全体现 力争将你们的工作和创造性成果或新的研究结果都充分地反映出来 要求内容充实 论据充分 论证有力 主题明确 层次分明 通过大小标题分为若干个逻辑段落 让评委各取所需 一目了然 不要给评委留下更多的疑问和猜测 实事求是 不要过分夸张 2020 2 9 信息工程大学信息工程学院 14 四 参加数学建模竞赛的技巧 3 参加竞赛的七条准则 1 数据处理的实用性和规范性 2 建模方法的先进性和适用性 3 模型建立的创新性和正确性 4 模型表述的准确性和完整性 5 数据结果的可靠性和正确性 6 论文结构的合理性和清晰性 7 语言表述的完美性和客观性 数学建模成功的条件和模型 有兴趣 肯钻研 有信心 勇挑战 有决心 不怕难 有知识 思路宽 有能力 能开拓 有水平 善协作 有办法 点子多 有毅力 轻结果 数学建模成功的数学模型为 兴趣 信心 决心 知识 能力 水平 办法 毅力 运气 成功 奖励 16 排队论 QueuingTheory 排队论 queuing 也称随机服务系统理论 是运筹学的一个主要分支 1909年 丹麦哥本哈根电子公司电话工程师A K Erlang的开创性论文 概率论和电话通讯理论 标志此理论的诞生 排队论的发展最早是与电话 通信中的问题相联系的 并到现在是排队论的传统的应用领域 近年来在计算机通讯网络系统 交通运输 医疗卫生系统 库存管理 作战指挥等各领域中均得到应用 排队系统由接受服务的实体和提供服务的实体组成 排队论是运筹学的又一个分支 它也被称为随机服务系统理论 排队论主要研究排队系统的排队队长 排队的等待时间及所提供的服务的效率等各种参数 研究排队问题实质上就是研究如何平衡等待时间与服务时间 也就是如何确定一个排队系统 能够对顾客和服务者都有利 即服务效率要高 顾客等待时间又要合理 排队系统 以理发馆系统为例 在研究理发馆系统时 不考虑如下情况 1 理发馆的设备与工具 2 理发师的个人行为 道德品质 技术高低 3 顾客对发型的偏好等关注的是 1 理发馆的服务能力 2 理发师的忙闲状况 3 顾客拥挤程度 等待理发的顾客有多少 研究目的为 1 分析系统运行状况 2 找出系统运行的瓶颈 3 改造系统结构 排队系统 以此来提高系统运行效率从而产生更大经济效益 分析理发排队系统 1 如果增加理发师 则排队减少 获得服务的顾客会增多 理发馆收入会增加 但是理发师工资成本也会增加 2 如果减少理发师 则排队严重 获得服务的顾客会减少 理发馆收入会减少 但是理发师工资成本也会降低 由此产生了矛盾的两个方面 1 增加服务能力 收入会增加但成本也会增加 2 减少服务能力 收入会减少但成本也会减少 因此肯定会存在一个最优的服务能力 使理发馆获得利润最大 排队系统 例 只有一个理发师的理发店模型 单窗口排队系统图解式模型 到达 服务 离开 空闲 排队 到达 排队 服务 离开 服务台 排队系统的业务流程 Y N 有限顾客源系统 集装箱码头的拖车 起重机为服务员 物流公司的运输车辆 公交公司的运输车辆无限顾客源系统 餐馆 银行 流水生产线 2 排队规则排队规则指队列中顾客的逻辑顺序以及当服务台变成空闲时选取队列中哪一个顾客为其服务的规则 常见的排队规则包括先进先出 FIFO 后进先出 LIFO 随机服务 SIRO 最短处理时间优先 SPT 以及按优先级别服务 PR 以上规则缩写在后片中另有表示 排队系统的业务流程 22 3 服务机构服务机构向顾客提供服务 与服务机构密切相关的三个属性为 1为顾客服务所需要的时间 同样具有一定规律 服从某种分布 2服务机构所具有的服务能力 即能够同时服务的顾客数量 3服务是否允许被抢占 抢占采取怎样的方式与规则 在无限总体模型中 无限顾客源系统 顾客总是会以一定的间隔时间 依次到达系统 我们通常用相继到达的顾客的到达间隔时间来刻画顾客的到达过程 相继到达的顾客的间隔时间往往是一个随机的变量 间隔时间貌似杂乱无章 无规律可循 但是如果他们作为一个总体来看 往往能够与某一特定的随机分布函数相吻合 例如 顾客到达餐馆 顾客到达银行 呼叫中心的电话 对某种服务或产品的请求或订单的到达以及进入维修车间的故障设备的到达等此类的间隔时间往往符合泊松分布 特征值各有不同 若顾客到达间隔时间或服务时间中有一个为随机变量 则这个排队系统称为随机排队系统 在日常生活和生产管理中 存在着大量的随机排队系统 表2 1 1列出了一些常见的随机排队系统 随机排队系统 随机排队系统 25 1 1排队系统的组成与特征排队系统一般有三个基本组成部分 1 输入过程 2 排队规则 3 服务机构 现分别说明 1排队论的基本概念 26 输入即为顾客的到达 可有下列3种情况 1 顾客来源 顾客总体 称为顾客源 的组成可能是有限的 也可能是无限的 如 上游河水流入水库可以认为总体是无限的 工厂内停机待修的机器显然是有限的总体 2 顾客到达方式 顾客到来的方式可能是一个一个的 也可能是成批的 如 到餐厅就餐就有单个到来的顾客和受邀请来参加宴会的成批顾客 1 输入过程 27 3 顾客流的概率分布 顾客随机一个 批 个 批 来到排队系统 顾客流的概率分布用来描述相继到达的顾客之间的间隔时间分布是确定的还是随机的 分布参数是什么 到达的间隔时间是否独立 分布是随时间变化的还是平稳的 28 2 排队规则 1 损失制 顾客到达时 如果所有的服务台都被占用 且服务机构又不允许顾客等待 顾客只能离去 这种服务规则就是损失制 2 等待制 当顾客到达时 如果所有服务台都被顾客占用而无空闲 这时该顾客自动加入队列排队等待服务 服务完才离开 1 先到先服务FCFS 2 后到先服务LCFS 3 随机服务RAND 4 有优先权服务PR 29 3 服务机构 1 服务机构可以是单服务员和多服务员服务 这种服务形式与队列规则联合后形成了多种不同队列 不同形式的排队服务机构 如 30 上述特征中最主要的 影响最大的是 顾客相继到达的间隔时间分布服务时间的分布服务台数D G Kendall 1953提出了分类法 称为Kendall记号 适用于并列服务台 即 X Y Z A B C 2 服务方式分为单个顾客服务和成批顾客服务 3 服务时间分为确定型和随机型 4 服务时间的分布在这里我们假定是平稳的 1 2排队系统的模型分类 31 式中 X 顾客相继到达间隔时间分布 M 负指数分布Markov D 确定型分布Deterministic Ek K阶爱尔朗分布Erlang GI 一般相互独立随机分布 GeneralIndependent G 一般随机分布 Y 填写服务时间分布 与上同 Z 填写并列的服务台数A 排队系统的最大容量B 顾客源数量C 排队规则如 M M 1 FCFS 即为顾客到达为泊松过程 服务时间为负指数分布 单台 无限容量 无限源 先到先服务的排队系统模型 32 系统指标队长 指在系统中的顾客数 它的期望值记Ls 2 排队长 指在系统中排队等待服务的顾客数 它的期望值记作Lq 一般情形 Ls 或Lq 越大 说明服务效率越低 33 3 逗留时间 指一个顾客在系统中的停留时间 它的期望值记作Ws 4 等待时间 指一个顾客在系统中排队等待的时间 它的期望值记作Wq 34 1 3排队论研究的基本问题1 排队系统的统计推断 即通过对排队系统主要参数的统计推断和对排队系统的结构分析 判断一个给定的排队系统符合于哪种模型 以便根据排队理论进行研究 2 系统性态问题 即研究各种排队系统的概率规律性 主要研究队长分布 等待时间分布和忙期分布等统计指标 包括了瞬态和稳态两种情形 3 最优化问题 即包括最优设计 静态优化 最优运营 动态优化 35 1 4排队问题求解 主要指性态问题 求解一般排队系统问题的目的主要是通过研究排队系统运行的效率指标 估计服务质量 确定系统的合理结构和系统参数的合理值 以便实现对现有系统合理改进和对新建系统的最优设计等 排队问题的一般步骤 1 确定或拟合排队系统顾客到达的时间间隔分布和服务时间分布 可实测 2 研究系统状态的概率 系统状态是指系统中顾客数 状态概率用Pn t 表示 即在t时刻系统中有n个顾客的概率 也称瞬态概率 36 求解状态概率Pn t 方法是建立含Pn t 的微分差分方程 通过求解微分差分方程得到系统瞬态解 由于瞬态解一般求出确定值比较困难 即便求得一般也很难使用 因此我们常常使用它的极限 如果存在的话 稳态的物理意义见右图 系统的稳态一般很快都能达到 但实际中达不到稳态的现象也存在 值得注意的是求稳态概率Pn并不一定求t 的极限 而只需求Pn t 0即可 称为稳态 steadystate 解 或称统计平衡状态 StatisticalEquilibriumState 的解 37 2排队论主要知识点 排队系统的组成与特征排队系统的模型分类顾客到达间隔时间和服务时间的经验分布与理论分布稳态概率Pn的计算标准的M M 1模型 M M 1 FCFS 系统容量有限制的模型 M M 1 N FCFS 顾客源有限模型 M M 1 M FCFS 标准的 M M C 模型 M M C FCFS 38 M M C型系统和C个M M 1型系统系统容量有限制的多服务台模型 M M C N 顾客源为有限的多服务台模型 M M C M 一般服务时间的 M G 1 模型Pollaczek Khintchine P K 公式定长服务时间M D 1模型爱尔朗服务时间M Ek 1模型排队系统优化M M 1模型中的最优服务率u标准的M M 1Model系统容量为N的情形M M C模型中最优服务台数C 39 3到达间隔时间分布和服务时间的分布 一个排队系统的最主要特征参数是顾客的到达间隔时间分布与服务时间分布 要研究到达间隔时间分布与服务时间分布需要首先根据现存系统原始资料统计出它们的经验分布 见数理统计 然后与理论分布拟合 若能照应 我们就可以得出上述的分布情况 40 3 1经验分布 经验分布是对排队系统的某些时间参数根据经验数据进行统计分析 并依据统计分析结果假设其统计样本的总体分布 选择合适的检验方法进行检验 当通过检验时 我们认为时间参数的经验数据服从该假设分布 分布的拟合检验一般采用 2检验 由数理统计的知识我们知 若样本量n充分大 n 50 则当假设H0为真时 统计量总是近似地服从自由度为k r 1的 2分布 其中k为分组数 r为检验分布中被估计的参数个数 41 3 2理论分布 1 泊松分布在概率论中 我们曾学过泊松分布 设随机变量为X 则有 n 0 1 2 1 与时间有关的随机变量的概率 是一个随机过程 即泊松过程 t 0 n 0 1 2 2 42 t2 t1 n 0 若设N t 表示在时间区间 0 t 内到达的顾客数 t 0 Pn t1 t2 表示在时间区间 t1 t2 t2 t1 内有n 0 个顾客到达的概率 即 当Pn t1 t2 符合下述三个条件时 顾客到达过程就是泊松过程 顾客到达形成泊松流 43 平稳性 即对于足够小的 t 有 泊松流具有如下特性 在 t t t 内有一个顾客到达的概率与t无关 而与 t成正比 44 普通性 对充分小的 t 在时间区间 t t t 内有2个或2个以上顾客到达的概率是一高阶无穷小 由此知 在 t t t 区间内没有顾客到达的概率为 令t1 0 t2 t 则P t1 t2 Pn 0 t Pn t 0是常数 它表示单位时间到达的顾客数 称为概率强度 即 P0 P1 P 2 1 在上述假设下 t时刻系统中到达n个顾客的概率pn t 45 46 1 当n 0时 则 瞬态方程 由 1 变量分离 2 常数变易 得 47 级数 令k n 1 则 同理方差为 顾客到达过程是一个泊松过程 泊松流 期望 48 表示单位时间内顾客平均到达数 1 表示顾客到达的平均间隔时间 对顾客的服务时间 系统处于忙期时两顾客相继离开系统的时间间隔 一般地也服从负指数分布 接受服务 然后离开 服务时间的分布 2 负指数分布可以证明当输入过程是泊松流时 两顾客相继到达的时间间隔T独立且服从负指数分布 等价 则 49 其中 表示单位时间内能被服务的顾客数 即平均服务率 1 表示一个顾客的平均服务时间 3 爱尔朗 Erlang 分布设v1 v2 vk是k个独立的随机变量 服从相同参数k 的负指数分布 那么 则 令 则 称为服务强度 50 串联的k个服务台 每台服务时间相互独立 服从相同的负指数分布 参数k 那么一顾客走完k个服务台总共所需要服务时间就服从上述的k阶Erlang分布 则称T服从k阶爱尔朗分布 其特征值为 其概率密度是 1 k 表示一个顾客的一个服务台的平均服务时间 51 例 有易碎物品500件 由甲地运往乙地 根据以往统计资料 在运输过程中易碎物品按普阿松流发生破碎 其破损率为0 002 现求 1 破碎3件物品的概率 2 破碎少于3件的概率和多于3件的概率 3 至少有一件破损的概率 解 0 002 500 11 破碎3件物品的概率为 P k 3 3 3 e 13 3 e 1 0 0613即物品破碎3件的概率为6 13 2 破碎物品少于3件的概率 52 破碎物品少于3件的概率为91 97 破碎物品多于3件的概率为 3 至少有一件破碎的概率为P k 1 1 1k k e 1 10 0 e 1 0 632 53 对排队模型 在给定输入和服务条件下 主要研究系统的下述运行指标 1 系统的平均队长Ls 期望值 和平均队列长Lq 期望值 2 系统中顾客平均逗留时间Ws与队列中平均等待时间Wq 本节只研究M M 1模型 下面分三种情况讨论 4 M M 1模型 54 4 1标准的M M 1模型 单服务窗等待制 系统中有n个顾客 M M 1 FCFS 模型 1 稳态概率Pn的计算 在任意时刻t 状态为n的概率Pn t 瞬态概率 它决定了系统的运行特征 已知顾客到达服从参数为 的泊松过程 服务时间服从参数为 的负指数分布 现仍然通过研究区间 t t t 的变化来求解 在时刻t t 系统中有n个顾客不外乎有下列四种情况 t t t 内到达或离开2个以上没列入 55 由于这四种情况是互不相容的 所以Pn t t 应是这四项之和 则有 所有的高阶无穷小合并 56 当n 0时 只有表中的 A B 两种情况 因为在较小的 t内不可能发生 D 到达后即离去 若发生可将 t取小即可 生灭过程 瞬态解 57 由此可得该排队系统的状态转移图 将其代入 3 式并令n 1 2 也可从状态转移图中看出状态平衡方程 得 关于Pn的差分方程 58 n 1 n 2 59 以此类推 当n n时 5 以及概率性质知 否则排队无限远 系统稳态概率 60 2 系统的运行指标计算 1 系统中的队长Ls 平均队长 0 1 期望 61 2 队列中等待的平均顾客数Lq 8 3 顾客在系统中的平均逗留时间Ws顾客在系统中的逗留时间是随机变量 可以证明 它服从参数为 的负指数分布 分布函数 62 4 顾客在队列中的平均逗留时间Wq 等待时间 顾客在队列中的平均逗留时间应为Ws减去平均服务时间 考虑LS与WS的关系 63 四个指标的关系为 Little公式 李特尔公式 3 系统的忙期与闲期 系统处于空闲状态的概率 系统处于繁忙状态的概率 服务强度 64 在繁忙状态下 队列中的平均顾客数Lb 顾客平均等待时间 一个忙期平均服务的顾客数为 Lb P N 0 Lq 65 例 某医院手术室根据病人来诊和完成手术的时间记录 任意抽查100个工作小时 每小时来就诊的病人数n的出现次数如表9 4 又任意抽查了100个完成手术的病历 所用时间v 小时 出现的次数如表9 5 计算手术室的各项指标 66 表9 4 表9 5 67 1 参数的确定算出每小时病人平均到达率 2 1 人 小时 每次手术平均时间 0 4 小时 人 每小时完成手术人数 平均服务率 2 5 人 小时 2 取 2 1 2 5 可以通过统计检验的方法 例如 2检验法 认为病人到达数服从参数为2 1的普阿松分布 手术时间服从参数为2 5的负指数分布 3 它说明服务机构 手术室 有84 的时间是繁忙 被利用 有16 的时间是空闲的 68 4 依次算出各指标 在病房中病人数 期望值 排队等待病人数 期望值 病人在病房中逗留时间 期望值 病人排队等待时间 期望值 4 2单服务窗混合制 系统的容量有限制的情形列出状态概率的稳态方程 各状态间概率强度的转换关系图 列出状态概率的稳态方程 令 因而得 现在把型的指标归纳如下 当时 4 3顾客源为有限的情形 省略求解步骤 求得系统的各项指标为 74 5 多服务台的情形 M M C 5 1标准的 M M C 模型 等待制 即 M M C FCFS 标准的 M M C 模型与标准的 M M 1 模型的各特征规定相同 另外 各服务台工作是相互独立且平均服务率相同 即 1 2 3 c 整个服务机构的平均服务率为 c n c时 或n n c时 令 只有当时 才不会形成无限队列 75 从右图的队列图分析系统中的状态转移关系 见下面状态转移图 由上图知 当n c时 为c 故可得差分方程 76 利用递推法解该差分方程可求得状态概率为 这里 1 77 系统的运行指标为 78 例4 某售票所有三个窗口 一个队列形成M M C系统 顾客到达服从泊松流 0 9人 M 服务时间服从负指数分布 0 4人 M 求 1 空闲的概率 2 平均队长Ls Lq 3 平均等待时间和逗留时间Wq Ws 4 顾客到达后必须等待的概率 解 1 79 2 3 80 4 为计算简化 现专门根据 c 值和c值编制了Wq 数值表可供使用 其结构为 顾客到达后必须等待的概率 81 例如上题中可查表得 0 75 c 3 Wq 0 756 82 5 2M M C型系统和C个M M 1型系统的比较 上面说的是M M C型系统 系统中只有一个队列 若系统c个服务台前各有一个队列 则是c个M M 1系统的迭加 见下面图示 虽然这两种系统看上去相似 但其运行指标却有很大差别 83 现仍以上面的例4进行分析 如果除排队方式外 其它条件不变 顾客到达每个窗口前各排一队 且进入队后坚持不换 这就形成了上面的队列 每个队列的平均到达率为 1 2 c c 0 9 3 0 3人 M 这样 原来的系统就变成了 0 3人 M的3个M M 1型子系统 且相互独立 按M M 1求解并与上面的比较得 从上表可知 M M C系统明显比C个M M 1系统的指标优 84 5 3系统容量有限制的情形 M M C N 损失制 设系统的容量最大限制为N C 当系统中顾客数n已达到N 即队列中的顾客数已达N C 时 再来的顾客将被拒绝 其他条件与标准的M M C型相同 此时的状态概率为 85 其中 运行指标为 86 5 4顾客源为有限的情况 M M C M 设顾客源为有限m 且m c 顾客到达率是按每个顾客考虑的 在机器维修模型中就是有m台机器 C个修理工 机器故障率就是每个机器单位运转时间出故障的期望次数 系统中顾客数n就是出故障的机器台数 当n C时 无排队 有c n个修理工空闲 当c n m时 有 n c 台机器停机等待修理 系统处于繁忙状态 假定 1 每个服务台速率均为 的负指数分布 2 故障修复时间与正在生产的机器是否发生故障是相互独立的 则有 87 88 例 设有两个修理工人 负责5台机器的正常运行 每台机器平均损坏率为每运转小时1次 两工人能以相同的平均修复率4 次 小时 修好机器 求 1 等待修理的机器平均数2 需要修理的机器平均数3 有效损坏率4 等待修理时间5 停工时间 89 解m 5 1 次 小时 4 台 小时 c 2 c m 1 4 90 6一般服务时间的 M G 1 模型 任意分布服务时间 任何情形下面的关系都正确 Ls Lq Lse Lse 服务机构中的顾客数 Ws Wq E T E T 服务平均时间 Ls Ws Lq Wq当然 对于有容量限制和有限源情形 要换成 e 6 1Pollaczek Khintchine P K 公式对M G 1模型 只要服务时间的E T 和Var T 存在 其他条件与M M 1相同 且 1 E T 则有 6 2定长服务时间M D 1模型该情况是服务时间是确定的常数 如一条装配线上完成一件工作的时间是常数 则 T 1 Var T 0Ls 2 2 1 这就是著名的P K公式 只要知道 E T Var T 无论T服从什么分布 各项运行指标都可算出来 92 例5某售票口 顾客平均2 5分钟到达一个 服从负指数分布 顾客在售票口前至少要占用一分钟 且服务时间服从 f y e y 1y 10y 0即x是服从均值为1的负指数分布 E y E 1 x 2 Var y Var 1 x Var x 1根据P K公式 93 人 94 定长服务时间M D 1模型 服务时间是确定的常数 例如在一条装配线上完成一件工作的时间是常数 自动的汽车冲洗台 冲洗一辆汽车的时间也是常数 这时 T 1 Var T 0 95 例6某实验室有一台自动检验机器性能的仪器 要求检机器的顾客按普阿松分布到达 每小时平均4个顾客 检验每台机器所需时间为6分钟 1 在检验室内机器台数Ls 期望值 2 等候检验的机器台数Lq 3 每台机器在室内消耗时间Ws 4 每台机器平均等待检验的时间Wq 96 6 3爱尔朗服务时间M Ek 1模型如图示 若顾客必须经过k个服务站 在每个服务站的服务时间Ti相互独立 并服从相同的负指数分布 参数为k 那么服从k阶爱尔朗分布 97 则M Ek 1模型的运行指标为 98 例7某单人裁缝店做西服 每套需经过4个不同的工序 4个工序完成后才开始做另一套 每一工序的时间服从指数分布 期望值为2小时 顾客到达服从普阿松分布 平均订货率为5 5套 周 设一周为6天 每天8小时 问一顾客为等到做好一套西服的期望时间为多长 5 5套 周 设 为平均服务率 单位时间做完的套数 1 为平均每套所需要的时间 1 4 为平均每工序所需要的时间 1 8套 小时 6套 周 解 期望时间即等待时间 1小时完成二分之一工序 99 7经济分析 排队系统优化 排队系统优化问题分为两类 系统设计和系统控制优化 前者称为静态问题 研究如何使设备达到最大效益或机构最为经济 后者称为动态问题 研究如何运营可使某个目标达到最优 该问题是多年来的研究重点之一 因涉及更多的数学知识 本节我们只讨论静态问题 从静态考虑 排队系统主要涉及两项费用 等待损失费用和服务费用 服务费容易确切计算 而等待费不易确定 它们之间的关系如下图示 100 研究这类问题 对离散变量常用边际分析法 对连续变量常用经典的微分法 也可用NLP及DP 图中的服务水平主要是平均服务率 其他是服务设备 台数c 及队列限制N等也可以通过服务强度 表示 101 7 1M M 1模型中的最优服务率 1 标准的M M 1Model设 Cs为在 1时服务机构的单位时间费用 Cw为每个顾客在系统停留单位时间的费用 则总单位时间成本z为 102 2 系统容量为N的情形 单服务台混合制排队模型 该系统中顾客到达后在系统中超过N个时 将被拒绝 拒绝概率为PN 则1 PN为接受概率 所以 1 PN 为单位时间内进入系统的顾客平均数 也是单位时间内实际服务的平均数 1 PN 1 P0 设每服务一个能收