運籌學：第七章 排隊論

第七章排隊論第一節(jié)排隊論的基本概念第二節(jié)生滅過程第三節(jié)常用的排隊模型（M/M/1)第四節(jié)其他排隊模型及優(yōu)化第五節(jié)Excel在排隊系統(tǒng)中的應用案例：電話系統(tǒng)排隊問題一、排隊論及排隊系統(tǒng)在日常生活和工作中，會遭遇到許多排隊問題，如在火車站排隊買票、在醫(yī)院排隊掛號、排隊候診、在企業(yè)的生產過程中半成品等待再加工。進入排隊系統(tǒng)的對象被統(tǒng)稱為達到的顧客（人或物）；這些顧客進入排隊系統(tǒng)的目的被統(tǒng)稱為服務；顧客將在排隊系統(tǒng)中按照系統(tǒng)的規(guī)則進行有形或者無形的排隊。第一節(jié)排隊論的基本概念

一般的排隊過程可以這樣描述：顧客由顧客源出發(fā)，到達服務機構（服務臺、服務員）前，按排隊規(guī)則排隊等待接受服務，服務機構按服務規(guī)則給顧客服務，顧客接受完服務后就離開。

盡管排隊系統(tǒng)是多種多樣的，但所有的排隊系統(tǒng)都是由輸入過程、排隊及排隊規(guī)則、服務機構及服務規(guī)則三個基本部分組成的。（1）輸入過程：描述顧客來源以及顧客到達排隊系統(tǒng)的規(guī)律。（數(shù)量有限或無限；單個或成批；到達時間是否獨立；分布是確定型或隨機型，等等）

（2）排隊及排隊規(guī)則：描述顧客排隊等待的隊列和接受服務的次序。（損失制---排隊空間為零的系統(tǒng)，顧客不排隊，流失；等待制---顧客排隊，按以下規(guī)則接受服務；混合制---顧客可排隊，可流失。）（3）服務機構及服務規(guī)則：指服務機構的服務設施的個數(shù)、排列方式及服務方式。（服務臺數(shù)量；服務臺排列；服務方式；服務時間。）

常見的幾種排隊系統(tǒng)的結構12ss單隊-單臺系統(tǒng)單隊-多臺（并聯(lián)）系統(tǒng)單隊-多臺（串聯(lián)）系統(tǒng)1多隊-多臺（并聯(lián)）系統(tǒng)多隊-多臺（混聯(lián)、網絡）系統(tǒng)112s

實例、大學生到學生食堂排隊就餐。涉及到的問題和需要解決的問題如下:（1）總共有多少學生要到食堂就餐?（2）目前食堂總共有多少個服務窗口？（3）學生排隊就餐是按照什么規(guī)則？（4）學生在隊列中的平均排隊時間？（5）隊列中的學生數(shù)量滿足什么分布？（6）學生的排隊等待時間滿足什么分布？（7）學生心理上的最大等待時間是多少？（8）要確保只有5％內的學生的等待時間不超過其最大心理等待時間，目前的服務窗口是否夠用？（9）如果已知增加一個服務窗口的成本，流失一個學生顧客的損失，現(xiàn)有條件下，設置多少個服務窗口最合算？……1、輸入過程的模型輸入過程是用來表述顧客到達排隊系統(tǒng)的背景及規(guī)律；根據(jù)顧客來源的數(shù)量不同可以分為有限顧客源和無限顧客源；根據(jù)顧客達到排隊系統(tǒng)的方式的不同可以分為單個到達和成批到達。輸入過程中最重要的表述是顧客相繼到達時間間隔，Tn表示第n個顧客到達時刻，Xn=Tn-Tn-1表示第n個顧客與其前一個顧客的時間間隔，一般地，假設｛Xn｝是獨立的同分布的。二、排隊論模型顧客相繼到達時間間隔Xn的分布形式主要有以下幾種：①定長輸入（D）②最簡單流輸入（M）③埃爾朗輸入（Ek）④一般獨立輸入（G）⑤成批到達的輸入2、排隊規(guī)則的模型排隊規(guī)則模型主要有三種：①損失制，即顧客到達時，若所有服務臺均被占，該顧客就自動消失。（如停車場，某些電話呼叫系統(tǒng)）②等待制，即顧客到達時，若所有服務臺均被占，顧客就排隊等待服務。（如銀行、超市收銀臺、餐廳等）③混合制，系統(tǒng)排隊空間有限制的情形，若限制隊長為N，則在顧客到達時的隊長小于N

