排隊論模型及實例
某維修中心在周末現(xiàn)只安排一名員工為顧客提供服務(wù)。新來,維修的顧客到達(dá)后,若已有顧客正在接受服務(wù),則需要排隊,等待。若排隊的人數(shù)過多,勢必會造成顧客抱怨,會影響到,公司產(chǎn)品的銷售;若維修人員多,會增加維修中心的支出,,如何調(diào)整兩者的關(guān)系,使得系統(tǒng)達(dá)到最優(yōu).,例10.1,排隊的例子,它是一個典型的排隊的例子,關(guān)于排隊的例子有很多,例如:,上下班坐公共汽車,等待公共汽車的排隊;顧客到商店購物形,成的排隊;病人到醫(yī)院看病形成的排隊;售票處購票形成的排,隊等;另一種排隊是物的排隊,例如文件等待打印或發(fā)送;路,口紅燈下面的汽車、自行車通過十字路口等等.,排隊現(xiàn)象是由兩個方面構(gòu)成,一方要求得到服務(wù),另一方設(shè),法給予服務(wù)。我們把要求得到服務(wù)的人或物(設(shè)備)統(tǒng)稱為,顧客,給予服務(wù)的服務(wù)人員或服務(wù)機構(gòu)統(tǒng)稱為服務(wù)員或服務(wù),臺。顧客與服務(wù)臺就構(gòu)成一個排隊系統(tǒng),或稱為隨機服務(wù)系,統(tǒng)。顯然缺少顧客或服務(wù)臺任何一方都不會形成排隊系統(tǒng).,對于任何一個排隊服務(wù)系統(tǒng),每一名顧客通過排隊服務(wù)系統(tǒng),總要經(jīng)過如下過程:顧客到達(dá)、排隊等待、接受服務(wù)和離,去,其過程如下圖所示:,顧客總體,隊 伍,輸出,輸入,服務(wù)臺,服務(wù)系統(tǒng),輸入過程,顧客源總體:顧客的來源可能是有限的,也可,能是無限的,2.,排隊服務(wù)系統(tǒng)的基本概念,到達(dá)的類型:顧客是單個到達(dá),或是成批到達(dá),相繼顧客到達(dá)的間隔時間:通常假定是相互獨,立、同分布的,有的是等距間隔時間,有的是,服從Poisson分布,有的是服從k階Erlang分布,輸入過程是描述顧客來源及顧客是按怎樣的規(guī)律抵達(dá)排隊系統(tǒng),排隊規(guī)則,損失制排隊系統(tǒng):顧客到達(dá)時,若有服務(wù)臺均被占,服務(wù)機構(gòu),又不允許顧客等待,此時該顧客就自動辭去,2.,排隊服務(wù)系統(tǒng)的基本概念,等待制排隊系統(tǒng):顧客到達(dá)時若所有服務(wù)臺均被占,他們,就排隊等待服務(wù)。在等待制系統(tǒng)中,服務(wù),順序又分為:先到先服務(wù),即顧客按到達(dá),的先后順序接受服務(wù);后到先服務(wù).,混合制排隊系統(tǒng):損失制與等待制的混合,分為隊長(容量),有限的混合制系統(tǒng),等待時間有限的混,合制系統(tǒng),以及逗留時間有限制的混合,系統(tǒng).,排隊規(guī)則是指服務(wù)允許不允許排隊,顧客是否愿意排隊,服務(wù)機構(gòu),服務(wù)臺的數(shù)目:在多個服務(wù)臺的情形下,是串,聯(lián)或是并聯(lián);,2.,排隊服務(wù)系統(tǒng)的基本概念,顧客所需的服務(wù)時間服從什么樣的概率分布,,每個顧客所需的服務(wù)時間是否相互獨立,是成,批服務(wù)或是單個服務(wù)等。常見顧客的服務(wù)時間,分布有:定長分布、負(fù)指數(shù)分布、超指數(shù)分,布、k階Erlang分布、幾何分布、一般分布等.,3.,符號表示,排隊論模型的記號是20世紀(jì)50年代初由D.G.Kendall(肯,達(dá)爾)引入的,通常由3,5個英文字母組成,其形式為,其中,A,表示輸入過程,,B,表示服務(wù)時間,,C,表示服務(wù)臺數(shù)目,,n,表示系統(tǒng)空間數(shù)。例如:,M/M/S/,表示輸入過程是,Poisson,流,服務(wù)時間服從負(fù),指數(shù)分布,系統(tǒng)有,S,個服務(wù)臺平行服務(wù),系統(tǒng)容量為無窮的,等待制排隊系統(tǒng),.,(2),M/G/1/,表示輸入過程是Poisson流,顧客所需的服務(wù),時間為獨立、服從一般概率分布,系統(tǒng)中只有一個服務(wù),臺,容量為無窮的等待制系統(tǒng).,GI/M/1/,表示輸入過程為顧客獨立到達(dá)且相繼到達(dá)的間,隔時間服從一船概率分布,服務(wù)時間是相互獨立、服從負(fù)指,數(shù)分布,系統(tǒng)中只有一個服務(wù)臺,容量為無窮的等待制系統(tǒng),3.,符號表示,(4),E,k,/G/1/K,表示相繼到達(dá)的間隔時間獨立、服從k階Erlang,分布,服務(wù)時間為獨立、服從一般概率分布,系統(tǒng)中只有一,個服務(wù)臺,容量為K的混合制系統(tǒng).,(5),D/M/S/K,表示相繼到達(dá)的間隔時間獨立、服從定長分布、,服務(wù)時間相互獨立、服從負(fù)指數(shù)分布,系統(tǒng)中有S個服務(wù)臺,平行服務(wù),容量為K的混合制系統(tǒng).,4.描述排隊系統(tǒng)的主要數(shù)量指標(biāo),隊長與等待隊長,隊長(通常記為,L,S,)是指在系統(tǒng)中的顧客的平均數(shù)(包括正在接受服務(wù)的顧客),而等待隊長(通常記為,L,q,)是指系統(tǒng)中排隊等待的顧客的平均數(shù),它們是顧客和服務(wù)機構(gòu)雙方都十分關(guān)心的數(shù)量指標(biāo)。顯然隊長等于等待隊長加上正在被服務(wù)的顧客數(shù).,顧客的平均等待時間與平均逗留時間,顧客的平均等待時間(通常記為,W,q,)是指從顧客進入系,統(tǒng)的時刻起直到開始接受服務(wù)止的平均時間。平均逗,留時間(通常記為,W,s,)是指顧客在系統(tǒng)中的平均等待時,間與平均服務(wù)時間之和。平均等待時間與平均服務(wù)時,間是顧客最關(guān)心的數(shù)量指標(biāo).,4.描述排隊系統(tǒng)的主要數(shù)量指標(biāo),系統(tǒng)的忙期與閑期,從顧客到達(dá)空閑的系統(tǒng),服務(wù)立即開始,直到系統(tǒng)再次變?yōu)榭臻e,這段時間是系統(tǒng)連續(xù)繁忙的時間,我們稱為系統(tǒng)的忙期,它反映了系統(tǒng)中服務(wù)機構(gòu)的工作強度,是衡量服務(wù)機構(gòu)利用效率的指標(biāo),即,與忙期對應(yīng)的是系統(tǒng)的閑期,即系統(tǒng)連續(xù)保持空閑的時,間長度.,服務(wù)機構(gòu),工作強度,用于服務(wù)顧客的時間,服務(wù)設(shè)施總的服務(wù)時間,用于服務(wù)顧客的時間,服務(wù)設(shè)施總的服務(wù)時間,5.Little(利特爾)公式,用,表示單位時間內(nèi)顧客到達(dá)的平均數(shù),表示單位時間內(nèi),被服務(wù)完畢離去的平均顧客數(shù),因此1/,表示相鄰兩顧客到,達(dá)的平均時間,1/,表示對每個顧客的平均服務(wù)時間.,J.D.C.Little給出了如下公式:,6.與排隊論模型有關(guān)的LINGO函數(shù),(1)peb(load,S),該函數(shù)的返回值是當(dāng)?shù)竭_(dá)負(fù)荷為load,服務(wù)系統(tǒng)中有S個服務(wù),器且允許排隊時系統(tǒng)繁忙的概率,也就是顧客等待的概率.,(2)pel(load,S),該函數(shù)的返回值是當(dāng)?shù)竭_(dá)負(fù)荷為load,服務(wù)系統(tǒng)中有S個服務(wù),器且不允許排隊時系統(tǒng)損失概率,也就是顧客得不到服務(wù)離,開的概率.,(3)pfs(load,S,K),該函數(shù)的返回值是當(dāng)?shù)竭_(dá)負(fù)荷為load,顧客數(shù)為K,平行服務(wù),器數(shù)量為S時,有限源的Poisson服務(wù)系統(tǒng)等待或返修顧客數(shù),的期望值.,10.2 等待制排隊模型,等待制排隊模型中最常見的模型是,即顧客到達(dá)系統(tǒng)的相繼到達(dá)時間間隔獨立,且服從參數(shù),為,的負(fù)指數(shù)分布(即輸入過程為Poisson過程),服務(wù)臺,的服務(wù)時間也獨立同分布,且服從參數(shù)為,的負(fù)指數(shù)分,布,而且系統(tǒng)空間無限,允許永遠(yuǎn)排隊.,1.,等待制排隊模型的基本參數(shù),(1),顧客等待的概率P,wait,其中S是服務(wù)臺或服務(wù)員的個數(shù),load是系統(tǒng)到達(dá)負(fù)荷,,即 load=,/,=R*T,式中R表示,T表示1/,R表示,在下面的程序中,因此,R或,是顧客的平均到達(dá)率,,是顧客的平均被服務(wù)數(shù),T 就是平均服務(wù)時間.,1.,等待制排隊模型的基本參數(shù),(2),顧客的平均等待時間W,q,其中T/(S-load)是一個重要指標(biāo),可以看成一個“合理的,長度間隔”。注意,當(dāng)loadS時,此值趨于無窮。也就,是說,系統(tǒng)負(fù)荷接近服從器的個數(shù)時,顧客平均等待時,間將趨于無窮.,當(dāng)load S時,上式W,q,無意義。其直觀的解釋是:當(dāng)系統(tǒng),負(fù)荷超過服從器的個數(shù)時,排隊系統(tǒng)達(dá)不到穩(wěn)定的狀態(tài),其隊將越排越長.,1.,等待制排隊模型的基本參數(shù),顧客的平均逗留時間W,s,、隊長L,s,和等待隊長L,q,這三個值可由,Little,公式直接得到,2.等待制排隊模型的計算實例,S=1,的情況,(,M/M/1/,),即只有一個服務(wù)臺或一名服務(wù)員服務(wù)的情況,.,例10.2,某維修中心在周末現(xiàn)只安排一名員工為顧客提供服務(wù)。新來維修的顧客到達(dá)后,若已有顧客正在接受服務(wù),則需要排隊等待。假設(shè)來維修的顧客到達(dá)過程為Poisson流,平均4人/小時,維修時間服從負(fù)指數(shù)分布,平均需要6分鐘。試求該系統(tǒng)的主要數(shù)量指標(biāo)。,解,按照式上面分析,編寫LINGO程序,其中R=4,T=6/60,load=R.T,S=1.程序名:exam1002.lg4.,2.等待制排隊模型的計算實例,由此得到:,(1)系統(tǒng)平均隊長 L,s,=0.6666667,(2)系統(tǒng)平均等待隊長 L,q,=0.2666667,(3)顧客平均逗留時間 W,s,=0.1666667(小時)=10(分鐘),(4)顧客平均等待時間 W,q,=0.06666667(小時)=4(分鐘),(5)系統(tǒng)繁忙概率 P,wait,=0.4,在商業(yè)中心處設(shè)置一臺ATM機,假設(shè)來取錢的顧客平均每分鐘0.6個,而每個顧客的平均取錢的時間為1.25分鐘,試求該ATM機的主要數(shù)量指標(biāo).,解,只需將上例LINGO程序作如下改動:R=0.6,T=1.25 即可得到結(jié)果.程序名:exam1003.lg4.,計算結(jié)果見運行,例,10.3,即平均隊長為3人,平均等待隊長為2.25人,顧客平均逗留時間5分鐘,顧客平均等待時間為3.75分鐘,系統(tǒng)繁忙概率為0.75.,S1,的情況,(,M/M/S/,),表示有多個服務(wù)臺或多名服務(wù)員服務(wù)的情況,例10.,設(shè)打印室有3名打字員,平均每個文件的打印時間為10分鐘,而文件的到達(dá)率為每小時15件,試求該打印室的主要數(shù)量指標(biāo).,解,按照上面分析,編寫LINGO程序,程名:exam1004.lg4.,計算結(jié)果分析,:即在打字室內(nèi)現(xiàn)有的平均文件數(shù)為6.011件,等待打印平均文件數(shù)3.511件,每份文件在打字室平均停留時間為0.400小時(24分鐘),排隊等待打印的平均時間0.234小時(14分鐘),打印室不空閑的概率0.702.,某售票點有兩個售票窗口,顧客按參數(shù),=8人/分鐘的Poisson流到達(dá),每個窗口的售票時間均服從參數(shù),=5人/分鐘的負(fù)指數(shù)分布,試比較以下兩種排隊方案的運行指標(biāo).,(1)顧客到達(dá)后,以1/2的概率站成兩個隊列,如右圖所示:,例,10.5,(2),顧客到達(dá)后排成一個隊列,顧客發(fā)現(xiàn)哪個窗口空時,他就接受該窗口的服務(wù),如下圖所示:,解,(1)實質(zhì)上是兩個獨立的,M/M/1/,系統(tǒng),其參數(shù)S=1,R=,1,=,2,=4,T=1/,=,1/5=0.2,編寫其LINGO程序,程序名:exam1005a.lg4.計算結(jié)果見運行,例,10.5,(2)是兩個并聯(lián)系統(tǒng),其參數(shù)S=2,R=,=8,T=1/,=,1/5=0.2,編寫其LINGO程序,程序名:exam1005b.lg4.計算結(jié)果見運行,兩種系統(tǒng)的計算結(jié)果,從上表中所列的計算結(jié)果可以看出,在服務(wù)臺的各種性能指,標(biāo)不變的情況下,采用不同的排隊方式,其結(jié)果是不同的.從,表得到,采用多隊列排隊系統(tǒng)的隊長為4,而采用單排隊系統(tǒng),總隊長為4.444,也就是說每一個子隊的隊長為2.222,幾乎是,多列隊排隊系統(tǒng)的1/2,效率幾乎提高了一倍.,例,10.5比較分析,10.3 損失制排隊模型,損失制排隊模型通常記為,當(dāng)S個服務(wù)器被占用后,顧客自動離去。其模型的基本,參數(shù)與等待制排隊模型有些不同,我們關(guān)心如下指標(biāo):,(1),系統(tǒng)損失的概率,其中l(wèi)oad是系統(tǒng)到達(dá)負(fù)荷,S是服務(wù)臺或服務(wù)員的個數(shù).,1.,損失制排隊模型的基本參數(shù),(2),單位時間內(nèi)平均進入系統(tǒng)的顧客數(shù)(,e,或R,e,),(3),系統(tǒng)的相對通過能力Q與絕對通過能力A,(4),系統(tǒng)在單位時間內(nèi)占用服務(wù)臺(或服務(wù)員)的均值L,s,注意:在損失制排隊系統(tǒng)中,L,q,=0,即等待隊長為0.,(5),系統(tǒng)服務(wù)臺(或服務(wù)員)的效率,(6),顧客在系統(tǒng)內(nèi)平均逗留時間(由于W,q,=0,即為W,s,),注意:在損失制排隊系統(tǒng)中,W,q,=0,即等待時間為0.,在上述公式中,引入,e,(或R,e,)是十分重要的,因為盡管,顧客的以平均,(或R)的速率到達(dá)服務(wù)系統(tǒng),但當(dāng)系統(tǒng),被占滿后,有一部分顧客會自動離去,因此,真正進入系,統(tǒng)的顧客輸入率是,e,它小于,.,2.損失制排隊模型的計算實例,S=1,的情況,(,M/M/1/,1,),例10.6,設(shè)某條電話線,平均每分鐘有0.6次呼喚,若每次通話時間平均為1.25分鐘,求系統(tǒng)相應(yīng)的參數(shù)指標(biāo)。,解,按照上面分析,編寫LINGO程序,其中S=1,R=,=0.6,T=1/,=1.25,程序名:exam1006.lg4,結(jié)果見運行,系統(tǒng)的顧客損失率為43%,即43%的電話沒有接通,有57%,的電話得到了服務(wù),通話率為平均每分鐘有0.195次,系統(tǒng)的,服務(wù)效率為43%.對于一個服務(wù)臺的損失制系統(tǒng),系統(tǒng)的服,務(wù)效率等于