運籌學OR2-Ch13-排隊論課件

1、第十三章 排隊論13-1 M/M/1排隊系統(tǒng)13-2 M/M/C排隊系統(tǒng)13-3 一般服務時間模型13-4 一般服務時間損失制模型 13.1 M/M/1排隊系統(tǒng)系統(tǒng)設定：顧客到達和服務時間隨機；單隊；FIFO一、M/M/1/FIFO顧客平均到達數(shù)；平均服務數(shù)；且令:且注意到：帶入第三章系統(tǒng)穩(wěn)態(tài)概率公式得到系統(tǒng)的狀態(tài)概率表達式為：排隊系統(tǒng)的運行參數(shù)如下：1. 隊長（即在系統(tǒng)中的平均顧客數(shù)） *Page 2 of 28系統(tǒng)中至少有一個顧客的概率（或系統(tǒng)不為空的概率），即系統(tǒng)為忙期的概率 2. 排隊長（即排隊顧客數(shù)） 3. 逗留時間（在系統(tǒng)中耗費時間） （推導略，參見P.325角注） 4. 等待時間

2、（即排隊等候的時間） 這是因為 （每名顧客被服務時間的平均值）。 13.1 M/M/1排隊系統(tǒng)標準型*Page 3 of 28概述四個指標之間的關系為： 除此之外，我們還可以求得：系統(tǒng)內(nèi)顧客多于k 的概率： 在系統(tǒng)中逗留時間大于的概率： 排隊等待時間 的概率 ：逗留時間 的概率 例：汽車平均以每5分鐘一輛的到達率去某加油站加油，并且到達過程構成泊松流。汽車加油時間服從負指數(shù)分布，且平均需要4分鐘。若此加油站只有一臺加油設備，試求1. 加油站里的平均汽車數(shù)；2. 每輛汽車平均等待加油的時間為多少？3. 汽車等待加油時間超過2分鐘的概率為多少？13.1 M/M/1排隊系統(tǒng)標準型*Page 4 of

3、 28解：本題為M/M/1系統(tǒng)。若取單位時間為5分鐘，則：1. 平均汽車數(shù)： （輛）2. 每輛汽車的平均等待時間：（單位時間）=16（分鐘）3. 汽車等待加油時間超過2分鐘的概率： P等待時間2/5=1等待時間2/5=二、有限隊長模型 系統(tǒng)容量限制為N，則排隊顧客最多為N1個，如果顧客數(shù)超過N個，則被拒絕進入系統(tǒng)。根據(jù)系統(tǒng)狀態(tài)轉(zhuǎn)移圖：13.1 M/M/1排隊系統(tǒng)有限隊長*Page 5 of 28由此也得到系統(tǒng)的運行指標如下：（推導略，見盧向華等著運籌學p.317） 13.1 M/M/1排隊系統(tǒng)有限隊長*Page 6 of 28注意到是平均到達率，而PN是顧客被拒絕的概率， (1PN)是顧客被接

4、納的概率。故 是到達系統(tǒng)并被接納的概率，稱之為有效到達率。記為三顧客源有限顧客數(shù)為m，平均每個人的到達率為（注：此處與前述含義不同），系統(tǒng)外的平均數(shù)為 ，有效到達率：典型的例子就是企業(yè)中設備故障修理問題，其狀態(tài)轉(zhuǎn)移圖為：13.1 M/M/1排隊系統(tǒng)有限顧客源*Page 7 of 28每臺設備有正常轉(zhuǎn)移為故障轉(zhuǎn)移率為 m臺設備轉(zhuǎn)移為一臺故障轉(zhuǎn)移率為 由狀態(tài)1轉(zhuǎn)移到狀態(tài)0 轉(zhuǎn)移率為 所以在穩(wěn)態(tài)條件下上述狀態(tài)轉(zhuǎn)移規(guī)律可以描述為： 解此差分方程得： 13.1 M/M/1排隊系統(tǒng)有限顧客源*Page 8 of 28系統(tǒng)的運行參數(shù)為： 平均正常運轉(zhuǎn)臺數(shù)： 13.1 M/M/1排隊系統(tǒng)有限顧客源*Page

5、9 of 28作業(yè)：教材Lets take break.Would you like coffee or tea?Help yourself please.*Page 10 of 2813.2 M/M/C排隊系統(tǒng)4.2.1. 標準M/M/C模型(M/M/n/FIFO)系統(tǒng)穩(wěn)態(tài)概率及等待概率有c個服務臺，彼此獨立，顧客到達率為，平均服務率相同為。整個服務系統(tǒng)的平均服務率為c(nc)或n (nc) 令 (平均服務強度)，只有 時才能形成穩(wěn)定局面。按上述狀態(tài)轉(zhuǎn)移圖有： 且有：*Page 11 of 28解之得系統(tǒng)狀態(tài)概率及運行指標為：13.2 M/M/C排隊系統(tǒng)標準型*Page 12 of 28例：

6、某車站售票處有三個售票口，顧客以泊松流到達，到達率為 ；售票員的服務時間為負指數(shù)分布，每個服務的服務率為 ；另顧客排成一隊依次購票。求1。系統(tǒng)的運行參數(shù)。2。購票人數(shù)超過3人的概率。3。與排成3隊購票比較。解：1. 系統(tǒng)運行指標：13.2 M/M/C排隊系統(tǒng)標準型*Page 13 of 283. 與 相比較 必須等待的概率為：0.8313.2 M/M/C排隊系統(tǒng)標準型*Page 14 of 284.2.2 混合制，無限源令從顧客源來的顧客到達率為 ，每臺的服務率為 則有 j = , j=0,1, . , N1; N=0， j = j, 當jc; j=c,當jc, j=1, . , N將j ,

