资源预览内容
第1页 / 共41页
第2页 / 共41页
第3页 / 共41页
第4页 / 共41页
第5页 / 共41页
第6页 / 共41页
第7页 / 共41页
第8页 / 共41页
第9页 / 共41页
第10页 / 共41页
亲,该文档总共41页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第12章 排队论,第1节 基本概念,1.1 排队过程的一般表示,一般的排队过程为:顾客由顾客源出发,到达服务机构(服务台)前,按排队规则排队等待接受服务,服务机构按服务规则给顾客服务,顾客接受完服务后就离开。排队过程的一般过程可用下图表示。,我们所说的排队系统就是指图中虚线所包括的部分。这里的“顾客”和“服务台”要作广泛的理解;队列可以是具体的,也可以是无形的。,1.2 排队系统的组成和特征,尽管排队系统是多种多样的,但从决定排队系统进程的因素来看,它有三个基本的组成部分,这就是输入过程、排队规则及服务机构。,顾客源中主体的数量是有限还是无限; 顾客到达的方式是单个到达还是成批到达; 顾客相继到达的间隔时间分布是确定型的还是随机型的,是否相互独立,是否平稳,分布的类型和参数是什么。,2、排队规则 描述了顾客排队等待的队列和接受服务的次序。包括下列情况:,1、输入过程 描述了顾客来源以及顾客到达排队系统的规律。包括下列情况:,即时制还是等待制; 等待制下队列的情况(队列是有形还是无形的,单列还是多列,容量是否有限制;顾客在队列中能不能中途退出,在各列间能不能相互转移); 等待制下顾客接受服务的次序(先到先服务,后到先服务,随机服务,有优先权的服务)。,服务台(员)的数目和排列情况; 服务台(员)的服务方式是对顾客单个进行的,还是成批进行的; 服务时间是确定型的还是随机型的,是否相互独立,是否平稳 ,分布的类型和参数是什么 。,3、服务机构 描述了服务台(员)的机构形式和工作情况。包括下列情况:,1.3 排队模型的分类,在1971年关于排队论符号标准化的会议上决定,将Kendall符号扩充为: X/Y/Z/A/B/C 其中前三项意义不变,后三项意义分别为:A处填写系统容量限制;B处填写顾客源中的顾客数目;C处填写服务规则(如FCFS,LCFS)。 约定,如略去后三项,即指X/Y/Z/FCFS。,D.G.Kendall在1953年提出了一个分类方法,按照系统的三个最主要的、影响最大的特征要素进行分类,它们是:顾客相继到达的间隔时间分布、服务时间的分布、并列的服务台个数。 按照这三个特征要素分类的排队系统,用符号(称为Kendall记号)表示为: X/Y/Z 其中,X处填写顾客相继到达间隔时间的分布,Y处填写服务时间的分布,Z处填写并列的服务台个数。,1.4 排队系统的求解,对于一个排队系统,运行状况的好坏既涉及到顾客的利益,又涉及到服务机构的利益,还有社会效果好坏的问题。为了研究排队系统运行的效率、估计服务质量、研究设计改进措施,必须确定一些基本指标,用以判断系统运行状况的优劣。 下面介绍几种常用的指标:,(1)队长,指在系统中的顾客数,它的期望值记作Ls。 排队长(队列长), 指系统中排队等待服务的顾客数,它的期望值记作Lq。显然有 队长排队长正被服务的顾客数。,(2)逗留时间,指一个顾客从到达排队系统到服务完毕离去的总停留时间,它的期望值记作Ws。等待时间,指一个顾客在系统中排队等待的时间,它的期望值记作Wq。显然有 逗留时间等待时间服务时间。,此外 ,还有忙期、损失率、服务强度等指标,都是常用的重要指标。,计算这些指标的基础是系统状态的概率分布。所谓状态,指系统中的顾客数,记为n,n=0,1, 2,(或n=0,1, 2, N,或n=0,1, 2,c)。,考虑在时刻t系统的状态为n的概率,用Pn(t)表示,它是随时刻t而变化的,称为系统的瞬态(或称过渡状态)。 求系统的瞬态是很不容易的,一般即使求出也很难利用,因此常用它的极限(如果存在的话),称为系统的稳态或称统计平衡状态。,稳态的物理意义是,当系统运行了无限长的时间以后,初始状态的影响将消失,系统的状态概率分布不再随时间变化。当然,实际应用中大多数系统会很快趋于稳态,无需等到无限长的时间以后。,第2节 几个主要概率分布,解决排队系统问题,先要把有关的原始资料进行统计,确定顾客到达间隔和服务时间的经验分布,然后按照统计学的方法确定符合哪种理论分布。 经验分布的主要指标如下:,2.1 经验分布,处理实际问题时,首先要记录每个顾客的到达时刻i和服务时间si;然后,计算出每个顾客的到达间隔ti 和排队等待时间i 再利用前面的公式计算出经验分布指标。例P308,2.2 泊松分布,(3)普通性:在充分短的时间区间t内,到达两个或两个以上顾客的概率极小,可忽略不计,即,设N(t)表示在时间区间t0,t0+t)内到达的顾客数,是随机变量。当N(t)满足下面的三个条件时,我们说顾客的到达符合普阿松分布。这三个条件是:,(1)平稳性:在时间区间t0,t0+t)内到达的顾客数N(t),只与区间长度t有关而与时间起点t0无关。,(2)无后效性:在时间区间t0,t0+t)内到达的顾客数N(t),与t0以前到达的顾客数独立。,为了求出pn(t),考虑0, t+t) 内来n个顾客的概率 pn(t+t )=pn(t)p0(t)+pn-1(t)p1(t)+p0(t)pn(t),N(t)的数学期望为t,可知即平均到达率。,对于充分小的t, 则有 p0(t)=e-t=1-t+o(t) p1(t)=1-p0(t)+o(t) =t+o(t),p0(t)表示在时间长度为t的时间段中没有顾客到达的概率,它关于t单调下降,则存在0,使p0(t)=e-t,则 pn(t+t )=pn(t)(1-t)+pn-1(t) (t)+o(t) (n1),依次求解下去,可得,2.3 负指数分布,负指数分布具有下列性质: (1)无记忆性或马尔柯夫性,即 PTt+s / TsPTt (2)当顾客到达符合普阿松分布时,顾客相继到达的间隔时间T必服从负指数分布。,T的数学期望和方差分别为: ET1/, Var(T)1/2,用普阿松分布描述顾客到达时,表示顾客的平均到达率,所以1/表示顾客相继到达的平均间隔时间。而用负指数分布描述顾客相继到达的间隔时间时,顾客相继到达的平均间隔时间为ET= 1/,所以同样表示顾客的平均到达率。,第3节 单服务台负指数分布排队系统分析,排队系统的状态n随时间变化的过程称为生灭过程。设平均到达率为,平均服务率为, 排队系统M/M/1/的生灭过程可用下面的状态转移图表示:,3.1 标准M/M/1模型(M/M/1/),这里的称为服务强度,也称话务强度,它刻画了服务机构的繁忙程度,所以又称服务机构的利用率。,系统的各项运行指标计算如下:,平均队长:,平均排队长:,逗留时间W的分布函数为:,平均逗留时间:,平均等待时间:,解:,(2)排队等待平均病人数为 Lq= 5.25-0.84=4.41人,3.2 系统容量有限制的情形(M/M/1/N/),当系统的容量有限制(为N)时,设平均到达率为、平均服务率为,排队系统(M/M/1/N/)的生灭过程可用下面的状态转移图表示:,设=/1, 考虑到 p0+ p1+ + pN=1, 解得,系统的各项运行指标计算如下:,平均队长:,平均排队长:,有效到达率(平均单位时间实际进入排队系统的顾客数):e=(1-pN)=(1-p0),平均逗留时间:,平均等待时间:,损失率:,例 单人理发馆有6个椅子接待人们排队等待理发,当6个椅子都坐满时,后来到的顾客不进店就离开。顾客平均到达率为3人/小时,理发需时平均15分钟。求: (1)某顾客一到达就理发的概率; (2)需要等待的顾客数的期望值; (3)有效到达率; (4)一顾客在理发馆内逗留的期望时间; (5)到来的顾客不等待就离开的概率。,解:,(1)顾客一到达就理发的概率为,N=7, =3(人/小时),=60/15=4 (人/小时),(2)需要等待的顾客数的期望值为,(3)有效到达率为 e = (1-p0) = 4(1-0.2778) = 2.89(人/小时),(4)顾客逗留的期望时间为 Ws=2.112.89=0.73小时,(5)顾客不等待就离开的概率为 p7 = 1-e/= 1-2.89/3 3.7%,现以本例比较系统容量为有限和无限两种情况:,Lq = 2.11-(1-0.2778) = 1.39(人),3.3 顾客源为有限的情形(M/M/1/m),当系统的顾客源为有限(m)时,设各个顾客的平均到达率都为、服务台的平均服务率为, 排队系统的生灭过程可用下面的状态转移图表示:,考虑到 p0+ p1+ + pm=1, 解得,平均队长:Ls=m(1-p0)/ 平均排队长:Lq=Ls(1-p0) 顾客源中的顾客平均数:m-Ls 有效到达率(排队系统总的平均到达率): e=(m-Ls)=(1-p0) 平均逗留时间: Ws= Ls /e 平均等待时间:Wq=Ws1/=Lq /e,系统的各项运行指标计算如下:,例:某车间有5台机器,每台机器的连续运转时间服从负指数分布,平均连续运转时间15分钟。有一个修理工,每次修理时间服从负指数分布,平均每次12分钟。求: (1)修理工空闲的概率; (2)5台机器都出故障的概率; (3)出故障机器的平均台数; (4)等待修理机器的平均台数; (5)平均停工时间; (6)平均等待修理时间; (7)评价这些结果。,解:,m=5, =50/15=4,=60/12=5,/=0.8,(1)修理工空闲的概率为 p0 = (5!/5!)0.80+ (5!/0!)0.85 -1 = 0.0073,(3)出故障机器的平均台数为 Ls = 5-(1-0.0073)/0.8=3.76(台),(5)平均停工时间为 e = (1-p0) = 5(1-0.0073) = 4.9635 Ws= 3.76/4.9635=0.758(小时) 46(分钟),(6)平均等待修理时间为 Wq=46-12=34(分钟),(2) 5台机器都出故障的概率为 p5 = (5!/0!)0.85p0 = 0.287,(4)等待修理机器的平均台数为 Lq = 3.76-(1-0.0073) = 2.77(台),(7)评价这些结果:,第4节 多服务台负指数分布排队系统分析,4.1 标准M/M/c模型(M/M/c/),对于排队系统M/M/c/,规定c个服务台相互独立且平均服务率都为。设 ,其生灭过程可用下面的状态转移图表示:,稳态概率方程如下:,解得稳态概率分布为:,系统的运行指标如下:,例 某售票窗处有三个窗口,顾客的到达服从泊松过程,平均到达率为=0.9(人/分),服务时间服从负指数分布,平均服务率为=0.4(人/分)。现设顾客到达后排成一队,依次向空闲的窗口购票,求: (1)整个售票处空闲的概率; (2)平均队长; (3)平均逗留时间; (4)平均排队等待时间; (5)顾客到达后必须等待的概率。,解:,c=3,/=2.25,=2.25/3=0.751,(3)平均逗留时间为 Ws= 3.95/0.9=4.39(分钟),(4)平均排队等待时间为 Wq= 4.39-1/0.4=1.89(分钟),(1)整个售票处空闲的概率,(2)平均队长,(5)顾客到达后必须等待的概率,就前面的例子,如果顾客到达后在每个窗口前各排一队,且不准换队,整个系统就变成了3个M/M/1子系统,每个子系统的平均到达率均为0.9/3=0.3(人/分钟)。计算各项指标并与前面的计算结果比较如下:,4.2 M/M/c系统和c个M/M/1系统的比较,通过对比可以看出,单队比多队有显著的优越性,在安排排队方式时应该注意。,多服务台时,由于计算p0和各项指标的公式很复杂,可使用专门的Wq数值表计算各项指标。,上例中,c=3, /c=0.75。查表无此数,用线性插值法得,因=0.4,所以Wq=0.8129/0.4=2.03(分钟),Ws=2.03+1/0.4=4.53(分钟),因
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号