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

––平均到達率，即單位時間內平均到達的顧客數

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

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

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

q(t)=o(t)即

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

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

即服從以為參數的Poisson分布。

lll=1=3=7Pkk.4.3.2.10數學家泊松（Poisson）（1781—1840）

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

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

泊松是法國數學家、物理學家和力學家

Poisson流與負指數分布之間的關系定理

在排隊系統中，如果單位時間內顧客到達數服從以為參數的Poisson分布，則顧客相繼到達的時間間隔服從以為參數的負指數分布。

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

用途：返回泊松分布。泊松分布通常用于預測一段時間內事件發生的次數，比如一分鐘內通過收費站的轎車的數量。

語法：POISSON(x，mean，cumulative)

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

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

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

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

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

系統總的平均顧客數L

平均等待顧客個數Lq

包括服務的平均等待時間W

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

令

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

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

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

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

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

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

隊列中的平均顧客數Lq顧客在系統中的平均逗留時間W顧客在隊列中的平均逗留時間Wq例高速公路入口收費處設有一個收費通道，汽車到達服從Poisson分布，平均到達速率為200輛/小時，收費時間服從負指數分布，平均收費時間為15秒/輛。求L、Lq、W和Wq。解根據題意，=200輛/小時，=240輛/小時，=/=5/6。有限隊列模型[M/M/1]:[N//FCFS]當隊列的容量從無限值變為有限值N時，[M/M/1]:[//FCFS]就轉化成為[M/M/1]:[N//FCFS]

系統的狀態轉移圖

λ012n-1n系統的狀態概率平衡方程對于狀態0： P0=P1

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

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

因客滿而離去的概率為0.048當N=6時

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

。當正在等待及正在接受服務的顧客數為n時，則在單位時間內要求接受服務的平均顧客數為：

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

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

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

(n=1，2，…，m)

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

多服務臺模型[M/M/c]標準的[M/M/c]:[∞/∞/FCFS]模型系統容量有限的[M/M/c]:[N/∞/FCFS]模型有限顧客源的[M/M/c]:[∞/m/FCFS]模型

[M/M/c]:[∞/∞/FCFS]模型服務臺服務臺服務臺顧客到達顧客離去顧客離去顧客離去隊列顧客到達后，進入隊列尾端；當某一個服務臺空閑時，隊列中的第一個顧客即到該服務臺接收服務；服務完畢后隨即離去。各服務臺互相獨立且服務速率相同，即μ1=μ2=…=μc

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

則當ρ＜1時系統才不會排成無限長的隊列

狀態轉移圖與狀態轉移方程對狀態0: λP0=μP1

對狀態1: λP0+2μP2=(λ+μ)P1 …………對狀態c： λPc-1+cμPc+1=(λ+cμ)Pc …………對狀態n λPn-1+cμPn+1=(λ+cμ)Pn ………01cn狀態概率運行指標例某售票處有三個窗口，顧客到達服從Poisson流，到達速率為0.9人／分，售票時間服從負指數分布，每個窗口的平均售票速率為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]模型離開服務臺服務臺服務臺顧客到達顧客離去顧客離去顧客離去隊列分析設系統容量為N(N≥c)，當系統中的顧數n＜N時，到達的顧客就進入系統；當n=N時，到達的顧客就被拒絕。設顧客到達的速率為λ，m每個服務臺服務的速率為μ，ρ=λ/cμ。由于系統不會無限止地接納顧客，對ρ不必加以限制。

狀態轉移圖與狀態轉移方程對狀態0: λP0=μP1

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