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

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

Little公式概要

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

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

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

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

1.輸入過(guò)程

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

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

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

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

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

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

k=0，1，2，…

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

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

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

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

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

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

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

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

①單服務(wù)臺(tái)：

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

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

√隨機(jī)服務(wù)，例如搖號(hào)抽獎(jiǎng)；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3排隊(duì)系統(tǒng)的分類與符號(hào)

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

通?？梢杂扇缦缕邆€(gè)特征來(lái)決定：

(1)顧客的輸入過(guò)程。

(2)對(duì)顧客的服務(wù)過(guò)程。

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

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

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

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

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

例2.1

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

例2.2

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

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

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

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

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

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

2.5

Little公式概要

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

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

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

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