管理運(yùn)籌學(xué)第十章排隊(duì)論

1、精選精選ppt1精選精選ppt2 第十章第十章 排隊(duì)論排隊(duì)論精選精選ppt3 10.1概述概述 排隊(duì)論（排隊(duì)論（Queing Theory）也稱隨機(jī)服務(wù)）也稱隨機(jī)服務(wù) 系統(tǒng)。任何一個(gè)服務(wù)系統(tǒng)均由客體和主系統(tǒng)。任何一個(gè)服務(wù)系統(tǒng)均由客體和主 體組成。前者是要求服務(wù)的對(duì)象，我們體組成。前者是要求服務(wù)的對(duì)象，我們 一律稱之為一律稱之為“顧客顧客”；后者是提供服務(wù)；后者是提供服務(wù)的的 機(jī)構(gòu)或人員，一律稱之為機(jī)構(gòu)或人員，一律稱之為“服務(wù)員服務(wù)員”。顧顧 客可泛指機(jī)器、病人、飛機(jī)、輪船等，客可泛指機(jī)器、病人、飛機(jī)、輪船等， 服務(wù)員可泛指機(jī)修工、醫(yī)生、碼頭等。服務(wù)員可泛指機(jī)修工、醫(yī)生、碼頭等。精選精選ppt4

2、 .服務(wù)系統(tǒng)服務(wù)系統(tǒng)顧客顧客:機(jī)器、飛機(jī)、輪船、病人機(jī)器、飛機(jī)、輪船、病人顧客到達(dá)顧客到達(dá)等待服務(wù)等待服務(wù)接受服務(wù)接受服務(wù)顧客離去顧客離去服務(wù)員：機(jī)修工、碼頭設(shè)備、醫(yī)生服務(wù)員：機(jī)修工、碼頭設(shè)備、醫(yī)生到達(dá)時(shí)間到達(dá)時(shí)間服務(wù)時(shí)間服務(wù)時(shí)間 系統(tǒng)空閑系統(tǒng)空閑到達(dá)時(shí)間到達(dá)時(shí)間=服務(wù)時(shí)間服務(wù)時(shí)間 充分利用充分利用,無排隊(duì)無排隊(duì)到達(dá)時(shí)間到達(dá)時(shí)間服務(wù)時(shí)間服務(wù)時(shí)間 排隊(duì)越來越長(zhǎng)排隊(duì)越來越長(zhǎng)精選精選ppt5問題是問題是: 到達(dá)間隔、服務(wù)時(shí)間均為隨到達(dá)間隔、服務(wù)時(shí)間均為隨機(jī)變量，這也是隨機(jī)服務(wù)系統(tǒng)機(jī)變量，這也是隨機(jī)服務(wù)系統(tǒng)的基本特征。所以難以確定系的基本特征。所以難以確定系統(tǒng)狀態(tài)，只能求期望值。我們統(tǒng)狀態(tài)，只能求期望

3、值。我們希望借助隨機(jī)服務(wù)系統(tǒng)理論來希望借助隨機(jī)服務(wù)系統(tǒng)理論來揭示這些規(guī)律。揭示這些規(guī)律。精選精選ppt6 例：某港口裝卸臺(tái)負(fù)責(zé)貨輪裝卸工作，貨輪即顧客以例：某港口裝卸臺(tái)負(fù)責(zé)貨輪裝卸工作，貨輪即顧客以某固定周期間隔到達(dá)港口，比如每隔某固定周期間隔到達(dá)港口，比如每隔a=6a=6小時(shí)到達(dá)一艘，小時(shí)到達(dá)一艘，而裝卸臺(tái)卸貨需要一段時(shí)間，假定它對(duì)每艘貨輪的服而裝卸臺(tái)卸貨需要一段時(shí)間，假定它對(duì)每艘貨輪的服務(wù)時(shí)間也是定長(zhǎng)的，比如每艘需卸時(shí)間為務(wù)時(shí)間也是定長(zhǎng)的，比如每艘需卸時(shí)間為s=4s=4小時(shí)。這小時(shí)。這一服務(wù)系統(tǒng)的特征是到達(dá)和服務(wù)時(shí)間均是確定不變的一服務(wù)系統(tǒng)的特征是到達(dá)和服務(wù)時(shí)間均是確定不變的定長(zhǎng)。定長(zhǎng)。結(jié)

