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

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

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

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

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

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

6、*316l 顧客到達(dá)間隔時間顧客到達(dá)間隔時間負(fù)指數(shù)分布，參數(shù)為負(fù)指數(shù)分布，參數(shù)為 l 顧客接受服務(wù)的時間顧客接受服務(wù)的時間負(fù)指數(shù)分布，參數(shù)為負(fù)指數(shù)分布，參數(shù)為 mnm-n17l 0,1,2,. 010kkEmkmkknnnkm0n-121n23(n-1)nn+1nn個服務(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)的相對通過能力系統(tǒng)的相對通過

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

8、排隊系統(tǒng)內(nèi)顧客與顧客源中顧客總數(shù)是固定的是固定的 (m-c)mnc個顧客個顧客m-c個顧客源個顧客源220,1,2,. ()010kkEmmkkmkknnnkm0n-121nm(m-1)(m-2)(m-n+1)23(n-1)n(m-n)n+1nn個服務(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頁）內(nèi)線占用外線，內(nèi)線上產(chǎn)生頁）內(nèi)線占用外線，內(nèi)線上產(chǎn)生電話呼叫，如果外線有空閑的則占有外線，電話呼叫，如果外線有空閑的則占有外線，如果沒有空閑的外線則排隊等待如果沒有空閑的外線則排隊等待l有有m條內(nèi)線和條內(nèi)線和n條外線，采用條外線，采用BCD（Blocked Call Delayed）排隊規(guī)則）排隊規(guī)則內(nèi)線平均空閑時間內(nèi)線平均空閑時間： 內(nèi)線平均空閑概率內(nèi)線平均空閑概率1tssmLtpmtW內(nèi)線內(nèi)線m條（顧客源）條（顧客源）外線外線n條（服務(wù)窗）條（服務(wù)窗）26內(nèi)線被占用的概率內(nèi)

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

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

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

13、實際走過的一條路線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á)與離去是一個一個發(fā)生的，并且由于到達(dá)與離去是一個一個發(fā)生的，并且n-n+1與與n+1-n是交錯發(fā)生的。所以到是交錯發(fā)生的。所以到t時刻為止，時刻為止，An(t)與與Dn(t)至多相至多相差差1l 設(shè)設(shè)A(t)、D(t)為從任何狀態(tài)開始上跳一步的總次數(shù)和下跳為從任何狀態(tài)開始上跳一步的總次數(shù)和下跳一步的總次數(shù)，在統(tǒng)計平衡條件下，有：一步的總次數(shù)，在統(tǒng)計平衡條件下，有： ( )( )( )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)，即任意時刻，到達(dá)的顧客看到的隊長分布等，即任意時刻，到達(dá)的顧客看到的隊長分布等于系統(tǒng)隊長的分布于系統(tǒng)隊長的分布l 證明證明令令A(yù)(t, t+t)表示在表示在t, t+t)時間內(nèi)

15、到達(dá)了一個顧客，則時間內(nèi)到達(dá)了一個顧客，則 因為輸入流是泊松流，所以因為輸入流是泊松流，所以A(t, t+t)發(fā)生的概率是發(fā)生的概率是 t+o(t)，與，與N(t)=n這個事件無關(guān)。所以這個事件無關(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排隊系統(tǒng)排隊系統(tǒng)pn- =pn+

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

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

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