排隊(duì)論及其模型

1、1運(yùn)籌學(xué)運(yùn)籌學(xué)2排隊(duì)論排隊(duì)論也稱隨機(jī)服務(wù)系統(tǒng)理論(Random Service System Theory)，是為研究和解決具有擁擠現(xiàn)象的問題而發(fā)展起來的一門應(yīng)用數(shù)學(xué)的分支。 具體地說，它是在研究各種排隊(duì)系統(tǒng)概率規(guī)律性的基礎(chǔ)上，解決相應(yīng)排隊(duì)系統(tǒng)的最優(yōu)設(shè)計(jì)和最優(yōu)控制問題。3排隊(duì)論排隊(duì)論 排隊(duì)論是1909年由丹麥工程師愛爾朗(A.KErlang)在研究電活系統(tǒng)時創(chuàng)立的，幾十年來排隊(duì)論的應(yīng)用領(lǐng)域越來越廣泛，理論也日漸完善。特別是自二十世紀(jì)60年代以來，由于計(jì)算機(jī)的飛速發(fā)展，更為排隊(duì)論的應(yīng)用開拓了寬闊的前景。4排隊(duì)論排隊(duì)論 研究內(nèi)容包括三個部分：n (1) (1) 排隊(duì)系統(tǒng)的性態(tài)問題排隊(duì)系統(tǒng)的性態(tài)問題

2、n (2) (2) 排隊(duì)系統(tǒng)的最優(yōu)化問題排隊(duì)系統(tǒng)的最優(yōu)化問題n (3) (3) 排隊(duì)系統(tǒng)的統(tǒng)計(jì)推斷問題排隊(duì)系統(tǒng)的統(tǒng)計(jì)推斷問題性態(tài)問題，即研究各種排隊(duì)系統(tǒng)的概率規(guī)性態(tài)問題，即研究各種排隊(duì)系統(tǒng)的概率規(guī)律性，主要研究隊(duì)長分布、等待時間分布和律性，主要研究隊(duì)長分布、等待時間分布和忙期分布等。忙期分布等。最優(yōu)化，又分靜態(tài)最優(yōu)和動態(tài)最優(yōu)，前者最優(yōu)化，又分靜態(tài)最優(yōu)和動態(tài)最優(yōu)，前者指最優(yōu)設(shè)計(jì)，后者指現(xiàn)有排隊(duì)系統(tǒng)的最優(yōu)運(yùn)指最優(yōu)設(shè)計(jì)，后者指現(xiàn)有排隊(duì)系統(tǒng)的最優(yōu)運(yùn)營。營。統(tǒng)計(jì)推斷，即判斷一個給定的排隊(duì)系統(tǒng)符統(tǒng)計(jì)推斷，即判斷一個給定的排隊(duì)系統(tǒng)符合哪種模型，以便根據(jù)排隊(duì)理論進(jìn)行研究。合哪種模型，以便根據(jù)排隊(duì)理論進(jìn)行研究。

3、解排隊(duì)問題的目的，是研究排隊(duì)系統(tǒng)運(yùn)行的效率，估計(jì)服務(wù)質(zhì)量，確定系統(tǒng)參數(shù)的最優(yōu)值，以決定系統(tǒng)結(jié)構(gòu)是否合理，研究設(shè)計(jì)改進(jìn)措施等。5排隊(duì)論排隊(duì)論n第1節(jié) 基本概念n第2節(jié) 到達(dá)間隔的分布和服務(wù)時間的分布n第3節(jié) 單服務(wù)臺負(fù)指數(shù)分布排隊(duì)系統(tǒng)的分析n第4節(jié) 多服務(wù)臺負(fù)指數(shù)分布排隊(duì)系統(tǒng)的分析n第5節(jié) 一般服務(wù)時間M/G/1模型n第6節(jié) 經(jīng)濟(jì)分析系統(tǒng)的最優(yōu)化n第7節(jié) 分析排隊(duì)系統(tǒng)的隨機(jī)模擬法6第第1節(jié)節(jié) 基基 本本 概概 念念 v1.1 排隊(duì)過程的一般表示v1.2 排隊(duì)系統(tǒng)的組織和特征v1.3 排隊(duì)模型的分類v1.4 排隊(duì)問題的求解7 不同的顧客與服務(wù)組成了各式各樣的服務(wù)系統(tǒng)。顧客為了得到某種服務(wù)而到達(dá)系統(tǒng)

4、、若不能立即獲得服務(wù)而又允許排隊(duì)等待，則加入隊(duì)列排隊(duì)等待接受服務(wù)，然后服務(wù)臺按一定規(guī)則從隊(duì)列中選擇顧客進(jìn)行服務(wù)，獲得服務(wù)的顧客立即離開系統(tǒng)。1.1 排隊(duì)過程的一般表示排隊(duì)過程的一般表示81.1 排隊(duì)過程的一般表示排隊(duì)過程的一般表示v各個顧客由顧客源(總體)出發(fā)，到達(dá)服務(wù)機(jī)構(gòu)(服務(wù)臺、服務(wù)員)前排隊(duì)等候接受服務(wù)，服務(wù)完成后離開。v排隊(duì)結(jié)構(gòu)指隊(duì)列的數(shù)目和排列方式，排隊(duì)規(guī)則和服務(wù)規(guī)則是說明顧客在排隊(duì)系統(tǒng)中按怎樣的規(guī)則、次序接受服務(wù)的。排隊(duì)過程的一般模型排隊(duì)過程的一般模型91.1 排隊(duì)過程的一般表示排隊(duì)過程的一般表示到達(dá)的顧客到達(dá)的顧客要求服務(wù)內(nèi)容要求服務(wù)內(nèi)容服務(wù)機(jī)構(gòu)服務(wù)機(jī)構(gòu)1.不能運(yùn)轉(zhuǎn)的機(jī)器2.修理

5、技工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) 10 實(shí)際的排隊(duì)系統(tǒng)雖然千差萬別，但是它們 有以下的共同特征： (1)有請求服務(wù)的人或物顧客； (2)有為顧客服務(wù)的人或物，即服務(wù)員或服務(wù)臺； (3)顧客到達(dá)系統(tǒng)的時刻是隨機(jī)的，為每一位顧客提供服務(wù)的時間是隨機(jī)的，因而整個排隊(duì)系統(tǒng)的狀態(tài)也是隨機(jī)的

6、。排隊(duì)系統(tǒng)的這種隨機(jī)性造成某個階段顧客排隊(duì)較長，而另外一些時候服務(wù)員(臺)又空閑無事。1.2 排隊(duì)系統(tǒng)的組成和特征排隊(duì)系統(tǒng)的組成和特征 111.2 排隊(duì)系統(tǒng)的組成和特征排隊(duì)系統(tǒng)的組成和特征 v排隊(duì)系統(tǒng)由三個基本部分組成： 輸入過程輸入過程 排隊(duì)規(guī)則排隊(duì)規(guī)則 服務(wù)機(jī)構(gòu)服務(wù)機(jī)構(gòu)121.2 排隊(duì)系統(tǒng)的組成和特征排隊(duì)系統(tǒng)的組成和特征 輸入過程輸入過程v輸入即指顧客到達(dá)排隊(duì)系統(tǒng)。輸入過程是指要求服務(wù)的顧客是按怎樣的規(guī)律到達(dá)排隊(duì)系統(tǒng)的過程，有時也把它稱為顧客流。v一般可以從以下幾個方面來描述個輸入過程(1) 顧客的總體數(shù)，又稱顧客源、顧客的總體數(shù)，又稱顧客源、輸入源。這是指顧客的輸入源。這是指顧客的來源。