4、論：結(jié)論：如果如果sa,sa，則形成等待卸貨隊(duì)伍，且隊(duì)長(zhǎng)不斷增加。，則形成等待卸貨隊(duì)伍，且隊(duì)長(zhǎng)不斷增加。asa 精選精選ppt7.如果貨輪到達(dá)時(shí)間間隔是隨機(jī)變量如果貨輪到達(dá)時(shí)間間隔是隨機(jī)變量,碼頭卸貨時(shí)間也為隨碼頭卸貨時(shí)間也為隨機(jī)變量機(jī)變量,則構(gòu)成一個(gè)隨機(jī)服務(wù)系統(tǒng)。即便貨輪到達(dá)時(shí)間間則構(gòu)成一個(gè)隨機(jī)服務(wù)系統(tǒng)。即便貨輪到達(dá)時(shí)間間隔的平均時(shí)間還為隔的平均時(shí)間還為6小時(shí)，但每一個(gè)間隔時(shí)間小時(shí)，但每一個(gè)間隔時(shí)間Xi（i=1、2）并不都是）并不都是6小時(shí)，只是指：小時(shí)，只是指：同理，平均服務(wù)時(shí)間為同理，平均服務(wù)時(shí)間為4小時(shí)，從而會(huì)產(chǎn)生排隊(duì)或服務(wù)空小時(shí)，從而會(huì)產(chǎn)生排隊(duì)或服務(wù)空閑時(shí)間。但事先無法確定。閑時(shí)間。

5、但事先無法確定。小時(shí)6/1nxnii精選精選ppt8對(duì)于隨機(jī)服務(wù)系統(tǒng)希望知道：對(duì)于隨機(jī)服務(wù)系統(tǒng)希望知道：1、在系統(tǒng)中平均隊(duì)長(zhǎng)、在系統(tǒng)中平均隊(duì)長(zhǎng)L從長(zhǎng)遠(yuǎn)來看，平均等待服從長(zhǎng)遠(yuǎn)來看，平均等待服務(wù)加上正接受服務(wù)的貨輪期望數(shù)；務(wù)加上正接受服務(wù)的貨輪期望數(shù)；2、在隊(duì)中平均隊(duì)長(zhǎng)、在隊(duì)中平均隊(duì)長(zhǎng)Lq從長(zhǎng)遠(yuǎn)來看，平均等待服務(wù)從長(zhǎng)遠(yuǎn)來看，平均等待服務(wù)的貨輪期望數(shù)；的貨輪期望數(shù)；3、系統(tǒng)中平均逗留時(shí)間、系統(tǒng)中平均逗留時(shí)間 從長(zhǎng)遠(yuǎn)看，任一進(jìn)從長(zhǎng)遠(yuǎn)看，任一進(jìn)入系統(tǒng)貨輪用于等待服務(wù)加上接受服務(wù)的期望時(shí)間；入系統(tǒng)貨輪用于等待服務(wù)加上接受服務(wù)的期望時(shí)間；4、在隊(duì)中平均等待時(shí)間、在隊(duì)中平均等待時(shí)間 從長(zhǎng)遠(yuǎn)看，任一進(jìn)從長(zhǎng)遠(yuǎn)看，

