排隊論講義課件

排隊論一.概率論及隨機過程回顧二.排隊論的基本知識三.單服務臺負指數(shù)分布排隊系統(tǒng)分析四.多服務臺負指數(shù)分布排隊系統(tǒng)分析五.一般服務時間M/G/1模型分析六.經(jīng)濟分析___排隊系統(tǒng)的最優(yōu)化

一、概率論及隨機過程回顧隨機變量離散型隨機變量概率分布和概率分布圖數(shù)學期望和方差常見離散型隨機變量的概率分布二點分布?二項式分布?Poisson分布?1.1、隨機變量與概率分布一、概率論及隨機過程復習隨機變量離散型隨機變量概率分布和概率分布圖數(shù)學期望和方差常見離散型隨機變量的概率分布二點分布?二項式分布?Poisson分布?隨機變量連續(xù)型隨機變量概率密度函數(shù)概率分布函數(shù)數(shù)學期望和方差常見連續(xù)型隨機變量的概率分布均勻分布指數(shù)分布？正態(tài)分布？k階愛爾朗分布？一、隨機變量與概率分布隨機變量X為時間間隔，如顧客到達的時間間隔、電話呼叫的時間、產(chǎn)品的壽命等。密度函數(shù)?愛爾朗分布

為k個相互獨立的隨機變量；服從相同參數(shù)的負指數(shù)分布；設，則T的密度函數(shù)為

如k個服務臺串聯(lián)（k個服務階段），一個顧客接受k個服務共需的服務時間T，T愛爾朗分布。1.2隨機過程的有關概念隨機過程(Randomprocess)的定義設，是一族隨機變量，T是一個實數(shù)集，對是一個隨機變量，則稱為隨機過程。

T：參數(shù)集合當T={0,1,…,n,…}時，稱為隨機序列

：隨機過程的一個狀態(tài)狀態(tài)空間E={X(t)全體可能取值，}

隨機過程的基本類型二階矩過程平穩(wěn)過程平穩(wěn)獨立增量過程常見隨機過程馬爾可夫過程？Poisson過程？生滅過程？1.2隨機過程的有關概念定義：若滿足如下性質(zhì)：

對任意非負整數(shù)，只要

就有

則稱具有馬爾可夫性，或無后效性。馬爾可夫過程馬爾可夫鏈離散過去現(xiàn)在將來

“將來”的情況與“過去”無關，只是通過“現(xiàn)在”與“過去”發(fā)生聯(lián)系，若“現(xiàn)在”已知，“將來”與“過去”無關。時齊的馬氏鏈：馬氏鏈

若滿足：

則稱為時齊馬爾可夫鏈—系統(tǒng)由狀態(tài)i經(jīng)過m個時間間隔（或m步）轉(zhuǎn)移到狀態(tài)j的轉(zhuǎn)移概率Poisson過程定義：設為時間內(nèi)到達系統(tǒng)的顧客數(shù)，若滿足下面三個條件：獨立性：在任意兩個不相交的區(qū)間內(nèi)顧客到達的情況相互獨立；平穩(wěn)性：在內(nèi)有一個顧客到達的概率為普通性：在內(nèi)多于一個顧客到達的率為。則稱為Poisson過程。（1）只與區(qū)間長度與起點無關。（2）單位時間內(nèi)一個顧客到達的概率為。Poisson過程與Poisson分布定理1：設為時間內(nèi)到達系統(tǒng)的顧客數(shù)則為Poisson過程的充要條件是數(shù)理統(tǒng)計方法容易初步判斷:期望=標準差Poisson過程與負指數(shù)分布定理2：設為時間內(nèi)到達系統(tǒng)的顧客數(shù)則為參數(shù)為的Poisson過程的充要條件是相繼到達的時間間隔T服從相互獨立的參數(shù)為的負指數(shù)分布。負指數(shù)分布的性質(zhì):馬爾可夫性，或無后效性Poisson過程與Poisson分布的關系：定理1：設為時間內(nèi)到達系統(tǒng)的顧客數(shù)則為Poisson過程的充要條件是定理2：設為時間內(nèi)到達系統(tǒng)的顧客數(shù)則為參數(shù)為的Poisson過程的充要條件是相繼到達的時間間隔T服從相互獨立的參數(shù)為的負指數(shù)分布。對于Poisson流：——單位時間平均到達的顧客數(shù)——顧客相繼到達的平均間隔時間定義：設為一個隨機過程，若N(t)的概率分布具有以下性質(zhì)：(1)假設N(t)=n，則從時刻到下一個顧客到達時刻止的時間服從參數(shù)為的負指數(shù)分布；(2)假設N(t)=n，則從時刻到下一個顧客離開時刻止的時間服從參數(shù)為的負指數(shù)分布；(3)同一時刻是只有一個顧客到達或離去。則稱為一個生滅過程。

