排隊論隨機服務系統(tǒng)

1、1 第一節(jié) 第二節(jié) 第三節(jié)2大綱要求：掌握排隊論的基本概念、常見的到達時間間隔分布和服務時間分布特性，生滅過程及穩(wěn)態(tài)概率。單服務臺負指數(shù)分布排隊模型；多服務臺負指數(shù)排隊模型；排隊系統(tǒng)設計的最優(yōu)化重點：掌握m/m/1模型及其應用難點：到達流的穩(wěn)態(tài)概率和系統(tǒng)狀態(tài)轉移概率及其優(yōu)化服務設計自學：m/g/1模型3 排隊論（排隊論（queueing theory)，也稱隨機服務系統(tǒng)，也稱隨機服務系統(tǒng)理論，是運籌學的一個重要分支之一。理論，是運籌學的一個重要分支之一。 1909年，丹麥哥本哈根電子公司電話工程師年，丹麥哥本哈根電子公司電話工程師a. k. erlang的開創(chuàng)性論文的開創(chuàng)性論文“概率論和電話通

2、訊理論概率論和電話通訊理論”標志標志此理論的誕生。排隊論的發(fā)展最早是與電話，通信此理論的誕生。排隊論的發(fā)展最早是與電話，通信中的問題相聯(lián)系的，這些問題到現(xiàn)在仍是排隊論傳中的問題相聯(lián)系的，這些問題到現(xiàn)在仍是排隊論傳統(tǒng)的應用領域。統(tǒng)的應用領域。 近年來在計算機通訊、網(wǎng)絡系統(tǒng)近年來在計算機通訊、網(wǎng)絡系統(tǒng)、交通運輸、醫(yī)、交通運輸、醫(yī)療衛(wèi)生系統(tǒng)、庫存管理、作戰(zhàn)指揮等各領域中均得療衛(wèi)生系統(tǒng)、庫存管理、作戰(zhàn)指揮等各領域中均得到了廣泛的應用。到了廣泛的應用。 各種排隊問題：各種排隊問題：4到達的顧客要求的服務服務機構 機械壞了 修理 修理工人 修理工人 領取配件 管理員 病人 就診 醫(yī)生 打電話 通話 交換臺

3、 文件 打印 打印機 飛機降落 降落 跑道指揮機構 顧客 就餐 服務員 汽車 路口 紅綠燈5 首先看一下一般排隊系統(tǒng)的組成示意圖，不難首先看一下一般排隊系統(tǒng)的組成示意圖，不難發(fā)現(xiàn)排隊系統(tǒng)一般有三個基本組成部分：發(fā)現(xiàn)排隊系統(tǒng)一般有三個基本組成部分：1.1.輸入過輸入過程；程；2.2.排隊規(guī)則；排隊規(guī)則；3.3.服務機構?，F(xiàn)分別說明：服務機構?，F(xiàn)分別說明：排隊結構服務機構顧客源顧客到達排隊規(guī)則服務規(guī)則離去圖1 排 隊系統(tǒng)示意圖6 輸入即為顧客的到達，可有下列情況：輸入即為顧客的到達，可有下列情況： 1）顧客源可能是有限的，也可能是無限的。顧客源可能是有限的，也可能是無限的。 2）顧客是成批到達或是

4、單個到達。顧客是成批到達或是單個到達。 3）顧客到達的間隔時間可能是隨機的或確定的。顧客到達的間隔時間可能是隨機的或確定的。 4）顧客到達可能是相互獨立的或關聯(lián)的。所謂顧客到達可能是相互獨立的或關聯(lián)的。所謂獨立就是以前顧客的到達對以后顧客的到達無影響。獨立就是以前顧客的到達對以后顧客的到達無影響。 5）輸入過程可以是輸入過程可以是平穩(wěn)的平穩(wěn)的（stationarystationary），也），也可以是可以是非平穩(wěn)的非平穩(wěn)的。輸入過程是平穩(wěn)的是指顧客相繼。輸入過程是平穩(wěn)的是指顧客相繼到達的間隔時間分布和參數(shù)（均值、方差）與時間到達的間隔時間分布和參數(shù)（均值、方差）與時間無關；非平穩(wěn)的則是與時間相

5、關，非平穩(wěn)的處理比無關；非平穩(wěn)的則是與時間相關，非平穩(wěn)的處理比較困難。較困難。 7 1）顧客到達后接受服務，服務分為顧客到達后接受服務，服務分為即時制即時制（損失制）和（損失制）和等待制等待制。即時制不允許排隊，不形。即時制不允許排隊，不形成隊列；而對于等待制將會形成隊列，顧客可以成隊列；而對于等待制將會形成隊列，顧客可以按下規(guī)則接收服務：按下規(guī)則接收服務： (1)(1)先到先服務先到先服務 fcfs ;(2)fcfs ;(2)后到先服務后到先服務 lcfs lcfs (3)(3)隨機服務隨機服務rand; rand; （4 4）有優(yōu)先權服務）有優(yōu)先權服務 psps。 2）從隊列的空間可分為有

6、容量限制和無容量從隊列的空間可分為有容量限制和無容量限制。也可分為有形的和抽象的。限制。也可分為有形的和抽象的。 3 3）從隊列數(shù)可分為單列和多列。（多列時包）從隊列數(shù)可分為單列和多列。（多列時包括各列間可以相互轉移、括各列間可以相互轉移、不能相互轉移不能相互轉移；中途可；中途可退出、退出、中途不能退出中途不能退出等。）等。）8 1 1）服務機構分為單服務臺和多服務臺。不同）服務機構分為單服務臺和多服務臺。不同的輸入形式與排隊規(guī)則和服務機構聯(lián)合后形成不的輸入形式與排隊規(guī)則和服務機構聯(lián)合后形成不同的排隊服務機構，如：同的排隊服務機構，如：112n. . .12n。單隊單服務臺多隊多服務臺（并列)

