第10章-排隊(duì)論-《運(yùn)籌學(xué)》課件全

第十章排隊(duì)論OperationalResearch(OR)排隊(duì)系統(tǒng)特征及排隊(duì)論隊(duì)列服務(wù)機(jī)構(gòu)顧客源到達(dá)離去排隊(duì)系統(tǒng)的特征及排隊(duì)論現(xiàn)實(shí)世界中形形色色的排隊(duì)系統(tǒng)到達(dá)的顧客要求的服務(wù)服務(wù)機(jī)構(gòu)1.不能運(yùn)轉(zhuǎn)的機(jī)器修理修理工人2.修理工人領(lǐng)取修配零件管理員3.病人就診醫(yī)生4.打電話通話交換臺(tái)5.文稿打字打字員排隊(duì)系統(tǒng)的特征及排隊(duì)論排隊(duì)系統(tǒng)的具體形式：圖1單服務(wù)排隊(duì)系統(tǒng)顧客到達(dá)服務(wù)完成后離去服務(wù)臺(tái)…隊(duì)列正在接受服務(wù)的顧客顧客到達(dá)服務(wù)完成后離去服務(wù)臺(tái)2…隊(duì)列服務(wù)臺(tái)s服務(wù)臺(tái)1...圖2s個(gè)服務(wù)臺(tái)，一個(gè)隊(duì)列的排隊(duì)系統(tǒng)排隊(duì)系統(tǒng)的特征及排隊(duì)論…隊(duì)列2顧客到達(dá)服務(wù)完成后離去服務(wù)臺(tái)2…隊(duì)列1服務(wù)臺(tái)s服務(wù)臺(tái)1...…隊(duì)列s服務(wù)完成后離去服務(wù)完成后離去圖3s個(gè)服務(wù)臺(tái)，s個(gè)隊(duì)列的排隊(duì)系統(tǒng)顧客到達(dá)…………服務(wù)臺(tái)1…………服務(wù)臺(tái)2服務(wù)完成離去隊(duì)列隊(duì)列圖4多個(gè)服務(wù)臺(tái)的串聯(lián)排隊(duì)系統(tǒng)排隊(duì)系統(tǒng)的特征及排隊(duì)論上述形式都可概括為：服務(wù)機(jī)構(gòu)聚散（輸入）（輸出）圖5隨機(jī)服務(wù)系統(tǒng)排隊(duì)系統(tǒng)的描述1.輸入過程（1）顧客總體（顧客源）數(shù)：?無限(如來商店購物的顧客數(shù)量)?有限

m

（如車間里待修理的機(jī)器）（2）到達(dá)方式：?jiǎn)蝹€(gè)到達(dá)還是成批到達(dá)。（3）顧客(單個(gè)或成批)相繼到達(dá)時(shí)間間隔的分布：①定長(zhǎng)分布（D）②最簡(jiǎn)流（或稱Poisson流）（M）排隊(duì)系統(tǒng)的描述2.排隊(duì)及排隊(duì)規(guī)則(1)排隊(duì)，排隊(duì)分為有限排隊(duì)和無限排隊(duì)兩類，對(duì)有限排隊(duì)系統(tǒng)，可進(jìn)一步分為兩種：①損失制排隊(duì)系統(tǒng)②混合制排隊(duì)系統(tǒng)，具體說來，又分為以下三種：

(i)隊(duì)長(zhǎng)有限

(ii)等待時(shí)間有限

(iii)逗留時(shí)間(等待時(shí)間與服務(wù)時(shí)間之和)有限排隊(duì)系統(tǒng)的描述(2)排隊(duì)規(guī)則，當(dāng)顧客到達(dá)時(shí)，若所有服務(wù)臺(tái)都被占用且又允許排隊(duì)，則該顧客將進(jìn)入隊(duì)列等待。服務(wù)臺(tái)對(duì)顧客進(jìn)行服務(wù)所遵循的規(guī)則通常有：①先來先服務(wù)(FCFS)②后來先服務(wù)(LCFS)③具有優(yōu)先權(quán)的服務(wù)(PS)排隊(duì)系統(tǒng)的描述3.服務(wù)機(jī)制

