第十二章

排隊論(QueuingTheory)排隊論的基本概念到達間隔的分布和服務時間的分布排隊系統的分析排隊論(QueuingTheory)，又稱隨機服務系統理論(RandomServiceSystemTheory),是一門研究擁擠現象(排隊、等待)的科學。具體地說，它是在研究各種排隊系統概率規律性的基礎上，解決相應排隊系統的最優設計和最優控制問題。排隊論是1909年由丹麥工程師愛爾朗(A.K．Erlang)在研究電話系統時創立的，幾十年來排隊論的應用領域越來越廣泛，理論也日漸完善。特別是自二十世紀60年代以來，由于計算機的飛速發展，更為排隊論的應用開拓了寬闊的前景。第一節基本概念一、排隊系統的一般表示例1、各個顧客由顧客源出發，到達服務機構前排隊等候服務，服務完了后就離開。排隊結構指隊列的數目和排列方式排隊規則和服務規則是說明顧客在排隊系統中按怎樣的規則、次序接受服務的。顧客源排隊結構排隊規則服務規則服務機構離去顧客到來排隊系統排隊是我們在日常生活和生產中經常遇到的現象:上、下班搭乘公共汽車；顧客到商店購買物品；病員到醫院看病；旅客到售票處購買車票；學生去食堂就餐等就常常出現排隊和等待現象。排隊的不一定是人，也可以是物：通訊衛星與地面若干待傳遞的信息；生產線上的原料、半成品等待加工；因故障停止運轉的機器等待工人修理；碼頭的船只等待裝卸貨物；要降落的飛機因跑道不空而在空中盤旋等等。一般排隊的過程

顧客到達隊列（排隊規則）服務臺（接受服務）顧客離去二、排隊系統的組成和特征輸入即指顧客到達排隊系統，可能有以下不同情況。1、輸入過程

（1）顧客源的組成有限的無限的（2）顧客到來的方式

一個一個的成批的（3）顧客相繼到達的間隔時間確定型的隨機型的（4）顧客的到來相互獨立的關聯的（5）輸入過程平穩的，或稱對時間是齊次的非平穩的2、排隊規則顧客在排隊系統中按怎樣的規則、次序接受服務的。（1）顧客到達時，所有服務臺被占用隨即離去的稱為即時制（損失制）排隊等候稱為等待制先到先服務后到先服務隨機服務有優先權（2）從隊列占用空間有限的無限的（3）從隊列的數量單列多列3、服務機構（1）服務員數量沒有一個或多個（2）多服務臺時單隊—單服務臺單隊—多服務臺（并列）多隊—多服務臺（并列）多服務臺（串列）（3）服務方式對單個顧客進行對成批顧客進行（4）服務時間確定型隨機型（5）服務時間的分布我們總假定是平穩的，即分布的期望值、方差等參數都不受時間的影響12312多服務臺混合一個排隊系統的特征可以用六個參數表示，形式為：

[X/Y/Z]/[A/B/C]其中X––顧客到達的概率分布，可取M、D、Ek等；Y––服務時間的概率分布，可取M、D、Ek等；Z––服務臺個數，取正整數；A––排隊系統的最大容量，可取正整數或；B––顧客源的最大容量，可取正整數或；C––排隊規則，可取FCFS、LCFS等。三、排隊模型的分類(條件參數)表示相繼到達間隔時間和服務時間的各種分布的符號:M—負指數分布D—確定型Ek—k階愛爾朗分布GI—一般相互獨立的時間間隔的分布G—一般服務時間的分布例如：某排隊問題為

M/M/s/∞/∞/FCFS

則表示顧客到達間隔時間為負指數分布(泊松流)；服務時間為負指數分布；有s(s＞1)個服務臺；系統等待空間容量無限(等待制)；顧客源無限，采用先到先服務規則。可簡記為： M/M/s

四、排隊系統的參數(分析結果)1、隊長（Ls）指在系統中的顧客數,期望值2、排隊長（Lq）指系統中排隊等候服務的顧客數3、逗留時間（Ws）指一個顧客在系統中的停留時間4、等待時間（Wq）指一個顧客在系統中排隊等待的時間Ls=Lq+正被服務的顧客數Ws=Wq+服務時間這四項主要性能指標(又稱主要工作指標)的值越小，說明系統排隊越少，等待時間越少，因而系統性能越好。顯然，它們是顧客與服務系統的管理者都很關注的。5、忙期指從顧客到達空閑服務機構起到服務機構再次空閑止這段時間長度，即服務機構連續繁忙的時間長度。6、系統的狀態n：指系統中的顧客數。8、穩定狀態：t→時，t=0時的系統不穩定狀態將消失，系統的狀態概率分布不再隨時間變化，即