7、單隊多服務臺（并列）12n.12312單隊多服務臺（串列）混合形式9 2) 2)服務方式分為單個顧客服務和成批顧客服務。服務方式分為單個顧客服務和成批顧客服務。 3)3)服務時間分為確定型服務時間分為確定型( (定常時間）和隨機型。定常時間）和隨機型。 4)4)服務時間的分布在這里我們假定是平穩(wěn)的。服務時間的分布在這里我們假定是平穩(wěn)的。 我們研究的問題是：輸入是服從某種分布，我們研究的問題是：輸入是服從某種分布，顧客的到達是相互獨立到達的平穩(wěn)過程；各列顧客的到達是相互獨立到達的平穩(wěn)過程；各列間不能相互轉移、中途不能退出；單個單個地間不能相互轉移、中途不能退出；單個單個地服務方式，服務服從某種分

8、布，服務方式，服務服從某種分布， fcfsfcfs。10最主要的、影響最大的是：最主要的、影響最大的是：顧客相繼到達的間隔時間分布顧客相繼到達的間隔時間分布服務時間的分布服務時間的分布服務臺數(shù)服務臺數(shù)d.g.kendalld.g.kendall，19531953提出了分類法，稱為提出了分類法，稱為kendallkendall記記號號( (適用于并列服務臺適用于并列服務臺),1971),1971又擴展成為：又擴展成為：x/y/z/a/b/cx/y/z/a/b/c11 式中：式中： x 或或y 表示顧客相繼到達時間間隔分布和服表示顧客相繼到達時間間隔分布和服務時間分布的各種分布符號：務時間分布的各

9、種分布符號： m負指數(shù)分布（負指數(shù)分布具有無記憶性，即markov性）； d確定型（deterministic）分布； ekk階愛爾朗分布erlang； g i 一 般 相 互 獨 立 隨 機 分 布 ( g e n e r a l independent)； g 一般隨機分布。12z填寫并列的服務臺數(shù)填寫并列的服務臺數(shù)a排隊系統(tǒng)的最大容量排隊系統(tǒng)的最大容量nb顧客源數(shù)量顧客源數(shù)量m c排隊規(guī)則（排隊規(guī)則（fcfs、lcfs等。本章僅研究等。本章僅研究fcfs的排隊規(guī)則）的排隊規(guī)則） 如如 即為顧客到達時間間隔即為顧客到達時間間隔為負指數(shù)分布，服務時間為負指數(shù)分布，單臺，為負指數(shù)分布，服務時間

10、為負指數(shù)分布，單臺，無限容量，無限源，先到先服務的排隊系統(tǒng)模型。無限容量，無限源，先到先服務的排隊系統(tǒng)模型。13 1.1.排隊系統(tǒng)的統(tǒng)計推斷排隊系統(tǒng)的統(tǒng)計推斷: :即通過對排隊系統(tǒng)主即通過對排隊系統(tǒng)主要參數(shù)的統(tǒng)計推斷和對排隊系統(tǒng)的結構分析，判要參數(shù)的統(tǒng)計推斷和對排隊系統(tǒng)的結構分析，判斷一個給定的排隊系統(tǒng)符合于哪種模型，以便根斷一個給定的排隊系統(tǒng)符合于哪種模型，以便根據(jù)排隊理論進行研究。據(jù)排隊理論進行研究。 2.2.系統(tǒng)性態(tài)問題系統(tǒng)性態(tài)問題: :即研究各種排隊系統(tǒng)的概率即研究各種排隊系統(tǒng)的概率規(guī)律性，主要研究隊長分布、等待時間分布和忙規(guī)律性，主要研究隊長分布、等待時間分布和忙期分布等統(tǒng)計指標期分

11、布等統(tǒng)計指標, ,包括了瞬態(tài)和穩(wěn)態(tài)兩種情形。包括了瞬態(tài)和穩(wěn)態(tài)兩種情形。 3.3.最優(yōu)化問題：即包括最優(yōu)設計最優(yōu)化問題：即包括最優(yōu)設計( (靜態(tài)優(yōu)化靜態(tài)優(yōu)化) )，最優(yōu)運營（動態(tài)優(yōu)化）。最優(yōu)運營（動態(tài)優(yōu)化）。14 統(tǒng)計推斷 最優(yōu)設計 性態(tài)問題 排隊系統(tǒng)研究問題階段示意圖排隊系統(tǒng)研究問題階段示意圖15 求解一般排隊系統(tǒng)問題的目的主要是通過研究排求解一般排隊系統(tǒng)問題的目的主要是通過研究排隊系統(tǒng)運行的隊系統(tǒng)運行的效率指標，估計服務質(zhì)量，確定系統(tǒng)效率指標，估計服務質(zhì)量，確定系統(tǒng)的合理結構和系統(tǒng)參數(shù)的合理值的合理結構和系統(tǒng)參數(shù)的合理值，以便實現(xiàn)對現(xiàn)有，以便實現(xiàn)對現(xiàn)有系統(tǒng)合理改進和對新建系統(tǒng)的最優(yōu)設計等。系

12、統(tǒng)合理改進和對新建系統(tǒng)的最優(yōu)設計等。 認識系統(tǒng)：系統(tǒng)分析；改造系統(tǒng)：設計系統(tǒng)。認識系統(tǒng)：系統(tǒng)分析；改造系統(tǒng)：設計系統(tǒng)。 排隊問題的求解：排隊問題的求解： 1 1、確定或擬合排隊系統(tǒng)顧客到達時間間隔的時間、確定或擬合排隊系統(tǒng)顧客到達時間間隔的時間分布和服務時間分布分布和服務時間分布( (可實測可實測) )。16 2 2、根據(jù)排隊系統(tǒng)對應的理論模型求出用以、根據(jù)排隊系統(tǒng)對應的理論模型求出用以判斷系統(tǒng)運行優(yōu)劣的基本數(shù)量指標的概率分布或判斷系統(tǒng)運行優(yōu)劣的基本數(shù)量指標的概率分布或特征數(shù)。特征數(shù)。 數(shù)量指標主要包括數(shù)量指標主要包括: : (1) (1) 隊長：隊長：系統(tǒng)中的顧客數(shù)，它的數(shù)學期望記為系統(tǒng)中的

