排隊(duì)論及其模型

1、1,排 隊(duì) 論,運(yùn)籌學(xué),2,排隊(duì)論,排隊(duì)論(queuing theory)也稱隨機(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ì)論是1909年由丹麥工程師愛爾朗(A.K．Erlang)在研究電活系統(tǒng)時(shí)創(chuàng)立的，幾十年來排

2、隊(duì)論的應(yīng)用領(lǐng)域越來越廣泛，理論也日漸完善。特別是自二十世紀(jì)60年代以來，由于計(jì)算機(jī)的飛速發(fā)展，更為排隊(duì)論的應(yīng)用開拓了寬闊的前景。,4,排隊(duì)論,排隊(duì)論(queuing theory) 研究內(nèi)容包括三個(gè)部分： (1) 排隊(duì)系統(tǒng)的性態(tài)問題 (2) 排隊(duì)系統(tǒng)的最優(yōu)化問題 (3) 排隊(duì)系統(tǒng)的統(tǒng)計(jì)推斷問題,性態(tài)問題，即研究各種排隊(duì)系統(tǒng)的概率規(guī)律性，主要研究隊(duì)長分布、等待時(shí)間分布和忙期分布等。,最優(yōu)化，又分靜態(tài)最優(yōu)和動(dòng)態(tài)最優(yōu)，前者指最優(yōu)

3、設(shè)計(jì)，后者指現(xiàn)有排隊(duì)系統(tǒng)的最優(yōu)運(yùn)營。,統(tǒng)計(jì)推斷，即判斷一個(gè)給定的排隊(duì)系統(tǒng)符合哪種模型，以便根據(jù)排隊(duì)理論進(jìn)行研究。,解排隊(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ì)論,,第1節(jié) 基本概念第2節(jié) 到達(dá)間隔的分布和服務(wù)時(shí)間的分布第3節(jié) 單服務(wù)臺(tái)負(fù)指數(shù)分布排隊(duì)系統(tǒng)的分析第4節(jié) 多服務(wù)臺(tái)負(fù)指數(shù)分布排隊(duì)系統(tǒng)的分析第5節(jié) 一般服務(wù)時(shí)間M/G/1模型第6節(jié)

4、經(jīng)濟(jì)分析——系統(tǒng)的最優(yōu)化第7節(jié) 分析排隊(duì)系統(tǒng)的隨機(jī)模擬法,6,第1節(jié) 基 本 概 念,1.1 排隊(duì)過程的一般表示1.2 排隊(duì)系統(tǒng)的組織和特征1.3 排隊(duì)模型的分類1.4 排隊(duì)問題的求解,7,不同的顧客與服務(wù)組成了各式各樣的服務(wù)系統(tǒng)。顧客為了得到某種服務(wù)而到達(dá)系統(tǒng)、若不能立即獲得服務(wù)而又允許排隊(duì)等待，則加入隊(duì)列排隊(duì)等待接受服務(wù)，然后服務(wù)臺(tái)按一定規(guī)則從隊(duì)列中選擇顧客進(jìn)行服務(wù)，獲得服務(wù)的顧客立即離開系統(tǒng)。,1.1 排隊(duì)過程的一般表示,

5、8,1.1 排隊(duì)過程的一般表示,各個(gè)顧客由顧客源(總體)出發(fā)，到達(dá)服務(wù)機(jī)構(gòu)(服務(wù)臺(tái)、服務(wù)員)前排隊(duì)等候接受服務(wù)，服務(wù)完成后離開。排隊(duì)結(jié)構(gòu)指隊(duì)列的數(shù)目和排列方式，排隊(duì)規(guī)則和服務(wù)規(guī)則是說明顧客在排隊(duì)系統(tǒng)中按怎樣的規(guī)則、次序接受服務(wù)的。,排隊(duì)過程的一般模型,9,1.1 排隊(duì)過程的一般表示,形形色色的排隊(duì)系統(tǒng),10,實(shí)際的排隊(duì)系統(tǒng)雖然千差萬別，但是它們 有以下的共同特征： (1)有請求服務(wù)的人或物——顧客；

6、(2)有為顧客服務(wù)的人或物，即服務(wù)員或服務(wù)臺(tái)； (3)顧客到達(dá)系統(tǒng)的時(shí)刻是隨機(jī)的，為每一位顧客提供服務(wù)的時(shí)間是隨機(jī)的，因而整個(gè)排隊(duì)系統(tǒng)的狀態(tài)也是隨機(jī)的。排隊(duì)系統(tǒng)的這種隨機(jī)性造成某個(gè)階段顧客排隊(duì)較長，而另外一些時(shí)候服務(wù)員(臺(tái))又空閑無事。,1.2 排隊(duì)系統(tǒng)的組成和特征,11,1.2 排隊(duì)系統(tǒng)的組成和特征,排隊(duì)系統(tǒng)由三個(gè)基本部分組成：① 輸入過程② 排隊(duì)規(guī)則③ 服務(wù)機(jī)構(gòu),12,1.2 排隊(duì)系統(tǒng)的組成和特征,輸入過程輸入

7、即指顧客到達(dá)排隊(duì)系統(tǒng)。輸入過程是指要求服務(wù)的顧客是按怎樣的規(guī)律到達(dá)排隊(duì)系統(tǒng)的過程，有時(shí)也把它稱為顧客流。一般可以從以下幾個(gè)方面來描述—個(gè)輸入過程(1) 顧客的總體數(shù)，又稱顧客源、輸入源。這是指顧客的來源。 顧客源可以是有限的，也可以是無限的。 例如，到售票處購票的顧客總數(shù)可以認(rèn)為是無限的，而某個(gè)工廠因故障待修的機(jī)床則是有限的。,13,1.2 排隊(duì)系統(tǒng)的組成和特征,輸入過程(2) 顧客到來的方式。這是描述顧客是怎樣來到系

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

