第12章 排隊模型

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

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

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

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

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

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

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

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

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

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

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

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

服務機構——一個服務臺，各顧客的服務時間相互獨立，服從相同的負指數(shù)分布

2.系統(tǒng)狀態(tài)概率分布Pn3.隊長Ls4.排隊長逗留時間分布為:所以平均停留時間:又因為所以平均等待時間：5.平均停留時間Ws和平均等待時間Wq6.指標參數(shù)之間的關系—Little公式三、M/M/1系統(tǒng)舉例：

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