管理運籌學(xué)講義-第12-章--排隊理論

1、1,第12 章 排隊理論,Sub title,學(xué)習(xí)要點,正確理解排隊系統(tǒng)中排隊規(guī)則和服務(wù)規(guī)則 顧客輸入過程和服務(wù)過程的時間分布函數(shù) 排隊問題的求解步驟及運行指標(biāo)間的關(guān)系 標(biāo)準(zhǔn)M/M/1模型的狀態(tài)方程及其運行指標(biāo) 標(biāo)準(zhǔn)M/M/c模型與c個M/M/1模型的差別 典型排隊系統(tǒng)的結(jié)構(gòu)優(yōu)化和運行優(yōu)化問題,2,第12 章 排隊理論,排隊論(Queuing Theory)又稱隨機(jī)服務(wù)系統(tǒng)理論，研究排隊等待問題研究各種排隊系統(tǒng)概率規(guī)律

2、性排隊系統(tǒng)的最優(yōu)設(shè)計排隊系統(tǒng)的最優(yōu)運營排隊是經(jīng)常遇到的，若要求服務(wù)的數(shù)量超過服務(wù)機(jī)構(gòu)的容量，即不能立即得到服務(wù)，就出現(xiàn)了排隊現(xiàn)象。顧客到達(dá)和服務(wù)時間是隨機(jī)的，排隊現(xiàn)象是不可避免的：增設(shè)服務(wù)機(jī)構(gòu)，就要增加投資，可能發(fā)生空閑浪費減少服務(wù)機(jī)構(gòu)，排隊現(xiàn)象將會嚴(yán)重在需要服務(wù)的顧客數(shù)與服務(wù)機(jī)構(gòu)容量之間取得平衡,3,第一節(jié) 排隊系統(tǒng)分析,顧客由顧客源到達(dá)服務(wù)機(jī)構(gòu)排隊等待接受服務(wù)，服務(wù)完了離去,,,,顧客,到達(dá),接受服務(wù),離去,,,等待

3、時間,,服務(wù)時間,,逗留時間,逗留時間=等待時間+服務(wù)時間,從到達(dá)系統(tǒng)排隊等待至開始接受服務(wù)的時間。,從開始接受服務(wù)到服務(wù)后離去的時間。,顧客從到達(dá)至離去，在系統(tǒng)中停留的時間。,4,,第一節(jié) 排隊系統(tǒng)分析,一、排隊系統(tǒng)的一般結(jié)構(gòu),顧客源,,,輸入,離去,等待隊列,服務(wù)機(jī)構(gòu),,排隊規(guī)則,服務(wù)規(guī)則,顧客：人：病人、就餐者等；物：不能運轉(zhuǎn)的機(jī)器、駛?cè)敫劭诘拇坏?；需處理的信息。等待隊列結(jié)構(gòu)：隊列的數(shù)目和排列方式。隊列有形或無形；顧

4、客走向服務(wù)機(jī)構(gòu)或相反(如送貨上門)。服務(wù)機(jī)構(gòu)的結(jié)構(gòu)是指服務(wù)機(jī)構(gòu)的數(shù)目及其排列方式。服務(wù)機(jī)構(gòu)可以是人，也可以是物；還可以是一個系統(tǒng)。排隊規(guī)則和服務(wù)規(guī)則是說明顧客接受服務(wù)的規(guī)則和次序。,排隊系統(tǒng),5,常見排隊系統(tǒng)的結(jié)構(gòu)單隊——單服務(wù)臺單隊——多服務(wù)臺多隊——多服務(wù)臺,第一節(jié) 排隊系統(tǒng)分析,隊列數(shù)目可以是單隊，也可以是多隊；服務(wù)機(jī)構(gòu)的數(shù)目可以是單服務(wù)臺，也可以是多服務(wù)臺。對于多服務(wù)臺,可能是串聯(lián),也可能是并列,或者

