排队模型(掌握mm1,mmc,mm1k)

排队模型凯里学院余英模型要点1、掌握排队模型的基本概念2、了解常见的分布函数及生灭过程3、掌握典型排队系统模型的结构及应用排队模型的基本概念1、什么是排队模型（排队论）？排队论是研究拥挤现象的一门学科。它是在研究各种排队系统概率规律性的基础上，解决有关排队系统的最优化设计（静态）和最优控制（动态）问题。一、引言现实生活中的排队系统序号到达的顾客要求服务内容服务机构1不能运转的机器修理修理技工2修理技工领取修配零件发放修配零件的管理员3病人诊断或做手术医生(或包括手术台)4电话呼唤通话交换台5文件搞打字打字员6提货单提取存货仓库管理员7驶入港口的货船装(卸)货装(卸)货码头(泊位)8上游河水进入水库放水，调整水位水闸管理员2、排队论的起源与应用领域1）、20世纪初Bell电话公司为减少用户呼叫，研究电话线路合理配置问题；2）、1909年丹麦工程师A.K.Erlang受热力学统计平衡概念启发发表论文《概率论与电话交换》，解决上述问题；3）、应用于：通讯系统、交通运输、机器维修、库存控制、计算几设计等领域。二、排队系统的特征及其组成1、排队系统的特征即拥挤现象的共性1）、有请求服务的人或物2）、有为顾客服务的人或物3）、具有随机性4）、服务的数量超过服务机构的容量2、排队系统的三大基本组成部分1）、输入过程(顾客到达的方式)a、顾客的总体（顾客源）的组成可能是有限的，也可能是无限的；b、顾客相继到达的时间间隔可以是确定的，也可以是随机的，对于随机的情形，要知道单位时间内的顾客到达数或相继到达的间隔时间的概率分布；c、输入过程可以是平稳的（描述相继到达的间隔时间分布和所含参数（如期望值、方差等）都是与时间无关的），否则成为非平稳的，我们研究平稳的。2、排队系统的三大基本组成部分2）、排队规则a、顾客到达时，如所有服务台都被占用，在这种情形下，顾客可以随即离去，也可以排队等待，前者成为损失制，后者成为等待制，我们研究后者；其次还有混合制，它是介于等待制和损失制之间的；b、从占有的空间来看，有的系统要规定容量（即允许进入排队系统的顾客数）的最大限，有的没有这种限制2、排队系统的三大基本组成部分3）、服务过程a、可以是没有服务员，单个的，多个的，对于多个的，它们之间可以是平行排列（并列）的，也可以是前后排列（串列）的，也可以是混合的；b、服务时间可以是确定的，也可以是随机的，对于后者要知道它的概率分布；c、服务时间可以是平稳的，也可以是非平稳的，我们研究前者；d、对于等待制，服务规则又可以分为先到先服务（FCFS），后到先服务（LCFS），随机服务和有优先权的服务。三、排队模型的分类（符号表示）我们采用Kendall记号顾客相继到达时间间隔分布/服务时间分布/服务台数目/排队系统允许的最大顾客容量（系统容量）/顾客总体数量（顾客源数量）/排队规则说明：如果Kendall记号中略去后3项，表示x/y/z/∞/∞/FCFS相继到达时间间隔和服务时间分布的符号如下：M——负指数分布D——确定型Ek——k阶爱尔朗分布GI——一般相互独立的时间间隔分布G——一般服务时间分布四、排队模型的数量指标1、平均队长(Ls)：指在系统中的顾客数（包括正被服务的顾客和排队等待的顾客）的期望值。2、平均排队长(Lq)：指系统中排队等候服务的顾客数的期望值。3、平均逗留时间(Ws)：指一个顾客在系统中的停留时间期望值。4、平均等待时间(Wq)：指一个顾客在系统中排队等待的时间的期望值。Ls=Lq+正被服务的顾客数Ws=Wq+服务时间5、忙期：指从顾客到达空闲服务机构起到服务机构再次空闲止这段时间长度，即服务机构连续繁忙的时间长度。6、系统的状态概率[Pn(t)]：指系统中的顾客数为n的概率。7、稳定状态：limPn(t)→Pn四、排队模型的数量指标8、λn——系统有n个顾客时的平均到达率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、独立性（无后效性）：任意两个不相交区间内顾客到达情况相互独立；c、普遍性：在[t,t+∆t]内多于一个顾客到达的概率为o(∆t);则称{N（t），t≥0}为poisson流。2、poisson分布设N（t）为时间[0，t]内到达系统的顾客数，则{N（t），t≥0}为poisson流的充要条件是：(){()}(1,2,...)!nttpNtnenn五、常见的分布函数及生灭过程3、负指数分布定理：设N（t）为时间[0，t]内到达系统的顾客数，则{N（t），t≥0}为参数为λ的poisson流的充要条件是：相继到达时间间隔服从相互独立的参数为λ的负指数分布。4、k阶爱尔朗分布设v1,v2,...,vk是k个相互独立的随机变量，服从相同参数kμ的负指数分布，那么T=v1+v2+...+vk服从k阶爱尔朗分布。五、常见的分布函数及生灭过程5、生灭过程定义：设{N（t），t≥0}为一随机过程，若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），t≥0}为一个生灭过程。五、常见的分布函数及生灭过程根据系统平稳状态时“流入=流出”原理，得到如下任一状态下的平衡方程：0μ1p1=λ0p01λ0p0+μ2p2=（λ1+μ1）p12λ1p1+μ3p3=（λ2+μ2）p2……n-1λn-2pn-2+μnpn=（λn-1+μn-1）pn-1nλn-1pn-1+μn+1pn+1=（λn+μn）pn……生灭过程中Cn与p0的推导及应用五、常见的分布函数及生灭过程由上述方程可求得0p1=p0λ0/μ11p2=λ1p1/μ2+(μ1p1-p0λ0)/μ2=p0λ0λ1/(μ2μ1)2p3=λ2p2/μ3+(μ2p2-p1λ1)/μ3=p0λ2λ1λ0/(μ3μ2μ1)……n-1pn=λn-1pn-1/μn+(μn-1pn-1-pn-2λn-2)/μn=p0λn-2λn-1…λ0/(μnμn-1…μ1)np3=λnpn/μn+1+(μnpn-pn-1λn-1)/μn+1=p0λnλn-1…λ0/(μn+1μn…μ1)五、常见的分布函数及生灭过程记则平稳状态的分布为pn=cnp0。由此可得生灭过程排队系统的各项指标，即12010...(1,2,...)...nnnnncn0111nnpc0,(),,qnqnqnnceeelllnplncpww其中是整体平均到达率6、经验分布例1某服务机构单服务台，先到先服务，对41顾客记录到达时刻和服务时间s（单位：分钟）如下表，表中第1号顾客到达时刻为0。全部服务时间为127（分钟）。(1)i(2)τi(3)si(4)ti(5)wi(1)i(2)τi(3)si(4)ti(5)wi(1)i(2)τi(3)si(4)ti(5)wi10520512271093612022743619435103827036156722346114552041191282631051247423五、常见的分布函数及生灭过程(1)i(2)τi(3)si(4)ti(5)wi(1)i(2)τi(3)si(4)ti(5)wi(1)i(2)τi(3)si(4)ti(5)wi13491352386622331174471452293248854634121267156111025921373512712316622302695365361296121765150271012423713033718703202810521038133527197248129106131391352410208031030109250401394382181222311141204114219228333232116810到达间隔分布表服务时间分布表平均间隔时间：=142/40=3.55(分钟/人)平均到达率：41/142=0.28(人/分钟)平均服务率：41/127=0.32(人/分钟)平均服务时间：127/41=3.12(分钟/人)到达间隔(分钟)次数12345678910以上61086322111合计40服务时间(分钟)次数123456789以上10107542111合计41六、典型排队系统模型的结构及应用M/M/C等待制排队模型研究要点：a、系统意义b、状态转移速度图与状态转移速度矩阵c、状态概率方程d、系统的基本数量指标Passion分布设N(t)表示在时间[0,t)内到达顾客数；令Pn(t1,t2)表示在时间区间[t1,t2)（t2t1）内有n（0）个顾客到达的概率，即Pn(t1,t2)=P{N(t2)–N(t1)=n}（t2t1，n0）Passion分布的三条件：(1)无后效性：不相重叠的时间区间内顾客到达数相互独立1(2)(,)()Pttttt2(3)(,)()nnPttttPn(t+Δt)=Pn(t)(1-λΔt+o(Δt))+Pn-1(t)λΔt+o(Δt)情况[0,t)[t,t+Δt)[0,t+Δt)个数概率个数概率个数概率(A)(B)(C)nn-1n-2n-3…0Pn(t)Pn-1(t)Pn-2(t)Pn-3(t)…P0(t)0123…n1-λΔt+o(Δt)λΔto(Δt)nnnn…nPn(t)(1-λΔt+o(Δt))Pn-1(t)λΔto(Δt)在上述条件下，研究顾客到达数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令Δt0dPn(t)/dt=-λPn(t)+λPn-1(t)Pn(0)=0（n1）dP0(t)/dt=-λP0(t)P0(0)=1（n=0）P0(t)=e-λtPn(t)=[(λt)ne-λt]/nt0,n=0，1，2…负指数分布fT（t）=λe-λt，t00，t0[1ttttttttETtedttedttdeteedtedtedte()（）（）000000001]1ttttVTETETtedttetedttedt（）（）（）222202220002221[]11[2]2211一、M/M/1模型1、假设（1）顾客到达的间隔时间满足参数为λ的负指数分布（2）服务时间满足参数为µ的负指数分布（λµ）（3）服务机构是单服务台（4）顾客源是无限的，顾客相互独立（5）单队排列，且对队长没有限制第三节单服务台负指数分布排队系统的分析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)λΔtμΔt情况在时刻t顾客数在区间（t,t+Δt）在时刻t+Δt顾客数到达离去(A)(B)(C)(D)nn+1n-1n××OO×O×Onnnn整理得：Pn(t