第2章排隊現(xiàn)象建模

第2章排隊現(xiàn)象建模2.1排隊現(xiàn)象分析2.2排隊系統(tǒng)基本構(gòu)成2.3排隊系統(tǒng)的分類與符號2.4排隊系統(tǒng)的特性指標(biāo)2.5

Little公式概要

2.1排隊現(xiàn)象分析

排隊現(xiàn)象并不僅限于上述電話系統(tǒng)，許多系統(tǒng)的設(shè)計中都存在類似的問題。表2.1列舉了一些排隊現(xiàn)象。

2.2排隊系統(tǒng)基本構(gòu)成

各類服務(wù)系統(tǒng)，盡管形式和內(nèi)容不同，其排隊系統(tǒng)都是由顧客到達(dá)、在隊列排隊和服務(wù)員服務(wù)三部分組成(或又稱為：輸入過程(arrivalprocess)、排隊規(guī)則(queuediscipline)和服務(wù)規(guī)則(servicediscipline))。典型排隊系統(tǒng)如圖2.1所示，這里使用的“顧客源”和“服務(wù)窗”要作廣義理解。下面將分別給予介紹。圖2.1典型排隊系統(tǒng)模型

1.輸入過程

輸入過程通?？梢杂萌缦碌娜N隨機(jī)過程來描述，這三者的含義與各自的關(guān)系分別如表2.2和圖2.2所示。圖2.2輸入過程的三種隨機(jī)過程示意圖為了便于研究，人們根據(jù)到達(dá)過程的不同概率特性將其分為如下幾類，并給予不同的符號以示區(qū)別。

·定長輸入(D)：這種輸入是指顧客規(guī)則的等間隔到達(dá)，即每隔時間c到達(dá)一個顧客，即tn≡c。顯然tn的分布函數(shù)為

·Poisson流輸入(M)：系統(tǒng)的輸入過程{M(t)，t≥0}為Poisson流是指其滿足如下四個條件：

①M(fèi)(t)取值為非負(fù)整數(shù)，即為計數(shù)過程；

②P(M(0)=0)=1，即時間間隔為0時到達(dá)系統(tǒng)的人數(shù)為0；

③對于任意的0≤a<t+a，每一個增量M(a+t)－M(a)非負(fù)，且服從參數(shù)為lt(l≥0)的泊松分布，即

k=0，1，2，…

④過程{M(t)，t≥0}具有平穩(wěn)獨立增量性。

·k階Erlang輸入(Ek)：顧客的到達(dá)過程{tn，n=1,2,…}是獨立同分布的隨機(jī)變量序列，且tn的概率密度函數(shù)為

其中，k稱為相位。一般獨立輸入(G)：也稱通用獨立輸入，顧客的到達(dá)過程{tn，n=1，2，…}是獨立同分布的非負(fù)隨機(jī)變量序列，其分布函數(shù)可以為任意函數(shù)，但是其均值有限，且方差存在。

成批到達(dá)：顧客一批接一批的相繼到達(dá)系統(tǒng)，每批顧客的個數(shù)可以是常數(shù)(通常是正整數(shù))，也可以是一個離散型(通常取非負(fù)整數(shù))隨機(jī)變量，而各批相繼到達(dá)的時間間隔可以為上述各種分布之一。

2.排隊與服務(wù)規(guī)則

顧客進(jìn)入排隊系統(tǒng)后的排隊規(guī)則通常有損失制、等待制和混合制三種。

·損失制(無排隊隊列)：顧客到達(dá)時，所有服務(wù)臺均被占用，則該顧客就離去，永不再來。例如電話系統(tǒng)就屬于損失制，當(dāng)一次呼叫不通，則此次呼叫作廢，這次呼叫永遠(yuǎn)消失(注意：如果再次呼叫被認(rèn)為與上次呼叫無關(guān))。

·排隊制(等待制)：當(dāng)顧客到達(dá)時，所有服務(wù)臺均被占用，他們就排隊等待服務(wù)，其排隊方式有以下幾種。

