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

m

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

(i)隊長有限

(ii)等待時間有限

(iii)逗留時間(等待時間與服務時間之和)有限排隊系統的描述(2)排隊規則，當顧客到達時，若所有服務臺都被占用且又允許排隊，則該顧客將進入隊列等待。服務臺對顧客進行服務所遵循的規則通常有：①先來先服務(FCFS)②后來先服務(LCFS)③具有優先權的服務(PS)排隊系統的描述3.服務機制

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

XX：顧客到達時間間隔的分布

YY：服務時間的分布

ZZ：服務臺個數A：系統容量BB：顧客源數量

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

滅

過

程

和Poisson過

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

滅

過

程

和Poisson過

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

滅

過

程

和Poisson過

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

等

待

制

排

隊

模

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

合

制

排

隊

模

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

系統控制優化（動態）：一個給定