運(yùn)籌學(xué)排隊(duì)論2

第十章排隊(duì)論(Queuingtheory)引言排隊(duì)論的基本概念顧客到達(dá)數(shù)及服務(wù)時(shí)間的理論分布單服務(wù)臺(tái)(M/M/1)排隊(duì)模型多服務(wù)臺(tái)的排隊(duì)模型排隊(duì)系統(tǒng)費(fèi)用的優(yōu)化模型§1引言排隊(duì)是日常生活和經(jīng)濟(jì)領(lǐng)域中常見的現(xiàn)象.如顧客在郵局,銀行排隊(duì)辦理業(yè)務(wù),病人在醫(yī)院排隊(duì)就醫(yī),工廠中等待維修的機(jī)床,港口內(nèi)等候卸貨或進(jìn)港的輪船,機(jī)場內(nèi)等候起飛或降落的飛機(jī),等等.這都是有形的排隊(duì)現(xiàn)象.打電話時(shí)占線,需要等待,這是無形的排隊(duì)現(xiàn)象.排隊(duì)是怎樣產(chǎn)生的?首先,我們把上述現(xiàn)象中的人或物,看做是被服務(wù)隊(duì)象,他們希望得到某種服務(wù),如果在某個(gè)時(shí)刻,要求服務(wù)的對(duì)象超過了服務(wù)機(jī)構(gòu)所能提供的服務(wù)數(shù)量時(shí)就產(chǎn)生了排隊(duì)現(xiàn)象.要減少排隊(duì),可以增加服務(wù)設(shè)施,但是如果增加的太多,服務(wù)設(shè)施又會(huì)出現(xiàn)空閑浪費(fèi);如果服務(wù)設(shè)施少,顧客排隊(duì)太長時(shí),就會(huì)損失顧客也會(huì)造成很大損失.因此,決策者必須在服務(wù)對(duì)象和服務(wù)臺(tái)之間取得平衡,達(dá)到一種最優(yōu)配置.此外,在一些大型項(xiàng)目的設(shè)計(jì)中(港口泊位,機(jī)場跑道,電話線路等),也要根據(jù)排隊(duì)理論作到超前設(shè)計(jì),同時(shí)還要考慮費(fèi)用的優(yōu)化問題,這就是排隊(duì)論研究的內(nèi)容.排隊(duì)論的創(chuàng)始人是丹麥哥本哈根市電話局的工程師愛爾朗(A.K.Erlang),他早期研究電話理論,特別是電話的占線問題,就是早期排隊(duì)論的內(nèi)容.§2排隊(duì)論的基本概念一.排隊(duì)現(xiàn)象的共同特征:為了獲得某種服務(wù)而到達(dá)的顧客,如不能立即得到服務(wù)而又允許排隊(duì)等候,則加入等待的隊(duì)伍,獲得服務(wù)后離開.我們把包含這些特征的系統(tǒng)稱為排隊(duì)系統(tǒng).排隊(duì)系統(tǒng)的幾種情況:1.單服務(wù)臺(tái)排隊(duì)系統(tǒng)服務(wù)臺(tái)2.C個(gè)服務(wù)臺(tái),一個(gè)公共隊(duì)伍服務(wù)臺(tái)1服務(wù)臺(tái)2服務(wù)臺(tái)C3.C個(gè)服務(wù)臺(tái),C個(gè)隊(duì)伍服務(wù)臺(tái)1服務(wù)臺(tái)2服務(wù)臺(tái)C二.排隊(duì)系統(tǒng)的三個(gè)組成部分1.輸入過程:指顧客按怎樣的規(guī)律到達(dá).