①單服務(wù)臺：

√先到先服務(wù)，例如數(shù)據(jù)結(jié)構(gòu)中的隊列；

√后到先服務(wù)，例如數(shù)據(jù)結(jié)構(gòu)中的堆棧；

√隨機(jī)服務(wù)，例如搖號抽獎；

√優(yōu)先權(quán)服務(wù)，例如銀行VIP會員。

②多服務(wù)臺：常見的是在每個服務(wù)臺前排成一隊或排成公共一隊。當(dāng)服務(wù)臺有空時，按順序進(jìn)行服務(wù)。

·混合制：可分為如下三種。

①排隊長度(隊長)有限：當(dāng)顧客到達(dá)時，若隊長已等于規(guī)定長度時，顧客離去；若小于規(guī)定長度時，則排隊。系統(tǒng)不存在超過隊長的狀態(tài)。如醫(yī)院專家號掛號已滿，就不再排隊了。

②等待時間有限：顧客在隊中排隊超過某個時間間隔時，則離去。例如醫(yī)院血庫的血漿、生物制劑等。

③逗留時間(等待時間與服務(wù)時間之和)有限，顧客在系統(tǒng)中的逗留時間不得超過確定的時間，例如藥品的有效期。

3.服務(wù)機(jī)構(gòu)

服務(wù)機(jī)構(gòu)通常包括：服務(wù)員的個數(shù)、服務(wù)機(jī)構(gòu)的結(jié)構(gòu)形式(如串聯(lián)、并聯(lián)、混聯(lián)或網(wǎng)絡(luò)等結(jié)構(gòu)形式)、服務(wù)過程等。

圖2.3給出了單隊列單服務(wù)員系統(tǒng)。圖2.3單隊列單服務(wù)員系統(tǒng)這個服務(wù)系統(tǒng)的服務(wù)方式是這樣的。該系統(tǒng)的核心是一個服務(wù)員，它負(fù)責(zé)為顧客提供某種服務(wù)。從某顧客群體中到來的顧客來到這個系統(tǒng)要求服務(wù)。如果服務(wù)員空閑，顧客就立即得到服務(wù)，否則到達(dá)的顧客就進(jìn)入等待隊列。當(dāng)服務(wù)員服務(wù)完一個顧客時，該顧客就離開服務(wù)系統(tǒng)。如果等待隊列中有顧客，那么一個顧客就被交給服務(wù)員。圖2.4多服務(wù)員隊列與多個單服務(wù)員隊列若以vn表示到達(dá)系統(tǒng)的第n個顧客在系統(tǒng)中接受服務(wù)的時間，則{vn，n=1，2，…}稱為服務(wù)過程，可分為如下幾類：

·定長服務(wù)分布(D)：每個顧客接受服務(wù)的時間為正常數(shù)c，其分布函數(shù)為

·負(fù)指數(shù)服務(wù)分布(M)：此時每個顧客的服務(wù)時間v1，

v2，…，vn，…相互獨立，并具有相同的負(fù)指數(shù)分布，其分布函數(shù)為

·k階Erlang服務(wù)分布(Ek)：此時每個顧客的服務(wù)時間v1，v2，…，vn，…相互獨立，并有相同的k階Erlang分布，其分布函數(shù)為

·一般獨立服務(wù)分布(G)：也稱通用獨立服務(wù)分布，所有顧客接受服務(wù)的時間是獨立同分布的非負(fù)隨機(jī)變量序列，其分布函數(shù)可以為任意函數(shù)，但是其均值有限，且方差存在。

2.3排隊系統(tǒng)的分類與符號

考慮到排隊系統(tǒng)

通?？梢杂扇缦缕邆€特征來決定：

(1)顧客的輸入過程。

(2)對顧客的服務(wù)過程。

(3)服務(wù)員的個數(shù)。

