排隊(duì)論大學(xué)課件9多服務(wù)窗排隊(duì)模型

1、1lM/M/n的排隊(duì)模型的排隊(duì)模型服務(wù)窗個(gè)數(shù)為多個(gè)服務(wù)窗個(gè)數(shù)為多個(gè)假定單個(gè)服務(wù)窗的服務(wù)率為假定單個(gè)服務(wù)窗的服務(wù)率為 ，則系統(tǒng)在某狀態(tài)，則系統(tǒng)在某狀態(tài)下的消亡率為下的消亡率為j ，j是此狀態(tài)下正在忙的服務(wù)窗個(gè)是此狀態(tài)下正在忙的服務(wù)窗個(gè)數(shù)數(shù) 2l 顧客到達(dá)的間隔時(shí)間顧客到達(dá)的間隔時(shí)間負(fù)指數(shù)分布，參數(shù)為負(fù)指數(shù)分布，參數(shù)為 l 顧客接受服務(wù)的時(shí)間顧客接受服務(wù)的時(shí)間負(fù)指數(shù)分布，參數(shù)為負(fù)指數(shù)分布，參數(shù)為 l 系統(tǒng)有系統(tǒng)有n個(gè)服務(wù)窗個(gè)服務(wù)窗l(fā) 系統(tǒng)最多容納顧客系統(tǒng)最多容納顧客n個(gè)個(gè) 因系統(tǒng)滿(mǎn)員造成顧客損失因系統(tǒng)滿(mǎn)員造成顧客損失3l 0k-121k23(k-1)kn-1nn(n-1)0,1,2,., 0,1,

2、2,.,11,2,3,.,kkEnknkknM/M/n/n排隊(duì)模型的狀態(tài)流圖排隊(duì)模型的狀態(tài)流圖4l求平穩(wěn)分布求平穩(wěn)分布0101011001101()!1!kkkknkkknkkkknkpppoffered loadkkppkpkk5l 目標(biāo)參量目標(biāo)參量P損損稱(chēng)為愛(ài)爾蘭損失公式，又稱(chēng)愛(ài)爾蘭稱(chēng)為愛(ài)爾蘭損失公式，又稱(chēng)愛(ài)爾蘭B公式，歐洲人稱(chēng)公式，歐洲人稱(chēng)為愛(ài)爾蘭第一公式為愛(ài)爾蘭第一公式 1101110/ !/ !( ,)( ,)!nknknknknknB nB nk6l愛(ài)爾蘭愛(ài)爾蘭B公式的廣泛性：公式的廣泛性：我們把一個(gè)具有泊松輸入的損失制排隊(duì)系統(tǒng)稱(chēng)為愛(ài)爾蘭損失制系統(tǒng)愛(ài)爾蘭損失制系統(tǒng)，這種損失制系統(tǒng)對(duì)

3、于任何服務(wù)時(shí)間分布，它在統(tǒng)計(jì)平衡條件下的狀態(tài)概率都相同與M/M/n/n相同。 即M/M/n/n排隊(duì)系統(tǒng)的平穩(wěn)分布M/G/n/n排隊(duì)系統(tǒng)的平穩(wěn)分布78 服務(wù)窗占用的均值：服務(wù)窗占用的均值：服務(wù)窗的效率（勞動(dòng)強(qiáng)度）服務(wù)窗的效率（勞動(dòng)強(qiáng)度）(1)enp0.neskkeseLLkpLW服服eLnn服9l 顧客到達(dá)的間隔時(shí)間顧客到達(dá)的間隔時(shí)間負(fù)指數(shù)分布，參數(shù)為負(fù)指數(shù)分布，參數(shù)為 l 顧客接受服務(wù)的時(shí)間顧客接受服務(wù)的時(shí)間負(fù)指數(shù)分布，參數(shù)為負(fù)指數(shù)分布，參數(shù)為 l 系統(tǒng)有系統(tǒng)有n個(gè)服務(wù)窗個(gè)服務(wù)窗l(fā) 系統(tǒng)最多容納顧客系統(tǒng)最多容納顧客 個(gè)個(gè) 100,1,2,.kkEkknnkn0n-121n23(n-1)nn+1

