1第九章排隊(duì)論2§9-1基本概念§9-2泊松排隊(duì)系統(tǒng)§9-3非泊松排隊(duì)系統(tǒng)3

在人們的日常生活和經(jīng)濟(jì)活動(dòng)中，排隊(duì)現(xiàn)象隨處可見，如乘客等候乘車，飛機(jī)等候起飛和降落，機(jī)器等候工人修理，用戶在電話機(jī)前等候電話，進(jìn)入雷達(dá)接受機(jī)的信號等待處理等等，都是排隊(duì)現(xiàn)象。

也就是說，只要一個(gè)服務(wù)系統(tǒng)在工作過程中，由于某項(xiàng)服務(wù)的需求超過了當(dāng)前提供服務(wù)的能力，就會出現(xiàn)排隊(duì)現(xiàn)象。這里，將這種具有排隊(duì)等候現(xiàn)象的服務(wù)系統(tǒng)稱為排隊(duì)系統(tǒng)。以下簡稱系統(tǒng)。

任何一個(gè)排隊(duì)系統(tǒng)總是由“顧客”和“服務(wù)員”這兩個(gè)相輔相成的要素所構(gòu)成。凡是要求接受服務(wù)的人或物統(tǒng)稱為顧客，如上述的乘客、飛機(jī)、機(jī)器、電話用戶和信號；凡是給與顧客服務(wù)的人和物統(tǒng)稱為服務(wù)員（或服務(wù)臺），如公共汽車、機(jī)場的跑道、工人、電話交換臺和信號處理器等。4

從經(jīng)濟(jì)學(xué)角度，排隊(duì)現(xiàn)象必然會造成某種或某些資源的浪費(fèi)。簡單得講，當(dāng)顧客到達(dá)的數(shù)量過多服務(wù)設(shè)施過少時(shí)，至少會造成時(shí)間上的浪費(fèi)；而當(dāng)顧客到達(dá)的數(shù)量少或無顧客到達(dá)時(shí)，會使某些獲全體服務(wù)員無事可做（處于空間狀態(tài)），至少要造成服務(wù)設(shè)施的浪費(fèi)。

因此，在服務(wù)機(jī)構(gòu)的設(shè)計(jì)或運(yùn)營中，決策者或管理員面臨的一個(gè)重要課題是：如何選擇適當(dāng)?shù)姆?wù)設(shè)施和運(yùn)營策略，使得既可避免過多嚴(yán)重的排隊(duì)現(xiàn)象，又不會因過多的設(shè)施增加不必要的成本或負(fù)擔(dān)過高的運(yùn)營費(fèi)用。研究這類問題的理論稱為排隊(duì)論（QueuingTheory），也稱為隨機(jī)服務(wù)系統(tǒng)理論。

5

顯然，解決上述問題的關(guān)鍵是掌握顧客到達(dá)時(shí)刻和顧客服務(wù)時(shí)間等變化過程的規(guī)律，因此，排隊(duì)論的主要研究任務(wù)是：通過對排隊(duì)系統(tǒng)的變化過程概率規(guī)律性的分析研究，去尋找達(dá)到服務(wù)供求平衡的手段。

排隊(duì)論是解決排隊(duì)問題過程中形成而在不斷發(fā)展的一個(gè)數(shù)學(xué)分支。它通過對排隊(duì)現(xiàn)象中概率特性的研究，以解決經(jīng)濟(jì)管理和其他許多領(lǐng)域中的服務(wù)系統(tǒng)的最優(yōu)設(shè)計(jì)和最優(yōu)控制（運(yùn)營）問題。

6

排隊(duì)論起源于1969年丹麥電話工程師A.K.ERlang工作。他在對電話擁擠問題進(jìn)行了實(shí)驗(yàn)后發(fā)表了開創(chuàng)性的論文“概率論和電話通話”，標(biāo)志了排隊(duì)輪研究的開始。但早期的研究只局限在電話交換領(lǐng)域，直到第二次世界大戰(zhàn)末期人們才開始對其他一般排隊(duì)問題的研究，在理論研究的同時(shí)，不斷的擴(kuò)大排隊(duì)輪的應(yīng)用領(lǐng)域。時(shí)至今日，排隊(duì)輪在經(jīng)濟(jì)管理和其他領(lǐng)域中得到廣泛的應(yīng)用，如交通運(yùn)輸系統(tǒng)，礦山采掘系統(tǒng)，醫(yī)療衛(wèi)生系統(tǒng)，生產(chǎn)管理系統(tǒng)，計(jì)算機(jī)系統(tǒng)，軍事作戰(zhàn)系統(tǒng)等。排隊(duì)輪已經(jīng)成為系統(tǒng)優(yōu)化設(shè)計(jì)和系統(tǒng)分析中的重要數(shù)學(xué)工具。