排隊(duì)系統(tǒng)的服務(wù)機(jī)制主要包括：服務(wù)員的數(shù)量及其連接形式(串聯(lián)或并聯(lián))；顧客是單個(gè)還是成批接受服務(wù)；服務(wù)時(shí)間的分布。記某服務(wù)臺(tái)的服務(wù)時(shí)間為V，其分布函數(shù)為B(t)，密度函數(shù)為b(t)，則常見的分布有：(1)定長(zhǎng)分布(D)(2)負(fù)指數(shù)分布(M)(3)k階愛爾朗分布(Ek)：排隊(duì)系統(tǒng)的符號(hào)表示排隊(duì)系統(tǒng)的符號(hào)表示“Kendall記號(hào)”，其一般形式為：X/Y/Z/A/B/C，其中

XX：顧客到達(dá)時(shí)間間隔的分布

YY：服務(wù)時(shí)間的分布

ZZ：服務(wù)臺(tái)個(gè)數(shù)A：系統(tǒng)容量BB：顧客源數(shù)量

CC：服務(wù)規(guī)則例（M/M/1/FCFS）表示：到達(dá)間隔為負(fù)指數(shù)分布，服務(wù)時(shí)間也為負(fù)指數(shù)分布，1個(gè)服務(wù)臺(tái)，顧客源無限，系統(tǒng)容量也無限，先到先服務(wù)。若只討論先到先服務(wù)的情況，可略去第6項(xiàng)。排隊(duì)系統(tǒng)的主要數(shù)量指標(biāo)和記號(hào)描述一個(gè)排隊(duì)系統(tǒng)運(yùn)行狀況的主要數(shù)量指標(biāo)有：1.隊(duì)長(zhǎng)和排隊(duì)長(zhǎng)2.等待時(shí)間和逗留時(shí)間3.忙期和閑期上述一些主要數(shù)量指標(biāo)的常用記號(hào)：N(t)：時(shí)刻t系統(tǒng)中的顧客數(shù)(又稱為系統(tǒng)的狀態(tài))，即隊(duì)長(zhǎng)；Nq(t)：時(shí)刻t系統(tǒng)中排隊(duì)的顧客數(shù)，即排隊(duì)長(zhǎng)；T(t)：時(shí)刻t到達(dá)系統(tǒng)的顧客在系統(tǒng)中的逗留時(shí)間；Tq(t)：時(shí)刻t到達(dá)系統(tǒng)的顧客在系統(tǒng)中的等待時(shí)間。排隊(duì)系統(tǒng)的主要數(shù)量指標(biāo)和記號(hào)記pn(t)為時(shí)刻t時(shí)系統(tǒng)處于狀態(tài)n的概率，即系統(tǒng)的瞬時(shí)分布。我們將主要分析系統(tǒng)的平穩(wěn)分布，即當(dāng)系統(tǒng)達(dá)到統(tǒng)計(jì)平衡時(shí)處于狀態(tài)n的概率，記為pn。又記N：系統(tǒng)處于平穩(wěn)狀態(tài)時(shí)的隊(duì)長(zhǎng)，其均值為L(zhǎng)，稱為平均隊(duì)長(zhǎng)；Nq：系統(tǒng)處于平穩(wěn)狀態(tài)時(shí)的排隊(duì)長(zhǎng)，其均值為L(zhǎng)q，稱為平均排隊(duì)長(zhǎng)；T：系統(tǒng)處于平穩(wěn)狀態(tài)時(shí)顧客的逗留時(shí)間，其均值記為W，稱為平均逗留時(shí)間；Tq：系統(tǒng)處于平穩(wěn)狀態(tài)時(shí)顧客的等待時(shí)間，其均值記為Wq，稱為平均等待時(shí)間；排隊(duì)系統(tǒng)的主要數(shù)量指標(biāo)和記號(hào)λn：當(dāng)系統(tǒng)處于狀態(tài)n時(shí)，新來顧客的平均到達(dá)率(單位時(shí)間內(nèi)來到系統(tǒng)的平均顧客數(shù))；μn：當(dāng)系統(tǒng)處于狀態(tài)n時(shí)，整個(gè)系統(tǒng)的平均服務(wù)率(單位時(shí)間內(nèi)可以服務(wù)完的顧客數(shù))；當(dāng)λn為常數(shù)時(shí)，記為λ；當(dāng)每個(gè)服務(wù)臺(tái)的平均服務(wù)率為常數(shù)時(shí)，記每個(gè)服務(wù)臺(tái)的服務(wù)率為μ，則當(dāng)n≥s時(shí)，有μn=sμ。因此，顧客相繼到達(dá)的平均時(shí)間間隔為1/λ，平均服務(wù)時(shí)間為1/μ。令ρ=λ/sμ，稱ρ為系統(tǒng)的服務(wù)強(qiáng)度。另外，記忙期為B，閑期為I，平均忙期和平均閑期分別記為和，記s為系統(tǒng)中并行的服務(wù)臺(tái)數(shù)。排隊(duì)論研究的基本問題排隊(duì)論研究的基本問題：(1)通過研究主要數(shù)量指標(biāo)在瞬時(shí)或平穩(wěn)狀態(tài)下的概率分布及其數(shù)字特征，了解系統(tǒng)運(yùn)行的基本特征。(2)統(tǒng)計(jì)推斷問題，建立適當(dāng)?shù)呐抨?duì)模型是排隊(duì)論研究的第一步，建立模型過程中經(jīng)常會(huì)碰到如下問題：檢驗(yàn)系統(tǒng)是否達(dá)到平穩(wěn)狀態(tài)；檢驗(yàn)顧客相繼到達(dá)時(shí)間間隔的相互獨(dú)立性；確定服務(wù)時(shí)間的分布及有關(guān)參數(shù)等。(3)系統(tǒng)優(yōu)化問題，又稱為系統(tǒng)控制問題或系統(tǒng)運(yùn)營(yíng)問題，其基本目的是使系統(tǒng)處于最優(yōu)或最合理的狀態(tài)。系統(tǒng)優(yōu)化問題包括最優(yōu)設(shè)計(jì)問題和最優(yōu)運(yùn)營(yíng)問題，其內(nèi)容很多，有最少費(fèi)用問題、服務(wù)率的控制問題、服務(wù)臺(tái)的開關(guān)策略、顧客(或服務(wù))根據(jù)優(yōu)先權(quán)的最優(yōu)排序等方面的問題。生