5、是串并結(jié)合,6,第一節(jié) 排隊系統(tǒng)分析,二、排隊系統(tǒng)的組成,一般排隊系統(tǒng)都有三個基本組成部分： 輸入過程 2. 服務(wù)規(guī)則3. 服務(wù)過程,服務(wù)機(jī)構(gòu)個數(shù)接受服務(wù)方式服務(wù)時間分布,顧客源的容量顧客到達(dá)方式到達(dá)時間分布,即時制等待制? 混合制,先到先服務(wù)后到先服務(wù)隨機(jī)性服務(wù)優(yōu)先權(quán)服務(wù),隊長有限時間有限,,7,第一節(jié) 排隊系統(tǒng)分析,三、排隊問題的模型,柯恩達(dá)爾(D.G.Kendal

6、l)953年提出 X/Y/Z， 即 輸入過程分布/服務(wù)時間分布/服務(wù)臺的數(shù)目 D ：定長分布； M ：泊松分布或負(fù)指數(shù)分布； Ek ： k階愛爾朗分布； GI ：一般獨立分布； G ：一般分布。1971年排隊論符號標(biāo)準(zhǔn)化會議決定，擴(kuò)充X/Y/A/A/B/C A 系統(tǒng)容量限制 N ；

7、B 顧客源數(shù)目m ； C 服務(wù)規(guī)則。例如，M/M/1/∞/∞/ FCFS ，表示輸入過程服從泊松分布、服務(wù)時間服從負(fù)指數(shù)分布、單服務(wù)臺、系統(tǒng)容量無限、顧客源無限、先到先服務(wù)的排隊模型,8,確定經(jīng)驗分布 首先要對所研究的排隊系統(tǒng)進(jìn)行統(tǒng)計推斷， 根據(jù)實際數(shù)據(jù)確定輸入過程分布和服務(wù)時間分布， 估計參數(shù)值: 平均到達(dá)率? 平均服務(wù)率? 服務(wù)強(qiáng)度? 確定模型類別 給定服務(wù)臺數(shù)、系統(tǒng)容量和服務(wù)規(guī)則， 按X/

8、Y/Z/A/B/C確定排隊模型。 求運行指標(biāo): 顧客數(shù) 排隊時間 忙期,第二節(jié) 排隊問題求解,一、求解步驟,9,第二節(jié) 排隊問題求解,二、分布函數(shù),泊松分布 條件： 性質(zhì)：,輸入流的平穩(wěn)性輸入流無后效性輸入流的普通性輸入流的有限性,輸入過成服從泊松分布，顧客相繼到達(dá)的間隔時間服從負(fù)指數(shù)分布。,負(fù)指數(shù)分布,10,第二節(jié) 排隊問題求解,三、運行指標(biāo),顧客數(shù)量 平均隊長Ls，指

9、系統(tǒng)中顧客數(shù)的期望值 平均隊列長Lq，指系統(tǒng)中排隊等待服務(wù)顧客數(shù)的期望值 Ls=Lq+［正被服務(wù)的顧客數(shù)］ 排隊時間 平均逗留時間Ws是指一個顧客在系統(tǒng)中停留時間的期望值 平均等待時間Wq指一個顧客在系統(tǒng)中排隊等待時間的期望值Ws=Wq+［服務(wù)時間］忙期指服務(wù)機(jī)構(gòu)連續(xù)繁忙工作的時間。,11,第三節(jié) 標(biāo)準(zhǔn)M/M/1模型,一、模型特征,輸入過程排隊規(guī)則服務(wù)機(jī)構(gòu),顧客源無限；顧客到達(dá)方式是單個到達(dá)，且相互獨立；

