1、-PAGE 78-PAGE 88- 第六章 排隊(pi du)論模型排隊論起源于1909年丹麥(dn mi)電話工程師A. K愛爾朗的工作，他對電話通話(tng hu)擁擠問題進行了研究。1917年，愛爾朗發(fā)表了他的著名的文章“自動電話交換中的概率理論的幾個問題的解決”。排隊論已廣泛應用于解決軍事、運輸、維修、生產、服務、庫存、醫(yī)療衛(wèi)生、教育、水利灌溉之類的排隊系統的問題，顯示了強大的生命力。排隊是在日常生活中經常遇到的現象，如顧客到商店購買物品、病人到醫(yī)院看病常常要排隊。此時要求服務的數量超過服務機構（服務臺、服務員等）的容量。也就是說，到達的顧客不能立即得到服務，因而出現了排隊現象。這種現

2、象不僅在個人日常生活中出現，電話局的占線問題，車站、碼頭等交通樞紐的車船堵塞和疏導，故障機器的停機待修，水庫的存貯調節(jié)等都是有形或無形的排隊現象。由于顧客到達和服務時間的隨機性。可以說排隊現象幾乎是不可避免的。 排隊論（Queuing Theory）也稱隨機服務系統理論，就是為解決上述問題而發(fā)展的一門學科。它研究的內容有下列三部分：（ = 1 * roman i）性態(tài)問題，即研究各種排隊系統的概率規(guī)律性，主要是研究隊長分布、等待時間分布和忙期分布等，包括了瞬態(tài)和穩(wěn)態(tài)兩種情形。 （ = 2 * roman ii）最優(yōu)化問題，又分靜態(tài)最優(yōu)和動態(tài)最優(yōu)，前者指最優(yōu)設計。后者指現有排隊系統的最優(yōu)運營。

3、（ = 3 * roman iii）排隊系統的統計推斷，即判斷一個給定的排隊系統符合于那種模型，以便根據排隊理論進行分析研究。 這里將介紹排隊論的一些基本知識，分析幾個常見的排隊模型。1 基本概念1.1 排隊過程的一般表示 下圖是排隊論的一般模型。服務機構（服務時間隨機）顧客排隊 顧客隨機達到 顧客離去 圖中虛線所包含的部分為排隊系統。各個顧客從顧客源出發(fā)，隨機地來到服務機構，按一定的排隊規(guī)則等待服務，直到按一定的服務規(guī)則接受完服務后離開排隊系統。 凡要求服務的對象統稱為顧客，為顧客服務的人或物稱為服務員，由顧客和服務員組成服務系統。對于一個服務系統來說，如果服務機構過小，以致不能滿足要求服務

4、的眾多顧客的需要，那么就會產生擁擠現象而使服務質量降低。 因此，顧客總希望服務機構越大越好，但是，如果服務機構過大，人力和物力方面的開支也就相應增加，從而會造成浪費，因此研究排隊模型的目的就是要在顧客需要和服務機構的規(guī)模之間進行權衡決策，使其達到合理的平衡。1.2 排隊(pi du)系統的組成和特征 一般的排隊過程都由輸入(shr)過程、排隊規(guī)則、服務過程三部分組成，現分述如下：1.2.1 輸入(shr)過程輸入過程是指顧客到來時間的規(guī)律性，可能有下列不同情況：（ = 1 * roman i）顧客的組成可能是有限的，也可能是無限的。 （ = 2 * roman ii）顧客到達的方式可能是一個個

5、的，也可能是成批的。 （ = 3 * roman iii）顧客到達可以是相互獨立的，即以前的到達情況對以后的到達沒有影響；否則是相關的。 （ = 4 * roman iv）輸入過程可以是平穩(wěn)的，即相繼到達的間隔時間分布及其數學期望、方差等數字特征都與時間無關，否則是非平穩(wěn)的。1.2.2 排隊規(guī)則 排隊規(guī)則指到達排隊系統的顧客按怎樣的規(guī)則排隊等待，可分為損失制，等待制和混合制三種。 （ = 1 * roman i）損失制（消失制）。當顧客到達時，所有的服務臺均被占用，顧客隨即離去。 （ = 2 * roman ii）等待制。當顧客到達時，所有的服務臺均被占用，顧客就排隊等待，直到接受完服務才離去