滅

過

程

和Poisson過

程設(shè){N(t),t≥0}為一個(gè)隨機(jī)過程。若N(t)的概率分布具有以下性質(zhì)：(1)假設(shè)N(t)=n，則從時(shí)刻t起到下一個(gè)顧客到達(dá)時(shí)刻止的時(shí)間服從參數(shù)為λn的負(fù)指數(shù)分布，n=0,1,2,…。(2)假設(shè)N(t)=n，則從時(shí)刻t起到下一個(gè)顧客離去時(shí)刻止的時(shí)間服從參數(shù)為μn的負(fù)指數(shù)分布，n=0,1,2，…。(3)同一時(shí)刻時(shí)只有一個(gè)顧客到達(dá)或離去。則稱{N(t),t≥0}為一個(gè)生滅過程。一、生滅過程簡(jiǎn)介定義1生

滅

過

程

和Poisson過

程二、Poisson過程和負(fù)指數(shù)分布設(shè)N(t)為時(shí)間［0,t］內(nèi)到達(dá)系統(tǒng)的顧客數(shù)，如果滿足下面三個(gè)條件：(1)平穩(wěn)性：在［t,t+Δt］內(nèi)有一個(gè)顧客到達(dá)的概率為λt+o(Δt)；(2)獨(dú)立性：任意兩個(gè)不相交區(qū)間內(nèi)顧客到達(dá)情況相互獨(dú)立；(3)普通性：在［t,t+Δt］內(nèi)多于一個(gè)顧客到達(dá)的概率為o(Δt)。則稱{N(t),t≥0}為Poisson過程。定義2生

滅

過

程

和Poisson過

