第12章 排隊(duì)模型

第12章排隊(duì)模型§12-1概述§12-2(M/M/1):(∞/∞/FCFS)模型§12-3其他馬氏過(guò)程排隊(duì)模型§12-4兩個(gè)非馬氏排隊(duì)模型§12-1概述一、排隊(duì)過(guò)程的一般表示

到達(dá)的顧客要求服務(wù)內(nèi)容服務(wù)機(jī)構(gòu)1．不能運(yùn)轉(zhuǎn)的機(jī)器2．修理技工3．病人4．電話呼喚5．交件稿6．提貨單7．到達(dá)機(jī)場(chǎng)上空的飛機(jī)8．駛?cè)敫劭诘呢洿?．上游河水進(jìn)入水庫(kù)10．進(jìn)入我方陣地的敵機(jī)修理領(lǐng)取修配零件診斷或動(dòng)手術(shù)通話打字提取存貨降落裝（卸）貨放水，調(diào)整水位我方高射炮進(jìn)行射擊修理技工發(fā)放修配零件的管理員醫(yī)生(或包括手術(shù)臺(tái))交換臺(tái)打字員倉(cāng)庫(kù)管理員跑道裝（卸）貨碼頭(泊位)水閘管理員我方高射炮排隊(duì)系統(tǒng)舉例：二、排隊(duì)系統(tǒng)的組成和特征輸入過(guò)程、排隊(duì)規(guī)則、服務(wù)機(jī)構(gòu)

1.輸入過(guò)程:指各種類型的“顧客”按怎樣的規(guī)律到來(lái)指數(shù)分布(M)：又稱最簡(jiǎn)單流，在長(zhǎng)為t的時(shí)間區(qū)間內(nèi)到達(dá)n個(gè)顧客的概率服從波松分布，即或者說(shuō)顧客相繼到達(dá)間隔時(shí)間T服從負(fù)指數(shù)分布：k階愛(ài)爾朗輸入(Ek):到達(dá)間隔相互獨(dú)立，具有相同的愛(ài)爾朗分布密度：

2.排隊(duì)規(guī)則損失制：又稱即時(shí)制。顧客到達(dá)時(shí)，若所有服務(wù)臺(tái)被占用，該顧客就自動(dòng)消失，永不再來(lái)等待制：顧客到達(dá)時(shí)，若所有的服務(wù)臺(tái)被占用，就排隊(duì)等候:等待服務(wù)的次序可以采用下列規(guī)則：先到先服務(wù)(FCFS):即按照到達(dá)次序接受服務(wù)，這是最通常的情況后到先服務(wù)(LCFS):例如將鋼板堆入倉(cāng)庫(kù)看成是顧客到來(lái)，需要時(shí)將它們陸續(xù)取走看成是服務(wù)，則一般是先取最上面的，也就是最后放上的鋼板隨機(jī)服務(wù)(SIRO):服務(wù)機(jī)構(gòu)從等待的顧客中隨機(jī)地選一個(gè)進(jìn)行服務(wù)優(yōu)先權(quán)服務(wù)(PR):如危重病人可掛急診、加急電報(bào)優(yōu)先發(fā)送等混合制：損失制與等待制兼而有之的情況。假定服務(wù)系統(tǒng)的容量有限,最多只能容納k個(gè)顧客,那么當(dāng)顧客到達(dá)時(shí)，發(fā)現(xiàn)服務(wù)系統(tǒng)已經(jīng)占滿,該顧客將自動(dòng)消失,否則就進(jìn)入服務(wù)系統(tǒng)3.服務(wù)機(jī)構(gòu)

服務(wù)臺(tái)的個(gè)數(shù)可以是一個(gè)或幾個(gè);幾個(gè)服務(wù)臺(tái)可以是并聯(lián)或串聯(lián);可以是單位個(gè)服務(wù),也可以是成批服務(wù)