生滅過程10nn-1n+1平穩(wěn)生滅過程系統(tǒng)狀態(tài)n平衡方程：“流入=流出”系統(tǒng)達到平穩(wěn)狀態(tài)時：的分布系統(tǒng)達到平穩(wěn)狀態(tài)時：其中平衡方程：當時才有意義二、排隊論的基本知識2.1

排隊模型2.2排隊系統(tǒng)的組成和特征排隊論研究的內(nèi)容性態(tài)問題:排隊系統(tǒng)的概率規(guī)律,如隊長分布,等待時間分布等.最優(yōu)化問題:排隊系統(tǒng)的最優(yōu)設計.統(tǒng)計推斷:判定排隊系統(tǒng)的類型.顧客源2.1、排隊模型排隊系統(tǒng)排隊結(jié)構(gòu)服務機構(gòu)排隊規(guī)則服務規(guī)則接受服務后離去——排隊系統(tǒng)的的一般表示服務機構(gòu)服務臺(a)一個隊列、單服務臺（階段）服務臺1服務臺2(b)一個隊列、s個服務階段服務機構(gòu)服務臺1服務臺2服務機構(gòu)(c)一個隊列、s個服務臺一個服務階段服務臺3服務臺4服務臺1服務臺2服務機構(gòu)(d)s個隊列、s個服務階段服務臺3服務臺4服務臺1服務臺2:1–2–4:2–4–3:3–2–1–4服務機構(gòu)(e)混合型排隊結(jié)構(gòu)服務臺(f)一個隊列服務臺(g)s個隊列

輸入過程顧客總體:有限,無限.顧客到達方式:單個,成批.顧客到達間隔時間:確定的、隨機的.顧客到達的獨立性:獨立,不獨立.輸入過程的平穩(wěn)性:與時間無關(平穩(wěn)的),與時間有關(非平穩(wěn)的).2.2、排隊系統(tǒng)的組成和特征顧客到達時間間隔的分布:：第n個顧客與第n-1個顧客到達的時間間隔；：第n個顧客到達的時刻；設令顧客到達時間間隔的分布:假定是獨立同分布，分布函數(shù)為，排隊論中常用的有兩種：（2）最簡流（即Poisson流）（M）：

顧客到達時間間隔為獨立的，服從負指數(shù)分布，其密度函數(shù)為（1）定長分布（D）：顧客到達時間間隔為確定的。因為負指數(shù)分布具有無后效性（即Markov性）

排隊及排隊規(guī)則即時制(損失制)等待制先到先服務:FCFS后到先服務:LCFS隨機服務優(yōu)先權(quán)服務：PS隊容量:有限,無限;有形,無形.隊列數(shù)目:單列,多列.

服務機構(gòu)服務員數(shù)量:無,單個,多個.隊列與服務臺的組合服務方式:單個顧客,成批顧客.服務時間:確定的,隨機的.服務時間和到達間隔時間至少一個是隨機的.服務時間分布是平穩(wěn)的.服務時間分布:

設某服務臺的服務時間為V，其密度函數(shù)為b（t），常見的分布有：（1）定長分布（D）：每個顧客接受服務的時間是一個確定的常數(shù)。（2）負指數(shù)分布（M）：每個顧客接受服務時間相互獨立，具有相互的負指數(shù)分布：

其中，為一常數(shù)。μ--單位時間平均服務完成的顧客數(shù)1/μ--每個顧客的平均服務時間服務時間分布:（3）k階愛爾朗（Erlang）分布：每個顧客接受服務時間服從k階愛爾朗分布，其密度函數(shù)為：

符號表示:X/Y/ZX--客到達間隔時間分布Y--服務時間分布Z--服務臺個數(shù)X,Y可以是:M--負指數(shù)分布D--確定性的Ek--k階Erlang分布GI--一般相互獨立的到達時間間隔分布G--一般(General)時間分布排隊系統(tǒng)的分類

擴展符號表示:X/Y/Z/A/B/CA--系統(tǒng)容量B--顧客源中顧客的數(shù)量C--服務規(guī)則:FCFS,LCFS,等等.若省略后三項，即是指下面的情形：

X/Y/Z///FCFS例：M/M/s/K表示？

已知:顧客到達間隔時間分布,服務時間分布.求:隊長:Ls--系統(tǒng)中的顧客數(shù).排隊長(隊列長):Lq--隊列中的顧客數(shù).

