管理運(yùn)籌學(xué)排隊(duì)論課件

第十章排隊(duì)論1第十章1第十章排隊(duì)論§10.1概述排隊(duì)論（QueingTheory）也稱(chēng)隨機(jī)服務(wù)系統(tǒng)。任何一個(gè)服務(wù)系統(tǒng)均由客體和主體組成。前者是要求服務(wù)的對(duì)象，我們一律稱(chēng)之為“顧客”；后者是提供服務(wù)的機(jī)構(gòu)或人員，一律稱(chēng)之為“服務(wù)員”。顧客可泛指機(jī)器、病人、飛機(jī)、輪船等，服務(wù)員可泛指機(jī)修工、醫(yī)生、碼頭等。2第十章排隊(duì)論§10.1概述2第十章排隊(duì)論.服務(wù)系統(tǒng)顧客:機(jī)器、飛機(jī)、輪船、病人……顧客到達(dá)——等待服務(wù)——接受服務(wù)——顧客離去服務(wù)員：機(jī)修工、碼頭設(shè)備、醫(yī)生……到達(dá)時(shí)間>服務(wù)時(shí)間系統(tǒng)空閑到達(dá)時(shí)間=服務(wù)時(shí)間充分利用,無(wú)排隊(duì)到達(dá)時(shí)間<服務(wù)時(shí)間排隊(duì)越來(lái)越長(zhǎng)3第十章排隊(duì)論.服務(wù)系統(tǒng)顧客:機(jī)器、飛機(jī)、輪船、第十章排隊(duì)論問(wèn)題是:

到達(dá)間隔、服務(wù)時(shí)間均為隨機(jī)變量，這也是隨機(jī)服務(wù)系統(tǒng)的基本特征。所以難以確定系統(tǒng)狀態(tài)，只能求期望值。我們希望借助隨機(jī)服務(wù)系統(tǒng)理論來(lái)揭示這些規(guī)律。4第十章排隊(duì)論問(wèn)題是:4第十章排隊(duì)論

