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

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

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

4、納的概率。故 是到達(dá)系統(tǒng)并被接納的概率，稱之為有效到達(dá)率。記為三顧客源有限顧客數(shù)為m，平均每個(gè)人的到達(dá)率為（注：此處與前述含義不同），系統(tǒng)外的平均數(shù)為 ，有效到達(dá)率：典型的例子就是企業(yè)中設(shè)備故障修理問題，其狀態(tài)轉(zhuǎn)移圖為：13.1 M/M/1排隊(duì)系統(tǒng)有限顧客源*Page 7 of 28每臺(tái)設(shè)備有正常轉(zhuǎn)移為故障轉(zhuǎn)移率為 m臺(tái)設(shè)備轉(zhuǎn)移為一臺(tái)故障轉(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排隊(duì)系統(tǒng)有限顧客源*Page 8 of 28系統(tǒng)的運(yùn)行參數(shù)為： 平均正常運(yùn)轉(zhuǎn)臺(tái)數(shù)： 13.1 M/M/1排隊(duì)系統(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排隊(duì)系統(tǒng)4.2.1. 標(biāo)準(zhǔn)M/M/C模型(M/M/n/FIFO)系統(tǒng)穩(wěn)態(tài)概率及等待概率有c個(gè)服務(wù)臺(tái)，彼此獨(dú)立，顧客到達(dá)率為，平均服務(wù)率相同為。整個(gè)服務(wù)系統(tǒng)的平均服務(wù)率為c(nc)或n (nc) 令 (平均服務(wù)強(qiáng)度)，只有 時(shí)才能形成穩(wěn)定局面。按上述狀態(tài)轉(zhuǎn)移圖有： 且有：*Page 11 of 28解之得系統(tǒng)狀態(tài)概率及運(yùn)行指標(biāo)為：13.2 M/M/C排隊(duì)系統(tǒng)標(biāo)準(zhǔn)型*Page 12 of 28例：

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

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

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

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

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

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