運籌學(xué)：第七章 排隊論

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

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

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

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

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

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

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

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

代表服務(wù)機構(gòu)模型，n代表服務(wù)臺的數(shù)目，A代表系統(tǒng)容量，B代表顧客源的數(shù)量，C代表排隊規(guī)則。三、排隊模型中的主要參數(shù)1、隊長和排隊長：隊長是指系統(tǒng)中顧客總數(shù)（包括排隊等待和正在接受服務(wù)的人數(shù)），記為N(t)，它的期望值為平均隊長，記為L。隊長是排隊系統(tǒng)中顧客的平均數(shù)（期望值），它是正在被服務(wù)的顧客和等待接受服務(wù)的顧客總數(shù)的期望值。反映了排隊系統(tǒng)中的一種總規(guī)模。排隊長是指排隊等待的顧客數(shù)，記為Nq(t)，其期望值為平均排隊長，記為Lq。L=Lq+正在服務(wù)的人數(shù)2、等待時間和逗留時間：等待時間是指從顧客到達(dá)時間算起到他開始接受服務(wù)為止的這段時間，記為Tq(t)，它的期望值為平均等待時間，記為Wq。逗留時間是指顧客到達(dá)時刻算起到他接受服務(wù)完畢為止的這段時間，記為T(t)，它的期望值為平均逗留時間，記為W。一般地有：逗留時間=等待時間+服務(wù)時間。3、忙期和閑期：忙期是指服務(wù)臺連續(xù)繁忙的時間，即顧客從到達(dá)空閑服務(wù)臺算起到服務(wù)臺再次變?yōu)榭臻e時止的這段時間。這是服務(wù)臺最關(guān)心數(shù)量指標(biāo)，它直接關(guān)系到服務(wù)員的工作強度。閑期是指服務(wù)臺連續(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)設(shè)計和最優(yōu)運營問題。前者屬于靜態(tài)問題，它是在輸入和服務(wù)參數(shù)給定的情況下，確定系統(tǒng)的設(shè)計參數(shù)，以使服務(wù)設(shè)施達(dá)到最大效益或者服務(wù)機構(gòu)實現(xiàn)最為經(jīng)濟。后者屬于動態(tài)問題，它是指對于一個給定的系統(tǒng)，在系統(tǒng)運行的參數(shù)可以隨著時間或狀態(tài)變化的情況下，考慮如何運營使某個目標(biāo)函數(shù)達(dá)到最優(yōu)?？傎M用=服務(wù)費用+等待費用隨著服務(wù)水平提高，服務(wù)費用增加而等待費用減少！

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

1、馬爾可夫過程簡介

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

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

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

令：

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

；當(dāng)ρ≥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ī)生值班，病人的到達(dá)時間間隔服從負(fù)指數(shù)分布，平均每小時來2個病人，醫(yī)生治療病人的時間也服從負(fù)指數(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=μ，但對于到達(dá)的情況則需分為兩種情況討論：

同樣令

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

可解得：

由于系統(tǒng)空間為K有限，因此當(dāng)系統(tǒng)人數(shù)達(dá)到K時就不會再有人到達(dá)，λ就不再是真正的平均達(dá)到率，引進(jìn)實際平均達(dá)到率λe，λe=λ*(1-pK)+0*pK=λ*(1-pK)例7.3某理發(fā)店只有1個理發(fā)師，店內(nèi)共有6個座位，顧客到達(dá)間隔時間服從負(fù)指數(shù)分布，平均每小時來20個潛在顧客，當(dāng)座位滿的時候，顧客則不再進(jìn)店直接離開；理發(fā)師為一個顧客理發(fā)平均需要15分鐘，理發(fā)時間也服從負(fù)指數(shù)分布。求：各項平均指標(biāo)；理發(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)中服務(wù)臺的個數(shù)。假設(shè)顧客到達(dá)率保持穩(wěn)定λn=λ，每個服務(wù)臺的服務(wù)率也都是μ，但對整個系統(tǒng)而言，μn與系統(tǒng)中的顧客數(shù)有關(guān),即：例7.4某銀行有3個服務(wù)窗口，顧客到達(dá)時間間隔服從負(fù)指數(shù)分布，平均到達(dá)率為9人/小時，每個窗口的服務(wù)時間服從負(fù)指數(shù)分布，平均服務(wù)率為4人/小時，3個窗口共享一個隊列。求這個排隊系統(tǒng)的相關(guān)指標(biāo)。例7.4，解：由題意可知，λ=9，μ=4，s=3,ρ=9/4=2.25，ρs=2.25/3=0.75<1整個系統(tǒng)空閑概率：

平均排隊長：

平均排隊時間：

平均逗留時間：

平均隊長：

顧客到達(dá)時必須排隊的概率：

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

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