例：某港口裝卸臺(tái)負(fù)責(zé)貨輪裝卸工作，貨輪即顧客以某固定周期間隔到達(dá)港口，比如每隔a=6小時(shí)到達(dá)一艘，而裝卸臺(tái)卸貨需要一段時(shí)間，假定它對(duì)每艘貨輪的服務(wù)時(shí)間也是定長(zhǎng)的，比如每艘需卸時(shí)間為s=4小時(shí)。這一服務(wù)系統(tǒng)的特征是到達(dá)和服務(wù)時(shí)間均是確定不變的定長(zhǎng)。結(jié)論：如果s<a,則服務(wù)員的空閑時(shí)間為總時(shí)間的倍；如果s=a，則服務(wù)員得到充分利用，且無(wú)貨輪等待；如果s>a，則形成等待卸貨隊(duì)伍，且隊(duì)長(zhǎng)不斷增加。5第十章排隊(duì)論例：某港口裝卸臺(tái)負(fù)責(zé)貨輪裝卸工作第十章排隊(duì)論.如果貨輪到達(dá)時(shí)間間隔是隨機(jī)變量,碼頭卸貨時(shí)間也為隨機(jī)變量,則構(gòu)成一個(gè)隨機(jī)服務(wù)系統(tǒng)。即便貨輪到達(dá)時(shí)間間隔的平均時(shí)間還為6小時(shí)，但每一個(gè)間隔時(shí)間Xi（i=1、2……）并不都是6小時(shí)，只是指：同理，平均服務(wù)時(shí)間為4小時(shí)，從而會(huì)產(chǎn)生排隊(duì)或服務(wù)空閑時(shí)間。但事先無(wú)法確定。6第十章排隊(duì)論.如果貨輪到達(dá)時(shí)間間隔是隨機(jī)變量,第十章排隊(duì)論對(duì)于隨機(jī)服務(wù)系統(tǒng)希望知道：1、在系統(tǒng)中平均隊(duì)長(zhǎng)L——從長(zhǎng)遠(yuǎn)來(lái)看，平均等待服務(wù)加上正接受服務(wù)的貨輪期望數(shù)；2、在隊(duì)中平均隊(duì)長(zhǎng)Lq——從長(zhǎng)遠(yuǎn)來(lái)看，平均等待服務(wù)的貨輪期望數(shù)；3、系統(tǒng)中平均逗留時(shí)間——從長(zhǎng)遠(yuǎn)看，任一進(jìn)入系統(tǒng)貨輪用于等待服務(wù)加上接受服務(wù)的期望時(shí)間；4、在隊(duì)中平均等待時(shí)間——從長(zhǎng)遠(yuǎn)看，任一進(jìn)入系統(tǒng)貨輪用于等待服務(wù)的期望時(shí)間。7第十章排隊(duì)論對(duì)于隨機(jī)服務(wù)系統(tǒng)希望知道：7第十章排隊(duì)論一、服務(wù)系統(tǒng)的結(jié)構(gòu)假如將要求服務(wù)的對(duì)象統(tǒng)稱(chēng)為“顧客”，進(jìn)行服務(wù)的統(tǒng)稱(chēng)為“服務(wù)機(jī)構(gòu)”或“服務(wù)員”，一個(gè)排隊(duì)系統(tǒng)就能抽象地描述為：為了獲得某種服務(wù)而到達(dá)的顧客，若不能立即獲得服務(wù)，而又允許排隊(duì)等待，則加入等待隊(duì)伍，獲得服務(wù)之后離開(kāi)系統(tǒng)。作為服務(wù)系統(tǒng)基本上由三個(gè)部分組成：8第十章排隊(duì)論一、服務(wù)系統(tǒng)的結(jié)構(gòu)8第十章排隊(duì)論1、輸入過(guò)程刻劃顧客按怎樣的規(guī)律到達(dá)服務(wù)系統(tǒng)，主要有以下幾方面：1）顧客總體（顧客源）數(shù)可能是有限的（例廠內(nèi)故障設(shè)備數(shù)）也可能是無(wú)限的（到達(dá)售票窗口前的顧客總體）；2）顧客可能是單個(gè)到達(dá)，也可能是成批到達(dá)；3）顧客相繼到達(dá)的間隔時(shí)間分布可以是確定型，也可以是隨機(jī)型；4）顧客的到達(dá)可以是相互獨(dú)立的，即以前的到達(dá)情況對(duì)以后顧客的到來(lái)沒(méi)有影響；9第十章排隊(duì)論1、輸入過(guò)程刻劃顧第十章排隊(duì)論5）輸入過(guò)程可以是平穩(wěn)的（指描述相繼到達(dá)的間隔時(shí)間分布和所含參數(shù)（如）都與時(shí)間無(wú)關(guān)，否則稱(chēng)為非平穩(wěn)的；6）具有不耐煩顧客的輸入a）棄長(zhǎng)隊(duì)而去b）排隊(duì)太久而去c）轉(zhuǎn)隊(duì)10第十章排隊(duì)論5）輸入過(guò)程可以是平穩(wěn)的（指描述相第十章排隊(duì)論2、排隊(duì)規(guī)則（到達(dá)的顧客按什么樣的規(guī)則接受服務(wù)）1）損失制即服務(wù)臺(tái)一旦占用，顧客隨即離去；2）等待制顧客到達(dá)后須等待服務(wù)，服務(wù)次序?yàn)椋篴）先到先服務(wù)b）后到先服務(wù)c）隨機(jī)服務(wù)d）有優(yōu)先權(quán)的服務(wù)3）混合制（損失制與等待制的混合）a）隊(duì)長(zhǎng)有限制的情形隊(duì)長(zhǎng)<k，排隊(duì);隊(duì)長(zhǎng)>k，離去11第十章排隊(duì)論2、排隊(duì)規(guī)則（到達(dá)的顧客按什么樣的第十章排隊(duì)論b）等待（或逗留）時(shí)間有限制的情形排隊(duì)時(shí)間>t0,離去;反之排下去4)從隊(duì)伍的數(shù)目看,可以是單列,也可以是多列a)顧客可轉(zhuǎn)移;b)顧客不可轉(zhuǎn)移;12第十章排隊(duì)論b）等待（或逗留）時(shí)間有限制的情形第十章排隊(duì)論3、服務(wù)機(jī)構(gòu)1）服務(wù)員的數(shù)目串列、并列、串并混合2）服務(wù)方式對(duì)單個(gè)顧客服務(wù)或?qū)Τ膳櫩头?wù)3）服務(wù)時(shí)間分確定型和隨機(jī)型服務(wù)時(shí)間13第十章排隊(duì)論3、服務(wù)機(jī)構(gòu)13第十章排隊(duì)論二、表示排隊(duì)模型的符號(hào)D.G.Kendall于1953年提出排隊(duì)符號(hào):(i/j/c)i:到達(dá)過(guò)程的分布;j:服務(wù)過(guò)程分布;c:服務(wù)員數(shù)到了1971年進(jìn)一步定為：(到達(dá)分布/服務(wù)分布/服務(wù)員數(shù)/系統(tǒng)容量/顧客源/排隊(duì)規(guī)則)(M/M/1/∞/∞/FCFS)常規(guī)表示法為(M/M/1)14第十章排隊(duì)論二、表示排隊(duì)模型的符號(hào)(到達(dá)分布/第十章排隊(duì)論三、排隊(duì)模型中常用參數(shù)：到達(dá)速度（單位時(shí)間到達(dá)顧客數(shù)）；：服務(wù)速度（單位時(shí)間服務(wù)完成數(shù)）；1/：相繼顧客到達(dá)的平均間隔時(shí)間；1/：一個(gè)顧客的平均服務(wù)時(shí)間；=（1/：1/）=/稱(chēng)為服務(wù)強(qiáng)度，指相同時(shí)間區(qū)間內(nèi)顧客到達(dá)的平均數(shù)與能被服務(wù)完的平均顧客數(shù)之比；15第十章排隊(duì)論三、排隊(duì)模型中常用參數(shù)15第十章排隊(duì)論四、系統(tǒng)的穩(wěn)態(tài)性態(tài)1、j——穩(wěn)態(tài)概率j定義為穩(wěn)態(tài)系統(tǒng)中有j個(gè)顧客（包括正在服務(wù)的）的概率。0=1-——稱(chēng)為系統(tǒng)空閑的概率16第十章排隊(duì)論四、系統(tǒng)的穩(wěn)態(tài)性態(tài)0=1-第十章排隊(duì)論2、3、4、5、17第十章排隊(duì)論2、17第十章排隊(duì)論6、7、進(jìn)入系統(tǒng)的顧客逗留時(shí)間超過(guò)t的概率。進(jìn)入系統(tǒng)的顧客等待時(shí)間超過(guò)t的概率。18第十章排隊(duì)論進(jìn)入系統(tǒng)的顧客逗留時(shí)間超過(guò)t的概率第十章排隊(duì)論五、穩(wěn)態(tài)性態(tài)中各量值的分析1、=/的意義1）平均到達(dá)速度與平均服務(wù)速度之比；2）服務(wù)員利用率=1-03）一個(gè)平均服務(wù)時(shí)間內(nèi)到達(dá)的顧客平均數(shù)19第十章排隊(duì)論五、穩(wěn)態(tài)性態(tài)中各量值的分析19第十章排隊(duì)論4）正在接受服務(wù)的顧客平均數(shù)=0×0+1×（1-0）2、L與Lq的關(guān)系表示系統(tǒng)中平均人數(shù)等于隊(duì)中平均人數(shù)加上正在接受服務(wù)顧客平均人數(shù)。20第十章排隊(duì)論4）正在接受服務(wù)的顧客平均數(shù)表示系第十章排隊(duì)論3、系統(tǒng)逗留時(shí)間減排隊(duì)時(shí)間恰為服務(wù)時(shí)間的期望值。21第十章排隊(duì)論3、系統(tǒng)逗留時(shí)間減排隊(duì)時(shí)間恰為服務(wù)第十章排隊(duì)論4、22第十章排隊(duì)論4、22第十章排隊(duì)論5、23第十章排隊(duì)論5、23第十章排隊(duì)論§10.2M/M/1模型實(shí)例例1、某廠有幾千名工人，醫(yī)務(wù)室平均每小時(shí)約有4位工人來(lái)看病，醫(yī)生每小時(shí)平均診斷約5個(gè)病人，若到達(dá)時(shí)間間隔服從普阿松（Pisson）分布，服務(wù)時(shí)間服從負(fù)指數(shù)分布，試分析該系統(tǒng)。解：本例屬標(biāo)準(zhǔn)(M/M/1/∞/∞/FCFS)問(wèn)題，已知=4人/小時(shí)；=5人/小時(shí)，=/=4/5=0.8系統(tǒng)隊(duì)長(zhǎng)L=/(1-)=0.8/(1-0.8)=4人;平均4人排隊(duì)和看病隊(duì)長(zhǎng)Lq=2/(1-)=0.82/(1-0.8)=3.2人;平均有3.2人在排隊(duì)或Lq=L-=4-0.8=3.2人24第十章排隊(duì)論§10.2M/M/1模型實(shí)例第十章排隊(duì)論工人在醫(yī)務(wù)室平均逗留時(shí)間：病人平均在醫(yī)務(wù)室內(nèi)排隊(duì)和看病時(shí)間約為1小時(shí)。工人在醫(yī)務(wù)室平均排隊(duì)時(shí)間：病人平均在醫(yī)務(wù)室內(nèi)排隊(duì)時(shí)間約為0.8小時(shí)。25第十章排隊(duì)論工人在醫(yī)務(wù)室平均逗留時(shí)間：病人平均第十章排隊(duì)論系統(tǒng)空閑概率0=1-=1-0.8=0.2系統(tǒng)忙的概率1-0==0.8以該廠每天工作8小時(shí)計(jì),則每天平均來(lái)看病的人數(shù)為:L總=8=8×4=32人/天;全體病人每天平均等待看病所化時(shí)間為:W總=病人逗留時(shí)間和排隊(duì)超過(guò)1小時(shí)的概率分別為：26第十章排隊(duì)論系統(tǒng)空閑概率0=1-=1-0第十章排隊(duì)論若要計(jì)算系統(tǒng)中大于10個(gè)病人的概率,則:n>10=11=0.811=0.086即醫(yī)務(wù)室中大于10個(gè)病人的概率僅為8.6%醫(yī)務(wù)室中病員大于K的概率27第十章排隊(duì)論醫(yī)務(wù)室中病員大于K的概率27第十章排隊(duì)論例2、某電機(jī)修理車(chē)間，每天平均有2臺(tái)電機(jī)到達(dá)修理。負(fù)責(zé)修理的是1名修理工，平均每3小時(shí)修完1臺(tái)。若到達(dá)為泊松分布，修理時(shí)間為負(fù)指數(shù)分布，求1臺(tái)電機(jī)從到達(dá)到修理完畢的平均時(shí)間及修理工人每天的平均空閑時(shí)間（每天以8小時(shí)計(jì)）解：本問(wèn)題屬(M/M/1/∞/∞/FCFS)模式到達(dá)速度=2臺(tái)/8小時(shí)=1/4臺(tái)/小時(shí)服務(wù)速度=1臺(tái)/3小時(shí)=1/3臺(tái)/小時(shí)=/=1/4/1/3=3/4<128第十章排隊(duì)論例2、某電機(jī)修理車(chē)間，每天平均有2第十章排隊(duì)論一臺(tái)電機(jī)從到達(dá)到修理完畢的平均時(shí)間為：一臺(tái)電機(jī)排隊(duì)的平均時(shí)間為：29第十章排隊(duì)論一臺(tái)電機(jī)從到達(dá)到修理完畢的平均時(shí)間第十章排隊(duì)論服務(wù)員空閑概率0=1-=1-3/4=1/4每天空閑時(shí)間=1/4×8=2小時(shí)/天系統(tǒng)中平均人數(shù)L=/(1-)=3/4/1/4)=3人系統(tǒng)中平均隊(duì)長(zhǎng)Lq=2/(1-)=3/42/1/4=9/4人30第十章排隊(duì)論服務(wù)員空閑概率0=1-=1-第十章排隊(duì)論例3、某裝卸臺(tái)裝卸設(shè)備的設(shè)計(jì)方案中，有三個(gè)方案可供選擇，有關(guān)費(fèi)用見(jiàn)下表：方案每天固定費(fèi)用Fi（元）每天可變操作費(fèi)Vi（元）每小時(shí)裝卸率μi（袋）1601001000213015020003250200600031第十章排隊(duì)論例3、某裝卸臺(tái)裝卸設(shè)備的設(shè)計(jì)方案中第十章排隊(duì)論

