運(yùn)籌學(xué)-8、排隊(duì)論

運(yùn)籌學(xué)OperationsResearchQueuingtheory第7章排隊(duì)論7.1排隊(duì)論的基本概念7.2排隊(duì)系統(tǒng)常用分布7.3單服務(wù)臺(tái)模型[M/M/1]7.4多服務(wù)臺(tái)模型[M/M/s]7.5其它服務(wù)時(shí)間分布模型7.6排隊(duì)系統(tǒng)的優(yōu)化WheretheTimeGoes美國(guó)人一生中平均要花費(fèi)--6年吃5年排隊(duì)等待4年做家務(wù)2年回電話(huà)不成功1年尋找放置不當(dāng)?shù)奈锲?個(gè)月打開(kāi)郵寄廣告6個(gè)月停在紅燈前排隊(duì)系統(tǒng)的基本特征離開(kāi)排隊(duì)規(guī)則到達(dá)過(guò)程排隊(duì)結(jié)構(gòu)服務(wù)過(guò)程退出離開(kāi)需求群體商業(yè)服務(wù)系統(tǒng)系統(tǒng)類(lèi)型 顧客 服務(wù)臺(tái)理發(fā)店 人 理發(fā)師銀行出納服務(wù) 人 出納ATM機(jī)服務(wù) 人 ATM機(jī)商店收銀臺(tái) 人 收銀員管道服務(wù) 阻塞的管道 管道工電影院售票窗口 人 售票員機(jī)場(chǎng)檢票處 人 航空公司代理人經(jīng)紀(jì)人服務(wù) 人 股票經(jīng)紀(jì)人內(nèi)部服務(wù)系統(tǒng)系統(tǒng)類(lèi)型 顧客 服務(wù)臺(tái)秘書(shū)服務(wù) 雇員 秘書(shū)復(fù)印服務(wù) 雇員 復(fù)印機(jī)計(jì)算機(jī)編程服務(wù) 雇員 程序員大型計(jì)算機(jī) 雇員 計(jì)算機(jī)急救中心 雇員 護(hù)士傳真服務(wù) 雇員 傳真機(jī)物料處理系統(tǒng) 貨物 物料處理單元維護(hù)系統(tǒng) 設(shè)備 維修工人質(zhì)檢站 物件 質(zhì)檢員運(yùn)輸服務(wù)系統(tǒng)系統(tǒng)類(lèi)型 顧客 服務(wù)臺(tái)公路收費(fèi)站 汽車(chē) 收費(fèi)員卡車(chē)裝貨地 卡車(chē) 裝貨工人港口卸貨區(qū) 輪船 卸貨工人等待起飛的飛機(jī) 飛機(jī) 跑道航班服務(wù) 人 飛機(jī)出租車(chē)服務(wù) 人 出租車(chē)電梯服務(wù) 人 電梯消防部門(mén) 火災(zāi) 消防車(chē)停車(chē)場(chǎng) 汽車(chē) 停車(chē)空間急救車(chē)服務(wù) 人 急救車(chē)到達(dá)過(guò)程靜態(tài)動(dòng)態(tài)預(yù)約定價(jià)接受/拒絕不加入排隊(duì)退出排隊(duì)恒定到達(dá)率的隨機(jī)到達(dá)變動(dòng)到達(dá)率的隨機(jī)到達(dá)由設(shè)施控制顧客控制到達(dá)過(guò)程到達(dá)過(guò)程的內(nèi)容顧客總體數(shù)或顧客源數(shù)有限或無(wú)限顧客的到達(dá)類(lèi)型單個(gè)或成批顧客的到達(dá)間隔時(shí)間間隔時(shí)間分布排隊(duì)結(jié)構(gòu)領(lǐng)號(hào)多條隊(duì)列有限隊(duì)長(zhǎng)有限隊(duì)長(zhǎng)有限或無(wú)限隊(duì)長(zhǎng)快速通道排隊(duì)結(jié)構(gòu)單一隊(duì)列允許或不允許移動(dòng)排隊(duì)結(jié)構(gòu)-例多隊(duì)多服務(wù)臺(tái)領(lǐng)號(hào)34826101211579單隊(duì)多服務(wù)臺(tái)入口排隊(duì)規(guī)則排隊(duì)規(guī)則靜態(tài)(FCFS規(guī)則)(LCFS規(guī)則).動(dòng)態(tài)基于排隊(duì)狀況選擇即與特定顧客特征選擇等待的顧客數(shù)協(xié)商優(yōu)先級(jí)強(qiáng)占顧客服務(wù)時(shí)間(SPT規(guī)則)排隊(duì)規(guī)則的內(nèi)容損失制系統(tǒng)服務(wù)臺(tái)被占用時(shí)新到的顧客將離開(kāi)等待制系統(tǒng)FCFSLCFSRSPR混合制系統(tǒng)損失制與等待制的混合服務(wù)過(guò)程服務(wù)過(guò)程靜態(tài)服務(wù)過(guò)程動(dòng)態(tài)服務(wù)過(guò)程自我服務(wù)機(jī)械速度不同的服務(wù)率開(kāi)關(guān)服務(wù)通道服務(wù)過(guò)程的內(nèi)容服務(wù)臺(tái)數(shù)量單個(gè)或多個(gè)每次服務(wù)顧客的數(shù)量單個(gè)或成批服務(wù)顧客的時(shí)間分布時(shí)間分布常用的記號(hào)n––系統(tǒng)中的顧客數(shù)

