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

Little公式概要

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

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

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

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

1.輸入過程

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

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

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

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

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

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

k=0，1，2，…

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

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

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

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

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

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

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

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

①單服務臺：

√先到先服務，例如數(shù)據(jù)結構中的隊列；

√后到先服務，例如數(shù)據(jù)結構中的堆棧；

√隨機服務，例如搖號抽獎；

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

②多服務臺：常見的是在每個服務臺前排成一隊或排成公共一隊。當服務臺有空時，按順序進行服務。

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

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

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

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

3.服務機構

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

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

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

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

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

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

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

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

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

通常可以由如下七個特征來決定：

(1)顧客的輸入過程。

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

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

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

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

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

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

例2.1

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

例2.2

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

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

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

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

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

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

2.5

Little公式概要

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

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

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

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