運(yùn)籌學(xué)：第七章 排隊(duì)論

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

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

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

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

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

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

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

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

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

排隊(duì)系統(tǒng)優(yōu)化問(wèn)題的研究

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

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

1、馬爾可夫過(guò)程簡(jiǎn)介

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

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

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

令：

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

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

急診室里的平均隊(duì)長(zhǎng)和排隊(duì)長(zhǎng)：

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

同樣令

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

可解得：

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

其中顧客流失概率為：

平均隊(duì)長(zhǎng)：平均排隊(duì)長(zhǎng)：

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

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

平均排隊(duì)長(zhǎng)：

平均排隊(duì)時(shí)間：

平均逗留時(shí)間：

平均隊(duì)長(zhǎng)：

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

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

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