時，顧客就排入隊伍；當其等于N時，顧客就離去。（如醫(yī)院門診人數(shù)）當進行排隊時，還存在著不同的排隊規(guī)則：①先到先服務（FCFS）：如餐廳、收銀臺大多數(shù)排隊系統(tǒng)等②后到先服務（LCFS）：如貨輪上等待卸船的貨物③隨機服務（SIRO）：如等待抽檢的產品④優(yōu)先權服務（PS）：如醫(yī)院的急診病人或銀行的VIP客戶3、服務機構的模型在服務設施方面，服務臺的個數(shù)可以是一個或幾個；在其組織形式上，可以是并聯(lián)的或串聯(lián)的或循環(huán)的；在服務方式上，可以是單個服務的或成批服務的；在服務時間上，是與輸入過程相類似的各種分布。

輸入過程的模型+排隊規(guī)則模型+服務機構的模型=排隊論模型隨機服務系統(tǒng)分類的記號X/Y/n/A/B/C，其中X代表輸入模型，Y

代表服務機構模型，n代表服務臺的數(shù)目，A代表系統(tǒng)容量，B代表顧客源的數(shù)量，C代表排隊規(guī)則。三、排隊模型中的主要參數(shù)1、隊長和排隊長：隊長是指系統(tǒng)中顧客總數(shù)（包括排隊等待和正在接受服務的人數(shù)），記為N(t)，它的期望值為平均隊長，記為L。隊長是排隊系統(tǒng)中顧客的平均數(shù)（期望值），它是正在被服務的顧客和等待接受服務的顧客總數(shù)的期望值。反映了排隊系統(tǒng)中的一種總規(guī)模。排隊長是指排隊等待的顧客數(shù)，記為Nq(t)，其期望值為平均排隊長，記為Lq。L=Lq+正在服務的人數(shù)2、等待時間和逗留時間：等待時間是指從顧客到達時間算起到他開始接受服務為止的這段時間，記為Tq(t)，它的期望值為平均等待時間，記為Wq。逗留時間是指顧客到達時刻算起到他接受服務完畢為止的這段時間，記為T(t)，它的期望值為平均逗留時間，記為W。一般地有：逗留時間=等待時間+服務時間。3、忙期和閑期：忙期是指服務臺連續(xù)繁忙的時間，即顧客從到達空閑服務臺算起到服務臺再次變?yōu)榭臻e時止的這段時間。這是服務臺最關心數(shù)量指標，它直接關系到服務員的工作強度。閑期是指服務臺連續(xù)保持空閑的時間長度。顯然在排隊系統(tǒng)中忙期與閑期是交替出現(xiàn)的。

排隊系統(tǒng)優(yōu)化問題的研究

研究排隊系統(tǒng)的目的就是通過對該系統(tǒng)概率規(guī)律的研究，實現(xiàn)系統(tǒng)的優(yōu)化。系統(tǒng)的優(yōu)化包括最優(yōu)設計和最優(yōu)運營問題。前者屬于靜態(tài)問題，它是在輸入和服務參數(shù)給定的情況下，確定系統(tǒng)的設計參數(shù)，以使服務設施達到最大效益或者服務機構實現(xiàn)最為經濟。后者屬于動態(tài)問題，它是指對于一個給定的系統(tǒng)，在系統(tǒng)運行的參數(shù)可以隨著時間或狀態(tài)變化的情況下，考慮如何運營使某個目標函數(shù)達到最優(yōu)?？傎M用=服務費用+等待費用隨著服務水平提高，服務費用增加而等待費用減少！

優(yōu)化：總費用最少！費用總費用服務費用等待費用服務水平0第二節(jié)生滅過程

1、馬爾可夫過程簡介

隨機過程：一連串隨機事件動態(tài)關系的定量描述。排隊系統(tǒng)中的顧客總數(shù)記為N(t)。這里的N(t)首先它是一個隨機變量，當時間變化到t=t1時刻時，N(t1)又是一個新的隨機變量了，把這樣的隨機變量放在一起，記為｛N(t),t≥0｝，就是一個隨機過程。