13、顧客數(shù)，它的數(shù)學期望記為l ls s 。 隊列長：隊列長：系統(tǒng)中排隊等待服務的顧客數(shù)，它系統(tǒng)中排隊等待服務的顧客數(shù)，它的數(shù)學期望記為的數(shù)學期望記為l lq q 。 系統(tǒng)中顧客數(shù)系統(tǒng)中顧客數(shù)l ls s = =系統(tǒng)中排隊等待服務的顧系統(tǒng)中排隊等待服務的顧客數(shù)客數(shù)l lq q + +正被服務的顧客數(shù)正被服務的顧客數(shù) (2) (2) 逗留時間：逗留時間：指一個顧客在系統(tǒng)中的停留時間，指一個顧客在系統(tǒng)中的停留時間，它的數(shù)學期望記為它的數(shù)學期望記為wsws。 17 等待時間：等待時間：指一個顧客在系統(tǒng)中排隊等待的指一個顧客在系統(tǒng)中排隊等待的時間，它的數(shù)學期望記為時間，它的數(shù)學期望記為wq wq 。逗留時

14、間逗留時間= =等待時間等待時間+ +服務時間服務時間(3)(3)忙期：忙期：指從顧客到達空閑服務機構起到服務指從顧客到達空閑服務機構起到服務機構再次為空閑這段時間長度。（忙期和一個忙機構再次為空閑這段時間長度。（忙期和一個忙期中平均完成服務顧客數(shù)都是衡量服務機構效率期中平均完成服務顧客數(shù)都是衡量服務機構效率的指標，忙期關系到工作強度）的指標，忙期關系到工作強度） 為了計算上述的數(shù)量指標，必須首先計算系為了計算上述的數(shù)量指標，必須首先計算系統(tǒng)狀態(tài)的概率統(tǒng)狀態(tài)的概率 系統(tǒng)狀態(tài)系統(tǒng)狀態(tài)：系統(tǒng)狀態(tài)是指系統(tǒng)中顧客數(shù)。：系統(tǒng)狀態(tài)是指系統(tǒng)中顧客數(shù)。18 狀態(tài)概率狀態(tài)概率：用：用p pn n(t)(t)表示

15、表示, ,即在即在t t時刻系統(tǒng)中有時刻系統(tǒng)中有n n個個顧客的概率，也稱瞬態(tài)概率。它是表述系統(tǒng)的各種顧客的概率，也稱瞬態(tài)概率。它是表述系統(tǒng)的各種性能指標的基礎。性能指標的基礎。 狀態(tài)的可能值：狀態(tài)的可能值： 隊長沒有限制時：隊長沒有限制時：n=0 ，1，2， 隊長有限制時：隊長有限制時：n= 0，1，2，3，n 即時制：服務臺個數(shù)是即時制：服務臺個數(shù)是c時，時，n=0 ，1，c 求解狀態(tài)概率求解狀態(tài)概率p pn n(t)(t)方法：是建立含方法：是建立含p pn n(t)(t)的微的微分差分方程，通過求解微分差分方程得到系統(tǒng)瞬分差分方程，通過求解微分差分方程得到系統(tǒng)瞬態(tài)解，由于瞬態(tài)解一般求出

