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

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

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

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

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

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

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

對任意非負整數，只要

就有

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

“將來”的情況與“過去”無關，只是通過“現在”與“過去”發生聯系，若“現在”已知，“將來”與“過去”無關。時齊的馬氏鏈：馬氏鏈

若滿足：

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

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

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

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

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

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

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

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

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

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

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

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

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

Ls=

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

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

排隊系統分析

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

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

計算有關指標隊長隊列長

計算有關指標

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

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

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

nun010128229316410566以上1合計100完成手術時間出現次數

rvr0.0~0.2380.2~0.4250.4~0.6170.6~0.890.8~1.061.0~1.251.2以上0合計100解：到達的病人數出現次數

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

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

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

(M/M/1/N/∞/FCFS）狀態轉移圖狀態轉移方程N-1N求排隊系統顧客數的分布狀況其中

求排隊系統顧客數的分布狀況

隊長隊列長計算有關指標

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

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

顧客到達就能理發的概率

-------相當于理發店內沒有顧客等待顧客數的期望值

求有效到達率

顧客在理發館內逗留的期望時間小時分鐘人/小時

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

λ：每個顧客的到達率，

m-Ls：系統外顧客的平均數，

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

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

態

轉

移

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

(m-n)n+1......m-1m...(m-1)2狀態轉移方程注意到，

求解狀態轉移方程得有效到達率求解顧客數概率分布

等待時間正常運轉的平均設備臺數計算有關指標

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

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

n>c狀

態

轉

移

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

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

顧客等候的概率

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

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

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

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

圖a

窗口1=0.4

窗口2=0.4

窗口3=0.4

=0.9M/M/c型系統和c個M/M/1型系統的比較圖aM/M/c型系統和c個M/M/1型系統的比較

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

M/G/1模型設系統的平均到達率為

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

E(V)