7、來源。 顧客源可以是有限的，也可以是無限的。顧客源可以是有限的，也可以是無限的。 例如，到售票處購票的顧客總數(shù)可以認(rèn)為是無限的，例如，到售票處購票的顧客總數(shù)可以認(rèn)為是無限的，而某個工廠因故障待修的機(jī)床則是有限的。而某個工廠因故障待修的機(jī)床則是有限的。131.2 排隊(duì)系統(tǒng)的組成和特征排隊(duì)系統(tǒng)的組成和特征 輸入過程輸入過程(2) 顧客到來的方式。顧客到來的方式。這是描述顧客是怎樣來到系統(tǒng)的，這是描述顧客是怎樣來到系統(tǒng)的，他們是單個到達(dá)，還是成批到達(dá)。他們是單個到達(dá)，還是成批到達(dá)。 病人到醫(yī)院看病是顧客單個到達(dá)的例子。在庫存問題病人到醫(yī)院看病是顧客單個到達(dá)的例子。在庫存問題中如將生產(chǎn)器材進(jìn)貨或產(chǎn)品入

8、庫看作是顧客，那么這中如將生產(chǎn)器材進(jìn)貨或產(chǎn)品入庫看作是顧客，那么這種顧客則是成批到達(dá)的。種顧客則是成批到達(dá)的。141.2 排隊(duì)系統(tǒng)的組成和特征排隊(duì)系統(tǒng)的組成和特征 輸入過程輸入過程(3)(3)顧客流的概率分布，或稱相繼顧客到達(dá)的時間間隔的分顧客流的概率分布，或稱相繼顧客到達(dá)的時間間隔的分布。這是求解排隊(duì)系統(tǒng)有關(guān)運(yùn)行指標(biāo)問題時，首先需要布。這是求解排隊(duì)系統(tǒng)有關(guān)運(yùn)行指標(biāo)問題時，首先需要確定的指標(biāo)。這也可以理解為在一定的時間間隔內(nèi)到達(dá)確定的指標(biāo)。這也可以理解為在一定的時間間隔內(nèi)到達(dá)K K個顧客個顧客( (K K=1=1、2 2、) )的概率是多大。的概率是多大。 顧客相繼到達(dá)的間隔時間可以是確定型的

9、，也可以是隨機(jī)顧客相繼到達(dá)的間隔時間可以是確定型的，也可以是隨機(jī)型的。型的。 顧客流的概率分布一般有定長分布、二項(xiàng)分布、泊松流顧客流的概率分布一般有定長分布、二項(xiàng)分布、泊松流( (最簡單流最簡單流) )、愛爾朗分布等若干種。、愛爾朗分布等若干種。151.2 排隊(duì)系統(tǒng)的組成和特征排隊(duì)系統(tǒng)的組成和特征 輸入過程輸入過程(4) 顧客的到達(dá)可以是相互獨(dú)立的。顧客的到達(dá)可以是相互獨(dú)立的。(5) 輸入過程可以是平穩(wěn)的，或稱對時間是齊次的，即描輸入過程可以是平穩(wěn)的，或稱對時間是齊次的，即描述相繼到達(dá)的間隔時間分布和所含參數(shù)述相繼到達(dá)的間隔時間分布和所含參數(shù)(如期望值、方如期望值、方差等差等)都是與時間無關(guān)的

10、。都是與時間無關(guān)的。161.2 排隊(duì)系統(tǒng)的組成和特征排隊(duì)系統(tǒng)的組成和特征 排隊(duì)規(guī)則排隊(duì)規(guī)則 v這是指服務(wù)臺從隊(duì)列中選取顧客進(jìn)行服務(wù)的順序。一般可以分為損失制、等待制和混合制等3大類。v(1)損失制。這是指如果顧客到達(dá)排隊(duì)系統(tǒng)時，所有服務(wù)臺都已被先來的顧客占用，那么他們就自動離開系統(tǒng)永不再來。典型例子是，如電話拔號后出現(xiàn)忙音，顧客不愿等待而自動掛斷電話，如要再打，就需重新拔號，這種服務(wù)規(guī)則即為損失制。 171.2 排隊(duì)系統(tǒng)的組成和特征排隊(duì)系統(tǒng)的組成和特征 排隊(duì)規(guī)則排隊(duì)規(guī)則 (2)等待制。這是指當(dāng)顧客來到系統(tǒng)時，所有服務(wù)臺都不空，顧客加入排隊(duì)行列等待服務(wù)。例如，排隊(duì)等待售票，故障設(shè)備等待維修等。

11、對于等待制，為顧客進(jìn)行服務(wù)的次序可以采用下列各種規(guī)則：先到先服務(wù)先到先服務(wù)(FCFS)后到先服務(wù)后到先服務(wù)(LCFS)隨機(jī)服務(wù)隨機(jī)服務(wù)(RS)有優(yōu)先權(quán)的服務(wù)有優(yōu)先權(quán)的服務(wù)181.2 排隊(duì)系統(tǒng)的組成和特征排隊(duì)系統(tǒng)的組成和特征 排隊(duì)規(guī)則排隊(duì)規(guī)則 (2)等待制。 對于等待制，為顧客進(jìn)行服務(wù)的次序可以采用下列各種規(guī)則： 先到先服務(wù)。按顧客到達(dá)的先后順序?qū)︻櫩瓦M(jìn)行服務(wù)，這是最普遍的情形。 后到先服務(wù)。倉庫中迭放的鋼材，后迭放上去的都先被領(lǐng)走，就屬于這種情況。 隨機(jī)服務(wù)。即當(dāng)服務(wù)臺空閑時，不按照排隊(duì)序列而隨意指定某個顧客去接受服務(wù)，如電話交換臺接通呼叫電話就是一例。 優(yōu)先權(quán)服務(wù)。如老人、兒童先進(jìn)車站；危重

12、病員先就診；遇到重要數(shù)據(jù)需要處理計(jì)算機(jī)立即中斷其他數(shù)據(jù)的處理等，均屬于此種服務(wù)規(guī)則。191.2 排隊(duì)系統(tǒng)的組成和特征排隊(duì)系統(tǒng)的組成和特征 排隊(duì)規(guī)則排隊(duì)規(guī)則 (3)混合制這是等待制與損失制相結(jié)合的一種服務(wù)規(guī)則，一般是指允許排隊(duì)，但又不允許隊(duì)列無限長下去。具體說來，大致有三種： 隊(duì)長有限。當(dāng)排隊(duì)等待服務(wù)的顧客人數(shù)超過規(guī)定數(shù)量時，后來的顧客就自動離去，另求服務(wù)，即系統(tǒng)的等待空間是有限的。例如最多只能容納K個顧客在系統(tǒng)中，當(dāng)新顧客到達(dá)時，若系統(tǒng)中的顧客數(shù)(又稱為隊(duì)長)小于K，則可進(jìn)入系統(tǒng)排隊(duì)或接受服務(wù)；否則，便離開系統(tǒng)，并不再回來。如水庫的庫容是有限的，旅館的床位是有限的。201.2 排隊(duì)系統(tǒng)的組成和

13、特征排隊(duì)系統(tǒng)的組成和特征 排隊(duì)規(guī)則排隊(duì)規(guī)則 (3)混合制 隊(duì)長有限。 等待時間有限。即顧客在系統(tǒng)中的等待時間不超過某一給定的長度T，當(dāng)?shù)却龝r間超過T時，顧客將自動離去，并不再回來。如易損壞的電子元器件的庫存問題，超過一定存儲時間的元器件被自動認(rèn)為失效。又如顧客到飯館就餐，等了一定時間后不愿再等而自動離去另找飯店用餐。211.2 排隊(duì)系統(tǒng)的組成和特征排隊(duì)系統(tǒng)的組成和特征 排隊(duì)規(guī)則排隊(duì)規(guī)則 (3)混合制 隊(duì)長有限。 等待時間有限。 逗留時間(等待時間與服務(wù)時間之和)有限。例如用高射炮射擊敵機(jī)，當(dāng)敵機(jī)飛越高射炮射擊有效區(qū)域的時間為t時，若在這個時間內(nèi)未被擊落，也就不可能再被擊落了。 不難注意到，損失