⑴顧客的總體數(shù)或顧客源:指可能到達(dá)服務(wù)機(jī)構(gòu)的顧客總數(shù).顧客總體數(shù)可以是有限的,也可以是無限的;⑵顧客到達(dá)的類型:顧客是單個(gè)到達(dá)還是成批到達(dá);⑶顧客相繼到達(dá)時(shí)間間隔的分布,如按泊松分布,定長分布還是負(fù)指數(shù)分布.2.排隊(duì)規(guī)則:指顧客接受服務(wù)的先后次序問題⑴損失制:顧客到達(dá)時(shí),服務(wù)臺(tái)被占用,顧客隨即離去,不再接受服務(wù);⑵等待制:服務(wù)臺(tái)被占用,顧客排隊(duì)等候.根據(jù)服務(wù)臺(tái)對(duì)顧客服務(wù)的先后順序又分為ⅰ.先到先服務(wù);ⅱ.后到先服務(wù);ⅲ.隨機(jī)服務(wù);ⅳ.優(yōu)先權(quán)服務(wù).⑶混合制:顧客起初排隊(duì),看到隊(duì)伍太長又離去.3.服務(wù)機(jī)構(gòu):又稱服務(wù)臺(tái)⑴服務(wù)臺(tái)的數(shù)目:有單服務(wù)臺(tái),多服務(wù)臺(tái);⑵任一時(shí)刻接受服務(wù)的顧客數(shù);⑶服務(wù)時(shí)間的分布:對(duì)每個(gè)顧客的服務(wù)時(shí)間是隨機(jī)變量,但是其概率分布多按負(fù)指數(shù)分布來處理,也有的服從定長分布.二.排隊(duì)系統(tǒng)的描述符號(hào)及分類n:排隊(duì)系統(tǒng)中顧客的數(shù)目

:顧客到達(dá)的平均速率,即單位時(shí)間內(nèi)到達(dá)的顧客數(shù)

:系統(tǒng)的平均服務(wù)速率,即單位時(shí)間內(nèi)可服務(wù)完的顧客數(shù)

:在時(shí)刻t時(shí)系統(tǒng)中有n個(gè)顧客的概率C:服務(wù)臺(tái)的個(gè)數(shù)FCFS:先到先服務(wù)的排隊(duì)規(guī)則LCFS:后到先服務(wù)的排隊(duì)規(guī)則PR:優(yōu)先權(quán)服務(wù)的排隊(duì)規(guī)則M:到達(dá)過程為泊松過程或負(fù)指數(shù)過程D:定長型分布

:k階愛爾朗分布a:顧客到達(dá)過程的概率分布(輸入)b:服務(wù)過程的概率分布(輸出)d:排隊(duì)系統(tǒng)的最大容量e:顧客總體的數(shù)量f:排隊(duì)規(guī)則1953年由K.D.Kendall提出了排隊(duì)模型記號(hào)方案,由a/b/c/d組成,即輸入/輸出/并聯(lián)服務(wù)臺(tái)數(shù)/顧客總體數(shù)量如:M/M/1/表示:排隊(duì)系統(tǒng)中顧客到達(dá)是泊松過程,服務(wù)時(shí)間服從負(fù)指數(shù)分布,單服務(wù)臺(tái),顧客源無限.1971年國際排隊(duì)符號(hào)標(biāo)準(zhǔn)會(huì)上將上述符號(hào)擴(kuò)充到六項(xiàng),即a/b/c/d/e/f.如:M/M/1///FCFS)M/M/4/N//FCFS)§3顧客到達(dá)數(shù)及服務(wù)時(shí)間的理論分布在排隊(duì)服務(wù)過程中,單位時(shí)間內(nèi)顧客到達(dá)數(shù),顧客到達(dá)時(shí)間間隔,服務(wù)時(shí)間都是隨機(jī)變量,因此必須了解它們的概率分布.一.泊松流現(xiàn)將上式參數(shù)引入時(shí)間因素,即將換為,得到表示長為t的時(shí)間區(qū)間內(nèi)到達(dá)n個(gè)顧客的概率為

