運籌學(xué)排隊論2

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

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

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

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

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

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

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

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

//FCFS模型例9.5在某倉庫卸貨臺裝卸設(shè)備的設(shè)計方案中,有三個方案可供選擇,分別記為甲,乙,丙,要求選取使總費用最小的方案.有關(guān)數(shù)據(jù)如下:方案每天固定費用(元)可變操作費(c元/天)平均卸貨數(shù)(袋/小時甲601001000乙1301502000丙2502006000設(shè)貨車按泊松流到達(dá),平均每天(按10小時計算)到達(dá)15輛,每車平均裝貨500袋,卸貨時間服從負(fù)指數(shù)分布,每輛車停留1小時的損失為10元,求總費用最小的方案.解:每個方案的費用綜合如下:方案固定費用可變費用/天停留費用/天總費用/天甲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)決策:乙方案總費用最小.012N-1N…四.系統(tǒng)系統(tǒng)特點:泊松輸入過程,服務(wù)時間為負(fù)指數(shù)分布,單服務(wù)臺,系統(tǒng)內(nèi)只允許有N個顧客,客源無限,先到先服務(wù).同前面的分析一樣,系統(tǒng)處于平穩(wěn)狀態(tài)時,對于每個狀態(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個顧客時,新到的顧客就不進(jìn)入系統(tǒng)了.因為所有的狀態(tài)概率之和等于1,所以歸納為排隊系統(tǒng)中各種指標(biāo)的計算:設(shè)表示有效到達(dá)率,即實際進(jìn)入系統(tǒng)的顧客到達(dá)速率,則由利特爾公式補(bǔ)充當(dāng)時的公式例9.6某汽車檢測站有一條檢測線，要求做檢測的車輛按泊松流到達(dá)，平均每小時6輛，每輛車的檢測時間服從負(fù)指數(shù)分布，平均每輛10分鐘，用于等待檢測的停車泊位有5個，當(dāng)無停車泊位時，來檢測的車輛自動離去。試計算試計算：1、某車輛一到達(dá)就可進(jìn)行檢測的概率；2、等待檢測的平均車數(shù)；3、每輛車在檢測線上等待的期望時間；4、在可能到來的車輛中，有百分之幾不等待離開；5、如果車輛因停車泊位全部被占用而離去，每輛車損失a元，求每小時因車輛離去而造成的損失。（北方交大2003年研究生考題，20分）解：例9.7某加油站只有一個加油管,接待等待加油的汽車.已知站內(nèi)只能停泊5輛汽車(含正在加油的汽車),后來的汽車不進(jìn)站而離去.汽車的平均到達(dá)速率為4輛/小時,是泊松流.加油時間平均為10分鐘/輛,是負(fù)指數(shù)分布.求1.汽車一到達(dá)就能加油的概率;2計算和;3.汽車在站內(nèi)停留的全部時間的期望值;4.因客滿而離開加油站的損失概率.解:五.模型

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

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