排隊論及其模型

關(guān)于排隊論及其模型1第一頁，共一百七十一頁，編輯于2023年，星期一2排隊論排隊論(queuingtheory)也稱隨機服務(wù)系統(tǒng)理論(RandomServiceSystemTheory)，是為研究和解決具有擁擠現(xiàn)象的問題而發(fā)展起來的一門應(yīng)用數(shù)學(xué)的分支。具體地說，它是在研究各種排隊系統(tǒng)概率規(guī)律性的基礎(chǔ)上，解決相應(yīng)排隊系統(tǒng)的最優(yōu)設(shè)計和最優(yōu)控制問題。第二頁，共一百七十一頁，編輯于2023年，星期一3排隊論

排隊論是1909年由丹麥工程師愛爾朗(A.K．Erlang)在研究電活系統(tǒng)時創(chuàng)立的，幾十年來排隊論的應(yīng)用領(lǐng)域越來越廣泛，理論也日漸完善。特別是自二十世紀(jì)60年代以來，由于計算機的飛速發(fā)展，更為排隊論的應(yīng)用開拓了寬闊的前景。第三頁，共一百七十一頁，編輯于2023年，星期一4排隊論排隊論(queuingtheory)

研究內(nèi)容包括三個部分：

(1)排隊系統(tǒng)的性態(tài)問題

(2)排隊系統(tǒng)的最優(yōu)化問題

(3)排隊系統(tǒng)的統(tǒng)計推斷問題性態(tài)問題，即研究各種排隊系統(tǒng)的概率規(guī)律性，主要研究隊長分布、等待時間分布和忙期分布等。最優(yōu)化，又分靜態(tài)最優(yōu)和動態(tài)最優(yōu)，前者指最優(yōu)設(shè)計，后者指現(xiàn)有排隊系統(tǒng)的最優(yōu)運營。統(tǒng)計推斷，即判斷一個給定的排隊系統(tǒng)符合哪種模型，以便根據(jù)排隊理論進(jìn)行研究。解排隊問題的目的，是研究排隊系統(tǒng)運行的效率，估計服務(wù)質(zhì)量，確定系統(tǒng)參數(shù)的最優(yōu)值，以決定系統(tǒng)結(jié)構(gòu)是否合理，研究設(shè)計改進(jìn)措施等。第四頁，共一百七十一頁，編輯于2023年，星期一5排隊論

第1節(jié)基本概念第2節(jié)到達(dá)間隔的分布和服務(wù)時間的分布第3節(jié)單服務(wù)臺負(fù)指數(shù)分布排隊系統(tǒng)的分析第4節(jié)多服務(wù)臺負(fù)指數(shù)分布排隊系統(tǒng)的分析第5節(jié)一般服務(wù)時間M/G/1模型第6節(jié)經(jīng)濟(jì)分析——系統(tǒng)的最優(yōu)化第7節(jié)分析排隊系統(tǒng)的隨機模擬法第五頁，共一百七十一頁，編輯于2023年，星期一6第1節(jié)基本概念1.1排隊過程的一般表示1.2排隊系統(tǒng)的組織和特征1.3排隊模型的分類1.4排隊問題的求解第六頁，共一百七十一頁，編輯于2023年，星期一7

不同的顧客與服務(wù)組成了各式各樣的服務(wù)系統(tǒng)。顧客為了得到某種服務(wù)而到達(dá)系統(tǒng)、若不能立即獲得服務(wù)而又允許排隊等待，則加入隊列排隊等待接受服務(wù)，然后服務(wù)臺按一定規(guī)則從隊列中選擇顧客進(jìn)行服務(wù)，獲得服務(wù)的顧客立即離開系統(tǒng)。1.1排隊過程的一般表示第七頁，共一百七十一頁，編輯于2023年，星期一81.1排隊過程的一般表示各個顧客由顧客源(總體)出發(fā)，到達(dá)服務(wù)機構(gòu)(服務(wù)臺、服務(wù)員)前排隊等候接受服務(wù)，服務(wù)完成后離開。排隊結(jié)構(gòu)指隊列的數(shù)目和排列方式，排隊規(guī)則和服務(wù)規(guī)則是說明顧客在排隊系統(tǒng)中按怎樣的規(guī)則、次序接受服務(wù)的。排隊過程的一般模型第八頁，共一百七十一頁，編輯于2023年，星期一91.1排隊過程的一般表示到達(dá)的顧客要求服務(wù)內(nèi)容服務(wù)機構(gòu)1.不能運轉(zhuǎn)的機器2.修理技工3.病人4.電話呼喚5.文件稿6.提貨單7.到達(dá)機場上空的飛機8.駛?cè)敫劭诘呢洿?.上游河水進(jìn)入水庫10.進(jìn)入我方陣地的敵機修理領(lǐng)取修配零件診斷或動手術(shù)通話打字提取存貨降落裝(卸)貨裝(卸)放水，調(diào)整水位我方高射炮進(jìn)行射擊修理技工發(fā)放修配零件的管理員醫(yī)生(或包括手術(shù)臺)交換臺打字員倉庫管理員跑道貨碼頭(泊位)水閘管理員我方高射炮形形色色的排隊系統(tǒng)第九頁，共一百七十一頁，編輯于2023年，星期一10

實際的排隊系統(tǒng)雖然千差萬別，但是它們有以下的共同特征：

(1)有請求服務(wù)的人或物——顧客；

(2)有為顧客服務(wù)的人或物，即服務(wù)員或服務(wù)臺；

(3)顧客到達(dá)系統(tǒng)的時刻是隨機的，為每一位顧客提供服務(wù)的時間是隨機的，因而整個排隊系統(tǒng)的狀態(tài)也是隨機的。排隊系統(tǒng)的這種隨機性造成某個階段顧客排隊較長，而另外一些時候服務(wù)員(臺)又空閑無事。1.2排隊系統(tǒng)的組成和特征第十頁，共一百七十一頁，編輯于2023年，星期一111.2排隊系統(tǒng)的組成和特征排隊系統(tǒng)由三個基本部分組成：①輸入過程②排隊規(guī)則③服務(wù)機構(gòu)第十一頁，共一百七十一頁，編輯于2023年，星期一121.2排隊系統(tǒng)的組成和特征輸入過程輸入即指顧客到達(dá)排隊系統(tǒng)。輸入過程是指要求服務(wù)的顧客是按怎樣的規(guī)律到達(dá)排隊系統(tǒng)的過程，有時也把它稱為顧客流。一般可以從以下幾個方面來描述—個輸入過程(1)顧客的總體數(shù)，又稱顧客源、輸入源。這是指顧客的來源。顧客源可以是有限的，也可以是無限的。例如，到售票處購票的顧客總數(shù)可以認(rèn)為是無限的，而某個工廠因故障待修的機床則是有限的。第十二頁，共一百七十一頁，編輯于2023年，星期一131.2排隊系統(tǒng)的組成和特征輸入過程(2)顧客到來的方式。這是描述顧客是怎樣來到系統(tǒng)的，他們是單個到達(dá)，還是成批到達(dá)。病人到醫(yī)院看病是顧客單個到達(dá)的例子。在庫存問題中如將生產(chǎn)器材進(jìn)貨或產(chǎn)品入庫看作是顧客，那么這種顧客則是成批到達(dá)的。第十三頁，共一百七十一頁，編輯于2023年，星期一141.2排隊系統(tǒng)的組成和特征輸入過程(3)顧客流的概率分布，或稱相繼顧客到達(dá)的時間間隔的分布。這是求解排隊系統(tǒng)有關(guān)運行指標(biāo)問題時，首先需要確定的指標(biāo)。這也可以理解為在一定的時間間隔內(nèi)到達(dá)K個顧客(K=1、2、)的概率是多大。顧客相繼到達(dá)的間隔時間可以是確定型的，也可以是隨機型的。顧客流的概率分布一般有定長分布、二項分布、泊松流(最簡單流)、愛爾朗分布等若干種。第十四頁，共一百七十一頁，編輯于2023年，星期一151.2排隊系統(tǒng)的組成和特征輸入過程(4)顧客的到達(dá)可以是相互獨立的。(5)輸入過程可以是平穩(wěn)的，或稱對時間是齊次的，即描述相繼到達(dá)的間隔時間分布和所含參數(shù)(如期望值、方差等)都是與時間無關(guān)的。第十五頁，共一百七十一頁，編輯于2023年，星期一161.2排隊系統(tǒng)的組成和特征排隊規(guī)則

