排隊(duì)論講義課件

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

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

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

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

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

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

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

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

就有

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

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

若滿足：

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

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

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

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

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

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

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

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

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

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

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

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

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

Ls=

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

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

排隊(duì)系統(tǒng)分析

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

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

計算有關(guān)指標(biāo)隊(duì)長隊(duì)列長

計算有關(guān)指標(biāo)

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

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

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

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

nun010128229316410566以上1合計100每小時病人平均到達(dá)率（人/小時）每次手術(shù)平均時間（小時/人）每小時完成手術(shù)人數(shù)（平均服務(wù)率）（人/小時）完成手術(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(yùn)-1N求排隊(duì)系統(tǒng)顧客數(shù)的分布狀況其中

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

隊(duì)長隊(duì)列長計算有關(guān)指標(biāo)

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

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

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

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

求有效到達(dá)率

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

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

λ：每個顧客的到達(dá)率，

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

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

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

態(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)移方程得有效到達(dá)率求解顧客數(shù)概率分布

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

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

c(當(dāng)nc)，n(當(dāng)n<c);記=/,s=/c=/c為服務(wù)系統(tǒng)的平均利用率當(dāng)/c<1時，不會排成無限隊(duì)列。4.1標(biāo)準(zhǔn)的M/M/c模型（M/M/c//）12c….服務(wù)臺C個系統(tǒng)人數(shù)n人12c….服務(wù)臺C個系統(tǒng)人數(shù)n人n<=c12c….服務(wù)臺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標(biāo)準(zhǔn)的M/M/c模型（M/M/c//）解差分方程，求得狀態(tài)概率為4.1標(biāo)準(zhǔn)的M/M/c模型（M/M/c//）

顧客等候的概率

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

隊(duì)長隊(duì)列長逗留時間及等待時間計算有關(guān)指標(biāo)唯一

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

=0.9人/分鐘，服務(wù)=0.4人/分鐘。設(shè)顧客到達(dá)后依次排成一隊(duì)向空閑的窗口購票，如圖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,符合要求.整個售票所空閑概率平均隊(duì)長平均等待時間和逗留時間顧客到達(dá)后必須等待概率

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

窗口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)的比較模型指標(biāo)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標(biāo)準(zhǔn)的M/M/c/N/模型狀態(tài)圖是多服務(wù)臺和容量有限的綜合平衡方程你會嗎?4.2標(biāo)準(zhǔn)的M/M/c/N/模型求系統(tǒng)有n位顧客的概率分布4.2標(biāo)準(zhǔn)的M/M/c/N/模型求系統(tǒng)的指標(biāo)有效到達(dá)率平均被占用的服務(wù)臺4.2標(biāo)準(zhǔn)的M/M/c/N/模型求系統(tǒng)的指標(biāo)4.3標(biāo)準(zhǔn)的M/M/c//m模型自學(xué)5.1M/G/1模型5.2M/Ｄ/1模型5.3M/Ek/1模型5.一般服務(wù)時間

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

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

E(V)