10、輸入過程服從參數(shù)為? 的泊松分布，到達(dá)過程平穩(wěn)。,隊列為單隊；隊長無限，即系統(tǒng)容量無限；系統(tǒng)按先到先服務(wù)的等待制規(guī)則進(jìn)行服務(wù),只有一個服務(wù)臺；服務(wù)方式為單個服務(wù)，服務(wù)時間相互獨立；服務(wù)時間服從相同參數(shù) 的負(fù)指數(shù)分布。,12,第三節(jié) 標(biāo)準(zhǔn)M/M/1排隊模型,平均隊長平均隊列長平均逗留時間平均等待時間忙期概率,如何尋求系統(tǒng)運行指標(biāo)？,13,第三節(jié) 標(biāo)準(zhǔn)M/M/1模型,Pn(t+⊿t)=?⊿t?⊿t Pn(t)+ (1-

11、?⊿t)(1-?⊿t) Pn(t)+ ?⊿t(1-?⊿t) Pn-1(t)+ (1- ?⊿t) ?⊿t Pn+1(t) =(1-?⊿t-?⊿t)Pn(t)+ ?⊿t) Pn(t)+ ?⊿t Pn+1(t)+ ?⊿tPn-1(t)+o(⊿t ),二、狀態(tài)方程 在t+⊿t 時刻，系統(tǒng)中有n>0 個顧客的概率Pn(t+⊿t),Pn(t),?⊿t,?⊿t,?⊿t?⊿t Pn(t),Pn(t),1- ?⊿

12、t,1-?⊿t,(1- ?⊿t)(1-?⊿t) Pn(t),Pn-1(t),?⊿t,1-?⊿t,?⊿t(1-?⊿t) Pn-1(t),Pn+1(t),1- ?⊿t,?⊿t,(1- ?⊿t) ?⊿t Pn+1(t),14,第三節(jié) 標(biāo)準(zhǔn)M/M/1模型,在t+⊿t 時刻，系統(tǒng)中有n=0 個顧客 的概率P0(t+⊿t),P0(t+⊿t)=(1- ?⊿t) P0(t)+ (1- ?⊿t) ?⊿t P1(t),15,第三節(jié) 標(biāo)準(zhǔn)M/M/1模型,三、

13、穩(wěn)態(tài)解,由狀態(tài)方程有平衡方程式：這是關(guān)于Pn 的差分方程，表明各種狀態(tài)間的轉(zhuǎn)移關(guān)系用馬爾科夫鏈(Markov)表示為：統(tǒng)計平衡狀態(tài)下，系統(tǒng)狀態(tài)為 的概率：,16,第三節(jié) 標(biāo)準(zhǔn)M/M/1模型,四、運行指標(biāo),平均隊長平均隊列長平均逗留時間平均等待時間 [服務(wù)時間] 忙期概率,17,第三節(jié) 標(biāo)準(zhǔn)M/M/1模型,例題,為了評價某單人理發(fā)館隨機(jī)服務(wù)系統(tǒng)，記錄了100個工作小時，每小時來理發(fā)的顧

14、客數(shù)的統(tǒng)計情況。又記錄了100次理發(fā)所用的時間，如表所示。 試求：顧客平均到達(dá)率及該理發(fā)員的平均服務(wù)率；服務(wù)強(qiáng)度及顧客來理發(fā)館不必等待的概率；系統(tǒng)運行指標(biāo)；如果顧客在店內(nèi)平均逗留時間超過1.25小時，則店主將考慮增加設(shè)備及人員，問平均到達(dá)率提高到多少時店主才做這樣的考慮?,18,第三節(jié) 標(biāo)準(zhǔn)M/M/1模型,例題,解：（1） (人/時) (分/人)

15、 (人/時) （2） =75%。,（3） （人） （人） （時） （時）（4）顧客在店內(nèi)平均逗留時間超過1.25時，即

16、 時，店主將考慮增加設(shè)備及人員，有 ，解得 人/時，即平均到達(dá)率提高到每小時3.2人，店主將做這樣的考慮。,19,第四節(jié) 標(biāo)準(zhǔn)M/M/c模型,一、模型特征,1. 輸入過程 顧客源無限； 顧客到達(dá)方式是單個到達(dá)，且相互獨立； 輸入過程服從參數(shù)?的泊松分布，到達(dá)過程已是平穩(wěn)的。2. 排隊規(guī)則 隊列為單隊； 隊長無限； 服務(wù)規(guī)則是先到先服務(wù)。3. 服務(wù)機(jī)構(gòu) 有c個服務(wù)臺(c>1)