這是指服務(wù)臺從隊列中選取顧客進(jìn)行服務(wù)的順序。一般可以分為損失制、等待制和混合制等3大類。(1)損失制。這是指如果顧客到達(dá)排隊系統(tǒng)時，所有服務(wù)臺都已被先來的顧客占用，那么他們就自動離開系統(tǒng)永不再來。典型例子是，如電話拔號后出現(xiàn)忙音，顧客不愿等待而自動掛斷電話，如要再打，就需重新拔號，這種服務(wù)規(guī)則即為損失制。

第十六頁，共一百七十一頁，編輯于2023年，星期一171.2排隊系統(tǒng)的組成和特征排隊規(guī)則

(2)等待制。這是指當(dāng)顧客來到系統(tǒng)時，所有服務(wù)臺都不空，顧客加入排隊行列等待服務(wù)。例如，排隊等待售票，故障設(shè)備等待維修等。

對于等待制，為顧客進(jìn)行服務(wù)的次序可以采用下列各種規(guī)則：先到先服務(wù)(FCFS)后到先服務(wù)(LCFS)隨機服務(wù)(RS)有優(yōu)先權(quán)的服務(wù)第十七頁，共一百七十一頁，編輯于2023年，星期一181.2排隊系統(tǒng)的組成和特征排隊規(guī)則

(2)等待制。

對于等待制，為顧客進(jìn)行服務(wù)的次序可以采用下列各種規(guī)則：①先到先服務(wù)。按顧客到達(dá)的先后順序?qū)︻櫩瓦M(jìn)行服務(wù)，這是最普遍的情形。②后到先服務(wù)。倉庫中迭放的鋼材，后迭放上去的都先被領(lǐng)走，就屬于這種情況。③隨機服務(wù)。即當(dāng)服務(wù)臺空閑時，不按照排隊序列而隨意指定某個顧客去接受服務(wù)，如電話交換臺接通呼叫電話就是一例。④優(yōu)先權(quán)服務(wù)。如老人、兒童先進(jìn)車站；危重病員先就診；遇到重要數(shù)據(jù)需要處理計算機立即中斷其他數(shù)據(jù)的處理等，均屬于此種服務(wù)規(guī)則。第十八頁，共一百七十一頁，編輯于2023年，星期一191.2排隊系統(tǒng)的組成和特征排隊規(guī)則

(3)混合制．這是等待制與損失制相結(jié)合的一種服務(wù)規(guī)則，一般是指允許排隊，但又不允許隊列無限長下去。具體說來，大致有三種：①隊長有限。當(dāng)排隊等待服務(wù)的顧客人數(shù)超過規(guī)定數(shù)量時，后來的顧客就自動離去，另求服務(wù)，即系統(tǒng)的等待空間是有限的。例如最多只能容納K個顧客在系統(tǒng)中，當(dāng)新顧客到達(dá)時，若系統(tǒng)中的顧客數(shù)(又稱為隊長)小于K，則可進(jìn)入系統(tǒng)排隊或接受服務(wù)；否則，便離開系統(tǒng)，并不再回來。如水庫的庫容是有限的，旅館的床位是有限的。第十九頁，共一百七十一頁，編輯于2023年，星期一201.2排隊系統(tǒng)的組成和特征排隊規(guī)則

(3)混合制①隊長有限。②等待時間有限。即顧客在系統(tǒng)中的等待時間不超過某一給定的長度T，當(dāng)?shù)却龝r間超過T時，顧客將自動離去，并不再回來。如易損壞的電子元器件的庫存問題，超過一定存儲時間的元器件被自動認(rèn)為失效。又如顧客到飯館就餐，等了一定時間后不愿再等而自動離去另找飯店用餐。第二十頁，共一百七十一頁，編輯于2023年，星期一211.2排隊系統(tǒng)的組成和特征排隊規(guī)則

(3)混合制①隊長有限。②等待時間有限。③逗留時間(等待時間與服務(wù)時間之和)有限。例如用高射炮射擊敵機，當(dāng)敵機飛越高射炮射擊有效區(qū)域的時間為t時，若在這個時間內(nèi)未被擊落，也就不可能再被擊落了。

不難注意到，損失制和等待制可看成是混合制的特殊情形，如記s為系統(tǒng)中服務(wù)臺的個數(shù)，則當(dāng)K=s時，混合制即成為損失制；當(dāng)K=∞時，混合制即成為等待制。第二十一頁，共一百七十一頁，編輯于2023年，星期一221.2排隊系統(tǒng)的組成和特征排隊規(guī)則（續(xù)）從允許排隊的空間看隊列可以排在具體的處所，也可以是抽象的。排隊空間可以有限，也可以無限。從排隊的隊列數(shù)目看，可以是單列，也可以是多列。在多列的情形，各列間的顧客有的可以互相轉(zhuǎn)移，有的不能。有的排隊顧客因等候時間過長而中途退出，有的不能退出，必須堅持到被服務(wù)為止。第二十二頁，共一百七十一頁，編輯于2023年，星期一231.2排隊系統(tǒng)的組成和特征服務(wù)機構(gòu)

(服務(wù)臺情況)服務(wù)臺可以從以下3方面來描述：(1)服務(wù)臺數(shù)量及構(gòu)成形式。服務(wù)機構(gòu)可以沒有服務(wù)員，也可以有一個或多個服務(wù)員(服務(wù)臺、通道、窗口等)。從數(shù)量上說，服務(wù)臺有單服務(wù)臺和多服務(wù)臺之分。在有多個服務(wù)臺的情形中，可以是平行排列的，也可以是前后排列的，或混合排列的。第二十三頁，共一百七十一頁，編輯于2023年，星期一241.2排隊系統(tǒng)的組成和特征服務(wù)機構(gòu)

(服務(wù)臺情況)服務(wù)臺可以從以下3方面來描述：(1)服務(wù)臺數(shù)量及構(gòu)成形式。從構(gòu)成形式上看，服務(wù)臺有：

①單隊——單服務(wù)臺式；如(a)圖②單隊——多服務(wù)臺并聯(lián)式；如(c)圖③多隊——多服務(wù)臺并聯(lián)式；如(b)圖④單隊——多服務(wù)臺串聯(lián)式；如(d)圖⑤單隊——多服務(wù)臺并串聯(lián)混合式；⑥多隊——多服務(wù)臺并串聯(lián)混合式等等。服務(wù)臺的各種排列方式第二十四頁，共一百七十一頁，編輯于2023年，星期一25單隊列——S個服務(wù)臺并聯(lián)的排隊系統(tǒng)S個隊列——S個服務(wù)臺的并聯(lián)排隊系統(tǒng)1.2排隊系統(tǒng)的組成和特征第二十五頁，共一百七十一頁，編輯于2023年，星期一26單隊——多個服務(wù)臺的串聯(lián)排隊系統(tǒng)

多隊——多服務(wù)臺混聯(lián)、網(wǎng)絡(luò)系統(tǒng)1.2排隊系統(tǒng)的組成和特征第二十六頁，共一百七十一頁，編輯于2023年，星期一271.2排隊系統(tǒng)的組成和特征服務(wù)機構(gòu)

(服務(wù)臺情況)(2)服務(wù)方式。這是指在某一時刻接受服務(wù)的顧客數(shù)，它有單個服務(wù)和成批服務(wù)兩種。如公共汽車一次就可裝載一批乘客就屬于成批服務(wù)。(3)服務(wù)時間的分布。服務(wù)時間可分為確定型和隨機型。一般來說，在多數(shù)情況下，對每一個顧客的服務(wù)時間是一隨機變量，其概率分布有定長分布、負(fù)指數(shù)分布、K級愛爾良分布、一般分布(所有顧客的服務(wù)時間都是獨立同分布的)等等。服務(wù)時間的分布通常假定是平穩(wěn)的。第二十七頁，共一百七十一頁，編輯于2023年，星期一281.3排隊模型的分類排隊模型分類方法——D.G.Kendall，1953構(gòu)成排隊模型的三個主要特征指標(biāo)(1)相繼顧客到達(dá)間隔時間的分布；(2)服務(wù)時間的分布；(3)服務(wù)臺的個數(shù)。根據(jù)這三個特征對排隊模型進(jìn)行分類的Kendall記號：