6、。例如出故障的機器排隊等待維修就是這種情況。 （ = 3 * roman iii）混合制。介于損失制和等待制之間的是混合制，即既有等待又有損失。有隊列長度有限和排隊等待時間有限兩種情況，在限度以內就排隊等待，超過一定限度就離去。 排隊方式還分為單列、多列和循環(huán)隊列。 1.2.3 服務過程（ = 1 * roman i）服務機構。主要有以下幾種類型：單服務臺；多服務臺并聯（每個服務臺同時為不同顧客服務）；多服務臺串聯（多服務臺依次為同一顧客服務）；混合型。（ = 2 * roman ii）服務規(guī)則。按為顧客服務的次序采用以下幾種規(guī)則：先到先服務，這是通常的情形。 后到先服務，如情報系統中，最后到

7、的情報信息往往最有價值，因而常被優(yōu)先處理。 隨機服務，服務臺從等待的顧客中隨機地取其一進行服務，而不管到達的先后。優(yōu)先服務，如醫(yī)療系統對病情嚴重的病人給予優(yōu)先治療。1.3 排隊模型的符號表示排隊模型用六個符號表示，在符號之間用斜線隔開，即。第一個符號表示顧客到達流或顧客到達間隔時間的分布；第二個符號表示服務時間的分布；第三個符號表示服務臺數目；第四個符號是系統容量限制；第五個符號是顧客源數目；第六個符號是服務規(guī)則，如先到先服務FCFS，后到先服務LCFS等。并約定，如略去后三項，即指的情形。我們只討論先到先服務FCFS的情形，所以略去第六項。表示(biosh)顧客到達間隔時間和服務時間的分布的

8、約定符號為：指數分布（是Markov的字頭，因為(yn wi)指數分布具有無記憶性，即Markov性）；確定(qudng)型（Deterministic）；階愛爾朗(Erlang)分布；一般（general）服務時間的分布；一般相互獨立（General Independent）的時間間隔的分布。例如，表示相繼到達間隔時間為指數分布、服務時間為指數分布、單服務臺、等待制系統。表示確定的到達時間、服務時間為指數分布、個平行服務臺（但顧客是一隊）的模型。 1.4 排隊系統的運行指標 為了研究排隊系統運行的效率，估計其服務質量，確定系統的最優(yōu)參數，評價系統的結構是否合理并研究其改進的措施，必須確定用以

9、判斷系統運行優(yōu)劣的基本數量指標，這些數量指標通常是： ( = 1 * roman i)平均隊長：指系統內顧客數（包括正被服務的顧客與排隊等待服務的顧客）的數學期望，記作。 ( = 2 * roman ii)平均排隊長:指系統內等待服務的顧客數的數學期望，記作。 ( = 3 * roman iii)平均逗留時間：顧客在系統內逗留時間（包括排隊等待的時間和接受服務的時間）的數學期望，記作。 （ = 4 * roman iv）平均等待時間：指一個顧客在排隊系統中排隊等待時間的數學期望，記作。（ = 5 * roman v）平均忙期：指服務機構連續(xù)繁忙時間（顧客到達空閑服務機構起，到服務機構再次空閑止

10、的時間）長度的數學期望，記為。還有由于顧客被拒絕而使企業(yè)受到損失的損失率以及以后經常遇到的服務強度等，這些都是很重要的指標。計算這些指標的基礎是表達系統狀態(tài)的概率。所謂系統的狀態(tài)即指系統中顧客數，如果系統中有個顧客就說系統的狀態(tài)是，它的可能值是（ = 1 * roman i）隊長沒有限制時，（ = 2 * roman ii）隊長有限制，最大數為時，（ = 3 * roman iii）損失制，服務臺個數是時，。這些狀態(tài)的概率一般是隨時刻而變化，所以在時刻、系統狀態(tài)為的概率用表示。穩(wěn)態(tài)時系統狀態(tài)為的概率用表示。2 輸入過程與服務時間的分布排隊系統中的事件流包括顧客到達流和服務時間流。由于顧客到達的

11、間隔時間和服務時間不可能是負值，因此，它的分布是非負隨機變量的分布。最常用的分布有泊松分布、確定型分布，指數分布和愛爾朗分布。2.1 泊松流與指數分布設表示(biosh)在時間區(qū)間內到達(dod)的顧客數（），令表示在時間(shjin)區(qū)間內有個顧客到達的概率，即當合于下列三個條件時，我們說顧客的到達形成泊松流。這三個條件是：1o 在不相重疊的時間區(qū)間內顧客到達數是相互獨立的，我們稱這性質為無后效性。2o 對充分小的，在時間區(qū)間內有一個顧客到達的概率與無關，而約與區(qū)間長成正比，即 （1）其中，當時，是關于的高階無窮小。是常數，它表示單位時間有一個顧客到達的概率，稱為概率強度。3o 對于充分小的