14、制和等待制可看成是混合制的特殊情形，如記s為系統(tǒng)中服務(wù)臺的個數(shù)，則當(dāng)K=s時，混合制即成為損失制；當(dāng)K=時，混合制即成為等待制。221.2 排隊(duì)系統(tǒng)的組成和特征排隊(duì)系統(tǒng)的組成和特征 排隊(duì)規(guī)則排隊(duì)規(guī)則 （續(xù)）v從允許排隊(duì)的空間看隊(duì)列可以排在具體的處所，也可以是抽象的。隊(duì)列可以排在具體的處所，也可以是抽象的。排隊(duì)空間可以有限，也可以無限。排隊(duì)空間可以有限，也可以無限。v從排隊(duì)的隊(duì)列數(shù)目看，可以是單列單列，也可以是多列多列。在多列的情形，各列間的顧客有的可以互相轉(zhuǎn)移，有的不能。在多列的情形，各列間的顧客有的可以互相轉(zhuǎn)移，有的不能。有的排隊(duì)顧客因等候時間過長而中途退出，有的不能退出，有的排隊(duì)顧客因等候

15、時間過長而中途退出，有的不能退出，必須堅(jiān)持到被服務(wù)為止。必須堅(jiān)持到被服務(wù)為止。231.2 排隊(duì)系統(tǒng)的組成和特征排隊(duì)系統(tǒng)的組成和特征 服務(wù)機(jī)構(gòu)服務(wù)機(jī)構(gòu) (服務(wù)臺情況)服務(wù)臺可以從以下3方面來描述：(1) 服務(wù)臺數(shù)量及構(gòu)成形式。服務(wù)機(jī)構(gòu)可以沒有服務(wù)員，也可以有一個或多個服務(wù)員(服務(wù)臺、通道、窗口等)。從數(shù)量上說，服務(wù)臺有單服務(wù)臺和多服務(wù)臺之分。在有多個服務(wù)臺的情形中，可以是平行排列的，也可以是前后排列的，或混合排列的。241.2 排隊(duì)系統(tǒng)的組成和特征排隊(duì)系統(tǒng)的組成和特征 服務(wù)機(jī)構(gòu)服務(wù)機(jī)構(gòu) (服務(wù)臺情況)服務(wù)臺可以從以下3方面來描述：(1) 服務(wù)臺數(shù)量及構(gòu)成形式。從構(gòu)成形式上看，服務(wù)臺有： 單隊(duì)單服

16、務(wù)臺式；如(a)圖 單隊(duì)多服務(wù)臺并聯(lián)式；如(c)圖 多隊(duì)多服務(wù)臺并聯(lián)式；如(b)圖 單隊(duì)多服務(wù)臺串聯(lián)式；如(d)圖 單隊(duì)多服務(wù)臺并串聯(lián)混合式； 多隊(duì)多服務(wù)臺并串聯(lián)混合式等等。服務(wù)臺的各服務(wù)臺的各種排列方式種排列方式25單隊(duì)列S個服務(wù)臺并聯(lián)的排隊(duì)系統(tǒng)S個隊(duì)列S個服務(wù)臺的并聯(lián)排隊(duì)系統(tǒng)1.2 排隊(duì)系統(tǒng)的組成和特征排隊(duì)系統(tǒng)的組成和特征 26單隊(duì)多個服務(wù)臺的串聯(lián)排隊(duì)系統(tǒng) 多隊(duì)多服務(wù)臺混聯(lián)、網(wǎng)絡(luò)系統(tǒng)1.2 排隊(duì)系統(tǒng)的組成和特征排隊(duì)系統(tǒng)的組成和特征 271.2 排隊(duì)系統(tǒng)的組成和特征排隊(duì)系統(tǒng)的組成和特征 服務(wù)機(jī)構(gòu)服務(wù)機(jī)構(gòu) (服務(wù)臺情況)(2) 服務(wù)方式。這是指在某一時刻接受服務(wù)的顧客數(shù)，它有單個服務(wù)和成批服務(wù)

17、兩種。如公共汽車一次就可裝載一批乘客就屬于成批服務(wù)。(3) 服務(wù)時間的分布。服務(wù)時間可分為確定型確定型和隨機(jī)型隨機(jī)型。一般來說，在多數(shù)情況下，對每一個顧客的服務(wù)時間是一隨機(jī)變量，其概率分布有定長分布、負(fù)指數(shù)分布、K級愛爾良分布、一般分布(所有顧客的服務(wù)時間都是獨(dú)立同分布的)等等。v服務(wù)時間的分布通常假定是平穩(wěn)的。281.3 排隊(duì)模型的分類排隊(duì)模型的分類 排隊(duì)模型分類方法排隊(duì)模型分類方法D.G.Kendall，1953構(gòu)成排隊(duì)模型的三個主要特征指標(biāo)構(gòu)成排隊(duì)模型的三個主要特征指標(biāo)o(1) 相繼顧客到達(dá)間隔時間的分布；相繼顧客到達(dá)間隔時間的分布；o(2) 服務(wù)時間的分布；服務(wù)時間的分布；o(3) 服

18、務(wù)臺的個數(shù)。服務(wù)臺的個數(shù)。根據(jù)這三個特征對排隊(duì)模型進(jìn)行分類的根據(jù)這三個特征對排隊(duì)模型進(jìn)行分類的Kendall記號：記號： X/Y/ZoX：表示相繼到達(dá)間隔時間的分布；：表示相繼到達(dá)間隔時間的分布；oY：表示服務(wù)時間的分布；：表示服務(wù)時間的分布；oZ：并列的服務(wù)臺的數(shù)目。：并列的服務(wù)臺的數(shù)目。291.3 排隊(duì)模型的分類排隊(duì)模型的分類 vM負(fù)指數(shù)分布負(fù)指數(shù)分布(M是是Markov的字頭，因?yàn)樨?fù)指數(shù)分的字頭，因?yàn)樨?fù)指數(shù)分布具有無記憶性，即布具有無記憶性，即Markov性性)vD確定型確定型(deterministic)vEkk階愛爾朗階愛爾朗(erlang)分布分布vGI 一般相互獨(dú)立一般相互獨(dú)立(

19、general independent)的時間間隔的時間間隔的分布的分布vG 一般一般(general)服務(wù)時間的分布服務(wù)時間的分布301.3 排隊(duì)模型的分類排隊(duì)模型的分類vKendall符號的擴(kuò)充 X/Y/Z/A/B/C其中前三項(xiàng)的意義不變，后三項(xiàng)的意義分別是：其中前三項(xiàng)的意義不變，后三項(xiàng)的意義分別是：oA：系統(tǒng)容量限制：系統(tǒng)容量限制N，或稱等待空間容量。如系統(tǒng)有，或稱等待空間容量。如系統(tǒng)有N個等待位個等待位子，則子，則 0 N 0為一常數(shù)，此種的平均服務(wù)時間為： K=1時愛爾朗分布化歸為負(fù)指數(shù)分布當(dāng)K時，得到長度為1/的定長服務(wù)。0,)!1()()(1xekxkkxbxkk01)()(dx

20、xxbtE例子：例子：串列的串列的k個服務(wù)臺，每臺服務(wù)時間相互獨(dú)立，服從相同個服務(wù)臺，每臺服務(wù)時間相互獨(dú)立，服從相同的負(fù)指數(shù)分布的負(fù)指數(shù)分布(參數(shù)參數(shù)k)，那么一顧客走完這，那么一顧客走完這k個服務(wù)臺總共所需個服務(wù)臺總共所需要服務(wù)時間就服從要服務(wù)時間就服從k階愛爾朗分布。階愛爾朗分布。2.2.3 服務(wù)時間的愛爾朗分布服務(wù)時間的愛爾朗分布63n第1節(jié) 基本概念n第2節(jié) 到達(dá)間隔的分布和服務(wù)時間的分布n第3節(jié) 單服務(wù)臺負(fù)指數(shù)分布排隊(duì)系統(tǒng)的分析n第4節(jié) 多服務(wù)臺負(fù)指數(shù)分布排隊(duì)系統(tǒng)的分析n第5節(jié) 一般服務(wù)時間M/G/1模型n第6節(jié) 經(jīng)濟(jì)分析系統(tǒng)的最優(yōu)化n第7節(jié) 分析排隊(duì)系統(tǒng)的隨機(jī)模擬法排隊(duì)論排隊(duì)論64

21、排隊(duì)論排隊(duì)論n 排隊(duì)論研究的首要問題是排隊(duì)系統(tǒng)主要數(shù)量指標(biāo)的概率規(guī)律，即研究系統(tǒng)的整體性質(zhì)，然后進(jìn)一步研究系統(tǒng)的優(yōu)化問題。與這兩個問題相關(guān)的還包括排隊(duì)系統(tǒng)的統(tǒng)計(jì)推斷問題。n (1)通過研究主要數(shù)量指標(biāo)在瞬時或平穩(wěn)狀態(tài)下的概率分布及其數(shù)字特征，了解系統(tǒng)運(yùn)行的基本特征。n (2)統(tǒng)計(jì)推斷問題，建立適當(dāng)?shù)呐抨?duì)模型是排隊(duì)論研究的第一步，建立模型過程中經(jīng)常會碰到如下問題：檢驗(yàn)系統(tǒng)是否達(dá)到平穩(wěn)狀態(tài)；檢驗(yàn)顧客相繼到達(dá)時間間隔的相互獨(dú)立性；確定服務(wù)時間的分布及有關(guān)參數(shù)等。65n (3)系統(tǒng)優(yōu)化問題，又稱為系統(tǒng)控制問題或系統(tǒng)運(yùn)營問題，其基本目的是使系統(tǒng)處于最優(yōu)或最合理的狀態(tài)。n 系統(tǒng)優(yōu)化問題包括最優(yōu)設(shè)計(jì)問題和最