X/Y/ZX：表示相繼到達(dá)間隔時間的分布；Y：表示服務(wù)時間的分布；Z：并列的服務(wù)臺的數(shù)目。第二十八頁，共一百七十一頁，編輯于2023年，星期一291.3排隊模型的分類表示相繼到達(dá)間隔時間和服務(wù)時間的各種分布符號M——負(fù)指數(shù)分布(M是Markov的字頭，因為負(fù)指數(shù)分布具有無記憶性，即Markov性)D——確定型(deterministic)Ek——k階愛爾朗(erlang)分布GI——一般相互獨立(generalindependent)的時間間隔的分布G——一般(general)服務(wù)時間的分布第二十九頁，共一百七十一頁，編輯于2023年，星期一301.3排隊模型的分類Kendall符號的擴(kuò)充

X/Y/Z/A/B/C其中前三項的意義不變，后三項的意義分別是：A：系統(tǒng)容量限制N，或稱等待空間容量。如系統(tǒng)有N個等待位子，則0<N

<∞。當(dāng)N

=0時，說明系統(tǒng)不允許等待，即為損失制。N

=∞時為等待制系統(tǒng)，此時∞般省略不寫。N為有限整數(shù)時，表示為混合制系統(tǒng)。B：顧客源數(shù)目m。分有限與無限兩種，∞表示顧客源無限，此時一般∞也可省略不寫。C：服務(wù)規(guī)則，如先到先服務(wù)(FCFS)，后到后服務(wù)(LCFS)，優(yōu)先權(quán)服務(wù)(PR)等。第三十頁，共一百七十一頁，編輯于2023年，星期一311.3排隊模型的分類Kendall符號的擴(kuò)充

X/Y/Z/A/B/C

某些情況下，排隊問題僅用上述表達(dá)形式中的前3個、4個、5個符號。如不特別說明則均理解為系統(tǒng)等待空間容量無限；顧客源無限，先到先服務(wù)，單個服務(wù)的等待制系統(tǒng)。約定：如略去后三項，即指X/Y/Z/∞/∞/FCFS的情形。例如：某排隊問題為M／M／S／∞／∞／FCFS／，則表示顧客到達(dá)間隔時間為負(fù)指數(shù)分布(泊松流)；服務(wù)時間為負(fù)指數(shù)分布；有s(s＞1)個服務(wù)臺；系統(tǒng)等待空間容量無限(等待制)；顧客源無限，采用先到先服務(wù)規(guī)則。第三十一頁，共一百七十一頁，編輯于2023年，星期一321.4排隊問題的求解首先需要確定屬于哪種排隊模型，其中顧客到達(dá)的間隔時間分布和服務(wù)時間的分布需要實測的數(shù)據(jù)來確定確定用以判斷系統(tǒng)運行優(yōu)劣的基本數(shù)量指標(biāo)，求出這些數(shù)量指標(biāo)的概率分布或特征數(shù)第三十二頁，共一百七十一頁，編輯于2023年，星期一331.4排隊問題的求解用于描述排隊系統(tǒng)運行狀況的基本數(shù)量指標(biāo)

(1)隊長：系統(tǒng)中的顧客數(shù)，是排隊等待的顧客數(shù)與正在接受服務(wù)的顧客數(shù)之和，期望值記作Ls；

排隊長（隊列長）：系統(tǒng)中排隊等待服務(wù)的顧客數(shù)，期望值記作Lq；

隊長和排隊長一般都是隨機變量。我們希望能確定它們的分布，或至少能確定它們的平均值(即平均隊長和平均排隊長)及有關(guān)的矩(如方差等)。隊長的分布是顧客和服務(wù)員都關(guān)心的，特別是對系統(tǒng)設(shè)計人員來說，如果能知道隊長的分布，就能確定隊長超過某個數(shù)的概率，從而確定合理的等待空間。第三十三頁，共一百七十一頁，編輯于2023年，星期一341.4排隊問題的求解用于描述排隊系統(tǒng)運行狀況的基本數(shù)量指標(biāo)

(2)逗留時間：顧客在系統(tǒng)中的停留時間，從顧客到達(dá)時刻起到他接受服務(wù)完成止這段時間，期望值記作Ws；是隨機變量，也是顧客最關(guān)心的指標(biāo)之一。

等待時間：顧客在系統(tǒng)中排隊等待的時間，從顧客到達(dá)時刻起到他開始接受服務(wù)止這段時間，期望值記作Wq，是隨機變量，也是顧客最關(guān)心的指標(biāo)，因為顧客通常希望等待時間越短越好。［逗留時間］＝［等待時間］＋［服務(wù)時間］

對這兩個指標(biāo)的研究當(dāng)然是希望能確定它們的分布，或至少能知道顧客的平均等待時間和平均逗留時間。第三十四頁，共一百七十一頁，編輯于2023年，星期一351.4排隊問題的求解用于描述排隊系統(tǒng)運行狀況的基本數(shù)量指標(biāo)

(3)

忙期：指從顧客到達(dá)空閑服務(wù)機構(gòu)起，到服務(wù)機構(gòu)再次為空閑止的時間長度，即服務(wù)機構(gòu)連續(xù)忙的時間。這是個隨機變量，是服務(wù)員最為關(guān)心的指標(biāo)，因為它關(guān)系到服務(wù)員的服務(wù)強度。閑期：即服務(wù)機構(gòu)連續(xù)保持空閑的時間。在排隊系統(tǒng)中，忙期和閑期總是交替出現(xiàn)的。其他一些指標(biāo)，如在損失制或系統(tǒng)容量有限的情況下，由于顧客被拒絕，而使服務(wù)系統(tǒng)受到損失的顧客損失率及服務(wù)強度等第三十五頁，共一百七十一頁，編輯于2023年，星期一361.4排隊問題的求解系統(tǒng)狀態(tài)的概率分布系統(tǒng)的狀態(tài)即指系統(tǒng)中的顧客數(shù)，它的可能取值是：(1)隊長沒有限制時，n=0，1，2，…(2)隊長有限制、最大數(shù)為N時，n=0，1，2，…，N(3)即時制且服務(wù)臺個數(shù)為c時，n=0，1，2，…，c系統(tǒng)處于這些狀態(tài)的概率一般是隨時間t變化的，所以在時刻t、系統(tǒng)狀態(tài)為n的概率可以用Pn(t)表示。第三十六頁，共一百七十一頁，編輯于2023年，星期一371.4排隊問題的求解求狀態(tài)概率Pn(t)的方法：

建立含Pn(t)的關(guān)系式，該關(guān)系式一般是包含Pn(t)的微分差分方程(關(guān)于t的微分方程，關(guān)于n的差分方程)。該方程的解稱為瞬態(tài)(或稱過渡狀態(tài))(transientstate)解。它的極限稱為穩(wěn)態(tài)(steadystate)解，或稱統(tǒng)計平衡狀態(tài)(statisticalequilibriumstate)解。第三十七頁，共一百七十一頁，編輯于2023年，星期一381.4排隊問題的求解穩(wěn)態(tài)解的物理意義當(dāng)系統(tǒng)運行了無限長時間后，初始(t=0)狀態(tài)的概率分布(Pn(0)，n≥0)的影響將消失，系統(tǒng)狀態(tài)的概率分布不再隨時間而變化。在實際應(yīng)用中，大多數(shù)系統(tǒng)會很快趨于穩(wěn)態(tài)，而無需等到t→∞以后。求穩(wěn)態(tài)概率Pn時，不需要求t→∞時Pn(t)的極限，而只需令導(dǎo)數(shù)P’n(t)=0即可。第三十八頁，共一百七十一頁，編輯于2023年，星期一391.4排隊問題的求解

上面給出的這些數(shù)量指標(biāo)一般都是和系統(tǒng)運行的時間有關(guān)的隨機變量，求這些隨機變量的瞬時分布一般是很困難的。為了分析上的簡便，并注意到相當(dāng)一部分排隊系統(tǒng)在運行了一定時間后，都會趨于一個平衡狀態(tài)(或稱平穩(wěn)狀態(tài))。在平衡狀態(tài)下，隊長的分布、等待時間的分布和忙期的分布都和系統(tǒng)所處的時刻無關(guān)，而且系統(tǒng)的初始狀態(tài)的影響也會消失。因此，本章中將主要討論與系統(tǒng)所處時刻無關(guān)的性質(zhì)，即統(tǒng)計平衡性質(zhì)。第三十九頁，共一百七十一頁，編輯于2023年，星期一40排隊論