6、任一進(jìn)入系統(tǒng)貨輪用于等待服務(wù)的期望時(shí)間。入系統(tǒng)貨輪用于等待服務(wù)的期望時(shí)間。WqW精選精選ppt9 一、服務(wù)系統(tǒng)的結(jié)構(gòu)一、服務(wù)系統(tǒng)的結(jié)構(gòu) 假如將要求服務(wù)的對(duì)象統(tǒng)稱為假如將要求服務(wù)的對(duì)象統(tǒng)稱為“顧客顧客”， 進(jìn)行服務(wù)的統(tǒng)稱為進(jìn)行服務(wù)的統(tǒng)稱為“服務(wù)機(jī)構(gòu)服務(wù)機(jī)構(gòu)”或或“服務(wù)服務(wù)員員”，一，一 個(gè)排隊(duì)系統(tǒng)就能抽象地描述為：個(gè)排隊(duì)系統(tǒng)就能抽象地描述為： 為了獲得某種服務(wù)而到達(dá)的顧客，若不能立為了獲得某種服務(wù)而到達(dá)的顧客，若不能立即即 獲得服務(wù)，而又允許排隊(duì)等待，則加入等待獲得服務(wù)，而又允許排隊(duì)等待，則加入等待隊(duì)隊(duì) 伍，獲得服務(wù)之后離開系統(tǒng)。伍，獲得服務(wù)之后離開系統(tǒng)。 作為服務(wù)系統(tǒng)基本上由三個(gè)部分組成：作為

7、服務(wù)系統(tǒng)基本上由三個(gè)部分組成：精選精選ppt10 1、輸入過程、輸入過程 刻劃顧客按怎樣的規(guī)律到達(dá)服務(wù)系刻劃顧客按怎樣的規(guī)律到達(dá)服務(wù)系統(tǒng)，主要有以下幾方面：統(tǒng)，主要有以下幾方面： 1）顧客總體（顧客源）數(shù)可能是有限的（例廠內(nèi)故）顧客總體（顧客源）數(shù)可能是有限的（例廠內(nèi)故障設(shè)備數(shù)）也可能是無限的（到達(dá)售票窗口前的顧障設(shè)備數(shù)）也可能是無限的（到達(dá)售票窗口前的顧客總體）；客總體）； 2）顧客可能是單個(gè)到達(dá)，也可能是成批到達(dá)；）顧客可能是單個(gè)到達(dá)，也可能是成批到達(dá)； 3）顧客相繼到達(dá)的間隔時(shí)間分布可以是確定型，也）顧客相繼到達(dá)的間隔時(shí)間分布可以是確定型，也可以是隨機(jī)型；可以是隨機(jī)型； 4）顧客的到達(dá)可

8、以是相互獨(dú)立的，即以前的到達(dá)情）顧客的到達(dá)可以是相互獨(dú)立的，即以前的到達(dá)情況對(duì)以后顧客的到來沒有影響；況對(duì)以后顧客的到來沒有影響；精選精選ppt11 5）輸入過程可以是）輸入過程可以是平穩(wěn)平穩(wěn)的（指描述相繼到達(dá)的的（指描述相繼到達(dá)的 間隔時(shí)間分布和所含參數(shù)（如間隔時(shí)間分布和所含參數(shù)（如 ） 都與時(shí)間都與時(shí)間無關(guān)無關(guān)，否則稱為非平穩(wěn)的；，否則稱為非平穩(wěn)的； 6）具有不耐煩顧客的輸入）具有不耐煩顧客的輸入 a）棄長(zhǎng)隊(duì)而去）棄長(zhǎng)隊(duì)而去 b）排隊(duì)太久而去）排隊(duì)太久而去 c）轉(zhuǎn)隊(duì)）轉(zhuǎn)隊(duì)等和2x精選精選ppt12 2、排隊(duì)規(guī)則（到達(dá)的顧客按什么樣的規(guī)則接受服務(wù)）、排隊(duì)規(guī)則（到達(dá)的顧客按什么樣的規(guī)則接受服務(wù)

9、） 1）損失制）損失制 即服務(wù)臺(tái)一旦占用，顧客隨即離去；即服務(wù)臺(tái)一旦占用，顧客隨即離去； 2）等待制）等待制 顧客到達(dá)后須等待服務(wù)，服務(wù)次序?yàn)椋侯櫩偷竭_(dá)后須等待服務(wù)，服務(wù)次序?yàn)椋?a）先到先服務(wù)）先到先服務(wù) b）后到先服務(wù)）后到先服務(wù) c）隨機(jī)服務(wù)）隨機(jī)服務(wù) d）有優(yōu)先權(quán)的服務(wù)）有優(yōu)先權(quán)的服務(wù) 3）混合制（損失制與等待制的混合）混合制（損失制與等待制的混合） a）隊(duì)長(zhǎng)有限制的情形）隊(duì)長(zhǎng)有限制的情形 隊(duì)長(zhǎng)隊(duì)長(zhǎng)k，離去，離去精選精選ppt13 b）等待（或逗留）時(shí)間有限制的情形）等待（或逗留）時(shí)間有限制的情形 排隊(duì)時(shí)間排隊(duì)時(shí)間t0,離去離去;反之排下去反之排下去 4)從隊(duì)伍的數(shù)目看從隊(duì)伍的數(shù)目看,

