運籌學(xué)-8、排隊論

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

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

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

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

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

q(t)=o(t)即

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

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

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

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

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

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

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

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

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

l=0.41/為平均到達間隔時間Excel中的泊松分布POISSON

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

語法：POISSON(x，mean，cumulative)

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

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

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

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

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

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

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

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

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

令

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

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

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

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

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

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

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

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

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

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

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

。當(dāng)正在等待及正在接受服務(wù)的顧客數(shù)為n時，則在單位時間內(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)

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

多服務(wù)臺模型[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ù)臺服務(wù)臺服務(wù)臺顧客到達顧客離去顧客離去顧客離去隊列顧客到達后，進入隊列尾端；當(dāng)某一個服務(wù)臺空閑時，隊列中的第一個顧客即到該服務(wù)臺接收服務(wù)；服務(wù)完畢后隨即離去。各服務(wù)臺互相獨立且服務(wù)速率相同，即μ1=μ2=…=μc

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

則當(dāng)ρ＜1時系統(tǒng)才不會排成無限長的隊列

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

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

(2)平均隊長，即求L的值，必須先求Lq

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

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

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

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