运筹学第三版排队论课件.ppt

1 排队论 排队论 queuingtheory 研究内容包括三个部分 1 排队系统的性态问题 2 排队系统的最优化问题 3 排队系统的统计推断问题 解排队问题的目的 是研究排队系统运行的效率 估计服务质量 确定系统参数的最优值 以决定系统结构是否合理 研究设计改进措施等 统计推断 即判断一个给定的排队系统符合哪种模型 以便根据排队理论进行研究 最优化 又分静态最优和动态最优 前者指最优设计 后者指现有排队系统的最优运营 性态问题 即研究各种排队系统的概率规律性 主要研究队长分布 等待时间分布和忙期分布等 2 排队论 第1节基本概念第2节到达间隔的分布和服务时间的分布第3节单服务台负指数分布排队系统的分析第4节多服务台负指数分布排队系统的分析第5节一般服务时间M G 1模型第6节经济分析 系统的最优化第7节分析排队系统的随机模拟法 3 第1节基本概念 1 1排队过程的一般表示1 2排队系统的组织和特征1 3排队模型的分类1 4排队问题的求解 4 不同的顾客与服务组成了各式各样的服务系统 顾客为了得到某种服务而到达系统 若不能立即获得服务而又允许排队等待 则加入队列排队等待接受服务 然后服务台按一定规则从队列中选择顾客进行服务 获得服务的顾客立即离开系统 1 1排队过程的一般表示 5 1 1排队过程的一般表示 各个顾客由顾客源 总体 出发 到达服务机构 服务台 服务员 前排队等候接受服务 服务完成后离开 排队结构指队列的数目和排列方式 排队规则和服务规则是说明顾客在排队系统中按怎样的规则 次序接受服务的 排队过程的一般模型 6 1 1排队过程的一般表示 形形色色的排队系统 7 实际的排队系统虽然千差万别 但是它们有以下的共同特征 1 有请求服务的人或物 顾客 2 有为顾客服务的人或物 即服务员或服务台 3 顾客到达系统的时刻是随机的 为每一位顾客提供服务的时间是随机的 因而整个排队系统的状态也是随机的 排队系统的这种随机性造成某个阶段顾客排队较长 而另外一些时候服务员 台 又空闲无事 1 2排队系统的组成和特征 8 1 2排队系统的组成和特征 排队系统由三个基本部分组成 输入过程 排队规则 服务机构 9 1 2排队系统的组成和特征 输入过程输入即指顾客到达排队系统 输入过程是指要求服务的顾客是按怎样的规律到达排队系统的过程 有时也把它称为顾客流 一般可以从以下几个方面来描述 个输入过程 1 顾客的总体数 又称顾客源 输入源 这是指顾客的来源 顾客源可以是有限的 也可以是无限的 例如 到售票处购票的顾客总数可以认为是无限的 上游河水流入水库可以认为顾客总体是无限的例如 某个工厂因故障待修的机床则是有限的 10 1 2排队系统的组成和特征 输入过程 2 顾客到来的方式 这是描述顾客是怎样来到系统的 他们是单个到达 还是成批到达 病人到医院看病是顾客单个到达的例子 在库存问题中如将生产器材进货或产品入库看作是顾客 那么这种顾客则是成批到达的 11 1 2排队系统的组成和特征 输入过程 3 顾客流的概率分布 或称相继顾客到达的时间间隔的分布 这是求解排队系统有关运行指标问题时 首先需要确定的指标 这也可以理解为在一定的时间间隔内到达K个顾客 K 1 2 的概率是多大 顾客相继到达的间隔时间可以是确定型的 也可以是随机型的 例如 在流水线上装配的各部件必须按确定的时间间隔到达装配点 定点运行的列车 班机的到达也都是确定的 例如 物流配送等待的顾客 办理出关手续的顾客 通过路口的车辆的到达都是随机的 12 1 2排队系统的组成和特征 输入过程对于随机的情形 必须了解单位时间的顾客到达数或相继到达的时间间隔的概率分布 顾客流的概率分布一般有定长分布 二项分布 泊松流 最简单流 爱尔朗分布等若干种 13 1 2排队系统的组成和特征 输入过程 4 顾客的到达可以是相互独立的 5 输入过程可以是平稳的 或称对时间是齐次的 即描述相继到达的间隔时间分布和所含参数 如期望值 方差等 都是与时间无关的 14 1 2排队系统的组成和特征 排队规则这是指服务台从队列中选取顾客进行服务的顺序 一般可以分为损失制 等待制和混合制等3大类 1 损失制 这是指如果顾客到达排队系统时 所有服务台都已被先来的顾客占用 那么他们就自动离开系统永不再来 例如 电话拔号后出现忙音 顾客不愿等待而自动挂断电话 如要再打 就需重新拔号 这种服务规则即为损失制 15 1 2排队系统的组成和特征 排队规则 2 等待制 这是指当顾客来到系统时 所有服务台都不空 顾客加入排队行列等待服务 例如 排队等待售票 故障设备等待维修等 对于等待制 为顾客进行服务的次序可以采用下列各种规则 先到先服务 FCFS 后到先服务 LCFS 随机服务 RS 有优先权的服务 16 1 2排队系统的组成和特征 排队规则 2 等待制 续 先到先服务 按顾客到达的先后顺序对顾客进行服务 这是最普遍的情形 后到先服务 例如 仓库中迭放的钢材 后迭放上去的都先被领走 随机服务 即当服务台空闲时 不按照排队序列而随意指定某个顾客去接受服务 例如 电话交换台接通呼叫电话 优先权服务 例如 老人 儿童先进车站 危重病员先就诊 遇到重要数据需要处理计算机立即中断其他数据的处理等 17 1 2排队系统的组成和特征 排队规则 3 混合制 这是等待制与损失制相结合的一种服务规则 一般是指允许排队 但又不允许队列无限长下去 具体说来 大致有三种 队长有限 等待时间有限 逗留时间有限 18 1 2排队系统的组成和特征 排队规则 3 混合制 队长有限 当排队等待服务的顾客人数超过规定数量时 后来的顾客就自动离去 另求服务 即系统的等待空间是有限的 具体地 最多只能容纳K个顾客在系统中 当新顾客到达时 若系统中的顾客数 又称为队长 小于K 则可进入系统排队或接受服务 否则 便离开系统 并不再回来 例如 水库的库容是有限的 旅馆的床位是有限的 19 1 2排队系统的组成和特征 排队规则 3 混合制 队长有限 等待时间有限 即顾客在系统中的等待时间不超过某一给定的长度T 当等待时间超过T时 顾客将自动离去 并不再回来 例如 易损坏的电子元器件的库存问题 超过一定存储时间的元器件被自动认为失效 例如 顾客到饭馆就餐 等了一定时间后不愿再等而自动离去另找饭店用餐 20 1 2排队系统的组成和特征 排队规则 3 混合制 队长有限 等待时间有限 逗留时间 等待时间与服务时间之和 有限 例如 用高射炮射击敌机 当敌机飞越高射炮射击有效区域的时间为t时 若在这个时间内未被击落 也就不可能再被击落了 不难注意到 损失制和等待制可看成是混合制的特殊情形 如记s为系统中服务台的个数 则当K s时 混合制即成为损失制 当K 时 混合制即成为等待制 21 1 2排队系统的组成和特征 排队规则 续 从允许排队的空间看队列可以排在具体的处所 也可以是抽象的 排队空间可以有限 也可以无限 从排队的队列数目看 可以是单列 也可以是多列 在多列的情形 各列间的顾客有的可以互相转移 有的不能 有的排队顾客因等候时间过长而中途退出 有的不能退出 必须坚持到被服务为止 22 1 2排队系统的组成和特征 服务机构 服务台情况 服务台可以从以下3方面来描述 1 服务台数量及构成形式 服务机构可以没有服务员 也可以有一个或多个服务员 服务台 通道 窗口等 从数量上说 服务台有单服务台和多服务台之分 在有多个服务台的情形中 可以是平行排列的 也可以是前后排列的 或混合排列的 23 1 2排队系统的组成和特征 服务机构 服务台情况 服务台可以从以下3方面来描述 1 服务台数量及构成形式 从构成形式上看 服务台有 单队 单服务台式 如 a 图 单队 多服务台并联式 如 c 图 服务台的各种排列方式 24 1 2排队系统的组成和特征 服务机构 服务台情况 服务台可以从以下3方面来描述 1 服务台数量及构成形式 从构成形式上看 服务台有 单队 单服务台式 如 a 图 单队 多服务台并联式 如 c 图 多队 多服务台并联式 如 b 图 服务台的各种排列方式 25 1 2排队系统的组成和特征 服务机构 服务台情况 服务台可以从以下3方面来描述 1 服务台数量及构成形式 从构成形式上看 服务台有 单队 单服务台式 如 a 图 单队 多服务台并联式 如 c 图 多队 多服务台并联式 如 b 图 单队 多服务台串联式 如 d 图 服务台的各种排列方式 26 1 2排队系统的组成和特征 服务机构 服务台情况 服务台可以从以下3方面来描述 1 服务台数量及构成形式 从构成形式上看 服务台有 单队 单服务台式 如 a 图 单队 多服务台并联式 如 c 图 多队 多服务台并联式 如 b 图 单队 多服务台串联式 如 d 图 单队 多服务台并串联混合式 服务台的各种排列方式 27 1 2排队系统的组成和特征 服务机构 服务台情况 服务台可以从以下3方面来描述 1 服务台数量及构成形式 从构成形式上看 服务台有 单队 单服务台式 如 a 图 单队 多服务台并联式 如 c 图 多队 多服务台并联式 如 b 图 单队 多服务台串联式 如 d 图 单队 多服务台并串联混合式 多队 多服务台并串联混合式等等 服务台的各种排列方式 28 1 2排队系统的组成和特征 服务机构 服务台情况 服务台可以从以下3方面来描述 1 服务台数量及构成形式 从构成形式上看 服务台有 单队 单服务台式 如 a 图 单队 多服务台并联式 如 c 图 多队 多服务台并联式 如 b 图 单队 多服务台串联式 如 d 图 单队 多服务台并串联混合式 多队 多服务台并串联混合式等等 服务台的各种排列方式 29 1 2排队系统的组成和特征 服务机构 服务台情况 2 服务方式 这是指在某一时刻接受服务的顾客数 它有单个服务和成批服务两种 如公共汽车一次就可装载一批乘客就属于成批服务 3 服务时间的分布 服务时间可分为确定型和随机型 一般来说 在多数情况下 对每一个顾客的服务时间是一随机变量 其概率分布有定长分布 负指数分布 K级爱尔良分布 一般分布 所有顾客的服务时间都是独立同分布的 等等 服务时间的分布通常假定是平稳的 指时间间隔分布及其特征参数 数学期望 方差等 不随时间的变化而变化 30 1 3排队模型的分类 排队模型分类方法 D G Kendall 1953构成排队模型的三个主要特征指标 1 相继顾客到达间隔时间的分布 2 服务时间的分布 3 服务台的个数 根据这三个特征对排队模型进行分类的Kendall记号 X Y ZX 表示相继到达间隔时间的分布 Y 表示服务时间的分布 Z 并列的服务台的数目 31 1 3排队模型的分类 表示相继到达间隔时间和服务时间的各种分布符号M 负指数分布 M是Markov的字头 因为负指数分布具有无记忆性 即Markov性 D 确定型 deterministic Ek k阶爱尔朗 erlang 分布GI 一般相互独立 generalindependent 的时间间隔的分布G 一般 general 服务时间的分布 32 1 3排队模型的分类 Kendall符号的扩充X Y Z A B C其中前三项的意义不变 后三项的意义分别是 A 系统容量限制N 或称等待空间容量 如系统有N个等待位子 则0 N 当N 0时 说明系统不允许等待 即为损失制 N 时为等待制系统 此时 般省略不写 N为有限整数时 表示为混合制系统 B 顾客源数目m 分有限与无限两种 表示顾客源无限 此时一般 也可省略不写 C 服务规则 如先到先服务 FCFS 后到后服务 LCFS 优先权服务 PR 等 33 1 3排队模型的分类 Kendall符号的扩充X Y Z A B C某些情况下 排队问题仅用上述表达形式中的前3个 4个 5个符号 如不特别说明则均理解为系统等待空间容量无限 顾客源无限 先到先服务 单个服务的等待制系统 约定 如略去后三项 即指X Y Z FCFS的情形 例如 某排队问题为M M S FCFS 则表示顾客到达间隔时间为负指数分布 泊松流 服务时间为负指数分布 有s s 1 个服务台 系统等待空间容量无限 等待制 顾客源无限 采用先到先服务规则 34 1 3排队模型的分类 Kendall符号的扩充X Y Z A B CM M c 表示输入过程是负指数分布 服务时间服从负指数分布 系统有c个服务台平行服务 0 c 系统容量为无穷 系统是等待制系统 M G 1 表示输入过程是负指数分布 顾客所需的服务时间为独立 服从一般概率分布 系统中只有一个服务台 容量为无穷的等待制系统 GI M 1 表示输入过程是负指数分布 顾客独立到达且相继到达的间隔时间服从一般概率分布 服务时间是相互独立 服从负指数分布 系统中只有一个服务台 容量为无穷的等待制系统 Ek G 1 K表示相继到达的间隔时间独立 服从k阶爱尔朗分布 服务时间为独立 服从一般概率分布 系统中只有一个服务台 容量为K 1 K 的混合制系统 D M c K表示相继到达的间隔时间独立 服从定长分布 服务时间相互独立 服从负指数分布 系统中有c个服务台平行服务 容量为K c K 的混合制系统 35 1 4排队问题的求解 首先需要确定属于哪种排队模型 其中顾客到达的间隔时间分布和服务时间的分布需要实测的数据来确定确定用以判断系统运行优劣的基本数量指标 求出这些数量指标的概率分布或特征数 36 1 4排队问题的求解 用于描述排队系统运行状况的基本数量指标 1 队长 系统中的顾客数 是排队等待的顾客数与正在接受服务的顾客数之和 期望值记作Ls 排队长 队列长 系统中排队等待服务的顾客数 期望值记作Lq 队长和排队长一般都是随机变量 我们希望能确定它们的分布 或至少能确定它们的平均值 即平均队长和平均排队长 及有关的矩 如方差等 队长的分布是顾客和服务员都关心的 特别是对系统设计人员来说 如果能知道队长的分布 就能确定队长超过某个数的概率 从而确定合理的等待空间 37 1 4排队问题的求解 用于描述排队系统运行状况的基本数量指标 2 逗留时间 顾客在系统中的停留时间 从顾客到达时刻起到他接受服务完成止这段时间 期望值记作Ws 是随机变量 也是顾客最关心的指标之一 等待时间 顾客在系统中排队等待的时间 从顾客到达时刻起到他开始接受服务止这段时间 期望值记作Wq 是随机变量 也是顾客最关心的指标 因为顾客通常希望等待时间越短越好 逗留时间 等待时间 服务时间 对这两个指标的研究当然是希望能确定它们的分布 或至少能知道顾客的平均等待时间和平均逗留时间 38 1 4排队问题的求解 用于描述排队系统运行状况的基本数量指标 3 忙期 指从顾客到达空闲服务机构起 到服务机构再次为空闲止的时间长度 即服务机构连续忙的时间 这是个随机变量 是服务员最为关心的指标 因为它关系到服务员的服务强度 闲期 即服务机构连续保持空闲的时间 在排队系统中 忙期和闲期总是交替出现的 其他一些指标 如在损失制或系统容量有限的情况下 由于顾客被拒绝 而使服务系统受到损失的顾客损失率及服务强度等 39 1 4排队问题的求解 系统状态的概率分布系统的状态即指系统中的顾客数 它的可能取值是 1 队长没有限制时 n 0 1 2 2 队长有限制 最大数为N时 n 0 1 2 N 3 即时制且服务台个数为c时 n 0 1 2 c系统处于这些状态的概率一般是随时间t变化的 所以在时刻t 系统状态为n的概率可以用Pn t 表示 40 1 4排队问题的求解 求状态概率Pn t 的方法 建立含Pn t 的关系式 该关系式一般是包含Pn t 的微分差分方程 关于t的微分方程 关于n的差分方程 该方程的解称为瞬态 或称过渡状态 transientstate 解 它的极限称为稳态 steadystate 解 或称统计平衡状态 statisticalequilibriumstate 解 41 1 4排队问题的求解 稳态解的物理意义当系统运行了无限长时间后 初始 t 0 状态的概率分布 Pn 0 n 0 的影响将消失 系统状态的概率分布不再随时间而变化 在实际应用中 大多数系统会很快趋于稳态 而无需等到t 以后 求稳态概率Pn时 不需要求t 时Pn t 的极限 而只需令导数P n t 0即可 42 1 4排队问题的求解 上面给出的这些数量指标一般都是和系统运行的时间有关的随机变量 求这些随机变量的瞬时分布一般是很困难的 为了分析上的简便 并注意到相当一部分排队系统在运行了一定时间后 都会趋于一个平衡状态 或称平稳状态 在平衡状态下 队长的分布 等待时间的分布和忙期的分布都和系统所处的时刻无关 而且系统的初始状态的影响也会消失 因此 本章中将主要讨论与系统所处时刻无关的性质 即统计平衡性质 43 排队论 第1节基本概念第2节到达间隔的分布和服务时间的分布第3节单服务台负指数分布排队系统的分析第4节多服务台负指数分布排队系统的分析第5节一般服务时间M G 1模型第6节经济分析 系统的最优化第7节分析排队系统的随机模拟法 44 2 1到达间隔的分布2 1 1经验分布 定长输入 2 1 2普阿松流 泊松流 2 1 3普阿松流与负指数分布关系2 2服务时间的分布2 2 1经验分布 定长分布 2 2 2负指数分布2 2 3爱尔朗分布 第2节到达间隔的分布和服务时间的分布 45 泊松分布定义设随机变量X所有可能取的值为0 1 2 而取各个值的概率为 k 0 1 2 其中 0是常数 则称X服从参数为 的泊松分布 其均值为 方差为 第2节到达间隔的分布和服务时间的分布 46 若随机变量t取具有概率密度函数为 其中 0为常数 则称t服从参数为 的指数分布 其分布函数F t 为 其均值为 方差为 负指数分布的定义 第2节到达间隔的分布和服务时间的分布 47 如果随机变量T的概率密度是则称T服从负指数分布 它的分布函数是数学期望为方差为标准差为 负指数分布的定义 第2节到达间隔的分布和服务时间的分布 48 2 1 1经验分布 例1大连港大港区1979年载货500吨以上船舶到达 不包括定期到达的船舶 逐日记录见书上表12 2 将表12 2整理成船舶到达数的分布表 可以计算出 平均到达率 到达总数 总天数 1271 365 3 48 艘 天 49 2 1 1经验分布 以 i表示第i号顾客到达的时刻 以si表示对它的服务时间 这样可算出相继到达的间隔时间ti ti i 1 i 和排队等待时间wi 它们的关系如下 实际中测定相继到达时间间隔的方法 相继到达时间间隔等待时间 50 2 1 1经验分布 通过一个例题来说明原始资料的整理 例2某服务机构是单服务台 先到先服务 对41个顾客记录到达时刻 和服务时间s 单位为分钟 如表12 4 在表中以第1号顾客到达时刻为0 对所有顾客的全部服务时间为127分钟 将原始记录整理成下表 51 2 1 1经验分布 52 2 1 1经验分布 53 2 1 1经验分布 例2某服务机构是单服务台 先到先服务 对41个顾客记录到达时刻 和服务时间s 单位为分钟 如表12 4 在表中以第1号顾客到达时刻为0 对所有顾客的全部服务时间为127分钟 将原始记录整理成下表 54 2 1 1经验分布 例2平均间隔时间 142 40 3 55 分钟 人 平均到达率 41 142 0 28 人 分钟 平均服务时间 127 41 3 12 分钟 人 平均服务率 41 127 0 32 人 分钟 55 普阿松流 又称为泊松流 Poisson过程 最简单流 是排队论中一种常用来描述顾客到达规律的特殊的随机过程 2 1 2普阿松流 泊松流 56 2 1 2普阿松流 泊松流 设表示在时间区间内到达的顾客数令表示在时间区间内有个顾客到达的概率 即当满足下列三个条件时 我们说顾客的到达形成泊松流 1 在不相重叠的时间区间内顾客到达数是相互独立的 即无后效性 通俗地说就是以前到达的顾客情况 对以后顾客的到来没有影响 否则就是关联的 2 平稳性 又称作输入过程是平稳的 对充分小的 在时间区间内有1个顾客到达的概率与t无关 而与区间长度成正比 即其中 当时 是关于的高阶无穷小 进一步地 在长度为t的时段内恰好到达k个顾客的概率仅与时段长度有关 而与时段起点无关 即对任意 0 在 t 或 0 t 内恰好到达k个顾客的概率相等 3 单个性又称普通性 对于充分小的 在时间区间内有2个或2个以上顾客到达的概率极小 以至于可以忽略 即 57 当顾客到达为泊松流时 研究顾客到达数n的概率分布 由条件 2 总可以取时间由0算起 并简记由条件 2 和 3 容易推得在区间内没有顾客到达的概率将区间分成两个互不重叠的区间和 则到达总数n分别出现在这两个区间和上 有下列 A B C 三种情况 2 1 2普阿松流 泊松流 58 2 1 2普阿松流 泊松流 在内到达n个顾客应是表中 A B C 三种互不相容的情况之一 所以概率应是表中三个概率之和 各合为一项 令 得下列方程 并注意到初始条件 则有当n 0时 没有 B C 两种情况 所以得 59 解 12 5 式和 12 6 式 得表示长为t的时间区间内到达n个顾客 即N t n 的概率 由 12 7 式得随机变量服从泊松分布 结论 当顾客到达为泊松流时 在长度为t的时间内到达n个顾客的概率Pn t 服从泊松分布 它的数学期望和方差分别是 2 1 2普阿松流 泊松流 相等 特别地 t 1时 E N 1 因此 表示单位时间平均到达的顾客数 60 我们再来研究两个顾客先后到达的时间间隔T的概率分布 61 当输入过程是泊松流时 由于在单位时间里到达的顾客数是随机变量 那么对应的 前后两个顾客到达的时间间隔也就是随机变量了 即有的时间间隔长一些 有的时间隔又短一些 设T的分布函数为FT t 则这个概率也就是在 0 t 区间内至少有一个顾客到达的概率 2 1 3普阿松流与负指数分布关系 62 泊松过程的顾客到达时间间隔分布顾客到达的时间间隔小于t的概率 即t内有顾客的概率分布 两相邻顾客到达的时间间隔是一连续型随机变量 用T表示 在t时间内没有顾客到达的概率为 2 1 3普阿松流与负指数分布关系 63 在区间内至少有1个顾客到达的概率是即顾客相继到达的间隔时间T必然服从负指数分布 其概率密度函数 则T的分布函数为 数学期望为 表示单位时间内顾客平均到达数 1 表示顾客到达的平均间隔时间 2 1 3普阿松流与负指数分布关系 64 顾客相继到达的间隔时间独立且为同负指数分布 密度函数为 与输入过程为泊松流 参数为 是等价的 对于泊松流 表示单位时间平均到达的顾客数 1 表示相继顾客到达平均间隔时间 相继到达时间间隔为负指数分布与到达为泊松流的等价性 上述内容还可以用如下表达 对于泊松流 其相继顾客到达时间间隔 i i 1 2 是相互独立同分布的 其分布函数为负指数分布 2 1 3普阿松流与负指数分布关系 65 当输入过程是泊松流时 那么顾客相继到达的间隔时间T 注意T是随机变量 必然服从负指数分布 2 1 3普阿松流与负指数分布关系 66 负指数分布的性质由条件概率公式容易证明该性质称为无记忆性或马尔柯夫性 若T表示排队系统中顾客相继到达的间隔时间 该性质说明 一个顾客到来所需的时间与过去一个顾客到来所需时间s无关 也就是说该顾客是随机地到达 2 1 3普阿松流与负指数分布关系 67 例 有易碎物品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件的概率 68 破碎物品少于3件的概率为91 97 破碎物品多于3件的概率为 3 至少有一件破碎的概率为P k 1 1 1k k e 1 10 0 e 1 0 632 69 2 1到达间隔的分布2 1 1经验分布 定长输入 2 1 2普阿松流 泊松流 2 1 3普阿松流与负指数分布关系2 2服务时间的分布2 2 1经验分布 定长分布 2 2 2负指数分布2 2 3爱尔朗分布 第2节到达间隔的分布和服务时间的分布 70 每一个顾客的服务时间都是常数 此时服务时间t的分布函数为 2 2 1服务时间的定长分布 71 服务时间v的分布对顾客的服务时间 也就是在忙期相继离开系统的两顾客的间隔时间 有时也服从负指数分布 设它的分布函数和密度分别是其中 表示对顾客的平均服务时间 表示单位时间能被服务完成的顾客数 称为平均服务率 2 2 2服务时间的负指数分布 72 是指相继顾客到达时间间隔T相互独立 其分布密度为其中 k为非负整数 爱尔朗分布 2 2 3服务时间的爱尔朗分布 73 设是k个相互独立的随机变量 服从相同参数的负指数分布 那么的概率密度是称T服从k阶爱尔朗分布 其均值和方差分别为 可以证明如下结论 2 2 3服务时间的爱尔朗分布 74 爱尔朗分布的意义当k 1时 爱尔朗分布化为负指数分布 可看成是一种完全随机的分布 当k增大时 爱尔朗分布的图形逐渐变为对称的 当k 30时爱尔朗分布近似于正态分布 k 时 Var T 0 这时爱尔朗分布化为确定型分布 一般k阶爱尔朗分布可看成完全随机与完全确定的中间型 能对现实世界提供更为广泛的适应性 2 2 3服务时间的爱尔朗分布 75 可以证明 在参数为 的泊松输人中 对任意的j与k 设第j与第j k个顾客之间的到达间隔为 则随机变量Tk的分布必遵从参数为 的爱尔朗分布 其分布密度为 1 k 表示一个顾客的一个服务台的平均服务时间 2 2 3服务时间的爱尔朗分布 76 例如 某排队系统有并联的k个服务台 顾客流为泊松流 规定第i K i 2K i 个顾客排入第i号台 i 1 2 K 则第K台所获得的顾客流 即为爱尔朗输入流 其他各台 从它的第一个顾客到达以后开始所获得的流也为爱尔朗输入流 例如 串联的k个服务台 每台服务时间相互独立 服从相同的负指数分布 参数k 那么一顾客走完k个服务台总共所需要服务时间就服从k阶Erlang分布 2 2 3服务时间的爱尔朗分布 77 第1节基本概念第2节到达间隔的分布和服务时间的分布第3节单服务台负指数分布排队系统的分析第4节多服务台负指数分布排队系统的分析第5节一般服务时间M G 1模型第6节经济分析 系统的最优化第7节分析排队系统的随机模拟法 排队论 78 排队论 排队论研究的首要问题是排队系统主要数量指标的概率规律 即研究系统的整体性质 然后进一步研究系统的优化问题 与这两个问题相关的还包括排队系统的统计推断问题 1 通过研究主要数量指标在瞬时或平稳状态下的概率分布及其数字特征 了解系统运行的基本特征 2 统计推断问题 建立适当的排队模型是排队论研究的第一步 建立模型过程中经常会碰到如下问题 检验系统是否达到平稳状态 检验顾客相继到达时间间隔的相互独立性 确定服务时间的分布及有关参数等 79 3 系统优化问题 又称为系统控制问题或系统运营问题 其基本目的是使系统处于最优或最合理的状态 系统优化问题包括最优设计问题和最优运营问题 其内容很多 有最少费用问题 服务率的控制问题 服务台的开关策略 顾客 或服务 根据优先权的最优排序等方面的问题 对于一般的排队系统运行情况的分析 通常是在给定输入与服务条件下 通过求解系统状态为n 有n个顾客 的概率Pn t 再进行计算其主要的运行指标 排队论 80 系统中顾客数 队长 的期望值L或Ls 排队等待的顾客数 排队长 的期望值Lq 顾客在系统中全部时间 逗留时间 的期望值W或Ws 顾客排队等待时间的期望值Wq 排队系统中 由于顾客到达分布和服务时间分布是多种多样的 加之服务台数 顾客源有限无限 排队容量有限无限等的不同组合 就会有不胜枚举的不同排队模型 若对所有排队模型都进行分析与计算 不但十分繁杂而且也没有必要 下面拟分析几种常见排队系统模型 排队论 81 3 1标准的M M 1模型 M M 1 3 2系统容量有限的情况 M M 1 N 3 3顾客源有限的情形 M M 1 m 第3节单服务台负指数分布排队系统的分析 本节讨论输入过程服从普阿松分布过程 服务时间服从负指数分布单服务台的排队系统 82 标准的M M 1模型 1 输入过程 顾客源是无限的 顾客单个到来 相互独立 一定时间内的到达数服从泊松分布 到达过程是平稳的 2 排队规则 单队 且对队长没有限制 先到先服务 3 服务机构 单服务台 各顾客的服务时间相互独立 服从相同的负指数分布 此外 还假定到达间隔时间和服务时间是相互独立的 3 1标准的M M 1模型 M M 1 即已知条件 顾客进入系统的平均速度 单位时间到达的顾客数 顾客离开系统的平均速度 单位时间能被服务完成的顾客数 83 首先要求出 系统在任意时刻t的状态为n 即系统中有n个顾客 的概率 它决定了系统运行的特征 现仍然通过研究区间 t t t 的变化来求解 在时刻t t 系统中有n个顾客不外乎有下列四种情况 t t t 内到达或离开2个以上没列入 3 1标准的M M 1模型 M M 1 84 因已知到达规律服从参数为的泊松过程 服务时间服从参数为的负指数分布 所以在时间区间内分为 1 有1个顾客到达的概率为没有顾客到达的概率就是 2 当有顾客在接受服务时 1个顾客被服务完了 离去 的概率是 没有离去的概率就是 3 多于一个顾客的到达或离去的概率是 可以忽略 3 1标准的M M 1模型 M M 1 85 3 1标准的M M 1模型 M M 1 在时刻 系统中有n个顾客 n 0 存在下列四种情况 到达或离去是2个以上的没列入 表示发生 1个 表示没有发生 86 87 这四种情况是互不相容的 所以应是这四项之和 即即令 得关于的微分差分方程 3 1标准的M M 1模型 M M 1 所有的高阶无穷小和并 88 当 则只有上表中 A B 情况 因为在较小的 t内不可能发生 D 到达后即离去 若发生可将 t取小即可 且式 A 中无离去的概率为1 即同理求得 它们的概率分别是情况 A 情况 B 情况 C 情况 D 3 1标准的M M 1模型 M M 1 89 研究稳态的情况 这时与时间t无关 可写成 它的导数为0 由 12 15 式和 12 16 式可得这是关于的差分方程 它表明了各状态间的转移关系 状态0转移到状态1的转移率为 状态1转移到状态0的转移率为 3 1标准的M M 1模型 M M 1 这种系统状态 n 随时间变化的过程就是生灭过程 BirthandDeathProcess 方程 12 15 12 16 解是瞬态解 无法应用 90 3 1标准的M M 1模型 M M 1 对状态0必须满足以下平衡方程同样对任何的状态 可得如 12 18 所示的平衡方程 由 12 17 式可得将它代入 12 18 式 令 得到同理依次推得今设 否则队列将排至无限远 又由概率的性质知即 得到 91 对 的实际意义的解释 是平均到达率与平均服务率之比 即在相同时区内顾客到达的平均数与被服务的平均数之比 若将 表示为 1 1 它是一个顾客的服务时间与到达间隔时间之比 称 为服务强度 trafficintensity 或话务强度 由 12 19 式可知 1 P0 它刻画了服务机构的繁忙程度 所以 又称为服务机构的利用率 3 1标准的M M 1模型 M M 1 系统处于空闲状态的概率 系统处于繁忙状态的概率 92 3 1标准的M M 1模型 M M 1 根据平稳分布 求排队系统的有关运行指标 1 系统中的平均顾客数 平均队长 或 2 在队列中等待的平均顾客数 期望 93 顾客在系统中的逗留时间W 为一个随机变量 在M M 1情形下 服从参数为 的负指数分布 即分布函数概率密度 于是 得到 3 在系统中顾客逗留时间的期望值 4 在队列中顾客等待时间的期望值 3 1标准的M M 1模型 M M 1 平均逗留时间减去平均服务时间 94 将以上结果归纳如下 它们的相互关系如下 上式称为Little公式 3 1标准的M M 1模型 M M 1 95 3 1标准的M M 1模型 M M 1 Ls Lq Ws Wq之间的关系 几何解释 稳态时 一个顾客 进入系统后 每单位时间 平均到达 顾客 逗留时间的期望值Ws 队长Ls由时间段内个 组成的 Ls Ws 同理 Lq WqWs Wq 1 Ws与Wq只相差一段平均服务时间1 96 泊松输入 负指数分布服务的排队系统的一般决策过程 根据已知条件绘制状态转移速度图 依据状态转移速度图写出各稳态概率之间的关系 求出P0及Pn 计算各项数量运行指标 用系统运行指标构造目标函数 对系统进行优化 3 1标准的M M 1模型 M M 1 97 例3某医院手术室根据病人来诊和完成手术时间的记录 任意抽查了100个工作小时 每小时来就诊的病人数n的出现次数如下表所示 又任意抽查了100个完成手术的病历 所用时间v 单位 小时 出现的次数如下表所示 3 1标准的M M 1模型 M M 1 98 1 每小时病人平均到达率 人 小时 每次手术平均时间 小时 人 每小时完成手术人数 平均服务率 人 小时 2 取 可以通过统计检验的方法 认为病人到达数服从参数为2 1的泊松分布 手术时间服从参数为2 5的负指数分布 3 说明服务机构 手术室 有84 的时间是繁忙的 有16 的时间是空闲的 4 依次代入 12 21 式 算出各指标 在病房中病人数 期望值 人 排队等待病人数 期望值 人 病人在病房中逗留时间 期望值 小时 病人排队等待时间 期望值 小时 3 1标准的M M 1模型 M M 1 99 例2 某修理店只有一位修理工 来修理的顾客到达过程为Poisson流 平均每小时4人 修理时间服从负指数分布 平均需要6分钟 试求 修理店空闲的概率 店内恰有3位顾客的概率 店内至少有一位顾客的概率 在店内平均顾客数 每位在店内平均逗留时间 等待服务的平均顾客数 每位顾客平均等待服务时间 顾客在店内等待时间超过10分钟的概率 3 1标准的M M 1模型 M M 1 100 解 本例可看成一个M M 1 排队问题 其中 4 1 0 1 10 人 小时 2 5 1修理店内空闲的概率P0 1 1 2 5 0 6店内恰有3个顾客的概率P3 3 1 2 5 3 1 2 5 0 038 3 1标准的M M 1模型 M M 1 101 店内至少有1位顾客的概率P N 1 1 P0 1 1 2 5 0 4在店内平均顾客数L 1 2 5 1 2 5 0 67 人 每位顾客在店内平均逗留时间W L 0 67 4 10分钟 3 1标准的M M 1模型 M M 1 102 等待服务的平均顾客数Lq L 0 67 2 5 0 27 人 每个顾客平均等待服务时间Wq Lq 0 27 4 0 0675小时 4分钟 3 1标准的M M 1模型 M M 1 103 顾客在店内等待时间超过10分钟的概率P T t 1 F w e tt 10分钟 10人 小时 10 60 1 6 4人 小时 4 60 1 15P T 10 e 10 1 6 1 15 e 1 0 3677 3 1标准的M M 1模型 M M 1 104 例1 考虑一个铁路列车编组站 设待编列车到达时间间隔服从负指数分布 平均每小时到达2列 服务台是编组站 编组时间服从负指数分布 平均每20分钟可编一组 已知编组站上共有2股道 当均被占用时 不能接车 再来的列车只能停在站外或前方站 求在平衡状态下系统中列车的平均数 每一列车的平均逗留时间 等待编组的列车平均数 如果列车因站中2股道均被占用而停在站外或前方站时 每列车每小时费用为a元 求每天由于列车在站外等待而造成的损失 3 1标准的M M 1模型 M M 1 105 解 本例可看成一个M M 1 排队问题 其中 2 3 2 3 1系统中列车的平均数L 1 2 3 1 2 3 2 列 列车在系统中的平均停留时间W L 2 2 1 小时 系统中等待编组的列车平均数Lq L 2 2 3 4 3 列 列车在系统中的平均等待编组时间Wq Lq 4 3 1 2 2 3 小时 3 1标准的M M 1模型 M M 1 106 记列车平均延误 由于站内2股道均被占用而不能进站 时间为W0则W0 WP N 2 W 1 P0 P1 P2 W 1 l l 1 l 2 1 3 3 2 3 3 0 296 小时 故每天列车由于等待而支出的平均费用E 24 W0a 24 2 0 296 a 14 2a元 3 1标准的M M 1模型 M M 1 107 如果系统的最大容量为N 对于单服务台的情形 排队等待的顾客最多为N 1 在某时刻一顾客到达时 如系统中已有N个顾客 那么这个顾客就被拒绝进入系统 当N 1时为即时制的情形 当N 时为容量无限制的情形 3 2系统的容量有限制的情况 M M 1 N 108 泊松输入 负指数分布服务的排队系统的一般决策过程 根据已知条件绘制状态转移速度图 依据状态转移速度图写出各稳态概率之间的关系 求出P0及Pn 计算各项数量运行指标 用系统运行指标构造目标函数 对系统进行优化 3 2系统的容量有限制的情况 M M 1 N 109 3 2系统的容量有限制的情况 M M 1 N 稳态情形下各状态间概率强度的转换关系图状态概率的稳态方程 110 3 2系统的容量有限制的情况 M M 1 N 稳态情形下各状态间概率强度的转换关系图状态概率的稳态方程其中 12 23b 也可写成 则有 111 3 2系统的容量有限制的情况 M M 1 N 由 N则 nP0 1n 0 N即P0 1 n n 0 1 1 N 1 1 N 1 112 M M 1 N 排队系统的各项指标 1 队长 期望值 2 队列长 期望值 3 顾客逗留时间 期望值 4 顾客等待时间 期望值 5 有效到达率 3 2系统的容量有限制的情况 M M 1 N 令 得到 113 1 平均队长Ls 1 试证 1时 Ls N 2 3 2系统的容量有限制的情况 M M 1 N 114 M M 1 N 排队系统的各项指标 1 队长 期望值 2 队列长 期望值 3 顾客逗留时间 期望值 4 顾客等待时间 期望值 5 有效到达率 3 2系统的容量有限制的情况 M M 1 N 令 得到 115 5 有效到达率 e系统容量有限 当满员 n N 时 顾客将被拒绝 实际的顾客到达率与 不一样 此种情况的公式与前类似 只有Ls不同 e与 不同 求 e必须先求得P0或PN才行 可以证明 3 2系统的容量有限制的情况 M M 1 N 116 M M 1 N 排队系统各项指标的归纳 当时 3 2系统的容量有限制的情况 M M 1 N 117 例2 某单人理发馆共有六把椅子接待顾客排队 无座时将离去 顾客平均到达率为3人 h 理发时间平均为15分钟 求 1 求某一顾客到达就能理发的概率 2 求需要等待的顾客数的期望值 3 求有效到达率 4 求一顾客在系统中的逗留时间和排队时间平均值 5 在可能到来的顾客中 有百分之几不等待就离开 3 2系统的容量有限制的情况 M M 1 N 118 1 求某一顾客到达就能理发的概率 2 求需要等待的顾客数的期望值 3 求有效到达率 4 求一顾客在系统中的逗留时间和排队时间平均值 3 2系统的容量有限制的情况 M M 1 N 119 5 在可能到来的顾客中 有百分之几不等待就离开 顾客为何不等待就离去 因为系统已经满员 3 2系统的容量有限制的情况 M M 1 N 故拒绝的概率为3 71 120 例4某单人理发馆为等待的顾客准备了6把椅子 当6把椅子都坐满时 再来的顾客将不进店而离开 顾客的平均到达率为3人 小时 理发平均需要15分钟 则系统的容量为N 6 1 7 人 小时 人 小时 1 某顾客一到达就能理发的概率 2 需要等待的顾客数的期望值 3 有效到达率 人 小时 4 一顾客在理发馆内逗留的期望时间 小时 分钟 3 2系统的容量有限制的情况 M M 1 N 121 5 在可能到来的顾客中不等待就离开的概率这也是理发馆的损失率 以本例为例 比较队长为有限和无限的情形 3 2系统的容量有限制的情况 M M 1 N 122 背景设有m台机器 顾客总体 机器因故障停机表示 到达 待修的机器形成队列 修理工人是服务员 本节讨论单服务员的情形 顾客总体虽只有m个 但每个顾客到来并经过服务后 仍回到原来总体 所以仍然可以再到来 如在机器故障问题中 同一台机器出了故障 到来 并经修好 服务完了 仍可再出故障 形成循环 模型符号中的 表示对系统的容量没有限制 但实际上它不会超过m 所以可写成 M M 1 m m 3 3顾客源为有限的情形 M M 1 m 123 泊松输入 负指数分布服务的排队系统的一般决策过程 根据已知条件绘制状态转移速度图 依据状态转移速度图写出各稳态概率之间的关系 求出P0及Pn 计算各项数量运行指标 用系统运行指标构造目标函数 对系统进行优化 124 设每个顾客的到达率相同 均为 这里 的含义是单台机器在单位时间里发生故障的概率或平均次数 设系统内顾客数为Ls 则系统外的顾客平均数为m Ls 所以系统的有效到达率为 e m Ls 12 26 考虑稳态情况下状态间的转移率由状态0转移到状态1 每台设备由正常状态转移为故障状态的转移率为 P0 m台设备由无故障状态转移为有一台设备 不论哪一台 发生故障的转移率为m P0 由状态1转移到状态0 其状态转移率为 P1 所以 状态0时有平衡方程为 m P0 P1 3 3顾客源为有限的情形 M M 1 m 125 各状态间的转移差分方程解得 注意到因而不要求 系统的各项指标为 3 3顾客源为有限的情形 M M 1 m 126 例5某车间有5台机器 每台机器的连续运转时间服从负指数分布 平均连续运转时间15分钟 有一个修理工 每次修理时间服从负指数分布 平均每次12分钟 求 1 修理工空闲的概率 2 五台机器都出故障的概率 3 出故障的平均台数 4 等待修理的平均台数 5 平均停工时间 6 平均等待修理时间 7 评价这些结果 3 3顾客源为有限的情形 M M 1 m 127 解 1 2 五台机器都出现故障的概率 3 出故障的平均台数 台 4 等待修理的平均台数 台 5 平均停工时间 分钟 6 平均等待修理时间 分钟 7 机器停工时间过长 修理工几乎没有空闲时间 应当提高服务率减少修理时间或增加修理工人 3 3顾客源为有限的情形 M M 1 m 128 第1节基本概念第2节到达间隔的分布和服务时间的分布第3节单服务台负指数分布排队系统的分析第4节多服务台负指数分布排队系统的分析第5节一般服务时间M G 1模型第6节经济分析 系统的最优化第7节分析排队系统的随机模拟法 排队论 129 本节讨论单队 并列的多服务台 服务台数为c 的情形 4 1标准的M M c模型4 2M M c型系统和c个M M 1型系统的比较4 3系统容量有限的情形 M M c N 4 4顾客源有限的情形 M M c m 第4节多服务台负指数分布排队系统的分析 130 4 1标准的M M c模型 标准的M M c模型各种特征的规定与标准的M M 1模型的规定相同 各服务台工作是相互独立的 不搞协作 且