16、確定值比較困難，即態(tài)解，由于瞬態(tài)解一般求出確定值比較困難，即便求得一般也很難使用。因此我們常常使用它的便求得一般也很難使用。因此我們常常使用它的極限極限( (如果存在的話如果存在的話) )：19nttnp)(plim 穩(wěn)態(tài)的物理意義見右圖，穩(wěn)態(tài)的物理意義見右圖，系統(tǒng)的穩(wěn)態(tài)一般很快都系統(tǒng)的穩(wěn)態(tài)一般很快都能達到，但實際中達不能達到，但實際中達不到穩(wěn)態(tài)的現(xiàn)象也存在。到穩(wěn)態(tài)的現(xiàn)象也存在。值得注意的是求穩(wěn)態(tài)概值得注意的是求穩(wěn)態(tài)概率率p pn n并不一定求并不一定求t的的極限極限,而只需求而只需求p pn n(t)=0 (t)=0 即可。即可。 過渡狀態(tài) 穩(wěn)定狀態(tài) pn t 圖3 排隊系統(tǒng)狀態(tài)變化示意圖

17、稱為穩(wěn)態(tài)稱為穩(wěn)態(tài)(steady state)(steady state)解，或稱統(tǒng)計平衡狀態(tài)解，或稱統(tǒng)計平衡狀態(tài) (statistical equilibrium state)(statistical equilibrium state)的解。的解。20 排隊系統(tǒng)的組成與特征排隊系統(tǒng)的組成與特征 排隊系統(tǒng)的模型分類排隊系統(tǒng)的模型分類 顧客到達間隔時間和服務時間的經(jīng)驗分布與顧客到達間隔時間和服務時間的經(jīng)驗分布與理論分布理論分布 穩(wěn)態(tài)概率穩(wěn)態(tài)概率p pn n的計算的計算 標準的標準的m/m/1m/m/1模型模型( (m/m/1/fcfs)/fcfs) 系統(tǒng)容量有限制的系統(tǒng)容量有限制的模型模型m/m

18、/1/n/fcfs/fcfs 顧客源有限模型顧客源有限模型m/m/1/m/m/ fcfsfcfs 標準的標準的m/m/cm/m/c模型模型m/m/c/fcfs/fcfs21 m/m/c型系統(tǒng)和型系統(tǒng)和c個個m/m/1型系統(tǒng)型系統(tǒng) 系統(tǒng)容量有限制的多服務臺模型系統(tǒng)容量有限制的多服務臺模型(m/m/c/n/) 顧客源為有限的顧客源為有限的多服務臺模型多服務臺模型(m/m/c/m)(m/m/c/m) 一般服務時間的（一般服務時間的（m/g/1m/g/1）模型）模型 pollaczek-khintchine(p-k) 公式公式定長服務時間定長服務時間 m/d/1m/d/1模型模型 愛爾朗服務時間愛爾朗

19、服務時間m/ek/1模型模型 排隊系統(tǒng)優(yōu)化排隊系統(tǒng)優(yōu)化 m/m/1 模型中的最優(yōu)服務率模型中的最優(yōu)服務率 標準的標準的m/m/1 model 系統(tǒng)容量為系統(tǒng)容量為n的情形的情形 m/m/c模型中最優(yōu)服務臺數(shù)模型中最優(yōu)服務臺數(shù)c22 要解決排隊問題，首先要確定排隊系統(tǒng)要解決排隊問題，首先要確定排隊系統(tǒng)的到達間隔時間分布與服務時間分布。的到達間隔時間分布與服務時間分布。要研究到達間隔時間分布與服務時間分要研究到達間隔時間分布與服務時間分布需要首先根據(jù)現(xiàn)有系統(tǒng)原始資料統(tǒng)計布需要首先根據(jù)現(xiàn)有系統(tǒng)原始資料統(tǒng)計出它們的經(jīng)驗分布（見出它們的經(jīng)驗分布（見p315p315319319），然），然后與理論分布擬合

20、，若能對應，我們就后與理論分布擬合，若能對應，我們就可以得出上述的分布情況?？梢缘贸錾鲜龅姆植记闆r。23 經(jīng)驗分布是對排隊系統(tǒng)的某些時間參數(shù)根據(jù)經(jīng)驗分布是對排隊系統(tǒng)的某些時間參數(shù)根據(jù)經(jīng)驗數(shù)據(jù)進行的統(tǒng)計分析，并依據(jù)統(tǒng)計分析結果經(jīng)驗數(shù)據(jù)進行的統(tǒng)計分析，并依據(jù)統(tǒng)計分析結果假設其統(tǒng)計樣本的總體分布，選擇合適的檢驗方假設其統(tǒng)計樣本的總體分布，選擇合適的檢驗方法進行檢驗，當通過檢驗時，我們認為時間參數(shù)法進行檢驗，當通過檢驗時，我們認為時間參數(shù)的經(jīng)驗數(shù)據(jù)服從該假設分布。的經(jīng)驗數(shù)據(jù)服從該假設分布。 分布的擬合檢驗一般采用分布的擬合檢驗一般采用2檢驗。具體參見有檢驗。具體參見有關的概率統(tǒng)計教材內(nèi)容。關的概率統(tǒng)計

21、教材內(nèi)容。24隨機變量：數(shù)隨機變量：數(shù) 隨著實驗的結果的不同而變化隨著實驗的結果的不同而變化 離散型：離散型： 的所有可能只有限或至多可列個的所有可能只有限或至多可列個 連續(xù)型：連續(xù)型： （ ）取值于某個區(qū)間（）取值于某個區(qū)間（a a，b b）分布函數(shù)（連續(xù)）分布函數(shù)（連續(xù)）: : xpxf afbfbap 的概率分布的概率分布(離散): iixpxp i=1,2,311iixp25 數(shù)學期望數(shù)學期望:(離散) e()= 1iiipxdxxxf (連續(xù)) e()= 方差方差: 2eed ee22 = bapbpabp 條件概率條件概率: 密度函數(shù)密度函數(shù):(連續(xù)) dttfxfx 0 xf 1

22、dttf , ,26式中式中為常數(shù)為常數(shù)(0)0)，稱，稱x x服從參數(shù)為服從參數(shù)為的泊松分布。的泊松分布。若在上式中引入時間參數(shù)若在上式中引入時間參數(shù)t t，即令，即令tt代替代替，則有：，則有： 在概率論中，我們曾學過泊松分布，設隨機變在概率論中，我們曾學過泊松分布，設隨機變量為量為x，則有：，則有：!nenxpn n=0,1,2, （1）tnnenttp!)(t0，n=0,1,2, （2）27 (2) (2)式所表示的是與時間有關的隨機變量的概率，式所表示的是與時間有關的隨機變量的概率，這已不是簡單的概率論的知識了，而是一個隨機過這已不是簡單的概率論的知識了，而是一個隨機過程，即泊松過程

23、。程，即泊松過程。 下面我們在一定的假設條件下，推出顧客的到達下面我們在一定的假設條件下，推出顧客的到達過程就是一個泊松過程。過程就是一個泊松過程。 若設若設n(t)n(t)表示在時間區(qū)間表示在時間區(qū)間0,t)0,t)內(nèi)到達的顧客數(shù)內(nèi)到達的顧客數(shù)(t0)(t0)，p pn n(t(t1 1,t,t2 2) )表示在時間區(qū)間表示在時間區(qū)間tt1 1,t,t2 2)(t)(t2 2tt1 1) )內(nèi)內(nèi)有有n(0)n(0)個顧客到達的概率。即：個顧客到達的概率。即： )()(,1221ntntnpttpn （t2t1，n0）28 無后效性（獨立性）：無后效性（獨立性）：各區(qū)間內(nèi)的顧客到達數(shù)相各區(qū)間內(nèi)

24、的顧客到達數(shù)相互獨立，即互獨立，即markovmarkov性。性。. . . . . . . t0 t1 t2 tn-1 tn 平穩(wěn)性：平穩(wěn)性：即對于足夠小的即對于足夠小的tt，在時間區(qū)間，在時間區(qū)間tt，t+t+ t)t)內(nèi)內(nèi)有有1 1個顧客到達的概率為個顧客到達的概率為)()(1tttttp， 當當p pn n(t(t1 1,t,t2 2) )符合于下述三個條件時，我們說顧客到符合于下述三個條件時，我們說顧客到達過程就是泊松過程或者說顧客到達形成普阿松流。達過程就是泊松過程或者說顧客到達形成普阿松流。 普阿松流的三個特性：普阿松流的三個特性： 設表示單位時間內(nèi)有 一個顧客到達的概率29 普

25、通性：普通性：對充分小的對充分小的t,t,在時間區(qū)間在時間區(qū)間 t,t+tt）內(nèi)有內(nèi)有2 2個或個或2 2個以上顧客到達的概率是個以上顧客到達的概率是tt一高階無窮一高階無窮小小. .)(1),(0tottttp 令令t1 1=0,t=0,t2 2=t, =t, 則則p pn n(t(t1 1,t,t2 2)=p)=pn n(0,t)=p(0,t)=pn n(t)(t) 也就是在也就是在t,t+tt,t+t內(nèi)有一個顧客到達的概率與內(nèi)有一個顧客到達的概率與t t無關無關, ,而與而與tt成正比。成正比。 0 0 是常數(shù)，是常數(shù)，稱為概率強度稱為概率強度2)(),(nntotttp 即即 由此知，

26、在由此知，在(t，t+t)t)區(qū)間內(nèi)沒有顧客到達的概率為區(qū)間內(nèi)沒有顧客到達的概率為: :ttttttptttpii)(1),(1),(10 區(qū)間長度為t時有 n個顧客的概率30 為了求為了求pn(t)，即，即pn(0,t)，需要研究它在時刻，需要研究它在時刻t到到t+tt時刻的改變量，也就是要建立時刻的改變量，也就是要建立p pn n(t)(t)的微分方程。的微分方程。 對于區(qū)間對于區(qū)間00，t+t)+t)可以分成可以分成00，t)t)和和tt，t+t)t+t)，其到達總數(shù)是，其到達總數(shù)是n n，不外有下列三種情況：所，不外有下列三種情況：所以有：以有：310，t)t,t+t0,t+t 區(qū)間情