本章我們介紹排隊(duì)輪的一些基本概念，分析幾個(gè)常見的排隊(duì)模型，并應(yīng)用這些理論介紹服務(wù)機(jī)構(gòu)優(yōu)化設(shè)計(jì)的一些基本方法。7§9-1基本概念§9-2泊松排隊(duì)系統(tǒng)

§9-3非泊松排隊(duì)系統(tǒng)8§9-1基本概念一、Poisson過程二、（負(fù)）指數(shù)過程三、Erlang過程四、排隊(duì)系統(tǒng)與排隊(duì)模型五、排隊(duì)模型分類六、排隊(duì)系統(tǒng)性能指標(biāo)9一、Poisson過程

在系統(tǒng)中，我們首先要弄清楚的是系統(tǒng)運(yùn)行過程中有關(guān)要素變化過程的概率特性。如：顧客逐個(gè)到達(dá)系統(tǒng)的變化過程、對每個(gè)不同顧客服務(wù)時(shí)間的變化過程、不同時(shí)間進(jìn)入系統(tǒng)的顧客總數(shù)變化過程，等等。這些具有隨機(jī)特性的事物變化過程，在概率論中用隨機(jī)過程來定量描述。定義1：設(shè)T為時(shí)間參數(shù)，若對每個(gè)t

T，有一個(gè)隨機(jī)變量函數(shù)X(t)與之對應(yīng)，則當(dāng)t取遍參數(shù)集T中的每一值時(shí)，由這簇依賴于T的隨機(jī)變數(shù)構(gòu)成的集合稱為隨機(jī)過程，記作：{X(t)|t

T}。在隨機(jī)過程中，參數(shù)集T可以為連續(xù)集或離散集，也可以為有限集或無限集。10

設(shè)M(t)為在[0,t)時(shí)間間隔內(nèi)到達(dá)系統(tǒng)的顧客數(shù)，Pn(t1,t2)表示在時(shí)間區(qū)間[t1,t2)內(nèi)有n個(gè)顧客到達(dá)系統(tǒng)的概率，即：當(dāng)Pn(t1,t2)滿足下列三個(gè)條件時(shí)，隨機(jī)過程{M(t)|t

0}被稱為Poisson過程或Poisson流。（1）無后效性。在互不重疊的時(shí)間區(qū)間內(nèi)，到達(dá)系統(tǒng)的顧客數(shù)是相互獨(dú)立的；（2）平穩(wěn)性。對充分小的t，在時(shí)間區(qū)間內(nèi)有一個(gè)顧客到達(dá)系統(tǒng)的概率與t無關(guān)，且?guī)缀跖c區(qū)間長度t成正比；（3）普通性。對充分小的t，在時(shí)間區(qū)間內(nèi)，到達(dá)系統(tǒng)的顧客數(shù)大于1的概率幾乎為0。11

由于平穩(wěn)性，總可以將起始時(shí)間由0算起，且將記作。在實(shí)際生活中，具有上述概率特性的客觀事物的變化過程非常普遍，而在排隊(duì)論研究中，顧客的含義具有廣泛性，因此，Poisson過程就具有描述許多事物變化過程的一般意義。

定理1：若{M(t)|t≥0}為參數(shù)λ(>0)的Poisson過程，則：證：略該定理表明：隨機(jī)變數(shù)M(t)服從參數(shù)為λt的Poisson分布，這也是{M(t)|t≥0}稱為Poisson過程的由來。

12相繼到達(dá)的平均間隔時(shí)間，從而λ為單位時(shí)間內(nèi)到達(dá)系統(tǒng)的平均顧客數(shù)，稱之為顧客的平均到達(dá)率。

由概率論可知：M(t)的數(shù)學(xué)期望與方差都為λt，因此，λ表示單位時(shí)間（t=1）內(nèi)已經(jīng)到達(dá)系統(tǒng)的平均顧客數(shù)，稱為平均到達(dá)率。如果以顧客相繼到達(dá)的間隔時(shí)間作為隨機(jī)變量來描述Poisson流輸入過程，則該隨機(jī)過程相互獨(dú)立且服從具有相同參數(shù)的負(fù)指數(shù)分布：其分布函數(shù)為：由于的數(shù)學(xué)期望為，因此，的實(shí)際意義為顧客13二、（負(fù)）指數(shù)過程

如果隨機(jī)變數(shù)X(t)的概率密度為：則稱X服從參數(shù)為k的（負(fù)）指數(shù)分布，其分布函數(shù)為：

X的數(shù)學(xué)期望與方差分別為：定義2：設(shè)相互獨(dú)立的隨機(jī)變數(shù)服從同一（負(fù)）指數(shù)分布，則隨機(jī)過程稱為（負(fù)）指數(shù)過程。14定理2：到達(dá)系統(tǒng)顧客數(shù)的隨機(jī)過程為Poisson過程等價(jià)于前后兩個(gè)顧客相繼到達(dá)的時(shí)間間隔的隨機(jī)過程為（負(fù)）指數(shù)過程。證：略