12、，在時間區(qū)間內有兩個或兩個以上顧客到達的概率極小，以致可以忽略，即 （2）在上述條件下，我們研究顧客到達數的概率分布。由條件2o，我們總可以取時間由0算起，并簡記。由條件1o和2o，有 由條件2o和3o得 因而有 ，.在以上兩式中，取趨于零的極限，當假設所涉及的函數可導時，得到以下微分方程組：，.取初值，容易(rngy)解出；再令，可以(ky)得到及其它所滿足(mnz)的微分方程組，即 ，.由此容易解得 .正如在概率論中所學過的，我們說隨機變量服從泊松分布。它的數學期望和方差分別是；。當輸入過程是泊松流時，那么顧客相繼到達的時間間隔必服從指數分布。這是由于內呼叫次數為零那么，以表示的分布函數，

13、則有而分布密度函數為.對于泊松流,表示單位時間平均到達的顧客數,所以就表示相繼顧客到達平均間隔時間，而這正和的意義相符。對一顧客的服務時間也就是在忙期相繼離開系統的兩顧客的間隔時間，有時也服從指數分布。這時設它的分布函數和密度函數分別是，我們得到 這表明，在任何小的時間間隔內一個顧客被服務完了（離去）的概率是。表示單位時間能被服務完成的顧客數，稱為平均服務率，而表示一個顧客的平均服務時間。2.2 常用的幾種概率分布及其產生2.2.1 常用的連續(xù)型概率分布我們只給出這些分布的參數、記號和通常的應用范圍，更詳細的內容參看專門的概率論書籍。（ = 1 * roman i）均勻分布區(qū)間內的均勻分布記作

14、。服從分布的隨機變量又稱為隨機數，它是產生其它隨機變量的基礎。如若為分布，則服從。（ = 2 * roman ii）正態(tài)分布以為期望(qwng)，為方差(fn ch)的正態(tài)分布記作。正態(tài)分布的應用十分廣泛。正態(tài)分布還可以作為(zuwi)二項分布一定條件下的近似。（ = 3 * roman iii）指數分布指數分布是單參數的非對稱分布，記作，概率密度函數為：它的數學期望為，方差為。指數分布是唯一具有無記憶性的連續(xù)型隨機變量，即有，在排隊論、可靠性分析中有廣泛應用。（ = 4 * roman iv）Gamma分布Gamma分布是雙參數的非對稱分布，記作，期望是。時蛻化為指數分布。個相互獨立、同分布

15、（參數）的指數分布之和是Gamma分布（。Gamma分布可用于服務時間，零件壽命等。Gamma分布又稱愛爾朗分布。（ = 5 * roman v）Weibull分布 Weibull分布是雙參數的非對稱分布，記作。時蛻化為指數分布。作為設備、零件的壽命分布在可靠性分析中有著非常廣泛的應用。（ = 6 * roman vi）Beta分布Beta分布是區(qū)間內的雙參數、非均勻分布，記作。2.2.2 常用的離散型概率分布（ = 1 * roman i）離散均勻分布（ = 2 * roman ii）Bernoulli分布（兩點分布）Bernoulli分布是處取值的概率分別是和的兩點分布，記作。用于基本的離

16、散模型。（ = 3 * roman iii）泊松（Poisson）分布泊松分布與指數分布有密切的關系。當顧客平均到達率為常數的到達間隔服從指數分布時，單位時間內到達的顧客數服從泊松分布，即單位時間內到達位顧客的概率為 記作。反過來也是這樣。泊松分布在排隊服務、產品檢驗、生物與醫(yī)學統計、天文、物理等領域都有廣泛應用。（ = 4 * roman iv）二項分布在獨立進行的每次試驗中，某事件發(fā)生的概率為，則次試驗中該事件發(fā)生的次數服從二項分布，即發(fā)生次的概率為 .記作。二項分布是個獨立(dl)的Bernoulli分布之和。它在產品檢驗、保險、生物和醫(yī)學統計等領域(ln y)有著廣泛的應用。當很大時，