設(shè)貨車(chē)按Poisson流到達(dá)，平均每天（按10小時(shí)計(jì)算）到達(dá)15車(chē)，每車(chē)平均裝貨500袋，卸裝時(shí)間遵從負(fù)指數(shù)分布，每輛車(chē)停留一小時(shí)的損失費(fèi)為10元，問(wèn)該選擇哪個(gè)方案？解：本系同屬M(fèi)/M/1模型平均到達(dá)率=15/10=1.5車(chē)/小時(shí)服務(wù)率1=(1000袋/小時(shí))/(500袋/車(chē))=2車(chē)/小時(shí)或=1.5×500=750袋/小時(shí);1=(1000袋/小時(shí))32第十章排隊(duì)論設(shè)貨車(chē)按Poiss第十章排隊(duì)論33第十章排隊(duì)論33第十章排隊(duì)論.一輛車(chē)在系統(tǒng)中的平均停留時(shí)間為:34第十章排隊(duì)論.一輛車(chē)在系統(tǒng)中的平均停留時(shí)間為:第十章排隊(duì)論

因此,每天貨車(chē)在系統(tǒng)里逗留時(shí)間的平均損失費(fèi)為:35第十章排隊(duì)論因此,每天貨車(chē)在系統(tǒng)第十章排隊(duì)論服務(wù)強(qiáng)度：每天實(shí)際可變費(fèi)用：36第十章排隊(duì)論服務(wù)強(qiáng)度：每天實(shí)際可變費(fèi)用：36第十章排隊(duì)論.各方案總費(fèi)用:方案固定費(fèi)用Fi(元)可變費(fèi)用Vi(元)逗留費(fèi)用(元)總費(fèi)用(元)16075300435213056.256024632502514.25289.25結(jié)論:應(yīng)選方案2。37第十章排隊(duì)論.各方案總費(fèi)用:方案固定費(fèi)用第十章排隊(duì)論§10.3容量有限的M/M/1/K/∞/FCFS模型本模型與前相比為系統(tǒng)容量有限。若在某一時(shí)刻有一顧客到達(dá)時(shí)，如系統(tǒng)中已有K個(gè)顧客，那個(gè)顧客就被拒絕進(jìn)入系統(tǒng)當(dāng)系統(tǒng)已滿(mǎn)（N=K），則到達(dá)率=0，所以有必要找出有效的到達(dá)率ee=（1-Pk）38第十章排隊(duì)論§10.3容量有限的M/M/1/K第十章排隊(duì)論