27、形個數(shù)概率個數(shù)概率概率a n pn(t) 0 1-t+ pn(t)(1-t+ (t) (t)b n-1 pn-1(t) 1t pn-1(t)t (t) (t) n-2 pn-2(t) 2 c n-3 pn-3(t) 3 0 p0(t) n32 令令t0t0取極限（并注意初始條件）得：取極限（并注意初始條件）得： 當當n=0時，沒有時，沒有b，c兩種情況，則：兩種情況，則：1)0(0p)()(00tpdttdp (4)(4)()()1)()(1tttpttpttpnnn)()()()()(1tttpttptpttpnnnntttptpttpttpnnnn)()()()()(1)()()(1tpt

28、pdttdpnnn n0 (3)(3)(0)0np33 代初始條件代初始條件(t=0)(t=0)有：有：cct01n c = 0 c = 0ttp)(n0 （3 3）式兩端乘）式兩端乘 e et t 并移項得：并移項得：tetp)(0 (5) （沒有顧客到達的概率）dttptdp)()(00 由上式得：由上式得：cttp)(n0 兩邊積分得：兩邊積分得： 一階臺勞展一階臺勞展開為開為1-1-tt34tntnetpetpdtd)()(1 將將n=1,2,3代入（代入（6）得：）得： 積分得：積分得：11101)()(dtetpetptnttn (6)(6)110011)()(dtetpetptt

29、t (注意利用注意利用(5)式式)tdteettt1011tntntnetpetpedttdp)()()(1tntnntetpetpdttdpe)()()(135 如此繼續(xù)遞推下去得：如此繼續(xù)遞推下去得：tettp! 2)()(22 （2 2個顧客到達的概率）個顧客到達的概率） （n n個顧客到達的概率）個顧客到達的概率）tnnenttp!)()( 即隨機變量即隨機變量n(t)=n服從泊松分布。它的數(shù)學期望服從泊松分布。它的數(shù)學期望和方差為：和方差為：tettp)(1 （1 1個顧客到達的概率）個顧客到達的概率）11011102111)()(dteetdtetpetptttttt2221t36

30、1)0(,)(nxfexf則有 由高等數(shù)學知，若設由高等數(shù)學知，若設.!.! 212nxxxenx 即：即：tkkekt!)(0!)()()(11ntnetnptnenntnn)!1()(11nttennt 令令k=n-1，則：，則：!)()(0kttetnekkt tetetnett)(372121)()!1()()!2()(tntntttennnttttttettett22)() 1()() 1(ttnvar)( 即：即：21221)(!)()()(tntnnettpnnntnn22)()()(tnetnetnvar 同理方差為：同理方差為：211121)()!1()()!1()() 1(

31、)()!1()(tntntntetntnennntnnt38 其概率密度函數(shù)為：其概率密度函數(shù)為：tttedtdftf)( t0t0ttetptf1)(1)(0 t0t0tetp)(0 沒有顧客到達的概率為：沒有顧客到達的概率為： (由（由（5）式而來）式而來) 當輸入過程是當輸入過程是泊泊松流時，我們研究兩顧客相繼松流時，我們研究兩顧客相繼到達的時間間隔的概率分布。到達的時間間隔的概率分布。 設設t t為時間間隔，分布函數(shù)為為時間間隔，分布函數(shù)為f ft t（t t），即：），即： f ft t（t t）=ptt=ptt 此概率等價于在此概率等價于在00，t t）區(qū)間內(nèi)至少有）區(qū)間內(nèi)至少有1

32、 1個顧客個顧客到達的概率到達的概率. .39 由前知，由前知，表示單位時間內(nèi)顧客平均到達數(shù)表示單位時間內(nèi)顧客平均到達數(shù)，這，這里里1/表示顧客到達的平均間隔時間表示顧客到達的平均間隔時間，兩者是吻合的。，兩者是吻合的。 可以證明，間隔時間可以證明，間隔時間t t獨立且服從負指數(shù)分布與顧獨立且服從負指數(shù)分布與顧客到達形成泊松流是等價的?？偷竭_形成泊松流是等價的。 下面我們再談一下服務時間的分布：下面我們再談一下服務時間的分布： 對顧客的服務時間對顧客的服務時間，實際是系統(tǒng)處于忙期時兩，實際是系統(tǒng)處于忙期時兩顧客相繼離開系統(tǒng)的時間間隔，一般地也服從負指顧客相繼離開系統(tǒng)的時間間隔，一般地也服從負指

33、數(shù)分布，即：數(shù)分布，即： 即即t服從負指數(shù)分布，由概率論知它的期望及方差為：服從負指數(shù)分布，由概率論知它的期望及方差為：1te21tvar dxxxfte)(40其中：其中： 表示單位時間內(nèi)能被服務完成的顧客數(shù)表示單位時間內(nèi)能被服務完成的顧客數(shù)，即，即平均服務率。平均服務率。 1/1/ 表示一個顧客的平均服務時間表示一個顧客的平均服務時間。 設設v v1 1, v, v2 2，, v, vk k是是k k個獨立的隨機變量，服從相同個獨立的隨機變量，服從相同參數(shù)參數(shù)k k 的負指數(shù)分布，那么：的負指數(shù)分布，那么：tetf1)(tetf)( ，則，則令令 ，則，則稱為稱為服務強度服務強度。41 串

34、列的串列的k k個服務臺，每臺服務時間相互獨立，服個服務臺，每臺服務時間相互獨立，服從相同的負指數(shù)分布（參數(shù)從相同的負指數(shù)分布（參數(shù)k k ），那么一顧客走完），那么一顧客走完k k個服務臺總共所需要服務時間就服從上述的個服務臺總共所需要服務時間就服從上述的k k階階erlangerlang分布。分布。0)!1()()(1tekktktftkkk 則稱則稱t服從服從k階階愛爾朗分布，其特征值為愛爾朗分布，其特征值為: :1te21ktvar ,kt 21的概率密度是的概率密度是(可以證明可以證明) 當當k=1k=1時，時， erlangerlang分布即為負指數(shù)分布；分布即為負指數(shù)分布； 當當

35、k k增加時，增加時， erlangerlang分布逐漸變?yōu)閷ΨQ的；分布逐漸變?yōu)閷ΨQ的； 當當k k 3030時，時， erlangerlang分布近似于正態(tài)分布；分布近似于正態(tài)分布； 每一個服從每一個服從k k ，因此，因此e(te(ti i)=1/ )=1/ k k ，且，且t ti i之間相互獨立之間相互獨立 b bk k(t)(t) t t k=1k=1 k=2k=2 1/1/ erlangerlang分布曲線分布曲線 k=3k=342 例例: :有易碎物品有易碎物品500500件件, ,由甲地運往乙地由甲地運往乙地, ,根據(jù)以根據(jù)以往統(tǒng)計資料往統(tǒng)計資料, ,在運輸過程中易碎物品按普阿

