排队论简述.ppt

排队论
专注于医疗领域
专业于流程优化
ValuMetrix
一、简介
排队论(Queuing Theory),是研究系统随机聚散现象和随机服务系统工作过程的数学理论和方法,又叫随机服务系统理论,是数学运筹学的分支学科。它是研究服务系统中排队现象随机规律的学科。
排队论研究的内容有3个方面:
性态问题,即研究各种排队系统的概率规律性,主要是研究队长分布、等待时间分布和忙期分布等,包括了瞬态和稳态两种情形。
最优化问题,又分静态最优和动态最优,前者指最优设计,后者指现有排队系统的最优运营。
排队系统的统计推断,即判断一个给定的排队系统符合于哪种模型,以便根据排队理论进行分析研究。
二、排队系统模型的基本组成部分
排队现象是由两个方面构成,一方要求得到服务,另一方设法给予服务。我们把要求得到服务的人或物(设备)统称为顾客,给予服务的服务人员或服务机构统称为服务员或服务台。顾客与服务台就构成一个排队系统,或称为随机服务系统。显然缺少顾客或服务台任何一方都不会形成排队系统。
对于任何一个排队服务系统,每一名顾客通过排队服务系统总要经过如下过程:顾客到达、排队等待、接受服务和离去,其过程如下图所示:
顾客总体
队伍
输出
输入
服务台
服务系统
三、排队服务系统的基本概念
1、输入过程
输入过程考察的是顾客到达服务系统的规律。(有限/无限,单独/成批,是否独立,是否平稳)
2、排队规则
损失制
等待制
混合制(队长有限、等待时间有限、逗留时间有限)
3、服务机构
单台/多台、串联/并联
服务时间服从什么样的概率分布,每个顾客所需的服务时间是否相互独立,是成批服务或是单个服务等。
四、排队系统的描述符号与模型分类
,称为Kendall记号(适用于并列服务台)即:X/Y/Z,
X-顾客相继到达的间隔时间分布
Y-服务时间的分布
Z-并列的服务台数
各记号的含义:
M-负指数分布Markov
D-确定型分布Deterministic
Ek-K阶爱尔朗分布Erlang
GI-一般相互独立随机分布(General Independent)
G-一般随机分布,
四、排队系统的描述符号与模型分类
在1971年的一次号扩充为:X/Y/Z/A/B/C。其中前三项意义不变,后三项为
A-排队系统的最大容量
B-顾客源数量
C-排队规则
并约定,如略去后三项,即指 X/Y/Z/∞/∞/FCFS。M/M/1/∞/∞/FCFS,可简写为M/M/1,指顾客到达为泊松过程,服务时间为负指数分布,单台,无限容量,无限源,先到先服务的排队系统模型。
五、描述排队系统的主要数量指标
求解一般排队系统问题的目的主要是通过研究排队系统运行的效率指标,估计服务质量,确定系统的合理结构和系统参数的合理值,以便实现对现有系统合理改进和对新建系统的最优设计等。
排队问题的一般步骤:
1. 确定或拟合排队系统顾客到达的时间间隔分布和服务时间分布。
2. 研究分析排队系统理论分布的概率特征。
3. 研究系统状态及其概率。系统状态N(t)是指排队系统在时刻t的全部顾客数(一般N(t)是随机的)。系统状态概率瞬态概率用Pn(t)表示,表示时刻系统状态N(t)=n的概率;稳态概率用Pn表示(一般系统运行了一定长时间后,系统状态的概率分布不再随时间t变化)
五、描述排队系统的主要数量指标
。
平均队长(Ls):指系统内顾客数(包括正被服务的顾客与排队等待服务的顾客)的数学期望。
平均队列长(Lq):指系统内等待服务的顾客数的数学期望。
平均逗留时间(Ws):顾客在系统内逗留时间(包括排队等待的时间和接受服务的时间)的数学期望
平均等待时间(Wq):指一个顾客在排队系统中排队等待时间的数学期望间
忙期(Tb):指服务机构连续繁忙时间(顾客到达空闲服务机构起,到服务机构再次空闲止的时间)长度的数学期望
六、Little(利特尔)公式
用λ表示单位时间内顾客到达的平均数,μ表示单位时间内被服务完毕离去的平均顾客数,因此1/λ表示相邻两顾客到达的平均时间,1/μ表示对每个顾客的平均服务时间.
:
七、M/M/1等待制排队模型
单服务台等待制模型M/M/1/∞是指:顾客的相继到达时间服从参数为λ的负指数分布,服务台个数为1,服务时间服从参数为μ的负指数分布,系统空间无限,允许无限排队,这是一类最简单的排队系统。
系统达到平衡状态后
ρ是系统中至少有一个顾客的概率,也就是服务台处于忙的状态的概率,因而也称ρ为服务强度,它反映了系统繁忙的程度,服务强度ρ的计