系統(tǒng)的狀態(tài)概率：39第十章排隊(duì)論第十章排隊(duì)論40第十章排隊(duì)論40第十章排隊(duì)論例4、某美容院有6個(gè)椅子接待顧客等待理發(fā)。當(dāng)6個(gè)椅子都坐滿(mǎn)時(shí)，后到的顧客就被拒絕。顧客到達(dá)時(shí)間服從負(fù)指數(shù)分布，平均到達(dá)率為3人/小時(shí)，每人的理發(fā)時(shí)間也服從負(fù)指數(shù)分布，平均需要5分鐘。試分析這一系統(tǒng)。解（k=76人排隊(duì)，1人接受服務(wù)）這是M/M/1/7/∞/FCFS系統(tǒng)，=3人/小時(shí)，=4人/小時(shí)1、求某顧客一到美容院就理發(fā)的概率，即求系統(tǒng)空閑概率41第十章排隊(duì)論例4、某美容院有6個(gè)椅子接待顧客等第十章排隊(duì)論.2、求系統(tǒng)逗留顧客人數(shù)及排隊(duì)人數(shù)42第十章排隊(duì)論.2、求系統(tǒng)逗留顧客人數(shù)及排隊(duì)人數(shù)第十章排隊(duì)論.3、求有效到達(dá)率4、求每一顧客在美容院內(nèi)逗留時(shí)間的期望值5、求每一顧客在美容院排隊(duì)時(shí)間的期望值43第十章排隊(duì)論.3、求有效到達(dá)率4、求每一顧客在第十章排隊(duì)論.6、求系統(tǒng)客滿(mǎn)時(shí)顧客流失率44第十章排隊(duì)論.6、求系統(tǒng)客滿(mǎn)時(shí)顧客流失率44第十章排隊(duì)論例5、某汽車(chē)加油車(chē)站只有一臺(tái)加油泵，且場(chǎng)地最多只能容納三輛車(chē)，當(dāng)站內(nèi)場(chǎng)地占滿(mǎn)時(shí)，到達(dá)的汽車(chē)只能去別處加油。汽車(chē)到達(dá)間隔時(shí)間服從普阿松分布，其中均值為每8分鐘一輛。服務(wù)時(shí)間間隔服從負(fù)指數(shù)分布，其平均值為4分鐘一輛。加油站有機(jī)會(huì)租賃毗鄰的一塊空地，以供多停放一輛前來(lái)加油的車(chē)（無(wú)加油泵），租地費(fèi)用為每周1000元，每周從每個(gè)顧客那里期望凈收益是50元，這個(gè)站每天開(kāi)放10小時(shí)，問(wèn)租賃空地是否有利？45第十章排隊(duì)論例5、某汽車(chē)加油車(chē)站只有一臺(tái)加油泵第十章排隊(duì)論.解:本系統(tǒng)屬M(fèi)/M/1/3/∞/FCFS模型已知:=60/8=7.5輛/小時(shí);=60/4=15輛/小時(shí)=/=7.5/15=0.51、系統(tǒng)空閑概率46第十章排隊(duì)論.解:本系統(tǒng)屬M(fèi)/M/1/3/∞/第十章排隊(duì)論.

