《排隊論模型及實例》由會員分享，可在線閱讀，更多相關《排隊論模型及實例（48頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、某維修中心在周末現(xiàn)只安排一名員工為顧客提供服務。新來,維修的顧客到達后，若已有顧客正在接受服務，則需要排隊,等待。若排隊的人數(shù)過多，勢必會造成顧客抱怨，會影響到,公司產(chǎn)品的銷售；若維修人員多，會增加維修中心的支出，,如何調(diào)整兩者的關系，使得系統(tǒng)達到最優(yōu).,例10.1,排隊的例子,它是一個典型的排隊的例子,關于排隊的例子有很多,例如：,上下班坐公共汽車,等待公共汽車的排隊;顧客到商店購物形,成的排隊;病人到醫(yī)院看病形成的排隊;售票處購票形成的排,隊等;另一種排隊是物的排隊，例如文件等待打印或發(fā)送;路,口紅燈下面的汽車、自行車通過十字路口等等.,排隊現(xiàn)象是由兩個方面構成，一方要求得到服務，另一方設

2、,法給予服務。我們把要求得到服務的人或物（設備）統(tǒng)稱為,顧客,給予服務的服務人員或服務機構統(tǒng)稱為服務員或服務,臺。顧客與服務臺就構成一個排隊系統(tǒng)，或稱為隨機服務系,統(tǒng)。顯然缺少顧客或服務臺任何一方都不會形成排隊系統(tǒng).,對于任何一個排隊服務系統(tǒng)，每一名顧客通過排隊服務系統(tǒng),總要經(jīng)過如下過程：顧客到達、排隊等待、接受服務和離,去，其過程如下圖所示:,顧客總體,隊 伍,輸出,輸入,服務臺,服務系統(tǒng),輸入過程,顧客源總體：顧客的來源可能是有限的，也可,能是無限的,2.,排隊服務系統(tǒng)的基本概念,到達的類型：顧客是單個到達，或是成批到達,相繼顧客到達的間隔時間：通常假定是相互獨,立、同分布的，有的是等距間

3、隔時間，有的是,服從Poisson分布，有的是服從k階Erlang分布,輸入過程是描述顧客來源及顧客是按怎樣的規(guī)律抵達排隊系統(tǒng),排隊規(guī)則,損失制排隊系統(tǒng)：顧客到達時,若有服務臺均被占,服務機構,又不允許顧客等待,此時該顧客就自動辭去,2.,排隊服務系統(tǒng)的基本概念,等待制排隊系統(tǒng)：顧客到達時若所有服務臺均被占，他們,就排隊等待服務。在等待制系統(tǒng)中,服務,順序又分為：先到先服務,即顧客按到達,的先后順序接受服務；后到先服務.,混合制排隊系統(tǒng)：損失制與等待制的混合，分為隊長(容量),有限的混合制系統(tǒng)，等待時間有限的混,合制系統(tǒng)，以及逗留時間有限制的混合,系統(tǒng).,排隊規(guī)則是指服務允許不允許排隊，顧客是

4、否愿意排隊,服務機構,服務臺的數(shù)目:在多個服務臺的情形下，是串,聯(lián)或是并聯(lián)；,2.,排隊服務系統(tǒng)的基本概念,顧客所需的服務時間服從什么樣的概率分布，,每個顧客所需的服務時間是否相互獨立，是成,批服務或是單個服務等。常見顧客的服務時間,分布有：定長分布、負指數(shù)分布、超指數(shù)分,布、k階Erlang分布、幾何分布、一般分布等.,3.,符號表示,排隊論模型的記號是20世紀50年代初由D.G.Kendall(肯,達爾)引入的，通常由3,5個英文字母組成，其形式為,其中,A,表示輸入過程，,B,表示服務時間，,C,表示服務臺數(shù)目，,n,表示系統(tǒng)空間數(shù)。例如:,M/M/S/,表示輸入過程是,Poisson,