9、的，也可以是隨機(jī)型的。 顧客流的概率分布一般有定長分布、二項(xiàng)分布、泊松流(最簡單流)、愛爾朗分布等若干種。,15,1.2 排隊(duì)系統(tǒng)的組成和特征,輸入過程(4) 顧客的到達(dá)可以是相互獨(dú)立的。(5) 輸入過程可以是平穩(wěn)的，或稱對時(shí)間是齊次的，即描述相繼到達(dá)的間隔時(shí)間分布和所含參數(shù)(如期望值、方差等)都是與時(shí)間無關(guān)的。,16,1.2 排隊(duì)系統(tǒng)的組成和特征,排隊(duì)規(guī)則 這是指服務(wù)臺(tái)從隊(duì)列中選取顧客進(jìn)行服務(wù)的順序。一般可以分為損失制、等

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

11、為顧客進(jìn)行服務(wù)的次序可以采用下列各種規(guī)則：先到先服務(wù)(FCFS)后到先服務(wù)(LCFS)隨機(jī)服務(wù)(RS)有優(yōu)先權(quán)的服務(wù),18,1.2 排隊(duì)系統(tǒng)的組成和特征,排隊(duì)規(guī)則 (2)等待制。 對于等待制，為顧客進(jìn)行服務(wù)的次序可以采用下列各種規(guī)則： ① 先到先服務(wù)。按顧客到達(dá)的先后順序?qū)︻櫩瓦M(jìn)行服務(wù)，這是最普遍的情形。 ② 后到先服務(wù)。倉庫中迭放的鋼材，后迭放上去的都先被領(lǐng)走，就屬于這種情況。 ③

12、 隨機(jī)服務(wù)。即當(dāng)服務(wù)臺(tái)空閑時(shí)，不按照排隊(duì)序列而隨意指定某個(gè)顧客去接受服務(wù)，如電話交換臺(tái)接通呼叫電話就是一例。 ④ 優(yōu)先權(quán)服務(wù)。如老人、兒童先進(jìn)車站；危重病員先就診；遇到重要數(shù)據(jù)需要處理計(jì)算機(jī)立即中斷其他數(shù)據(jù)的處理等，均屬于此種服務(wù)規(guī)則。,19,1.2 排隊(duì)系統(tǒng)的組成和特征,排隊(duì)規(guī)則 (3)混合制．這是等待制與損失制相結(jié)合的一種服務(wù)規(guī)則，一般是指允許排隊(duì)，但又不允許隊(duì)列無限長下去。具體說來，大致有三種： ① 隊(duì)長有限。當(dāng)排

13、隊(duì)等待服務(wù)的顧客人數(shù)超過規(guī)定數(shù)量時(shí)，后來的顧客就自動(dòng)離去，另求服務(wù)，即系統(tǒng)的等待空間是有限的。例如最多只能容納K個(gè)顧客在系統(tǒng)中，當(dāng)新顧客到達(dá)時(shí)，若系統(tǒng)中的顧客數(shù)(又稱為隊(duì)長)小于K，則可進(jìn)入系統(tǒng)排隊(duì)或接受服務(wù)；否則，便離開系統(tǒng)，并不再回來。如水庫的庫容是有限的，旅館的床位是有限的。,20,1.2 排隊(duì)系統(tǒng)的組成和特征,排隊(duì)規(guī)則 (3)混合制① 隊(duì)長有限。② 等待時(shí)間有限。即顧客在系統(tǒng)中的等待時(shí)間不超過某一給定的長度T，當(dāng)?shù)却龝r(shí)間超

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

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

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

17、來描述：(1) 服務(wù)臺(tái)數(shù)量及構(gòu)成形式。從構(gòu)成形式上看，服務(wù)臺(tái)有： ①單隊(duì)——單服務(wù)臺(tái)式；如(a)圖 ②單隊(duì)——多服務(wù)臺(tái)并聯(lián)式；如(c)圖 ③多隊(duì)——多服務(wù)臺(tái)并聯(lián)式；如(b)圖 ④單隊(duì)——多服務(wù)臺(tái)串聯(lián)式；如(d)圖 ⑤單隊(duì)——多服務(wù)臺(tái)并串聯(lián)混合式； ⑥多隊(duì)——多服務(wù)臺(tái)并串聯(lián)混合式等等。,服務(wù)臺(tái)的各種排列方式,25,單隊(duì)列——S個(gè)服務(wù)臺(tái)并聯(lián)的排隊(duì)系統(tǒng),S個(gè)隊(duì)列——S個(gè)服務(wù)臺(tái)的并聯(lián)排隊(duì)系統(tǒng),1.2 排隊(duì)

18、系統(tǒng)的組成和特征,26,單隊(duì)——多個(gè)服務(wù)臺(tái)的串聯(lián)排隊(duì)系統(tǒng),,多隊(duì)——多服務(wù)臺(tái)混聯(lián)、網(wǎng)絡(luò)系統(tǒng),1.2 排隊(duì)系統(tǒng)的組成和特征,27,1.2 排隊(duì)系統(tǒng)的組成和特征,服務(wù)機(jī)構(gòu) (服務(wù)臺(tái)情況)(2) 服務(wù)方式。這是指在某一時(shí)刻接受服務(wù)的顧客數(shù)，它有單個(gè)服務(wù)和成批服務(wù)兩種。如公共汽車一次就可裝載一批乘客就屬于成批服務(wù)。(3) 服務(wù)時(shí)間的分布。服務(wù)時(shí)間可分為確定型和隨機(jī)型。一般來說，在多數(shù)情況下，對每一個(gè)顧客的服務(wù)時(shí)間是一隨機(jī)變量，其概率分布有定