17、近似于正態(tài)分布；當很大、很小，且約為常數(chngsh)時，近似于。3 標準的模型標準的模型是指適合下列條件的排隊系統：（ = 1 * roman i）輸入過程顧客源是無限的，顧客單個到來，相互獨立，一定時間的到達數服從泊松分布，到達過程已是平穩(wěn)的。（ = 2 * roman ii）排隊規(guī)則單隊，且對隊長沒有限制，先到先服務。（ = 3 * roman iii）服務機構單服務臺，各顧客的服務時間是相互獨立的，服從相同的指數分布。此外，還假定到達時間間隔和服務時間是相互獨立的。在分析標準的模型時，首先要求出系統在任意時刻的狀態(tài)為（系統中有個顧客）的概率，它決定了系統運行的特征。因已知到達規(guī)律服從

18、參數為的泊松過程，服務時間服從參數為的指數分布，所以在時間區(qū)間內有：（ = 1 * roman i）有一個顧客到達的概率為；沒有顧客到達的概率就是。（ = 2 * roman ii）當有顧客在接受服務時，1個顧客被服務完了（離去）的概率是，沒有離去的概率就是。（ = 3 * roman iii）多于一個顧客的到達或離去的概率是，是可以忽略的。設（否則隊列將排至無限遠），我們可以推出在系統穩(wěn)態(tài)時 以上式為基礎可以算出系統的運行指標：（ = 1 * roman i）在系統中的平均顧客數（隊長期望值）（ = 2 * roman ii）在隊列中等待的平均顧客數（排隊長期望值）（ = 3 * roman

19、 iii）在系統中顧客逗留時間的期望值（ = 4 * roman iv）在隊列中顧客等待時間的期望值4 產生給定分布(fnb)的隨機數的方法Matlab可以產生常用分布的隨機數。下面我們介紹按照給定(i dn)的概率分布產生隨機數的一般方法，這些方法都以分布的隨機變量(su j bin lin)為基礎。( = 1 * roman i)反變換法定理 設是一個具有連續(xù)分布函數的隨機變量，則在0，1上有均勻分布。設概率分布函數是嚴格單調增的，的反函數記作。先產生，再取即為所求，稱為反變換法。指數分布能夠方便地用反變換法產生。由的分布函數，可得思考 有的書上用代替上式，對嗎，為什么？（ = 2 * r

20、oman ii）卷積法如果隨機變量是個獨立、同分布的另一隨機變量之和，而又容易產生時，先產生個獨立的，再令即可。因為的分布函數是分布函數的卷積，故稱為卷積法。二項分布可以用卷積法產生。因為是個獨立的之和，而很容易由按以下方法得到：若，令；否則令。( = 3 * roman iii)取舍法若隨機變量在有限區(qū)間內變化，但概率密度具有任意形式（甚至沒有解析表達式），無法用前面的方法產生時，可用取舍法。一種比較簡單的取舍法的步驟是：1o 產生和；2o 記，若，則??；否則，舍去，返回1o。5 排隊模型的計算機模擬5.1 確定隨機變量概率分布的常用方法在模擬一個帶有隨機因素的實際系統時，究竟用什么樣的概率

21、分布描述問題中的隨機變量，是我們總是要碰到的一個問題，下面簡單介紹確定分布的常用方法：1o 根據一般知識和經驗，可以假定其概率分布的形式，如顧客到達間隔服從指數分布；產品需求量服從正態(tài)分布；訂票后但未能按時前往機場登機的人數服從二項分布。然后由實際數據估計分布的參數等，參數估計可用極大似然估計、矩估計等方法。2o 直接由大量的實際數據作直方圖，得到經驗(jngyn)分布，再通過假設檢驗，擬合分布函數，可用檢驗(jinyn)等方法。3o 既缺少(qusho)先驗知識，又缺少數據時，對區(qū)間內變化的隨機變量，可選用Beta分布（包括均勻分布）。先根據經驗確定隨機變量的均值和頻率最高時的數值（即密度函