5、流,服務時間服從負,指數(shù)分布,系統(tǒng)有,S,個服務臺平行服務,系統(tǒng)容量為無窮的,等待制排隊系統(tǒng),.,(2),M/G/1/,表示輸入過程是Poisson流，顧客所需的服務,時間為獨立、服從一般概率分布，系統(tǒng)中只有一個服務,臺，容量為無窮的等待制系統(tǒng).,GI/M/1/,表示輸入過程為顧客獨立到達且相繼到達的間,隔時間服從一船概率分布，服務時間是相互獨立、服從負指,數(shù)分布，系統(tǒng)中只有一個服務臺，容量為無窮的等待制系統(tǒng),3.,符號表示,(4),E,k,/G/1/K,表示相繼到達的間隔時間獨立、服從k階Erlang,分布，服務時間為獨立、服從一般概率分布，系統(tǒng)中只有一,個服務臺，容量為K的混合制系統(tǒng).,(

6、5),D/M/S/K,表示相繼到達的間隔時間獨立、服從定長分布、,服務時間相互獨立、服從負指數(shù)分布，系統(tǒng)中有S個服務臺,平行服務，容量為K的混合制系統(tǒng).,4.描述排隊系統(tǒng)的主要數(shù)量指標,隊長與等待隊長,隊長(通常記為,L,S,)是指在系統(tǒng)中的顧客的平均數(shù)(包括正在接受服務的顧客),而等待隊長(通常記為,L,q,)是指系統(tǒng)中排隊等待的顧客的平均數(shù)，它們是顧客和服務機構雙方都十分關心的數(shù)量指標。顯然隊長等于等待隊長加上正在被服務的顧客數(shù).,顧客的平均等待時間與平均逗留時間,顧客的平均等待時間(通常記為,W,q,)是指從顧客進入系,統(tǒng)的時刻起直到開始接受服務止的平均時間。平均逗,留時間(通常記為,W

7、,s,)是指顧客在系統(tǒng)中的平均等待時,間與平均服務時間之和。平均等待時間與平均服務時,間是顧客最關心的數(shù)量指標.,4.描述排隊系統(tǒng)的主要數(shù)量指標,系統(tǒng)的忙期與閑期,從顧客到達空閑的系統(tǒng)，服務立即開始，直到系統(tǒng)再次變?yōu)榭臻e，這段時間是系統(tǒng)連續(xù)繁忙的時間，我們稱為系統(tǒng)的忙期，它反映了系統(tǒng)中服務機構的工作強度，是衡量服務機構利用效率的指標，即,與忙期對應的是系統(tǒng)的閑期，即系統(tǒng)連續(xù)保持空閑的時,間長度.,服務機構,工作強度,用于服務顧客的時間,服務設施總的服務時間,用于服務顧客的時間,服務設施總的服務時間,5.Little（利特爾）公式,用,表示單位時間內(nèi)顧客到達的平均數(shù),表示單位時間內(nèi),被服務完畢離

8、去的平均顧客數(shù)，因此1/,表示相鄰兩顧客到,達的平均時間，1/,表示對每個顧客的平均服務時間.,J.D.C.Little給出了如下公式：,6.與排隊論模型有關的LINGO函數(shù),(1)peb(load,S),該函數(shù)的返回值是當?shù)竭_負荷為load,服務系統(tǒng)中有S個服務,器且允許排隊時系統(tǒng)繁忙的概率,也就是顧客等待的概率.,(2)pel(load,S),該函數(shù)的返回值是當?shù)竭_負荷為load,服務系統(tǒng)中有S個服務,器且不允許排隊時系統(tǒng)損失概率,也就是顧客得不到服務離,開的概率.,(3)pfs(load,S,K),該函數(shù)的返回值是當?shù)竭_負荷為load,顧客數(shù)為K,平行服務,器數(shù)量為S時,有限源的Pois

9、son服務系統(tǒng)等待或返修顧客數(shù),的期望值.,10.2 等待制排隊模型,等待制排隊模型中最常見的模型是,即顧客到達系統(tǒng)的相繼到達時間間隔獨立，且服從參數(shù),為,的負指數(shù)分布(即輸入過程為Poisson過程),服務臺,的服務時間也獨立同分布,且服從參數(shù)為,的負指數(shù)分,布，而且系統(tǒng)空間無限，允許永遠排隊.,1.,等待制排隊模型的基本參數(shù),(1),顧客等待的概率P,wait,其中S是服務臺或服務員的個數(shù)，load是系統(tǒng)到達負荷，,即 load=,/,=R*T,式中R表示,T表示1/,R表示,在下面的程序中，因此，R或,是顧客的平均到達率，,是顧客的平均被服務數(shù)，T 就是平均服務時間.,1.,等待制排隊模

10、型的基本參數(shù),(2),顧客的平均等待時間W,q,其中T/(S-load)是一個重要指標，可以看成一個“合理的,長度間隔”。注意，當loadS時，此值趨于無窮。也就,是說，系統(tǒng)負荷接近服從器的個數(shù)時，顧客平均等待時,間將趨于無窮.,當load S時,上式W,q,無意義。其直觀的解釋是：當系統(tǒng),負荷超過服從器的個數(shù)時,排隊系統(tǒng)達不到穩(wěn)定的狀態(tài),其隊將越排越長.,1.,等待制排隊模型的基本參數(shù),顧客的平均逗留時間W,s,、隊長L,s,和等待隊長L,q,這三個值可由,Little,公式直接得到,2.等待制排隊模型的計算實例,S=1,的情況,(,M/M/1/,),即只有一個服務臺或一名服務員服務的情況,