19、長分布、負(fù)指數(shù)分布、K級愛爾良分布、一般分布(所有顧客的服務(wù)時(shí)間都是獨(dú)立同分布的)等等。服務(wù)時(shí)間的分布通常假定是平穩(wěn)的。,28,1.3 排隊(duì)模型的分類,排隊(duì)模型分類方法——D.G.Kendall，1953構(gòu)成排隊(duì)模型的三個(gè)主要特征指標(biāo)(1) 相繼顧客到達(dá)間隔時(shí)間的分布；(2) 服務(wù)時(shí)間的分布；(3) 服務(wù)臺(tái)的個(gè)數(shù)。根據(jù)這三個(gè)特征對排隊(duì)模型進(jìn)行分類的Kendall記號：

20、 X/Y/ZX：表示相繼到達(dá)間隔時(shí)間的分布；Y：表示服務(wù)時(shí)間的分布；Z：并列的服務(wù)臺(tái)的數(shù)目。,29,1.3 排隊(duì)模型的分類,表示相繼到達(dá)間隔時(shí)間和服務(wù)時(shí)間的各種分布符號M——負(fù)指數(shù)分布(M是Markov的字頭，因?yàn)樨?fù)指數(shù)分布具有無記憶性，即Markov性)D——確定型(deterministic)Ek——k階愛爾朗(erlang)分布GI—— 一般相互獨(dú)立(general independent)的時(shí)間

21、間隔的分布G—— 一般(general)服務(wù)時(shí)間的分布,30,1.3 排隊(duì)模型的分類,Kendall符號的擴(kuò)充 X/Y/Z/A/B/C其中前三項(xiàng)的意義不變，后三項(xiàng)的意義分別是：A：系統(tǒng)容量限制N，或稱等待空間容量。如系統(tǒng)有N個(gè)等待位子，則 0< N <∞。當(dāng) N =0 時(shí)，說明系統(tǒng)不允許等待，即為損失制。N =∞ 時(shí)為等待制系統(tǒng)，此時(shí)∞般省略不寫。N為有限整數(shù)時(shí)，表示為混合制系統(tǒng)。

22、B：顧客源數(shù)目m。分有限與無限兩種，∞表示顧客源無限，此時(shí)一般∞也可省略不寫。C：服務(wù)規(guī)則，如先到先服務(wù)(FCFS)，后到后服務(wù)(LCFS)，優(yōu)先權(quán)服務(wù)(PR)等。,31,1.3 排隊(duì)模型的分類,Kendall符號的擴(kuò)充 X/Y/Z/A/B/C 某些情況下，排隊(duì)問題僅用上述表達(dá)形式中的前3個(gè)、4個(gè)、5個(gè)符號。如不特別說明則均理解為系統(tǒng)等待空間容量無限；顧客源無限，先到先服務(wù)，單個(gè)服務(wù)的等待制

23、系統(tǒng)。約定：如略去后三項(xiàng)，即指X/Y/Z/∞/∞/FCFS的情形。例如：某排隊(duì)問題為M／M／S／∞／∞／FCFS／，則表示顧客到達(dá)間隔時(shí)間為負(fù)指數(shù)分布(泊松流)；服務(wù)時(shí)間為負(fù)指數(shù)分布；有s(s＞1)個(gè)服務(wù)臺(tái)；系統(tǒng)等待空間容量無限(等待制)；顧客源無限，采用先到先服務(wù)規(guī)則。,32,1.4 排隊(duì)問題的求解,首先需要確定屬于哪種排隊(duì)模型，其中顧客到達(dá)的間隔時(shí)間分布和服務(wù)時(shí)間的分布需要實(shí)測的數(shù)據(jù)來確定 確定用以判斷系統(tǒng)運(yùn)行優(yōu)劣的基本數(shù)量指

24、標(biāo)，求出這些數(shù)量指標(biāo)的概率分布或特征數(shù),33,1.4 排隊(duì)問題的求解,用于描述排隊(duì)系統(tǒng)運(yùn)行狀況的基本數(shù)量指標(biāo) (1) 隊(duì)長：系統(tǒng)中的顧客數(shù)，是排隊(duì)等待的顧客數(shù)與正在接受服務(wù)的顧客數(shù)之和，期望值記作Ls； 排隊(duì)長（隊(duì)列長）：系統(tǒng)中排隊(duì)等待服務(wù)的顧客數(shù)，期望值記作Lq； 隊(duì)長和排隊(duì)長一般都是隨機(jī)變量。我們希望能確定它們的分布，或至少能確定它們的平均值(即平均隊(duì)長和平均排隊(duì)長)及有

25、關(guān)的矩(如方差等)。隊(duì)長的分布是顧客和服務(wù)員都關(guān)心的，特別是對系統(tǒng)設(shè)計(jì)人員來說，如果能知道隊(duì)長的分布，就能確定隊(duì)長超過某個(gè)數(shù)的概率，從而確定合理的等待空間。,,34,1.4 排隊(duì)問題的求解,用于描述排隊(duì)系統(tǒng)運(yùn)行狀況的基本數(shù)量指標(biāo) (2) 逗留時(shí)間：顧客在系統(tǒng)中的停留時(shí)間，從顧客到達(dá)時(shí)刻起到他接受服務(wù)完成止這段時(shí)間，期望值記作Ws； 是隨機(jī)變量，也是顧客最關(guān)心的指標(biāo)之一。 等待時(shí)間：顧客在系統(tǒng)中排隊(duì)等待的時(shí)間，從顧客到達(dá)時(shí)刻起到