––平均到達(dá)率，即單位時(shí)間內(nèi)平均到達(dá)的顧客數(shù)

––平均服務(wù)率，即單位時(shí)間內(nèi)服務(wù)完畢的顧客數(shù)Sn(t)––時(shí)刻t系統(tǒng)中有n個(gè)顧客Pn(t)––時(shí)刻t系統(tǒng)狀態(tài)Sn(t)的概率C––服務(wù)臺(tái)的個(gè)數(shù)M––顧客相繼到達(dá)的時(shí)間間隔服從負(fù)指數(shù)分布D––顧客相繼到達(dá)的時(shí)間間隔服從定長(zhǎng)分布Ek––顧客相繼到達(dá)的時(shí)間間隔服從k階Erlang分布排隊(duì)系統(tǒng)的符號(hào)表示一個(gè)排隊(duì)系統(tǒng)的特征可以用六個(gè)參數(shù)表示，形式為：

[A／B／C]：[d／e／f]其中A––顧客到達(dá)的概率分布，可取M、D、Ek等；B––服務(wù)時(shí)間的概率分布，可取M、D、Ek等；C––服務(wù)臺(tái)個(gè)數(shù)，取正整數(shù)；d––排隊(duì)系統(tǒng)的最大容量，可取正整數(shù)或；e––顧客源的最大容量，可取正整數(shù)或；f––排隊(duì)規(guī)則，可取FCFS、LCFS等。[M/M/1]：[//FCFS]表示：顧客到達(dá)的時(shí)間間隔是負(fù)指數(shù)分布服務(wù)時(shí)間是負(fù)指數(shù)分布一個(gè)服務(wù)臺(tái)排隊(duì)系統(tǒng)和顧客源的容量都是無(wú)限實(shí)行先到先服務(wù)的一個(gè)服務(wù)系統(tǒng)

Poisson流（Poisson過(guò)程）定義滿(mǎn)足以下四個(gè)條件的輸入流稱(chēng)為Poisson流（Poisson過(guò)程）1、平穩(wěn)性：在時(shí)間區(qū)間[t,t+t)內(nèi)到達(dá)k個(gè)顧客的概率與t無(wú)關(guān)，只與t有關(guān)。記為pk(t）。2、無(wú)后效性：不相交的時(shí)間區(qū)間內(nèi)到達(dá)的顧客數(shù)互相獨(dú)立。3、普通性：設(shè)在[t,t+t）內(nèi)到達(dá)多于一個(gè)顧客的概率為q(t），則

q(t)=o(t)即

4、有限性：任意有限個(gè)區(qū)間內(nèi)到達(dá)有限個(gè)顧客的概率等于一。即Poisson流與Poisson分布定理

對(duì)于一個(gè)參數(shù)為的Poisson流，在[0，t)內(nèi)到達(dá)k個(gè)顧客的概率為

即服從以為參數(shù)的Poisson分布。

lll=1=3=7Pkk.4.3.2.10數(shù)學(xué)家泊松（Poisson）（1781—1840）

“泊松是第一個(gè)沿著復(fù)平面上的路徑實(shí)行積分的人.”──克蘭

“我建立了描述隨機(jī)現(xiàn)象的一種概率分布.”──泊松

泊松是法國(guó)數(shù)學(xué)家、物理學(xué)家和力學(xué)家

Poisson流與負(fù)指數(shù)分布之間的關(guān)系定理

在排隊(duì)系統(tǒng)中，如果單位時(shí)間內(nèi)顧客到達(dá)數(shù)服從以為參數(shù)的Poisson分布，則顧客相繼到達(dá)的時(shí)間間隔服從以為參數(shù)的負(fù)指數(shù)分布。

l=0.41/為平均到達(dá)間隔時(shí)間Excel中的泊松分布POISSON

用途：返回泊松分布。泊松分布通常用于預(yù)測(cè)一段時(shí)間內(nèi)事件發(fā)生的次數(shù)，比如一分鐘內(nèi)通過(guò)收費(fèi)站的轎車(chē)的數(shù)量。

語(yǔ)法：POISSON(x，mean，cumulative)

參數(shù)：X是某一事件出現(xiàn)的次數(shù)，Mean是期望值，Cumulative為確定返回的概率分布形式的邏輯值。Cumulative

為一邏輯值，確定所返回的概率分布形式。如果cumulative為T(mén)RUE，函數(shù)POISSON返回泊松累積分布概率，即，隨機(jī)事件發(fā)生的次數(shù)在0到x之間（包含0和1）；如果為FALSE，則返回泊松概率密度函數(shù)，即，隨機(jī)事件發(fā)生的次數(shù)恰好為x。

實(shí)例：公式“=POISSON(5，10，TRUE)”返回0.067085963，=POISSON(3，12，F(xiàn)ALSE)返回0.001769533。k階Erlang分布定理

設(shè)v1，v2，…，vk是k個(gè)互相獨(dú)立的，具有相同參數(shù)的負(fù)指數(shù)分布隨機(jī)變量，則隨機(jī)變量

S=v1+v2+…+vk服從k階Erlang分布，S的密度函數(shù)為m=1k=1k=2k=4k=8系統(tǒng)績(jī)效度量

系統(tǒng)總的平均顧客數(shù)L

平均等待顧客個(gè)數(shù)Lq

包括服務(wù)的平均等待時(shí)間W

平均顧客等待時(shí)間Wq基本排隊(duì)模型[M/M/1]:[//FCFS]顧客到達(dá)的時(shí)間間隔是負(fù)指數(shù)分布服務(wù)時(shí)間是負(fù)指數(shù)分布一個(gè)服務(wù)臺(tái)排隊(duì)系統(tǒng)和顧客源的容量都是無(wú)限實(shí)行先到先服務(wù)的一個(gè)服務(wù)系統(tǒng)[M/M/1]:[//FCFS]的分析假設(shè)在t+t時(shí)刻系統(tǒng)中顧客數(shù)為n的概率Pn(t+t)SnSnSn+1Sn-1SnPn(t)Pn-1(t)Pn+1(t)Pn(t)t時(shí)刻t+t時(shí)刻無(wú)到達(dá)，無(wú)離開(kāi)無(wú)到達(dá)，離開(kāi)一個(gè)到達(dá)一個(gè)，無(wú)離開(kāi)到達(dá)一個(gè)，離開(kāi)一個(gè)系統(tǒng)的過(guò)渡狀態(tài)與穩(wěn)定狀態(tài)過(guò)渡穩(wěn)定穩(wěn)定狀態(tài)下的狀態(tài)概率得到

令

稱(chēng)為服務(wù)強(qiáng)度，則得[M/M/1]:[//FCFS]的狀態(tài)轉(zhuǎn)移分析λ012n-1nn+1例高速公路入口收費(fèi)處設(shè)有一個(gè)收費(fèi)通道，汽車(chē)到達(dá)服從Poisson分布，平均到達(dá)速率為100輛／小時(shí)，收費(fèi)時(shí)間服從負(fù)指數(shù)分布，平均收費(fèi)時(shí)間為15秒／輛。求1、收費(fèi)處空閑的概率；2、收費(fèi)處忙的概率；3、系統(tǒng)中分別有1，2，3輛車(chē)的概率。解根據(jù)題意,=100輛/小時(shí),1/=15秒=1/240（小時(shí)/輛）,即＝240（輛/小時(shí)）。因此，=/=100/240=5/12。系統(tǒng)空閑的概率為：

P0=1-=1-(5/12)=7/12=0.583系統(tǒng)忙的概率為：

1-P0=1-(1-)==5/12=0.417系統(tǒng)中有1輛車(chē)的概率為：

P1=(1-)=0.417×0.583=0.243系統(tǒng)中有2輛車(chē)的概率為：

P2=2(1-)=0.4172×0.583=0.101系統(tǒng)中有3輛車(chē)的概率為：

P3=3(1-)=0.4173×0.583=0.0421Little公式[M/M/1]:[//FCFS]的系統(tǒng)指標(biāo)系統(tǒng)中的平均顧客數(shù)L

隊(duì)列中的平均顧客數(shù)Lq顧客在系統(tǒng)中的平均逗留時(shí)間W顧客在隊(duì)列中的平均逗留時(shí)間Wq例高速公路入口收費(fèi)處設(shè)有一個(gè)收費(fèi)通道，汽車(chē)到達(dá)服從Poisson分布，平均到達(dá)速率為200輛/小時(shí)，收費(fèi)時(shí)間服從負(fù)指數(shù)分布，平均收費(fèi)時(shí)間為15秒/輛。求L、Lq、W和Wq。解根據(jù)題意，=200輛/小時(shí)，=240輛/小時(shí)，=/=5/6。有限隊(duì)列模型[M/M/1]:[N//FCFS]當(dāng)隊(duì)列的容量從無(wú)限值變?yōu)橛邢拗礜時(shí)，[M/M/1]:[//FCFS]就轉(zhuǎn)化成為[M/M/1]:[N//FCFS]

系統(tǒng)的狀態(tài)轉(zhuǎn)移圖

λ012n-1n系統(tǒng)的狀態(tài)概率平衡方程對(duì)于狀態(tài)0： P0=P1

… …對(duì)于狀態(tài)k： Pk-1+Pk+1=(+)Pk0<k<N… …對(duì)于狀態(tài)N： PN-1=PN系統(tǒng)的狀態(tài)概率由得到

系統(tǒng)的運(yùn)行指標(biāo)對(duì)于1有有效到達(dá)率Little公式例一個(gè)單人理發(fā)店，除理發(fā)椅外，還有4把椅子可供顧客等候。顧客到達(dá)發(fā)現(xiàn)沒(méi)有座位空閑，就不再等待而離去。顧客到達(dá)的平均速率為4人/小時(shí)，理發(fā)的平均時(shí)間為10分鐘/人。顧客到達(dá)服從Poisson流，理發(fā)時(shí)間服從負(fù)指數(shù)分布。求：1、顧客到達(dá)不用等待就可理發(fā)的概率；2、理發(fā)店里的平均顧客數(shù)以及等待理發(fā)的平均顧客數(shù)；3、顧客來(lái)店理發(fā)一次平均花費(fèi)的時(shí)間及平均等待的時(shí)間；4、顧客到達(dá)后因客滿(mǎn)而離去的概率；5、增加一張椅子可以減少的顧客損失率。解這是一個(gè)[M/M/1]:[N//FCFS]系統(tǒng)，其中N=4+1=5，=4人/小時(shí)，=6人/小時(shí)，=2/3。

因客滿(mǎn)而離去的概率為0.048當(dāng)N=6時(shí)

P5-P6=0.0480-0.0311=0.0169=1.69%即增加一張椅子可以減少顧客損失率1.69%[M/M/1]:[∞/m/FCFS]模型設(shè)顧客總數(shù)為m。當(dāng)顧客需要服務(wù)時(shí)，就進(jìn)入隊(duì)列等待；服務(wù)完畢后，重新回到顧客源中。如此循環(huán)往復(fù)。服務(wù)臺(tái)...顧客源需要服務(wù)服務(wù)完畢隊(duì)列分析假定每一個(gè)顧客在單位時(shí)間內(nèi)需要接受服務(wù)的平均次數(shù)是相同的，設(shè)為λ

。當(dāng)正在等待及正在接受服務(wù)的顧客數(shù)為n時(shí)，則在單位時(shí)間內(nèi)要求接受服務(wù)的平均顧客數(shù)為：

λn=λ(m-n)01nm狀態(tài)轉(zhuǎn)移方程λ0P0=μP1 ……[λn+μ]Pn=μPn+1+λn-1Pn-1

(n=1，2，…，m-1)

……μPm=λm-1Pm-1

(n=1，2，…，m)

運(yùn)行指標(biāo)例某車(chē)間有5臺(tái)機(jī)器，每臺(tái)機(jī)器的連續(xù)運(yùn)轉(zhuǎn)時(shí)間服從負(fù)指數(shù)分布，平均連續(xù)運(yùn)行時(shí)間15分鐘。有一個(gè)修理工，每次修理時(shí)間服從負(fù)指數(shù)分布，平均每次12分鐘。求:(1)修理工空閑的概率；(2)五臺(tái)機(jī)器都出故障的概率；(3)出故障的平均臺(tái)數(shù)；(4)平均停工時(shí)間；(5)平均等待修理時(shí)間；(6)評(píng)價(jià)這個(gè)系統(tǒng)的運(yùn)行情況。解根據(jù)題意，m=5，λ=1/15，μ=1/12，ρ=λ/μ=0.8

多服務(wù)臺(tái)模型[M/M/c]標(biāo)準(zhǔn)的[M/M/c]:[∞/∞/FCFS]模型系統(tǒng)容量有限的[M/M/c]:[N/∞/FCFS]模型有限顧客源的[M/M/c]:[∞/m/FCFS]模型

[M/M/c]:[∞/∞/FCFS]模型服務(wù)臺(tái)服務(wù)臺(tái)服務(wù)臺(tái)顧客到達(dá)顧客離去顧客離去顧客離去隊(duì)列顧客到達(dá)后，進(jìn)入隊(duì)列尾端；當(dāng)某一個(gè)服務(wù)臺(tái)空閑時(shí)，隊(duì)列中的第一個(gè)顧客即到該服務(wù)臺(tái)接收服務(wù)；服務(wù)完畢后隨即離去。各服務(wù)臺(tái)互相獨(dú)立且服務(wù)速率相同，即μ1=μ2=…=μc

分析系統(tǒng)的服務(wù)速率與系統(tǒng)中的顧客數(shù)有關(guān)。當(dāng)系統(tǒng)中的顧客數(shù)k不大于服務(wù)臺(tái)個(gè)數(shù)，即1≤k≤c時(shí)，系統(tǒng)中的顧客全部在服務(wù)臺(tái)中，這時(shí)系統(tǒng)的服務(wù)速率為kμ；當(dāng)系統(tǒng)中的顧客數(shù)k＞c時(shí)，服務(wù)臺(tái)中正在接受服務(wù)的顧客數(shù)仍為c個(gè)，其余顧客在隊(duì)列中等待服務(wù)，這時(shí)系統(tǒng)的服務(wù)速率為cμ。

則當(dāng)ρ＜1時(shí)系統(tǒng)才不會(huì)排成無(wú)限長(zhǎng)的隊(duì)列

狀態(tài)轉(zhuǎn)移圖與狀態(tài)轉(zhuǎn)移方程對(duì)狀態(tài)0: λP0=μP1

對(duì)狀態(tài)1: λP0+2μP2=(λ+μ)P1 …………對(duì)狀態(tài)c： λPc-1+cμPc+1=(λ+cμ)Pc …………對(duì)狀態(tài)n λPn-1+cμPn+1=(λ+cμ)Pn ………01cn狀態(tài)概率運(yùn)行指標(biāo)例某售票處有三個(gè)窗口，顧客到達(dá)服從Poisson流，到達(dá)速率為0.9人／分，售票時(shí)間服從負(fù)指數(shù)分布，每個(gè)窗口的平均售票速率為0.4人／分。顧客到達(dá)后排成一隊(duì)，依次到空閑窗口購(gòu)票。求：(1)所有窗口都空閑的概率；(2)平均隊(duì)長(zhǎng)；(3)平均等待時(shí)間及逗留時(shí)間；(4)顧客到達(dá)后必須等待的概率。解λ/μ=2.25，ρ=λ/cμ=0.75(1)所有窗口都空閑的概率，即求P0的值

(2)平均隊(duì)長(zhǎng)，即求L的值，必須先求Lq

(3)平均等待時(shí)間和平均逗留時(shí)間，即求Wq和W和的值

(4)顧客到達(dá)后必須等待，即n≥3[M/M/c]:[N/∞/FCFS]模型離開(kāi)服務(wù)臺(tái)服務(wù)臺(tái)服務(wù)臺(tái)顧客到達(dá)顧客離去顧客離去顧客離去隊(duì)列分析設(shè)系統(tǒng)容量為N(N≥c)，當(dāng)系統(tǒng)中的顧數(shù)n＜N時(shí)，到達(dá)的顧客就進(jìn)入系統(tǒng)；當(dāng)n=N時(shí)，到達(dá)的顧客就被拒絕。設(shè)顧客到達(dá)的速率為λ，m每個(gè)服務(wù)臺(tái)服務(wù)的速率為μ，ρ=λ/cμ。由于系統(tǒng)不會(huì)無(wú)限止地接納顧客，對(duì)ρ不必加以限制。

狀態(tài)轉(zhuǎn)移圖與狀態(tài)轉(zhuǎn)移方程對(duì)狀態(tài)0: λP0=μP1

對(duì)狀態(tài)1: λP0+2μP2=(λ+μ)P1 …………對(duì)狀態(tài)c： λPc-1+cμPc+1=(λ+cμ)Pc …………對(duì)狀態(tài)N