第12章 排隊(duì)模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

有一火車售票處，設(shè)有一個售票窗口，顧客到達(dá)為泊松流，平均到達(dá)率為0.3人/分。服務(wù)時間服從負(fù)指數(shù)分布，平均服務(wù)率為0.4人/分，試求服務(wù)系統(tǒng)的各項(xiàng)指標(biāo)和顧客逗留15分鐘以上的概率。解：已知條件1)服務(wù)強(qiáng)度和空閑率2）系統(tǒng)狀態(tài)的概率3）平均隊(duì)長和平均排隊(duì)長4）顧客的停留時間和等待時間5）顧客在系統(tǒng)中停留15分鐘以上的概率§12-3其他馬氏過程排隊(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)無顧客的概率所以顧客到達(dá)后需要等待的概率很容易證明顧客到達(dá)后立即能得到服務(wù)的概率平均空間指標(biāo)和平均時間指標(biāo)平均空間指標(biāo)平均時間指標(biāo)—Little公式關(guān)于Lq的公式的推導(dǎo)關(guān)于平均工作服務(wù)臺數(shù)公式的推導(dǎo)二、M/M/1/N模型1.穩(wěn)態(tài)時的狀態(tài)分布2.M/M/1/N的狀態(tài)分布3.M/M/1/N系統(tǒng)的空間指標(biāo)1）平均隊(duì)長2）平均排隊(duì)長當(dāng)時：當(dāng)=1時：M/M/1/N系統(tǒng)的有效到達(dá)率和時間指標(biāo)1.有效到達(dá)率2.平均時間指標(biāo)指標(biāo)公式的進(jìn)一步討論2)