定長(zhǎng)服務(wù)(D):每一個(gè)顧客的服務(wù)時(shí)間都是常數(shù)β，此時(shí)服務(wù)時(shí)間v的分布函數(shù)為負(fù)指數(shù)分布(M):

即各個(gè)顧客的服務(wù)時(shí)間相互獨(dú)立，具有相同的負(fù)指數(shù)分布：K階愛(ài)爾朗分布(Ek)：各個(gè)顧客的服務(wù)時(shí)間相互獨(dú)立，具有相同的愛(ài)爾朗分布，其密度函數(shù)為：一般分布（G）：它的到達(dá)間隔相互獨(dú)立，且都具有相同的概率分布三、排隊(duì)系統(tǒng)的符號(hào)表示

1.D.G.Kendall于1953年提出用符號(hào)（A/B/C）來(lái)表示排隊(duì)模型的特征A——顧客相繼到達(dá)間隔時(shí)間的概率分布B——服務(wù)時(shí)間的概率分布C——并列的服務(wù)臺(tái)的數(shù)目（或稱通道數(shù)）例如:M/Ek/1表示相繼到達(dá)間隔時(shí)間為負(fù)指數(shù)分布，服務(wù)時(shí)間服從k階愛(ài)爾朗分布，單服務(wù)臺(tái)的模型

A：顧客相繼到達(dá)間隔時(shí)間的概率分布B：服務(wù)時(shí)間的概率分布C：并列的服務(wù)臺(tái)數(shù)d：排隊(duì)系統(tǒng)的容量，即系統(tǒng)允許的最大顧客數(shù)e：顧客總體（顧客源）的數(shù)目f：服務(wù)規(guī)則例如∶(M/M/1):(∞/∞/FCFS)排隊(duì)模型表示顧客相繼到達(dá)間隔時(shí)間和服務(wù)時(shí)間服從負(fù)指數(shù)分布，單服務(wù)臺(tái)，系統(tǒng)能容納無(wú)限個(gè)顧客，顧客源為無(wú)限源，排隊(duì)服務(wù)規(guī)則是先到先服務(wù)。2.國(guó)際通用形式：

3.排隊(duì)系統(tǒng)的主要運(yùn)行指標(biāo)L——系統(tǒng)期望顧客數(shù)(系統(tǒng)中等待服務(wù)的顧客數(shù)）的期望值，又稱隊(duì)長(zhǎng)Lq——系統(tǒng)期望排隊(duì)顧客數(shù),指一個(gè)顧客從到達(dá)系統(tǒng)起到接受服務(wù)后離開系統(tǒng)為止所花費(fèi)的時(shí)間的期望值,又稱排隊(duì)長(zhǎng)W——顧客在系統(tǒng)的期望停留時(shí)間

Wq——顧客在系統(tǒng)的期望等待時(shí)間§12-2(M/M/1):(∞/∞/FCFS)模型一、生滅過(guò)程1.生滅過(guò)程的定義(1)假定有一堆細(xì)菌,每一細(xì)菌在時(shí)間內(nèi)分裂成兩個(gè)的概率為；而在內(nèi)死亡的概率為，各個(gè)細(xì)菌在任何時(shí)段內(nèi)分裂或死亡都是相互獨(dú)立的。如果將細(xì)菌的分裂或死亡都看成發(fā)生一個(gè)事件的話，當(dāng)足夠小時(shí)，發(fā)生兩個(gè)或兩個(gè)以上事件的概率為。假定初始時(shí)刻細(xì)菌的個(gè)數(shù)已知，則經(jīng)過(guò)時(shí)間t后，細(xì)菌變成了多少？這是生滅過(guò)程的例子，不少排隊(duì)過(guò)程是和這個(gè)過(guò)程相仿的。(2)設(shè)為一個(gè)隨機(jī)過(guò)程，隨機(jī)變量的取值集合為或，這個(gè)集合也稱為狀態(tài)集，設(shè)在時(shí)刻t時(shí)，在時(shí)刻時(shí)，的概率為,其中為與t無(wú)關(guān)的常數(shù)；在時(shí)刻時(shí)，的概率為，其中也是與t無(wú)關(guān)的常數(shù)；在時(shí)刻時(shí)，為S中其它元素的概率均為。滿足上述條件的隨機(jī)過(guò)程稱為生滅過(guò)程。(3)生滅過(guò)程具有無(wú)后效性，故也是一個(gè)馬爾柯夫過(guò)程(4)把具有生滅過(guò)程特征的排隊(duì)模型稱為馬氏過(guò)程排隊(duì)模型。二、M/M/1模型的運(yùn)行指標(biāo)1.應(yīng)滿足下列條件：輸入過(guò)程——顧客源是無(wú)限的，顧客按普阿松流到達(dá)排隊(duì)系統(tǒng)

排隊(duì)規(guī)則——單隊(duì)，隊(duì)長(zhǎng)沒(méi)有限制，先到先服務(wù)

服務(wù)機(jī)構(gòu)——一個(gè)服務(wù)臺(tái)，各顧客的服務(wù)時(shí)間相互獨(dú)立，服從相同的負(fù)指數(shù)分布

2.系統(tǒng)狀態(tài)概率分布Pn3.隊(duì)長(zhǎng)Ls4.排隊(duì)長(zhǎng)逗留時(shí)間分布為:所以平均停留時(shí)間:又因?yàn)樗云骄却龝r(shí)間：5.平均停留時(shí)間Ws和平均等待時(shí)間Wq6.指標(biāo)參數(shù)之間的關(guān)系—Little公式三、M/M/1系統(tǒng)舉例：