第1節(jié)基本概念第2節(jié)到達(dá)間隔的分布和服務(wù)時間的分布第3節(jié)單服務(wù)臺負(fù)指數(shù)分布排隊系統(tǒng)的分析第4節(jié)多服務(wù)臺負(fù)指數(shù)分布排隊系統(tǒng)的分析第5節(jié)一般服務(wù)時間M/G/1模型第6節(jié)經(jīng)濟(jì)分析——系統(tǒng)的最優(yōu)化第7節(jié)分析排隊系統(tǒng)的隨機模擬法第四十頁，共一百七十一頁，編輯于2023年，星期一412.1到達(dá)間隔的分布2.1.1經(jīng)驗分布（定長輸入）2.1.2普阿松流（泊松流）2.1.3愛爾朗分布2.2服務(wù)時間的分布2.2.1經(jīng)驗分布（定長分布）2.2.2負(fù)指數(shù)分布2.2.3愛爾朗分布第2節(jié)到達(dá)間隔的分布和服務(wù)時間的分布第四十一頁，共一百七十一頁，編輯于2023年，星期一422.1.1經(jīng)驗分布例1

大連港大港區(qū)1979年載貨500噸以上船舶到達(dá)(不包括定期到達(dá)的船舶)逐日記錄見書上表12-2。將表12-2整理成船舶到達(dá)數(shù)的分布表?？梢杂嬎愠觯浩骄竭_(dá)率=到達(dá)總數(shù)/總天數(shù)=1271/365=3.48(艘/天)船舶到達(dá)數(shù)n頻數(shù)頻率(%)0120.0331430.1182640.1753740.2034710.1955490.1346260.0717190.052840.011920.00510以上10.003合計3651.000第四十二頁，共一百七十一頁，編輯于2023年，星期一432.1.1經(jīng)驗分布以τi表示第i號顧客到達(dá)的時刻，以si表示對它的服務(wù)時間，這樣可算出相繼到達(dá)的間隔時間ti(ti=τi+1-τi)和排隊等待時間wi，它們的關(guān)系如下：實際中測定相繼到達(dá)時間間隔的方法相繼到達(dá)時間間隔等待時間第四十三頁，共一百七十一頁，編輯于2023年，星期一442.1.1經(jīng)驗分布例2

某服務(wù)機構(gòu)是單服務(wù)臺，先到先服務(wù)，對41個顧客記錄到達(dá)時刻τ和服務(wù)時間s(單位為分鐘)如表12-4。在表中以第1號顧客到達(dá)時刻為0，對所有顧客的全部服務(wù)時間為127分鐘。將原始記錄整理成下表。到達(dá)間隔/分鐘次數(shù)162103846536272819110以上1合計40服務(wù)時間/分鐘次數(shù)1102103745546271819以上1合計41第四十四頁，共一百七十一頁，編輯于2023年，星期一452.1.1經(jīng)驗分布例2平均間隔時間=142/40=3.55(分鐘/人)平均到達(dá)率=41/142=0.28(人/分鐘)平均服務(wù)時間=127/41=3.12(分鐘/人)平均服務(wù)率=41/127=0.32(人/分鐘)第四十五頁，共一百七十一頁，編輯于2023年，星期一46普阿松流，又稱為泊松流、Poisson過程、最簡單流，是排隊論中一種常用來描述顧客到達(dá)規(guī)律的特殊的隨機過程。2.1.2普阿松流（泊松流）第四十六頁，共一百七十一頁，編輯于2023年，星期一472.1.2普阿松流（泊松流）設(shè)表示在時間區(qū)間內(nèi)到達(dá)的顧客數(shù)令表示在時間區(qū)間內(nèi)有個顧客到達(dá)的概率，即當(dāng)滿足下列三個條件時，我們說顧客的到達(dá)形成泊松流。(1)在不相重疊的時間區(qū)間內(nèi)顧客到達(dá)數(shù)是相互獨立的，即無后效性。通俗地說就是以前到達(dá)的顧客情況，對以后顧客的到來沒有影響。否則就是關(guān)聯(lián)的。(2)平穩(wěn)性。又稱作輸入過程是平穩(wěn)的，對充分小的，在時間區(qū)間內(nèi)有1個顧客到達(dá)的概率與t無關(guān)，而與區(qū)間長度成正比，即

其中，當(dāng)時，是關(guān)于的高階無窮小。

進(jìn)一步地，在長度為t的時段內(nèi)恰好到達(dá)k個顧客的概率僅與時段長度有關(guān)，而與時段起點無關(guān)。即對任意∈(0,∞)，在(,+t]或(0,t)內(nèi)恰好到達(dá)k個顧客的概率相等：(3)單個性又稱普通性。對于充分小的，在時間區(qū)間內(nèi)有2個或2個以上顧客到達(dá)的概率極小，以至于可以忽略，即

第四十七頁，共一百七十一頁，編輯于2023年，星期一48當(dāng)顧客到達(dá)為泊松流時，研究顧客到達(dá)數(shù)n的概率分布。由條件(2)，總可以取時間由0算起，并簡記由條件(2)和(3)，容易推得在區(qū)間內(nèi)沒有顧客到達(dá)的概率

將區(qū)間分成兩個互不重疊的區(qū)間和。則到達(dá)總數(shù)n分別出現(xiàn)在這兩個區(qū)間和上，有下列(A)(B)(C)三種情況：概率個數(shù)概率個數(shù)概率個數(shù)區(qū)間情況2.1.2普阿松流（泊松流）第四十八頁，共一百七十一頁，編輯于2023年，星期一492.1.2普阿松流（泊松流）在內(nèi)到達(dá)n個顧客應(yīng)是表中(A)(B)(C)三種互不相容的情況之一，所以概率應(yīng)是表中三個概率之和(各合為一項)令，得下列方程，并注意到初始條件，則有當(dāng)n=0時，沒有(B)，(C)兩種情況，所以得第四十九頁，共一百七十一頁，編輯于2023年，星期一50解(12-5)式和(12-6)式，得

表示長為t的時間區(qū)間內(nèi)到達(dá)n個顧客（即N(t)=n）的概率，由(12-7)式得隨機變量服從泊松分布。結(jié)論：當(dāng)顧客到達(dá)為泊松流時，在長度為t的時間內(nèi)到達(dá)n個顧客的概率Pn(t)服從泊松分布!!它的數(shù)學(xué)期望和方差分別是2.1.2普阿松流（泊松流）相等！特別地，t=1時，E[N(1)]=λ

，因此λ表示單位時間平均到達(dá)的顧客數(shù)第五十頁，共一百七十一頁，編輯于2023年，星期一51

是指相繼顧客到達(dá)時間間隔T相互獨立，其分布密度為

其中，k為非負(fù)整數(shù)。

2.1.3愛爾朗分布愛爾朗分布第五十一頁，共一百七十一頁，編輯于2023年，星期一522.1.3愛爾朗分布設(shè)是k個相互獨立的隨機變量，服從相同參數(shù)的負(fù)指數(shù)分布，那么的概率密度是稱T服從k階愛爾朗分布，其均值和方差分別為可以證明如下結(jié)論。第五十二頁，共一百七十一頁，編輯于2023年，星期一532.1.3愛爾朗分布愛爾朗分布的意義當(dāng)k=1時，愛爾朗分布化為負(fù)指數(shù)分布，可看成是一種完全隨機的分布；當(dāng)k增大時，愛爾朗分布的圖形逐漸變?yōu)閷ΨQ的；當(dāng)k≥30時愛爾朗分布近似于正態(tài)分布；k→∞時，Var［T］→0，這時愛爾朗分布化為確定型分布。一般k階愛爾朗分布可看成完全隨機與完全確定的中間型，能對現(xiàn)實世界提供更為廣泛的適應(yīng)性。第五十三頁，共一百七十一頁，編輯于2023年，星期一542.1.3愛爾朗分布可以證明，在參數(shù)為的泊松輸人中，對任意的j與k,設(shè)第j與第j+k個顧客之間的到達(dá)間隔為。則隨機變量Tk的分布必遵從參數(shù)為的愛爾朗分布，其分布密度為：