2、求系統(tǒng)逗留顧客人數(shù)及排隊(duì)人數(shù)3、求有效到達(dá)率47第十章排隊(duì)論.2、求系統(tǒng)逗留顧客人數(shù)及排隊(duì)人數(shù)第十章排隊(duì)論4、求每一輛車(chē)在加油站內(nèi)逗留時(shí)間的期望值5、求每一輛車(chē)在加油站內(nèi)排隊(duì)時(shí)間的期望值48第十章排隊(duì)論4、求每一輛車(chē)在加油站內(nèi)逗留時(shí)間的第十章排隊(duì)論6、求系統(tǒng)客滿(mǎn)時(shí)車(chē)輛流失率7.逗留時(shí)間超過(guò)半小時(shí)的概率P{WS>0.5}=e-(1-)t=e-4(1-0.5)0.5=0.367849第十章排隊(duì)論6、求系統(tǒng)客滿(mǎn)時(shí)車(chē)輛流失率7.逗留第十章排隊(duì)論若是租賃場(chǎng)地，則新系統(tǒng)變?yōu)椋篗/M/1/3/∞/FCFS模型此時(shí)顧客流失率為：加油站每周將增加服務(wù)車(chē)輛數(shù)為：50第十章排隊(duì)論若是租賃場(chǎng)地，則新系統(tǒng)變?yōu)椋篗/M第十章排隊(duì)論每周將增加收入為：50元/輛×18.38輛/周=919元<1000元/周由于增加的收入不足以支付每周的場(chǎng)地租賃費(fèi),所以租賃空地不經(jīng)濟(jì)。51第十章排隊(duì)論每周將增加收入為：515252

第十章排隊(duì)論53第十章1第十章排隊(duì)論§10.1概述排隊(duì)論（QueingTheory）也稱(chēng)隨機(jī)服務(wù)系統(tǒng)。任何一個(gè)服務(wù)系統(tǒng)均由客體和主體組成。前者是要求服務(wù)的對(duì)象，我們一律稱(chēng)之為“顧客”；后者是提供服務(wù)的機(jī)構(gòu)或人員，一律稱(chēng)之為“服務(wù)員”。顧客可泛指機(jī)器、病人、飛機(jī)、輪船等，服務(wù)員可泛指機(jī)修工、醫(yī)生、碼頭等。54第十章排隊(duì)論§10.1概述2第十章排隊(duì)論.服務(wù)系統(tǒng)顧客:機(jī)器、飛機(jī)、輪船、病人……顧客到達(dá)——等待服務(wù)——接受服務(wù)——顧客離去服務(wù)員：機(jī)修工、碼頭設(shè)備、醫(yī)生……到達(dá)時(shí)間>服務(wù)時(shí)間系統(tǒng)空閑到達(dá)時(shí)間=服務(wù)時(shí)間充分利用,無(wú)排隊(duì)到達(dá)時(shí)間<服務(wù)時(shí)間排隊(duì)越來(lái)越長(zhǎng)55第十章排隊(duì)論.服務(wù)系統(tǒng)顧客:機(jī)器、飛機(jī)、輪船、第十章排隊(duì)論問(wèn)題是:

到達(dá)間隔、服務(wù)時(shí)間均為隨機(jī)變量，這也是隨機(jī)服務(wù)系統(tǒng)的基本特征。所以難以確定系統(tǒng)狀態(tài)，只能求期望值。我們希望借助隨機(jī)服務(wù)系統(tǒng)理論來(lái)揭示這些規(guī)律。56第十章排隊(duì)論問(wèn)題是:4第十章排隊(duì)論

