您好,欢迎访问三七文档
1第六章排队论(QueueingTheory)本章重点:到达与服务的规律、M/M/1排队系统,M/M/C排队系统本章难点:排队系统到达与服务的规律本章将比较全面地介绍运筹学的重要分支排队论的基本内容,包括基本概念、达到与服务的规律、几种主要的排队系统及模型,以及排队系统的优化。6.1基本概念6.1.1排队系统的组成排队是日常生活中经常遇到的现象,如到商店买东西,到医院看病,均是顾客希望得到某种服务,而当某时刻要求服务的顾客数量超过服务机构的容量时,便出现排队现象。这时,排队等待的顾客与服务机构便构成一个排队系统,如图6.1所示,现实世界中存在着形形色色的排队系统,如表6.1所示。图6.1排队系统表6.1现实世界中形形色色的排队系统如果服务设施过少或服务效率太低,便会加剧拥挤,排队成龙。但增加服务设施便会增加服务成本或造成系统空闲,而有些服务设施如机场、港口泊位等一旦建成就不易改动。因此,有必要对排队系统的结构和运行规律加以研究,为排队系统的设计和调控提供依据。排队系统的基本组成部分主要有输入过程、排队规则、服务机构。1.输入过程输入过程是指顾客到达排队系统的过程,对此我们主要讨论两方面内容:(1)顾客源:分为•无限∞(如电话呼唤)•有限m(如车间里待修理的机器)(2)到达规律:指到达间隔时间T的分布分为•定长D•负指数M到达的顾客要求服务的内容服务机构不能运转的机器修理技工电话呼唤修理领取修配零件通话修理技工发放零件的管理员交换台队列服务机构顾客源离去2•k阶爱尔朗kE2.排队规则排队规则是指顾客到达系统后排队等候服务的方式和规则。可分为三种类型:(1)损失制指顾客到达时若所有服务实施均被占用,则顾客自动离去。(2)等待制指顾客到达时若所有服务实施均被占用,则留下来等待,直至被服务完离去。等待制的排队规则又可按顾客被服务的次序分为以下几种:•先到先服务(FCFS)•后到先服务(LCFS)•具有优先权的服务(PS)(3)混合制这是损失制和等待制的混合。这种排队规则既允许排队又不允许队列无限长,主要分为:•系统容量有限制•等待时间有限制3.服务机构对服务机构的研究内容主要有服务设施(称为服务台)的数量和服务的规律。(1)服务台个数11()C=⎧⎨⎩并列多台(2)服务规律:指服务时间v的分布分为:定长D、负指数M、k阶爱尔朗kE、一般分布G6.1.2排队模型的表示根据输入过程、排队规则和服务机构的不同情况对排队系统进行描述和归类,可以给出很多排队模型。为了方便对众多模型的描述,康道尔在1953年提出一种依据排队系统的三个基本特征对排队模型进行分类表示的方法,称为Kendall记号,后来,在1971年的一次关于排队符号标准化会议上决定,将Kendalll记号扩充为(X/Y/Z/A/B/C),其中X:顾客到达时间间隔的分布Y:服务时间的分布Z:服务台个数A:系统容量B:顾客源数量C:服务规则(M/M/1/∞/∞/FCFS)表示:到达间隔为负指数分布,服务时间也为负指数分布,1个服务台,顾客源无限,系统容量也无限,先到先服务。若只讨论先到先服务的情况,可略去第6项。6.1.3排队问题的求解研究排队系统的目的是通过了解系统的运行的状况,对系统进行调整和控制,使系统处于最优运行状态。而描述系统运行状况的客观数量指标主要是系统中由于排队和被服务而滞留的顾客数量,以及顾客为等待服务而必须在系统中消耗的时间。因此,排队论中对排队问3题的求解,一个基本内容就是研究和计算这些描述系统运行状态的数量指标,简称系统运行指标。这些数量指标一般来说都是随机变量,并且和系统运行的时间t有关。这里主要研究∞→t时的稳态情形。这时系统处于平衡状态,数量指标的分布等与时间无关,这时求得的结果称为系统处于统计平衡下的解。1.队长和排队长队长:系统中的顾客数;其概率分布称状态概率,记为Pn,表示系统中有n个顾客的概率;队长的平均值记为Ls。排队长:系统中正在排队等待的顾客数,记其均值为Lq。2.逗留时间和等待时间逗留时间:一个顾客在系统中的停留时间,记为W,其均值记为SW。等待时间:一个顾客在系统中排队等待的时间,记其均值为Wq。6.1.4到达的规律描述顾客到达规律可从两方面现实中有许多服务系统,其顾客的到达具有下述特征:(1)无后效性:任一时段的到达数不受前一时段的影响;(2)平稳性:顾客到达是均匀的;(3)稀有性:瞬时内只可能有1个顾客到达。称具有上述特征的输入为泊松流,其在t时段内到达n个顾客的概率为,1,0,!)()(==−nenttPtnnλλ(6-1)即参数为tλ的泊松分布。由概率论知识可知,泊松分布的参数即其均值。因此,λ的含义是单位时间到达系统的平均顾客数,即到达率。下面考察,当顾客按泊松流到达时,其到达的间隔时间T是服从什么分布呢?因为到达为泊松流,所以t时段内没有来顾客的概率为tteettPλλλ−−==!0)()(00(6-2)所以,t时段内有顾客到来(即间隔tT≤)的概率为而这正是负指数分布的分布函数,说明T服从负指数分布,且参数同为λ。可证反之也成立。于是得到关于到达规律的重要性质:到达数为泊松流到达间隔服从负指数分布(同参数)。由概率论知识可知,负指数分布的表达式(密度函数)为⎩⎨⎧≥=−0,00,)(ttetftTλλ(6-3)ttetFetTPλλ−−−=−=≤1)(1)(,即⎩⎨⎧)()(人数到达数时间到达间隔4参数λ即其均值的倒数。因此,λ1的含义是平均间隔时间,这与λ为单位时间到达系统的平均顾客数的含义一致。负指数分布有一个有趣的性质:无记忆性,即)()(00tTPtTttTP=+(6-4)直观上看,在已知0tT的条件下估计tT的概率,与无条件时估计tT的概率相同,把以前的0t时间给忘了。证:由条件概率公式得)()()()())()()(00)(0000000tTPeeetTPttTPtTPtTttTPtTttTPtttt===+=+=+−−+−λλλ∩(6-5)假若T表示某种电子元件的寿命,则当元件已使用了0t时间后估计它还能再使用t时间的概率,与它全新时估计用t时间的概率一样,即它对已使用了的0t时间无记忆。说明这种元件是高度耐磨损的。6.1.5服务的规律描述排队系统的服务规律主要是采用系统对顾客服务时间v的分步。主要讨论服务时间v服从负指数分布的情形,参数为μ,即⎩⎨⎧≥=−00,0,)(ttetftvμμ(6-6)由于v的均值为μ1,即平均对每位顾客的服务时间为μ1,可得,参数μ的含义:服务率,即单位时间平均服务完μ人。注:负指数分布的一般化——爱尔朗分布,可用于描述由k道程序组成的1个服务台的服务时间的分布。6.2M/M/1排队模型6.2.1标准的M/M/1模型(M/M/1/∞/∞)1.问题的一般提法设:泊松输入/负指服务/单服务台/系统无限制/顾客源无限制求:(1)系统状态概率Pn;(2)系统运行指标Ls,Lq,Ws,Wq。2.系统状态概率(1)利用状态转移图列出平衡方程图6.2n+1102λλn-1nλλ…….…μμμμ5状态转移图是处理稳态M/M/C系统的一种工具,设到达与服务率分别为λ和μ,则对于状态n(,...2,1=n),由于系统满足统计平衡,即流入应等于流出,故有:nnnnPPPPμλμλ+=++−11(6-7)对于状态0,也应有10PPμλ=(6-8)由此列出平衡方程:⎩⎨⎧≥+=+=+−1,)(1110nPPPPPnnnμλμλμλ(6-9)(2)由平衡方程解得状态概率由平衡方程⎩⎨⎧≥+=+=+−1,)(1110nPPPPPnnnμλμλμλ可解得状态概率:⎪⎪⎩⎪⎪⎨⎧≥−=−=1),1()(10nPPnnμλμλμλ(6-10)记μλ=ρ,称为服务强度,规定ρ1,则⎩⎨⎧=−=001PPPnnρρ(6-11)式中ρ有明确的实际意义,由于ρ=μλ,说明ρ是平均到达率与平均服务率之比,由于λμρ11=说明ρ是平均服务时间与平均到达间隔时间之比,反映了系统的服务强度。而由01P−=ρ说明ρ是系统忙着的概率,反映了系统的繁忙程度和利用率。因此,称ρ为服务强度或服务机构的利用率。3.系统运行指标(1)Ls与Lq∵Ls表示系统中的平均顾客数,由期望定义∑∑∑∞=−∞=∞=−=−==∴1100)(1)1(nnnnnnsnnnpLρρρρρ∑∑∞=∞=−=−=01nndd)(1dd)(1nnρρρρρρρρ2)(11)(111dd)(1ρρρρρρρ−−=−−=λμλρρ−=−=1(6-12)6)1()1(0101PLPnPPnLsnnnnnnq−−=−=−=∑∑∑∞=∞=∞=ρ−=sL(6-13)其中1=μλρ。问题:为什么1=−ρqsLL(而不是=1)呢?——因为是均值。(2)Ws与Wq首先可证,逗留时间W服从参数为λμ−的负指数分布,而负指数分布的均值等于其参数的倒数,故平均逗留时间λμ−=1sW。平均等待时间等于平均逗留时间减去平均服务时间,即μ1−=sqWW。(3)上述4个指标之间的关系——里特公式ssWLλ=qqWLλ=μλ=−qsLL1μ=−qsWW一般的里特公式中λ应为eλ,称有效到达率,即实际进入系统率。本模型中因系统容量无限制,故λλ=e。例6.1某修理店只有一个修理工人,来修理的顾客到达数服从泊松分布,平均每小时4人;修理时间服从负指数分布,平均需6分钟。求:(1)修理店空闲的概率;(2)店内有3个顾客的概率;(3)店内至少有1个顾客的概率;(4)店内顾客的平均数;(5)顾客在店内的平均逗留时间;(6)等待服务的顾客平均数;(7)平均等待修理时间;(8)必须在店内消耗15分钟以上的概率。解:此为标准的M/M/1模型,λ=4人/小时,61=μ人/分钟=10人/小时,52==μλρ(1)5310=−=ρP;(2)0.0384)53()52()(1333==−=ρρP;(3)5210=−P;(4)3264==−=λμλsL(人/小时);(5)611==ssLWλ(人/小时);(6)1545232=−=−=ρsqLL(人/小时);(7)151101611=−=−=μsqWW(人/小时);(8)0.223)41(1)41(1)41(1.5414)(10===−=−=≥−−−eeFWPWP76.2.2系统容量有限的M/M/1模型(M/M/1/N/∞)1.与(M/M/1/∞/∞)的区别(1)系统状态只有N+1种(Nn,,,10=);(2)顾客的实际进入系统的速率⎩⎨⎧≥NnNnλ当0,当,,故平均到达率)1(0)(1NNNePPP−=+−=λλλ注:由于系统稳定时应达到统计平衡,即进入速率应等于离去速率,故)P-(1)(10μλ=−NP。2.状态概率首先画出系统的状态转移方程,如图6.3所示:图6.3根据系统的状态转移图,由此列出平衡方程:⎪⎩⎪⎨⎧==+=+=+−NN-nnnPPNnPPPPPμλμλμλμλ111101-,1,,)((6-14)先解得0PPnnρ=,再由111010000=−−=+++=∑=+NnNNnPPPPPρρρρ可解得0P,故⎪⎩⎪⎨⎧=−−=+01011PPPNNNρρρ。当ρ=1,由平衡方程组可得P0=P1=…=PN=11+N。状态概率中的PN表示系统满员的概率,因此也可称为系统对顾客的拒绝率或顾客的损失率。3.系统运行指标先求出系统的平均队长11011)(1++=−+−−==∑NNNnnsNnPLρρρρ,(6-15)再由里特公式,求出其他三个指标。)(10PLLsq−−=(6-16)essLWλ=(6-17)eqqLWλ=(6-18)λλλλλμμμμn12n-1n+10….NN+1…μ8)1(NeP−=λλ为有效到达率,它的直观解释是,顾客到达且系统未满而实际进入系统率。由统计平衡知,它应等于实际服务率μ(1—P0)。它表示系统不空且以μ的速率服务着。μλe称为本系统的服务强度。例6.2某修理站只有1个修理工,且站内最多只能停放3台待修理的机器。设待修理的机器按泊松流到达,平均每小时到达1台;修理时间服从负指数
本文标题:第六章-排队论
链接地址:https://www.777doc.com/doc-7213539 .html