Poisson過程中，λ表示單位時(shí)間內(nèi)已到達(dá)的平均顧客數(shù)，負(fù)指數(shù)分布過程中，1/λ表示顧客相繼到達(dá)的平均間隔時(shí)間，兩者意義正好相符。

定義3：若對任何t與s>0，隨機(jī)變數(shù)滿足：定理3：隨機(jī)變數(shù)具有無后效性的充分必要條件是服從（負(fù)）指數(shù)分布。證：略。

，則稱X具有無后效性，也稱Markov性。15三、Erlang過程Erlang過程為研究系統(tǒng)的排隊(duì)過程提供了更廣泛的模型。定義4：若隨機(jī)變數(shù)X的概率密度為：則稱X服從n階Erlang分布，其數(shù)學(xué)期望與方差分別為：

定義5：設(shè)相互獨(dú)立的隨機(jī)變數(shù)服從n階Erlang分布，則隨機(jī)過程稱為Erlang分布。16定理4：設(shè)是n個(gè)相互獨(dú)立的隨機(jī)變數(shù)，服從參數(shù)為的同一（負(fù)）指數(shù)分布，則服從n階Erlang分布。證：略定理5：當(dāng)顧客按Poisson過程到達(dá)時(shí)，其到達(dá)的時(shí)刻形成Erlang過程。證：略。

17四、排隊(duì)系統(tǒng)與排隊(duì)模型任何一個(gè)排隊(duì)系統(tǒng)由三個(gè)基本部分構(gòu)成：輸入過程、排隊(duì)規(guī)則與隊(duì)列結(jié)構(gòu)、服務(wù)規(guī)則與服務(wù)機(jī)構(gòu)。如圖9-1所示。

顧客到達(dá)隊(duì)列結(jié)構(gòu)服務(wù)機(jī)構(gòu)排隊(duì)規(guī)則服務(wù)規(guī)則顧客離開顧客源圖9-1輸入過程（顧客按照怎樣的規(guī)律到達(dá)）排隊(duì)規(guī)則與隊(duì)列結(jié)構(gòu)(顧客按照一定規(guī)則排隊(duì)和方式等待服務(wù))服務(wù)規(guī)則與服務(wù)機(jī)構(gòu)(服務(wù)機(jī)構(gòu)的設(shè)置,服務(wù)臺的數(shù)量,服務(wù)的方式,服務(wù)時(shí)間分布等)18

顧客由顧客源出發(fā)，到達(dá)服務(wù)機(jī)構(gòu)前排隊(duì)等候接受服務(wù)，服務(wù)完畢后離開排隊(duì)系統(tǒng)。因此，排隊(duì)系統(tǒng)的概率規(guī)律性取決于以下三個(gè)因素：（1）顧客到達(dá)規(guī)律;

（2）顧客排隊(duì)與接受服務(wù)的規(guī)則;

（3）服務(wù)機(jī)構(gòu)的結(jié)構(gòu)形式、服務(wù)方式與服務(wù)速率。這三個(gè)要素稱為排隊(duì)系統(tǒng)的三個(gè)基本組成部分，下面分別說明各部分的特征。1.輸入過程輸入過程是對顧客到達(dá)規(guī)律的一種數(shù)學(xué)描述，也是決定排隊(duì)系統(tǒng)性質(zhì)的重要因素之一。19

在實(shí)際的排隊(duì)問題中，顧客到來的方式可以是單個(gè)的，也可以是成批的；顧客相繼到達(dá)的時(shí)間可以是確定的，也可以是隨機(jī)的；顧客的到達(dá)可以是相互獨(dú)立的，也可以是彼此關(guān)聯(lián)的，等等。為了對不同的系統(tǒng)進(jìn)行研究，我們根據(jù)各種輸入過程的不同概率特性，將其分為四類，并用不同的記號加以區(qū)分：（1）定長輸入（D）定長輸入是指顧客有規(guī)律地按照固定的時(shí)間間隔相繼到達(dá)，這種情況簡單而容易處理，屬于確定型輸入。例如：在自動(dòng)裝配線上需裝配的部件按確定的間隔時(shí)間依次到達(dá)裝配點(diǎn)，定期運(yùn)行的班車每天準(zhǔn)時(shí)到達(dá)車站等均屬于定長輸入。

20（2）Poisson流輸入（M）

poison流輸入是指輸入過程{M,t≥0}是一個(gè)以