10、可以是單列可以是單列,也可以是多列也可以是多列 a)顧客可轉(zhuǎn)移顧客可轉(zhuǎn)移; b)顧客不可轉(zhuǎn)移顧客不可轉(zhuǎn)移;精選精選ppt14 3、服務(wù)機(jī)構(gòu)、服務(wù)機(jī)構(gòu) 1）服務(wù)員的數(shù)目）服務(wù)員的數(shù)目 串列、并列、串并混合串列、并列、串并混合 2）服務(wù)方式）服務(wù)方式 對(duì)單個(gè)顧客服務(wù)或?qū)Τ膳櫩头?wù)對(duì)單個(gè)顧客服務(wù)或?qū)Τ膳櫩头?wù) 3）服務(wù)時(shí)間）服務(wù)時(shí)間 分確定型和隨機(jī)型服務(wù)時(shí)間分確定型和隨機(jī)型服務(wù)時(shí)間精選精選ppt15 二、表示排隊(duì)模型的符號(hào)二、表示排隊(duì)模型的符號(hào) D.G.Kendall 于于1953 年提出排隊(duì)符號(hào)年提出排隊(duì)符號(hào): (i/j/c) i:到達(dá)過程的分布到達(dá)過程的分布;j:服務(wù)過程分布服務(wù)過程分布;c

11、:服務(wù)員數(shù)服務(wù)員數(shù) 到了到了1971年進(jìn)一步定為：年進(jìn)一步定為：(到達(dá)分布到達(dá)分布/服務(wù)分布服務(wù)分布/服務(wù)員數(shù)服務(wù)員數(shù)/系統(tǒng)容量系統(tǒng)容量/顧客源顧客源/排隊(duì)規(guī)則排隊(duì)規(guī)則)(M/M/1/FCFS)常規(guī)表示法為常規(guī)表示法為(M/M/1)精選精選ppt16 三、排隊(duì)模型中常用參數(shù)三、排隊(duì)模型中常用參數(shù) ：到達(dá)速度（單位時(shí)間到達(dá)顧客數(shù)）；：到達(dá)速度（單位時(shí)間到達(dá)顧客數(shù)）； ：服務(wù)速度（單位時(shí)間服務(wù)完成數(shù)）；：服務(wù)速度（單位時(shí)間服務(wù)完成數(shù)）； 1/ ：相繼顧客到達(dá)的平均間隔時(shí)間；：相繼顧客到達(dá)的平均間隔時(shí)間； 1/ ：一個(gè)顧客的平均服務(wù)時(shí)間；：一個(gè)顧客的平均服務(wù)時(shí)間； =（1/ ：1/ ）= / 稱為稱

12、為服務(wù)強(qiáng)度服務(wù)強(qiáng)度，指相同時(shí)，指相同時(shí) 間區(qū)間內(nèi)顧客到達(dá)的平均數(shù)與能被服務(wù)完的平均顧間區(qū)間內(nèi)顧客到達(dá)的平均數(shù)與能被服務(wù)完的平均顧 客數(shù)之比；客數(shù)之比；精選精選ppt17 四、系統(tǒng)的穩(wěn)態(tài)性態(tài)四、系統(tǒng)的穩(wěn)態(tài)性態(tài) 1、 j穩(wěn)態(tài)概率穩(wěn)態(tài)概率 j定義為穩(wěn)態(tài)系統(tǒng)中有定義為穩(wěn)態(tài)系統(tǒng)中有j個(gè)顧客（包括正在服務(wù)的）個(gè)顧客（包括正在服務(wù)的） 的概率。的概率。00jjj 0=1- 稱為系統(tǒng)空閑的概率稱為系統(tǒng)空閑的概率精選精選ppt18 2、 3、 4、 5、（系統(tǒng)人數(shù)）10jjjL（排隊(duì)人數(shù)）（1211jjqjL（逗留時(shí)間）（111W（等待時(shí)間）（1qW精選精選ppt19 6、 7、tse）（1twte）（1qtP

