第10章排队论随机服务系统(1)

1第十章排队论—随机服务系统随机服务系统随机服务过程服务时间与间隔时间输入过程生灭过程和纯增过程M/M/n损失制M/M/n等待制，无限源，无限容量M/G/1等待制，无限源，无限容量特殊随机服务系统2随机服务系统系统的输入与输出是随机变量A.k.Erlang于1909~1920年发表了一系列根据话务量计算电话机键配置的方法，为随机服务理论奠定了基础又称为排队论(QueuingTheory)或拥塞理论(CongestionTheory)顾客源三个服务台离去的顾客随机服务系统排队等待顾客...3与服务系统性能相关的特性服务系统存在来自两个矛盾方面的要求z顾客希望服务质量好，如排队等待时间短，损失率低z系统运营方希望设备利用率高给用户一个经济上能够承受的满意的质量哪些系统特性会影响系统的性能？z服务机构的组织方式与服务方式z顾客的输入过程和服务时间分布z系统采用的服务规则一）、服务机构的组织方式与服务方式z单台制和多台制z并联服务z串联服务z串并联服务、网络服务z全利用度、部分利用度4二）、输入过程和服务时间z顾客单个到达或成批到达z顾客到达时间间隔的分布和服务时间的分布z顾客源是有限的还是无限的三）、服务规则z损失制：不允许排队，如电话系统z等待制：可以排队。服务规则分为：先到先服务(FCFS)，这是最通常的情形：后到先服务（LCFS），如信息采集等；优先权服务（PS），如患者就医；随机服务，如电话交换台接通呼唤电话z混合制：是损失制与等待制的结合，即允许排队，但不允许无限制排下去。一般分为：队长有限、等待时间有限、逗留时间有限等三种情况z逐个到达，成批服务；成批到达，逐个服务5以单台服务系统、等待制、先到先服务为例讨论如下顾客在系统中的总时长：逗留时间=等待时长+服务时长等待时长与顾客到达率和服务时长有关顾客到达时刻开始服务时刻服务终结时刻t1234τ1τ2τ3τ4w2w3h1h2h3h4空1234随机服务过程•τi,wi,hi分别表示到达间隔时间，等待时间和服务时间6当服务台连续不断服务(即忙期）时，有如下关系：wi+1+τi+1=wi+hi，（上图中τ4不属于这种情况）wi+hi表示了累计的未完成的服务时长，一般地有⎩⎨⎧≤−+−+−+=++++0τhwif00τhwifτhww1iii1iii1iii1i•α(t)代表时段(0,t)中累计到达顾客数β(t)代表时段(0,t)中累计接受服务的顾客数γ(t)代表时段(0,t)中累计服务完毕的顾客数（离去的顾客数）•则在任意考察时刻t，有正在等待的顾客数：L(t)=α(t)−β(t)正在接受服务的顾客数：Ls(t)=β(t)−γ(t)系统中逗留的顾客数：N(t)=α(t)−γ(t)上述关系是普遍成立的，与服务台设置和服务规则无关7下面分析等待顾客数、等待时间和顾客到达率的关系z到达率定义为单位时间内平均到达的顾客数，即λt=α(t)/tz令δ(t)表示在时段(0,t)内到达系统内顾客的总逗留时长z则每一个顾客的平均逗留时间为Wdt=δ(t)/α(t)z系统中平均逗留顾客数可表达为Ldt=δ(t)/t=(α(t)/t)(δ(t)/α(t))=λtWdt(Littleformula)t系统中逗留顾客数平均逗留顾客数8系统的平稳状态是指：当排队系统运行一段时间后，系统进入正常的平衡状态（简称为稳态），此时，队长分布、等待时间分布等都和系统所处的时刻无关系统处于稳态时的利特尔公式：Ld=λWd利特尔公式也是普遍成立的，已知其中任两个量，可以求出另一个量利特尔公式的分解：Ld=λWd=λ(Wq+h)=Lq+LnLq=λWqLn=λhzWq是顾客的平均排队等待时间zLq是排队等待的平均队长zh是顾客的平均服务时长zLn是同时接受服务的平均顾客数(即服务台平均占用数)9一、概述顾客的服务时间由于多种原因具有不确定性（随机性），最好的描述方法就是概率分布；同样顾客到达的间隔时间也具有一定的概率分布服务时间和到达间隔时间服从什么分布？可以先通过统计得到经验分布，然后再做理论假设和检验经验分布一般采用直方图来表示，如下图频率%3020102468通话分钟服务时间与间隔时间统计区间分得越细，样本越多，经验分布折线越接近分布密度曲线10一般服务时间和间隔时间都是非负的连续型随机变量，令h代表服务时间，τ代表间隔时间，t为给定的时刻，则它们的概率分布函数分别表示为F1(t)=P{h≤t}F2(t)=P{τ≤t}概率密度函数为fi(t)=Fi′(t)，具有性质：fi(t)≥0，∫fi(t)dt=1,且当t＜0时，fi(t)=Fi(t)=0，i=1,2服务时间落在区间(a,c)的概率为{})a(F)c(Fdt)t(fchaP11ca1−==≤∫•　服务时间落在(t,t+Δt)的概率为P{th≤t+Δt}≈f1(t)Δt•　平均服务时长和平均间隔时长∫∫∞∞====0201dt)t(tf]τ[Eτdt)t(tf]h[Eh•　平均服务时长的倒数是服务率，平均间隔时长的倒数是到达率即τλμ11==h11二、常用的概率分布1、定长分布2、负指数分布一类最常用的分布，如上述通话时长，可靠性⎩⎨⎧≥=ltlttF01)(当当1/μdtetμh0t,eμf(t)0t,e1F(t)0tμtμtμ===−=∫∞−−−tlf(t)F(t)1tf(t)F(t)100μ定长分布负指数分布123、爱尔朗分布z一种代表性更广的分布tf(t)01/μk=1k=2k=3k=20k为整数，称为k阶爱尔朗分布，期望值为1/μ，方差为1/kμ2；当k=1时，退化为负指数分布；k→∞时，趋向确定型分布（相应的随机变量退化为常量1/μ）。爱尔朗分布实际上是k个独立同分布的负指数分布随机变量的和的分布，即k个服务台的串联,每个服务台的服务时间相互独立，且平均服务时长均为1/kμ（期望值）,则一顾客走完这k个服务台所需服务时间就服从该分布0t,e1)!(kkt)k(μμf(t)ktμ1k−=−−k增大时，爱尔朗分布的图形逐渐变为对称的,k≥30时，其分布近似于正态分布13三、负指数分布的特点负指数分布有很好的特性，使数学分析变得方便（很多情况下，服务和等待时间用负指数分布描述）无记忆性设服务时间服从负指数分布，则不管一次服务已过去多长时间，该次服务所剩服务时间仍服从原负指数分布{}{}{}{}{}{}{}Q.E.De1)e(11)e(1e1thPthPtthPthPtthtPthtthPthtthPtththtμtμtμ)t(tμ000000000000000-----------）-==≤+≤=+≤=+≤=≤−+时它的分布函数为,则服务剩余时间为,代表服务已过去的时间代表服务时间,令:证0(14一个服从负指数分布的服务，在下一瞬间结束的概率{})tΔ(otΔμ]!3)tΔμ(!2)tΔμ(tΔμ1[1e1thtΔthP32tΔμ00+=+−+−−=−=+≤−L应用无记忆性•在Δt内服务终结的概率只与μ和Δt成正比，与t0无关；因此μ又称为终结率，或离去率•同理，在Δt内服务不终结的概率为1–μΔt+o(Δt)•n个独立同分布(负指数)的服务台同时被占用，在Δt内只有一个服务台终结的概率为o(Δt)tnμΔo(Δt))tμo(Δt))(1Δt(μC1n1n+=+−+−Δ•在Δt内有k1个服务台终结的概率为o(Δt)，称为普通性)tΔ(o))tΔ(otΔμ1())tΔ(otΔμ(Cknkkn=+−+−15即顾客到达的过程，可用相继到达顾客的间隔时间描述，也可以用单位时间内到达的顾客数描述z间隔时间服从定长分布z单位时间内到达的顾客数服从泊松分布(法国数学家Poisson,1837)z间隔时间服从爱尔朗分布z一般独立同分布一、泊松输入过程及其特点(0,t)时间内到达顾客的个数服从泊松（流）分布，若tλkke!k)tλ()t(P−=λ是到达率，期望值为λtk=0，1，2，…输入过程16电话呼叫的到达，商店的顾客到达，十字路口的汽车流，港口到达的船只，机场到达的飞机等所有泊松流问题泊松输入过程的特点（泊松流的定义）(1)平稳性：在一个时间段内，顾客到达数只与时间区间长度有关(2)无后效性（独立性）：不相交的时间区间内所到达的顾客数是独立的(3)普通性：在Δt时间内到达一个顾客的概率为λΔt+o(Δt)，到达两个或两个以上顾客的概率为o(Δt)；即两个顾客不可能同时到达泊松过程具有可加性z即独立的泊松变量的和仍服从泊松分布17泊松输入过程的到达间隔时间为负指数分布z令τ代表间隔时间，则概率P{τt}代表时间区间(0,t)内没有顾客来的概率；由泊松分布可知P0(t)=P{τt}=e−λt，t＞0z故间隔时间τ的分布为P{τ≤t}=1−e−λt,t＞0　二、马尔科夫链马尔科夫链(MarkovChain)又简称马氏链，是一种离散事件随机过程。用数学式表达为P{Xn+1=xn+1|X1=x1,X2=x2,...,Xn=xn}=P{Xn+1=xn+1|Xn=xn}zXn+1的状态只与Xn的状态有关，与Xn前的状态无关，具有无记忆性，或无后效性，又称马氏性z状态转移是一步一步发生的，一步状态转移概率Pij(t)=P{Xn+1=j|Xn=i}18例1、一售货员出售两种商品A和B，每日工作8小时。购买每种商品的顾客到达过程为泊松分布，到达率分别为λA=8人/日，λB=16人/日，试求：(1)1小时内来到顾客总数为3人的概率；(2)三个顾客全是购买B类商品的概率。解：(1)顾客总到达率为λA+λB=24人/日，1小时=1/8日，故(2)3个顾客全是购买B类商品的概率为224.0e!3)8/124()8/1(P8/12433=×=×−0664.0ee!3)8/116()8/1(P)8/1(P8/188/11630A3B=××=×−×−19一种描述自然界生灭现象的数学方法，如细菌的繁殖和灭亡，人口的增减，生物种群的灭种现象，顾客的到达与离去等（见P325定义）采用马氏链z令N(t)代表系统在时刻t的状态（如排队系统中顾客数等），下一瞬间t+Δt系统的状态只能转移到相邻状态，或维持不变，如图所示z三种转移是不相容的，三者必居其一z只有具有无记忆性和普通性的过程(分布)才适用马氏链zPj(t)=P{N(t)=j}代表系统在时刻t处于状态j的概率生灭过程和纯增过程20jjj+1j−1tt+ΔtλjΔt1−(λj+μj)ΔtμjΔt这里λj表示：在状态N(t)=j时，单位时间内到达系统的平均顾客数—新来顾客的平均到达率；μj：在状态N(t)=j时，单位时间内可以服务完的顾客数—整个系统的平均服务率21一、生灭过程的马氏链01j+1njj−1......λ0Δtλj−1ΔtλjΔtλ1ΔtμjΔtμj+1Δtμ1Δtμj−1Δtλn−1ΔtμnΔt1−(λ1+μ1)Δt1−(λj-1+μj-1)Δt1−(λj+μj)Δt1−(λj+1+μj+1)Δt根据马氏链，应用全概率公式，有状态转移概率方程1,,2,1)()1)(()()()(1111−=Δ+Δ−Δ−+Δ+Δ=Δ+++−−njtotttpttpttpttpjjjjjjjjLμλμλ•　另有两个边界方程)()1)(()()(00110tottpttpttpΔ+Δ−+Δ=Δ+λμ)()1)(()()(11tottpttpttpnnnnnΔ+Δ−+Δ=Δ+−−μλ22二、生灭方程的推导过程将上述三个差分方程化为微分方程(t))pμ(λ(t)pμ(t)pλ(t)p1n,1,2,j(t))pμ(λ(t)pμ(t)pλΔt(t)pΔt)(tplimjjj1j1j1j1jjjjj1j1j1j1jjj0Δt+−+=′−=+−+=−+++−−++−−→即L•上述三个方程是动态方程，当系统处于稳态时，系统处于统计平衡状态，即状态概率不随时间变化，从而状态概率导数为0；令上三个方程左侧为0，得稳态方程组)t(pμ)t(pλ)t(p)t(pλ)t(pμ)t(pnn1n1nn00110−=′−=′−−同理有23三、生