22、優(yōu)運(yùn)營問題，其內(nèi)容很多，有最少費(fèi)用問題、服務(wù)率的控制問題、服務(wù)臺的開關(guān)策略、顧客(或服務(wù))根據(jù)優(yōu)先權(quán)的最優(yōu)排序等方面的問題。n 對于一般的排隊(duì)系統(tǒng)運(yùn)行情況的分析，通常是在給定輸入與服務(wù)條件下，通過求解系統(tǒng)狀態(tài)為n(有n個顧客)的概率Pn(t)，再進(jìn)行計(jì)算其主要的運(yùn)行指標(biāo)： 排隊(duì)論排隊(duì)論66 系統(tǒng)中顧客數(shù)(隊(duì)長)的期望值L或Ls； 排隊(duì)等待的顧客數(shù)(排隊(duì)長)的期望值Lq； 顧客在系統(tǒng)中全部時間(逗留時間)的期望值W或Ws； 顧客排隊(duì)等待時間的期望值Wq。 排隊(duì)系統(tǒng)中，由于顧客到達(dá)分布和服務(wù)時間分布是多種多樣的，加之服務(wù)臺數(shù)。顧客源有限無限，排隊(duì)容量有限無限等的不同組合，就會有不勝枚舉的不同排隊(duì)模

23、型，若對所有排隊(duì)模型都進(jìn)行分析與計(jì)算，不但十分繁雜而且也沒有必要。 下面擬分析幾種常見排隊(duì)系統(tǒng)模型。排隊(duì)論排隊(duì)論67v3.1 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/)v3.2 系統(tǒng)容量有限的情況(M/M/1/N/)v3.3 顧客源有限的情形(M/M/1/m)第第3節(jié)節(jié) 單服務(wù)臺負(fù)指數(shù)分布排隊(duì)系統(tǒng)的分析單服務(wù)臺負(fù)指數(shù)分布排隊(duì)系統(tǒng)的分析本節(jié)討論輸入過程服從普阿松分布過程、服務(wù)時間本節(jié)討論輸入過程服從普阿松分布過程、服務(wù)時間服從負(fù)指數(shù)分布單服務(wù)臺的排隊(duì)系統(tǒng)。服從負(fù)指數(shù)分布單服務(wù)臺的排隊(duì)系統(tǒng)。68v標(biāo)準(zhǔn)的M/M/1模型(1) 輸入過程輸入過程顧客源是無限的，顧客單個到來，相互獨(dú)立，一顧客源是無限的，顧客單

24、個到來，相互獨(dú)立，一定時間內(nèi)的定時間內(nèi)的到達(dá)數(shù)服從泊松分布到達(dá)數(shù)服從泊松分布，到達(dá)過程是平穩(wěn)的。，到達(dá)過程是平穩(wěn)的。(2) 排隊(duì)規(guī)則排隊(duì)規(guī)則單隊(duì)，且對隊(duì)長沒有限制，先到先服務(wù)。單隊(duì)，且對隊(duì)長沒有限制，先到先服務(wù)。(3) 服務(wù)機(jī)構(gòu)服務(wù)機(jī)構(gòu)單服務(wù)臺，各顧客的單服務(wù)臺，各顧客的服務(wù)時間相互獨(dú)立，服從相服務(wù)時間相互獨(dú)立，服從相同的負(fù)指數(shù)分布同的負(fù)指數(shù)分布。此外，還假定到達(dá)間隔時間和服務(wù)時間是相互獨(dú)立的。此外，還假定到達(dá)間隔時間和服務(wù)時間是相互獨(dú)立的。 3.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1模型模型(M/M/1/)即已知條件：v ：顧客進(jìn)入系統(tǒng)的平均速度，即單位時間到達(dá)的顧客數(shù)。v ：顧客離開系統(tǒng)的平均速度，即

25、單位時間能被服務(wù)完成的顧客數(shù)。69v首先要求出：系統(tǒng)在任意時刻t的狀態(tài)為n(即系統(tǒng)中有n個顧客)的概率 ，它決定了系統(tǒng)運(yùn)行的特征。因已知到達(dá)規(guī)律服從參數(shù)為因已知到達(dá)規(guī)律服從參數(shù)為 的泊松過程，服務(wù)時間服從參數(shù)為的泊松過程，服務(wù)時間服從參數(shù)為 的負(fù)指數(shù)分布，所以在的負(fù)指數(shù)分布，所以在 時間區(qū)間內(nèi)分為：時間區(qū)間內(nèi)分為：(1) 有有1個顧客到達(dá)的概率為個顧客到達(dá)的概率為 沒有顧客到達(dá)的概率就是沒有顧客到達(dá)的概率就是 (2) 當(dāng)有顧客在接受服務(wù)時，當(dāng)有顧客在接受服務(wù)時，1個顧客被服務(wù)完了個顧客被服務(wù)完了(離去離去)的概率的概率是是 ，沒有離去的概率就是，沒有離去的概率就是 。(3) 多于一個顧客的到達(dá)

26、或離去的概率是多于一個顧客的到達(dá)或離去的概率是 ，可以忽略。，可以忽略。( )nP t, t tt()tot 1()tot ()tot 1()tot ()ot3.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1模型模型(M/M/1/)703.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1模型模型(M/M/1/)v在時刻 ，系統(tǒng)中有n個顧客(n0)存在下列四種情況(到達(dá)或離去是2個以上的沒列入)：表示發(fā)生表示發(fā)生(1個個)；表示沒有發(fā)生。表示沒有發(fā)生。tttt , t ttnn(D)nn-1(C)nn+1(B)nn(A)離去離去到達(dá)到達(dá)在時刻在時刻 顧客數(shù)顧客數(shù)在區(qū)間在區(qū)間在時刻在時刻t顧顧客數(shù)客數(shù)情況情況7172v這四種情況是互不相容

27、的，所以 應(yīng)是這四項(xiàng)之和，即 即v令 ，得關(guān)于 的微分差分方程 ()nP tt1111()( )(1 )( )( )()()( )()( )( )()( )nnnnnnnnnP ttP tttPttPttotP ttP totPtPtP ttt 0t ( )nP t11( )( )( )()( ) 1,2,(12 15)nnnndP tPtPtP tndt3.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1模型模型(M/M/1/)( )(1 )(1)nP ttt 1( )(1)nPttt 1( ) (1)nPttt ( ) nP ttt 所有的高階所有的高階無窮小和并無窮小和并tttPtttPtttPttPnnnn