limPn(t)→Pn。7、系統狀態的概率Pn(t)：指時刻t、系統狀態為n的概率。一般為關于t的微分方程、關于n的差分方程。9、其他常用數量指標s ——系統中并聯服務臺的數目； ——平均到達率；1/ ——平均到達間隔。 ——平均服務率；1/ ——平均服務時間。 ——服務強度，每個服務臺單位時間內的平均服務時間；一般有s

；當s=1時：對于損失制和混合制的排隊系統，顧客在到達服務系統時，若系統容量已滿，則自行消失。這就是說，到達的顧客不一定全部進入系統，為此引入：e——有效平均到達率,即每單位時間實際進入系統的平均顧客數（期望值），不同于.

對于等待制的排隊系統，

e

＝一、經驗分布例2某服務機構單服務臺，先到先服務，對41顧客記錄到達時刻和服務時間s（單位：分鐘）如下表，表中第1號顧客到達時刻為0。全部服務時間為127（分鐘）。第二節到達間隔的分布和服務時間的分布(1)i(2)τi(3)si(4)ti(5)wi(1)i(2)τi(3)si(4)ti(5)wi(1)i(2)τi(3)si(4)ti(5)wi10520512271093612022743619435103827036156722346114552041191282631051247423(1)i(2)

τi(3)si(4)ti(5)wi(1)i(2)

τi(3)si(4)ti(5)wi(1)i(2)

τi(3)si(4)ti(5)wi134913523866223311744714522932488546341212671561110259213735127123166223026953653612961217651502710124237130337187032028105210381335271972481291061313913524102080310301092504013943821812223111412041142119228333232116810各欄意義：（1）i，顧客編號；（2）τi：顧客i到達的時刻；（3）si：服務時間；以上三欄是原始數據；（4）ti

：到達間隔；（5）wi：排隊等待時間；這倆欄是可以通過計算得到的到達間隔分布表服務時間分布表到達間隔（分鐘）次數12345678910以上11122368106合計40服務時間（分鐘）次數123456789以上11214571010合計41平均間隔時間=142/40=3.55(分鐘/人)平均到達率=41/142=0.28(人/分鐘)平均服務率=41/127=0.32(人/分鐘)平均服務時間=127/41=3.12(分鐘/人)輸入過程是描述各種類型的顧客以怎樣的規律到達系統，一般用相繼兩顧客到達時間間隔來描述系統輸入特征。主要輸入過程有：定長輸入，泊松輸入…1．定長輸入是指顧客有規則地等距到達，每隔時間到達一個顧客。這時相繼顧客到達間隔的分布函數F(t)為定長輸入例如，生產自動線上產品從傳送帶上進入包裝箱就是這種情況．二、泊松(Poisson)輸入泊松(Poisson)輸入，即泊松流，又稱最簡單流。設隨機變量X服從Poisson分布，則概率密度如果一個隨機變量，概率分布與時間t有關，則稱這個隨機變量為一隨機過程，排隊系統中顧客到達的個數就是一個隨機過程。