為參數(shù)的Poisson過程，或稱為Poisson流，它是在實(shí)際問題中應(yīng)用最廣。（3）k階Erlang輸入（Ek）如果顧客相繼到達(dá)的時(shí)間間隔相互獨(dú)立，且均服從k階Erlang分布，則該輸入過程為k階Erlang輸入。（4）一般獨(dú)立輸入（GI）一般獨(dú)立輸入是指顧客相繼到達(dá)的時(shí)間間隔相互獨(dú)立且同分布。在這里，對顧客相繼到達(dá)的時(shí)間間隔所服從分布的具體形式不再要求。顯然（2）、（3）都是（4）的特例。212.排隊(duì)規(guī)則與隊(duì)列結(jié)構(gòu)（1）排隊(duì)規(guī)則排隊(duì)規(guī)則指顧客必須遵守某種制度進(jìn)行排隊(duì)來接受服務(wù)。一般有下面的三種形式：①損失制：當(dāng)顧客到達(dá)時(shí)，若所有的服務(wù)均被占用，顧客不再等待而是立刻離開。這種排隊(duì)系統(tǒng)會失掉一些顧客，故稱為損失制。例如：通常的電話呼喚，在占線的呼喚停止而不進(jìn)入排隊(duì)系統(tǒng)（下一次電話呼喚應(yīng)視為不同的顧客）。②等待制：當(dāng)顧客到達(dá)時(shí)，若所有的服務(wù)臺均被占用，顧客排隊(duì)等待，直到接受服務(wù)。例如：通常的觀眾排隊(duì)買票，乘客排隊(duì)等候上車，飛機(jī)等待起飛等。22③混合制：當(dāng)顧客到達(dá)時(shí)，若排隊(duì)的顧客數(shù)小于某個(gè)臨界值N,顧客就排隊(duì)等待接受服務(wù)，否則，顧客不等待離開系統(tǒng)。例如：藥品過期就等待處理就屬于這種情況。也就是說顧客根據(jù)某種條件決定等待服務(wù)還是離開系統(tǒng)。這種情況在排隊(duì)問題中經(jīng)常出現(xiàn)的，條件還可以不是排隊(duì)的人數(shù)，而是其他因素如等待時(shí)間等。（2）隊(duì)列結(jié)構(gòu)排隊(duì)的隊(duì)列結(jié)構(gòu)有單列和多列之分，多列有可更換（顧客從一個(gè)隊(duì)列中轉(zhuǎn)到另一個(gè)隊(duì)列中）和不可更換之分，也有單列、多列混合編排等其他形式。23①先到先服務(wù)（FCFS)：指按照顧客到達(dá)的先后順序進(jìn)行服務(wù)；②后到先服務(wù)（LCFS)：指按照顧客到達(dá)先后，反序進(jìn)行服務(wù)；③隨機(jī)服務(wù)（SIRO）：指服務(wù)員隨機(jī)挑選一個(gè)顧客進(jìn)行服務(wù)，而不管到達(dá)的先后次序；④優(yōu)先服務(wù)（PR）：進(jìn)入系統(tǒng)的顧客有不同的優(yōu)先等級，具有較高優(yōu)先級的顧客可先于優(yōu)先級地的顧客接受服務(wù)，而不管他們到達(dá)系統(tǒng)的先后次序。3.服務(wù)規(guī)則與服務(wù)機(jī)構(gòu)（1）服務(wù)規(guī)則服務(wù)規(guī)則是指顧客進(jìn)入排隊(duì)系統(tǒng)后，按照哪種方式接受服務(wù)。通常有下列四種形式。24（2）服務(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ù)方式（如單個(gè)服務(wù)和成批服務(wù)）和服務(wù)時(shí)間（如確定型和隨機(jī)型）。大多數(shù)情況下，服務(wù)時(shí)間是隨機(jī)的。（3）服務(wù)時(shí)間分布服務(wù)時(shí)間的隨機(jī)分布和輸入過程的隨機(jī)分布類似，一般按下列四種形式：

①

定長分布服務(wù)（D）：對每一顧客的服務(wù)時(shí)間相同，屬于確定型服務(wù)；25②（負(fù)）指數(shù)分布服務(wù)（M）：對每一個(gè)顧客的服務(wù)時(shí)間相互獨(dú)立，且服從相同的（負(fù)）指數(shù)分布；③k階Erlang分布服務(wù)（Ek）：對各顧客的服務(wù)時(shí)間獨(dú)立，且服從相同的k階Erlang分布；④一般獨(dú)立分布服務(wù)（GI）對各顧客的服務(wù)時(shí)間相互獨(dú)立。且服從相同的分布，但對所服從的分布沒有具體要求。顯然，②、③都是④的特例。26五、排隊(duì)模型分類

根據(jù)上面的討論，由于各種排隊(duì)系統(tǒng)所處的環(huán)境及所研究的問題互不相同，排隊(duì)系統(tǒng)的結(jié)構(gòu)有很大的差別，人們無法將其抽象為一個(gè)統(tǒng)一結(jié)構(gòu)的數(shù)學(xué)模型來研究，Kendall根據(jù)系統(tǒng)的三個(gè)主要特征提出了一種分類方法，后來，人們又陸續(xù)增加了三個(gè)特征。這六個(gè)特征為：（1）輸入過程（顧客相繼到達(dá)間隔時(shí)間的分布）；（2）對顧客服務(wù)時(shí)間的分布；（3）并聯(lián)服務(wù)員的個(gè)數(shù)；（4）系統(tǒng)容量（系統(tǒng)中所允許的最大顧客數(shù)）；（5）顧客源中顧客總數(shù)；（6）服務(wù)規(guī)則。