26、他開始接受服務(wù)止這段時(shí)間，期望值記作Wq， 是隨機(jī)變量，也是顧客最關(guān)心的指標(biāo)，因?yàn)轭櫩屯ǔＯＭ却龝r(shí)間越短越好。 ［逗留時(shí)間］＝［等待時(shí)間］＋［服務(wù)時(shí)間］ 對這兩個(gè)指標(biāo)的研究當(dāng)然是希望能確定它們的分布，或至少能知道顧客的平均等待時(shí)間和平均逗留時(shí)間。,,35,1.4 排隊(duì)問題的求解,用于描述排隊(duì)系統(tǒng)運(yùn)行狀況的基本數(shù)量指標(biāo) (3) 忙期：指從顧客到達(dá)空閑服務(wù)機(jī)構(gòu)起，到服務(wù)機(jī)構(gòu)再次為空閑止的時(shí)間長

27、度 ，即服務(wù)機(jī)構(gòu)連續(xù)忙的時(shí)間。 這是個(gè)隨機(jī)變量，是服務(wù)員最為關(guān)心的指標(biāo)，因?yàn)樗P(guān)系到服務(wù)員的服務(wù)強(qiáng)度。 閑期：即服務(wù)機(jī)構(gòu)連續(xù)保持空閑的時(shí)間。 在排隊(duì)系統(tǒng)中，忙期和閑期總是交替出現(xiàn)的。其他一些指標(biāo)，如在損失制或系統(tǒng)容量有限的情況下，由于顧客被拒絕，而使服務(wù)系統(tǒng)受到損失的顧客損失率及服務(wù)強(qiáng)度等,,36,1.4 排隊(duì)問題的求解,系統(tǒng)狀態(tài)的概率分布系統(tǒng)的狀態(tài)即指系統(tǒng)中的顧客數(shù)，它的可能取值是：(1) 隊(duì)長沒有限制時(shí)，n=0，1，

28、2，…(2) 隊(duì)長有限制、最大數(shù)為N時(shí)，n=0，1，2，…，N(3) 即時(shí)制且服務(wù)臺(tái)個(gè)數(shù)為c時(shí)，n=0，1，2，…，c系統(tǒng)處于這些狀態(tài)的概率一般是隨時(shí)間t變化的，所以在時(shí)刻t、系統(tǒng)狀態(tài)為n的概率可以用Pn(t)表示。,37,1.4 排隊(duì)問題的求解,求狀態(tài)概率Pn(t)的方法： 建立含Pn(t)的關(guān)系式，該關(guān)系式一般是包含Pn(t)的微分差分方程(關(guān)于t的微分方程，關(guān)于n的差分方程)。該方程的解稱為瞬態(tài)(或稱過渡狀態(tài))(tran

29、sient state)解。它的極限稱為穩(wěn)態(tài)(steady state)解，或稱統(tǒng)計(jì)平衡狀態(tài)(statistical equilibrium state)解。,,38,1.4 排隊(duì)問題的求解,穩(wěn)態(tài)解的物理意義當(dāng)系統(tǒng)運(yùn)行了無限長時(shí)間后，初始(t=0)狀態(tài)的概率分布(Pn(0)，n≥0)的影響將消失，系統(tǒng)狀態(tài)的概率分布不再隨時(shí)間而變化。在實(shí)際應(yīng)用中，大多數(shù)系統(tǒng)會(huì)很快趨于穩(wěn)態(tài)，而無需等到t→∞以后。求穩(wěn)態(tài)概率Pn時(shí)，不需要求t→∞

30、時(shí)Pn(t)的極限，而只需令導(dǎo)數(shù)P’n(t)=0即可。,39,1.4 排隊(duì)問題的求解,上面給出的這些數(shù)量指標(biāo)一般都是和系統(tǒng)運(yùn)行的時(shí)間有關(guān)的隨機(jī)變量，求這些隨機(jī)變量的瞬時(shí)分布一般是很困難的。 為了分析上的簡便，并注意到相當(dāng)一部分排隊(duì)系統(tǒng)在運(yùn)行了一定時(shí)間后，都會(huì)趨于一個(gè)平衡狀態(tài)(或稱平穩(wěn)狀態(tài))。在平衡狀態(tài)下，隊(duì)長的分布、等待時(shí)間的分布和忙期的分布都和系統(tǒng)所處的時(shí)刻無關(guān)，而且系統(tǒng)的初始狀態(tài)的影響也會(huì)消失。因此，本章中將主要討論與系統(tǒng)所

31、處時(shí)刻無關(guān)的性質(zhì)，即統(tǒng)計(jì)平衡性質(zhì)。,40,,排隊(duì)論,第1節(jié) 基本概念第2節(jié) 到達(dá)間隔的分布和服務(wù)時(shí)間的分布第3節(jié) 單服務(wù)臺(tái)負(fù)指數(shù)分布排隊(duì)系統(tǒng)的分析第4節(jié) 多服務(wù)臺(tái)負(fù)指數(shù)分布排隊(duì)系統(tǒng)的分析第5節(jié) 一般服務(wù)時(shí)間M/G/1模型第6節(jié) 經(jīng)濟(jì)分析——系統(tǒng)的最優(yōu)化第7節(jié) 分析排隊(duì)系統(tǒng)的隨機(jī)模擬法,41,2.1 到達(dá)間隔的分布2.1.1 經(jīng)驗(yàn)分布（定長輸入）2.1.2 普阿松流（泊松流）2.1.3 愛爾朗分布2.2 服務(wù)時(shí)間的

32、分布2.2.1 經(jīng)驗(yàn)分布（定長分布）2.2.2 負(fù)指數(shù)分布2.2.3 愛爾朗分布,第2節(jié) 到達(dá)間隔的分布和服務(wù)時(shí)間的分布,42,2.1.1 經(jīng)驗(yàn)分布,例1 大連港大港區(qū)1979年載貨500噸以上船舶到達(dá)(不包括定期到達(dá)的船舶)逐日記錄見書上表12-2。將表12-2整理成船舶到達(dá)數(shù)的分布表?？梢杂?jì)算出：平均到達(dá)率=到達(dá)總數(shù)/總天數(shù)=1271/365=3.48(艘/天),43,2. 1.1 經(jīng)驗(yàn)分布,以τi表示第i號顧客到