程設(shè)N(t)為時(shí)間［0,t］內(nèi)到達(dá)系統(tǒng)的顧客數(shù)，則{N(t),t≥0}為Poisson過程的充分必要條件是：(n=1,2,...)設(shè)N(t)為時(shí)間［0,t］內(nèi)到達(dá)系統(tǒng)的顧客數(shù)，則{N(t),t≥0}為參數(shù)為λ的Poisson過程的充分必要條件是：相繼到達(dá)時(shí)間間隔服從相互獨(dú)立的參數(shù)為λ的負(fù)指數(shù)分布。定理1定理2M/M/s

等

待

制

排

隊(duì)

模

型一、單服務(wù)臺(tái)模型單服務(wù)臺(tái)等待制模型M/M/1/∞是指：顧客的相繼到達(dá)時(shí)間服從參數(shù)為λ的負(fù)指數(shù)分布，服務(wù)臺(tái)個(gè)數(shù)為1，服務(wù)時(shí)間V服從參數(shù)為μ的負(fù)指數(shù)分布，系統(tǒng)空間無限，允許無限排隊(duì)。單服務(wù)臺(tái)模型1.隊(duì)長(zhǎng)的分布記pn=P{N=n}(n=0,1,2,…)為系統(tǒng)達(dá)到平穩(wěn)狀態(tài)后隊(duì)長(zhǎng)N的概率分布，并注意到λn=λ,n=0,1,2,…和μn=μ，n=1,2,…記ρ=λ/μ設(shè)ρ<1，則(n=1,2,...)故(n=1,2,...)其中，因此，(n=0,1,2,...)單服務(wù)臺(tái)模型2.幾個(gè)主要數(shù)量指標(biāo)對(duì)單服務(wù)臺(tái)等待制排隊(duì)系統(tǒng)，由已得到的平穩(wěn)狀態(tài)下隊(duì)長(zhǎng)的分布，可以得到平均隊(duì)長(zhǎng)L為:平均排隊(duì)長(zhǎng)Lq為：?jiǎn)畏?wù)臺(tái)模型關(guān)于顧客在系統(tǒng)中的逗留時(shí)間T，可說明它服從參數(shù)為μ-λ的負(fù)指數(shù)分布，即t≥0因此，平均逗留時(shí)間W為：因?yàn)椋櫩驮谙到y(tǒng)中的逗留時(shí)間為等待時(shí)間和接受服務(wù)時(shí)間之和，即T=Tq+V。其中，V為服務(wù)時(shí)間，故由可得平均等待時(shí)間Wq為:單服務(wù)臺(tái)模型平均隊(duì)長(zhǎng)L與平均逗留時(shí)間W的關(guān)系：L=λW平均排隊(duì)長(zhǎng)Lq與平均等待時(shí)間Wq有如下關(guān)系：Lq=λWq這兩個(gè)式子通常稱為L(zhǎng)ittle公式，是排隊(duì)論中一個(gè)非常重要的公式。單服務(wù)臺(tái)模型3.忙期和閑期忙期的平均長(zhǎng)度和閑期的平均長(zhǎng)度之比是：平均忙期為：不難發(fā)現(xiàn)，一個(gè)顧客在系統(tǒng)內(nèi)的平均逗留時(shí)間等于服務(wù)員平均連續(xù)忙的時(shí)間。多服務(wù)臺(tái)模型前提:單隊(duì)、并列服務(wù)臺(tái)我們僅討論標(biāo)準(zhǔn)的M/M/C2……1C多服務(wù)臺(tái)模型下面來討論這個(gè)排隊(duì)系統(tǒng)的平穩(wěn)分布。記pn=P{N=n}(n=0,1,2，…)為系統(tǒng)達(dá)到平穩(wěn)狀態(tài)后隊(duì)長(zhǎng)N的概率分布，注意到對(duì)個(gè)數(shù)為s的多服務(wù)臺(tái)系統(tǒng)，有λn=λ(n=0,1,2,…)和n=1,2,...,sn=s,s+1,...記則當(dāng)ρs<1時(shí)，有n=1,2,...,sn≥s多服務(wù)臺(tái)模型故n=1,2,...,sn≥s其中，給出了在平衡條件下系統(tǒng)中顧客數(shù)為n的概率，當(dāng)n≥s時(shí)，即系統(tǒng)中顧客數(shù)大于或等于服務(wù)臺(tái)個(gè)數(shù)，這時(shí)再來的顧客必須等待，因此記稱為Erlang等待公式，它給出了顧客到達(dá)系統(tǒng)時(shí)需要等待的概率。多服務(wù)臺(tái)模型對(duì)多服務(wù)臺(tái)等待制排隊(duì)系統(tǒng)，由已得到的平穩(wěn)分布可得平均排隊(duì)長(zhǎng)Lq為：或多服務(wù)臺(tái)模型記系統(tǒng)中正在接受服務(wù)的顧客的平均數(shù)為，顯然也是正在忙的服務(wù)臺(tái)的平均數(shù)，故說明，平均在忙的服務(wù)臺(tái)個(gè)數(shù)不依賴于服務(wù)臺(tái)個(gè)數(shù)s平均隊(duì)長(zhǎng)L為：L=平均排隊(duì)長(zhǎng)+正在接受服務(wù)的顧客的平均數(shù)=Lq+ρ對(duì)多服務(wù)臺(tái)系統(tǒng)，Little公式依然成立，即有M/M/s混