27

根據(jù)這六個(gè)特征，可以用短豎線分隔依次排列的專門符號來表示這種按特征分類的排隊(duì)模型，如下所示。

X|Y|Z|A|B|C其中每個(gè)符號表示系統(tǒng)的一個(gè)特征，他們依次為：

X：顧客到達(dá)過程，可為D,M,Ek,GI等Y：對顧客的服務(wù)時(shí)間，可為D,M,Ek,GI等Z：服務(wù)員個(gè)數(shù)，可為1，2，…C等A：系統(tǒng)容量，即系統(tǒng)內(nèi)所能允許進(jìn)入的最大顧客數(shù)，可為N，

B：顧客源的數(shù)目，可為m，

C：服務(wù)規(guī)則，可為FCFS，LCFS，SIRO，PR等

上面的六個(gè)特征可描述前面所討論的排隊(duì)系統(tǒng)的結(jié)構(gòu)，其中排隊(duì)規(guī)則可由Z，A和B來求得。

例如：M|M|1|

|m|FCFS—表示Poisson輸入、服務(wù)時(shí)間為（負(fù)）指數(shù)分布、單一服務(wù)員、系統(tǒng)容量無限（即等待制）、有限顧客源中顧客數(shù)量為m、先到先服務(wù)的排隊(duì)模型。28六、排隊(duì)系統(tǒng)性能指標(biāo)

一般而言，系統(tǒng)在經(jīng)歷了一個(gè)不穩(wěn)定的短期初始運(yùn)行階段后，便會達(dá)到穩(wěn)定的長期持續(xù)運(yùn)行階段。將與時(shí)間t有關(guān)的系統(tǒng)狀態(tài)特性稱為瞬間特性（主要指初始階段），而將與時(shí)間無關(guān)的系統(tǒng)狀態(tài)特性稱為穩(wěn)定特性（反映持續(xù)運(yùn)行階段）。我們只討論一些典型的排隊(duì)系統(tǒng)的穩(wěn)態(tài)分析。首先給出如下的概念：(1)隊(duì)長：穩(wěn)態(tài)下系統(tǒng)中的顧客數(shù)；(2)排隊(duì)長：穩(wěn)態(tài)下系統(tǒng)中排隊(duì)等待接受服務(wù)的顧客數(shù)；(3)逗留時(shí)間：穩(wěn)態(tài)下顧客在系統(tǒng)內(nèi)停留的時(shí)間；(4)等待時(shí)間：穩(wěn)態(tài)下顧客在系統(tǒng)內(nèi)為接受服務(wù)排隊(duì)等候的時(shí)間。

29衡量系統(tǒng)瞬態(tài)特性的主要性能指標(biāo)如表9-1所示。表9-1L(t)t時(shí)刻系統(tǒng)中顧客總數(shù)的平均系統(tǒng)隊(duì)長Lq(t)t時(shí)刻系統(tǒng)中顧客排隊(duì)的平均等待隊(duì)長W(t)t時(shí)刻到達(dá)系統(tǒng)的顧客在系統(tǒng)中的平均逗留時(shí)間Wq(t)t時(shí)刻到達(dá)系統(tǒng)的顧客在隊(duì)列中的平均等待時(shí)間Pn(t)t時(shí)刻系統(tǒng)中有n個(gè)顧客的概率，稱為系統(tǒng)t時(shí)刻的狀態(tài)概率

當(dāng)t

時(shí)，上述各項(xiàng)性能指標(biāo)即為系統(tǒng)的穩(wěn)定性，記作：L、Lq、W、Wq、Pn。

逗留時(shí)間和等待時(shí)間均為連續(xù)型的隨機(jī)變量，上述變量間具有如下關(guān)系：正在被服務(wù)的顧客數(shù)=隊(duì)長-排隊(duì)長服務(wù)時(shí)間=逗留時(shí)間-等待時(shí)間30

上述各隨機(jī)變數(shù)的數(shù)學(xué)期望,即平均隊(duì)長L,平均排隊(duì)長Lq,平均逗留時(shí)間W和平均等待時(shí)間Wq,被稱為排隊(duì)系統(tǒng)的運(yùn)行指標(biāo),它們在平均的意義下刻劃了系統(tǒng)工程的一些性質(zhì)。一般來說，性能指標(biāo)值愈小，說明系統(tǒng)中顧客隊(duì)列愈短，等待時(shí)間愈少，系統(tǒng)性能愈好。由于這些指標(biāo)體現(xiàn)了排隊(duì)系統(tǒng)在穩(wěn)態(tài)運(yùn)行下的工作效率和服務(wù)質(zhì)量，是評價(jià)一個(gè)排隊(duì)系統(tǒng)，或者說是評價(jià)服務(wù)機(jī)構(gòu)的標(biāo)準(zhǔn)。因此，無論顧客還是服務(wù)系統(tǒng)管理人員，對這些數(shù)量指標(biāo)都是關(guān)注的。