,且服從泊松分布.這稱為泊松流或泊松過程或簡單流.設(shè)t時(shí)間內(nèi)到達(dá)的顧客數(shù)為隨機(jī)變量N(t),則有二.負(fù)指數(shù)分布現(xiàn)在研究當(dāng)輸入過程是泊松流時(shí),兩顧客先后到達(dá)時(shí)間間隔T的概率分布.由可知,當(dāng)n=0時(shí)即在[0,t]內(nèi)沒有顧客到達(dá)的概率為則至少有一個(gè)顧客到達(dá)的概率分布函數(shù)為相應(yīng)的概率密度為三.服務(wù)時(shí)間v的概率分布一般總是假定顧客接受服務(wù)的時(shí)間v也服從負(fù)指數(shù)分布負(fù)指數(shù)分布的一個(gè)重要特征是“無記憶性”，也稱無后效性或馬爾科夫性。這個(gè)性質(zhì)為排隊(duì)輪問題的求解帶來了方便。如果輸入分布或服務(wù)分布為負(fù)指數(shù)分布，則不論實(shí)際排隊(duì)過程進(jìn)行了多長時(shí)間，要研究從現(xiàn)在起以后的情況，只要考慮當(dāng)前排隊(duì)所處的狀況就可以了，在此以前的情況可以不考慮，就好像過程剛開始一樣。例9.1某倉庫全天都可以進(jìn)行發(fā)料業(yè)務(wù)，假設(shè)顧客到達(dá)的時(shí)間間隔服從均值為1的負(fù)指數(shù)分布現(xiàn)在有一位顧客正好中午12：00到達(dá)領(lǐng)料，試求：（1）下一個(gè)顧客將在下午1：00前到達(dá)的概率；（2）在下午1：00與2：00之間到達(dá)的概率：（3）在下午2：00以后到達(dá)的概率。解：因?yàn)轭櫩偷竭_(dá)間隔時(shí)間T服從負(fù)指數(shù)分布，所以T的概率密度為取時(shí)間起點(diǎn)為中午12:00，則相對(duì)時(shí)間為。（1）下一個(gè)顧客在下午1：00前到達(dá)的概率為（2）顧客在下午1：00到2：00之間到達(dá)，則（3）顧客在下午2：00以后到達(dá)，則定義:稱為服務(wù)強(qiáng)度(Trafficintensity).也稱為話務(wù)強(qiáng)度,這是因?yàn)閻蹱柪试谠缙谘芯颗抨?duì)論時(shí)是從研究電話理論開始的.