有一火車售票處，設(shè)有一個(gè)售票窗口，顧客到達(dá)為泊松流，平均到達(dá)率為0.3人/分。服務(wù)時(shí)間服從負(fù)指數(shù)分布，平均服務(wù)率為0.4人/分，試求服務(wù)系統(tǒng)的各項(xiàng)指標(biāo)和顧客逗留15分鐘以上的概率。解：已知條件1)服務(wù)強(qiáng)度和空閑率2）系統(tǒng)狀態(tài)的概率3）平均隊(duì)長(zhǎng)和平均排隊(duì)長(zhǎng)4）顧客的停留時(shí)間和等待時(shí)間5）顧客在系統(tǒng)中停留15分鐘以上的概率§12-3其他馬氏過(guò)程排隊(duì)模型一、M/M/C模型二、M/M/1/N模型三、M/M/C/N模型四、M/M/1/N/N模型(不講)五、M/M/C/N/N

模型(不講)一、M/M/C

模型系統(tǒng)的參數(shù)為設(shè)因此系統(tǒng)狀態(tài)分布系統(tǒng)無(wú)顧客的概率所以顧客到達(dá)后需要等待的概率很容易證明顧客到達(dá)后立即能得到服務(wù)的概率平均空間指標(biāo)和平均時(shí)間指標(biāo)平均空間指標(biāo)平均時(shí)間指標(biāo)—Little公式關(guān)于Lq的公式的推導(dǎo)關(guān)于平均工作服務(wù)臺(tái)數(shù)公式的推導(dǎo)二、M/M/1/N模型1.穩(wěn)態(tài)時(shí)的狀態(tài)分布2.M/M/1/N的狀態(tài)分布3.M/M/1/N系統(tǒng)的空間指標(biāo)1）平均隊(duì)長(zhǎng)2）平均排隊(duì)長(zhǎng)當(dāng)時(shí)：當(dāng)=1時(shí)：M/M/1/N系統(tǒng)的有效到達(dá)率和時(shí)間指標(biāo)1.有效到達(dá)率2.平均時(shí)間指標(biāo)指標(biāo)公式的進(jìn)一步討論2)