36、松流發(fā)在運輸過程中易碎物品按普阿松流發(fā)生破碎生破碎, ,其概率為其概率為0.002,0.002,現(xiàn)求現(xiàn)求:1.:1.破碎破碎3 3件物品的概件物品的概率率;2.;2.破碎少于破碎少于3 3件的概率和多于件的概率和多于3 3件的概率件的概率;3.;3.至至少有一件破損的概率少有一件破損的概率. . 解解:1.:1.求破碎求破碎3 3件物品的概率件物品的概率: : =0.002500=1 則則 p(k=3)=(p(k=3)=( 3 3/3/3！)e)e- - =(1=(13 3/3/3！)e)e-1-1=0.0613=0.0613 即物品破碎即物品破碎3 3件的概率為件的概率為6.136.13 2

37、. 2.破碎物品少于破碎物品少于3 3件的概率件的概率: :43 破碎物品少于破碎物品少于3 3件的概率為件的概率為91.9791.97 破碎物品多于破碎物品多于3 3件的概率為件的概率為: :02. 098. 01!1430kkekp 3.3.至少有一件破碎的概率為至少有一件破碎的概率為 pkpk 1=1-(11=1-(1k k/k!)e/k!)e- - =1-(1=1-(10 0/0!)e/0!)e-1-1=0.632=0.6329197. 02111!2120eekkknp44 研究對象為單隊、單服務臺（服務臺數(shù)為研究對象為單隊、單服務臺（服務臺數(shù)為1 1），），包括：包括： （1 1）

38、標準）標準m/m/1m/m/1模型（模型（m/m/1/m/m/1/）；）； （2 2）系統(tǒng)容量有限制（）系統(tǒng)容量有限制（m/m/1/n/m/m/1/n/） （3 3）有限顧客源（）有限顧客源（m/m/1/mm/m/1/m）45 以后各節(jié)將介紹幾個常見的排隊模型。對排隊模以后各節(jié)將介紹幾個常見的排隊模型。對排隊模型，在給定輸入和服務條件下，主要研究系統(tǒng)的下型，在給定輸入和服務條件下，主要研究系統(tǒng)的下述運行指標：述運行指標： (1)(1)系統(tǒng)的平均隊長系統(tǒng)的平均隊長ls(ls(期望值期望值) )和平均隊列長和平均隊列長lqlq期望值；期望值； (2)(2)系統(tǒng)中顧客平均逗留時間系統(tǒng)中顧客平均逗留時

39、間wsws與隊列中平均等與隊列中平均等待時間待時間wqwq； 本節(jié)只研究本節(jié)只研究m/m/1m/m/1模型，下面分三種情況討論：模型，下面分三種情況討論：46 為分析模型，首先要確定在任意時刻為分析模型，首先要確定在任意時刻t t，狀態(tài)，狀態(tài)為為n n（系統(tǒng)中有（系統(tǒng)中有n n個顧客個顧客）的概率的概率p pn n(t)(t)(瞬態(tài)概率瞬態(tài)概率) )，它決定了系統(tǒng)的運行特征。它決定了系統(tǒng)的運行特征。 已知顧客到達服從參數(shù)為已知顧客到達服從參數(shù)為的普阿松過程，服的普阿松過程，服務時間服從參數(shù)為務時間服從參數(shù)為的負指數(shù)分布?，F(xiàn)仍然通過研的負指數(shù)分布?，F(xiàn)仍然通過研究區(qū)間究區(qū)間 t，t+tt）的變化來