例：某港口裝卸臺(tái)負(fù)責(zé)貨輪裝卸工作，貨輪即顧客以某固定周期間隔到達(dá)港口，比如每隔a=6小時(shí)到達(dá)一艘，而裝卸臺(tái)卸貨需要一段時(shí)間，假定它對(duì)每艘貨輪的服務(wù)時(shí)間也是定長(zhǎng)的，比如每艘需卸時(shí)間為s=4小時(shí)。這一服務(wù)系統(tǒng)的特征是到達(dá)和服務(wù)時(shí)間均是確定不變的定長(zhǎng)。結(jié)論：如果s<a,則服務(wù)員的空閑時(shí)間為總時(shí)間的倍；如果s=a，則服務(wù)員得到充分利用，且無(wú)貨輪等待；如果s>a，則形成等待卸貨隊(duì)伍，且隊(duì)長(zhǎng)不斷增加。57第十章排隊(duì)論例：某港口裝卸臺(tái)負(fù)責(zé)貨輪裝卸工作第十章排隊(duì)論.如果貨輪到達(dá)時(shí)間間隔是隨機(jī)變量,碼頭卸貨時(shí)間也為隨機(jī)變量,則構(gòu)成一個(gè)隨機(jī)服務(wù)系統(tǒng)。即便貨輪到達(dá)時(shí)間間隔的平均時(shí)間還為6小時(shí)，但每一個(gè)間隔時(shí)間Xi（i=1、2……）并不都是6小時(shí)，只是指：同理，平均服務(wù)時(shí)間為4小時(shí)，從而會(huì)產(chǎn)生排隊(duì)或服務(wù)空閑時(shí)間。但事先無(wú)法確定。58第十章排隊(duì)論.如果貨輪到達(dá)時(shí)間間隔是隨機(jī)變量,第十章排隊(duì)論對(duì)于隨機(jī)服務(wù)系統(tǒng)希望知道：1、在系統(tǒng)中平均隊(duì)長(zhǎng)L——從長(zhǎng)遠(yuǎn)來(lái)看，平均等待服務(wù)加上正接受服務(wù)的貨輪期望數(shù)；2、在隊(duì)中平均隊(duì)長(zhǎng)Lq——從長(zhǎng)遠(yuǎn)來(lái)看，平均等待服務(wù)的貨輪期望數(shù)；3、系統(tǒng)中平均逗留時(shí)間——從長(zhǎng)遠(yuǎn)看，任一進(jìn)入系統(tǒng)貨輪用于等待服務(wù)加上接受服務(wù)的期望時(shí)間；4、在隊(duì)中平均等待時(shí)間——從長(zhǎng)遠(yuǎn)看，任一進(jìn)入系統(tǒng)貨輪用于等待服務(wù)的期望時(shí)間。59第十章排隊(duì)論對(duì)于隨機(jī)服務(wù)系統(tǒng)希望知道：7第十章排隊(duì)論一、服務(wù)系統(tǒng)的結(jié)構(gòu)假如將要求服務(wù)的對(duì)象統(tǒng)稱(chēng)為“顧客”，進(jìn)行服務(wù)的統(tǒng)稱(chēng)為“服務(wù)機(jī)構(gòu)”或“服務(wù)員”，一個(gè)排隊(duì)系統(tǒng)就能抽象地描述為：為了獲得某種服務(wù)而到達(dá)的顧客，若不能立即獲得服務(wù)，而又允許排隊(duì)等待，則加入等待隊(duì)伍，獲得服務(wù)之后離開(kāi)系統(tǒng)。作為服務(wù)系統(tǒng)基本上由三個(gè)部分組成：60第十章排隊(duì)論一、服務(wù)系統(tǒng)的結(jié)構(gòu)8第十章排隊(duì)論1、輸入過(guò)程刻劃顧客按怎樣的規(guī)律到達(dá)服務(wù)系統(tǒng)，主要有以下幾方面：1）顧客總體（顧客源）數(shù)可能是有限的（例廠內(nèi)故障設(shè)備數(shù)）也可能是無(wú)限的（到達(dá)售票窗口前的顧客總體）；2）顧客可能是單個(gè)到達(dá)，也可能是成批到達(dá)；3）顧客相繼到達(dá)的間隔時(shí)間分布可以是確定型，也可以是隨機(jī)型；4）顧客的到達(dá)可以是相互獨(dú)立的，即以前的到達(dá)情況對(duì)以后顧客的到來(lái)沒(méi)有影響；61第十章排隊(duì)論1、輸入過(guò)程刻劃顧第十章排隊(duì)論5）輸入過(guò)程可以是平穩(wěn)的（指描述相繼到達(dá)的間隔時(shí)間分布和所含參數(shù)（如）都與時(shí)間無(wú)關(guān)，否則稱(chēng)為非平穩(wěn)的；6）具有不耐煩顧客的輸入a）棄長(zhǎng)隊(duì)而去b）排隊(duì)太久而去c）轉(zhuǎn)隊(duì)62第十章排隊(duì)論5）輸入過(guò)程可以是平穩(wěn)的（指描述相第十章排隊(duì)論2、排隊(duì)規(guī)則（到達(dá)的顧客按什么樣的規(guī)則接受服務(wù)）1）損失制即服務(wù)臺(tái)一旦占用，顧客隨即離去；2）等待制顧客到達(dá)后須等待服務(wù)，服務(wù)次序?yàn)椋篴）先到先服務(wù)b）后到先服務(wù)c）隨機(jī)服務(wù)d）有優(yōu)先權(quán)的服務(wù)3）混合制（損失制與等待制的混合）a）隊(duì)長(zhǎng)有限制的情形隊(duì)長(zhǎng)<k，排隊(duì);隊(duì)長(zhǎng)>k，離去63第十章排隊(duì)論2、排隊(duì)規(guī)則（到達(dá)的顧客按什么樣的第十章排隊(duì)論b）等待（或逗留）時(shí)間有限制的情形排隊(duì)時(shí)間>t0,離去;反之排下去4)從隊(duì)伍的數(shù)目看,可以是單列,也可以是多列a)顧客可轉(zhuǎn)移;b)顧客不可轉(zhuǎn)移;64第十章排隊(duì)論b）等待（或逗留）時(shí)間有限制的情形第十章排隊(duì)論3、服務(wù)機(jī)構(gòu)1）服務(wù)員的數(shù)目串列、并列、串并混合2）服務(wù)方式對(duì)單個(gè)顧客服務(wù)或?qū)Τ膳櫩头?wù)3）服務(wù)時(shí)間分確定型和隨機(jī)型服務(wù)時(shí)間65第十章排隊(duì)論3、服務(wù)機(jī)構(gòu)13第十章排隊(duì)論二、表示排隊(duì)模型的符號(hào)D.G.Kendall于1953年提出排隊(duì)符號(hào):(i/j/c)i:到達(dá)過(guò)程的分布;j:服務(wù)過(guò)程分布;c:服務(wù)員數(shù)到了1971年進(jìn)一步定為：(到達(dá)分布/服務(wù)分布/服務(wù)員數(shù)/系統(tǒng)容量/顧客源/排隊(duì)規(guī)則)(M/M/1/∞/∞/FCFS)常規(guī)表示法為(M/M/1)66第十章排隊(duì)論二、表示排隊(duì)模型的符號(hào)(到達(dá)分布/第十章排隊(duì)論三、排隊(duì)模型中常用參數(shù)：到達(dá)速度（單位時(shí)間到達(dá)顧客數(shù)）；：服務(wù)速度（單位時(shí)間服務(wù)完成數(shù)）；1/：相繼顧客到達(dá)的平均間隔時(shí)間；1/：一個(gè)顧客的平均服務(wù)時(shí)間；=（1/：1/）=/稱(chēng)為服務(wù)強(qiáng)度，指相同時(shí)間區(qū)間內(nèi)顧客到達(dá)的平均數(shù)與能被服務(wù)完的平均顧客數(shù)之比；67第十章排隊(duì)論三、排隊(duì)模型中常用參數(shù)15第十章排隊(duì)論四、系統(tǒng)的穩(wěn)態(tài)性態(tài)1、j——穩(wěn)態(tài)概率j定義為穩(wěn)態(tài)系統(tǒng)中有j個(gè)顧客（包括正在服務(wù)的）的概率。0=1-——稱(chēng)為系統(tǒng)空閑的概率68第十章排隊(duì)論四、系統(tǒng)的穩(wěn)態(tài)性態(tài)0=1-第十章排隊(duì)論2、3、4、5、69第十章排隊(duì)論2、17第十章排隊(duì)論6、7、進(jìn)入系統(tǒng)的顧客逗留時(shí)間超過(guò)t的概率。進(jìn)入系統(tǒng)的顧客等待時(shí)間超過(guò)t的概率。70第十章排隊(duì)論進(jìn)入系統(tǒng)的顧客逗留時(shí)間超過(guò)t的概率第十章排隊(duì)論五、穩(wěn)態(tài)性態(tài)中各量值的分析1、=/的意義1）平均到達(dá)速度與平均服務(wù)速度之比；2）服務(wù)員利用率=1-03）一個(gè)平均服務(wù)時(shí)間內(nèi)到達(dá)的顧客平均數(shù)71第十章排隊(duì)論五、穩(wěn)態(tài)性態(tài)中各量值的分析19第十章排隊(duì)論4）正在接受服務(wù)的顧客平均數(shù)=0×0+1×（1-0）2、L與Lq的關(guān)系表示系統(tǒng)中平均人數(shù)等于隊(duì)中平均人數(shù)加上正在接受服務(wù)顧客平均人數(shù)。72第十章排隊(duì)論4）正在接受服務(wù)的顧客平均數(shù)表示系第十章排隊(duì)論3、系統(tǒng)逗留時(shí)間減排隊(duì)時(shí)間恰為服務(wù)時(shí)間的期望值。73第十章排隊(duì)論3、系統(tǒng)逗留時(shí)間減排隊(duì)時(shí)間恰為服務(wù)第十章排隊(duì)論4、74第十章排隊(duì)論4、22第十章排隊(duì)論5、75第十章排隊(duì)論5、23第十章排隊(duì)論§10.2M/M/1模型實(shí)例例1、某廠有幾千名工人，醫(yī)務(wù)室平均每小時(shí)約有4位工人來(lái)看病，醫(yī)生每小時(shí)平均診斷約5個(gè)病人，若到達(dá)時(shí)間間隔服從普阿松（Pisson）分布，服務(wù)時(shí)間服從負(fù)指數(shù)分布，試分析該系統(tǒng)。解：本例屬標(biāo)準(zhǔn)(M/M/1/∞/∞/FCFS)問(wèn)題，已知=4人/小時(shí)；=5人/小時(shí)，=/=4/5=0.8系統(tǒng)隊(duì)長(zhǎng)L=/(1-)=0.8/(1-0.8)=4人;平均4人排隊(duì)和看病隊(duì)長(zhǎng)Lq=2/(1-)=0.82/(1-0.8)=3.2人;平均有3.2人在排隊(duì)或Lq=L-=4-0.8=3.2人76第十章排隊(duì)論§10.2M/M/1模型實(shí)例第十章排隊(duì)論工人在醫(yī)務(wù)室平均逗留時(shí)間：病人平均在醫(yī)務(wù)室內(nèi)排隊(duì)和看病時(shí)間約為1小時(shí)。工人在醫(yī)務(wù)室平均排隊(duì)時(shí)間：病人平均在醫(yī)務(wù)室內(nèi)排隊(duì)時(shí)間約為0.8小時(shí)。77第十章排隊(duì)論工人在醫(yī)務(wù)室平均逗留時(shí)間：病人平均第十章排隊(duì)論系統(tǒng)空閑概率0=1-=1-0.8=0.2系統(tǒng)忙的概率1-0==0.8以該廠每天工作8小時(shí)計(jì),則每天平均來(lái)看病的人數(shù)為:L總=8=8×4=32人/天;全體病人每天平均等待看病所化時(shí)間為:W總=病人逗留時(shí)間和排隊(duì)超過(guò)1小時(shí)的概率分別為：78第十章排隊(duì)論系統(tǒng)空閑概率0=1-=1-0第十章排隊(duì)論若要計(jì)算系統(tǒng)中大于10個(gè)病人的概率,則:n>10=11=0.811=0.086即醫(yī)務(wù)室中大于10個(gè)病人的概率僅為8.6%醫(yī)務(wù)室中病員大于K的概率79第十章排隊(duì)論醫(yī)務(wù)室中病員大于K的概率27第十章排隊(duì)論例2、某電機(jī)修理車(chē)間，每天平均有2臺(tái)電機(jī)到達(dá)修理。負(fù)責(zé)修理的是1名修理工，平均每3小時(shí)修完1臺(tái)。若到達(dá)為泊松分布，修理時(shí)間為負(fù)指數(shù)分布，求1臺(tái)電機(jī)從到達(dá)到修理完畢的平均時(shí)間及修理工人每天的平均空閑時(shí)間（每天以8小時(shí)計(jì)）解：本問(wèn)題屬(M/M/1/∞/∞/FCFS)模式到達(dá)速度=2臺(tái)/8小時(shí)=1/4臺(tái)/小時(shí)服務(wù)速度=1臺(tái)/3小時(shí)=1/3臺(tái)/小時(shí)=/=1/4/1/3=3/4<180第十章排隊(duì)論例2、某電機(jī)修理車(chē)間，每天平均有2第十章排隊(duì)論一臺(tái)電機(jī)從到達(dá)到修理完畢的平均時(shí)間為：一臺(tái)電機(jī)排隊(duì)的平均時(shí)間為：81第十章排隊(duì)論一臺(tái)電機(jī)從到達(dá)到修理完畢的平均時(shí)間第十章排隊(duì)論服務(wù)員空閑概率0=1-=1-3/4=1/4每天空閑時(shí)間=1/4×8=2小時(shí)/天系統(tǒng)中平均人數(shù)L=/(1-)=3/4/1/4)=3人系統(tǒng)中平均隊(duì)長(zhǎng)Lq=2/(1-)=3/42/1/4=9/4人82第十章排隊(duì)論服務(wù)員空閑概率0=1-=1-第十章排隊(duì)論例3、某裝卸臺(tái)裝卸設(shè)備的設(shè)計(jì)方案中，有三個(gè)方案可供選擇，有關(guān)費(fèi)用見(jiàn)下表：方案每天固定費(fèi)用Fi（元）每天可變操作費(fèi)Vi（元）每小時(shí)裝卸率μi（袋）1601001000213015020003250200600083第十章排隊(duì)論例3、某裝卸臺(tái)裝卸設(shè)備的設(shè)計(jì)方案中第十章排隊(duì)論