22、數的最大值），則Beta分布中的參數可由以下關系求出：，.5.2 計算機模擬當排隊系統的到達間隔時間和服務時間的概率分布很復雜時，或不能用公式給出時，那么就不能用解析法求解。這就需用隨機模擬法求解，現舉例說明。例1 設某倉庫前有一卸貨場，貨車一般是夜間到達，白天卸貨，每天只能卸貨2車，若一天內到達數超過2車，那么就推遲到次日卸貨。根據下表所示的數據，貨車到達數的概率分布（相對頻率）平均為1.5車/天，求每天推遲卸貨的平均車數。到達車數 0 1 2 3 4 5 6概 率 0.23 0.30 0.30 0.1 0.05 0.02 0.00解 這是單服務臺的排隊系統，可驗證到達車數不服從泊松分布，服

23、務時間也不服從指數分布（這是定長服務時間）。隨機模擬法首先要求事件能按歷史的概率分布規(guī)律出現。模擬時產生的隨機數與事件的對應關系如下：到達車數概 率累積概率對應的隨機數012345230.303010050.0223538393980000.230.230.530.530.830.830.930.930.980.981.001.00我們用a1表示產生的隨機數，a2表示到達的車數，a3表示需要卸貨車數，a4表示卸貨車數，a5表示推遲卸貨車數。編寫程序如下：clearrand(state,sum(100*clock);n=50000;m=2a1=rand(n,1);a2=a1; %a2初始化a2(

24、find(a10.23)=0;a2(find(0.23=a1&a10.53)=1;a2(find(0.53=a1&a10.83)=2;a2(find(0.83=a1&a10.93),1)=3;a2(find(0.93=a1&a1=0.98)=5;a3=zeros(n,1);a4=zeros(n,1);a5=zeros(n,1);a3(1)=a2(1);if a3(1)=m a4(1)=a3(1);a5(1)=0;else a4(1)=m;a5(1)=a2(1)-m;endfor i=2:n a3(i)=a2(i)+a5(i-1); if a3(i)=m a4(i)=a3(i);a5(i)=0;

25、 else a4(i)=m;a5(i)=a3(i)-m; end enda=a1,a2,a3,a4,a5;sum(a)/n例2 銀行(ynhng)計劃安置自動取款機，已知型機的價格(jig)是型機的2倍，而型機的性能(xngnng)平均服務率也是型機的2倍，問應該購置1臺型機還是2臺型機。為了通過模擬回答這類問題，作如下具體假設，顧客平均每分鐘到達1位，型機的平均服務時間為0.9，型機為1.8分鐘，顧客到達間隔和服務時間都服從指數分布，2臺型機采取模型（排一隊），用前100名顧客（第1位顧客到達時取款機前為空）的平均等待時間為指標，對型機和型機分別作1000次模擬，進行比較。理論上已經得到，型

26、機和型機前100名顧客的平均等待時間分別為，即型機優(yōu)。對于模型，記第位顧客的到達時刻為，離開時刻為，等待時間為，它們很容易根據已有的到達間隔和服務時間按照以下的遞推關系得到（，設已知）：，在模擬型機時，我們用cspan表示到達間隔時間，sspan表示服務時間，ctime表示到達時間，gtime表示離開時間，wtime表示等待時間。我們總共模擬了次，每次個顧客。程序如下：ticrand(state,sum(100*clock);n=100;m=1000;mu1=1;mu2=0.9;for j=1:m cspan=exprnd(mu1,1,n);sspan=exprnd(mu2,1,n); cti

27、me(1)=cspan(1); gtime(1)=ctime(1)+sspan(1); wtime(1)=0; for i=2:n ctime(i)=ctime(i-1)+cspan(i); gtime(i)=max(ctime(i),gtime(i-1)+sspan(i); wtime(i)=max(0,gtime(i-1)-ctime(i); end result1(j)=sum(wtime)/n;endresult_1=sum(result1)/mtoc類似(li s)地，模擬型機的程序(chngx)如下：ticrand(state,sum(100*clock);n=100;m=1000

28、;mu1=1;mu2=1.8;for j=1:m cspan=exprnd(mu1,1,n);sspan=exprnd(mu2,1,n); ctime(1)=cspan(1);ctime(2)=ctime(1)+cspan(2); gtime(1:2)=ctime(1:2)+sspan(1:2); wtime(1:2)=0;flag=gtime(1:2); for i=3:n ctime(i)=ctime(i-1)+cspan(i); gtime(i)=max(ctime(i),min(flag)+sspan(i); wtime(i)=max(0,min(flag)-ctime(i); flag=max(flag),gtime(i); end result2(j)=sum(wtime)/n;endresult_2=sum(result2)/mto