33、達(dá)的時(shí)刻，以si表示對它的服務(wù)時(shí)間，這樣可算出相繼到達(dá)的間隔時(shí)間ti (ti=τi+1-τi)和排隊(duì)等待時(shí)間wi，它們的關(guān)系如下：,,實(shí)際中測定相繼到達(dá)時(shí)間間隔的方法,相繼到達(dá)時(shí)間間隔等待時(shí)間,44,2. 1.1 經(jīng)驗(yàn)分布,例2 某服務(wù)機(jī)構(gòu)是單服務(wù)臺(tái)，先到先服務(wù)，對41個(gè)顧客記錄到達(dá)時(shí)刻τ和服務(wù)時(shí)間s(單位為分鐘)如表12-4。在表中以第1號顧客到達(dá)時(shí)刻為0，對所有顧客的全部服務(wù)時(shí)間為127分鐘。將原始記錄整理成下表。,45,2.

34、 1.1 經(jīng)驗(yàn)分布,例2平均間隔時(shí)間=142/40=3.55(分鐘/人)平均到達(dá)率=41/142=0.28(人/分鐘)平均服務(wù)時(shí)間=127/41=3.12(分鐘/人)平均服務(wù)率=41/127=0.32(人/分鐘),46,普阿松流，又稱為泊松流、Poisson過程、最簡單流，是排隊(duì)論中一種常用來描述顧客到達(dá)規(guī)律的特殊的隨機(jī)過程。,2.1.2 普阿松流（泊松流）,47,2.1.2 普阿松流（泊松流）,設(shè) 表示在時(shí)

35、間區(qū)間 內(nèi)到達(dá)的顧客數(shù) 令 表示在時(shí)間區(qū)間 內(nèi)有 個(gè)顧客到達(dá)的概率，即當(dāng) 滿足下列三個(gè)條件時(shí)，我們說顧客的到達(dá)形成泊松流。 (1) 在不相重疊的時(shí)間區(qū)間內(nèi)顧客到達(dá)數(shù)是相互獨(dú)立的，即無后效性。 通俗地說就是以前到達(dá)的顧客情況，對以后顧客的到來沒有影響。否則就是關(guān)聯(lián)的。(2)平穩(wěn)性。又稱作輸入過程是平穩(wěn)的，

36、對充分小的 ，在時(shí)間區(qū)間內(nèi)有1個(gè)顧客到達(dá)的 概率與t無關(guān)，而與區(qū)間長度 成正比，即 其中 ，當(dāng) 時(shí)，是關(guān)于 的高階無窮小。 進(jìn)一步地，在長度為t的時(shí)段內(nèi)恰好到

37、達(dá)k個(gè)顧客的概率僅與時(shí)段長度有關(guān)，而與時(shí)段起點(diǎn)無關(guān)。即對任意?∈(0,∞)，在(?,?+t]或(0,t)內(nèi)恰好到達(dá)k個(gè)顧客的概率相等：(3)單個(gè)性又稱普通性。對于充分小的 ，在時(shí)間區(qū)間 內(nèi)有2個(gè)或2個(gè)以上顧客到達(dá)的概率極小，以至于可以忽略，即,,,,,,,,,,,,,,,,48,當(dāng)顧客到達(dá)為泊松流時(shí)，研究顧客到達(dá)數(shù)n的概率分布。由條件(2)，總可以取時(shí)間由0算起，并簡記由條件(2)和(

38、3)，容易推得在 區(qū)間內(nèi)沒有顧客到達(dá)的概率 將區(qū)間 分成兩個(gè)互不重疊的區(qū)間 和 。則到達(dá)總數(shù)n分別出現(xiàn)在這兩個(gè)區(qū)間 和

39、 上，有下列(A)(B)(C)三種情況：,,,,,,,,,,,,,,,,,,2.1.2 普阿松流（泊松流）,49,2.1.2 普阿松流（泊松流）,在 內(nèi)到達(dá)n個(gè)顧客應(yīng)是表中(A)(B)(C)三種互不相容的情況之一，所以概率 應(yīng)是表中三個(gè)概率之和(各 合為一項(xiàng))令 ，得下列方程，并注意

40、到初始條件，則有當(dāng)n=0 時(shí)，沒有(B)，(C)兩種情況， 所以得,,,,,,50,解(12-5)式和(12-6)式，得 表示長為t的時(shí)間區(qū)間內(nèi)到達(dá)n個(gè)顧客（即N (t)=n）的概率，由(12-7)式得隨機(jī)變量 服從

41、泊松分布。結(jié)論：當(dāng)顧客到達(dá)為泊松流時(shí)，在長度為t的時(shí)間內(nèi)到達(dá)n個(gè)顧客的概率Pn(t)服從泊松分布!!它的數(shù)學(xué)期望和方差分別是,,,,,2.1.2 普阿松流（泊松流）,,,,相等！,特別地，t=1時(shí)，E[N(1)]= λ ，因此λ表示單位時(shí)間平均到達(dá)的顧客數(shù),51,是指相繼顧客到達(dá)時(shí)間間隔T相互獨(dú)立，其分布密度為

42、 其中，k為非負(fù)整數(shù)。,,,2.1.3 愛爾朗分布,愛爾朗分布,52,2.1.3 愛爾朗分布,設(shè) 是k個(gè)相互獨(dú)立的隨機(jī)變量，服從相同參數(shù) 的負(fù)指數(shù)分布，那么 的概率密度是稱T服從k階愛爾朗分布，其均值和方差分別為,,,,,,,,可以證明如下結(jié)論。,53,2.1