是刻劃服務(wù)效率和服務(wù)機(jī)構(gòu)利用程度的重要標(biāo)志.當(dāng)時(shí),越小,表示單位時(shí)間內(nèi)到達(dá)顧客的平均數(shù)比服務(wù)完的顧客平均數(shù)小得多,顧客到達(dá)后可及時(shí)得到服務(wù),等待時(shí)間少,服務(wù)員空閑,服務(wù)設(shè)施利用率低;反之越大,反映的事實(shí)與上述相反.注意:同時(shí)滿足下面三個(gè)條件的流為泊松流⒈無后效性:前面到達(dá)的顧客數(shù)并不影響后面到達(dá)的顧客數(shù);⒉平穩(wěn)性:顧客到達(dá)的多少只與時(shí)間間隔有關(guān),而與統(tǒng)計(jì)時(shí)的時(shí)刻無關(guān);⒊普通性:在很短的時(shí)間間隔內(nèi),到達(dá)兩個(gè)或兩個(gè)以上顧客的概率極小,可以忽略不計(jì).§4單服務(wù)臺(tái)(M/M/1)模型(M/M/1)模型是指適合下列條件的系統(tǒng):1.輸入過程:顧客源是無限的,顧客單個(gè)到達(dá),相互獨(dú)立,到達(dá)數(shù)服從泊松分布,到達(dá)過程是平穩(wěn)的;2.排隊(duì)規(guī)則:單隊(duì),隊(duì)長無限制,先到先服務(wù);3.服務(wù)機(jī)構(gòu):單服務(wù)臺(tái),各顧客服務(wù)時(shí)間是相互獨(dú)立的,服從相同的指數(shù)分布.一.生滅過程在排隊(duì)理論中,通常采用一種名為”生滅過程”的方法來描述.首先畫出生滅圖,它的特點(diǎn)是系統(tǒng)的所有狀態(tài)看作一系列的點(diǎn),用0,1,2,…表示,并用正,反兩方向的箭頭線將左右狀態(tài)連接起來,如下圖012nn+1…“生”表示顧客的到達(dá),”滅”表示顧客離去.當(dāng)系統(tǒng)運(yùn)行一段時(shí)間達(dá)到平穩(wěn)狀態(tài)時(shí),其狀態(tài)的概率分布為并標(biāo)在各狀態(tài)上.單位時(shí)間到達(dá)的顧客數(shù)為(即泊松分布的參數(shù)),標(biāo)在指向右方的箭頭線上方.單位時(shí)間服務(wù)的顧客數(shù)為(即負(fù)指數(shù)分布的參數(shù)),標(biāo)在指向左方的箭頭線下方.箭頭線表示狀態(tài)的轉(zhuǎn)移關(guān)系.下面利用生滅圖來推導(dǎo)該排隊(duì)系統(tǒng)的狀態(tài)概率(表示系統(tǒng)中有n個(gè)顧客的概率).先考慮n=0的狀態(tài),狀態(tài)0的穩(wěn)定狀態(tài)概率為而從狀態(tài)0進(jìn)入狀態(tài)1的平均轉(zhuǎn)換率為,因此從狀態(tài)0進(jìn)入狀態(tài)1的輸出率為,同理,狀態(tài)1進(jìn)入狀態(tài)0的輸入率為.根據(jù)輸出率等于輸入率的原則,在系統(tǒng)平衡條件下,對(duì)狀態(tài)0有以下的狀態(tài)平衡方程.二.排隊(duì)系統(tǒng)運(yùn)行指標(biāo)1.在排隊(duì)系統(tǒng)中顧客數(shù)的期望值,它包含排隊(duì)等候的顧客和正在接受服務(wù)的顧客兩部分;2.排隊(duì)等候顧客數(shù)的期望值;3.顧客在排隊(duì)系統(tǒng)中全部時(shí)間的期望值,它是指顧客排隊(duì)等待時(shí)間與被服務(wù)時(shí)間之和的期望值;4.顧客排隊(duì)等待時(shí)間的期望值.三.1.系統(tǒng)狀態(tài)概率的計(jì)算(表示系統(tǒng)中有n個(gè)顧客的概率)2.系統(tǒng)運(yùn)行指標(biāo)的計(jì)算⑴⑵的計(jì)算在單服務(wù)臺(tái)情形下,當(dāng)系統(tǒng)中有顧客時(shí)排隊(duì)等待的顧客數(shù)比系統(tǒng)中顧客總數(shù)減少1,因此⑶W的計(jì)算顧客在系統(tǒng)中的時(shí)間是一個(gè)隨機(jī)變量,可以證明,在該系統(tǒng)中它服從參數(shù)為的負(fù)指數(shù)分布,其概率密度為⑷的計(jì)算顧客在隊(duì)列中排隊(duì)等待時(shí)間的期望值,應(yīng)等于顧客在系統(tǒng)中全部時(shí)間的期望值,減去對(duì)顧客服務(wù)時(shí)間的期望值,注意到服務(wù)時(shí)間服從參數(shù)為的負(fù)指數(shù)分布,因此服務(wù)時(shí)間的期望值為⑸系統(tǒng)內(nèi)多于一個(gè)顧客的概率系統(tǒng)內(nèi)多于m個(gè)顧客的概率(6)顧客停留時(shí)間大于t的概率是顧客在系統(tǒng)中平均排隊(duì)時(shí)間超過t的概率是(7)服務(wù)臺(tái)忙期當(dāng)時(shí)，忙期隨值得增加而增加，當(dāng)時(shí)，系統(tǒng)趨于飽和狀態(tài)，服務(wù)臺(tái)忙碌的均值為在一個(gè)忙期內(nèi)完成服務(wù)的平均顧客數(shù)為小結(jié):利特爾(J.D.C.Little)公式例9.2小汽車作過境檢查,到達(dá)速率為100輛/小時(shí),是泊松流,檢查一輛車平均需15秒,為負(fù)指數(shù)分布,試求穩(wěn)態(tài)概率及系統(tǒng)的各項(xiàng)指標(biāo).解:例9.3某電話間來打電話的人服從泊松分布,平均每小時(shí)24人,每次通話時(shí)間為負(fù)指數(shù)分布,平均2分鐘,求設(shè)備的各項(xiàng)指標(biāo)并求電話間有6人(含6人)以上的概率.解:例9.4慮一個(gè)鐵路列車編組站，設(shè)待編列車到達(dá)時(shí)間間隔服從負(fù)指數(shù)分布，平均到達(dá)2列/小時(shí)；服務(wù)臺(tái)是編組站，編組時(shí)間服從負(fù)指數(shù)分布，平均每20分鐘可編一組。已知編組站上共有2股道，當(dāng)均被占用時(shí)，不能接車，再來的列車只能在站外等候。求在平穩(wěn)狀態(tài)下系統(tǒng)中列車的平均數(shù)；每一列車的平均停留時(shí)間；等待編組的列車平均數(shù)。當(dāng)列車在站外停留時(shí)，每列車的損失費(fèi)為a元/小時(shí)，求每天由于列車在站外等待而造成的損失。解：看作一個(gè)M/M/1/

