第六章 排队论及其应用

第六章排队论其应第六章排队论及其应用第一节排队现象与排队系统（1）由于顾客到达和服务时间的随机性，现实中的排队现象几乎不可避免；（2）排队过程，通常是一个随机过程，排队论称随机务系统论排队论又称“随机服务系统理论”。二、排队系统二、排队系统（一）排队服务过程排队规则服务规则顾客源排队结构顾客到来顾客离去服务机构。。。顾客到来顾客离去排队系统（二）排队系统的基本要素（二）排队系统的基本要素顾客顾客服务设施、人员排队服务规则（三）服务系统类型（三）服务系统类型损失制（要等待时即离开系统）等待制（等待直到被服务）混合制（等待时间有限度，超过容忍时间限度即离开系统）（四）排队系统组成1、输入过程—顾客到达的规律顾客源：有限、无限顾客到达规律确定型随机型顾客到达规律：确定型、随机型2、排队服务规律2、排队服务规律先到先服务、先到后服务、优先服务、随机服务3、服务机构3、服务机构单通道单通道多通道多通道112121c…c…12c…三排队模型三、排队模型排模型表法(一)排队模型表示方法1、D.G.Kendall(1953)表示法X/Y/ZX/Y/Z——依据排队系统3个主要特征：（）顾客到达间隔时间分布（1）X顾客到达间隔时间分布；（2）Y服务台（员）服务时间分布；（3）Z服务台（员）个数（单个或多个并列）；2、国际排队论标准化会议(1971)表示法2、国际排队论标准化会议(1971)表示法X/Y/Z/A/B/C（1）A系统容量限制；（2）B顾客源（总体）数目（2）B顾客源（总体）数目；（3）C服务规则（FCFS，LCFS等）；——略去后三项，即指“X/Y/Z///FCFS”；——这里仅研究FCFS的情形；(二)到达间隔和服务时间典型分布(二)到达间隔和服务时间典型分布（1）泊松分布M；（2）负指数分布M；（3）k阶爱尔朗分布Ek；（3）k阶爱尔朗分布Ek；（4）确定型分布D；（5）般服务时间分布G（5）一般服务时间分布G；(三)排队模型示例——M/M/1，M/D/1，M/Ek/1；(三)排队模型示例——M/M/c，M/M/c//m，——M/M/c/N/，…M/M/c/N/，…四系统运行指标参数四、系统运行指标参数——评价排队系统的优劣。评价排队系统的优劣。1队长与排队长1、队长与排队长队长:系统中的顾客数，期望值，记为Ls排队长:系统中排队等待服务的顾客数，期望值记为L期望值，记为LqLq=Ls-E[正被服务的顾客数]2、逗留时间与等待时间逗留时间逗留时间:——指一个顾客在系统中的全部停留时间；指个顾客在系统中的全部停留时间；期望值，记为Ws等待时间:指个顾客在系统中的排队等待时间——指一个顾客在系统中的排队等待时间；期望值，记为WqqWs=Wq+E[服务时间]sq其他相关指标3、其他相关指标(1)忙期:指从顾客到达空闲服务机构起到服务(1)忙期:指从顾客到达空闲服务机构起到服务机构再次空闲的时间长度；忙务指个忙内系统均完(2)忙期服务量：指一个忙期内系统平均完成服务的顾客数；服务的顾客数；(3)损失率:指顾客到达排队系统，未接受服务而离去的概率而离去的概率；(4)服务强度：相同时间间隔内顾客的平均达到数与能被服务的平均数的比值。61例6-1：某铁路与公路相交的平面交叉口当火车通过交某铁路与公路相交的平面交叉口，当火车通过交叉口时，横木护栏挡住汽车通行。每次火车通过时，平均封锁公路3min，公路上平均每分钟有4辆汽车到达交叉口。求火车通过交叉口时，汽车排汽车到达交叉口。求火车通过交叉口时，汽车排队长度超过100m的概率（即排队汽车超过12辆的概率）概率）第二节顾客到达分布和服务时间分布第节顾客到分布和服务时间分布系统的组成系统的组成客务机构顾客服务机构顾客到达有先后服务时间有长短存在随机性存在随机性最简单流（泊松流）流的平稳性对任意的在时间区间()对于任意的t≥0及Δt≥0，在时间区间(t,t+Δt)内有n个顾客到达的概率只与Δt有关，与时间区间的起点t无关的起点t无关。当Δt充分小时，在(t,t+Δt)内有一个顾客到达的概率与Δt成正比即概率与Δt成正比，即其中()是当时关于高阶无穷小)(),(1tottttP其中，O(Δt)是当Δt→0时，关于Δt高阶无穷小，λ为单位时间内的顾客到达平均数。流的无后效性在时间轴上互不相交的时间区段和tt在时间轴上，互不相交的时间区段和内，顾客的到达数是21,tt43,tt)(4321tttt内顾客的到达数是相互独立的，即前一顾客的到达不影响后一顾客的到达43,tt)(4321tttt顾客的到达。流的普遍性在同一时刻，有两个及两个以上顾客到达的概率与有一个顾客到达的概率相比小到可以概率与有个顾客到达的概率相比小到可以忽略的程度，即当Δt充分小时，在时间区间(tt+Δt)内有2个及2个以上顾客到达的概率(t,t+Δt)内有2个及2个以上顾客到达的概率是关于的高阶无穷小。)(),(ntotttP2n符合最简单流（泊松流）的随机事件符合最简单流（泊松流）的随机事件发生规律称为泊松分布发生规律称为泊松分布tntP)()(tnenttP！)()(单位时间发生n个随机时间的概率单位时间发个随机时间的概率参数1个：λ—顾客的平均到达率泊松分布的另外一种表达方泊松分布的另外一种表达方式——负指数分布式负指数分布tnt)(tnenttP！)()(若n=0在∆t的时间段内没有顾客达到的概率tetP)(0tethP)(0前后两次随机事件发生的时间间隔大于Δt)(tethP)(tnnenttP！)()(ethP)(负指数分布n！泊松分布泊松分布在单位时间∆t内，发生次随机事件的概率随机事件发生时间间隔大于单位时间Δt的概率n次随机事件的概率大于单位时间Δt的概率tethP1)(随机事件发生时间间隔小于单位时间的概率参数1个：λ—顾客的平均到达率小于单位时间Δt的概率参数1个：λ顾客的平均到达率第三节排队系统的生灭过程生灭过程示意顾客到达——“生”；顾客离开——“灭”顾客离开灭服务机构顾客聚顾客散服务机构顾客聚顾客散顾客到达顾客离去n，n，一生灭过程的定义若排队系统具有下列性质:、生灭过程的定义若排队系统具有下列性质:(1)顾客到达为泊松流，时间间隔服从参()数为n的负指数分布;(2)顾客服务时间服从参数为n的负指数分布数分布;则排队系统的随机过程{N(t)t=0}具有马则排队系统的随机过程{N(t),t=0}具有马尔可夫性质,为一个生灭过程.二、生灭过程状态转移图顾客到达率λλλλλλλλλ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……状态系统服务率时()趋向于常数系统达到稳定t→∞时，Pi(t)趋向于常数：系统达到稳定系统达到稳定后：每个状态转入率的期系统达到稳定后：每个状态转入率的期望值与转出率的期望值相等。对于状态i：转出率的期望值为iiiiiiiPPP)(转入率的期望值为转入率的期望值为1111iiiiPP1111iiiiSSSSSSSSλ0λ1λ2λi-2λi-1λiλi+1λk-2λk-1S0S1S2Si-1SiSi+1Sk-1Skμ1μ2μ3μi-1μiμi+1μi+2μk-1μk……PP0P1P2Pi有P)(1111iiiiPP有iiiP)(1111iiiiPP对于对于对于S0PPPP对于Sk0011PP11kkkkPP转入转出转入转出λ0λ1λ2λi-2λi-1λiλi+1λk-2λk-1S0S1S2Si-1SiSi+1Sk-1Skμ1μ2μ3μi-1μiμi+1μi+2μk-1μk02ii1k2k-1……P0P1P2PiP)(1111iiiiPPiiiP)(1111iiiiPP态转状态转移方程求解该方程，可以获得各状态对应的概率对于S0011PP001PP对于S000111对于S12200111)(PPP0101PP021011212PPP依次类推01102111PPPiiiiiiii11iii且有kiP1i0例：例：某排队系统：M/M/1/3/∞/FCFS，λ=2，μ=3。求解各状态对应的概率。首先做出相应的状态转移图首先，做出相应的状态转移图S0S1S2S32220123333对于S024对于S0对于S10010132PPP002101121294PPPP对于S8PP对于S20327PP31P18420000PPPP01iiP127930000PPPP生灭过程求解排队系统各状态概率过程生灭过程求解排队系统各状态概率过程建立状态转移图各状态转入率期望值建立状态转移方程转与转出率期望值相等建立状态转移方程kiiP01求解状态转移方程i0各状态概率第四节M/M/1排队系统第四节排队系统顾客到达服从泊松分布—顾客到达率为λ服务过程服从泊松分布（负指数分布）系统服务率为μ服务过程服从泊松分布（负指数分布）—系统服务率为μ单通道，先到先服务最简单的M/M/1排队系统：最简单的M/M/1排队系统：M/M/1/∞/∞M/M/1/m/∞////////M/M/1/∞/∞排队系统系统容量无限、顾客源无限系统容量无限、顾客源无限最基本的排队系统排队过程为生灭过程过程λλλλλλλS0S1S2Si-1SiSi+1μμμμμμμ……P0P1P2Pi列状态转移方程组求各状态概率PP01PP001PPP1ii0111PPPPiiiiii01iiP1)1(032PiM/M/1/∞/∞排队系统各状态概率归结为无穷等比数列求和1)1(32Pi归结为无穷等比数列求和1)1(032Piρ1，数列收敛1110PP0=1-ρ系统稳定ρ1数列发散系统稳定系统不稳定ρ1，数列发散系统不稳定称ρ为服务强度，若服务强度大于1，说明单位时间内到达的顾客数比完成服务的顾客数多，系统中排队长度越来越大，产生阻塞。利用排队系统各状态概率计算运行指标利用排队系统各状态概率计算运行指标1队长系统中的顾客数量1、队长——系统中的顾客数量iSiPL队长0iiS队长)1(ii)(10iiiii)2()32(323200ii)10(32)10(12排队长系统中等待的顾客数量2、排队长——系统中等待的顾客数量1)1(iiqiPL通道数11PPiiiii)1(011PLSii1213逗留时间顾客在排队系统中的总时间3、逗留时间——顾客在排队系统中的总时间李太勒公式)1/(SSWL)(SS前后2名顾客到达系统的时间间隔前后2名顾客到达系统的时间间隔/SSLWSS4排队时间顾客在排队系统中的等待时间4、排队时间——顾客在排队系统中的等待时间李太勒公式)1/(qqWL)(qq前后2名顾客到达系统的时间间隔/LW/qqLWM/M/1/m/∞排队系统系统容量有限、顾客源无限λλλλλS2S0S1SiSmμμμμμ……P0P1P2PiPm列状态转移方程组求各状态概率PP01PP001PPP1ii0111PPPPiiiiiimiiP01)(32mi1)1(032