40、求解。在間刻）的變化來求解。在間刻t+tt，系統(tǒng)中有系統(tǒng)中有n n個顧客不外乎有下列四種情況（到達或個顧客不外乎有下列四種情況（到達或離去離去2 2個以上的沒列入，是高階無窮?。?。個以上的沒列入，是高階無窮?。?。1、輸入過程：顧客源無限，顧客單個到達，相互獨立，服從普阿松分布，平穩(wěn)；2、排隊規(guī)則：單隊，隊長無限制，fcfs。3、服務機構：單服務臺，各顧客服務時間相互獨立，服從負指數(shù)分布。此外：假設到達時間間隔和服務時間是相互獨立的。 標準的標準的m/m/1m/m/1模型即為模型即為m/m/1/fcfs/fcfs模型模型47區(qū)間(t,t+t)情況時刻t 的顧客 到達 離去時刻t+t的顧客(t,

41、t+t)的概率0, t+t的概率(略去(t)ann1-t+(t)1-t+(t)pn(t)(1-t)(1-t)bn+1n1-t+(t)t+(t)pn+1(t) (1-t)(t)cn-1nt+(t)1-t+(t)pn-1(t) (t)(1-t)dnnt+(t)t+(t)pn(t) (t)(t)48 由于這四種情況是互不相容的，所以由于這四種情況是互不相容的，所以pn(t+t)t)應應是這四項之和，將所有的高階無窮小合并，則有：是這四項之和，將所有的高階無窮小合并，則有：tttptttptttpttpnnnn)1)()()1)(1)()(1)()1 ()(1ttttpn)()()()()()(1)(

42、11ttpttptptttttpnnnn)()()()(11tttpttpnn49)()()()1)(11tttpttptttpnnntttptptpttpttpnnnnn)()()()()()()(11 令令t0t0，得關于，得關于p pn n(t)(t)的微分差分方程：的微分差分方程：)()()()()(11tptptpdttdpnnnn (1) 當當n=0時，只有表中的（時，只有表中的（a）、（）、（b）兩種情況，）兩種情況，因為在較小的因為在較小的tt內(nèi)不可能發(fā)生（內(nèi)不可能發(fā)生（d d）（到達后即離）（到達后即離去），若發(fā)生可將去），若發(fā)生可將tt取小即可。取小即可。50)()1)()

43、1)()(100tttpttpttp )()()(100tptpdttdp (2)對于方程(1)、(2)求解很麻煩，即便求得解也是瞬態(tài)解，無法應用。為此,我們只要求得穩(wěn)態(tài)解即可。 穩(wěn)態(tài)時，pn(t)與時間無關，可以寫成pn， 它對時間的導數(shù)為0，所以由(1)、(2)兩式得：在時刻t系統(tǒng)處于無顧客狀態(tài)，而在t+t時刻內(nèi)又沒有顧客來到系統(tǒng)（必然沒有離去事件）在時刻t系統(tǒng)有一個顧客接受服務，在t+t時刻內(nèi)服務完畢離去，且在t+t時刻內(nèi)又沒有顧客來到系統(tǒng)0)(11nnnppp010pp (3)(3) (4)(4)51 上式即為關于上式即為關于pn的差分方程。由此可得該排隊的差分方程。由此可得該排隊系統(tǒng)

44、的狀態(tài)轉移圖：系統(tǒng)的狀態(tài)轉移圖：012n-1nn+1. .狀態(tài)轉換圖 由（由（4）得：）得：001ppp 其中其中服務強度服務強度 將其代入（將其代入（3）式并令）式并令n=1,2,(也可從狀態(tài)轉移也可從狀態(tài)轉移圖中看出狀態(tài)平衡方程圖中看出狀態(tài)平衡方程)得：得：這種系統(tǒng)狀態(tài)(n)隨時間變化的過程就是生滅過程（birth and death process），它可以描述細菌的生滅過程。520)(120ppp n=10)(020ppp 020202)()(1pppp n=20)(231ppp0)(0230ppp 030302223)()(1pppp53 以此類推以此類推，當，當n=n時，時，00)

45、(pppnnn (5)(5)1 (否則排隊無限遠，無法服務完否則排隊無限遠，無法服務完)10nnp 以及概率性質(zhì)知：以及概率性質(zhì)知：111000ppnn (數(shù)列的極限為 ) 1110pnnp)1 ( (6)(6) 當=1時，似乎好象來一個顧客服務一個顧客，但這是在均衡條件下和所有的顧客的服務時間都相等時，才會出現(xiàn)不存在排隊現(xiàn)象的這種理想的現(xiàn)象。在隨機的情況下，這是不可能的。54 上式就是系統(tǒng)穩(wěn)態(tài)概率，以它為基礎可以上式就是系統(tǒng)穩(wěn)態(tài)概率，以它為基礎可以 算出系算出系統(tǒng)的運行指標。統(tǒng)的運行指標。 (1) 系統(tǒng)中的平均顧客數(shù)（隊長期望值系統(tǒng)中的平均顧客數(shù)（隊長期望值ls）nnnnsnpnl001.)