設(shè)貨車(chē)按Poisson流到達(dá)，平均每天（按10小時(shí)計(jì)算）到達(dá)15車(chē)，每車(chē)平均裝貨500袋，卸裝時(shí)間遵從負(fù)指數(shù)分布，每輛車(chē)停留一小時(shí)的損失費(fèi)為10元，問(wèn)該選擇哪個(gè)方案？解：本系同屬M(fèi)/M/1模型平均到達(dá)率=15/10=1.5車(chē)/小時(shí)服務(wù)率1=(1000袋/小時(shí))/(500袋/車(chē))=2車(chē)/小時(shí)或=1.5×500=750袋/小時(shí);1=(1000袋/小時(shí))84第十章排隊(duì)論設(shè)貨車(chē)按Poiss第十章排隊(duì)論85第十章排隊(duì)論33第十章排隊(duì)論.一輛車(chē)在系統(tǒng)中的平均停留時(shí)間為:86第十章排隊(duì)論.一輛車(chē)在系統(tǒng)中的平均停留時(shí)間為:第十章排隊(duì)論

因此,每天貨車(chē)在系統(tǒng)里逗留時(shí)間的平均損失費(fèi)為:87第十章排隊(duì)論因此,每天貨車(chē)在系統(tǒng)第十章排隊(duì)論服務(wù)強(qiáng)度：每天實(shí)際可變費(fèi)用：88第十章排隊(duì)論服務(wù)強(qiáng)度：每天實(shí)際可變費(fèi)用：36第十章排隊(duì)論.各方案總費(fèi)用:方案固定費(fèi)用Fi(元)可變費(fèi)用Vi(元)逗留費(fèi)用(元)總費(fèi)用(元)16075300435213056.256024632502514.25289.25結(jié)論:應(yīng)選方案2。89第十章排隊(duì)論.各方案總費(fèi)用:方案固定費(fèi)用第十章排隊(duì)論§10.3容量有限的M/M/1/K/∞/FCFS模型本模型與前相比為系統(tǒng)容量有限。若在某一時(shí)刻有一顧客到達(dá)時(shí)，如系統(tǒng)中已有K個(gè)顧客，那個(gè)顧客就被拒絕進(jìn)入系統(tǒng)當(dāng)系統(tǒng)已滿(mǎn)（N=K），則到達(dá)率=0，所以有必要找出有效的到達(dá)率ee=（1-Pk）90第十章排隊(duì)論§10.3容量有限的M/M/1/K第十章排隊(duì)論

系統(tǒng)的狀態(tài)概率：91第十章排隊(duì)論