(4)系統(tǒng)容量(系統(tǒng)內(nèi)所能允許進(jìn)入的最大顧客數(shù))。

(5)顧客源的個數(shù)。

(6)服務(wù)規(guī)則。

(7)服務(wù)機(jī)構(gòu)的結(jié)構(gòu)形式。于是人們就根據(jù)這些特征來劃分排隊模型。目前通用的是1953年英國數(shù)學(xué)家D.G.肯達(dá)爾提出的“肯達(dá)爾模型”，我們稱之為經(jīng)典排隊模型。該模型由A/B/C/D/E/F組成，各個符號的含義如圖2.5所示。圖2.5排隊模型-肯達(dá)爾記號

例2.1

M/M/c/k排隊系統(tǒng)，其含義為：該系統(tǒng)的輸入過程{M(t)，t≥0}為Poisson流，因而其顧客源的個數(shù)為∞；對每個顧客的服務(wù)時間{vn，n=1，2，…}為獨立同負(fù)指數(shù)分布；c個服務(wù)員；系統(tǒng)容量為k(k≥1)；顧客進(jìn)入系統(tǒng)后排成一列，按照先來先服務(wù)的原則，由c個服務(wù)員并行服務(wù)。

例2.2

G/E3/2/∞排隊系統(tǒng)，其含義為：該系統(tǒng)的輸入過程{tn，n=1，2，…}為一般獨立輸入；對每個顧客的服務(wù)時間{vn，n=1，2，…}為獨立同分布，其分布函數(shù)為3級Erlang分布；2個服務(wù)員；系統(tǒng)容量為∞；顧客進(jìn)入系統(tǒng)后排成一列，按照先來先服務(wù)的原則，由2個服務(wù)員并行服務(wù)；顧客源的個數(shù)為無限。

2.4排隊系統(tǒng)的特性指標(biāo)

具體說來在排隊系統(tǒng)的瞬態(tài)分析中，人們關(guān)心的系統(tǒng)特性指標(biāo)及其符號如表2.3所示。由表2.3可得出

2.穩(wěn)態(tài)特性指標(biāo)

穩(wěn)態(tài)分析較之瞬態(tài)分析要容易得多(在第3章大家將會看到)，故它是本章介紹的重點。具體說來在排隊系統(tǒng)的穩(wěn)態(tài)分析中，人們關(guān)心的系統(tǒng)特性指標(biāo)及其符號如表2.4所示。由表2.4可得出當(dāng)平穩(wěn)狀態(tài)存在時，系統(tǒng)的瞬態(tài)特性指標(biāo)與穩(wěn)態(tài)特性指標(biāo)存在如下關(guān)系

圖2.6以單服務(wù)員為例，對穩(wěn)態(tài)特性指標(biāo)進(jìn)行了圖示。圖2.6單服務(wù)員隊列穩(wěn)態(tài)指標(biāo)

2.5

Little公式概要

對一個排隊系統(tǒng)，一般假定滿足以下三個條件：

(1)排隊系統(tǒng)能夠進(jìn)入統(tǒng)計平衡狀態(tài)；

(2)服務(wù)員的忙期與閑期交替出現(xiàn)，即系統(tǒng)不是總處于忙的狀態(tài)；

(3)系統(tǒng)中任一顧客不會永遠(yuǎn)等待，系統(tǒng)也不會永無顧客到達(dá)。在上述假設(shè)成立時,Little公式(李特爾,JohnD.C.Little)成立，如下所示：當(dāng)一個顧客到達(dá)時，它會發(fā)現(xiàn)在它前面排隊等待以及系統(tǒng)中正在接受服務(wù)的顧客有L個。當(dāng)它被服務(wù)完畢并離開系統(tǒng)時，在系統(tǒng)中排隊和接受服務(wù)的顧客也有L個。這與系統(tǒng)中平均顧客數(shù)L是一致的。另外，已知這個顧客在系統(tǒng)中平均花費(fèi)的時間是T，且顧客到達(dá)速率是