排队论简要知识.ppt

随机服务系统理论 排队论及其应用 排队论的基本概念 排队系统描述基本概念M M 1模型M M S模型 第一节排队系统描述 顾客 要求服务的对象统称为 顾客 服务台 把提供服务的人或机构称为 服务台 或 服务员 各种形式的排队系统 各种形式的排队系统 各种形式的排队系统 各种形式的排队系统 各种形式的排队系统 随机服务系统 排队论所要研究解决的问题 面对拥挤现象 人们通常的做法是增加服务设施 但是增加的数量越多 人力 物力的支出就越大 甚至会出现空闲浪费 如果服务设施太少 顾客排队等待的时间就会很长 这样对顾客会带来不良影响 如何做到既保证一定的服务质量指标 又使服务设施费用经济合理 恰当地解决顾客排队时间与服务设施费用大小这对矛盾 就是随机服务系统理论 排队论所要研究解决的问题 第一节基本概念 一 排队系统的描述二 排队系统的主要数量指标 一 排队系统的描述 一 系统特征和基本排队过程 二 排队系统的基本组成部分 三 排队系统的描述符号 一 系统特征和基本排队过程 相似的特征及数学抽象 1 请求服务的人或者物 顾客 2 有为顾客服务的人或者物 即服务员或服务台 3 顾客到达系统的时刻是随机的 为每一位顾客提供服务的时间是随机的 因而整个排队系统的状态也是随机的 一 系统特征和基本排队过程 基本排队过程可以用图6 6表示 从图6 6可知 每个顾客由顾客源按一定方式到达服务系统 首先加入队列排队等待接受服务 然后服务台按一定规则从队列中选择顾客进行服务 获得服务的顾客立即离开 二 排队系统的基本组成部分 排队系统由3个部分组成1 输入过程2 服务规则3 服务台 1 输入过程 这是指要求服务的顾客是按怎样的规律到达排队系统的过程 有时也把它称为顾客流 一般可以从3个方面来描述 个输入过程 1 顾客总体数 又称顾客源 输入源 这是指顾客的来源 顾客源可以是有限的 也可以是无限的 2 顾客到达方式 这是描述顾客是怎样来到系统的 是单个到达 还是成批到达 3 顾客流的概率分布 或称相继顾客到达的时间间隔的分布 这是求解排队系统有关运行指标问题时 首先需要确定的指标 顾客流的概率分布一般有定长分布 二项分布 泊松流 最简单流 爱尔朗分布等若干种 2 服务规则 这是指服务台从队列中选取顾客进行服务的顺序 一般可以分为损失制 等待制和混合制等3大类 1 损失制 这是指如果顾客到达排队系统时 所有服务台都被先到的顾客占用 那么他们就自动离开系统永不再来 2 服务规则 2 等待制这是指当顾客来到系统时 所有服务台都不空 顾客加入排队行列等待服务 等待制中 服务台在选择顾客进行服务时常有如下四种规则 1 先到先服务 按顾客到达的先后顺序对顾客进行服务 2 后到先服务 3 随机服务 即当服务台空闲时 不按照排队序列而随意指定某个顾客接受服务 4 优先权服务 2 服务规则 3 混合制这是等待制与损失制相结合的一种服务规则 一般是指允许排队 但又不允许队列无限长下去 具体说来 大致有三种 1 队长有限 当排队等待服务的顾客人数超过规定数量时 后来的顾客就自动离去 另求服务 即系统的等待空间是有限的 2 等待时间有限 即顾客在系统中的等待时间不超过某一给定的长度T 当等待时间超过T时 顾客将自动离去 并不再回来 3 逗留时间 等待时间与服务时间之和 有限 3 服务台 1 服务台数量及构成形式 从数量上说 服务台有单服务台和多服务台之分 从构成形式上看 服务台有 单队 单服务台式 单队 多服务台并联式 多队 多服务台并联式 单队 多服务台串联式 单队 多服务台并串联混合式 以及多队多服务台并串联混合式等等 2 服务方式 这是指在某一时刻接受服务的顾客数 它有单个服务和成批服务两种 3 服务时间的分布 在多数情况下 对每一个顾客的服务时间是一随机变量 三 排队系统的符号表述 描述符号 各符号的意义 表示顾客相继到达间隔时间分布 常用下列符号 M 表示到达的过程为泊松过程或负指数分布 D 表示定长输入 EK 表示K阶爱尔朗分布 G 表示一般相互独立的随机分布 各符号的意义 表示服务时间分布 所用符号与表示顾客到达间隔时间分布相同 表示服务台 员 个数 1 表示单个服务台 s s 1 表示多个服务台 表示系统中顾客容量限额 或称等待空间容量 如系统有K个等待位子 则 0 K 当K 0时 说明系统不允许等待 即为损失制 K 时为等待制系统 此时一般 省略不写 K为有限整数时 表示为混合制系统 各符号的意义 表示顾客源限额 分有限与无限两种 表示顾客源无限 一般 也可省略不写 表示服务规则 常用下列符号FCFS 表示先到先服务的排队规则 LCFS 表示后到先服务的排队规则 PR 表示优先权服务的排队规则 各符号的意义 例如 某排队问题为M M S FCFS 则表示顾客到达间隔时间为负指数分布 泊松流 服务时间为负指数分布 有s s 1 个服务台 系统等待空间容量无限 等待制 顾客源无限 采用先到先服务规则 某些情况下 排队问题仅用上述表达形式中的前3个符号 例如 某排队问题为M M S 如不特别说明则均理解为系统等待空间容量无限 顾客源无限 先到先服务 单个服务的等待制系统 二 排队系统的主要数量指标 描述一个排队系统运行状况的主要数量指标有 1 队长和排队长 队列长 队长是指系统中的顾客数 排队等待的顾客数与正在接受服务的顾客数之和 排队长是指系统中正在排队等待服务的顾客数 队长和排队长一般都是随机变量 二 排队系统的主要数量指标 2 等待时间和逗留时间从顾客到达时刻起到他开始接受服务止这段时间称为等待时间 等待时间是个随机变量 从顾客到达时刻起到他接受服务完成止这段时间称为逗留时间 也是随机变量 3 忙期和闲期忙期是指从顾客到达空闲着的服务机构起 到服务机构再次成为空闲止的这段时间 即服务机构连续忙的时间 这是个随机变量 是服务员最为关心的指标 因为它关系到服务员的服务强度 与忙期相对的是闲期 即服务机构连续保持空闲的时间 在排队系统中 忙期和闲期总是交替出现的 二 排队系统的主要数量指标 4 数量指标的常用记号 1 主要数量指标L 平均队长 即稳态系统任一时刻的所有顾客数的期望值 Lq 平均等待队长 即稳态系统任一时刻等待服务的顾客数的期望值 W 平均逗留时间 即 在任意时刻 进入稳态系统的顾客逗留时间的期望值 Wq 平均等待时间 即 在任意时刻 进入稳态系统的顾客等待时间的期望值 4 数量指标的常用记号 2 其他常用数量指标s 系统中并联服务台的数目 平均到达率 1 平均到达间隔 平均服务率 1 平均服务时间 N 稳态系统任一时刻的状态 即系统中所有顾客数 U 任一顾客在稳态系统中的逗留时间 Q 任一顾客在稳态系统中的等待时间 2020 3 16 29 可编辑 2 其他常用数量指标 2 其他常用数量指标 服务强度 即每个服务台单位时间内的平均服务时间 般有 s 这是衡量排队系统繁忙程度的重要尺度 当 趋近于0时 表明对期望服务的数量来说 服务能力相对地说是很大的 这时 等待时间一定很短 服务台有大量的空闲时间 如服务强度 趋近于1 那么服务台空闲时间较少而顾客等待时间较多 我们一般都假定平均服务率 大于平均到达率 即 1 否则排队的人数会越来越多 以后总是保持这个假设而不再声明 李特尔公式 在系统达到稳态时 假定平均到达率为常数 平均服务时间为常数1 则有下面的李特尔公式 L WLq WqW Wq 1 L Lq 排队系统运行情况的分析 排队系统运行情况的分析 就是在给定输人与服务条件下 通过求解系统状态为n 有n个顾客 的概率Pn 再进行计算其主要的运行指标 系统中顾客数 队长 的期望值L 排队等待的顾客数 排队长 的期望值Lq 顾客在系统中全部时间 逗留时间 的期望值W 顾客排队等待时间的期望值Wq 第二节M N 1模型 模型的条件是 1 输入过程 顾客源是无限的 顾客到达完全是随机的 单个到来 到达过程服从普阿松分布 且是平稳的 2 排队规则 单队 且队长没有限制 先到先服务 3 服务机构 单服务台 服务时间的长短是随机的 服从相同的指数分布 对于M M 1模型有如下公式 例1 某医院急诊室同时只能诊治一个病人 诊治时间服从指数分布 每个病人平均需要15分钟 病人按泊松分布到达 平均每小时到达3人 试对此排队队系统进行分析 解对此排队队系统分析如下 1 先确定参数值 这是单服务台系统 有 故服务强度为 2 计算稳态概率 这就是急诊室空闲的概率 也是病人不必等待立即就能就诊的概率 而病人需要等待的概率则为 这也是急诊室繁忙的概率 2 计算系统主要工作指标 急诊室内外的病人平均数 急诊室外排队等待的病人平均数 病人在急诊室内外平均逗留时间 病人平均等候时间 4 为使病人平均逗留时间不超过半小时 那么平均服务时间应减少多少 由于代入 3 解得 5 平均服务时间为 15 12 3min即平均服务时间至少应减少3min 5 若医院希望候诊的病人90 以上都能有座位 则候诊室至少应安置多少座位 设应该安置 个座位 加上急诊室的一个座位 共有 1个 要使90 以上的候诊病人有座位 相当于使 来诊的病人数不多于 1个 的概率不少于90 即 两边取对数 x 2 lg lg0 1因 1 故所以 6即候诊室至少应安置6个座位 第三节M M S模型 此模型与M M 1模型不同之处在于有S个服务台 各服务台的工作相互独立 服务率相等 如果顾客到达时 S个服务台都忙着 则排成一队等待 先到先服务的单队模型 整个系统的平均服务率为s s 1 为该系统的服务强度 1 状态概率 2 主要运行指标3 系统状态N S的概率 例2承接例1 假设医院增强急诊室的服务能力 使其同时能诊治两个病人 且平均服务率相同 试分析该系统工作情况 并且 例1 例2的结果进行比较 解这相当于增加了一个服务台 故有 S 2 3人 h 4人 h 病人必须等候的概率 即系统状态N 2的概率 表6 1两个系统的比较 例3某医院挂号室有三个窗口 就诊者的到达服从泊松分布 平均到达率为每分钟0 9人 挂号员服务时间服从指数分布 平均服务率每分钟04人 现假设就诊者到达后排成一队 依次向空闲的窗口挂号 显然系统的容量和顾客源是不限的 属于M M 1型的排队服务模型 求 该系统的运行指标解 如果在例3中 就诊者到达后在每个挂号窗口各自排成一队 即排成3队 且进入队列后不离开 各列间也互不串换 这就形成3个队列 而例3中的其它条件不变 假设每个队列平均到达率相等且为 1 2 3 0 9 3 0 3 人 分钟 这样 原来的M M 3系统就变成了3个M M 1型的子系统 现按M M 1型计算主要运行指标 并与上面的例子进行对比分析 结果见表6 2 表6 2两个模型的比较 练习 1 思考题 1 排队论主要研究的问题是什么 2 试述排队系统的基本组成部分 3 理解平均到达率 平均服务率 平均服务时间和顾客到达间隔时间等概念 4 试述队长和排队长 等待时间和逗留时间 忙期和闲期等概念 练习 2 设有一个医院门诊 只有一个值班医生 病人的到达过程为泊松流 平均到达时间间隔为20min 诊断时间服从负指数分布 平均需12min 求 1 病人到来不用等待的