//FCFS模型例9.5在某倉庫卸貨臺(tái)裝卸設(shè)備的設(shè)計(jì)方案中,有三個(gè)方案可供選擇,分別記為甲,乙,丙,要求選取使總費(fèi)用最小的方案.有關(guān)數(shù)據(jù)如下:方案每天固定費(fèi)用(元)可變操作費(fèi)(c元/天)平均卸貨數(shù)(袋/小時(shí)甲601001000乙1301502000丙2502006000設(shè)貨車按泊松流到達(dá),平均每天(按10小時(shí)計(jì)算)到達(dá)15輛,每車平均裝貨500袋,卸貨時(shí)間服從負(fù)指數(shù)分布,每輛車停留1小時(shí)的損失為10元,求總費(fèi)用最小的方案.解:每個(gè)方案的費(fèi)用綜合如下:方案固定費(fèi)用可變費(fèi)用/天停留費(fèi)用/天總費(fèi)用/天甲60100×0.75=752×10×15=300300+75+60=435乙130150×0.37556.250.4×10×15=60246.25丙250200×0.125250.095×10×15=14.25289.25最優(yōu)決策:乙方案總費(fèi)用最小.012N-1N…四.系統(tǒng)系統(tǒng)特點(diǎn):泊松輸入過程,服務(wù)時(shí)間為負(fù)指數(shù)分布,單服務(wù)臺(tái),系統(tǒng)內(nèi)只允許有N個(gè)顧客,客源無限,先到先服務(wù).同前面的分析一樣,系統(tǒng)處于平穩(wěn)狀態(tài)時(shí),對(duì)于每個(gè)狀態(tài)來說,轉(zhuǎn)入率應(yīng)等于轉(zhuǎn)出率,在狀態(tài)0處有在狀態(tài)1處有在狀態(tài)N-1處有在狀態(tài)N處有綜合以上的結(jié)果可推出:

稱為損失概率,當(dāng)系統(tǒng)中有N個(gè)顧客時(shí),新到的顧客就不進(jìn)入系統(tǒng)了.因?yàn)樗械臓顟B(tài)概率之和等于1,所以歸納為排隊(duì)系統(tǒng)中各種指標(biāo)的計(jì)算:設(shè)表示有效到達(dá)率,即實(shí)際進(jìn)入系統(tǒng)的顧客到達(dá)速率,則由利特爾公式補(bǔ)充當(dāng)時(shí)的公式例9.6某汽車檢測站有一條檢測線，要求做檢測的車輛按泊松流到達(dá)，平均每小時(shí)6輛，每輛車的檢測時(shí)間服從負(fù)指數(shù)分布，平均每輛10分鐘，用于等待檢測的停車泊位有5個(gè)，當(dāng)無停車泊位時(shí)，來檢測的車輛自動(dòng)離去。試計(jì)算試計(jì)算：1、某車輛一到達(dá)就可進(jìn)行檢測的概率；2、等待檢測的平均車數(shù)；3、每輛車在檢測線上等待的期望時(shí)間；4、在可能到來的車輛中，有百分之幾不等待離開；5、如果車輛因停車泊位全部被占用而離去，每輛車損失a元，求每小時(shí)因車輛離去而造成的損失。（北方交大2003年研究生考題，20分）解：例9.7某加油站只有一個(gè)加油管,接待等待加油的汽車.已知站內(nèi)只能停泊5輛汽車(含正在加油的汽車),后來的汽車不進(jìn)站而離去.汽車的平均到達(dá)速率為4輛/小時(shí),是泊松流.加油時(shí)間平均為10分鐘/輛,是負(fù)指數(shù)分布.求1.汽車一到達(dá)就能加油的概率;2計(jì)算和;3.汽車在站內(nèi)停留的全部時(shí)間的期望值;4.因客滿而離開加油站的損失概率.解:五.模型