例如：

某排隊系統(tǒng)有并聯(lián)的k個服務(wù)臺，顧客流為泊松流，規(guī)定第i,K+i,2K+i…個顧客排入第i號臺(i=1,2,…,K)，則第K臺所獲得的顧客流，即為愛爾朗輸入流，其他各臺，從它的第一個顧客到達(dá)以后開始所獲得的流也為愛爾朗輸入流。第五十四頁，共一百七十一頁，編輯于2023年，星期一552.1到達(dá)間隔的分布2.1.1經(jīng)驗分布（定長輸入）2.1.2普阿松流（泊松流）2.1.3愛爾朗分布2.2服務(wù)時間的分布2.2.1經(jīng)驗分布（定長分布）2.2.2負(fù)指數(shù)分布2.2.3愛爾朗分布第2節(jié)到達(dá)間隔的分布和服務(wù)時間的分布第五十五頁，共一百七十一頁，編輯于2023年，星期一562.2服務(wù)時間的分布

2.2.1服務(wù)時間的定長分布。每一個顧客的服務(wù)時間都是常數(shù)，此時服務(wù)時間t的分布函數(shù)為：

第五十六頁，共一百七十一頁，編輯于2023年，星期一572.2.2服務(wù)時間的負(fù)指數(shù)分布如果隨機變量T的概率密度是則稱T服從負(fù)指數(shù)分布。它的分布函數(shù)是數(shù)學(xué)期望為方差為標(biāo)準(zhǔn)差為

負(fù)指數(shù)分布的定義第五十七頁，共一百七十一頁，編輯于2023年，星期一58服務(wù)時間v的分布對顧客的服務(wù)時間，也就是在忙期相繼離開系統(tǒng)的兩顧客的間隔時間，有時也服從負(fù)指數(shù)分布。設(shè)它的分布函數(shù)和密度分別是其中表示單位時間能被服務(wù)完成的顧客數(shù)，稱為平均服務(wù)率，表示對顧客的平均服務(wù)時間。2.2.2服務(wù)時間的負(fù)指數(shù)分布第五十八頁，共一百七十一頁，編輯于2023年，星期一59負(fù)指數(shù)分布的性質(zhì)(1)由條件概率公式容易證明該性質(zhì)稱為無記憶性或馬爾柯夫性。若T表示排隊系統(tǒng)中顧客相繼到達(dá)的間隔時間，該性質(zhì)說明：一個顧客到來所需的時間與過去一個顧客到來所需時間s無關(guān)，也就是說該顧客是隨機地到達(dá)。(2)當(dāng)輸入過程是泊松流時，那么顧客相繼到達(dá)的間隔時間T（注意T是隨機變量）必然服從負(fù)指數(shù)分布。這是因為對于泊松流，在區(qū)間內(nèi)至少有1個顧客到達(dá)的概率是又可表示為

根據(jù)（12.10）即得顧客相繼到達(dá)的間隔時間T必然服從負(fù)指數(shù)分布。2.2.2服務(wù)時間的負(fù)指數(shù)分布第五十九頁，共一百七十一頁，編輯于2023年，星期一60(2)當(dāng)輸入過程是泊松流時，那么顧客相繼到達(dá)的間隔時間T（注意T是隨機變量）必然服從負(fù)指數(shù)分布。這是因為對于泊松流，在區(qū)間內(nèi)至少有1個顧客到達(dá)的概率是又可表示為

根據(jù)（12.10）即得顧客相繼到達(dá)的間隔時間T必然服從負(fù)指數(shù)分布。上述內(nèi)容還可以用如下表達(dá)！

對于泊松流，其相繼顧客到達(dá)時間間隔i，i=1,2,…是相互獨立同分布的，其分布函數(shù)為負(fù)指數(shù)分布：

2.2.2服務(wù)時間的負(fù)指數(shù)分布第六十頁，共一百七十一頁，編輯于2023年，星期一61顧客相繼到達(dá)的間隔時間獨立且為同負(fù)指數(shù)分布(密度函數(shù)為)，與輸入過程為泊松流(參數(shù)為λ)是等價的。對于泊松流，λ表示單位時間平均到達(dá)的顧客數(shù)，1/λ表示相繼顧客到達(dá)平均間隔時間。

相繼到達(dá)時間間隔為負(fù)指數(shù)分布與到達(dá)為泊松流的等價性2.2.2服務(wù)時間的負(fù)指數(shù)分布第六十一頁，共一百七十一頁，編輯于2023年，星期一62

愛爾朗分布。即每個顧客的服務(wù)時間相互獨立，具有相同的愛爾朗分布。其密度函數(shù)為

其中>0為一常數(shù)，此種的平均服務(wù)時間為：

K=1時愛爾朗分布化歸為負(fù)指數(shù)分布當(dāng)K→∞時，得到長度為1/的定長服務(wù)。例子：串列的k個服務(wù)臺，每臺服務(wù)時間相互獨立，服從相同的負(fù)指數(shù)分布(參數(shù)kμ)，那么一顧客走完這k個服務(wù)臺總共所需要服務(wù)時間就服從k階愛爾朗分布。2.2.3服務(wù)時間的愛爾朗分布第六十二頁，共一百七十一頁，編輯于2023年，星期一63第1節(jié)基本概念第2節(jié)到達(dá)間隔的分布和服務(wù)時間的分布第3節(jié)單服務(wù)臺負(fù)指數(shù)分布排隊系統(tǒng)的分析第4節(jié)多服務(wù)臺負(fù)指數(shù)分布排隊系統(tǒng)的分析第5節(jié)一般服務(wù)時間M/G/1模型第6節(jié)經(jīng)濟(jì)分析——系統(tǒng)的最優(yōu)化第7節(jié)分析排隊系統(tǒng)的隨機模擬法排隊論

第六十三頁，共一百七十一頁，編輯于2023年，星期一64排隊論

排隊論研究的首要問題是排隊系統(tǒng)主要數(shù)量指標(biāo)的概率規(guī)律，即研究系統(tǒng)的整體性質(zhì)，然后進(jìn)一步研究系統(tǒng)的優(yōu)化問題。與這兩個問題相關(guān)的還包括排隊系統(tǒng)的統(tǒng)計推斷問題。

(1)通過研究主要數(shù)量指標(biāo)在瞬時或平穩(wěn)狀態(tài)下的概率分布及其數(shù)字特征，了解系統(tǒng)運行的基本特征。

(2)統(tǒng)計推斷問題，建立適當(dāng)?shù)呐抨犇Ｐ褪桥抨犝撗芯康牡谝徊?，建立模型過程中經(jīng)常會碰到如下問題：檢驗系統(tǒng)是否達(dá)到平穩(wěn)狀態(tài)；檢驗顧客相繼到達(dá)時間間隔的相互獨立性；確定服務(wù)時間的分布及有關(guān)參數(shù)等。第六十四頁，共一百七十一頁，編輯于2023年，星期一65(3)系統(tǒng)優(yōu)化問題，又稱為系統(tǒng)控制問題或系統(tǒng)運營問題，其基本目的是使系統(tǒng)處于最優(yōu)或最合理的狀態(tài)。系統(tǒng)優(yōu)化問題包括最優(yōu)設(shè)計問題和最優(yōu)運營問題，其內(nèi)容很多，有最少費用問題、服務(wù)率的控制問題、服務(wù)臺的開關(guān)策略、顧客(或服務(wù))根據(jù)優(yōu)先權(quán)的最優(yōu)排序等方面的問題。對于一般的排隊系統(tǒng)運行情況的分析，通常是在給定輸入與服務(wù)條件下，通過求解系統(tǒng)狀態(tài)為n(有n個顧客)的概率Pn(t)，再進(jìn)行計算其主要的運行指標(biāo)：排隊論

第六十五頁，共一百七十一頁，編輯于2023年，星期一66①系統(tǒng)中顧客數(shù)(隊長)的期望值L或Ls；②排隊等待的顧客數(shù)(排隊長)的期望值Lq；③顧客在系統(tǒng)中全部時間(逗留時間)的期望值W或Ws；④顧客排隊等待時間的期望值Wq。