7、j 代入生滅方程，得13.2 M/M/C排隊系統(tǒng)有限隊長*Page 15 of 28特別地，當 時，系統(tǒng)為損失制，這時當nc時，系統(tǒng)的到達率為 零。帶入到穩(wěn)態(tài)概率公式的：當N=c時，排隊系統(tǒng)已滿，顧客被拒絕的概率為Pc，并且有：例題：教材P.336*Page 16 of 2813.2.3 顧客源有限模型，到達率按每個顧客考慮； 時，均在服務， 個工人閑著； 時， 個顧客等待服務。 13.2 M/M/C排隊系統(tǒng)有限顧客源*Page 17 of 2813.2 M/M/C排隊系統(tǒng)有限顧客源平均設備故障數(shù)： ；等待修理設備數(shù)： ；有效到達率： ，其它運行參數(shù)：例題：教材P. 337 例8*Page 1

8、8 of 28作業(yè)：教材13.2 M/M/C排隊系統(tǒng)Take a break*Page 19 of 2813.3 一般服務時間模型以上七個變數(shù)只要知道其中三個就可以求出其余四個。在容量有限和顧客源有限時，要換成有效到達率 。假設：1.輸入為泊松流;2.無限隊長，無限源；3 單隊；4 FIFO；5 單服務員；6 服務時間T任意分布，均值E T ，方差為Var( T )；7 到達時間間隔大于期望服務時間。則總有下面的關系式成立：13.3.1 M/G/1一般服務時間模型*Page 20 of 28令 ，應用嵌入馬爾可夫鏈分析可得Pollaczek-Khintchine(P-K)公式：且有：13.3.

9、2 M/D/1 定長服務時間模型到達率為，服務率是常數(shù)，方差為0， ，則有：且有：例題：教材P.339例1013.3.3 M/E/1 愛爾朗服務時間模型*Page 21 of 2813.3.3 M/E/1 愛爾朗服務時間模型 此模型所描述的是更為普遍的現(xiàn)象。負指數(shù)服務和定長服務都可以看作是愛爾朗服務時間模型的特例。 此模型描述的是k個環(huán)節(jié)串聯(lián)服務的過程，并且k個環(huán)節(jié)的服務相互獨立，服從相同的參數(shù)為k的負指數(shù)分布。12kkk 設 是k個獨立隨機變量，服從k的負指數(shù)分布。 服從k階愛爾朗分布，則有：*Page 22 of 28對每個k期望值都一樣，單方差隨k的增加而減少。當k=1時為負指數(shù)分布；當

10、k時， 。例題：教材P. 340例1113.3.3 M/E/1 愛爾朗服務時間模型*Page 23 of 2813.4 一般服務時間M/G/c/c/ 損失制模型 這是一種有c個服務臺一般服務時間的損失制模型，當系統(tǒng)滿時，后來的顧客不再進入系統(tǒng)。該模型要解決的主要問題是在服務機構的空閑與顧客的流失之間找到平衡，找出最合適的服務臺數(shù)，使得該系統(tǒng)效益最大。典型的應用系統(tǒng)有：電話中轉(zhuǎn)系統(tǒng)、民航電話訂票系統(tǒng)等。由于損失制，故不存在排隊顧客的數(shù)目Lq及WS，這里給出系統(tǒng)里有幾個顧客的概率Pn和在系統(tǒng)里的平均顧客數(shù)Ls 。（推導略）*Page 24 of 28為顧客的平均到達率，為平均服務率，c為服務臺數(shù)。

11、其中Pc為系統(tǒng)里正好有c個顧客的概率，也就是系統(tǒng)里c個服務臺都被顧客占滿的概率。例題：某電器商場開展了電話訂貨業(yè)務，據(jù)統(tǒng)計分析電話到達過程服從泊松分布，平均到達率為每小時16個，而一個接話員處理訂貨事宜的時間是隨著訂貨的產(chǎn)品、規(guī)格、數(shù)量及顧客的不同而變化的，但平均每個人每小時可以處理8個訂貨電話，在此電器商場里安裝了一臺電話自動交換臺，它接到電話后可以接到任一個空閑的接話員的電話上。試問該商場應該安裝多少臺接話員的電話，使得訂貨電話占線而損失的概率不超過10% 。13.4 一般服務時間M/G/c/c/ 損失制模型 *Page 25 of 28解：這是一個損失值的M/G/c/c/模型。當c=3時，我們來計算M/G/3/3/系統(tǒng)中正好有3位顧客的概率，這時c=n=3，用上述公式計算得：這也就是說，當設置三個接受訂貨的電話時，三個電話都被占滿的概率為21.05%，這時別的電話就打不進來損失到了，也就是在這個系統(tǒng)了因電話占線而損失的概率為21.05%，超過了10%的要求，顯然不合要求。如果設置4個訂貨電話，這時c=4，在M/G/4/4/系統(tǒng)中，正好有4位顧客的概率為：13.4 一般服務時間M/G/c/c/ 損失制模型 *Page 26 of 28