運籌學排隊論2

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

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

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

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

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

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

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

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

//FCFS模型例9.5在某倉庫卸貨臺裝卸設備的設計方案中,有三個方案可供選擇,分別記為甲,乙,丙,要求選取使總費用最小的方案.有關(guān)數(shù)據(jù)如下:方案每天固定費用(元)可變操作費(c元/天)平均卸貨數(shù)(袋/小時甲601001000乙1301502000丙2502006000設貨車按泊松流到達,平均每天(按10小時計算)到達15輛,每車平均裝貨500袋,卸貨時間服從負指數(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)特點:泊松輸入過程,服務時間為負指數(shù)分布,單服務臺,系統(tǒng)內(nèi)只允許有N個顧客,客源無限,先到先服務.同前面的分析一樣,系統(tǒng)處于平穩(wěn)狀態(tài)時,對于每個狀態(tài)來說,轉(zhuǎn)入率應等于轉(zhuǎn)出率,在狀態(tài)0處有在狀態(tài)1處有在狀態(tài)N-1處有在狀態(tài)N處有綜合以上的結(jié)果可推出:

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

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

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