28、)1)()()1)(1)()(1)()1 ()(1tOtttPn73v當(dāng) ，則只有上表中(A)(B)情況，且方式(A)中無離去的概率為1，即v同理求得 v它們的概率分別是 o情況情況(A)o情況情況(B) o情況情況(C)o情況情況(D) tt , t ttnn(D)nn-1(C)nn+1(B)nn(A)離去離去到達(dá)到達(dá)在時刻在時刻 顧客數(shù)顧客數(shù)在區(qū)間在區(qū)間在時刻在時刻t 顧顧客數(shù)客數(shù)情況情況( )(1 )(1)nP ttt 1( )(1)nPttt 1( ) (1)nPttt ( ) nP ttt3.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1模型模型(M/M/1/)0n 001()( )(1 )( )(1

29、)P ttP ttP ttt 001( )( )( )(12 16)dP tP tP tdt 74v研究穩(wěn)態(tài)的情況。這時 與時間t無關(guān)，可寫成 ，它的導(dǎo)數(shù)為0。由(12-15)式和(12-16)式可得v這是關(guān)于 的差分方程，它表明了各狀態(tài)間的轉(zhuǎn)移關(guān)系：狀態(tài)0轉(zhuǎn)移到狀態(tài)1的轉(zhuǎn)移率為 ，狀態(tài)1轉(zhuǎn)移到狀態(tài)0的轉(zhuǎn)移率為 。 ( )nP tnP01110(12 17,12 18)()0 1nnnPPPPPn0P1PnP3.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1模型模型(M/M/1/)這種系統(tǒng)狀態(tài)這種系統(tǒng)狀態(tài)(n)隨時間變化的過程就是生滅過程（隨時間變化的過程就是生滅過程（Birth and Death Proces

30、s）。）。 方程方程(12-15)、(12-16) 解是瞬態(tài)解，無法應(yīng)用。解是瞬態(tài)解，無法應(yīng)用。 753.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1模型模型(M/M/1/)v對狀態(tài)0必須滿足以下平衡方程v同樣對任何 的狀態(tài)，可得如(12-18)所示的平衡方程。由(12-17)式可得v將它代入(12-18)式，令 ，得到v同理依次推得v今設(shè) (否則隊(duì)列將排至無限遠(yuǎn))，又由概率的性質(zhì)知 將 的關(guān)系代入 ，得到01PP1n10(/)PP220020()(/) (/)PPPPP；所以 1n 0(/)nnPP101nnPnP01 1(12 19)(1), 1nnPPn 000111nnPp01110(12 17,12

31、18)()0 1nnnPPPPPn 76v對的實(shí)際意義的解釋/，是平均到達(dá)率與平均服務(wù)率之比，即在相同時區(qū)內(nèi)，是平均到達(dá)率與平均服務(wù)率之比，即在相同時區(qū)內(nèi)顧客到達(dá)的平均數(shù)與被服務(wù)的平均數(shù)之比。顧客到達(dá)的平均數(shù)與被服務(wù)的平均數(shù)之比。若將若將表示為表示為(1/)/(1/)，它是一個顧客的服務(wù)時間與到，它是一個顧客的服務(wù)時間與到達(dá)間隔時間之比，稱達(dá)間隔時間之比，稱為服務(wù)強(qiáng)度為服務(wù)強(qiáng)度(traffic intensity)，或話務(wù)，或話務(wù)強(qiáng)度。強(qiáng)度。由由(12-19)式可知，式可知，=1-P0，它刻畫了服務(wù)機(jī)構(gòu)的繁忙程度，它刻畫了服務(wù)機(jī)構(gòu)的繁忙程度，所以所以又稱為服務(wù)機(jī)構(gòu)的利用率。又稱為服務(wù)機(jī)構(gòu)的利用

32、率。3.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1模型模型(M/M/1/) 系統(tǒng)處于空閑狀態(tài)的概率：系統(tǒng)處于空閑狀態(tài)的概率： 10P 系統(tǒng)處于繁忙狀態(tài)的概率：系統(tǒng)處于繁忙狀態(tài)的概率： 010P)N(P77v根據(jù)平穩(wěn)分布，求排隊(duì)系統(tǒng)的有關(guān)運(yùn)行指標(biāo)(1) 系統(tǒng)中的平均顧客數(shù)系統(tǒng)中的平均顧客數(shù)（平均隊(duì)長）（平均隊(duì)長） 或或 (2) 在隊(duì)列中等待的平均顧客數(shù)在隊(duì)列中等待的平均顧客數(shù) 012323423(1)(23)(23), 0 11nsnnnLnPn sL1112(1)1qnnnnnnsLnPnPPL3.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1模型模型(M/M/1/) 期望期望78顧客在系統(tǒng)中的逗留時間W(為一個隨機(jī)變量)在M/

33、M/1情形下，服從參數(shù)為 的負(fù)指數(shù)分布，即 分布函數(shù) 概率密度 ()( )1 e 0(1220)wF ww ()( )()ewf w 于是，得到于是，得到(3) 在系統(tǒng)中顧客逗留時間的期望值在系統(tǒng)中顧客逗留時間的期望值 (4) 在隊(duì)列中顧客等待時間的期望值在隊(duì)列中顧客等待時間的期望值 1sWE W1qsWW3.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1模型模型(M/M/1/) 平均逗留時間減平均逗留時間減去平均服務(wù)時間。去平均服務(wù)時間。79v將以上結(jié)果歸納如下： v它們的相互關(guān)系如下： 上式稱為Little公式。(1) (2) (1221)1(3) (4) sqsqLLWW(1) (2) (1222)1(3)

34、 (4) ssqqsqsqLWLWWWLL3.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1模型模型(M/M/1/)803.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1模型模型(M/M/1/)Ls ,L q, ,Ws ,Wq之間的關(guān)系：幾何解釋： 穩(wěn)態(tài)時，一個顧客，進(jìn)入系統(tǒng)后，每單位時間，平均到達(dá)顧客。 進(jìn)入時刻離開時刻總時間Ws 隊(duì)長Ls由時間段內(nèi)個組成的Ls=Ws(1) (2) (12 22)1(3) (4) ssqqsqsqLWLWWWLL同理：Lq=Wq Ws=Wq+（1/）-Ws與Wq只相差一段平均服務(wù)時間1/ 813.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1模型模型(M/M/1/)82 解：本例可看成一個解：本例可看成一個M/M/1

35、/ 排隊(duì)問題，其中排隊(duì)問題，其中 =2， =3， = / =2/31 系統(tǒng)中列車的平均數(shù)系統(tǒng)中列車的平均數(shù) L= / (1- )=(2/3)/(1-2/3)=2（列）（列）列車在系統(tǒng)中的平均停留時間列車在系統(tǒng)中的平均停留時間W=L/ = 2/2=1（小時）（小時）系統(tǒng)中等待編組的列車平均數(shù)系統(tǒng)中等待編組的列車平均數(shù)Lq=L- = 2-2/3=4/3（列）（列）列車在系統(tǒng)中的平均等待編組時間列車在系統(tǒng)中的平均等待編組時間 Wq = Lq/ =(4/3)/(1/2)=2/3（小時）（小時）3.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1模型模型(M/M/1/)833.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1模型模型(M/M/1/

36、)843.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1模型模型(M/M/1/)853.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1模型模型(M/M/1/)863.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1模型模型(M/M/1/)873.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1模型模型(M/M/1/)883.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1模型模型(M/M/1/)89v例3 某醫(yī)院手術(shù)室根據(jù)病人來診和完成手術(shù)時間的記錄，任意抽查了100個工作小時，每小時來就診的病人數(shù)n的出現(xiàn)次數(shù)如下表所示；又任意抽查了100個完成手術(shù)的病歷，所用時間v(單位：小時)出現(xiàn)的次數(shù)如下表所示。nf到達(dá)的病人數(shù)n出現(xiàn)人數(shù)0101282316410566以上以上1合計(jì)合計(jì)100vf為病人完成

37、手術(shù)時間v(小時)出現(xiàn)人數(shù)0.00.2380.20.4250.40.6170.60.890.81.061.01.251.2以上以上0合計(jì)合計(jì)1003.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1模型模型(M/M/1/)90v(1) 每小時病人平均到達(dá)率 (人/小時) 每次手術(shù)平均時間 (小時/人) 每小時完成手術(shù)人數(shù)(平均服務(wù)率) (人/小時)v(2) 取 ， ，可以通過統(tǒng)計(jì)檢驗(yàn)的方法，認(rèn)為病人到達(dá)數(shù)服從參數(shù)為2.1的泊松分布，手術(shù)時間服從參數(shù)為2.5的負(fù)指數(shù)分布。v(3) 說明服務(wù)機(jī)構(gòu)(手術(shù)室)有84%的時間是繁忙的，有16%的時間是空閑的。v(4) 依次代入(12-21)式，算出各指標(biāo)：在病房中病人數(shù)在病房

38、中病人數(shù)(期望值期望值) (人人)排隊(duì)等待病人數(shù)排隊(duì)等待病人數(shù)(期望值期望值) (人人)病人在病房中逗留時間病人在病房中逗留時間(期望值期望值) (小時小時)病人排隊(duì)等待時間病人排隊(duì)等待時間(期望值期望值) (小時小時)2.1100nnf0.4100vvf52.52.1sL 0.84 5.254.41qL sW 0.8qW 3.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1模型模型(M/M/1/)91v如果系統(tǒng)的最大容量為N，對于單服務(wù)臺的情形，排隊(duì)等待的顧客最多為N-1，在某時刻一顧客到達(dá)時，如系統(tǒng)中已有N個顧客，

39、那么這個顧客就被拒絕進(jìn)入系統(tǒng)。v當(dāng)N=1時為即時制的情形；當(dāng)N時為容量無限制的情形。3.2 系統(tǒng)的容量有限制的情況系統(tǒng)的容量有限制的情況(M/M/1/N/)92泊松輸入負(fù)指數(shù)分布服務(wù)的排隊(duì)系統(tǒng)的一般決策過程： 根據(jù)已知條件繪制狀態(tài)轉(zhuǎn)移速度圖； 依據(jù)狀態(tài)轉(zhuǎn)移速度圖寫出各穩(wěn)態(tài)概率之間的關(guān)系； 求出 P0 及 Pn ； 計(jì)算各項(xiàng)數(shù)量運(yùn)行指標(biāo)； 用系統(tǒng)運(yùn)行指標(biāo)構(gòu)造目標(biāo)函數(shù)，對系統(tǒng)進(jìn)行優(yōu)化。3.2 系統(tǒng)的容量有限制的情況系統(tǒng)的容量有限制的情況(M/M/1/N/)933.2 系統(tǒng)的容量有限制的情況系統(tǒng)的容量有限制的情況(M/M/1/N/)v穩(wěn)態(tài)情形下各狀態(tài)間概率強(qiáng)度的轉(zhuǎn)換關(guān)系圖v狀態(tài)概率的穩(wěn)態(tài)方程 101

40、11 (12-23a)(), 1 (12-23b) (12-23c)nnnNNPPPPPnNPP情情況況 時時刻刻 t 的的顧顧客客 區(qū)區(qū)間間 t, t+t t 時時刻刻 t+t t的的顧顧客客數(shù)數(shù) 概概率率 A A N N 無無離離去去 （肯肯定定不不到到達(dá)達(dá)） N N P Pn n( (t t) )( (1 1- -t t) ) B B N N- -1 1 一一人人到到達(dá)達(dá)（無無離離去去） N N P Pn n- -1 1( (t t) )t t ttPttPttPNNN)()1 ()()(1 )()()(1tPtPdttdPNNN 943.2 系統(tǒng)的容量有限制的情況系統(tǒng)的容量有限制的情況

41、(M/M/1/N/)v穩(wěn)態(tài)情形下各狀態(tài)間概率強(qiáng)度的轉(zhuǎn)換關(guān)系圖v狀態(tài)概率的穩(wěn)態(tài)方程 其中(12-23a)也可寫成 ，則有10111 (12-23a)(), 1 (12-23b) (12-23c)nnnNNPPPPPnNPP0(/)nnPP1001 (), 1 nnNNPPPPnNPP953.2 系統(tǒng)的容量有限制的情況系統(tǒng)的容量有限制的情況(M/M/1/N/) 由 1001 (), 1 nnNNPPPPnNPP N(/)nP0=1n=0 NP0=1/(/)n= n=0(1- (1- /)/)/(1- (1- (/) )N N+1+1 1/(1/(N N +1) +1) = =Pn=1/(N +1)

42、 =(1- (1- /)()(/ ) )n n/(1- (/(1- (/) )N N+1+1 011NPPP96vM/M/1/N/排隊(duì)系統(tǒng)的各項(xiàng)指標(biāo)：v(1) 隊(duì)長(期望值)v(2) 隊(duì)列長(期望值)v(3) 顧客逗留時間(期望值)v (4) 顧客等待時間(期望值)v(5) 有效到達(dá)率 110(1) 111NNsnNnNLnP01(1)(1)NqnsnLnPLP01(1)(1)qssNLLWPP1/qsWW(1)eNP3.2 系統(tǒng)的容量有限制的情況系統(tǒng)的容量有限制的情況(M/M/1/N/)v令 ，得到0111 111 (1224)1NnnNPPnN/971011 NPnNnP 111 (1,n

43、N(1,nN) ) (1) 平均平均隊(duì)長隊(duì)長Ls：nPnLnNnNNnns 01011nNnNn 0111111) 1(1 NNN (1) 試證試證=1=1時時,Ls=N/2,Ls=N/23.2 系統(tǒng)的容量有限制的情況系統(tǒng)的容量有限制的情況(M/M/1/N/)98 ? ? ?vM/M/1/N/排隊(duì)系統(tǒng)的各項(xiàng)指標(biāo)：v(1) 隊(duì)長(期望值)v(2) 隊(duì)列長(期望值)v(3) 顧客逗留時間(期望值)v (4) 顧客等待時間(期望值)v(5) 有效到達(dá)率 110(1) 111NNsnNnNLnP01(1)(1)NqnsnLnPLP01(1)(1)qssNLLWPP1/qsWW(1)eNP3.2 系統(tǒng)的

44、容量有限制的情況系統(tǒng)的容量有限制的情況(M/M/1/N/)v令 ，得到0111 111 (1224)1NnnNPPnN/返回返回P9899 (2) 有效到達(dá)率有效到達(dá)率e 系統(tǒng)容量有限，當(dāng)滿員（系統(tǒng)容量有限，當(dāng)滿員（n=N）時時，顧客將被拒絕，實(shí)際的顧客到達(dá)率，顧客將被拒絕，實(shí)際的顧客到達(dá)率與與不一樣，不一樣，)1(NeP 還可驗(yàn)證：還可驗(yàn)證：esesqLLL esSLW eqqLW 此種情況的公式與前類似此種情況的公式與前類似,只只有有Ls不同不同,e與與 不同。求不同。求e必必須先求得須先求得P0或或PN才行。才行。有效到達(dá)率為有效到達(dá)率為e 可以證明：可以證明：)1(0Pe 111)1(

45、1 NNN LsLs3.2 系統(tǒng)的容量有限制的情況系統(tǒng)的容量有限制的情況(M/M/1/N/)100vM/M/1/N/排隊(duì)系統(tǒng)各項(xiàng)指標(biāo)的歸納(當(dāng) 時)：11100(1)11(1)(12-25)(1)1/NsNqsssqsNLLLPLWPWW3.2 系統(tǒng)的容量有限制的情況系統(tǒng)的容量有限制的情況(M/M/1/N/)101例例2某單人理發(fā)館共有六把椅子接待顧客排隊(duì)，無座時將離某單人理發(fā)館共有六把椅子接待顧客排隊(duì)，無座時將離去，顧客平均到達(dá)率為去，顧客平均到達(dá)率為3人人/h，理發(fā)時間平均為，理發(fā)時間平均為15分鐘，求：分鐘，求：(1) 求某一顧客到達(dá)就能理發(fā)的概率求某一顧客到達(dá)就能理發(fā)的概率;(2) 求

46、需要等待的顧客數(shù)的期望值求需要等待的顧客數(shù)的期望值;(3) 求有效到達(dá)率求有效到達(dá)率;(4) 求一顧客在系統(tǒng)中的逗留時間和排隊(duì)時間平均值求一顧客在系統(tǒng)中的逗留時間和排隊(duì)時間平均值;(5) 在可能到來的顧客中，有百分之幾不等待就離開？在可能到來的顧客中，有百分之幾不等待就離開？3.2 系統(tǒng)的容量有限制的情況系統(tǒng)的容量有限制的情況(M/M/1/N/)10211. 275. 0175. 0825. 075. 01) 1(18811 NNsNL02.11 (1)2.11 (1 0.2778) 1.39qsLLP2778. 075. 0175. 0111810 NP(1) 求某一顧客到達(dá)就能理發(fā)的概率求

47、某一顧客到達(dá)就能理發(fā)的概率:(2) 求需要等待的顧客數(shù)的期望值求需要等待的顧客數(shù)的期望值:(3) 求有效到達(dá)率求有效到達(dá)率:89. 2)2778. 01(4)1(0 Pe(4) 求一顧客在系統(tǒng)中的逗留時間和排隊(duì)時間平均值求一顧客在系統(tǒng)中的逗留時間和排隊(duì)時間平均值:3.2 系統(tǒng)的容量有限制的情況系統(tǒng)的容量有限制的情況(M/M/1/N/)103min8 .4373. 089. 211. 2 hLWessmin86.2848. 089. 239. 1 hLWeqq%71. 375. 075. 0175. 01117817 NNPP0=0.27780P1=0.20836P2=0.15627P3=0.1

48、1720 = 0.9629=96.29% 1- 0.9629=3.71% P4=0.08790P5=0.06593P6=0.04944(5) 在可能到來的顧客中，有百分之幾不等待就離開？在可能到來的顧客中，有百分之幾不等待就離開？ 顧客為何不顧客為何不等待就離去？等待就離去？ 因?yàn)橄到y(tǒng)因?yàn)橄到y(tǒng)已經(jīng)滿員已經(jīng)滿員037. 0389. 23 e3.2 系統(tǒng)的容量有限制的情況系統(tǒng)的容量有限制的情況(M/M/1/N/)故拒絕的概率為故拒絕的概率為3.71%104v例例4 某單人理發(fā)館為等待的顧客準(zhǔn)備了6把椅子，當(dāng)6把椅子都坐滿時，再來的顧客將不進(jìn)店而離開。顧客的平均到達(dá)率為3人/小時，理發(fā)平均需要15分

49、鐘。則系統(tǒng)的容量為N=6+1=7， 人/小時， 人/小時。(1) 某顧客一到達(dá)就能理發(fā)的概率某顧客一到達(dá)就能理發(fā)的概率(2) 需要等待的顧客數(shù)的期望值需要等待的顧客數(shù)的期望值(3) 有效到達(dá)率有效到達(dá)率 (人人/小時小時)(4) 一顧客在理發(fā)館內(nèi)逗留的期望時間一顧客在理發(fā)館內(nèi)逗留的期望時間 (小時小時) (分鐘分鐘)34081 3/40.27781 (3/4)P8803/48(3/4)2.111 3/41 (3/4)(1)2.11 (1 0.2778)1.39sqsLLLP0(1)4(1 0.2778)2.89ePe/2.11/2.890.73ssWL3.2 系統(tǒng)的容量有限制的情況系統(tǒng)的容量有

50、限制的情況(M/M/1/N/)105v(5) 在可能到來的顧客中不等待就離開的概率 這也是理發(fā)館的損失率。(7)nP 77788311/343.7%1 (/)4314P人/小時人/小時有限隊(duì)長2.111.390.730.480.2783.7無限隊(duì)長32.251.00.750.25034sL7N qLsWqW0P7P以本例為例，比較隊(duì)長為有限和無限的情形：以本例為例，比較隊(duì)長為有限和無限的情形：3.2 系統(tǒng)的容量有限制的情況系統(tǒng)的容量有限制的情況(M/M/1/N/)106v背景設(shè)有設(shè)有m臺機(jī)器臺機(jī)器(顧客總體顧客總體)，機(jī)器因故障停機(jī)表示，機(jī)器因故障停機(jī)表示“到達(dá)到達(dá)”，待修的機(jī)器形成，待修的機(jī)

51、器形成隊(duì)列，修理工人是服務(wù)員，本節(jié)討論單服務(wù)員的情形。隊(duì)列，修理工人是服務(wù)員，本節(jié)討論單服務(wù)員的情形。顧客總體雖只有顧客總體雖只有m個，但每個顧客到來并經(jīng)過服務(wù)后，仍回到原來總體，所個，但每個顧客到來并經(jīng)過服務(wù)后，仍回到原來總體，所以仍然可以再到來。以仍然可以再到來。如在機(jī)器故障問題中，同一臺機(jī)器出了故障如在機(jī)器故障問題中，同一臺機(jī)器出了故障(到來到來)并經(jīng)修好并經(jīng)修好(服務(wù)完了服務(wù)完了)仍可仍可再出故障，形成循環(huán)。再出故障，形成循環(huán)。模型符號中的模型符號中的表示對系統(tǒng)的容量沒有限制，但實(shí)際上它不會超過表示對系統(tǒng)的容量沒有限制，但實(shí)際上它不會超過m，所以，所以可寫成可寫成(M/M/1/m/m)

52、。3.3 顧客源為有限的情形顧客源為有限的情形(M/M/1/m)107v設(shè)每個顧客的到達(dá)率相同，均為 (這里這里的含義是單臺機(jī)器在單位時的含義是單臺機(jī)器在單位時間里發(fā)生故障的概率或平均次數(shù)間里發(fā)生故障的概率或平均次數(shù))；設(shè)系統(tǒng)內(nèi)顧客數(shù)為Ls，則系統(tǒng)外的顧客平均數(shù)為mLs，所以系統(tǒng)的有效到達(dá)率為 e=(m Ls) (12-26) v考慮穩(wěn)態(tài)情況下狀態(tài)間的轉(zhuǎn)移率由狀態(tài)由狀態(tài)0轉(zhuǎn)移到狀態(tài)轉(zhuǎn)移到狀態(tài)1：每臺設(shè)備由正常狀態(tài)轉(zhuǎn)移為故障狀態(tài)的轉(zhuǎn)：每臺設(shè)備由正常狀態(tài)轉(zhuǎn)移為故障狀態(tài)的轉(zhuǎn)移率為移率為P0，m臺設(shè)備由無故障狀態(tài)轉(zhuǎn)移為有一臺設(shè)備臺設(shè)備由無故障狀態(tài)轉(zhuǎn)移為有一臺設(shè)備(不論哪一臺不論哪一臺)發(fā)生故障的轉(zhuǎn)移率

53、為發(fā)生故障的轉(zhuǎn)移率為mP0。由狀態(tài)由狀態(tài)1轉(zhuǎn)移到狀態(tài)轉(zhuǎn)移到狀態(tài)0：其狀態(tài)轉(zhuǎn)移率為：其狀態(tài)轉(zhuǎn)移率為P1。所以，狀態(tài)所以，狀態(tài)0時有平衡方程為：時有平衡方程為： mP0=P13.3 顧客源為有限的情形顧客源為有限的情形(M/M/1/m)108v各狀態(tài)間的轉(zhuǎn)移差分方程解得(注意到 因而不要求 ） v系統(tǒng)的各項(xiàng)指標(biāo)為10111(1)(), 11nnnmmPm PPmnPmnPnmPP01miiP/10001!()!(1227)! (1)()!iminnPmmimPPnmmn0000(1)()(1)(1)(1228)1(1)1/sqssqsLmPPLmLPmWPWW3.3 顧客源為有限的情形顧客源為有限

54、的情形(M/M/1/m)109v例例5 某車間有5臺機(jī)器，每臺機(jī)器的連續(xù)運(yùn)轉(zhuǎn)時間服從負(fù)指數(shù)分布，平均連續(xù)運(yùn)轉(zhuǎn)時間15分鐘，有一個修理工，每次修理時間服從負(fù)指數(shù)分布，平均每次12分鐘。求：(1) 修理工空閑的概率；修理工空閑的概率；(2) 五臺機(jī)器都出故障的概率；五臺機(jī)器都出故障的概率；(3) 出故障的平均臺數(shù)；出故障的平均臺數(shù)；(4) 等待修理的平均臺數(shù)；等待修理的平均臺數(shù)；(5) 平均停工時間；平均停工時間；(6) 平均等待修理時間；平均等待修理時間；(7) 評價這些結(jié)果。評價這些結(jié)果。3.3 顧客源為有限的情形顧客源為有限的情形(M/M/1/m)110解：解： (1)(2) 五臺機(jī)器都出現(xiàn)

55、故障的概率五臺機(jī)器都出現(xiàn)故障的概率(3) 出故障的平均臺數(shù)出故障的平均臺數(shù) (臺)(4) 等待修理的平均臺數(shù)等待修理的平均臺數(shù) (臺)(5)平均停工時間平均停工時間 (分鐘)(6)平均等待修理時間平均等待修理時間 (分鐘)(7) 機(jī)器停工時間過長，修理工幾乎沒有空閑時間，應(yīng)當(dāng)提高服務(wù)率減少修理時間或增加修理工人。5, 1/15, 1/12, /0.8m101234505!5!5!5!5!5!(0.8)(0.8)(0.8)(0.8)(0.8)(0.8)5!4!3!2!1!0!1/136.80.0073P5505! (0.8)0.2870!PP1 5(1 0.0073)3.760.8sL 3.76

56、0.9932.77qL 6515461(1 0.007)12W 461234qW 3.3 顧客源為有限的情形顧客源為有限的情形(M/M/1/m)111n第1節(jié) 基本概念n第2節(jié) 到達(dá)間隔的分布和服務(wù)時間的分布n第3節(jié) 單服務(wù)臺負(fù)指數(shù)分布排隊(duì)系統(tǒng)的分析n第4節(jié) 多服務(wù)臺負(fù)指數(shù)分布排隊(duì)系統(tǒng)的分析n第5節(jié) 一般服務(wù)時間M/G/1模型n第6節(jié) 經(jīng)濟(jì)分析系統(tǒng)的最優(yōu)化n第7節(jié) 分析排隊(duì)系統(tǒng)的隨機(jī)模擬法排隊(duì)論排隊(duì)論112本節(jié)討論單隊(duì)、并列的多服務(wù)臺（服務(wù)臺數(shù)為本節(jié)討論單隊(duì)、并列的多服務(wù)臺（服務(wù)臺數(shù)為c）的情形。）的情形。v4.1 標(biāo)準(zhǔn)的M/M/c模型v4.2 M/M/c型系統(tǒng)和c個M/M/1型系統(tǒng)的比較v4

57、.3 系統(tǒng)容量有限的情形（M/M/c/N/）v4.4 顧客源有限的情形（M/M/c/ /m）第第4節(jié)節(jié) 多服務(wù)臺負(fù)指數(shù)分布排隊(duì)系統(tǒng)的分析多服務(wù)臺負(fù)指數(shù)分布排隊(duì)系統(tǒng)的分析1134.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/c模型模型v標(biāo)準(zhǔn)的M/M/c模型各種特征的規(guī)定與標(biāo)準(zhǔn)的M/M/1模型的規(guī)定相同。v各服務(wù)臺工作是相互獨(dú)立的(不搞協(xié)作)，且平均服務(wù)率相同。v整個服務(wù)機(jī)構(gòu)的平均服務(wù)率為 (當(dāng) )；為 (當(dāng) )。v令 ，只有當(dāng) 時才不會排成無限的隊(duì)列稱 為系統(tǒng)的服務(wù)強(qiáng)度服務(wù)強(qiáng)度或服務(wù)機(jī)構(gòu)的平均利用率。平均利用率。12ccncnncc1cc1144.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/c模型模型vM/M/c排隊(duì)系統(tǒng)的狀態(tài)概率分布

58、狀態(tài)狀態(tài)1轉(zhuǎn)移到狀態(tài)轉(zhuǎn)移到狀態(tài)0：即系統(tǒng)中有一名顧客被服務(wù)完了：即系統(tǒng)中有一名顧客被服務(wù)完了(離去離去)的轉(zhuǎn)移率的轉(zhuǎn)移率為為 。狀態(tài)狀態(tài)2轉(zhuǎn)移到狀態(tài)轉(zhuǎn)移到狀態(tài)1：兩個服務(wù)臺上被服務(wù)的顧客中有一個被服務(wù)完成：兩個服務(wù)臺上被服務(wù)的顧客中有一個被服務(wù)完成而離去。因?yàn)椴幌弈囊粋€，于是狀態(tài)的轉(zhuǎn)移率為而離去。因?yàn)椴幌弈囊粋€，于是狀態(tài)的轉(zhuǎn)移率為 。狀態(tài)狀態(tài)n轉(zhuǎn)移到轉(zhuǎn)移到n-1：o當(dāng)當(dāng) 時，狀態(tài)轉(zhuǎn)移率為時，狀態(tài)轉(zhuǎn)移率為 ；o當(dāng)當(dāng) 時，因?yàn)橹挥袝r，因?yàn)橹挥衏個服務(wù)臺，最多有個服務(wù)臺，最多有c個顧客在被服務(wù)，個顧客在被服務(wù)， 個顧客在等候，因此這時狀態(tài)轉(zhuǎn)移率應(yīng)為個顧客在等候，因此這時狀態(tài)轉(zhuǎn)移率應(yīng)為 。1P22 P