排隊系統(tǒng)中，由于顧客到達(dá)分布和服務(wù)時間分布是多種多樣的，加之服務(wù)臺數(shù)。顧客源有限無限，排隊容量有限無限等的不同組合，就會有不勝枚舉的不同排隊模型，若對所有排隊模型都進(jìn)行分析與計算，不但十分繁雜而且也沒有必要。下面擬分析幾種常見排隊系統(tǒng)模型。排隊論

第六十六頁，共一百七十一頁，編輯于2023年，星期一673.1標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞)3.2系統(tǒng)容量有限的情況(M/M/1/N/∞)3.3顧客源有限的情形(M/M/1/∞/m)第3節(jié)單服務(wù)臺負(fù)指數(shù)分布排隊系統(tǒng)的分析本節(jié)討論輸入過程服從普阿松分布過程、服務(wù)時間服從負(fù)指數(shù)分布單服務(wù)臺的排隊系統(tǒng)。第六十七頁，共一百七十一頁，編輯于2023年，星期一68標(biāo)準(zhǔn)的M/M/1模型(1)輸入過程——顧客源是無限的，顧客單個到來，相互獨立，一定時間內(nèi)的到達(dá)數(shù)服從泊松分布，到達(dá)過程是平穩(wěn)的。(2)排隊規(guī)則——單隊，且對隊長沒有限制，先到先服務(wù)。(3)服務(wù)機構(gòu)——單服務(wù)臺，各顧客的服務(wù)時間相互獨立，服從相同的負(fù)指數(shù)分布。此外，還假定到達(dá)間隔時間和服務(wù)時間是相互獨立的。3.1標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞)即已知條件：

λ：顧客進(jìn)入系統(tǒng)的平均速度，即單位時間到達(dá)的顧客數(shù)。

μ：顧客離開系統(tǒng)的平均速度，即單位時間能被服務(wù)完成的顧客數(shù)。第六十八頁，共一百七十一頁，編輯于2023年，星期一69首先要求出：系統(tǒng)在任意時刻t的狀態(tài)為n(即系統(tǒng)中有n個顧客)的概率，它決定了系統(tǒng)運行的特征。因已知到達(dá)規(guī)律服從參數(shù)為的泊松過程，服務(wù)時間服從參數(shù)為的負(fù)指數(shù)分布，所以在時間區(qū)間內(nèi)分為：(1)有1個顧客到達(dá)的概率為沒有顧客到達(dá)的概率就是(2)當(dāng)有顧客在接受服務(wù)時，1個顧客被服務(wù)完了(離去)的概率是，沒有離去的概率就是。(3)多于一個顧客的到達(dá)或離去的概率是，可以忽略。3.1標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞)第六十九頁，共一百七十一頁，編輯于2023年，星期一703.1標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞)在時刻，系統(tǒng)中有n個顧客(n＞0)存在下列四種情況(到達(dá)或離去是2個以上的沒列入)：○表示發(fā)生(1個)；×表示沒有發(fā)生。n○○n(D)n×○n-1(C)n○×n+1(B)n××n(A)離去到達(dá)在時刻顧客數(shù)在區(qū)間在時刻t顧客數(shù)情況第七十頁，共一百七十一頁，編輯于2023年，星期一71第七十一頁，共一百七十一頁，編輯于2023年，星期一72這四種情況是互不相容的，所以應(yīng)是這四項之和，即即令，得關(guān)于的微分差分方程3.1標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞)所有的高階無窮小和并第七十二頁，共一百七十一頁，編輯于2023年，星期一73當(dāng)，則只有上表中(A)(B)情況，且方式(A)中無離去的概率為1，即同理求得它們的概率分別是情況(A)情況(B)情況(C)情況(D)n○○n(D)n×○n-1(C)n○×n+1(B)n××n(A)離去到達(dá)在時刻顧客數(shù)在區(qū)間在時刻t顧客數(shù)情況3.1標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞)第七十三頁，共一百七十一頁，編輯于2023年，星期一74研究穩(wěn)態(tài)的情況。這時與時間t無關(guān)，可寫成，它的導(dǎo)數(shù)為0。由(12-15)式和(12-16)式可得這是關(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)移率為。3.1標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞)這種系統(tǒng)狀態(tài)(n)隨時間變化的過程就是生滅過程（BirthandDeathProcess）。方程(12-15)、(12-16)解是瞬態(tài)解，無法應(yīng)用。第七十四頁，共一百七十一頁，編輯于2023年，星期一753.1標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞)對狀態(tài)0必須滿足以下平衡方程同樣對任何的狀態(tài)，可得如(12-18)所示的平衡方程。由(12-17)式可得將它代入(12-18)式，令，得到同理依次推得今設(shè)(否則隊列將排至無限遠(yuǎn))，又由概率的性質(zhì)知將的關(guān)系代入，得到第七十五頁，共一百七十一頁，編輯于2023年，星期一76對ρ的實際意義的解釋ρ＝λ/μ，是平均到達(dá)率與平均服務(wù)率之比，即在相同時區(qū)內(nèi)顧客到達(dá)的平均數(shù)與被服務(wù)的平均數(shù)之比。若將ρ表示為ρ＝(1/μ)/(1/λ)，它是一個顧客的服務(wù)時間與到達(dá)間隔時間之比，稱ρ為服務(wù)強度(trafficintensity)，或話務(wù)強度。由(12-19)式可知，ρ=1-P0，它刻畫了服務(wù)機構(gòu)的繁忙程度，所以ρ又稱為服務(wù)機構(gòu)的利用率。3.1標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞)系統(tǒng)處于空閑狀態(tài)的概率：系統(tǒng)處于繁忙狀態(tài)的概率：第七十六頁，共一百七十一頁，編輯于2023年，星期一77根據(jù)平穩(wěn)分布，求排隊系統(tǒng)的有關(guān)運行指標(biāo)(1)系統(tǒng)中的平均顧客數(shù)（平均隊長）

或 (2)在隊列中等待的平均顧客數(shù)

3.1標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞)期望第七十七頁，共一百七十一頁，編輯于2023年，星期一78顧客在系統(tǒng)中的逗留時間W(為一個隨機變量)在M/M/1情形下，服從參數(shù)為的負(fù)指數(shù)分布①，即

分布函數(shù)概率密度

于是，得到(3)

在系統(tǒng)中顧客逗留時間的期望值

(4)

在隊列中顧客等待時間的期望值

3.1標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞)平均逗留時間減去平均服務(wù)時間。第七十八頁，共一百七十一頁，編輯于2023年，星期一79將以上結(jié)果歸納如下：

它們的相互關(guān)系如下：

上式稱為Little公式。3.1標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞)第七十九頁，共一百七十一頁，編輯于2023年，星期一803.1標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞)Ls,Lq,λ

,Ws,Wq之間的關(guān)系：幾何解釋：穩(wěn)態(tài)時，一個顧客，進(jìn)入系統(tǒng)后，每單位時間，平均到達(dá)λ顧客。λλλλλ進(jìn)入時刻離開時刻總時間Ws

隊長Ls由時間段內(nèi)個λ組成的Ls=λWs同理：Lq=λWq

Ws=Wq+（1/μ）-------Ws與Wq只相差一段平均服務(wù)時間1/μ

第八十頁，共一百七十一頁，編輯于2023年，星期一81例1：考慮一個鐵路列車編組站。設(shè)待編列車到達(dá)時間間隔服從負(fù)指數(shù)分布，平均每小時到達(dá)2列；服務(wù)臺是編組站，編組時間服從負(fù)指數(shù)分布，平均每20分鐘可編一組。已知編組站上共有2股道，當(dāng)均被占用時，不能接車，再來的列車只能停在站外或前方站。求在平衡狀態(tài)下系統(tǒng)中列車的平均數(shù)；每一列車的平均逗留時間；等待編組的列車平均數(shù)。如果列車因站中2股道均被占用而停在站外或前方站時，每列車每小時費用為a元，求每天由于列車在站外等待而造成的損失。3.1標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞)第八十一頁，共一百七十一頁，編輯于2023年，星期一82解：本例可看成一個M/M/1/排隊問題，其中=2，=3，=/=2/3<1系統(tǒng)中列車的平均數(shù)L=/(1-)=(2/3)/(1-2/3)=2（列）列車在系統(tǒng)中的平均停留時間W=L/=2/2=1（小時）系統(tǒng)中等待編組的列車平均數(shù)Lq=L-=2-2/3=4/3（列）列車在系統(tǒng)中的平均等待編組時間