(1)Poisson流的定義滿足以下四個條件的輸入流稱為Poisson流(Poisson過程)①平穩性：增量與時間起點無關在時間區間[t,t+t)內到達k個顧客的概率與t無關，只與t有關。記為pk(t）。②無后效性不相交的時間區間內到達的顧客數互相獨立。③稀有性：瞬時內只可能有1個顧客到達設在[t,t+t）內到達多于一個顧客的概率為q(t），則q(t)=o(t).即④有限性任意有限個區間內到達有限個顧客的概率等于1。即區間情況[0,t)[t,t+Δt)[0,t+Δt)個數概率個數概率個數概率(A)nPn(t)01-λΔt+o(Δt)nPn(t)(1-λΔt+o(Δt))(B)n-1Pn-1(t)1λΔt+o(Δt)nPn-1(t)(λΔt+o(Δt))(C)n-2Pn-2(t)2o(Δt)no(Δt)n-3Pn-3(t)3n0P0(t)nn簡記Pn(0,t)=Pn(t)。表示[0,t)時間內到達n個顧客的概率，即輸入。對于區間[0,t+Δt)，可分成兩個互不重疊的區間[0,t)和[t,t+Δt)。設在區間[0,t+Δt)上，到達總數為n，會出現A,B,C三種情況：區間[0,t+Δt)內到達n個顧客應是表中三種互不相容的情況之一，所以概率Pn(t+Δt)應是三個概率之和，即：

Pn（t+Δt）=Pn（t）（1-λΔt

）+Pn-1（t）λΔt+o（Δt）[Pn（t+Δt）-Pn（t）]/Δt=－λPn（t）+λPn-1（t）+[o（Δt）]/Δt

令Δt0dPn（t）/dt=-λPn（t）+λPn-1（t）Pn（0）=0（n1）dP0（t）/dt=-λP0（t）P0（0）=1（n=0）求出

整理后得：由此可見，泊松輸入，即在t時段內到達n個顧客的概率服從參數為λ的泊松分布。注意：我們要把泊松輸入同前面提到的系統狀態Pn區分開參數的實際意義

設N(t)表示在[0，t）內到達的顧客數的期望值由此得到即的實際意義為單位時間內到達的顧客數的期望值，或稱平均到達速率。泊松分布由概率論可知，如果隨機變量X服從參數為λ泊松分布，則其分布函數為（注：不是很重要）

密度函數為

X的期望值為

X的方差為由概率論可知，如果隨機變量T服從負指數分布，則其分布函數為

密度函數為

T的期望值為

T的方差為三、負指數分布（指數分布）Poisson流與負指數分布之間的關系定理在排隊系統中，如果到達的顧客數服從以為參數的Poisson分布，則顧客相繼到達的時間間隔服從以為參數的負指數分布。證明：設Poisson流中顧客相繼到達的時間間隔為隨機變量T，并且在時刻0有一個顧客到達，則下一個顧客將在時刻T到達。T的分布函數為其中p[T>t]表示在[0，t）內沒有顧客到達的概率，因此

所以，T的分布函數為

T的密度函數為

因此，顧客相繼到達的時間間隔服從以為參數的負指數分布。可以看出，“到達的顧客數是一個以為參數的Poisson流”與“顧客相繼到達的時間間隔服從以為參數的負指數分布”兩個事實是等價的。顧客相繼到達的時間間隔服從以為參數的負指數分布服務時間服從負指數分布，概率密度為參數同樣具有兩層含義：單位時間內服務的顧客人數的期望值，或稱平均服務率。

由于的均值為1/

，即平均對每位顧客的服務時間為1/

.服務時間服從以為參數的負指數分布負指數分布具有無記憶性定理設對顧客的服務時間X服從參數為的負指數分布。在對某一個顧客的服務已經進行了一定時間的條件下，這個顧客的剩余的服務時間仍服從以為參數的負指數分布。證明：設服務已經進行的時間為，則剩余時間不少于t的條件概率為

由此看出，服務剩余時間的分布獨立與已經服務過的時間，并且與原來的服務時間的分布相同。設v1，v2，…，vk是k個互相獨立的，具有相同參數的負指數分布隨機變量，則隨機變量

服從k階Erlang分布，S的密度函數為四、k階愛爾朗(Erlang)分布期望值為 方差為注意：①當k=1時，愛爾朗分布就是負指數分布，是完全隨機的；②當k>=30時，近似于正態分布；③一般k階愛爾朗分布可看成是完全隨機與完全確定的中間型，有更廣泛的適應性。一、M/M/1模型1、假設（1）顧客到達的間隔時間滿足參數為λ的負指數分布（2）服務時間滿足參數為μ的負指數分布（λ<μ）（3）服務機構是單服務臺（4）顧客源是無限的，顧客到來相互獨立（5）單隊排列，且對隊長沒有限制第三節單服務臺負指數分布排隊系統的分析求： （1）系統狀態概率Pn； （2）系統運行指標Ls，Lq，Ws，Wq。2、Pn的計算情況在時刻t顧客數在區間（t，t+Δt）到達離去在時刻t+Δt顧客數ABCDnn+1n-1nnnnn注：表示發生（1個），表示沒有發生。整理后得：將Pn(t)移到左邊，兩邊同除以t，得到令t0時，得到關于Pn(t)的微分方程：當n=0，則只有表中A，B兩種情況，即同理，求得：Pn(t)的穩態解Pn如果能夠求解由無限個方程組成的差分微分方程組，就可以得到Pn(t)的瞬態解，即系統中有n個顧客的概率隨時間變化的解析表達式，但這是十分困難的。如果假定當時間足夠長，系統有n個顧客的概率Pn(t)會趨于某個穩定值，即當t時系統趨于概率穩態，這個穩態解是可以求出來的。設當t時，Pn(t)趨于一個常數，這時Pn(t)與t無關，可記為Pn，則Pn關于t的導數為0。這時(1)式和(2)式可得狀態轉移圖以系統中的顧客數0，1，2，…，n-1，n，n+1，…作為系統的狀態，(3)和(4)表示系統位于某一狀態的概率僅與其相鄰狀態的概率以及從相鄰狀態轉移到該狀態的概率有關。系統狀態（n）隨時間變化的過程是生滅過程的一個特殊情況，(3)和(4)關于Pn的差分方程，可以用狀態轉移圖來表示各狀態間的轉移關系，并能求解。0n123λλλλλμμμμμ由(3)和(4)可以遞推求解P1，P2，…，Pn，…。由(3)得到

(5)由(4)得到

(6)將(5)代入(6)

用遞推方法可以得到

(7)由得到令稱為服務強度，則當時，級數收斂，這時有

(8)代入(7)，得到

(9)(8)和(9)可以統一表示為

(10)當1時，級數發散，不存在穩態解(隊列將會排至無限遠），因此，排隊系統處于概率穩態的條件是注：是系統的服務強度，即是忙期，(1-)=P0就是系統空閑時間。例1 高速公路入口收費處設有一個收費通道，汽車到達服從Poisson分布，平均到達速率為100輛／小時，收費時間服從負指數分布，平均收費時間為15秒／輛。求1、收費處空閑的概率；2、收費處忙的概率；3、系統中分別有1，2，3輛車的概率。解：根據題意,=100輛/小時，=15秒=240（小時/輛）,即＝240（輛/小時）。因此系統空閑的概率為：系統忙的概率為：系統中有1輛車的概率為：系統中有2輛車的概率為：系統中有3輛車的概率為：

3、M/M/1參數計算（1）系統中平均顧客數隊長（Ls）（2）隊列中等待的平均顧客數（Lq）即 Lq=Ls（3）顧客逗留時間（Ws）（4）隊列中顧客等待時間（Wq）將以上結果總結如下：對于M/M/1///FCFS系統，系統中由k個顧客的概率為：

系統中的平均顧客數為：隊列的平均長度為：顧客在系統中的平均逗留時間為：顧客在隊列中的平均等待時間為： Little公式一般化

Little公式的條件:排隊系統能夠進入統計平衡狀態；服務臺的忙期與閑期交替出現；系統中任一顧客不會永遠等待，系統也不會永遠無顧客到達。例3100個工作小時內每小時來就診的病人數n出現次數如下100個完成手術的病例所用時間v（小時）出現的次數如下到達的病人數n出現次數fn0123456以上102829161061合計1002517965為病人完成手術時間v（小時）出現次數fv0.0-0.20.2-0.40.4-0.60.6-0.80.8-1.01.0-1.21.2以上380合計100假定系統最大容量為N，單服務臺情形，排隊等待的顧客最多為N-1，下面只考慮穩態情形：二、M/M/1/N/模型顧客到達因隊列滿而離去進入隊列接受服務服務完畢后離去0N-112N-2λλλλμμμμN0N-112N-2λλλλμμμμN根據上式我們可以推導出系統的各項指標：有效到達率：例4單人理發館有六個椅子接待客人。當6個椅子都坐滿時，后來的顧客不進店就離開。顧客平均到達率為3人/小時，理發需時平均15分鐘。則：

N=7為系統中最大的顧客數，λ=3人/小時，μ=4人/小時（1）求某顧客一到達就能理發的概率。（2）求需要等待的顧客數的期望值。（3）求有效到達率。（4）求一顧客在理發館內逗留的時間。（5）在可能到達的顧客中有百分之幾不等待就離開。機器故障問題：設共有m臺機器，機器故障停機表示到達，待修機器形成隊列，修理工是服務員。顧客總體雖然只有m個，但每個顧客服務后仍回到總體，仍然可以到來。三、顧客源有限的情形(M/M/1//m)λ的含義發生改變表示全體顧客的平均到達率表示每個顧客的平均到達率服務臺需要服務服務完畢隊列系統外的平均顧客數說明：進入率與狀態有關若m=5,n=3;如下圖所示：系統中已經有兩人丁和戊進入的為甲、乙或丙，所以為：λ

e=3λ由此列出平衡方程：狀態概率0m-112m-2mλ(m-1)λ2λλμμμμmμμ(m-2)λ3λ根據上式我們可以推導出系統的各項指標：在機器故障問題中Ls就是平均故障臺數，而例5某車間有5臺機器，每臺機器的連續運轉時間服從負指數分布，平均連續運轉時間15分鐘，有一個修理工，每次修理時間服從負指數分布，平均每次12分鐘。求（1）修理工空閑的概率；（2）五臺機器都出故障的概率；（3）出故障的平均臺數；（4）等待修理的臺數；（5）平均停工時間；（6）平均等待時間；（7）評價這些結果。（7）機器停工時間過長，修理工幾乎沒有空閑時間，應當提高服務率減少修理時間或增加修理工人。第四節多服務臺指數分布排隊系統的分析一、M/M/c0N12N-1λλλλμcμ2μcμcc-1λλcμcμc+13μλ(c-1)μλcμcμλλ用遞推法解上述差分方程，可求得狀態概率。根據上式我們可以推導出系統的各項指標：例6某售票所有三個窗口，顧客到達服從Passion過程，平均到達率每分鐘λ=0.9(人),服務(售票)時間服從負指數分布,平均服務率每分鐘μ=0.4(人).窗口(1)μ=0.4窗口(2)μ=0.4窗口(3)μ=0.4λ=0.9（1）整個售票所空閑的概率（2）平均隊長（3）平均等待時間和逗留時間（4）顧客到達后必須等待（即系統中顧客數已有3人）的概率二、M/M/c型系統和c個M/M/1系統的比較上例中，排隊方式不變，但顧客到達后在每個窗口前各排一隊，且進入隊列后堅持不換，這就形成3個隊列，如下圖二每個隊列平均到達率為λ=λ=λ=0.9/3=0.3（每分鐘），這樣原來的系統就變成3個M/M/1型的子系統。窗口(1)μ=0.4窗口(2)μ=0.4窗口(3)μ=0.4λ=0.9λ=0.3λ=0.3λ=0.3現按M/M/1型解決這個問題，并與上表比較：模型指標服務臺空閑的概率顧客必須等待的概率平均隊列平均隊長平均逗留時間平均等待時間（1）M/M/3型（2）M/M/1型0.0748P(n3)=0.571.703.954.39(分鐘)1.89(分鐘)0.25(每個子系統)0.752.25(每個子系統)9.00(整個系統)10(分鐘)7.5(分鐘)從表中各指標的對比可以看出單隊比三隊有顯著的優越性三、系統容量有限定的M/M/c/N/模型因隊列滿而離去0N-112N-2λλλλμcμ2μcμNcc-1λλcμcμc+13μλ(c-1)μλcμcμλλ系統的狀態概率和運行指標如下:四、顧客源為有限的M/M/c//m模型顧客到達修理速率μ發生故障等待修理的機器修理速率μ修理速率μ正在修理的機器到達速率(m-n)λ修理速率sμ運行的機器數m-n0m-112m-2mλ(m-1)λ2λλμcμ2μcμmcc-1(m-c+1)λcμ穩態概率方程求得其中：例7設有兩個修理工人，負責5臺機器的正常運行，每臺機器平均損壞的概率為每運轉一小時1次，兩個工人能以相同的平均修復率4（次/小時）修好機器。求（1）等待修理的機器平均數（2）需要修理的機器平均數（3）有效損壞數（4）等待修理時間（5）停工時間(1)Lq=P3+2P4+3P5=0.118(3)λe=1×(5-1.094)=3.906(4)Wq=0.118/3.906=0.03小時

(5)Ws=1.094/3.906=0.28小時第五節一般服務時間M/G/1模型一、M/G/1即：ρ=λE[T]Pollaczek-K