31

經(jīng)研究發(fā)現(xiàn)，許多排隊(duì)系統(tǒng)在穩(wěn)定狀態(tài)下，其主要數(shù)量指標(biāo)滿足如下的Little公式：

L=

eWLq=

eWq

其中：

e表示單位時(shí)間內(nèi)已經(jīng)到達(dá)并實(shí)際進(jìn)入系統(tǒng)的平均顧客，稱為有效到達(dá)率。（為簡便起見，在具體計(jì)算中近似值的計(jì)算都采用等號表示）32§9-2Poisson排隊(duì)系統(tǒng)

一、M|M|1|

系統(tǒng)二、M|M|1|N系統(tǒng)三、M|M|c|

系統(tǒng)四、M|M|c|N系統(tǒng)33一、M|M|1|

系統(tǒng)習(xí)慣上，將此模型簡記M|M|1，此類系統(tǒng)具有下述特性：（1）輸入過程{M(t)|t

0}為Poisson過程，平均到達(dá)率為

；（2）對每個(gè)顧客的服務(wù)時(shí)間相對獨(dú)立，且具有同一（負(fù)）指數(shù)分布，平均服務(wù)率為

；（3）單服務(wù)員；（4）系統(tǒng)容量無限，因此，每個(gè)到達(dá)的顧客總能進(jìn)入系統(tǒng)接受服務(wù)或者排隊(duì)等待，即：

e＝

；（5）到達(dá)過程與服務(wù)過程相互獨(dú)立。

凡是輸入過程為Poission過程，服務(wù)時(shí)間分布為（負(fù)）指數(shù)分布的排隊(duì)系統(tǒng)，稱為Poission排隊(duì)系統(tǒng)。這也是最常見的排隊(duì)系統(tǒng)。34令：，由Poisson流的特性，可推導(dǎo)出系統(tǒng)狀態(tài)概率為：

是平均到達(dá)率與平均服務(wù)率之比，即：在單位時(shí)間內(nèi)顧客到達(dá)的平均數(shù)與被服務(wù)的平均數(shù)之比，稱為服務(wù)強(qiáng)度。當(dāng)

<

時(shí)，系統(tǒng)正常運(yùn)行，隊(duì)長有限；當(dāng)

>

時(shí)。系統(tǒng)超負(fù)荷運(yùn)行，隊(duì)長將趨于無限；當(dāng)

=

時(shí)，由于隨機(jī)性，也將出現(xiàn)隊(duì)列愈來愈長的情況。所以一般假設(shè)

<1。35由動(dòng)態(tài)概率Pn可以導(dǎo)出系統(tǒng)的主要穩(wěn)態(tài)性能指標(biāo)如下：

可以證明：

在M|M|1系統(tǒng)中，平均等待時(shí)間W服從參數(shù)為

-

的（負(fù)）指數(shù)分布。因此可以求出顧客在系統(tǒng)中逗留某一時(shí)間界限中的概率，如顧客在系統(tǒng)中逗留時(shí)間不超過t小時(shí)的概率為：（1）平均系統(tǒng)隊(duì)長：

（2）平均等待隊(duì)長：（3）平均逗留時(shí)間（由Little得出）：（4）平均等待時(shí)間（由Little得出）：36例1：市醫(yī)院某科有1位專家設(shè)特需門診，就診病人按Poisson過程到達(dá)，平均10人/小時(shí)，專家診病時(shí)間服從（負(fù)）指數(shù)分布，平均診斷15人/小時(shí)，求該排隊(duì)系統(tǒng)的主要性能指標(biāo)。解：首先可以看出這是一個(gè)M|M|1系統(tǒng)。已知病人平均到達(dá)率

=10人/小時(shí)，平均服務(wù)時(shí)間為

=15人/小時(shí)，平均到達(dá)率與平均服務(wù)率之比

=

/

=10/15=0.67

因此可得該排隊(duì)系統(tǒng)的各項(xiàng)性能指標(biāo)如下：37在醫(yī)院（包括等待和正在看病的）的平均人數(shù)為：

在醫(yī)院排隊(duì)候診的平均人數(shù)為：病人為看病耗費(fèi)的平均時(shí)間（平均逗留時(shí)間）為：病人等待看病的平均等待時(shí)間為：

而病人在醫(yī)院逗留的時(shí)間不超過0.2小時(shí)的概率為：

38二、M|M|1|N系統(tǒng)

和前面系統(tǒng)容量為

相比，該系統(tǒng)容量為N，因此，排隊(duì)等候的人數(shù)最多為N-1個(gè)，當(dāng)系統(tǒng)中已有N個(gè)顧客時(shí)，后來的顧客不再入內(nèi)而是離開。其他條件與M|M|1系統(tǒng)相同。

因此，該系統(tǒng)的狀態(tài)概率為：