4、n+2nnnn個(gè)服務(wù)窗全忙服務(wù)窗還有空閑11l 求平穩(wěn)分布求平穩(wěn)分布1,1n令，10010001111000!11! 1kkkkknkk nkkknnknppknkkpnppknn nnppkn12l目標(biāo)參量目標(biāo)參量P損=0A=Q=1平均等待隊(duì)長(zhǎng)平均服務(wù)隊(duì)長(zhǎng)11021().(1)!()nqkk nLkn ppnn110.nkkkk nLkpnpn服13平均系統(tǒng)隊(duì)長(zhǎng)平均系統(tǒng)隊(duì)長(zhǎng)平均等待時(shí)間平均等待時(shí)間平均系統(tǒng)內(nèi)逗留時(shí)間平均系統(tǒng)內(nèi)逗留時(shí)間110121(1)!()nsqLLLpnn服1010221(1)!()!(1)nnqqLppWnnn n1sssqqLWWWWW服14來(lái)到系統(tǒng)的顧客必須排隊(duì)等待的

5、概率來(lái)到系統(tǒng)的顧客必須排隊(duì)等待的概率稱(chēng)為愛(ài)爾蘭等待公式，又稱(chēng)愛(ài)爾蘭稱(chēng)為愛(ài)爾蘭等待公式，又稱(chēng)愛(ài)爾蘭C公式，歐洲公式，歐洲人稱(chēng)為愛(ài)爾蘭第二公式人稱(chēng)為愛(ài)爾蘭第二公式101( ,)( ,)!.nkkk nk nnnC nC nppnnpn0.4*30.3*3M/M/33個(gè)個(gè)M/M/11個(gè)個(gè)M/M/1p00.07480.25(每個(gè)子系統(tǒng)）每個(gè)子系統(tǒng)）0.25顧客等候概率顧客等候概率0.570.750.75Lq1.76.75（整個(gè)系統(tǒng)）（整個(gè)系統(tǒng)）2.25Ls3.959.00 （整個(gè)系統(tǒng)）（整個(gè)系統(tǒng)）3.00Ws4.3910 3.33Wq1.897.5 2.50.4

6、*316l 顧客到達(dá)間隔時(shí)間顧客到達(dá)間隔時(shí)間負(fù)指數(shù)分布，參數(shù)為負(fù)指數(shù)分布，參數(shù)為 l 顧客接受服務(wù)的時(shí)間顧客接受服務(wù)的時(shí)間負(fù)指數(shù)分布，參數(shù)為負(fù)指數(shù)分布，參數(shù)為 mnm-n17l 0,1,2,. 010kkEmkmkknnnkm0n-121n23(n-1)nn+1nn個(gè)服務(wù)窗全忙服務(wù)窗還有空閑nmn18l 平穩(wěn)分布平穩(wěn)分布1,n令100100011111001100!111!1(1)1!kkkkknkk nkkknm nnkknnknppknkkpnppnkmn nnpknpnmnkn 19l 目標(biāo)參量目標(biāo)參量系統(tǒng)的損失概率系統(tǒng)的損失概率 P損損系統(tǒng)的相對(duì)通過(guò)能力系統(tǒng)的相對(duì)通過(guò)

7、能力單位時(shí)間內(nèi)損失的顧客數(shù)及平均進(jìn)入系統(tǒng)的顧客數(shù)單位時(shí)間內(nèi)損失的顧客數(shù)及平均進(jìn)入系統(tǒng)的顧客數(shù)0!nmmnppn011!nmmnQppn 00!(1)(1)!nmLmnmemnppnnQppn20平均服務(wù)隊(duì)長(zhǎng)平均服務(wù)隊(duì)長(zhǎng)平均等待隊(duì)長(zhǎng)平均等待隊(duì)長(zhǎng)平均系統(tǒng)隊(duì)長(zhǎng)平均系統(tǒng)隊(duì)長(zhǎng)eLW服服服110201 (1)()1!(1)()(1)12 !nnm nm nqnnpmnmnnLnmn mnpn sqLLl服21l 顧客源有限顧客源有限m顧客源顧客源m=系統(tǒng)最大顧客數(shù)系統(tǒng)最大顧客數(shù)m，任何的需求都可以得到任何的需求都可以得到滿(mǎn)足，滿(mǎn)足，P損損=0閉合式排隊(duì)系統(tǒng)：排隊(duì)系統(tǒng)內(nèi)顧客與顧客源中顧客總數(shù)閉合式排隊(duì)系統(tǒng)：

8、排隊(duì)系統(tǒng)內(nèi)顧客與顧客源中顧客總數(shù)是固定的是固定的 (m-c)mnc個(gè)顧客個(gè)顧客m-c個(gè)顧客源個(gè)顧客源220,1,2,. ()010kkEmmkkmkknnnkm0n-121nm(m-1)(m-2)(m-n+1)23(n-1)n(m-n)n+1nn個(gè)服務(wù)窗全忙服務(wù)窗還有空閑nmn23l求平穩(wěn)分布求平穩(wěn)分布0110112101010100110110.(1).(1)011 2 3.!(1).(1)!1!kkkkkkmkkkmk nk nmkkknkkkmmk nkk nppm mmkpCpknkC km mmkppknn nn npC kpCn n （）24l目標(biāo)參量目標(biāo)參量0(),() ()mq

9、kk nmskksqsseqqesseLkn pLkpLLLALAE mlmLLWLW服服25l例題（例題（120頁(yè)）內(nèi)線(xiàn)占用外線(xiàn)，內(nèi)線(xiàn)上產(chǎn)生頁(yè)）內(nèi)線(xiàn)占用外線(xiàn)，內(nèi)線(xiàn)上產(chǎn)生電話(huà)呼叫，如果外線(xiàn)有空閑的則占有外線(xiàn)，電話(huà)呼叫，如果外線(xiàn)有空閑的則占有外線(xiàn)，如果沒(méi)有空閑的外線(xiàn)則排隊(duì)等待如果沒(méi)有空閑的外線(xiàn)則排隊(duì)等待l有有m條內(nèi)線(xiàn)和條內(nèi)線(xiàn)和n條外線(xiàn)，采用條外線(xiàn)，采用BCD（Blocked Call Delayed）排隊(duì)規(guī)則）排隊(duì)規(guī)則內(nèi)線(xiàn)平均空閑時(shí)間內(nèi)線(xiàn)平均空閑時(shí)間： 內(nèi)線(xiàn)平均空閑概率內(nèi)線(xiàn)平均空閑概率1tssmLtpmtW內(nèi)線(xiàn)內(nèi)線(xiàn)m條（顧客源）條（顧客源）外線(xiàn)外線(xiàn)n條（服務(wù)窗）條（服務(wù)窗）26內(nèi)線(xiàn)被占用的概率內(nèi)

10、線(xiàn)被占用的概率內(nèi)線(xiàn)占用、不占用的循環(huán)周期內(nèi)線(xiàn)占用、不占用的循環(huán)周期內(nèi)線(xiàn)處于等待狀態(tài)概率內(nèi)線(xiàn)處于等待狀態(tài)概率1sLpmcyclesWtW ( )qLr mm閑閑忙忙tsWcycleW27外線(xiàn)利用率外線(xiàn)利用率 外線(xiàn)損失系數(shù)，（空閑、浪費(fèi)系數(shù)）外線(xiàn)損失系數(shù)，（空閑、浪費(fèi)系數(shù)）服Ln( )11 服Lq nn28l輸出是與輸入同強(qiáng)度的泊松流輸出是與輸入同強(qiáng)度的泊松流l設(shè)排隊(duì)系統(tǒng)為設(shè)排隊(duì)系統(tǒng)為M/M/n/m(1 n m )，設(shè)到，設(shè)到達(dá)的顧客流是參數(shù)為達(dá)的顧客流是參數(shù)為 的泊松流（在等待制的泊松流（在等待制時(shí)，進(jìn)入系統(tǒng)的流是參數(shù)為時(shí)，進(jìn)入系統(tǒng)的流是參數(shù)為 的泊松流；在的泊松流；在混合制與損失制時(shí)，進(jìn)入系統(tǒng)

11、的流是參數(shù)混合制與損失制時(shí)，進(jìn)入系統(tǒng)的流是參數(shù)為為 (1-pm)的泊松流），如果把混合制與損的泊松流），如果把混合制與損失制時(shí)的損失流也看作系統(tǒng)的輸出，失制時(shí)的損失流也看作系統(tǒng)的輸出，則系則系統(tǒng)的輸出是參數(shù)為統(tǒng)的輸出是參數(shù)為 的泊松流。的泊松流。l證明略證明略29l 設(shè)統(tǒng)計(jì)平衡條件下，顧客到達(dá)時(shí)看到的隊(duì)長(zhǎng)為設(shè)統(tǒng)計(jì)平衡條件下，顧客到達(dá)時(shí)看到的隊(duì)長(zhǎng)為ls-（不包括到達(dá)的這個(gè)顧客），（不包括到達(dá)的這個(gè)顧客）， ls-與平穩(wěn)隊(duì)長(zhǎng)與平穩(wěn)隊(duì)長(zhǎng)ls的的分布分布相同嗎？相同嗎？l 平穩(wěn)分布記做：平穩(wěn)分布記做：排隊(duì)系統(tǒng)排隊(duì)系統(tǒng)()()nsnspP lnpP ln30l 舉例舉例D/D/1排隊(duì)系統(tǒng)排隊(duì)系統(tǒng)假定顧客

12、到達(dá)間隔時(shí)間=服務(wù)時(shí)間=并且到達(dá)的間隔時(shí)間大于服務(wù)時(shí)間到達(dá)的顧客不需要等待，所以有：系統(tǒng)中最多有一個(gè)顧客，看到D/D/1排隊(duì)系統(tǒng)中：1101,0 (1,2,3.)nppn011,0 (2,3.)npppn nnpp31l下面我們研究三種時(shí)刻隊(duì)長(zhǎng)分布的關(guān)系下面我們研究三種時(shí)刻隊(duì)長(zhǎng)分布的關(guān)系lpn-=P(顧客到達(dá)時(shí)系統(tǒng)中已有顧客到達(dá)時(shí)系統(tǒng)中已有n個(gè)顧客個(gè)顧客)lPn=P(N=n)=平穩(wěn)分布隊(duì)長(zhǎng)為平穩(wěn)分布隊(duì)長(zhǎng)為n的概率的概率lpn+=P(顧客離開(kāi)系統(tǒng)時(shí)系統(tǒng)還有顧客離開(kāi)系統(tǒng)時(shí)系統(tǒng)還有n個(gè)顧客的個(gè)顧客的概率概率)32lG/G/1系統(tǒng)系統(tǒng)pn- =pn+N(t)tn+1n跟蹤跟蹤N(t)實(shí)際走過(guò)的一條路線(xiàn)

13、實(shí)際走過(guò)的一條路線(xiàn)33l 假定從狀態(tài)假定從狀態(tài)n上跳到狀態(tài)上跳到狀態(tài)n+1的次數(shù)為的次數(shù)為An(t)從狀態(tài)從狀態(tài)n+1下跳到狀態(tài)下跳到狀態(tài)n的次數(shù)為的次數(shù)為Dn(t)l 由于到達(dá)與離去是一個(gè)一個(gè)發(fā)生的，并且由于到達(dá)與離去是一個(gè)一個(gè)發(fā)生的，并且n-n+1與與n+1-n是交錯(cuò)發(fā)生的。所以到是交錯(cuò)發(fā)生的。所以到t時(shí)刻為止，時(shí)刻為止，An(t)與與Dn(t)至多相至多相差差1l 設(shè)設(shè)A(t)、D(t)為從任何狀態(tài)開(kāi)始上跳一步的總次數(shù)和下跳為從任何狀態(tài)開(kāi)始上跳一步的總次數(shù)和下跳一步的總次數(shù)，在統(tǒng)計(jì)平衡條件下，有：一步的總次數(shù)，在統(tǒng)計(jì)平衡條件下，有： ( )( )( )lim1( )tA tD tD tA

14、 t34( )( )( )( )( )( )lim( )( )( )( )( )( )lim( )( )( )( )( )( )( )( )limlim1( )( )( )( )0nnnnnntnnnntnnnttnnA tD tppA tD tD tA tD tA tD tA tA tA tD tD tD tA tD tA tA tA tD tD tA tD tpp35l M/G系統(tǒng)有系統(tǒng)有pn-(t)= pn(t)，即任意時(shí)刻，到達(dá)的顧客看到的隊(duì)長(zhǎng)分布等，即任意時(shí)刻，到達(dá)的顧客看到的隊(duì)長(zhǎng)分布等于系統(tǒng)隊(duì)長(zhǎng)的分布于系統(tǒng)隊(duì)長(zhǎng)的分布l 證明證明令令A(yù)(t, t+t)表示在表示在t, t+t)時(shí)間內(nèi)

