生滅過程及排隊論課件.ppt

《生滅過程及排隊論課件.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、隨機過程生滅過程及排隊論初步分析主要內(nèi)容生滅過程特點穩(wěn)態(tài)分析排隊論基礎(chǔ)排隊過程的基本參數(shù)和問題排隊問題的分析方法排隊問題的Little定律排隊問題舉例例1M/M/1/∞、例2M/M/1/N例3顧客成批到達的排隊問題例4電話交換問題（M/M/N/N）例5M/M/s/∞排隊系統(tǒng)、例6M/M/s/k例7機器維修問題生滅過程任何時刻，狀態(tài)最多只能轉(zhuǎn)移到臨近狀態(tài)若處于0狀態(tài)，則只能轉(zhuǎn)移到狀態(tài)1。若在t時刻處于n狀態(tài)，在(t,t+Δt)間隔內(nèi)轉(zhuǎn)移到狀態(tài)（n+1）的概率為λn(t)Δt+o(Δt)轉(zhuǎn)移到狀態(tài)（n-1）的概率為μn(t)Δt+o(Δt)轉(zhuǎn)移到其他狀態(tài)的概率為o(Δt)x0

2、1nn+1λn(t)Δt+o(Δt)μn(t)Δt+o(Δt)n-1生滅過程：穩(wěn)態(tài)分析穩(wěn)態(tài)方程與Σwn=1聯(lián)立，可解平穩(wěn)的條件：0≤λn≤μn生滅過程：穩(wěn)態(tài)分析平穩(wěn)的條件：0≤λn≤μn平衡方程局部平衡方程與Σwn=1聯(lián)立，得x01nn+1λn(t)Δt+o(Δt)μn(t)Δt+o(Δt)n-1生滅過程：實例排隊問題(排隊論分析)可靠性問題(可靠性分析)：M個元件組成的系統(tǒng)中失效元件數(shù)每個元件的正常工作時間服從負(fù)指數(shù)分布若t時刻有n個元件失效，則在(t,t+Δt)時間間隔內(nèi)產(chǎn)生一個新的失效元件的概率是λnΔt+o(Δt)，修復(fù)一個元件的概率是μnΔt+o(Δt)在(t,

3、t+Δt)間隔內(nèi)多個元件失效或修復(fù)的概率是o(Δt)系統(tǒng)正常工作至少要有k個元件正常工作——當(dāng)（M-k+1）元件失效時系統(tǒng)就停止工作，等待修復(fù)例例排隊系統(tǒng)的基本模型A/R/S/N/D：常見為A/R/S，或A/R/S/NA：到達類型R：服務(wù)時間分布S：服務(wù)者個數(shù)N：系統(tǒng)容量（含服務(wù)中用戶數(shù)），默認(rèn)無限大D：排隊規(guī)則，F(xiàn)IFO到達排隊服務(wù)中離開緩沖區(qū)服務(wù)者排隊系統(tǒng)的到達過程到達過程：到達的業(yè)務(wù)/顧客流構(gòu)成的隨機過程可以用一定間隔內(nèi)到達的顧客數(shù)的分布來表征也可以用顧客到達的時間間隔的分布來表征典型的到達過程：泊松過程一定間隔內(nèi)到達的顧客數(shù)服從泊松分布，到達率λ到達的時間間隔服從

4、負(fù)指數(shù)分布，平均到達時間1/λ到達緩沖區(qū)服務(wù)者排隊系統(tǒng)的服務(wù)時間服務(wù)時間：服務(wù)器處理每個顧客業(yè)務(wù)所需的時間是與服務(wù)器對具體業(yè)務(wù)的處理能力有關(guān)的隨機量一般用處理業(yè)務(wù)所需的時間的分布來表征典型的服務(wù)時間：負(fù)指數(shù)分布服務(wù)時間服從負(fù)指數(shù)分布，平均服務(wù)時間1/μ顧客離開率：μ服務(wù)時間緩沖區(qū)服務(wù)者排隊系統(tǒng)的基本問題概率分布特征:系統(tǒng)中顧客數(shù)的概率分布（及平均值L）在排隊等候的平均顧客數(shù)LQ用戶在系統(tǒng)中花費時間的概率分布（及平均值W或D）顧客排隊等候的平均用時WQ或DQ服務(wù)器忙或空閑的概率服務(wù)器處于工作狀態(tài)的持續(xù)時間的分布用戶因為隊列滿而離開的概率緩沖區(qū)服務(wù)者排隊問題的Little定律

5、排隊系統(tǒng)中普適性的定律，統(tǒng)計量服從的公式對到達過程、服務(wù)時間分布、服務(wù)規(guī)則無特殊要求描述長時間平穩(wěn)后的系統(tǒng)形式為：L=λ·WL：系統(tǒng)中的平均顧客數(shù)λ：平均(有效)到達率W：顧客在系統(tǒng)中所消耗的平均時間WM/M/1或M/M/1/∞排隊模型到達系統(tǒng)的顧客數(shù)服從泊松分布，參數(shù)λ服務(wù)時間服從負(fù)指數(shù)分布，平均服務(wù)時間是1/μ只有一個服務(wù)器若服務(wù)器正忙，則加入排隊行列（不限長）服務(wù)器空閑時間到達的顧客立刻得到服務(wù)服務(wù)時間與到達過程獨立顧客數(shù)組成一個生滅過程顧客到達和離開對應(yīng)于生滅過程的生和滅任意時刻和狀態(tài)，到達率和離開率均為相同常數(shù)λn=λ，μn=μ01μλ2μλ3μλ4μλμλM/

6、M/1排隊模型：應(yīng)用生滅過程的結(jié)論負(fù)載因子ρ=λ/μ<1的條件下，具有穩(wěn)態(tài)分布：系統(tǒng)中有n個顧客的概率系統(tǒng)平均用戶數(shù)：用戶數(shù)的方差：平均延遲：根據(jù)little公式D=L/λ輕負(fù)載情況下：λ?μ，延遲近似為平均服務(wù)時間業(yè)務(wù)極度繁忙情況下：λ≈μ，幾乎無限延遲典型排隊問題：最普通情形M/M/1/∞隊列有限M/M/1/NM元件1維修工人批量發(fā)生MX/M/1/∞每次三個電話接入M/M/N/NS個侍者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μλ

7、μλλλ01μ2μ(M-1)λ3μμNμλMλ(M-2)λ(M-3)λ穩(wěn)定狀態(tài)時，各狀態(tài)的概率寫出Q，列穩(wěn)態(tài)分布方程w’=wQ=0穩(wěn)態(tài)的“概率流”平衡：解得考慮到：M/M/1/∞：01μ1λ02μ2λ13μ3λ2μ4λ3解法12?解得最終結(jié)果穩(wěn)定狀態(tài)時，系統(tǒng)中的顧客數(shù)（分布和均值）M/M/1/∞為例已得wn=(1-ρ)ρn定義母函數(shù)：系統(tǒng)中用戶數(shù)：排隊中的用戶數(shù)：01μλ2μλ3μλμλ穩(wěn)定狀態(tài)時，顧客的耗時平均值M/M/1/∞母函數(shù)平均耗時：在隊列中的平均耗時：驗證Little定律：延遲時間的分布如何推導(dǎo)？01μλ2μλ3μ