4-3-生灭过程及排队论

主要内容生灭过程特点稳态分析排队论基础排队过程的基本参数和问题排队问题的分析方法排队问题的Little定律排队问题举例例1M/M/1/∞、例2M/M/1/N例3顾客成批到达的排队问题例4电话交换问题（M/M/N/N）例5M/M/s/∞排队系统、例6M/M/s/k例7机器维修问题生灭过程任何时刻，状态最多只能转移到临近状态若处于0状态，则只能转移到状态1。若在t时刻处于n状态，在(t,t+Δt)间隔内转移到状态（n+1）的概率为λn(t)Δt+o(Δt)转移到状态（n-1）的概率为μn(t)Δt+o(Δt)转移到其他状态的概率为o(Δt)x01nn+1λn(t)Δt+o(Δt)μn(t)Δt+o(Δt)n-10011112222λλ00μ(μλ)λ0Q0μ(μλ)λ生灭过程：稳态分析稳态方程与Σwn=1联立，可解平稳的条件：0≤λn≤μnkknkw(t)q00011n1n1nnnn1n10λwμw0λw(λμ)wμwn110n0n21λλλwwμμμ0011112222λλ00μ(μλ)λ0Q0μ(μλ)λ生灭过程：稳态分析平稳的条件：0≤λn≤μn平衡方程局部平衡方程与Σwn=1联立，得1100n1n1nnμwλwμwλwn110n0n21λλλwwμμμx01nn+1λn(t)Δt+o(Δt)μn(t)Δt+o(Δt)n-10011nnnnn1n1n1n1λw=μwμw+λw=μw+λw生灭过程：实例排队问题(排队论分析)可靠性问题(可靠性分析)：M个元件组成的系统中失效元件数每个元件的正常工作时间服从负指数分布若t时刻有n个元件失效，则在(t,t+Δt)时间间隔内产生一个新的失效元件的概率是λnΔt+o(Δt)，修复一个元件的概率是μnΔt+o(Δt)在(t,t+Δt)间隔内多个元件失效或修复的概率是o(Δt)系统正常工作至少要有k个元件正常工作——当（M-k+1）元件失效时系统就停止工作，等待修复例例排队系统的基本模型A/R/S/N/D：常见为A/R/S，或A/R/S/NA：到达类型R：服务时间分布S：服务者个数N：系统容量（含服务中用户数），默认无限大D：排队规则，FIFO到达排队服务中离开缓冲区服务者排队系统的到达过程到达过程：到达的业务/顾客流构成的随机过程可以用一定间隔内到达的顾客数的分布来表征也可以用顾客到达的时间间隔的分布来表征典型的到达过程：泊松过程一定间隔内到达的顾客数服从泊松分布，到达率λ到达的时间间隔服从负指数分布，平均到达时间1/λ到达缓冲区服务者排队系统的服务时间服务时间：服务器处理每个顾客业务所需的时间是与服务器对具体业务的处理能力有关的随机量一般用处理业务所需的时间的分布来表征典型的服务时间：负指数分布服务时间服从负指数分布，平均服务时间1/μ顾客离开率：μ服务时间缓冲区服务者排队系统的基本问题概率分布特征:系统中顾客数的概率分布（及平均值L）在排队等候的平均顾客数LQ用户在系统中花费时间的概率分布（及平均值W或D）顾客排队等候的平均用时WQ或DQ服务器忙或空闲的概率服务器处于工作状态的持续时间的分布用户因为队列满而离开的概率缓冲区服务者排队问题的Little定律排队系统中普适性的定律，统计量服从的公式对到达过程、服务时间分布、服务规则无特殊要求描述长时间平稳后的系统形式为：L=λ·WL：系统中的平均顾客数λ：平均(有效)到达率W：顾客在系统中所消耗的平均时间WM/M/1或M/M/1/∞排队模型到达系统的顾客数服从泊松分布，参数λ服务时间服从负指数分布，平均服务时间是1/μ只有一个服务器若服务器正忙，则加入排队行列（不限长）服务器空闲时间到达的顾客立刻得到服务服务时间与到达过程独立顾客数组成一个生灭过程顾客到达和离开对应于生灭过程的生和灭任意时刻和状态，到达率和离开率均为相同常数λn=λ，μn=μ01μλ2μλ3μλ4μλμλM/M/1排队模型：应用生灭过程的结论负载因子ρ=λ/μ1的条件下，具有稳态分布：系统中有n个顾客的概率系统平均用户数：用户数的方差：平均延迟：根据little公式D=L/λ轻负载情况下：λ«μ，延迟近似为平均服务时间业务极度繁忙情况下：λ≈μ，几乎无限延迟nnnλλw(1ρ)ρ1μμnn0Lnw1μλ22ρμλ1ρμλn110n0n21λλλwwμμμn0λwμn0ρwnλn0ρμd1ρρρdρρλ1ρμλ典型排队问题：最普通情形M/M/1/∞队列有限M/M/1/NM元件1维修工人批量发生MX/M/1/∞每次三个电话接入M/M/N/NS个侍者M/M/S/∞01μλ2μλ3μλ4μλ5μλμλ01μλ2μλ3μλμλNμλ01μλ2μλSsμλS+1sμλsμλ01μλ2μλN-1(N-1)μλNNμλ01μλ2μ3μ4μλμλλλ01μ2μ(M-1)λ3μμNμλMλ(M-2)λ(M-3)λ稳定状态时，各状态的概率写出Q，列稳态分布方程w’=wQ=0稳态的“概率流”平衡：解得考虑到：M/M/1/∞：01μ1λ02μ2λ13μ3λ2μ4λ30011112222λλ00μ(μλ)λ0Q0μ(μλ)λ0011n1n1nnnn1n10λwμw0λw(λμ)wμwn110n0n21λλλwwμμμnnw1解法12n1n1nnμwλw解得最终结果nn0λwwμnλλ1μμn(1ρ)ρ稳定状态时，系统中的顾客数（分布和均值）M/M/1/∞为例已得wn=(1-ρ)ρn定义母函数：系统中用户数：排队中的用户数：01μλ2μλ3μλμλnn0Lnwnnn0Φ(z)wznnn0(1ρ)ρz1ρ1ρzz1dΦ(z)dz2z1ρ(1ρ)(1ρz)ρ1ρQnn1L(n1)wnnn0n1nwwn0n0nw1wρρ1ρλμλ2λμμλ稳定状态时，顾客的耗时平均值M/M/1/∞母函数平均耗时：在队列中的平均耗时：验证Little定律：延迟时间的分布如何推导？nnn0Φ(z)wz1ρ1ρz01μλ2μλ3μλμλnnin0i0WwET1...μλnnin0i0wETnn01n1wμQnn01Wnwμnn01nwμ1λμμλλLλWμλ2QQλLλWμμλ(μλ)td(t)(μλ)e稳定状态时，L和W与负载的关系轻负载λμ，W≈1/μ，基本呈线性关系负载较重时，系统不稳定负载微小变化都将导致系统滞留顾客数和延迟急剧增加极度繁忙：λ≈μ，几乎无限延迟平均人数L平均延迟W负载因子ρρL1ρLWλλρμM/M/1/N排队模型稳态方程或而ΣWn=1母函数：平均用户数平均排队用户数平均延迟时间平均排队时间可验证符合Little定律n1nwρwnnN11ρwρ1ρ01μλ2μλμλNμλn1nμwλwnnn0Φ(z)wzN1N11ρ1zρ1ρ1zρN1NNnN1n0z1dρ1Nρ(N1)ρLnwΦ(z)dz1ρ1ρNnnn0wzQ0LL1wN1nNn011Wn1w...L1(N1)wμμN1QnNn011Wnw...LNwμμM/M/1/N排队模型阻塞概率：离去概率系统中用户满的情形01μλ2μλμλNμλ定义NNN11ρPρ1ρN=4N=16N=64负载因子ρ阻塞概率电话交换问题（M/M/N/N）概率流平衡阻塞概率：Erlang-B公式例01μλ2μλN-1(N-1)μλNNμλnn1λwwnμn01λwn!μnjNj01λ1λn!μj!μNjNNj01λ1λpN!μj!μM/M/S或M/M/S/∞排队模型平衡流关系：能够平衡的条件：ρ/S1排队概率：Erlang-C公式例01μλ2μλSsμλS+1sμλsμλkk0kk0kS1wρwkSk!ρwwkSS!S0nSS1n01wρρSn!S!SρqnnSP(s,p)w负载因子ρS0SρwS!(Sρ)M/M/S或M/M/S/∞排队模型（续）平均顾客数：平均排队顾客数：平均排队时间：平均延时：或者应用Little定律特殊关系：WQ/Pq=ρ/(S-ρ)01μλ2μλSsμλS+1sμλsμλSnnnn0n0nS1Lnwnwnw...QnnS1L(nS)wnnnSn0nS11μμQnnS1W(nS1)wSμ例S102SρwS!(Sρ)nnnSnS11(nS)wwSμSμ机器维修问题平衡流关系：损坏状态的机器的平均数：等待维修机器数的平均值例01μ2μ(M-1)λ3μμNμλMλ(M-2)λ(M-3)λMM1wρw2M22ρwM0M!ρwMMkk0M!ρM!ρ(Mk)!MMnnn0n1Lnwnw0μM1wλMQn0n1Ln1wL(1w)...