排隊論及其模型

1、1,排 隊 論,運籌學,2,排隊論,排隊論(queuing theory)也稱隨機服務系統(tǒng)理論(Random Service System Theory)，是為研究和解決具有擁擠現(xiàn)象的問題而發(fā)展起來的一門應用數(shù)學的分支。 具體地說，它是在研究各種排隊系統(tǒng)概率規(guī)律性的基礎上，解決相應排隊系統(tǒng)的最優(yōu)設計和最優(yōu)控制問題。,3,排隊論,排隊論是1909年由丹麥工程師愛爾朗(A.K．Erlang)在研究電活系統(tǒng)時創(chuàng)立的，幾十年來排

2、隊論的應用領域越來越廣泛，理論也日漸完善。特別是自二十世紀60年代以來，由于計算機的飛速發(fā)展，更為排隊論的應用開拓了寬闊的前景。,4,排隊論,排隊論(queuing theory) 研究內容包括三個部分： (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)

3、設計，后者指現(xiàn)有排隊系統(tǒng)的最優(yōu)運營。,統(tǒng)計推斷，即判斷一個給定的排隊系統(tǒng)符合哪種模型，以便根據排隊理論進行研究。,解排隊問題的目的，是研究排隊系統(tǒng)運行的效率，估計服務質量，確定系統(tǒng)參數(shù)的最優(yōu)值，以決定系統(tǒng)結構是否合理，研究設計改進措施等。,5,排隊論,,第1節(jié) 基本概念第2節(jié) 到達間隔的分布和服務時間的分布第3節(jié) 單服務臺負指數(shù)分布排隊系統(tǒng)的分析第4節(jié) 多服務臺負指數(shù)分布排隊系統(tǒng)的分析第5節(jié) 一般服務時間M/G/1模型第6節(jié)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

26、他開始接受服務止這段時間，期望值記作Wq， 是隨機變量，也是顧客最關心的指標，因為顧客通常希望等待時間越短越好。 ［逗留時間］＝［等待時間］＋［服務時間］ 對這兩個指標的研究當然是希望能確定它們的分布，或至少能知道顧客的平均等待時間和平均逗留時間。,,35,1.4 排隊問題的求解,用于描述排隊系統(tǒng)運行狀況的基本數(shù)量指標 (3) 忙期：指從顧客到達空閑服務機構起，到服務機構再次為空閑止的時間長

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

55、67,3.1 標準的M/M/1模型(M/M/1/∞/∞)3.2 系統(tǒng)容量有限的情況(M/M/1/N/∞)3.3 顧客源有限的情形(M/M/1/∞/m),第3節(jié) 單服務臺負指數(shù)分布排隊系統(tǒng)的分析,本節(jié)討論輸入過程服從普阿松分布過程、服務時間服從負指數(shù)分布單服務臺的排隊系統(tǒng)。,68,標準的M/M/1模型(1) 輸入過程——顧客源是無限的，顧客單個到來，相互獨立，一定時間內的到達數(shù)服從泊松分布，到達過程是平穩(wěn)的。(2) 排隊規(guī)則

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

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

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

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

60、)情況(D),,,,,,,3.1 標準的M/M/1模型(M/M/1/∞/∞),74,研究穩(wěn)態(tài)的情況。這時 與時間t無關，可寫成 ，它的導數(shù)為0。由(12-15)式和(12-16)式可得這是關于 的差分方程，它表明了各狀態(tài)間的轉移關系：狀態(tài)0轉移到狀態(tài)1的轉移率為 ，狀態(tài)1轉移到狀態(tài)0的轉移率為 。,,,,,,3.1 標準的M/M/1模型(M/M/1/∞/∞),這種系統(tǒng)狀態(tài)(

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

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

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

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

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

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

67、 標準的M/M/1模型(M/M/1/∞/∞),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/

68、2)=2/3（小時）,3.1 標準的M/M/1模型(M/M/1/∞/∞),83,,記列車平均延誤（由于站內2股道均被占用而不能進站）時間為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=24?W0a=24*2*0.296*a=14.2a元,3.1 標準的M/