在這個(gè)模型中，顧客總數(shù)為，當(dāng)顧客需要服務(wù)時(shí)，就進(jìn)入隊(duì)列等待；服務(wù)完以后就回到顧客中，如此循環(huán)往復(fù)。這是一種有限客源服務(wù)系統(tǒng)。典型問題是機(jī)器維修問題。設(shè)有臺(tái)機(jī)器在運(yùn)轉(zhuǎn)，單位時(shí)間內(nèi)平均出現(xiàn)故障的機(jī)器數(shù)即為顧客的平均到達(dá)速率，修理工維修一臺(tái)機(jī)器的平均時(shí)間就是平均服務(wù)時(shí)間。不加證明，給出該模型的各種公式：1、系統(tǒng)狀態(tài)概率的計(jì)算2、有限源系統(tǒng)的各項(xiàng)運(yùn)行指標(biāo)例9.8一位機(jī)修工負(fù)責(zé)3臺(tái)機(jī)器的維修工作。設(shè)每臺(tái)機(jī)器在修理之后平均運(yùn)行5天，平均修理一臺(tái)機(jī)器的時(shí)間為2天，修理時(shí)間服從負(fù)指數(shù)分布。求：1、機(jī)修工空閑的概率；2、3臺(tái)機(jī)器都出故障的概率；3、出故障的平均臺(tái)數(shù)及等待維修的平均機(jī)器數(shù)；4、平均停工時(shí)間；5、平均等待維修時(shí)間；6、評(píng)價(jià)這個(gè)系統(tǒng)的運(yùn)行情況。解：§5多服務(wù)臺(tái)排隊(duì)模型特點(diǎn):一個(gè)公共隊(duì)伍,并列多服務(wù)臺(tái)(c>1).有三種模型.設(shè)顧客到達(dá)的速率為,每個(gè)服務(wù)臺(tái)的服務(wù)速率均為,則整個(gè)服務(wù)系統(tǒng)的最大服務(wù)速率為

,服務(wù)強(qiáng)度為.各項(xiàng)指標(biāo)的計(jì)算公式如下:一、例9.9某售票處有三個(gè)窗口,顧客到達(dá)為泊松流,平均到達(dá)率為服務(wù)時(shí)間服務(wù)負(fù)指數(shù)分布,平均服務(wù)率設(shè)顧客到達(dá)后排成一列,依次向空閑窗口購票,求各項(xiàng)指標(biāo).解:顧客到達(dá)后必須等待的概率為現(xiàn)在對(duì)(M/M/c)和c個(gè)(M/M/1)系統(tǒng)作一個(gè)比較,看看哪一個(gè)系統(tǒng)更好一些.0.40.40.40.40.40.4仍使用上題的條件,顧客到達(dá)后排成三個(gè)隊(duì),每個(gè)隊(duì)的平均到達(dá)率為于是形成了三個(gè)(M/M/1)系統(tǒng),計(jì)算出相關(guān)數(shù)據(jù)并與上題進(jìn)行比較:M/M/3每個(gè)M/M/1服務(wù)臺(tái)空閑的概率0.07480.25顧客必須等待的概率0.570.75平均隊(duì)長1.70人2.25人總隊(duì)長3.95人9.00人總的停留時(shí)間4.39分10分排隊(duì)等待時(shí)間1.89