17、的排隊系統(tǒng)； 各服務(wù)臺服務(wù)方式是單個服務(wù)，且各服務(wù)臺相互獨立不協(xié)作； 各服務(wù)臺的服務(wù)時間服從參數(shù) ? 的負(fù)指數(shù)分布，則整個服務(wù)機(jī)構(gòu)的平均服務(wù)率為 c? (當(dāng)n≥c) 或 n? (當(dāng) n<c)，系統(tǒng)服務(wù)強(qiáng)度(服務(wù)機(jī)構(gòu)平均利用率) 。,20,第四節(jié) 標(biāo)準(zhǔn)M/M/c模型,二、平衡方程,三、穩(wěn)態(tài)解,（1）系統(tǒng)狀態(tài) 當(dāng) 時， ，有

18、 當(dāng) 時， ，有 當(dāng) 時， ，有 同理可得,21,第四節(jié) 標(biāo)準(zhǔn)M/M/c模型,三、穩(wěn)態(tài)解,（2）系統(tǒng)狀態(tài) 當(dāng) 時， ，有 當(dāng) 時，得,由

19、 ，得狀態(tài)概率為,22,第四節(jié) 標(biāo)準(zhǔn)M/M/c模型,四、運行指標(biāo),平均隊列長平均隊長平均逗留時間平均等待時間,23,第四節(jié) 標(biāo)準(zhǔn)M/M/c模型,例題,某售票廳有三個窗口，顧客以每分鐘4人的平均速率按泊松分布到達(dá)，排成一隊依次到空閑窗口購票；售票時間服從負(fù)指數(shù)分布，均值為0.5分鐘，試求系統(tǒng)的運行指標(biāo)。,解： =3， =4人/分， =2人/分，則 ， ，這是一個標(biāo)準(zhǔn)

20、 排隊系統(tǒng)。售票廳空閑的概率為 ；平均隊列長為 (人) ；平均隊長： (人) ；平均逗留時間： (分鐘)；平均等待時間： (分鐘)。系統(tǒng)中各售票口都沒空

21、閑的概率,24,第四節(jié) 標(biāo)準(zhǔn)M/M/c模型,例題,如果顧客到達(dá)后在每個窗口前各排成一隊，且進(jìn)入隊列后不換隊，這樣就形成了三隊并列的情況，即3個標(biāo)準(zhǔn) M/M/1 型的子系統(tǒng)，每個隊列平均到達(dá)率為?1=?2 =?3=3/4人/分。,,,,25,第五節(jié) M/G/1排隊模型,M/G/1排隊模型的服務(wù)時間服從任意分布，其均值為 ，方差為 ， ，且 ，則Po

22、llaczek Khintchine(PK)公式:系統(tǒng)中顧客數(shù)的期望值 =隊列中顧客數(shù)的期望值+服務(wù)機(jī)構(gòu)中顧客數(shù)的期望值。系統(tǒng)中逗留時間的期望值 =排隊等待時間的期望值+服務(wù)時間的期望值。,26,例：某汽車沖洗站有一條自動沖洗線，假設(shè)沖洗的汽車按泊松分布到達(dá)，每小時平均4輛，沖洗每輛汽車所需時間為6分鐘。求：沖洗站內(nèi)汽車的平均數(shù) ；等待沖洗的平均汽車數(shù) ；每輛汽車在沖洗站

23、內(nèi)的平均逗留時間 ；每輛汽車平均等待沖洗的時間 。解： 輛/時， =0.1小時， ， 。 (輛)； (輛)； =0.1325（小時）； =0.0325（

24、小時）。,第五節(jié) M/G/1排隊模型,27,第六節(jié) 排隊系統(tǒng)的優(yōu)化,設(shè) 為單位時間服務(wù)費用， 為一個顧客在系統(tǒng)中停留單位時間的逗留費用，取目標(biāo)函數(shù)為單位時間總費用的期望，又將 代入得：μ取何值時 為最小?可用微積分求極值的方法，即：解之得， ，為保證 ，使 ，根號前取+號。,一、標(biāo)準(zhǔn)M/M/1模型中的最優(yōu)服務(wù)率μ,28,第六節(jié) 排隊系統(tǒng)