Ls=

Lq+正在接受服務的顧客數(shù)逗留時間:WS--顧客在系統(tǒng)中的停留時間等待時間:Wq--顧客在隊列中的等待時間.

WS=Wq+服務時間忙期,損失率,服務強度.排隊問題的求解三.單服務臺負指數(shù)分布

排隊系統(tǒng)分析

3.1M/M/1模型3.2M/M/1/N/模型(即系統(tǒng)的容量有限)3.3M/M/1//m模型（即顧客源為有限）顧客源排隊系統(tǒng)排隊結(jié)構(gòu)服務機構(gòu)排隊規(guī)則服務規(guī)則接受服務后離去3.1M/M/1模型無限輸入過程服從參數(shù)為的Poisson過程單隊隊長無限先到先服務服務時間服從參數(shù)為的負指數(shù)分布生滅過程

求解：:系統(tǒng)達到平穩(wěn)后，系統(tǒng)有n個顧客的概率。平衡方程：，且當時其中關于的幾點說明：顧客平均到達率顧客平均服務率一個顧客服務時間一個顧客到達時間——服務強度即顧客的顧客平均到達率小于顧客平均服務率時，系統(tǒng)才能達到統(tǒng)計平穩(wěn)。系統(tǒng)中至少有一個顧客的概率；服務臺處于忙的狀態(tài)的概率；反映系統(tǒng)繁忙程度

計算有關指標隊長隊列長

計算有關指標

逗留時間:可以證明,Ws服從參數(shù)為μ-λ的負指數(shù)分布.則:等待時間計算有關指標計算有關指標Little公式（相互關系）小結(jié)平均服務時間平均在忙的服務臺數(shù)/正在接受服務的顧客數(shù)有效到達率平均忙期B,忙期出現(xiàn)的概率平均閑期I,閑期出現(xiàn)的概率(1-)忙期B:閑期I=:

(1-)平均閑期I=1/閑期的分布與顧客到達時間間隔的相同----服從參數(shù)為的負指數(shù)分布計算有關指標忙期與閑期WHY?1-P0=平均忙期B,忙期出現(xiàn)的概率平均閑期I,閑期出現(xiàn)的概率(1-)忙期B:閑期I=:

(1-)平均閑期I=1/平均忙期B=(/(1-))/=1/(-)計算有關指標忙期與閑期與逗留時間Ws相同!!!?例：某醫(yī)院手術(shù)室每小時就診病人數(shù)和手術(shù)時間的記錄如下：到達的病人數(shù)出現(xiàn)次數(shù)

nun010128229316410566以上1合計100完成手術(shù)時間出現(xiàn)次數(shù)

rvr0.0~0.2380.2~0.4250.4~0.6170.6~0.890.8~1.061.0~1.251.2以上0合計100解：到達的病人數(shù)出現(xiàn)次數(shù)

nun010128229316410566以上1合計100每小時病人平均到達率（人/小時）每次手術(shù)平均時間（小時/人）每小時完成手術(shù)人數(shù)（平均服務率）（人/小時）解：到達的病人數(shù)出現(xiàn)次數(shù)

nun010128229316410566以上1合計100每小時病人平均到達率（人/小時）每次手術(shù)平均時間（小時/人）每小時完成手術(shù)人數(shù)（平均服務率）（人/小時）完成手術(shù)時間出現(xiàn)次數(shù)

rvr0.0~0.2380.2~0.4250.4~0.6170.6~0.890.8~1.061.0~1.251.2以上0合計100解：3.2系統(tǒng)容量有限制的情形