11、.,例10.2,某維修中心在周末現(xiàn)只安排一名員工為顧客提供服務。新來維修的顧客到達后，若已有顧客正在接受服務，則需要排隊等待。假設來維修的顧客到達過程為Poisson流，平均4人/小時，維修時間服從負指數(shù)分布，平均需要6分鐘。試求該系統(tǒng)的主要數(shù)量指標。,解,按照式上面分析,編寫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(分鐘

12、),(4)顧客平均等待時間 W,q,=0.06666667(小時)=4(分鐘),(5)系統(tǒng)繁忙概率 P,wait,=0.4,在商業(yè)中心處設置一臺ATM機，假設來取錢的顧客平均每分鐘0.6個，而每個顧客的平均取錢的時間為1.25分鐘，試求該ATM機的主要數(shù)量指標.,解,只需將上例LINGO程序作如下改動：R=0.6,T=1.25 即可得到結果.程序名:exam1003.lg4.,計算結果見運行,例,10.3,即平均隊長為3人，平均等待隊長為2.25人，顧客平均逗留時間5分鐘，顧客平均等待時間為3.75分鐘，系統(tǒng)繁忙概率為0.75.,S1,的情況,(,M/M/S/,),表示有多個服務臺或多名服務員

13、服務的情況,例10.,設打印室有3名打字員,平均每個文件的打印時間為10分鐘，而文件的到達率為每小時15件，試求該打印室的主要數(shù)量指標.,解,按照上面分析,編寫LINGO程序,程名:exam1004.lg4.,計算結果分析,：即在打字室內(nèi)現(xiàn)有的平均文件數(shù)為6.011件，等待打印平均文件數(shù)3.511件，每份文件在打字室平均停留時間為0.400小時（24分鐘），排隊等待打印的平均時間0.234小時(14分鐘),打印室不空閑的概率0.702.,某售票點有兩個售票窗口，顧客按參數(shù),=8人/分鐘的Poisson流到達，每個窗口的售票時間均服從參數(shù),=5人/分鐘的負指數(shù)分布，試比較以下兩種排隊方案的運行指

14、標.,(1)顧客到達后,以1/2的概率站成兩個隊列，如右圖所示：,例,10.5,(2),顧客到達后排成一個隊列,顧客發(fā)現(xiàn)哪個窗口空時,他就接受該窗口的服務，如下圖所示:,解,(1)實質(zhì)上是兩個獨立的,M/M/1/,系統(tǒng),其參數(shù)S=1,R=,1,=,2,=4,T=1/,=,1/5=0.2,編寫其LINGO程序，程序名:exam1005a.lg4.計算結果見運行,例,10.5,(2)是兩個并聯(lián)系統(tǒng),其參數(shù)S=2,R=,=8,T=1/,=,1/5=0.2,編寫其LINGO程序,程序名:exam1005b.lg4.計算結果見運行,兩種系統(tǒng)的計算結果,從上表中所列的計算結果可以看出,在服務臺的各種性能指

15、,標不變的情況下,采用不同的排隊方式,其結果是不同的.從,表得到,采用多隊列排隊系統(tǒng)的隊長為4,而采用單排隊系統(tǒng),總隊長為4.444,也就是說每一個子隊的隊長為2.222,幾乎是,多列隊排隊系統(tǒng)的1/2,效率幾乎提高了一倍.,例,10.5比較分析,10.3 損失制排隊模型,損失制排隊模型通常記為,當S個服務器被占用后，顧客自動離去。其模型的基本,參數(shù)與等待制排隊模型有些不同,我們關心如下指標：,(1),系統(tǒng)損失的概率,其中l(wèi)oad是系統(tǒng)到達負荷,S是服務臺或服務員的個數(shù).,1.,損失制排隊模型的基本參數(shù),(2),單位時間內(nèi)平均進入系統(tǒng)的顧客數(shù)(,e,或R,e,),(3),系統(tǒng)的相對通過能力Q與

16、絕對通過能力A,(4),系統(tǒng)在單位時間內(nèi)占用服務臺(或服務員)的均值L,s,注意:在損失制排隊系統(tǒng)中,L,q,=0,即等待隊長為0.,(5),系統(tǒng)服務臺（或服務員）的效率,(6),顧客在系統(tǒng)內(nèi)平均逗留時間(由于W,q,=0,即為W,s,）,注意:在損失制排隊系統(tǒng)中,W,q,=0,即等待時間為0.,在上述公式中,引入,e,(或R,e,)是十分重要的,因為盡管,顧客的以平均,(或R)的速率到達服務系統(tǒng),但當系統(tǒng),被占滿后,有一部分顧客會自動離去,因此,真正進入系,統(tǒng)的顧客輸入率是,e,它小于,.,2.損失制排隊模型的計算實例,S=1,的情況,(,M/M/1/,1,),例10.6,設某條電話線，平均每分鐘有0.6次呼喚，若每次通話時間平均為1.25分鐘，求系統(tǒng)相應的參數(shù)指標。,解,按照上面分析,編寫LINGO程序，其中S=1,R=,=0.6,T=1/,=1.25,程序名:exam1006.lg4，結果見運行,系統(tǒng)的顧客損失率為43%,即43%的電話沒有接通,有57%,的電話得到了服務,通話率為平均每分鐘有0.195次,系統(tǒng)的,服務效率為43%.對于一個服務臺的損失制系統(tǒng),系統(tǒng)的服,務效率等于