第六章排队论.

第六章随机服务系统理论确定型只是随机现象的特例排队论QueuingTheory26.1随机服务系统基础•系统的输入与输出是随机变量•A.k.Erlang于1909~1920年发表了一系列根据话务量计算电话机键配置的方法，为随机服务理论奠定了基础•又称为排队论(QueuingTheory)或拥塞理论(CongestionTheory)•应用广泛•交通行业应用：交叉口/高速收费站/机场航班…3顾客来源队列服务机构排队系统顾客服务完离开排队系统的三个基本组成部分.•输入过程(顾客按照怎样的规律到达);•排队规则(顾客按照一定规则排队等待服务);•服务机构(服务机构的设置,服务台的数量,服务的方式,服务时间分布等)6.1.1基本要素4输入过程•顾客源–有限–无限•经常性的顾客来源–顾客到达间隔时间:到下一个顾客到达的时间–服从某一概率分布（确定型/随机型）•顾客的行为假定–在未服务之前不会离开–当看到队列很长的时候离开–从一个队列移到另一个队列5排队服务规则–队列容量•有限/无限–排队规则•损失制•等待制：先到先服务(FCFS)，后到先服务(LCFS)，随机服务(RS)，优先权服务(PS)•混合制•逐个到达，成批服务；成批到达，逐个服务6–单通道和多通道–并联服务–串联服务–串并联服务服务机构的组织方式与服务方式123顾客到达顾客离开123顾客到达顾客离开顾客离开顾客离开银行服务-叫号系统123顾客到达顾客到达顾客到达顾客离开顾客离开顾客离开机场安全检查通道7常用符号•M—泊松分布（负指数分布）•Ek—k阶爱尔朗分布•D—确定型分布•G—一般分布•M/M/1/K/∞/FCFS—顾客到达服从泊松分布，顾客的服务时间服从负指数分布，单通道，系统容量有限（K）而顾客源无限，先到先服务的排队系统顾客到达时间间隔分布/服务时间分布/服务台数目/排队系统允许的最大顾客容量/顾客总体数量/排队规则(扩充的Kendall符号)--Kendall’snotation6.1.2符号表示8队长：系统中的顾客数量的期望值排队长：系统中正在等待的顾客数量期望值逗留时间：顾客在排队系统中的总时间（等待时间与被服务时间之和）的期望值排队时间：顾客的排队等待时间的期望值忙期：服务机构连续繁忙的时间长度服务强度：顾客到达率的期望值与服务率的期望值之比6.1.3排队系统营运指标9•服务系统存在来自两个矛盾方面的要求–顾客希望服务质量好，如排队等待时间短，损失率低–系统运营方希望设备利用率高•给用户一个经济上能够承受的满意的质量•哪些系统特性会影响系统的性能？–服务机构的组织方式与服务方式–顾客的输入过程和服务时间分布–系统采用的服务规则与服务系统性能相关的特性6.2顾客到达分布和服务时间分布6.2.1概述•顾客的服务时间由于多种原因具有不确定性，最好的描述方法就是概率分布；同样顾客到达的间隔时间也服从一定的概率分布顾客到达时刻开始服务时刻服务终结时刻t12341234w2w3h1h2h3h4空123411频率%3020102468到达间隔时间（分钟）•若统计区间分得越细，样本越多，则经验分布的轮廓越接近曲线•经验分布一般采用直方图来表示，如下图–FrequencyDistribution•服务时间和到达间隔时间服从什么分布？可以先通过统计得到经验分布，然后再做理论假设和检验126.3.2输入过程（顾客到达分布）•可用相继到达顾客的间隔时间描述，也可以用单位时间内到达的顾客数描述–间隔时间服从定长分布（DeterministicDistribution）–间隔时间服从爱尔朗分布（Erlangdistribution）–二项分布（binomialdistribution）–单位时间t（或时间区间△t）内到达的顾客数服从泊松分布(法国数学家Poisson,1836)—最简单流（泊松流）（PoissonDistribution）–负指数分布（NegativeExponentialDistribution）136.3.2.1最简单流（泊松流）--纯生过程•(1)泊松流形成条件–流的平稳性对于任意的t≥0及Δt≥0，在时间区间(t,t+Δt)内有n个顾客到达的概率只与Δt有关，与时间区间的起点t无关。当Δt充分小时，在(t,t+Δt)内有一个顾客到达的概率与Δt成正比，即其中，O(Δt)是当Δt→0时，关于Δt高阶无穷小；λ为单位时间内的顾客到达平均数。1(,)()Pttttot14•在时间轴上，互不相交的时间区段和内，顾客的到达数是相互独立的，即前一顾客的到达不影响后一顾客的到达。–流的无后效性•当t充分小时，在t时间内到达一个顾客的概率为t+o(t)，到达两个或两个以上顾客的概率为o(t)；即两个顾客不可能同时到达–流的普遍性12,tt34,tt1234()tttt•设把长为Δt的时间区间分成m等分，每段长度为。若在dt内，有一个顾客到达，则称被“占着”，如果在dt内，没有顾客到达，则称为“空着”。被“占着”的概率近似为被“空着”的概率近似在长为Δt的时间区间内，到达n个顾客的概率1(,)()Pttdtdtodt)(tPn/dttm0(,)1()Pttdtdtodt根据流的无后效性，在m个dt中，有顾客到达与没有顾客到达可以看成是m次独立的试验•(2)泊松流详解16在长为Δt的时间区间内，到达n个顾客的概率)(tPn在m个dt中，有n个dt被顾客“占着”的概率利用二项定律()()1nmnnnmmttPtPnCmm17dt0，m()lim1nmnnnmmttPtCmm(1)(2)(1)lim1!nmnmmmmmnttnmm()11lim1mnnmtmmmntnmmmm！()lim1mnmttnm！tnnenttP！)()(()ntten！18符合最简单流（泊松流）的随机事件发生规律tnnenttP！)()(单位时间△t内有n个顾客到达的概率λ—顾客的平均到达率•(3)泊松分布19（4）泊松输入过程及其特点1)平稳性：顾客到达数只与时间区间长度有关2)无后效性：不相交的时间区间内所到达的顾客数是独立的3)普遍性：在t时间内到达一个顾客的概率为t+o(t)，到达两个或两个以上顾客的概率为o(t)；即两个顾客不可能同时到达•泊松过程具有可迭加性–即独立的泊松分布变量的和仍为泊松分布20•泊松过程的到达间隔时间为负指数分布–令h代表间隔时间，则概率P{ht}代表时间区间△t内没有顾客来的概率；由泊松分布可知：P0(h△t)=P{h△t}=e△t故间隔时间h的分布为P{h△t}=1e△t（1）推导()()ntntPten！0()1()1/tttFteftehtedtn=06.3.2.2负指数分布tf(t)F(t)021（2）负指数分布的特点•负指数分布之所以常用，是因为它有很好的特性，使数学分析变得方便•无记忆性。指的是不管一次服务已经过去了多长时间，该次服务所剩的服务时间仍服从原负指数分布Q.E.D1)1(1)1(1,,,:)(000000000000000ttttteeeethPthPtthPthPtthtPthtthPthtthPthth它的分布函数为则服务剩余时间为代表服务已过去的时间代表服务时间令证22•如果顾客的到达过程服从最简单流，则顾客单位时间内的到达数服从泊松分布。•如果顾客的到达过程服从最简单流，则顾客到达的时间间隔服从负指数分布。•从本质上看，泊松分布与负指数分布是同一个过程的不同表现形式。•可适用于服务时间分布6.3.3小结23()tPhte负指数分布()()ntntPten！泊松分布在单位时间Δt内，到达n个顾客的概率顾客到达时间间隔大于单位时间Δt的概率()1tPhte顾客到达时间间隔小于单位时间Δt的概率λ—顾客的平均到达率24例-1一售货员出售两种商品A和B，每日工作8小时。购买每种商品的顾客到达过程为泊松分布，到达率分别为A=8人/日，B=16人/日，试求：(1)1小时内来到顾客总数为3人的概率；(2)三个顾客全是购买B类商品的概率。解：(1)总到达率为A+B=24人/日，1小时=1/8日，故(2)3个顾客全是购买B类商品的概率为224.0!3)8/124()8/1(8/12433eP0664.0!3)8/116()8/1()8/1(8/188/116303eePPAB25例-2某铁路与公路相交的平面交叉口，当火车通过交叉口时，横木护栏挡住汽车通行。每次火车通过时，平均封锁公路3min，公路上平均每分钟有4辆汽车到达交叉口。求火车通过交叉口时，汽车排队长度超过100m的概率（即排队汽车超过12辆的概率）。26HomeworkP186227•研究系统内部状态变化的过程系统状态i状态i+1状态i-1在Δt时刻内发生两个或两个以上事件的概率为O(Δt)一个事件一个事件Δt→0，O(Δt)→06.4生灭过程（BirthandDeathProcesses）6.4.1定义系统具有0,1,2,……个状态。在任何时刻，若系统处于状态i，并且系统状态随时间变化的过程满足以下条件，称为一个生灭过程：N(t)表示时刻t系统中的顾客数。｛N(t)，t≥0｝为一随机过程。28(1)在（t,t+Δt）内系统由状态i转移到状态i+1的概率为λiΔt+O(Δt)——平稳性条件(2)在（t,t+Δt）内系统由状态i转移到状态i-1的概率为μiΔt+O(Δt)——平稳性条件Δt内有一个顾客离开的概率Δt内有一个顾客到达的概率(3)在（t,t+Δt）内系统发生两次以上转移的概率为O(Δt)，即有2个以上顾客到达或离开的概率为2()0nnPt普遍性条件排队系统的输入过程和服务过程符合泊松分布，则排队过程符合生灭过程29S0S1S2Si-1SiSi+1Sk-1Skμ1μ2μ3μi-1μiμi+1μi+2μk-1μkλ0λ1λ2λi-2λi-1λiλi+1λk-2λk-1……状态（Status）顾客到达率（Birthrate）系统服务率（Deathrate）可以证明：t→∞时，Pi(t)趋向于常数：系统达到稳定6.4.2状态转移图30•系统达到稳定后：每个状态转入率的期望值与转出率的期望值相等。对于状态i：转出率的期望值为iiiiiiiPPP)(转入率的期望值为1111iiiiPPS0S1S2Si-1SiSi+1Sk-1Skμ1μ2μ3μi-1μiμi+1μi+2μk-1μkλ0λ1λ2λi-2λi-1λiλi+1λk-2λk-1……P0P1P2Pi6.4.3状态转移方程31()iiiP1111iiiiPP则对于S00011PP转入转出11kkkkPP转入转出对于SkS0S1S2Si-1SiSi+1Sk-1Skμ1μ2μ3μi-1μiμi+1μi+2μk-1μkλ0λ1λ2λi-2λi-1λiλi+1λk-2λk-1……P0P1P2Pi32()iiiP1111iiiiPP状态转移方程求解该方程，可以获得各状态对应的概率330011PP0101PP对于S0对于S12200111)(PPP0101PP101210212PPP依次类推11201011iiiiiiiiPPP且有01kii