排队论简述 PPT课件

排队论 专注于医疗领域专业于流程优化 ValuMetrix 1 一 简介 排队论 QueuingTheory 是研究系统随机聚散现象和随机服务系统工作过程的数学理论和方法 又叫随机服务系统理论 是数学运筹学的分支学科 它是研究服务系统中排队现象随机规律的学科 排队论研究的内容有3个方面 性态问题 即研究各种排队系统的概率规律性 主要是研究队长分布 等待时间分布和忙期分布等 包括了瞬态和稳态两种情形 最优化问题 又分静态最优和动态最优 前者指最优设计 后者指现有排队系统的最优运营 排队系统的统计推断 即判断一个给定的排队系统符合于哪种模型 以便根据排队理论进行分析研究 2 二 排队系统模型的基本组成部分 排队现象是由两个方面构成 一方要求得到服务 另一方设法给予服务 我们把要求得到服务的人或物 设备 统称为顾客 给予服务的服务人员或服务机构统称为服务员或服务台 顾客与服务台就构成一个排队系统 或称为随机服务系统 显然缺少顾客或服务台任何一方都不会形成排队系统 对于任何一个排队服务系统 每一名顾客通过排队服务系统总要经过如下过程 顾客到达 排队等待 接受服务和离去 其过程如下图所示 3 三 排队服务系统的基本概念 1 输入过程输入过程考察的是顾客到达服务系统的规律 有限 无限 单独 成批 是否独立 是否平稳 2 排队规则损失制等待制混合制 队长有限 等待时间有限 逗留时间有限 3 服务机构单台 多台 串联 并联服务时间服从什么样的概率分布 每个顾客所需的服务时间是否相互独立 是成批服务或是单个服务等 4 四 排队系统的描述符号与模型分类 D G Kendall在1953提出了分类法 称为Kendall记号 适用于并列服务台 即 X Y Z X 顾客相继到达的间隔时间分布Y 服务时间的分布Z 并列的服务台数各记号的含义 M 负指数分布MarkovD 确定型分布DeterministicEk K阶爱尔朗分布ErlangGI 一般相互独立随机分布 GeneralIndependent G 一般随机分布 5 四 排队系统的描述符号与模型分类 在1971年的一次国际会议上 将Kendall记号扩充为 X Y Z A B C 其中前三项意义不变 后三项为A 排队系统的最大容量B 顾客源数量C 排队规则并约定 如略去后三项 即指X Y Z FCFS M M 1 FCFS 可简写为M M 1 指顾客到达为泊松过程 服务时间为负指数分布 单台 无限容量 无限源 先到先服务的排队系统模型 6 五 描述排队系统的主要数量指标 求解一般排队系统问题的目的主要是通过研究排队系统运行的效率指标 估计服务质量 确定系统的合理结构和系统参数的合理值 以便实现对现有系统合理改进和对新建系统的最优设计等 排队问题的一般步骤 1 确定或拟合排队系统顾客到达的时间间隔分布和服务时间分布 2 研究分析排队系统理论分布的概率特征 3 研究系统状态及其概率 系统状态N t 是指排队系统在时刻t的全部顾客数 一般N t 是随机的 系统状态概率瞬态概率用Pn t 表示 表示时刻系统状态N t n的概率 稳态概率用Pn表示 一般系统运行了一定长时间后 系统状态的概率分布不再随时间t变化 7 五 描述排队系统的主要数量指标 4 根据排队系统对应的理论模型求用以判断系统运行优劣的基本数量指标的概率分布或特征数 平均队长 Ls 指系统内顾客数 包括正被服务的顾客与排队等待服务的顾客 的数学期望 平均队列长 Lq 指系统内等待服务的顾客数的数学期望 平均逗留时间 Ws 顾客在系统内逗留时间 包括排队等待的时间和接受服务的时间 的数学期望平均等待时间 Wq 指一个顾客在排队系统中排队等待时间的数学期望间忙期 Tb 指服务机构连续繁忙时间 顾客到达空闲服务机构起 到服务机构再次空闲止的时间 长度的数学期望 8 六 Little 利特尔 公式 用 表示单位时间内顾客到达的平均数 表示单位时间内被服务完毕离去的平均顾客数 因此1 表示相邻两顾客到达的平均时间 1 表示对每个顾客的平均服务时间 J D C Little给出了如下公式 10 七 M M 1等待制排队模型 单服务台等待制模型M M 1 是指 顾客的相继到达时间服从参数为 的负指数分布 服务台个数为1 服务时间服从参数为 的负指数分布 系统空间无限 允许无限排队 这是一类最简单的排队系统 系统达到平衡状态后 是系统中至少有一个顾客的概率 也就是服务台处于忙的状态的概率 因而也称 为服务强度 它反映了系统繁忙的程度 服务强度 的计算方法 即要求顾客的平均到达率小于系统的平均服务率 才能使系统达到统计平衡 11 七 M M 1等待制排队模型 上面四个公式用于M M 1型排队制的计算 12 八 M M S等待制排队模型 某售票处有3个窗口 顾客的到达为Poisson流 平均到达率为 0 9人 min 服务 售票 时间服从负指数分布 平均服务率 0 4人 min 现设顾客到达后排成一个队列 依次向空闲的窗口购票 这一排队系统可看成是一个M M S 系统 在本例中 如果顾客的排队方式变为到达售票处后可到任一窗口前排队 且入队后不再换队 即可形成3个队列 这时 原来的M M 3 系统实际上变成了由3个M M 1 子系统组成的排队系统 且每个系统的平均到达率为 13 八 M M S等待制排队模型 下表给出了M M 3 和3个M M 1 的比较 14 八 M M S等待制排队模型 不难看出一个M M 3