這里的

沒有限制，不過當(dāng)

>1時(shí)，可以明顯看出：系統(tǒng)滿員的概率，也就是顧客損失率PN將是很大的。39由狀態(tài)概率Pn可推導(dǎo)出系統(tǒng)的主要穩(wěn)定性能指標(biāo)如下。（1）平均系統(tǒng)隊(duì)長：

（2）平均等待隊(duì)長：（3）平均逗留時(shí)間（由Little得出）：（4）平均等待時(shí)間（由Little得出）：

為了利用Little公式，需要求出有效到達(dá)率

e。由e的定義得：40例2：某照相館只有1個(gè)攝影室，接待廳有6把椅子供顧客排隊(duì)等待拍照。當(dāng)這6把椅子都坐滿時(shí)，后到的顧客就不再等待而離去。顧客按照Poisson過程到達(dá)，平均到達(dá)率為3人/小時(shí)，拍照時(shí)間服從（負(fù)）指數(shù)分布，平均每人耗時(shí)15分鐘，求：（1）顧客來拍照不必等待的概率；（2）在照相館內(nèi)的平均顧客數(shù)；（3）顧客在照相館內(nèi)的平均逗留時(shí)間；（4）在可能到來的顧客中不等待就離去者占多少？41（1）顧客來拍照不必等待的概率即為狀態(tài)概率P0

則根據(jù)狀態(tài)概率公式，當(dāng)

1時(shí)：

（2）在照相館內(nèi)的平均顧客數(shù)為（

1時(shí)）：

解：首先判斷出這是一個(gè)M|M|1|N系統(tǒng)。其中：N=7，

=3/小時(shí)，

=4人/小時(shí)，

=

/

=3/4=0.75

其它參數(shù)指標(biāo)計(jì)算如下。42（3）顧客在照相館內(nèi)的平均逗留時(shí)間

先求得顧客的有效到達(dá)率為：

則顧客在照相館內(nèi)的平均逗留時(shí)間為：

（4）在可能到來的顧客中不等待就離去者占多少？由“系統(tǒng)滿員的概率，也就是顧客損失率PN”得：離去者的百分比等于系統(tǒng)的滿員概率P7，當(dāng)

1時(shí)，

43三、M|M|c|

系統(tǒng)許多實(shí)際系統(tǒng)往往不止一個(gè)服務(wù)員，而是有多個(gè)服務(wù)員同時(shí)工作。如果在上述只有一個(gè)服務(wù)員、系統(tǒng)容量為無限的基礎(chǔ)上，改成為有c個(gè)服務(wù)員，就變成了M|M|c|

系統(tǒng)，簡記為M|M|c系統(tǒng)。因此，此系統(tǒng)模型除了服務(wù)員個(gè)數(shù)為c

1以外，其他系統(tǒng)特性與M|M|1系統(tǒng)完全相同。其中，規(guī)定各服務(wù)員的工作相互獨(dú)立，且平局服務(wù)率相同，即：

于是，服務(wù)機(jī)構(gòu)的平均服務(wù)率為：其中，n為系統(tǒng)中的顧客數(shù)。44這時(shí)，系統(tǒng)的服務(wù)強(qiáng)度應(yīng)為：為了避免形成無限長隊(duì)列，假設(shè)

<1。

系統(tǒng)的狀態(tài)概率為：45由狀態(tài)概率Pn可推導(dǎo)出系統(tǒng)的主要穩(wěn)定性能指標(biāo)如下。（1）平均系統(tǒng)隊(duì)長：

（2）平均等待隊(duì)長：（3）平均逗留時(shí)間：（4）平均等待時(shí)間：（5）系統(tǒng)中已有c人（即各服務(wù)臺都沒有空閑），后續(xù)顧客到來必須等待的概率為：46例3：某售票處有三個(gè)窗口，顧客到達(dá)為poisson過程，平均每分鐘到達(dá)0.9人，服務(wù)（售票）時(shí)間服從（負(fù)）指數(shù)分布，平均服務(wù)率為每分鐘0.4人，假設(shè)：（1）顧客到達(dá)后排成單隊(duì)，依次到空閑窗口買票；（2）顧客到達(dá)后可在任一窗口前排隊(duì)，形成三隊(duì)但各隊(duì)之間有欄桿隔開，不能互相轉(zhuǎn)移。（3）分析比較兩種排隊(duì)系統(tǒng)的主要性能指標(biāo)。解：(1)顧客到達(dá)后排成單隊(duì)，依次到空閑窗口買票。這時(shí)系統(tǒng)為為M|M|c系統(tǒng)。其中c=3，

=0.9（人/分），=0.4（人/分），故其系統(tǒng)服務(wù)強(qiáng)度：=

/c

=0.9/3*0.4=0.75

狀態(tài)概率：P0=0.074847顧客必須排隊(duì)等待服務(wù)的概率為：