43、.3 愛爾朗分布,愛爾朗分布的意義當(dāng)k=1時(shí)，愛爾朗分布化為負(fù)指數(shù)分布，可看成是一種完全隨機(jī)的分布；當(dāng)k增大時(shí)，愛爾朗分布的圖形逐漸變?yōu)閷ΨQ的；當(dāng)k≥30時(shí)愛爾朗分布近似于正態(tài)分布；k→∞時(shí)，Var［T］→0，這時(shí)愛爾朗分布化為確定型分布。一般k階愛爾朗分布可看成完全隨機(jī)與完全確定的中間型，能對現(xiàn)實(shí)世界提供更為廣泛的適應(yīng)性。,54,2.1.3 愛爾朗分布,可以證明，在參數(shù)為?的泊松輸人中，對任意的j與k,設(shè)第j與第j+k個(gè)

44、顧客之間的到達(dá)間隔為 。則隨機(jī)變量Tk的分布必遵從參數(shù)為?的愛爾朗分布，其分布密度為：,,例如： 某排隊(duì)系統(tǒng)有并聯(lián)的k個(gè)服務(wù)臺(tái)，顧客流為泊松流，規(guī)定第i, K+i, 2K+i…個(gè)顧客排入第i號臺(tái)(i=1,2,…,K)，則第K臺(tái)所獲得的顧客流，即為愛爾朗輸入流，其他各臺(tái)，從它的第一個(gè)顧客到達(dá)以后開始所獲得的流也為愛爾朗輸入流。,55,2.1 到達(dá)間隔的分布2.1.1 經(jīng)驗(yàn)分布（

45、定長輸入）2.1.2 普阿松流（泊松流）2.1.3 愛爾朗分布2.2 服務(wù)時(shí)間的分布2.2.1 經(jīng)驗(yàn)分布（定長分布）2.2.2 負(fù)指數(shù)分布2.2.3 愛爾朗分布,第2節(jié) 到達(dá)間隔的分布和服務(wù)時(shí)間的分布,56,2.2 服務(wù)時(shí)間的分布,2.2.1 服務(wù)時(shí)間的定長分布。每一個(gè)顧客的服務(wù)時(shí)間都是常數(shù)?，此時(shí)服務(wù)時(shí)間t的分布函數(shù)為：,,,57,2.2.2 服務(wù)時(shí)間的負(fù)指數(shù)分布,如果隨機(jī)變量T的概率密度是則稱T服從負(fù)指數(shù)分布

46、。它的分布函數(shù)是數(shù)學(xué)期望為 方差為標(biāo)準(zhǔn)差為,,,,,負(fù)指數(shù)分布的定義,58,服務(wù)時(shí)間v 的分布對顧客的服務(wù)時(shí)間，也就是在忙期相繼離開系統(tǒng)的兩顧客的間隔時(shí)間，有時(shí)也服從負(fù)指數(shù)分布。設(shè)它的分布函數(shù)和密度分別是其中 表示單位時(shí)間能被服務(wù)完成的顧客數(shù)，稱為平均服務(wù)率， 表示對顧客的平均服務(wù)時(shí)間。,,,2.2.2 服務(wù)時(shí)間的負(fù)指數(shù)分布,59,負(fù)指數(shù)分布的性質(zhì)(1

47、) 由條件概率公式容易證明該性質(zhì)稱為無記憶性或馬爾柯夫性。若T表示排隊(duì)系統(tǒng)中顧客相繼到達(dá)的間隔時(shí)間，該性質(zhì)說明：一個(gè)顧客到來所需的時(shí)間與過去一個(gè)顧客到來所需時(shí)間s 無關(guān)，也就是說該顧客是隨機(jī)地到達(dá)。(2) 當(dāng)輸入過程是泊松流時(shí)，那么顧客相繼到達(dá)的間隔時(shí)間T（注意T是隨機(jī)變量）必然服從負(fù)指數(shù)分布。這是因?yàn)閷τ诓此闪?，在區(qū)間 內(nèi)至少有1個(gè)顧客到達(dá)的概率是又可表示為 根據(jù)（12.10）即得顧客

48、相繼到達(dá)的間隔時(shí)間T必然服從負(fù)指數(shù)分布。,,,,,,2.2.2 服務(wù)時(shí)間的負(fù)指數(shù)分布,60,(2) 當(dāng)輸入過程是泊松流時(shí)，那么顧客相繼到達(dá)的間隔時(shí)間T（注意T是隨機(jī)變量）必然服從負(fù)指數(shù)分布。這是因?yàn)閷τ诓此闪?，在區(qū)間 內(nèi)至少有1個(gè)顧客到達(dá)的概率是又可表示為 根據(jù)（12.10）即得顧客相繼到達(dá)的間隔時(shí)間T必然服從負(fù)指數(shù)分布。,,,,,上述內(nèi)容還可以用如下表達(dá)！,對于泊松流

49、，其相繼顧客到達(dá)時(shí)間間隔?i，i=1,2,…是相互獨(dú)立同分布的，其分布函數(shù)為負(fù)指數(shù)分布：,2.2.2 服務(wù)時(shí)間的負(fù)指數(shù)分布,61,顧客相繼到達(dá)的間隔時(shí)間獨(dú)立且為同負(fù)指數(shù)分布(密度函數(shù)為 )，與輸入過程為泊松流(參數(shù)為λ)是等價(jià)的。對于泊松流，λ表示單位時(shí)間平均到達(dá)的顧客數(shù)，1/ λ表示相繼顧客到達(dá)平均間隔時(shí)間。,,,,相繼到達(dá)時(shí)間間隔為負(fù)指數(shù)分布與到達(dá)為泊松流的等價(jià)性,2.2.2 服務(wù)時(shí)間的負(fù)指數(shù)