(M/M/1/N/∞/FCFS）狀態(tài)轉(zhuǎn)移圖狀態(tài)轉(zhuǎn)移方程N-1N求排隊系統(tǒng)顧客數(shù)的分布狀況其中

求排隊系統(tǒng)顧客數(shù)的分布狀況

隊長隊列長計算有關指標

逗留時間等待時間計算有關指標系統(tǒng)已滿顧客不能到達的概率---損失率

有6個椅子接待人們排隊，超過6人顧客就離開，平均到達率3人/小時，理發(fā)需時平均15分鐘。Ｎ＝7為系統(tǒng)中的最大顧客數(shù)。平均到達率:＝3人/小時平均服務率:＝4人/小時舉例：單人理發(fā)館排隊問題

顧客到達就能理發(fā)的概率

-------相當于理發(fā)店內(nèi)沒有顧客等待顧客數(shù)的期望值

求有效到達率

顧客在理發(fā)館內(nèi)逗留的期望時間小時分鐘人/小時

可能的顧客中有百分之幾不等待就離開-----求系統(tǒng)中有7個顧客的概率設：m：為顧客總體數(shù)，

λ：每個顧客的到達率，

m-Ls：系統(tǒng)外顧客的平均數(shù)，

λe=λ（m-Ls）：為系統(tǒng)有效到達率。3.3顧客源有限制的情形

(M/M/1/∞/m/FCFS）含義與上節(jié)不同—對顧客而言，而不是對系統(tǒng)m對系統(tǒng)而言,有一個顧客到達的概率狀

態(tài)

轉(zhuǎn)

移

圖01mn-1n(m-n+1)

(m-n)n+1......m-1m...(m-1)2狀態(tài)轉(zhuǎn)移方程注意到，

求解狀態(tài)轉(zhuǎn)移方程得有效到達率求解顧客數(shù)概率分布

等待時間正常運轉(zhuǎn)的平均設備臺數(shù)計算有關指標

隊長隊列長逗留時間計算有關指標例：P343#例74.1標準的M/M/c模型（M/M/c//）4.2標準的M/M/c/N/型4.3標準的M/M/c//m模型四.多服務臺負指數(shù)分布排隊系統(tǒng)分析規(guī)定：各服務臺工作是相互獨立的，且平均服務率相同，均為。整個服務機構(gòu)的平均服務率為：

c(當nc)，n(當n<c);記=/,s=/c=/c為服務系統(tǒng)的平均利用率當/c<1時，不會排成無限隊列。4.1標準的M/M/c模型（M/M/c//）12c….服務臺C個系統(tǒng)人數(shù)n人12c….服務臺C個系統(tǒng)人數(shù)n人n<=c12c….服務臺C個系統(tǒng)人數(shù)n人

n>c狀

態(tài)

轉(zhuǎn)

移

圖01n-1nn(n+1)n+1......22n-1nccn+1......n<=c

n>c狀態(tài)轉(zhuǎn)移方程4.1標準的M/M/c模型（M/M/c//）解差分方程，求得狀態(tài)概率為4.1標準的M/M/c模型（M/M/c//）

顧客等候的概率

計算有關指標平均正接受服務的顧客數(shù)=正忙的服務臺數(shù)解釋?

隊長隊列長逗留時間及等待時間計算有關指標唯一

某售票所有三個窗口，顧客到達服從Poisson過程，到達

=0.9人/分鐘，服務=0.4人/分鐘。設顧客到達后依次排成一隊向空閑的窗口購票，如圖a.

圖a

窗口1=0.4

窗口2=0.4

窗口3=0.4

=0.9M/M/c型系統(tǒng)和c個M/M/1型系統(tǒng)的比較圖aM/M/c型系統(tǒng)和c個M/M/1型系統(tǒng)的比較

窗口1=0.4

窗口2=0.4

窗口3=0.4

=0.3

=0.3

=0.3

=0.9圖b

窗口1=0.4

窗口2=0.4

窗口3=0.4

=0.9屬于M/M/c型系統(tǒng)c=3,=/=2.25,

s=/c=2.25/3<1,符合要求.整個售票所空閑概率平均隊長平均等待時間和逗留時間顧客到達后必須等待概率

以上例說明,設顧客到達后在每個窗口前各排一隊(其它條件不變),共三隊,每隊平均到達率為:

窗口1=0.4

窗口2=0.4

窗口3=0.4

=0.3

=0.3

=0.3

=0.9圖bM/M/c型系統(tǒng)和c個M/M/1型系統(tǒng)的比較模型指標M/M/33個(M/M/1)P0LqLsWsWq必須等待概率0.07481.703.954.39(分鐘)1.89(分鐘)0.570.25(子系統(tǒng))2.25(子)9.00(整)10(分鐘)7.5(分鐘)0.75結(jié)果比較M/M/c型系統(tǒng)和c個M/M/1型系統(tǒng)的比較4.2標準的M/M/c/N/模型狀態(tài)圖是多服務臺和容量有限的綜合平衡方程你會嗎?4.2標準的M/M/c/N/模型求系統(tǒng)有n位顧客的概率分布4.2標準的M/M/c/N/模型求系統(tǒng)的指標有效到達率平均被占用的服務臺4.2標準的M/M/c/N/模型求系統(tǒng)的指標4.3標準的M/M/c//m模型自學5.1M/G/1模型5.2M/Ｄ/1模型5.3M/Ek/1模型5.一般服務時間

M/G/1模型設系統(tǒng)的平均到達率為

，任一顧客的服務時間為V,且有：

E(V)