13、w進(jìn)入系統(tǒng)的顧客逗留時(shí)間超過進(jìn)入系統(tǒng)的顧客逗留時(shí)間超過t的概率。的概率。進(jìn)入系統(tǒng)的顧客等待時(shí)間超過進(jìn)入系統(tǒng)的顧客等待時(shí)間超過t的概率。的概率。精選精選ppt20 五、穩(wěn)態(tài)性態(tài)中各量值的分析五、穩(wěn)態(tài)性態(tài)中各量值的分析 1、 = / 的意義的意義 1）平均到達(dá)速度與平均服務(wù)速度之比；）平均到達(dá)速度與平均服務(wù)速度之比； 2）服務(wù)員利用率）服務(wù)員利用率 =1- 0 3）一個(gè)平均服務(wù)時(shí)間）一個(gè)平均服務(wù)時(shí)間 內(nèi)到達(dá)的顧客平均數(shù)內(nèi)到達(dá)的顧客平均數(shù)1精選精選ppt21 4）正在接受服務(wù)的顧客平均數(shù)）正在接受服務(wù)的顧客平均數(shù) =0 0+1（1- 0） 2、L與與Lq的關(guān)系的關(guān)系qqLLLL即）（ 11112表示

14、系統(tǒng)中平均人數(shù)等于隊(duì)中平均人數(shù)加上正在接表示系統(tǒng)中平均人數(shù)等于隊(duì)中平均人數(shù)加上正在接受服務(wù)顧客平均人數(shù)。受服務(wù)顧客平均人數(shù)。精選精選ppt22 3、的關(guān)系與qWW1111）（）（qWW1qWW系統(tǒng)逗留時(shí)間減排隊(duì)時(shí)間恰為服務(wù)時(shí)間的期望值。系統(tǒng)逗留時(shí)間減排隊(duì)時(shí)間恰為服務(wù)時(shí)間的期望值。精選精選ppt23 4、WL）（11/1WL精選精選ppt24 5、qqWL）（1/12qqWL精選精選ppt25 10.2 M/M/1模型實(shí)例模型實(shí)例 例例1、某廠有幾千名工人，醫(yī)務(wù)室平均每小時(shí)約有、某廠有幾千名工人，醫(yī)務(wù)室平均每小時(shí)約有4 位工人來看病，醫(yī)生每小時(shí)平均診斷約位工人來看病，醫(yī)生每小時(shí)平均診斷約5個(gè)病人

15、，若個(gè)病人，若 到達(dá)時(shí)間間隔服從普阿松（到達(dá)時(shí)間間隔服從普阿松（Pisson）分布，服務(wù)時(shí)間）分布，服務(wù)時(shí)間 服從負(fù)指數(shù)分布，試分析該系統(tǒng)。服從負(fù)指數(shù)分布，試分析該系統(tǒng)。 解：本例屬標(biāo)準(zhǔn)解：本例屬標(biāo)準(zhǔn)(M/M/1/FCFS)問題，問題， 已知已知 =4人人/小時(shí)；小時(shí)； =5 人人/小時(shí)，小時(shí)， = / =4/5=0.8 系統(tǒng)隊(duì)長(zhǎng)系統(tǒng)隊(duì)長(zhǎng)L= /(1- )=0.8/(1-0.8)=4人人; 平均平均4人排隊(duì)和看病人排隊(duì)和看病 隊(duì)長(zhǎng)隊(duì)長(zhǎng)Lq= 2/(1- )=0.82/(1-0.8)=3.2人人;平均有平均有3.2人在排隊(duì)人在排隊(duì)或或 Lq= L- =4-0.8=3.2人人精選精選ppt26小時(shí)

