《排队模型(掌握mmmmcmm1k).ppt》由会员分享,可在线阅读,更多相关《排队模型(掌握mmmmcmm1k).ppt(45页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、排队模型,凯里学院 余英,模型要点,1、掌握排队模型的基本概念 2、了解常见的分布函数及生灭过程 3、掌握典型排队系统模型的结构及应用,排队模型的基本概念,1、什么是排队模型(排队论)?,排队论是研究拥挤现象的一门学科。 它是在研究各种排队系统概率规律性的基础上,解决有关排队系统的最优化设计(静态)和最优控制(动态)问题。,一、引言,现实生活中的排队系统,2、排队论的起源与应用领域,1)、20世纪初Bell电话公司为减少用户呼叫, 研究电话线路合理配置问题;,2)、1909年丹麦工程师A.K.Erlang受热力学统计平衡概念启发发表论文概率论与电话交换,解决上述问题;,3)、应用于:通讯系统、
2、交通运输、机器维修、库存控制、计算几设计等领域。,二、排队系统的特征及其组成,1、排队系统的特征即拥挤现象的共性 1)、有请求服务的人或物 2)、有为顾客服务的人或物 3)、具有随机性 4)、服务的数量超过服务机构的容量,2、排队系统的三大基本组成部分,1)、输入过程(顾客到达的方式) a、顾客的总体(顾客源)的组成可能是有限的,也可能是无限的; b、顾客相继到达的时间间隔可以是确定的,也可以是随机的,对于随机的情形,要知道单位时间内的顾客到达数或相继到达的间隔时间的概率分布; c 、输入过程可以是平稳的(描述相继到达的间隔时间分布和所含参数(如期望值、方差等)都是与时间无关的),否则成为非平
3、稳的,我们研究平稳的。,2、排队系统的三大基本组成部分,2)、排队规则 a、顾客到达时,如所有服务台都被占用,在这种情形下,顾客可以随即离去,也可以排队等待,前者成为损失制,后者成为等待制,我们研究后者;其次还有混合制,它是介于等待制和损失制之间的; b、从占有的空间来看,有的系统要规定容量(即允许进入排队系统的顾客数)的最大限,有的没有这种限制,2、排队系统的三大基本组成部分,3)、服务过程 a、可以是没有服务员,单个的,多个的,对于多个的,它们之间可以是平行排列(并列)的,也可以是前后排列(串列)的,也可以是混合的; b、服务时间可以是确定的,也可以是随机的,对于后者要知道它的概率分布;
4、c、服务时间可以是平稳的,也可以是非平稳的,我们研究前者; d、对于等待制,服务规则又可以分为先到先服务(FCFS),后到先服务(LCFS),随机服务和有优先权的服务。,三、排队模型的分类(符号表示),我们采用Kendall记号 顾客相继到达时间间隔分布/服务时间分布/服务台数目/排队系统允许的最大顾客容量(系统容量)/顾客总体数量(顾客源数量)/排队规则,说明:如果Kendall记号中略去后3项,表示x/y/z/FCFS,相继到达时间间隔和服务时间分布的符号如下: M负指数分布 D确定型 Ekk阶爱尔朗分布 GI一般相互独立的时间间隔分布 G一般服务时间分布,四、排队模型的数量指标,1、平均
5、队长(Ls): 指在系统中的顾客数(包括正被服务的顾客 和排队等待的顾客)的期望值。,2、平均排队长(Lq): 指系统中排队等候服务的顾客数的期望值。,3、平均逗留时间(Ws):指一个顾客在系统中的停留时间期望值。,4、平均等待时间(Wq):指一个顾客在系统中排队等待的时间的期望值。,Ls=Lq+正被服务的顾客数,Ws=Wq+服务时间,5、忙期:指从顾客到达空闲服务机构起到服务机构再次空闲止 这段时间长度,即服务机构连续繁忙的时间长度。,6、系统的状态概率Pn( t ) :指系统中的顾客数为n的概率。,7、稳定状态:limPn(t)Pn,四、排队模型的数量指标,8、n 系统有n个顾客时的平均到
6、达率 9、n 系统有n个顾客时的平均服务率 10、 对任何n都是常数的平均到达率 11、 对任何n都是常数的平均服务率 12、 服务强度,或称使用因子,平均到达率与服务台与平均服务率的乘积的比值 13、系统的状态系统中的顾客数,如果系统中有n个顾客,就说系统的状态是n,系统的状态是随着时间在变化的 14、pn(t):时刻t系统状态为n的概率,稳态时系统状态为n的概率用pn表示。,五、常见的分布函数及生灭过程,1、poisson流 定义:设N(t)为时间0,t内到达系统的顾客数,如果满足下面三个条件: a、平稳性:在t,t+t内有一个顾客到达的概率为 t+o(t); b、独立性(无后效性):任意
7、两个不相交区间内顾客到达情况相互独立; c、普遍性:在t,t+t内多于一个顾客到达的概率为o(t); 则称N(t),t0为poisson流。 2、poisson分布 设N(t)为时间0,t内到达系统的顾客数,则N(t),t0为poisson流的充要条件是:,五、常见的分布函数及生灭过程,3、负指数分布 定理:设N(t)为时间0,t内到达系统的顾客数,则N(t),t0为参数为 的poisson流的充要条件是:相继到达时间间隔服从相互独立的参数为的负指数分布。 4、k阶爱尔朗分布 设v1, v2,., vk是k个相互独立的随机变量,服从相同参数k的负指数分布,那么 T= v1+v2+.+ vk 服
8、从k阶爱尔朗分布。,五、常见的分布函数及生灭过程,5、生灭过程 定义:设N(t),t0为一随机过程,若N(t)的概率分布具有以下性质: a、假设N(t)=n,则从时刻t起到下一个顾客到达时刻止的时间服从参数为n的负指数分布,n=0,1,2, b、假设假设N(t)=n,则从时刻t起到下一个顾客离去时刻止的时间服从参数为n的负指数分布,n=0,1,2, c、同一时刻时只有一个顾客到达或离去。 则称N(t),t0为一个生灭过程。,五、常见的分布函数及生灭过程,根据系统平稳状态时“流入=流出”原理,得到如下任一状态下的平衡方程: 0 1p1= 0p0 1 0p0+ 2p2=( 1+ 1 )p1 2 1
9、 p1+ 3p3 =( 2+ 2)p2 n-1 n-2pn-2 + npn =( n-1+ n-1 )pn-1 n n-1pn-1 + n+1pn+1 =( n+ n )pn ,生灭过程中Cn与p0的推导及应用,五、常见的分布函数及生灭过程,由上述方程可求得 0 p1 = p00/ 1 1 p2 =1p1/2+(1p1- p00)/ 2 =p001/(21) 2 p3 =2p2/3+(2p2- p11)/3 =p0210/(321) n-1 pn =n-1pn-1/n+(n-1pn-1- pn-2n-2)/n =p0n-2n-10/(nn-11) n p3 =npn/n+1+(npn- pn-
10、1n-1)/n+1 =p0nn-10/(n+1n1),五、常见的分布函数及生灭过程,记 则平稳状态的分布为pn=cnp0。由此可得 生灭过程排队系统的各项指标,即,6、经验分布,例1 某服务机构单服务台,先到先服务,对41顾客记录到达时刻和服务时间s(单位:分钟)如下表,表中第1号顾客到达时刻为0。全部服务时间为127(分钟)。,五、常见的分布函数及生灭过程,到达间隔分布表,服务时间分布表,平均间隔时间:=142/40=3.55(分钟/人),平均到达率:41/142=0.28(人/分钟),平均服务率:41/127=0.32(人/分钟),平均服务时间:127/41=3.12(分钟/人),六、典型
11、排队系统模型的结构及应用,M/M/C等待制排队模型研究要点: a、系统意义 b、状态转移速度图与状态转移速度矩阵 c、状态概率方程 d、系统的基本数量指标,Passion分布,设N(t)表示在时间0, t)内到达顾客数;,令Pn(t1, t2)表示在时间区间t1, t2)(t2 t1)内有n(0)个顾客到达的概率,即,Pn(t1, t2)=P N(t2) N(t1)=n (t2t1,n0),Passion分布的三条件:,(1) 无后效性:不相重叠的时间区间内顾客到达数相互独立,Pn(t+t)= Pn(t) ( 1-t+o(t) + Pn-1(t)t + o(t),在上述条件下,研究顾客到达数
12、n 的概率分布,Pn(t+t)= Pn(t)(1-t )+Pn-1(t)t+ o(t),Pn(t+t)-Pn(t)/t =-Pn(t)+Pn-1(t)+o(t)/t,令t0, P0(t)=e -t,Pn(t)=(t)n e -t /n,t 0, n=0,1,2,负指数分布,一、M/M/1 模型,1、假设,第三节 单服务台负指数分布排队系统的分析,2、Pn的计算,O表示发生(1个) , 表示没有发生,Pn(t+t)= Pn(t)(1-t)(1- t) + Pn+1(t)(1-t)t + Pn-1(t)t(1- t) + Pn(t)tt,整理得:,Pn(t+t)=Pn(t)(1-t-t)+Pn+1
13、(t)t+Pn-1(t)t+o(t),Pn(t+t)-Pn(t)/t =Pn-1(t)+Pn+1(t)-(+)Pn(t) (1),t0 dPn(t)/dt=Pn-1(t)+Pn+1(t)(+)Pn(t),考虑P0(t)的情况:,P0(t+t)=P0(t)(1-t)+P1(t)(1-t)t,t0 dP0(t)/dt=-P0(t)+P1(t) (2),由dPn(t)/dt=0得到,由式(3)得,通过求解可得, 单位时间内到达的平均顾客数, 单位时间内服务的平均顾客数, 服务强度,参数意义:,3、M/M/1参数计算,(1)系统中平均顾客数(Ls),记,(2)队列中等待的平均顾客数(Lq),(3)顾客
14、逗留时间(Ws),(4)队列中顾客等待时间(Wq),它们的相互关系如下:,其中 称为little公式,它是排队论中的一个重要公式。,例3 100个工作小时内每小时来就诊的病人数n出现次数如下,100个完成手术的病例所用时间v(小时)出现的次数如下,解:,假定系统最大容量为N,单服务台情形排队等待的顾客最多为N-1,下面只考虑稳态情形:,二、M/M/1/N/ 模型,解得:,根据上式我们可以推导出系统的各项指标:,有效到达率e=(1-PN),可以验证:1-P0= e /,(4) 顾客等待时间,(3) 顾客逗留时间,(1) 队长,(2) 队列长,例4 单人理发馆有六个椅子接待客人。当6个椅子都坐满时
15、,后来的顾客不进店就离开。顾客平均到达率为3人/小时,理发需时平均15分钟。则:,N=7为系统中最大的顾客数,=3人/小时,=4人/小时,(1)求某顾客一到达就能理发的概率。,(2)求需要等待的顾客数的期望值。,(3)求有效到达率。,(4)求一顾客在理发馆内逗留的时间。,(5)在可能到达的顾客中有百分之几不等待就离开。,(人/小时),一、M/M/c,第四节 多服务台指数分布排队系统的分析,用递推法解上述差分方程,可求得状态概率。,根据上式我们可以推导出系统的各项指标:,例6 某售票所有三个窗口,顾客到达服从Passion过程,平均到达率每分钟=0.9(人),服务(售票)时间服从负指数分布,平均服务率每分钟=0.4(人).,=0.9,代入公式得,(1)整个售票所空闲的概率,(2)平均队长,(3)平均等待时间和逗留时间,(4)顾客到达后必须等待(即系统中顾客数已有3人)的概率,M/M/c型系统和c个M/M/1系统的比较,上例中,排队方式不变,但顾客到达后在每个窗口前各排一队,且进入队列后坚持不换,这就形成3个队列,如下图二每个队列平均到达率为=0.9/3=0.3(每分钟),这样原来的系统就变成3个M/M/1型的子系统。,现按M/M/1型解决这个问题,并与上表比较:,从表中各指标的对比可以看出单队比三队有显著的优越性,
限制150内