50、分布,62,愛爾朗分布。即每個(gè)顧客的服務(wù)時(shí)間相互獨(dú)立，具有相同的愛爾朗分布。其密度函數(shù)為 其中?>0為一常數(shù)，此種的平均服務(wù)時(shí)間為： K=1時(shí)愛爾朗分布化歸為負(fù)指數(shù)分布當(dāng)K→∞時(shí)，得到長度為1/?的定長服務(wù)。,,例子：串列的k個(gè)服務(wù)臺(tái)，每臺(tái)服務(wù)時(shí)間相互獨(dú)立，服從相同的負(fù)指數(shù)分布(參數(shù)kμ)，那么一顧客走完這k個(gè)服務(wù)臺(tái)總共所需要服

51、務(wù)時(shí)間就服從k階愛爾朗分布。,2.2.3 服務(wù)時(shí)間的愛爾朗分布,63,,第1節(jié) 基本概念第2節(jié) 到達(dá)間隔的分布和服務(wù)時(shí)間的分布第3節(jié) 單服務(wù)臺(tái)負(fù)指數(shù)分布排隊(duì)系統(tǒng)的分析第4節(jié) 多服務(wù)臺(tái)負(fù)指數(shù)分布排隊(duì)系統(tǒng)的分析第5節(jié) 一般服務(wù)時(shí)間M/G/1模型第6節(jié) 經(jīng)濟(jì)分析——系統(tǒng)的最優(yōu)化第7節(jié) 分析排隊(duì)系統(tǒng)的隨機(jī)模擬法,排隊(duì)論,64,排隊(duì)論,排隊(duì)論研究的首要問題是排隊(duì)系統(tǒng)主要數(shù)量指標(biāo)的概率規(guī)律，即研究系統(tǒng)的整體性質(zhì)，然后進(jìn)一步研究系統(tǒng)的優(yōu)

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

53、使系統(tǒng)處于最優(yōu)或最合理的狀態(tài)。 系統(tǒng)優(yōu)化問題包括最優(yōu)設(shè)計(jì)問題和最優(yōu)運(yùn)營問題，其內(nèi)容很多，有最少費(fèi)用問題、服務(wù)率的控制問題、服務(wù)臺(tái)的開關(guān)策略、顧客(或服務(wù))根據(jù)優(yōu)先權(quán)的最優(yōu)排序等方面的問題。 對于一般的排隊(duì)系統(tǒng)運(yùn)行情況的分析，通常是在給定輸入與服務(wù)條件下，通過求解系統(tǒng)狀態(tài)為n(有n個(gè)顧客)的概率Pn(t)，再進(jìn)行計(jì)算其主要的運(yùn)行指標(biāo)：,排隊(duì)論,66,①系統(tǒng)中顧客數(shù)(隊(duì)長)的期望值L或Ls； ②排隊(duì)等待的顧客

54、數(shù)(排隊(duì)長)的期望值Lq； ③顧客在系統(tǒng)中全部時(shí)間(逗留時(shí)間)的期望值W或Ws； ④顧客排隊(duì)等待時(shí)間的期望值Wq。 排隊(duì)系統(tǒng)中，由于顧客到達(dá)分布和服務(wù)時(shí)間分布是多種多樣的，加之服務(wù)臺(tái)數(shù)。顧客源有限無限，排隊(duì)容量有限無限等的不同組合，就會(huì)有不勝枚舉的不同排隊(duì)模型，若對所有排隊(duì)模型都進(jìn)行分析與計(jì)算，不但十分繁雜而且也沒有必要。 下面擬分析幾種常見排隊(duì)系統(tǒng)模型。,排隊(duì)論,

55、67,3.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ù)臺(tái)負(fù)指數(shù)分布排隊(duì)系統(tǒng)的分析,本節(jié)討論輸入過程服從普阿松分布過程、服務(wù)時(shí)間服從負(fù)指數(shù)分布單服務(wù)臺(tái)的排隊(duì)系統(tǒng)。,68,標(biāo)準(zhǔn)的M/M/1模型(1) 輸入過程——顧客源是無限的，顧客單個(gè)到來，相互獨(dú)立，一定時(shí)間內(nèi)的到達(dá)數(shù)服從泊松分布，到達(dá)過程是平穩(wěn)的。(2) 排隊(duì)規(guī)則

56、——單隊(duì)，且對隊(duì)長沒有限制，先到先服務(wù)。(3) 服務(wù)機(jī)構(gòu)——單服務(wù)臺(tái)，各顧客的服務(wù)時(shí)間相互獨(dú)立，服從相同的負(fù)指數(shù)分布。此外，還假定到達(dá)間隔時(shí)間和服務(wù)時(shí)間是相互獨(dú)立的。,3.1 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞),即已知條件： λ：顧客進(jìn)入系統(tǒng)的平均速度，即單位時(shí)間到達(dá)的顧客數(shù)。 μ：顧客離開系統(tǒng)的平均速度，即單位時(shí)間能被服務(wù)完成的顧客數(shù)。,69,首先要求出：系統(tǒng)在任意時(shí)刻t的狀態(tài)為n(即系統(tǒng)中有n個(gè)顧客)的概率

57、 ，它決定了系統(tǒng)運(yùn)行的特征。因已知到達(dá)規(guī)律服從參數(shù)為 的泊松過程，服務(wù)時(shí)間服從參數(shù)為 的負(fù)指數(shù)分布，所以在 時(shí)間區(qū)間內(nèi)分為：(1) 有1個(gè)顧客到達(dá)的概率為 沒有顧客到達(dá)的概率就是 (2) 當(dāng)有顧客在接受服務(wù)時(shí)，1個(gè)顧客被服務(wù)完了(離去)的概率是 ，沒有離去

