運籌學第9章 排隊論

1、運籌學排隊論第 9 章Where the Time Goes美國人一生中平均要花費- 6年 吃5年 排隊等待4年 做家務2年 回電話不成功 1年 尋找放置不當?shù)奈锲?個月 打開郵寄廣告6個月 停在紅燈前排隊系統(tǒng)的基本特征離開排隊規(guī)則到達過程排隊結構服務過程退出離開需求群體商業(yè)服務系統(tǒng)系統(tǒng)類型顧客服務臺理發(fā)店人理發(fā)師銀行出納服務人出納ATM機服務人ATM機商店收銀臺人收銀員管道服務阻塞的管道管道工電影院售票窗口人售票員機場檢票處人航空公司代理人經(jīng)紀人服務人股票經(jīng)紀人內(nèi)部服務系統(tǒng)系統(tǒng)類型顧客服務臺秘書服務雇員秘書復印服務雇員復印機計算機編程服務雇員程序員大型計算機雇員計算機急救中心雇員護士傳真服務

2、雇員傳真機物料處理系統(tǒng)貨物物料處理單元維護系統(tǒng)設備維修工人質(zhì)檢站物件質(zhì)檢員運輸服務系統(tǒng)系統(tǒng)類型顧客服務臺公路收費站汽車收費員卡車裝貨地卡車裝貨工人港口卸貨區(qū)輪船卸貨工人等待起飛的飛機飛機跑道航班服務人飛機出租車服務人出租車電梯服務人電梯消防部門火災消防車停車場汽車停車空間急救車服務人急救車到達過程靜態(tài)動態(tài)預約定價接受/拒絕不加入排隊退出排隊恒定到達率的隨機到達變動到達率的隨機到達由設施控制顧客控制到達過程到達過程的內(nèi)容顧客總體數(shù)或顧客源數(shù)有限或無限顧客的到達類型單個或成批顧客的到達間隔時間間隔時間分布排隊結構領號多條隊列有限隊長有限隊長有限或無限隊長快速通道排隊結構單一隊列允許或不允許移動排隊

3、結構-例多隊多服務臺領號 34826101211579單隊多服務臺入口 排隊規(guī)則排隊規(guī)則靜態(tài)(FCFS 規(guī)則)(LCFS 規(guī)則).動態(tài)基于排隊狀況選擇即與特定顧客特征選擇 等待的顧客數(shù)協(xié)商優(yōu)先級強占顧客服務時間(SPT 規(guī)則)排隊規(guī)則的內(nèi)容損失制系統(tǒng)服務臺被占用時新到的顧客將離開等待制系統(tǒng)FCFSLCFSRSPR混合制系統(tǒng)損失制與等待制的混合服務過程服務過程靜態(tài)服務過程動態(tài)服務過程 自我服務機械速度不同的服務率開關服務通道服務過程的內(nèi)容服務臺數(shù)量單個或多個每次服務顧客的數(shù)量單個或成批服務顧客的時間分布時間分布常用的記號n 系統(tǒng)中的顧客數(shù) 平均到達率，即單位時間內(nèi)平均到達的顧客數(shù) 平均服務率，即

4、單位時間內(nèi)服務完畢的顧客數(shù)Sn(t) 時刻t系統(tǒng)中有n個顧客Pn(t) 時刻t系統(tǒng)狀態(tài)Sn(t) 的概率C 服務臺的個數(shù)M 顧客相繼到達的時間間隔服從負指數(shù)分布D 顧客相繼到達的時間間隔服從定長分布 Ek 顧客相繼到達的時間間隔服從k階Erlang分布排隊系統(tǒng)的符號表示 一個排隊系統(tǒng)的特征可以用六個參數(shù)表示，形式為：ABC / def其中A 顧客到達的概率分布，可取M、D、Ek等；B 服務時間的概率分布，可取M、D、Ek等；C 服務臺個數(shù)，取正整數(shù)；d 排隊系統(tǒng)的最大容量，可取正整數(shù)或；e 顧客源的最大容量，可取正整數(shù)或；f 排隊規(guī)則，可取FCFS、LCFS等。M/M/1/FCFS表示：顧客到