這里t的取值若規(guī)定是t0,t1,…,tn…這樣離散的時間點，則為離散時間的隨機過程；若t的取值是連續(xù)的，則為連續(xù)時間的隨機過程。過程或（系統(tǒng)）在時刻t0所處的狀態(tài)為已知的條件下，過程在時刻t>t0所處狀態(tài)的條件分布，與過程在時刻t0之前處的狀態(tài)無關的特性稱為馬爾可夫性或無后效性。即：過程“將來”的情況與過程“過去”的情況是無關的。具有馬爾可夫性的隨機過程稱為馬爾可夫過程。此隨機過程的t的取值若為離散的時間點t0,t1,…,tn…，又稱為馬爾可夫鏈。記過程或（系統(tǒng)）在時刻ti所處的狀態(tài)為u(ti)，馬爾可夫的條件即為：P(u(tn+1)|u(t0),u(t1),…,u(tn))=P(u(tn+1)|u(tn))即：系統(tǒng)在tn+1時刻的狀態(tài)只與系統(tǒng)在tn時刻的狀態(tài)有關！對于排隊系統(tǒng)來說，系統(tǒng)在時刻ti所處的狀態(tài)u(ti)是指N(tj)=ntj，為方便起見，把離散的時間點t0,t1,…,tn…簡化為0,1,…,n…，這樣馬爾可夫的條件也就變成：P(Nn+1=in+1|N0=i0,N1=i1,…,Nn=in)=P(Nn+1=in+1|Nn=in)。進一步假設，對所有狀態(tài)，若P(Nn+1=j|Nn=i)與t無關，可記P(Nn+1=j|Nn=i)=Pij，為馬爾可夫鏈的狀態(tài)轉移概率，同時由于假設了轉移概率與t無關，又可稱為平穩(wěn)的馬爾可夫鏈。記馬爾可夫鏈的初始狀態(tài)概率為qi=P(N0=i)若把馬爾可夫鏈的所有狀態(tài)記為1,2,…,s，則q=(q1,…,qs)為馬爾可夫鏈的初始狀態(tài)概率分布。狀態(tài)轉移概率可用矩陣表示為：現(xiàn)在將矩陣P作冪運算，對于Pn來說，其第i行第j列元素記為Pij(n)，則Pij(n)=P(Nn=j|No=i)表示從初始狀態(tài)的i，通過一步步轉移，到第n步轉移成了狀態(tài)j。Pij滿足：1、0≤pij≤12、Σpij=1，對j求和例7.1（飲料的市場份額）假設某種飲料在某市場只有有兩個品牌A可口可樂、B百事可樂在競爭。假定狀態(tài)1為顧客最近一次選購了A品牌，狀態(tài)2為顧客最近一次選擇了B品牌。每一次的選擇其狀態(tài)轉移概率不變，為如下狀態(tài)轉移矩陣（1）當已知顧客初始選擇了A品牌，此后的第三次再選購飲料時選擇B品牌的概率；（2）若初始兩個品牌的選擇概率為（0.5，0.5），則三次轉移后兩個品牌的選擇概率。解：所以當已知顧客初始選擇了A品牌，此后的第三次再選購飲料時選擇B品牌的概率0.35。當初始兩個品牌的選擇概率（市場占有率）為（0.5，0.5）時，即（q1，q2）=（0.5，0.5），三次轉移后的選擇概率（市場占有率）為：不斷重復計算，可得出市場占有率將會近似為（0.6,0.4），此即為穩(wěn)定狀態(tài)下的市場占有率。穩(wěn)定狀態(tài)下的市場占有率二、生滅過程的模型定義：設｛N(t),t≥0｝為一個隨機過程，并且滿足：當N(t)=n時，從時刻t到下一個顧客到達的時間間隔服從參數(shù)為λn的負指數(shù)分布；從時刻t到下一個顧客離開的時間間隔服從參數(shù)為μn的負指數(shù)分布；同一時刻只有一個顧客到達或離開。則稱｛N(t),t≥0｝為一個生滅過程。記Pn(t)=P(N(t)=n)。即時刻t顧客為n人的概率在負指數(shù)分布中可以假定：從[t,t+⊿t]內，有一個顧客到達的概率為λn⊿t+o(⊿t)，有一個顧客離開的概率為μn⊿t+o(⊿t)，多于一個顧客達到或離開的概率為o(⊿t)。在時刻t+⊿t時，N（t+⊿t）=n的概率用狀態(tài)轉移來理解，可以表述為如下表達式：Pn(t+⊿t)=Pn-1(t)*(λn-1⊿t+o(⊿t))+Pn+1(t)*(μn⊿t+o(⊿t))+Pn(t)*(λn⊿t+o(⊿t))*(μn⊿t+o(⊿t))+Pn(t)*(1-λn⊿t+o(⊿t))*(1-μn⊿t+o(⊿t))整理后可得：Pn(t+⊿t)-Pn(t)=[Pn-1(t)*λn-1+Pn+1(t)*μn

–Pn(t)*λn-Pn(t)*μn]⊿t+o(⊿t))假定生滅過程是一個平穩(wěn)過程，即系統(tǒng)達到平穩(wěn)時，Pn(t)與t無關，或者說P’n(t)=0，此時記Pn(t)為pn?；喺恚篜n(t+⊿t)-Pn(t)=[Pn-1(t)*λn-1+Pn+1(t)*μn

-Pn(t)*λn-Pn(t)*μn]⊿t+o(⊿t))兩邊除⊿t，并令其趨于0，得：pn-1*λn-1+pn+1*μn=pn*λn+pn*μn