合

制

排

隊(duì)

模

型一、單服務(wù)臺(tái)混合制模型M/M/1/K：顧客的相繼到達(dá)時(shí)間服從參數(shù)為λ的負(fù)指數(shù)分布(即顧客的到達(dá)過程為Poisson流)，服務(wù)臺(tái)個(gè)數(shù)為1，服務(wù)時(shí)間V服從參數(shù)為μ的負(fù)指數(shù)分布，系統(tǒng)的空間為K。單服務(wù)臺(tái)混合制模型平穩(wěn)狀態(tài)下隊(duì)長(zhǎng)N的分布pn=P{N=n},n=0,1,2,…。由于所考慮的排隊(duì)系統(tǒng)中最多只能容納K個(gè)顧客(等待位置只有K-1個(gè))，因而有n=0,1,2,...,K-1n≥Kn=1,2,...Kn=0,1,2,...,Kn>K有故n=1,2,…,K其中，ρ≠1ρ=1單服務(wù)臺(tái)混合制模型由已得到的單服務(wù)臺(tái)混合制排隊(duì)系統(tǒng)平穩(wěn)狀態(tài)下隊(duì)長(zhǎng)的分布，可知當(dāng)ρ≠1時(shí)，平均隊(duì)長(zhǎng)L為：當(dāng)ρ=1時(shí)單服務(wù)臺(tái)混合制模型類似地可得到平均排隊(duì)長(zhǎng)Lq為:或ρ≠1ρ=1單位時(shí)間內(nèi)實(shí)際可進(jìn)入系統(tǒng)的顧客的平均數(shù)為：λe=λ(1-pK)=μ(1-P0)稱λe為有效到達(dá)率，而pK也被稱為顧客損失率，它表示了在來到系統(tǒng)的所有顧客數(shù)中不能進(jìn)入系統(tǒng)的顧客的比例。單服務(wù)臺(tái)混合制模型根據(jù)Little公式，可得：平均逗留時(shí)間平均等待時(shí)間且仍有特別，當(dāng)K=1時(shí)，M/M/1/1為單服務(wù)臺(tái)損失制系統(tǒng)，在上述有關(guān)結(jié)果中令K=1，可得到：多服務(wù)臺(tái)混合制模型二、多服務(wù)臺(tái)混合制模型M/M/s/K：顧客的相繼到達(dá)時(shí)間服從參數(shù)為λ的負(fù)指數(shù)分布(即顧客的到達(dá)過程為Poisson流)，服務(wù)臺(tái)個(gè)數(shù)為s，每個(gè)服務(wù)臺(tái)服務(wù)時(shí)間相互獨(dú)立，且服從參數(shù)為μ的負(fù)指數(shù)分布，系統(tǒng)的空間為K。多服務(wù)臺(tái)混合制模型n=0,1,2,...,K-1n≥K0≤n<ss≤n≤K由得0≤n<ss≤n≤K其中ρs≠1ρs=1多服務(wù)臺(tái)混合制模型由平穩(wěn)分布pn,n=0,1,2,…,K，可得平均排隊(duì)長(zhǎng)為：ρs≠1ρs=1平均隊(duì)長(zhǎng):顧客的有效到達(dá)率:利用Little公式，得到多服務(wù)臺(tái)混合制模型平均被占用的服務(wù)臺(tái)數(shù)(也是正在接受服務(wù)的顧客的平均數(shù))為：因此，又有其他排隊(duì)模型簡(jiǎn)介一、有限源排隊(duì)模型……服務(wù)臺(tái)顧客源隊(duì)列圖1有限源排隊(duì)系統(tǒng)顧客總數(shù)是有限的。每個(gè)顧客來到系統(tǒng)中接受服務(wù)后仍回到原來的總體，還有可能再來，這類排隊(duì)問題的典型例子是機(jī)器看管問題。有限源排隊(duì)模型平穩(wěn)狀態(tài)下隊(duì)長(zhǎng)N的分布pn=P{N=n},n=0,1,2,…,mn=1,2,...,sn=s,s+1,...m其中有限源排隊(duì)模型系統(tǒng)的有關(guān)運(yùn)行指標(biāo)：或有限源排隊(duì)模型特別，對(duì)單服務(wù)臺(tái)(s=1)系統(tǒng)，有（n=1,…,m）或系統(tǒng)的相對(duì)通過能力Q=1，絕對(duì)通過能力A=λeQ=λ(m-L)=μ(1-p0)非生滅過程排隊(duì)模型三、非生滅過程排隊(duì)模型以上討論的系統(tǒng)，其前提均為泊松輸入和負(fù)指數(shù)服務(wù)處理，在實(shí)際中，有時(shí)到達(dá)仍為泊松過程，但服務(wù)時(shí)間并不服從負(fù)指數(shù)分布，這時(shí)不能用生滅過程處理，必須引入新的方法來分析具有非負(fù)指數(shù)分布的排隊(duì)系統(tǒng)。下面僅就幾種特殊情形給出有關(guān)的結(jié)果。非生滅過程排隊(duì)模型1.M/G/1排隊(duì)模型M/G/1系統(tǒng)：顧客的到達(dá)為Poisson流，單個(gè)服務(wù)臺(tái)，服務(wù)時(shí)間為一般分布的排隊(duì)系統(tǒng)?，F(xiàn)假設(shè)顧客的平均到達(dá)率為λ，服務(wù)時(shí)間的均值為1/μ，方差為σ2，則可證明：當(dāng)ρ=λ/μ<1時(shí)，系統(tǒng)可以達(dá)到平穩(wěn)狀態(tài)，而給出平穩(wěn)分布的表示是比較困難的。已有的幾個(gè)結(jié)果為：Lq,L,W,Wq等僅依賴于ρ和服務(wù)時(shí)間的方差σ2，而與分布的類型沒有關(guān)系，這是排隊(duì)論中一個(gè)非常重要且令人驚奇的結(jié)果。通常被稱為Pollaczek\|Khintchine(P\|K)公式。非生滅過程排隊(duì)模型2.愛爾朗(Erlang)排隊(duì)模型對(duì)愛爾朗排隊(duì)模型研究的一般方法是根據(jù)k-階Erlang分布恰為k個(gè)相同負(fù)指數(shù)分布隨機(jī)變量和的分布這個(gè)關(guān)系，把服務(wù)時(shí)間或到達(dá)過程假想地(實(shí)際并非如此)分為k個(gè)獨(dú)立的同分布的位相(或階段)，然后利用負(fù)指數(shù)分布的性質(zhì)來加以分析。非生滅過程排隊(duì)模型作為一個(gè)特例，給出M/Ek/1/∞的主要數(shù)量指標(biāo)：服務(wù)時(shí)間為k-階Erlang分布，其分布密度函數(shù)為：t≥0其均值和方差分別為：排隊(duì)系統(tǒng)的優(yōu)化我們主要研究靜態(tài)優(yōu)化，目標(biāo):費(fèi)用(損失)最小。?ì?í?系統(tǒng)設(shè)計(jì)優(yōu)化（靜態(tài)）：如何設(shè)計(jì)一個(gè)系統(tǒng)（如何定μ，C，服務(wù)規(guī)則）使費(fèi)用最經(jīng)濟(jì)（未必最小）。

系統(tǒng)控制優(yōu)化（動(dòng)態(tài)）：一個(gè)給定