46、1(.)1 ( 3)1 ( 2)1 (32nn.3322143322nnnn1.32n (01)155ls 即: (7)(7)nnnnqnpnl111) 1() 1(nnnnn111)1 (12sl (8)(8) (3) 顧客在系統(tǒng)中的平均逗留時間顧客在系統(tǒng)中的平均逗留時間ws 顧客在系統(tǒng)中的逗留時間是隨機變量，可以證顧客在系統(tǒng)中的逗留時間是隨機變量，可以證明，它服從參數(shù)為明，它服從參數(shù)為-的負指數(shù)分布，分布函數(shù)的負指數(shù)分布，分布函數(shù) (2) 隊列中等待的平均顧客數(shù)隊列中等待的平均顧客數(shù)lq（隊列長期望值）（隊列長期望值）56 和密度函數(shù)為：和密度函數(shù)為：wewf)(1)(wewf)()()(

47、 （w00） 1wews)(wsls (4) (4)顧客在隊列中的等待時間的期望值顧客在隊列中的等待時間的期望值w wq q 顧客在隊列中的等待時間應為顧客在隊列中的等待時間應為w ws s減去平均服務減去平均服務時間。時間。111wswq)(wqlq57 四個指標的關系為四個指標的關系為(little little 公式公式)： 系統(tǒng)處于空閑狀態(tài)的概率：系統(tǒng)處于空閑狀態(tài)的概率：10p 系統(tǒng)處于繁忙狀態(tài)的概率：系統(tǒng)處于繁忙狀態(tài)的概率：01) 0(pnplslq1swqwwslswqlq1qswwqsll 下標s表示系統(tǒng) 下標q表示隊列583.2 系統(tǒng)容量有限制的系統(tǒng)容量有限制的模型模型 m/m

48、/1/n/fcfs/fcfs 當系統(tǒng)容量最大為當系統(tǒng)容量最大為n n時，排隊系統(tǒng)中多于時，排隊系統(tǒng)中多于n n個的顧個的顧客將被拒絕。當客將被拒絕。當n=1n=1時，即為瞬時制；時，即為瞬時制；nn時，即時，即為容量無限制的情況。為容量無限制的情況。排隊系統(tǒng) 服務臺顧客 n 4 3 2 1被拒絕59 現(xiàn)在研究系統(tǒng)中有現(xiàn)在研究系統(tǒng)中有n n個顧客的概率個顧客的概率p pn n(t).(t). 對于對于p p0 0(t)(t)，前面的（，前面的（2 2）式仍然成立）式仍然成立)()()(100tptpdttdp (2)(2) 對于對于(1)(1)式，當式，當n=1,2,n=1,2,n-1n-1時，

49、也仍能成立。時，也仍能成立。)()()()()(1tptptpdttdpnnnn (1)(1) (n=1,2,(n=1,2,n-1)n-1) 但當?shù)攏=nn=n時，有下面兩種情況：時，有下面兩種情況：60情 況時 刻t的 顧 客區(qū) 間 t, t+ t時 刻t+ t的 顧 客 數(shù)概 率an無 離 去 （ 肯 定 不 到 達 ）npn(t) (1- t)bn-1一 人 到 達 （ 無 離 去 ）npn-1(t) tttpttpttpnnn)()1 ()()(1 )()()(1tptpdttdpnnn (8)(8) 其狀態(tài)轉移圖為其狀態(tài)轉移圖為:012n-1nn+1. .狀態(tài)轉換圖. .n-1n6

50、1 在穩(wěn)態(tài)情況下有：在穩(wěn)態(tài)情況下有：010pp0)(11nnnppp01nnpp (9)(9) 解（解（9）式得：）式得：01pp022pp0ppnn nnnnnnnnnppp000001 而等比數(shù)列而等比數(shù)列10111nnnn621011npnnnp111 (1,nn)(1,nn)(10)(10) 注：當注：當=1=1時，試討論其概率時，試討論其概率p pn n下面計算其運行指標：下面計算其運行指標： (1) 平均隊長平均隊長ls：npnlnnnnnnns01011nnnnn0111111) 1(1nnn (1) 試證=1時,ls=n/263 （2 2）隊列長（期望值）隊列長（期望值）nns

51、nqplpnl10)1 () 1( 有效到達率有效到達率e的引入：的引入： little公式可應用的條件是：其平均到達率公式可應用的條件是：其平均到達率是在系統(tǒng)是在系統(tǒng)有空時有空時的平均到達率。當系統(tǒng)滿員時，就的平均到達率。當系統(tǒng)滿員時，就不能再應用了。要用就應該應用有效到達率。不能再應用了。要用就應該應用有效到達率。 因為系統(tǒng)容量有限，當滿員時，顧客將被拒絕，因為系統(tǒng)容量有限，當滿員時，顧客將被拒絕，因此實際的顧客到達率為因此實際的顧客到達率為0，與，與不一樣，為了求不一樣，為了求其他指標，需要求得有效到達率為其他指標，需要求得有效到達率為e：)1 (nep)1 (0pe可以驗證：可以驗證：

52、64esesqlllesslweqqlw 此種情況此種情況的公式與的公式與前類似，前類似，只有只有l(wèi)s不不同，同，e與與 不同。不同。求求e必須必須先求得先求得p0或或pn才行。才行。1)1 ()1 (0nqssplplw （3 3）顧客逗留時間（期望值）顧客逗留時間（期望值） （4 4）顧客等待時間（期望值）顧客等待時間（期望值）1sqww little公式65例例2某單人理發(fā)館共有六把椅子接待顧客排隊，無座時將離某單人理發(fā)館共有六把椅子接待顧客排隊，無座時將離去，顧客平均到達率為去，顧客平均到達率為3人人/h，理發(fā)時間平均為，理發(fā)時間平均為15分鐘，求：分鐘，求：(1) 求某一顧客到達就能理發(fā)的概率求某一顧客到達就能理發(fā)的概率;(2) 求需要等待的顧客數(shù)的期望值求需要等待的顧客數(shù)的期望值;(3) 求有效到達率求有效到達率;(4) 求一顧客在系統(tǒng)中的逗留時間和排隊時間平均值求一顧客在系統(tǒng)中的逗留時間和排隊時間平均值;(5) 在可能到來的顧客中，有百分之幾不等待就離開？在可能到來的顧客中，有百分之幾不等待就離開？解：解：n=6+1=7，=3=3，=4=42778. 075. 0175. 0111810np (1)(1)11. 275. 0175. 0825. 075. 01) 1(18811nnsnl39. 1)2778. 01 (11. 2)1 (0pllsq