15、到達(dá)了一個(gè)顧客，則時(shí)間內(nèi)到達(dá)了一個(gè)顧客，則 因?yàn)檩斎肓魇遣此闪?，所以因?yàn)檩斎肓魇遣此闪?，所以A(t, t+t)發(fā)生的概率是發(fā)生的概率是 t+o(t)，與，與N(t)=n這個(gè)事件無(wú)關(guān)。所以這個(gè)事件無(wú)關(guān)。所以00( )( )|( ,)( ),( ,)lim ( ,)( ) ( ,)|( )lim ( ,)nttptP N tnA t ttP N tn A t ttP A t ttP N tnP A t ttN tnP A t tt 0 ( ,)|( ) ( ,)( )lim( )( )nnntP A t ttN tnP A t ttp tp tp t 】36lG/G排隊(duì)系統(tǒng)排隊(duì)系統(tǒng)pn- =pn+

16、 即到達(dá)的顧客與離開(kāi)的顧客所看到的隊(duì)長(zhǎng)即到達(dá)的顧客與離開(kāi)的顧客所看到的隊(duì)長(zhǎng)分布是相等的分布是相等的lM/G排隊(duì)系統(tǒng)中排隊(duì)系統(tǒng)中pn- =pn+ =pn即在顧客為泊松流到達(dá)的排隊(duì)系統(tǒng)中，到即在顧客為泊松流到達(dá)的排隊(duì)系統(tǒng)中，到達(dá)的顧客與離開(kāi)的顧客看到的隊(duì)長(zhǎng)分布與達(dá)的顧客與離開(kāi)的顧客看到的隊(duì)長(zhǎng)分布與系統(tǒng)的隊(duì)長(zhǎng)分布都相等系統(tǒng)的隊(duì)長(zhǎng)分布都相等 37l 某電話(huà)交換機(jī)有某電話(huà)交換機(jī)有20條線(xiàn)，假定每次用線(xiàn)時(shí)間（通條線(xiàn)，假定每次用線(xiàn)時(shí)間（通話(huà)）平均話(huà)）平均3分鐘，不知其分布，通話(huà)需求是泊松分鐘，不知其分布，通話(huà)需求是泊松流，平均每分鐘有流，平均每分鐘有5個(gè)。打不通電話(huà)時(shí)則不等待個(gè)。打不通電話(huà)時(shí)則不等待（BCC