其他主要指標(biāo)為：（2）顧客到達(dá)后可在任一窗口前排隊(duì)，形成三隊(duì)，但各隊(duì)之間有欄桿隔開，不能互相轉(zhuǎn)移。這時(shí)，系統(tǒng)相當(dāng)于3個(gè)M|M|1系統(tǒng)，且平均到達(dá)率相等，即：其他主要性能指標(biāo)按照M|M|1系統(tǒng)的計(jì)算公式即可求得，具體數(shù)據(jù)見表9-2。48（3）兩種排隊(duì)方式的性能比較根據(jù)（1）、（2）兩種方式計(jì)算出來的性能指標(biāo)如表9-2所示。表9-2指標(biāo)M|M|3M|M|1P00.07480.25（子系統(tǒng)）P{Wq>0}0.570.75Lq1.7（人）2.25（人）（子系統(tǒng)）L3.95（人）10（人）（子系統(tǒng)）W4.39（分）10（分）Wq1.89（分）7.5（分）

對比表中各項(xiàng)指標(biāo)，可以看出：單隊(duì)列進(jìn)入一個(gè)M|M|3系統(tǒng)比3隊(duì)列進(jìn)入三個(gè)M|M|1系統(tǒng)有顯著的優(yōu)越性。49四、M|M|c|N系統(tǒng)當(dāng)系統(tǒng)容量為有限（最多容納N個(gè)顧客），且有多個(gè)服務(wù)員（服務(wù)員個(gè)數(shù)為c）的時(shí)候，就構(gòu)成一個(gè)M|M|c|N系統(tǒng)。該系統(tǒng)中排隊(duì)等候的顧客數(shù)最多為N-c，當(dāng)系統(tǒng)中已有N個(gè)顧客時(shí)，后來的顧客不再進(jìn)入系統(tǒng)而離去。其他條件與M|M|c系統(tǒng)相同。假設(shè)系統(tǒng)的服務(wù)強(qiáng)度

=

/c

1，則系統(tǒng)的狀態(tài)概率和性能指標(biāo)的計(jì)算公式如下：50由狀態(tài)概率Pn可推導(dǎo)出系統(tǒng)的主要穩(wěn)定性能指標(biāo)如下。（1）平均系統(tǒng)隊(duì)長：

（2）平均等待隊(duì)長：（3）平均逗留時(shí)間：（4）平均等待時(shí)間：當(dāng)出現(xiàn)N=c（即時(shí)制）的特殊情況時(shí)，有：平均系統(tǒng)隊(duì)長：

平均等待隊(duì)長：平均逗留時(shí)間：平均等待時(shí)間：此時(shí)，L既是系統(tǒng)內(nèi)的顧客數(shù)，也是正在服務(wù)的服務(wù)員平均數(shù)。51例4：某銀行有兩臺自動(dòng)取款柜員機(jī)，設(shè)取款人到達(dá)后排成一隊(duì)，依次走向空閑機(jī)器前取款。根據(jù)以往觀察，當(dāng)兩臺取款機(jī)前滿5人時(shí)，后面到達(dá)的顧客即會自動(dòng)離去。假設(shè)取款人到達(dá)的間隔時(shí)間與取款時(shí)間均為（負(fù)）指數(shù)分布，平均到達(dá)率為30人/小時(shí)，平均取款時(shí)間約為3.2人/mi，求到達(dá)即取款的概率與系統(tǒng)的主要性能指標(biāo)。解：根據(jù)題意分析，該系統(tǒng)為M|M|c|N系統(tǒng)。其中：c=2,N=5,λ=30（人/小時(shí)）

ц=60/3.2=18.75（人/小時(shí)）因此，其系統(tǒng)服務(wù)強(qiáng)度為：

=

/c

=30/2*18.75=0.852（1）到達(dá)即能取款的概率（等待時(shí)間為0的概率）即求：P(Wq=0)=P0+P1

根據(jù)公式求得：P0=0.1568；P1=0.2509；則：P(Wq=0)=0.1568+0.2509=0.4077=40.77%（2）系統(tǒng)主要性能指標(biāo)根據(jù)公式可以計(jì)算得：柜員機(jī)前平均等待人數(shù)Lq=0.73（人）；柜員機(jī)前取款加等待的平均人數(shù)L=2.16（人）；每個(gè)顧客的平均等待時(shí)間Wq=0.027（小時(shí)）=1.62（分）；顧客在柜員機(jī)前的平均逗留時(shí)間W=1.62+3.2=4.82（分）53§9-3非Poisson排隊(duì)系統(tǒng)一、Pollaczek-Khintchine公式二、M|D|1|

系統(tǒng)三、M|Ek|1|

系統(tǒng)54§9-3非Poisson排隊(duì)系統(tǒng)

Poission排隊(duì)系統(tǒng)的特點(diǎn)是輸入過程為Poission過程，服務(wù)時(shí)間分布為（負(fù)）指數(shù)分布，若兩個(gè)條件至少有一個(gè)不