16、14511W小時(shí)8 . 0458 . 0qW工人在醫(yī)務(wù)室平均逗留時(shí)間：工人在醫(yī)務(wù)室平均逗留時(shí)間：病人平均在醫(yī)務(wù)室內(nèi)排隊(duì)和看病時(shí)間約為病人平均在醫(yī)務(wù)室內(nèi)排隊(duì)和看病時(shí)間約為1小時(shí)。小時(shí)。工人在醫(yī)務(wù)室平均排隊(duì)時(shí)間：工人在醫(yī)務(wù)室平均排隊(duì)時(shí)間：病人平均在醫(yī)務(wù)室內(nèi)排隊(duì)時(shí)間約為病人平均在醫(yī)務(wù)室內(nèi)排隊(duì)時(shí)間約為0.8小時(shí)。小時(shí)。精選精選ppt27 系統(tǒng)空閑概率系統(tǒng)空閑概率 0=1- =1-0.8=0.2 系統(tǒng)忙的概率系統(tǒng)忙的概率1- 0= =0.8 以該廠每天工作以該廠每天工作8小時(shí)計(jì)小時(shí)計(jì),則每天平均來看病的人數(shù)為則每天平均來看病的人數(shù)為: L總總=8 =84=32人人/天天; 全體病人每天平均等待看病所化時(shí)

17、間為全體病人每天平均等待看病所化時(shí)間為: W總總=小時(shí)3213232W3679. 0) 11)8 . 01(5)1(eeWPt（病人逗留時(shí)間和排隊(duì)超過病人逗留時(shí)間和排隊(duì)超過1小時(shí)的概率分別為：小時(shí)的概率分別為：29424.08 .0)11)8 .01(5)1(eeWPtq（精選精選ppt28 若要計(jì)算系統(tǒng)中大于若要計(jì)算系統(tǒng)中大于10個(gè)病人的概率個(gè)病人的概率,則則: n10= 11=0.811=0.086 即醫(yī)務(wù)室中大于即醫(yī)務(wù)室中大于10個(gè)病人的概率僅為個(gè)病人的概率僅為8.6%101111)1 (1)1 (11kkjkjkjjkn醫(yī)務(wù)室中病員大于醫(yī)務(wù)室中病員大于K的概率的概率精選精選ppt29例

18、例2、某電機(jī)修理車間，每天平均有、某電機(jī)修理車間，每天平均有2臺(tái)電機(jī)到達(dá)修理。臺(tái)電機(jī)到達(dá)修理。負(fù)責(zé)修理的是負(fù)責(zé)修理的是1名修理工，平均每名修理工，平均每3小時(shí)修完小時(shí)修完1臺(tái)。若到臺(tái)。若到達(dá)為泊松分布，修理時(shí)間為負(fù)指數(shù)分布，求達(dá)為泊松分布，修理時(shí)間為負(fù)指數(shù)分布，求1臺(tái)電機(jī)從臺(tái)電機(jī)從到達(dá)到修理完畢的平均時(shí)間及修理工人每天的平均空到達(dá)到修理完畢的平均時(shí)間及修理工人每天的平均空閑時(shí)間（每天以閑時(shí)間（每天以8小時(shí)計(jì)）小時(shí)計(jì)）解：本問題屬解：本問題屬(M/M/1/FCFS)模式模式到達(dá)速度到達(dá)速度 =2臺(tái)臺(tái)/8小時(shí)小時(shí)=1/4 臺(tái)臺(tái)/小時(shí)小時(shí)服務(wù)速度服務(wù)速度 =1臺(tái)臺(tái)/3小時(shí)小時(shí)=1/3 臺(tái)臺(tái)/小時(shí)小時(shí) = / =1/4/1/3=3/40.5=e- (1- )t=e-4(1-0.5)0.5=0.3678精選精選ppt51若是租賃場(chǎng)地，則新系統(tǒng)變?yōu)椋喝羰亲赓U場(chǎng)地，則新系統(tǒng)變?yōu)椋篗/M/1/3/FCFSM/M/1/3/FCFS模型模