Wq=Lq/=(4/3)/(1/2)=2/3（小時）3.1標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞)第八十二頁，共一百七十一頁，編輯于2023年，星期一83記列車平均延誤（由于站內(nèi)2股道均被占用而不能進(jìn)站）時間為W0則W0=WP{N>2}=W{1-P0-P1-P2}=W{1-(l-)-(l-)1-(l-)2}=1*3=

3=(2/3)3=0.296（小時）故每天列車由于等待而支出的平均費用E=24W0a=24*2*0.296*a=14.2a元3.1標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞)第八十三頁，共一百七十一頁，編輯于2023年，星期一84例2：某修理店只有一位修理工，來修理的顧客到達(dá)過程為Poisson流，平均每小時4人；修理時間服從負(fù)指數(shù)分布，平均需要6分鐘。試求：修理店空閑的概率；店內(nèi)恰有3位顧客的概率；店內(nèi)至少有一位顧客的概率；在店內(nèi)平均顧客數(shù)；每位在店內(nèi)平均逗留時間；等待服務(wù)的平均顧客數(shù)；每位顧客平均等待服務(wù)時間；顧客在店內(nèi)等待時間超過10分鐘的概率。3.1標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞)第八十四頁，共一百七十一頁，編輯于2023年，星期一85解：本例可看成一個M/M/1/排隊問題，其中=4，=1/0.1=10(人/小時），=/=2/5<1修理店內(nèi)空閑的概率P0=1-=(1-2/5)=0.6店內(nèi)恰有3個顧客的概率P3=3(1-)=(2/5)3(1-2/5)=0.0383.1標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞)第八十五頁，共一百七十一頁，編輯于2023年，星期一86店內(nèi)至少有1位顧客的概率P{N1}=1-P0=1-

(1-)==2/5=0.4在店內(nèi)平均顧客數(shù)L=/(1-)=(2/5)/(1-2/5)=0.67(人）每位顧客在店內(nèi)平均逗留時間W=L/=0.67/4=10分鐘3.1標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞)第八十六頁，共一百七十一頁，編輯于2023年，星期一87等待服務(wù)的平均顧客數(shù)Lq=L-=0.67-2/5=0.27(人)每個顧客平均等待服務(wù)時間Wq=Lq/=0.27/4=0.0675小時

=4分鐘3.1標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞)第八十七頁，共一百七十一頁，編輯于2023年，星期一88顧客在店內(nèi)等待時間超過10分鐘的概率P{T>10}=e-10(1/6-1/15)=e-1=0.3677P{T>t}=e-(-)tt=10分鐘,=10人/小時=10/60=1/6=4人/小時=4/60=1/153.1標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞)第八十八頁，共一百七十一頁，編輯于2023年，星期一89例3

某醫(yī)院手術(shù)室根據(jù)病人來診和完成手術(shù)時間的記錄，任意抽查了100個工作小時，每小時來就診的病人數(shù)n的出現(xiàn)次數(shù)如下表所示；又任意抽查了100個完成手術(shù)的病歷，所用時間v(單位：小時)出現(xiàn)的次數(shù)如下表所示。到達(dá)的病人數(shù)n出現(xiàn)人數(shù)0101282316410566以上1合計100為病人完成手術(shù)時間v(小時)出現(xiàn)人數(shù)0.0~0.2380.2~0.4250.4~0.6170.6~0.890.8~1.061.0~1.251.2以上0合計1003.1標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞)第八十九頁，共一百七十一頁，編輯于2023年，星期一90(1)每小時病人平均到達(dá)率(人/小時)

每次手術(shù)平均時間(小時/人)

每小時完成手術(shù)人數(shù)(平均服務(wù)率)(人/小時)(2)取，，可以通過統(tǒng)計檢驗的方法，認(rèn)為病人到達(dá)數(shù)服從參數(shù)為2.1的泊松分布，手術(shù)時間服從參數(shù)為2.5的負(fù)指數(shù)分布。(3)說明服務(wù)機構(gòu)(手術(shù)室)有84%的時間是繁忙的，有16%的時間是空閑的。(4)依次代入(12-21)式，算出各指標(biāo)：在病房中病人數(shù)(期望值) (人)排隊等待病人數(shù)(期望值) (人)病人在病房中逗留時間(期望值) (小時)病人排隊等待時間(期望值) (小時)3.1標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞)第九十頁，共一百七十一頁，編輯于2023年，星期一91如果系統(tǒng)的最大容量為N，對于單服務(wù)臺的情形，排隊等待的顧客最多為N-1，在某時刻一顧客到達(dá)時，如系統(tǒng)中已有N個顧客，那么這個顧客就被拒絕進(jìn)入系統(tǒng)。當(dāng)N=1時為即時制的情形；當(dāng)N→∞時為容量無限制的情形。3.2系統(tǒng)的容量有限制的情況(M/M/1/N/∞)第九十一頁，共一百七十一頁，編輯于2023年，星期一92泊松輸入—負(fù)指數(shù)分布服務(wù)的排隊系統(tǒng)的一般決策過程：①根據(jù)已知條件繪制狀態(tài)轉(zhuǎn)移速度圖；②依據(jù)狀態(tài)轉(zhuǎn)移速度圖寫出各穩(wěn)態(tài)概率之間的關(guān)系；③求出P0

及

Pn；④計算各項數(shù)量運行指標(biāo)；⑤用系統(tǒng)運行指標(biāo)構(gòu)造目標(biāo)函數(shù)，對系統(tǒng)進(jìn)行優(yōu)化。3.2系統(tǒng)的容量有限制的情況(M/M/1/N/∞)第九十二頁，共一百七十一頁，編輯于2023年，星期一933.2系統(tǒng)的容量有限制的情況(M/M/1/N/∞)穩(wěn)態(tài)情形下各狀態(tài)間概率強度的轉(zhuǎn)換關(guān)系圖狀態(tài)概率的穩(wěn)態(tài)方程

∴第九十三頁，共一百七十一頁，編輯于2023年，星期一943.2系統(tǒng)的容量有限制的情況(M/M/1/N/∞)穩(wěn)態(tài)情形下各狀態(tài)間概率強度的轉(zhuǎn)換關(guān)系圖狀態(tài)概率的穩(wěn)態(tài)方程

其中(12-23a)也可寫成，則有第九十四頁，共一百七十一頁，編輯于2023年，星期一953.2系統(tǒng)的容量有限制的情況(M/M/1/N/∞)

由

N∑(λ/μ)nP0=1n=0

NP0=1/[∑(λ/μ)n]=

n=0(1-λ/μ)/