pn-1*λn-1+pn+1*μn=pn*λn+pn*μn

記

則求解結果可以描述為：

第三節(jié)常用的排隊模型

一、M/M/1模型M/M/1模型也就是M/M/1/∞/∞/FCFS，是指顧客到達的時間間隔服從參數(shù)為λ的負指數(shù)分布；服務時間服從參數(shù)為μ的負指數(shù)分布；只有一個服務臺；并且首先假定系統(tǒng)空間是無限的；顧客源是無限的；排隊規(guī)則是先來先服務。這也是排隊系統(tǒng)中最簡單的情況！λn=λ，μn=μ，穩(wěn)態(tài)概率為：

令：

得：當0<ρ<1時M/M/1模型有穩(wěn)態(tài)概率

；當ρ≥1時，等比級數(shù)不收斂，排隊系統(tǒng)不存在穩(wěn)定狀態(tài)。定理（Little公式）：對于處于穩(wěn)定狀態(tài)的排隊系統(tǒng)，下列公式成立：定理（Little公式）：對于處于穩(wěn)定狀態(tài)的排隊系統(tǒng)，下列公式成立：利用Little公式，可以輕松地計算出排隊系統(tǒng)的時間參數(shù)。例7.2（M/M/1模型）某醫(yī)院急癥室晚上有一個醫(yī)生值班，病人的到達時間間隔服從負指數(shù)分布，平均每小時來2個病人，醫(yī)生治療病人的時間也服從負指數(shù)分布，平均治療時間20分鐘（即平均每小時治療3個病人）。計算急癥室平均人數(shù)，以及病人的平均等待時間和平均逗留時間，醫(yī)生空閑的概率。解：由題意可知，此為M/M/1模型，λ=2，μ=3，ρ=λ/μ=2/3<1，模型能收斂。醫(yī)生空閑的概率：P0=1-ρ=1/3急診室里有n個病人的概率：

急診室里的平均隊長和排隊長：

病人的平均等待時間和平均逗留時間：。二、M/M/1/K模型（空間容量為K）在M/M/1/K模型中，依然可以令μn=μ，但對于到達的情況則需分為兩種情況討論：

同樣令

則穩(wěn)態(tài)概率

可解得：

由于系統(tǒng)空間為K有限，因此當系統(tǒng)人數(shù)達到K時就不會再有人到達，λ就不再是真正的平均達到率，引進實際平均達到率λe，λe=λ*(1-pK)+0*pK=λ*(1-pK)例7.3某理發(fā)店只有1個理發(fā)師，店內共有6個座位，顧客到達間隔時間服從負指數(shù)分布，平均每小時來20個潛在顧客，當座位滿的時候，顧客則不再進店直接離開；理發(fā)師為一個顧客理發(fā)平均需要15分鐘，理發(fā)時間也服從負指數(shù)分布。求：各項平均指標；理發(fā)師空閑的概率；顧客流失的概率。例7.3，解：由題意可知，此為M/M/1/6模型，λ=20，μ=4，ρ=5>1。理發(fā)師空閑概率：穩(wěn)態(tài)概率：

其中顧客流失概率為：

平均隊長：平均排隊長：

λe=λ*(1-pK)=20*0.2=4