17、Blocked Call Cleared），求損失概），求損失概率、平均損失顧客數(shù)。率、平均損失顧客數(shù)。B（15，20）0.33B（20，15）0.04638l在一個(gè)停車(chē)場(chǎng)中只有在一個(gè)停車(chē)場(chǎng)中只有10個(gè)停車(chē)位，汽車(chē)按個(gè)停車(chē)位，汽車(chē)按平均數(shù)為每小時(shí)平均數(shù)為每小時(shí)10部的泊松分布到達(dá)，停部的泊松分布到達(dá)，停車(chē)時(shí)間服從平均數(shù)為車(chē)時(shí)間服從平均數(shù)為10分鐘的指數(shù)分布。分鐘的指數(shù)分布。試求試求到達(dá)的汽車(chē)發(fā)現(xiàn)沒(méi)有停車(chē)位的概率到達(dá)的汽車(chē)發(fā)現(xiàn)沒(méi)有停車(chē)位的概率系統(tǒng)的有效到達(dá)率系統(tǒng)的有效到達(dá)率空停車(chē)位的期望值空停車(chē)位的期望值39l一理發(fā)店有發(fā)型師一理發(fā)店有發(fā)型師5人，供顧客等候的座位人，供顧客等候的座位有有10個(gè)，

18、若顧客以泊松流到達(dá)，每小時(shí)個(gè)，若顧客以泊松流到達(dá)，每小時(shí)8人，人，每一發(fā)型師平均要每一發(fā)型師平均要30分鐘做一個(gè)發(fā)型，理分鐘做一個(gè)發(fā)型，理發(fā)時(shí)間服從負(fù)指數(shù)分布。一顧客到達(dá)看到發(fā)時(shí)間服從負(fù)指數(shù)分布。一顧客到達(dá)看到無(wú)空座位要站著等候則馬上離開(kāi)。無(wú)空座位要站著等候則馬上離開(kāi)。求損失概率求損失概率平均損失的顧客數(shù)平均損失的顧客數(shù)平均忙的發(fā)型師數(shù)量平均忙的發(fā)型師數(shù)量40l 設(shè)有設(shè)有3個(gè)修理工負(fù)責(zé)個(gè)修理工負(fù)責(zé)7臺(tái)機(jī)器，假定停臺(tái)欲檢修的臺(tái)機(jī)器，假定停臺(tái)欲檢修的臺(tái)數(shù)為泊松流，修理時(shí)間為指數(shù)分布。每臺(tái)機(jī)器臺(tái)數(shù)為泊松流，修理時(shí)間為指數(shù)分布。每臺(tái)機(jī)器平均損壞率為每運(yùn)轉(zhuǎn)一小時(shí)發(fā)生一次；平均損壞率為每運(yùn)轉(zhuǎn)一小時(shí)發(fā)生一次；3個(gè)修理個(gè)修理工以工以4臺(tái)臺(tái)/小時(shí)相同的平均修復(fù)率修好機(jī)器。試求：小時(shí)相同的平均修復(fù)率修好機(jī)器。試求：1）計(jì)算停臺(tái)數(shù)為）計(jì)算停臺(tái)數(shù)為0、1、4的概率的概率2）修理工的平均勞動(dòng)率）修理工的平均勞動(dòng)率3）平均等候檢驗(yàn)的停臺(tái)機(jī)器數(shù)）平均等候檢驗(yàn)的停臺(tái)機(jī)器數(shù)4