[(1-(λ/μ)N+1]λμ

1/(N+1)λ=μ

Pn=1/(N+1)λ=μ

(1-λ/μ)(λ/μ)n/[(1-(λ/μ)N+1]λμ

第九十五頁，共一百七十一頁，編輯于2023年，星期一96M/M/1/N/∞排隊系統(tǒng)的各項指標(biāo)：(1)隊長(期望值)(2)隊列長(期望值)(3)顧客逗留時間(期望值)(4)顧客等待時間(期望值)(5)有效到達(dá)率3.2系統(tǒng)的容量有限制的情況(M/M/1/N/∞)令，得到第九十六頁，共一百七十一頁，編輯于2023年，星期一97(ρ≠1,n≤N)∴(1)平均隊長Ls：(ρ≠1)試證ρ=1時,Ls=N/23.2系統(tǒng)的容量有限制的情況(M/M/1/N/∞)第九十七頁，共一百七十一頁，編輯于2023年，星期一98

???M/M/1/N/∞排隊系統(tǒng)的各項指標(biāo)：(1)隊長(期望值)(2)隊列長(期望值)(3)顧客逗留時間(期望值)(4)顧客等待時間(期望值)(5)有效到達(dá)率3.2系統(tǒng)的容量有限制的情況(M/M/1/N/∞)令，得到返回P98第九十八頁，共一百七十一頁，編輯于2023年，星期一99(2)有效到達(dá)率λe

系統(tǒng)容量有限，當(dāng)滿員（n=N）時，顧客將被拒絕，實際的顧客到達(dá)率與λ不一樣，還可驗證：∴

此種情況的公式與前類似,只有Ls不同,λe與λ不同。求λe必須先求得P0或PN才行。有效到達(dá)率為λe

可以證明：Ls3.2系統(tǒng)的容量有限制的情況(M/M/1/N/∞)第九十九頁，共一百七十一頁，編輯于2023年，星期一100M/M/1/N/∞排隊系統(tǒng)各項指標(biāo)的歸納(當(dāng)時)：3.2系統(tǒng)的容量有限制的情況(M/M/1/N/∞)第一百頁，共一百七十一頁，編輯于2023年，星期一101例2．某單人理發(fā)館共有六把椅子接待顧客排隊，無座時將離去，顧客平均到達(dá)率為3人/h，理發(fā)時間平均為15分鐘，求：(1)求某一顧客到達(dá)就能理發(fā)的概率;(2)求需要等待的顧客數(shù)的期望值;(3)求有效到達(dá)率;(4)求一顧客在系統(tǒng)中的逗留時間和排隊時間平均值;(5)在可能到來的顧客中，有百分之幾不等待就離開？3.2系統(tǒng)的容量有限制的情況(M/M/1/N/∞)第一百零一頁，共一百七十一頁，編輯于2023年，星期一102(1)求某一顧客到達(dá)就能理發(fā)的概率:(2)求需要等待的顧客數(shù)的期望值:(3)求有效到達(dá)率:(4)求一顧客在系統(tǒng)中的逗留時間和排隊時間平均值:3.2系統(tǒng)的容量有限制的情況(M/M/1/N/∞)第一百零二頁，共一百七十一頁，編輯于2023年，星期一103P0=0.27780P1=0.20836P2=0.15627P3=0.11720=0.9629=96.29%1-0.9629=3.71%

P4=0.08790P5=0.06593P6=0.04944(5)在可能到來的顧客中，有百分之幾不等待就離開？顧客為何不等待就離去？因為系統(tǒng)已經(jīng)滿員3.2系統(tǒng)的容量有限制的情況(M/M/1/N/∞)故拒絕的概率為3.71%第一百零三頁，共一百七十一頁，編輯于2023年，星期一104例4

某單人理發(fā)館為等待的顧客準(zhǔn)備了6把椅子，當(dāng)6把椅子都坐滿時，再來的顧客將不進(jìn)店而離開。顧客的平均到達(dá)率為3人/小時，理發(fā)平均需要15分鐘。則系統(tǒng)的容量為N=6+1=7，人/小時，人/小時。(1)某顧客一到達(dá)就能理發(fā)的概率(2)需要等待的顧客數(shù)的期望值

(3)有效到達(dá)率

(人/小時)(4)一顧客在理發(fā)館內(nèi)逗留的期望時間

(小時)(分鐘)3.2系統(tǒng)的容量有限制的情況(M/M/1/N/∞)第一百零四頁，共一百七十一頁，編輯于2023年，星期一105(5)在可能到來的顧客中不等待就離開的概率這也是理發(fā)館的損失率。人/小時人/小時有限隊長2.111.390.730.480.2783.7無限隊長32.251.00.750.250以本例為例，比較隊長為有限和無限的情形：3.2系統(tǒng)的容量有限制的情況(M/M/1/N/∞)第一百零五頁，共一百七十一頁，編輯于2023年，星期一106背景設(shè)有m臺機器(顧客總體)，機器因故障停機表示“到達(dá)”，待修的機器形成隊列，修理工人是服務(wù)員，本節(jié)討論單服務(wù)員的情形。顧客總體雖只有m個，但每個顧客到來并經(jīng)過服務(wù)后，仍回到原來總體，所以仍然可以再到來。如在機器故障問題中，同一臺機器出了故障(到來)并經(jīng)修好(服務(wù)完了)仍可再出故障，形成循環(huán)。模型符號中的∞表示對系統(tǒng)的容量沒有限制，但實際上它不會超過m，所以可寫成(M/M/1/m/m)。3.3顧客源為有限的情形(M/M/1/∞/m)第一百零六頁，共一百七十一頁，編輯于2023年，星期一107設(shè)每個顧客的到達(dá)率相同，均為λ

(這里λ的含義是單臺機器在單位時間里發(fā)生故障的概率或平均次數(shù))；設(shè)系統(tǒng)內(nèi)顧客數(shù)為Ls，則系統(tǒng)外的顧客平均數(shù)為mLs，所以系統(tǒng)的有效到達(dá)率為

λe=λ(mLs)(12-26)考慮穩(wěn)態(tài)情況下狀態(tài)間的轉(zhuǎn)移率由狀態(tài)0轉(zhuǎn)移到狀態(tài)1：每臺設(shè)備由正常狀態(tài)轉(zhuǎn)移為故障狀態(tài)的轉(zhuǎn)移率為λP0，m臺設(shè)備由無故障狀態(tài)轉(zhuǎn)移為有一臺設(shè)備(不論哪一臺)發(fā)生故障的轉(zhuǎn)移率為mλP0。由狀態(tài)1轉(zhuǎn)移到狀態(tài)0：其狀態(tài)轉(zhuǎn)移率為μP1。所以，狀態(tài)0時有平衡方程為：

mλP0=μP13.3顧客源為有限的情形(M/M/1/∞/m)第一百零七頁，共一百七十一頁，編輯于2023年，星期一108各狀態(tài)間的轉(zhuǎn)移差分方程解得(注意到因而不要求）系統(tǒng)的各項指標(biāo)為3.3顧客源為有限的情形(M/M/1/∞/m)第一百零八頁，共一百七十一頁，編輯于2023年，星期一109例5

某車間有5臺機器，每臺機器的連續(xù)運轉(zhuǎn)時間服從負(fù)指數(shù)分布，平均連續(xù)運轉(zhuǎn)時間15分鐘，有一個修理工，每次修理時間服從負(fù)指數(shù)分布，平均每次12分鐘。求：(1)修理工空閑的概率；(2)五臺機器都出故障的概率；(3)出故障的平均臺數(shù)；(4)等待修理的平均臺數(shù)；(5)平均停工時間；(6)平均等待修理時間；(7)評價這些結(jié)果。3.3顧客源為有限的情形(M/M/1/∞/m)第一百零九頁，共一百七十一頁，編輯于2023年，星期一110解：

(1)(2)五臺機器都出現(xiàn)故障的概率(3)出故障的平均臺數(shù)(臺)(4)等待修理的平均臺數(shù)

(臺)(5)平均停工時間

(分鐘)(6)平均等待修理時間(分鐘)(7)機器停工時間過長，修理工幾乎沒有空閑時間，應(yīng)當(dāng)提高服務(wù)率減少修理時間或增加修理工人。3.3顧客源為有限的情形(M/M/1/∞/m)第一百一十頁，共一百七十一頁，編輯于2023年，星期一111第1節(jié)基本概念第2節(jié)到達(dá)間隔的分布和服務(wù)時間的分布第3節(jié)單服務(wù)臺負(fù)指數(shù)分布排隊系統(tǒng)的分析第4節(jié)多服務(wù)臺負(fù)指數(shù)分布排隊系統(tǒng)的分析第5節(jié)一般服務(wù)時間M/G/1模型第6節(jié)經(jīng)濟(jì)分析——系統(tǒng)的最優(yōu)化第7節(jié)分析排隊系統(tǒng)的隨機模擬法排隊論

第一百一十一頁，共一百七十一頁，編輯于2023年，星期一112本節(jié)討論單隊、并列的多服務(wù)臺（服務(wù)臺數(shù)為c）的情形。4.1標(biāo)準(zhǔn)的M/M/c模型4.2M/M/c型系統(tǒng)和c個M/M/1型系統(tǒng)的比較4.3系統(tǒng)容量有限的情形（M/M/c/N/）4.4顧客源有限的情形（M/M/c//m）第4節(jié)多服務(wù)臺負(fù)指數(shù)分布排隊系統(tǒng)的分析第一百一十二頁，共一百七十一頁，編輯于2023年，星期一1134.1標(biāo)準(zhǔn)的M/M/c模型標(biāo)準(zhǔn)的M/M/c模型各種特征的規(guī)定與標(biāo)準(zhǔn)的M/M/1模型的規(guī)定相同。各服務(wù)臺工作是相互獨立的(不搞協(xié)作)，且平均服務(wù)率相同。整個服務(wù)機構(gòu)的平均服務(wù)率為(當(dāng))；為