排隊(duì)論模型及實(shí)例

《排隊(duì)論模型及實(shí)例》由會(huì)員分享，可在線閱讀，更多相關(guān)《排隊(duì)論模型及實(shí)例（48頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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

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

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

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

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

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

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

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

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

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

11、.,例10.2,某維修中心在周末現(xiàn)只安排一名員工為顧客提供服務(wù)。新來維修的顧客到達(dá)后，若已有顧客正在接受服務(wù)，則需要排隊(duì)等待。假設(shè)來維修的顧客到達(dá)過程為Poisson流，平均4人/小時(shí)，維修時(shí)間服從負(fù)指數(shù)分布，平均需要6分鐘。試求該系統(tǒng)的主要數(shù)量指標(biāo)。,解,按照式上面分析,編寫LINGO程序，其中R=4,T=6/60,load=R.T,S=1.程序名:exam1002.lg4.,2.等待制排隊(duì)模型的計(jì)算實(shí)例,由此得到：,(1)系統(tǒng)平均隊(duì)長(zhǎng) L,s,=0.6666667,(2)系統(tǒng)平均等待隊(duì)長(zhǎng) L,q,=0.2666667,(3)顧客平均逗留時(shí)間 W,s,=0.1666667(小時(shí))=10(分鐘

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

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

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

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

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