三、M/M/s模型M/M/s排隊模型中的s是指排隊系統(tǒng)中服務臺的個數(shù)。假設顧客到達率保持穩(wěn)定λn=λ，每個服務臺的服務率也都是μ，但對整個系統(tǒng)而言，μn與系統(tǒng)中的顧客數(shù)有關,即：例7.4某銀行有3個服務窗口，顧客到達時間間隔服從負指數(shù)分布，平均到達率為9人/小時，每個窗口的服務時間服從負指數(shù)分布，平均服務率為4人/小時，3個窗口共享一個隊列。求這個排隊系統(tǒng)的相關指標。例7.4，解：由題意可知，λ=9，μ=4，s=3,ρ=9/4=2.25，ρs=2.25/3=0.75<1整個系統(tǒng)空閑概率：

平均排隊長：

平均排隊時間：

平均逗留時間：

平均隊長：

顧客到達時必須排隊的概率：

當有多個服務臺并且系統(tǒng)空間有限時，也即M/M/s/K模型時，假設系統(tǒng)空間沒滿時顧客到達率保持穩(wěn)定的λ，每個服務臺的服務率也都是μ。但對整個系統(tǒng)而言：這里的λe=λ(1-pK)，是指有效到達率表面上看來公式的推導與結果都比前幾個模型要復雜。其實在實際運用中，當s和K都不是太大時，可以把所有情況都列出來，也就是把N的分布列具體地表述出來，這樣所有的平均指標直接從分布列中就可以簡單計算得到。例7.5有一個汽車修理廠，有2個修理臺和2個修理師，另有2個等待車位，當4個位置都滿了，前來修理的車只能離開修理廠，待修汽車的到達是M流，平均每小時來一輛，修理時間服從負指數(shù)分布，平均修理1個小時，求：（1）這個排隊系統(tǒng)的各個主要指標；（2）客戶的損失率；（3）修理師都空閑的概率和至少有一個修理師空閑的概率。例7.5，解：由題意可知，此為M/M/2/4模型，λ=1，μ=1，ρ=1從分布列中得客戶的損失率為：pK=1/23；修理師都空閑的概率為p0=8/23，至少有一個修理師空閑概率為：p0+p1=16/23N的數(shù)學期望L=26/23；Nq的數(shù)學期望Lq=4/23；由于有損失，有效到達率λe=λ(1-pK)=22/23；N01234Nq00012Pn8/238/234/232/231/23第四節(jié)其他排隊模型及優(yōu)化

一、顧客源有限排隊模型有時排隊系統(tǒng)中顧客源數(shù)量很少比如車間里一個維修工負責修理發(fā)生了故障的機器，機器一共就m臺，機器發(fā)生故障相當于顧客到達，然后排隊等待維修工修理，在等待過程中，繼續(xù)正常工作的機器少了，單位時間內有機器發(fā)生故障的機會就少了。此類模型記為M/M/s/m/m模型，不能簡單套用上節(jié)介紹的模型。到達率，假設每個顧客的到達率都是相同的，記為λ，那么λn=λ(m-n)，其中0<n<m，服務率例7.6某車間有5臺機器，每臺機器的故障間隔時間服從負指數(shù)分布，平均間隔時間為1個小時，發(fā)生故障后，等待修理，每次的修理時間也服從負指數(shù)分布，平均為15分鐘，試計算此排隊系統(tǒng)的相關指標。解：由題意可知，此模型為M/M/1/5/5模型，λ=1，μ=4，ρ=1/4N的數(shù)學期望L=1.7963；Nq的數(shù)學期望Lq=0.9953；有效到達率λe=λ(m-L)=3.2037；根據(jù)Little公式：N012345Nq001234Pn0.19910.24880.24880.18660.09330.0233二、M/G/1排隊模型M/G/1排隊模型是指顧客的到達是M流，單個服務臺，但是和前面討論的所有排隊模型都不一樣的是，服務時間不再是負指數(shù)分布。對于服務時間只是假定其服從一般的分布，并假定服務時間的均值為1/μ，方差為σ2，依舊假定ρ=λ/μ，稱為服務強度。辛欽-波拉采克公式（Pollaczek-Khintchine公式）：其它相關的結論：例7.7（M/D/1模型）生產線最后一道工序是自動完成的，其服務時間是一個固定值0.5min，半成品達到這道工序的時間間隔依然是負指數(shù)分布，平均1分鐘到達1個，排隊空間可以認為無限，試計算此排隊系統(tǒng)的各項平均指標。例7.7解：由題意可知此排隊系統(tǒng)是M/D/1模型，λ=1，μ=2，ρ=1/2，由于服務時間是定長分布，所以σ2=0，根據(jù)辛欽-波拉采克公式，