58、的概率就是 。(3) 多于一個(gè)顧客的到達(dá)或離去的概率是 ，可以忽略。,,,,,,,,,,3.1 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞),70,3.1 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞),在時(shí)刻 ，系統(tǒng)中有n個(gè)顧客(n＞0)存在下列四種情況(到達(dá)或離去是2個(gè)以上的沒列入)：○表示發(fā)生(1個(gè))；×表示沒有發(fā)生。,,,,,,,

59、71,72,,這四種情況是互不相容的，所以 應(yīng)是這四項(xiàng)之和，即 即令 ，得關(guān)于 的微分差分方程,,,,,,,3.1 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞),所有的高階無窮小和并,73,當(dāng) ，則只有上表中(A)(B)情況，且方式(A)中無離去的概率為1，即同理求得,它們的概率分別是 情況(A)情況(B) 情況(C

60、)情況(D),,,,,,,3.1 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞),74,研究穩(wěn)態(tài)的情況。這時(shí) 與時(shí)間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)(

61、n)隨時(shí)間變化的過程就是生滅過程（Birth and Death Process）。 方程(12-15)、(12-16) 解是瞬態(tài)解，無法應(yīng)用。,75,3.1 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞),對狀態(tài)0必須滿足以下平衡方程同樣對任何 的狀態(tài)，可得如(12-18)所示的平衡方程。由(12-17)式可得將它代入(12-18)式，令 ，得到同理依次推得今設(shè)

62、 (否則隊(duì)列將排至無限遠(yuǎn))，又由概率的性質(zhì)知 將 的關(guān)系代入 ，得到,,,,,,,,,,,,76,對ρ的實(shí)際意義的解釋ρ＝λ/μ，是平均到達(dá)率與平均服務(wù)率之比，即在相同時(shí)區(qū)內(nèi)顧客到達(dá)的平均數(shù)與被服務(wù)的平均數(shù)之比。若將ρ表示為ρ＝(1/μ)/(1/λ)，它是一個(gè)顧客的服務(wù)時(shí)間與到達(dá)間隔時(shí)間之比，稱ρ為服務(wù)強(qiáng)度(traffic intensity)，或話務(wù)

63、強(qiáng)度。由(12-19)式可知，ρ=1-P0，它刻畫了服務(wù)機(jī)構(gòu)的繁忙程度，所以ρ又稱為服務(wù)機(jī)構(gòu)的利用率。,3.1 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞),系統(tǒng)處于空閑狀態(tài)的概率：,系統(tǒng)處于繁忙狀態(tài)的概率：,77,根據(jù)平穩(wěn)分布，求排隊(duì)系統(tǒng)的有關(guān)運(yùn)行指標(biāo)(1) 系統(tǒng)中的平均顧客數(shù)（平均隊(duì)長） 或 (2) 在隊(duì)列中等待的平均顧客數(shù),,,,,,,3.1 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞),期望,78,顧客在系

64、統(tǒng)中的逗留時(shí)間W(為一個(gè)隨機(jī)變量)在M/M/1情形下，服從參數(shù)為? ? ? 的負(fù)指數(shù)分布①，即 分布函數(shù) 概率密度,,,,,,于是，得到(3) 在系統(tǒng)中顧客逗留時(shí)間的期望值 (4) 在隊(duì)列中顧客等待時(shí)間的期望值,3.1 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞),平均逗留時(shí)間減去平均服務(wù)時(shí)間。,79,將以上結(jié)果歸納如下： 它們的相互關(guān)系如下： 上式稱為Lit

65、tle公式。,,,,,3.1 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞),80,3.1 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞),Ls ,L q,λ ,Ws ,Wq之間的關(guān)系：幾何解釋： 穩(wěn)態(tài)時(shí)，一個(gè)顧客，進(jìn)入系統(tǒng)后，每單位時(shí)間，平均到達(dá)λ顧客。,隊(duì)長Ls由時(shí)間段內(nèi)個(gè)λ組成的,,Ls=λWs,同理：Lq=λWq Ws=Wq+（1/μ）-------Ws與Wq只相差一段平均服務(wù)時(shí)間1/μ,81,,例1：考慮一個(gè)鐵路列車編組站。

66、設(shè)待編列車到達(dá)時(shí)間間隔服從負(fù)指數(shù)分布，平均每小時(shí)到達(dá)2列；服務(wù)臺(tái)是編組站，編組時(shí)間服從負(fù)指數(shù)分布，平均每20分鐘可編一組。已知編組站上共有2股道，當(dāng)均被占用時(shí)，不能接車，再來的列車只能停在站外或前方站。求在平衡狀態(tài)下系統(tǒng)中列車的平均數(shù)； 每一列車的平均逗留時(shí)間； 等待編組的列車平均數(shù)。 如果列車因站中2股道均被占用而停在站外或前方站時(shí)，每列車每小時(shí)費(fèi)用為a元，求每天由于列車在站外等待而造成的損失。,3.1

67、 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞),82,,解：本例可看成一個(gè)M/M/1/?排隊(duì)問題，其中? =2，? =3，?= ?/?=2/3<1系統(tǒng)中列車的平均數(shù)L= ?/ (1-?)=(2/3)/(1-2/3)=2（列）列車在系統(tǒng)中的平均停留時(shí)間W=L/?= 2/2=1（小時(shí)）系統(tǒng)中等待編組的列車平均數(shù)Lq=L-?= 2-2/3=4/3（列）列車在系統(tǒng)中的平均等待編組時(shí)間 Wq = Lq/ ?=(4/3)/(1/

68、2)=2/3（小時(shí)）,3.1 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/∞/∞),83,,記列車平均延誤（由于站內(nèi)2股道均被占用而不能進(jìn)站）時(shí)間為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（小時(shí)）故每天列車由于等待而支出的平均費(fèi)用E=24?W0a=24*2*0.296*a=14.2a元,3.1 標(biāo)準(zhǔn)的M/