5、達的時間間隔是負指數(shù)分布服務時間是負指數(shù)分布一個服務臺排隊系統(tǒng)和顧客源的容量都是無限實行先到先服務的一個服務系統(tǒng) 顧客到達和服務的時間分布 Poisson流（Poisson過程） 定義 滿足以下四個條件的輸入流稱為Poisson流（Poisson過程）1、平穩(wěn)性：在時間區(qū)間t, t+t)內(nèi)到達k個顧客的概率與t無關，只與t有關。記為pk(t）。2、無后效性：不相交的時間區(qū)間內(nèi)到達的顧客數(shù)互相獨立。3、普通性：設在t, t+t）內(nèi)到達多于一個顧客的概率為q(t），則q(t)=o(t)即4、有限性：任意有限個區(qū)間內(nèi)到達有限個顧客的概率等于1。即Poisson流與Poisson分布定理 對于一個參數(shù)

6、為的Poisson流，在0，t內(nèi)到達k個顧客的概率為即服從以為參數(shù)的Poisson分布。 lll= 1= 3= 7Pk(1)x.4.3.2.1 0Poisson流與負指數(shù)分布之間的關系 定理 在排隊系統(tǒng)中，如果單位時間內(nèi)顧客到達數(shù)服從以為參數(shù)的Poisson分布，則顧客相繼到達的時間間隔服從以為參數(shù)的負指數(shù)分布。 l=0.41/為平均到達間隔時間k階Erlang分布 定理 設v1，v2，vk是k個互相獨立的，具有相同參數(shù)的負指數(shù)分布隨機變量，則隨機變量S=v1+v2+vk服從k階Erlang分布，S的密度函數(shù)為m=1k=1k=2k=4k=8系統(tǒng)績效度量 系統(tǒng)總的平均顧客數(shù)L 平均等待顧客個數(shù)L

7、q 包括服務的平均等待時間W 平均顧客等待時間Wq 系統(tǒng)利用率r基本排隊模型 M/M/1/FCFS 顧客到達的時間間隔是負指數(shù)分布服務時間是負指數(shù)分布一個服務臺排隊系統(tǒng)和顧客源的容量都是無限實行先到先服務的一個服務系統(tǒng)M/M/1/FCFS的分析 假設在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)概率得到 令稱為服務強度，則得M/M/1/FCFS的狀態(tài)轉移分析012n-1nn+1例高速公路

8、入口收費處設有一個收費通道，汽車到達服從Poisson分布，平均到達速率為100輛小時，收費時間服從負指數(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.4170.583=0.243系統(tǒng)中有2輛車的概率為：P2=2(1-)=0.417

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

10、成為M/M/1/N/FCFS 系統(tǒng)的狀態(tài)轉移圖 012n-1N系統(tǒng)的狀態(tài)概率平衡方程對于狀態(tài)0：P0=P1對于狀態(tài)k：Pk-1+Pk+1=(+)Pk 0kN對于狀態(tài)N：PN-1=PN系統(tǒng)的狀態(tài)概率由得到 系統(tǒng)的運行指標 對于1有有效到達率 Little公式例一個單人理發(fā)店，除理發(fā)椅外，還有4把椅子可供顧客等候。顧客到達發(fā)現(xiàn)沒有座位空閑，就不再等待而離去。顧客到達的平均速率為4人/小時，理發(fā)的平均時間為10分鐘/人。顧客到達服從Poisson流，理發(fā)時間服從負指數(shù)分布。求：1、顧客到達不用等待就可理發(fā)的概率；2、理發(fā)店里的平均顧客數(shù)以及等待理發(fā)的平均顧客數(shù)；3、顧客來店理發(fā)一次平均花費的時間及平

11、均等待的時間；4、顧客到達后因客滿而離去的概率；5、增加一張椅子可以減少的顧客損失率。解這是一個M/M/1/N/FCFS系統(tǒng)，其中N=4+1=5，=4人/小時，=6人/小時，=2/3。 因客滿而離去的概率為0.0048 當N=6時 P5-P6=0.0480-0.0311=0.0169=1.69% 即增加一張椅子可以減少顧客損失率1.69% 設顧客總數(shù)為m。當顧客需要服務時，就進入隊列等待；服務完畢后，重新回到顧客源中。如此循環(huán)往復 。服務臺.顧客源需要服務服務完畢隊列顧客源有限模型M/M/1/m/FCFS模型分析假定每一個顧客在單位時間內(nèi)需要接受服務的平均次數(shù)是相同的，設為 。當正在等待及正在

12、接受服務的顧客數(shù)為n時，則在單位時間內(nèi)要求接受服務的平均顧客數(shù)為 ： n=(m-n) 01nm狀態(tài)轉移方程0P0 = P1 n+Pn = Pn+1+n-1Pn-1(n=1，2，m-1) Pm=m-1Pm-1(n=1，2，m)運行指標 例某車間有5臺機器，每臺機器的連續(xù)運轉時間服從負指數(shù)分布，平均連續(xù)運行時間15分鐘。有一個修理工，每次修理時間服從負指數(shù)分布，平均每次12分鐘。求:(1)修理工空閑的概率；(2)五臺機器都出故障的概率；(3)出故障的平均臺數(shù)；(4)平均停工時間；(5)平均等待修理時間；(6)評價這個系統(tǒng)的運行情況。解根據(jù)題意，m=5，=1/15，=1/12，=/=0.8 多服務臺

13、模型M/M/c 標準的M/M/c/FCFS模型系統(tǒng)容量有限的M/M/c/N/FCFS模型有限顧客源的M/M/c/m/FCFS模型 M/M/c/FCFS模型 服務臺服務臺服務臺顧客到達顧客離去顧客離去顧客離去隊列顧客到達后，進入隊列尾端；當某一個服務臺空閑時，隊列中的第一個顧客即到該服務臺接收服務；服務完畢后隨即離去。各服務臺互相獨立且服務速率相同，即1=2=c 分析系統(tǒng)的服務速率與系統(tǒng)中的顧客數(shù)有關。當系統(tǒng)中的顧客數(shù)k不大于服務臺個數(shù)，即1kc時，系統(tǒng)中的顧客全部在服務臺中，這時系統(tǒng)的服務速率為k；當系統(tǒng)中的顧客數(shù)kc時，服務臺中正在接受服務的顧客數(shù)仍為c個，其余顧客在隊列中等待服務，這時系統(tǒng)

14、的服務速率為c。 則當1時系統(tǒng)才不會排成無限的隊列 狀態(tài)轉移圖與狀態(tài)轉移方程對狀態(tài)0:P0=P1對狀態(tài)1:P0+2P2=(+)P1對狀態(tài)c：Pc-1+cPc+1=(+c)Pc對狀態(tài)n Pn-1+cPn+1=(+c)Pn01cn狀態(tài)概率運行指標 例某售票處有三個窗口，顧客到達服從Poisson流，到達速率為0.9人分，售票時間服從負指數(shù)分布，每個窗口的平均售票速率為0.4人分。顧客到達后排成一隊，依次到空閑窗口購票。求：(1)所有窗口都空閑的概率；(2)平均隊長；(3)平均等待時間及逗留時間；(4)顧客到達后必須等待的概率。解/=2.25，=/c=0.75 (1)所有窗口都空閑的概率，即求P0的

15、值 (2)平均隊長，即求L的值，必須先求Lq (3)平均等待時間和平均逗留時間，即求Wq和W和的值 (4)顧客到達后必須等待，即n3 M/M/c/N/FCFS模型 離開服務臺服務臺服務臺顧客到達顧客離去顧客離去顧客離去隊列分析設系統(tǒng)容量為N(Nc)，當系統(tǒng)中的顧數(shù)nN時，到達的顧客就進入系統(tǒng)；當n=N時，到達的顧客就被拒絕。設顧客到達的速率為，c每個服務臺服務的速率為，=/c。由于系統(tǒng)不會無限止地接納顧客，對不必加以限制。 狀態(tài)轉移圖與狀態(tài)轉移方程對狀態(tài)0:P0=P1對狀態(tài)1:P0+2P2=(+)P1對狀態(tài)c：Pc-1+cPc+1=(+c)Pc對狀態(tài)N PN-1=cPN 01cN狀態(tài)概率運行指

16、標 例某旅館有8個單人房間，旅客到達服從Poisson流，平均速率為6人天，旅客平均逗留時間為2天，求：(1)每天客房平均占用數(shù)； (2)旅館客滿的概率。 解旅館8個房間全滿的概率為0.423 平均占用客房數(shù)為6.9間。客房占用率為86.6% M/M/c/m/FCFS模型 顧客到達修理速率發(fā)生故障等待修理的機器修理速率修理速率正在修理的機器到達速率 (m-n)修理速率c運行的機器數(shù) m-n狀態(tài)概率 其中 運行指標效到達速率e為單位時間內(nèi)出現(xiàn)故障的機器數(shù)，有e=(m-L) 例車間有5臺機器，每臺機器的故障率為1次小時，有2個修理工負責修理這5臺機器，工作效率相同，為4臺小時。求：(1)等待修理的平均機器數(shù)；(2)等待修理及正在修理的平均機器數(shù)；(3)每小時發(fā)生故障的平均機器數(shù)；(4)平均等待修理的時間；(5)平均停工時間。解 可以計算得到（算式略）：P1=0.394，P2=0.197，P3=0.074，P4=0.018，P5=0.00