59、ncncnn Pncnc P1154.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/c模型模型v由圖12-13可得 這里 ，且 v用遞推法解上述差分方程，可求得狀態(tài)概率。101111(1)() (1)() ()nnnnnnPPnPPnPncc PPcPnc01iiP1)(!1)(!111!1!1001100cnPcccnPnPckPncnnnckc1164.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/c模型模型v系統(tǒng)的運(yùn)行指標(biāo)為：v 平均隊(duì)長v平均等待時間和逗留時間可由Little公式求得，sqcqn02n c 1LL(1230)(c )L(nc)PPc!(1) 0111()()!n cnn cn cnnnnc PnPcPc cn 因

60、為 右邊, qsqsLLWW1174.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/c模型模型v例6 某售票處有三個窗口，顧客的到達(dá)服從泊松過程，平均到達(dá)率每分鐘 (人)，服務(wù)(售票)時間服從負(fù)指數(shù)分布，平均服務(wù)率每分鐘 人?，F(xiàn)設(shè)顧客到達(dá)后排成一隊(duì)，依次向空閑的窗口購票如圖12-14(a)，這就是一個M/M/c型的系統(tǒng)，其中 ， ， 符合要求的條件，代入公式得：0.90.43c 2.252.253( 1)c0312323431184.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/c模型模型v(1) 整個售票處空閑概率v(2) 平均隊(duì)長v(3) 平均等待時間和逗留時間 (分鐘) (分鐘)v顧客到達(dá)后必須等待(即系統(tǒng)中顧客數(shù)已有3人即各服務(wù)