排隊論大學課件10-非馬爾科夫排隊模型

1、第五章 非馬爾可夫排隊模型1非馬爾可夫排隊模型排隊系統(tǒng)中的顧客數(shù)變化不具有馬爾可夫性顧客到達間隔時間分布、服務時間分布其中之一或兩者都不是負指數(shù)分布的（時間分布不具有無記憶性），則此排隊模型為非馬爾可夫排隊模型例如一條流水線，每2分鐘到達一個半成品，加工一個半成品的時間服從負指數(shù)分布，D/M/1電話網(wǎng)中，20的用戶需要撥號上網(wǎng)，上網(wǎng)時間為平均30分鐘的負指數(shù)分布，如何設計交換機？M/H2/m/m2第一節(jié) M/Ek/1排隊模型顧客到達間隔時間負指數(shù)分布顧客服務時間k階愛爾蘭分布單個服務窗等待制排隊模型不具有無記憶性采用相位法解決3愛爾蘭分布與負指數(shù)分布的密切關系22服務時間為：一個負指數(shù)分布服務

2、時間為：兩個獨立負指數(shù)分布時間的和4類似的我們可以表示k階愛爾蘭分布的服務時間kkkk顧客服務時間是k階愛爾蘭分布，相當于k個同參數(shù)的負指數(shù)分布的時間階段之和，稱每一個負指數(shù)分布的時間階段為一個相位。返回5因此，如果一個顧客正在接受服務，他可能處于k個相位中的任意一個相位。一個相位的服務時間服從負指數(shù)分布。服務完一個相位，就接著進入下一個相位進行服務。一個顧客服務完全部相位才離開服務窗，這時候下一個顧客進入服務窗開始服務。雖然顧客數(shù)的減少不具有無記憶性，但是相位數(shù)的減少具有無記憶性kkkk單個相位：服務率k平均服務時間1/k6M/Ek/1排隊模型相位法：把系統(tǒng)中當前所有顧客全部被服務完畢離開系

3、統(tǒng)應通過的相位數(shù)作為系統(tǒng)狀態(tài)。正在服務的顧客通過一個相位，則相位數(shù)減1到達一個顧客，則相位數(shù)加k因此系統(tǒng)增加k個相位和減少一個相位所需時間都是負指數(shù)分布的，系統(tǒng)相位數(shù)的變化是馬爾可夫鏈7M/Ek/1排隊模型相位法分析在足夠短時間t內(nèi)，能夠發(fā)生的事件只有兩種到達一個顧客，相位數(shù)加k，概率為t+o(t)如果有顧客在接受服務，服務完一個相位，概率為kt+o(t)因此得到Q矩陣：8M/Ek/1排隊模型畫出狀態(tài)流圖（現(xiàn)在的狀態(tài)是系統(tǒng)內(nèi)相位數(shù)）例如一個M/E3/1排隊模型012jkk+1j-kj+1012345678k3kkkkkkkkkk333333339M/Ek/1排隊模型相位數(shù)與顧客數(shù)的對應關系假定

4、相位數(shù)的平穩(wěn)分布為 ,而系統(tǒng)顧客數(shù)的平穩(wěn)分布為則例如，M/E3/1系統(tǒng)中有同樣多顧客對應有3種不同的相位數(shù)10M/Ek/1排隊模型求平穩(wěn)分布當 時，平穩(wěn)分布存在，若j0, pj=0列出平衡方程利用母函數(shù)把線性方程組化為一個線性方程，并求解11M/Ek/1排隊模型相位平穩(wěn)分布的母函數(shù)：將母函數(shù)展開成s的冪級數(shù)，則sj項的系數(shù)就是pj如何將母函數(shù)轉(zhuǎn)換為直觀的平穩(wěn)分布的表達式？將母函數(shù)拆分成部分分式，形如 的和將各個分式轉(zhuǎn)換為s的冪級數(shù)將各個部分分式的冪級數(shù)相加12M/Ek/1排隊模型可以確定 分母中，s=1是它的一個根，另外還有k個不同的實根，假設為s1,s2,sk將母函數(shù)拆分成部分分式：最終得到

5、相位的平穩(wěn)分布：13M/Ek/1排隊模型目標參量設一顧客到達時，系統(tǒng)中已有j個相位，且一個相位平均需要服務時間為 。于是，j個相位平均需服務時間為 ，故新到達系統(tǒng)的顧客平均等候服務的時間為14M/Ek/1排隊模型可見，k時，Ws，Wq， Ls，Lq，當k1時，為M/M/1排隊系統(tǒng)當k時，為M/D/1排隊系統(tǒng)15M/M/1、M/D/1排隊模型對比M/M/1M/D/116M/Ek/1例題1某半成品檢驗站設一名檢驗員進行質(zhì)量檢查。假定半成品以每小時75件的平均速率按泊松分布到達，檢驗員檢驗每件半成品的時間平均為0.75分鐘，且服從k=25階愛爾蘭分布，試回答：在檢驗站前等候檢驗的半成品的平均件數(shù)分別

6、采用以下措施時，等候檢驗的半成品數(shù)各降低到多少？降低生產(chǎn)速率，使半成品到達的時間間隔服從平均值為1.2的負指數(shù)分布更換一名更熟練的檢驗員，使對每件半成品的檢驗時間縮短為服從均值0.72分鐘、k2的愛爾蘭分布；配備兩名檢驗員，每名檢驗員檢驗一件半成品時間為0.75分鐘，且服從負指數(shù)分布。17M/Ek/1例題2設某電話間只有一部公用電話，顧客按泊松流到達，平均每小時到達6人，每次通話時間平均為8分鐘，方差為16平方分鐘，通話時間服從愛爾蘭分布。試求：平均等候排隊長度顧客平均等候時間怎么確定愛爾蘭分布的階數(shù)18第二節(jié) Ek/ M/ 1排隊模型分析單個服務窗的等待制排隊模型顧客到達間隔時間愛爾蘭分布服

7、務時間負指數(shù)分布平均到達間隔時間平均服務時間到達與服務相獨立，假定19Ek/ M/ 1排隊模型將愛爾蘭分布的顧客到達時間看作是k個相互獨立的負指數(shù)分布的時間段之和每個負指數(shù)分布的時間段視作一個“相位”這樣，下一個顧客通過一個相位所需的時間是負指數(shù)分布的，是具有無記憶性的kkkk通過每個相位的平均時間：1/k通過全部k個相位的平均時間：1/20Ek/ M/ 1排隊模型將某時刻所有顧客已經(jīng)通過的相位數(shù)之和看作系統(tǒng)狀態(tài)（所有顧客包括的是排隊系統(tǒng)內(nèi)的全部顧客和下一個即將到達的顧客）則，系統(tǒng)中的顧客已經(jīng)通過了k個相位即將到達的顧客已經(jīng)通過了0k-1個相位下一個到達的顧客通過一個相位相位總數(shù)加1正在服務的

8、顧客服務完畢相位數(shù)減k相位數(shù)的變化是一個馬爾可夫鏈21Ek/ M/ 1排隊模型畫出狀態(tài)流圖（現(xiàn)在的狀態(tài)是系統(tǒng)內(nèi)相位數(shù)）例如一個E3/M/1的排隊模型012jkk+1j-kj+1kkkkkkkkkk012345678kkkkkkkkk22Ek/ M/ 1排隊模型相位數(shù)與顧客數(shù)的對應關系假定相位數(shù)的平穩(wěn)分布為 ,而系統(tǒng)顧客數(shù)的平穩(wěn)分布為 則例如系統(tǒng)中有3個顧客時的相位數(shù)就有可能是：已經(jīng)通過的相位數(shù)為3已經(jīng)通過的相位數(shù)為123Ek/ M/ 1排隊模型求平穩(wěn)分布當 時，平穩(wěn)分布存在列出平衡方程利用母函數(shù)把線性方程組化為一個線性方程，并求解24Ek/ M/ 1排隊模型相位平穩(wěn)分布的母函數(shù)：經(jīng)過整理得：其

9、中s0是方程 的一個在單位圓外的根25Ek/ M/ 1排隊模型相位的平穩(wěn)分布系統(tǒng)內(nèi)顧客數(shù)的平穩(wěn)分布:26Ek/ M/ 1排隊模型目標參量平均系統(tǒng)隊長系統(tǒng)隊長方差平均等候隊長27Ek/ M/ 1排隊模型目標參量28Ek/ M/ 1排隊模型例題在一個E3/M/1排隊模型中，已知服務窗的利用率為0.8，服務窗服務一個顧客所需的平均時間為10分鐘。試求顧客的平均等候隊長Lq，平均等候時間Wq以及29相位法綜述1是否相位法只能使用在M/Ek/1和Ek/M/1兩種排隊模型中呢？回顧愛爾蘭分布：如果采用服務率不同的相位串連，則得到的變量其變異系數(shù)也1的分布，則用超指數(shù)分布（并聯(lián)的相位）例如一個2個并聯(lián)相位的

10、服務窗：12121231相位法綜述2M/H2/1的狀態(tài)流圖使用ki表示系統(tǒng)中有k個顧客，而正在服務的顧客所在的是i (i=1,2)號相位01112212212221112212132相位法綜述3為了繼續(xù)拓寬相位法的適用范圍，我們可以看看把相位串并組合后的結(jié)果。如果每個串連相位的服務率也可以不同的話，就可以產(chǎn)生更復雜的分布。r11ri21i11rR21Rr11ri222rR22r11ri2r1rR2rirR33相位法綜述4已經(jīng)證明，任何一種分布，都可以把這種分布拆分成串聯(lián)-并聯(lián)的相位組合。使用這種發(fā)法。首先，描述系統(tǒng)狀態(tài)必須包括3個量：系統(tǒng)中的顧客數(shù)下一個到達的顧客所在的相位正在接受服務的顧客所

11、在的相位然后我們可以畫出狀態(tài)流圖（往往非常復雜的圖）然后通過研究分析，寫出平穩(wěn)方程（往往非常羅嗦的公式）最后，使用計算機求解我們需要的結(jié)果這種方法的求解排隊模型，結(jié)果雖然不是像前面學習過的一樣可以預先得出，但這的確是一種理論上可行的方法。34補：M/M排隊系統(tǒng)的輸出過程輸出是與輸入同強度的泊松流設排隊系統(tǒng)為M/M/n/m(1nm )，設到達的顧客流是參數(shù)為的泊松流（在等待制時，進入系統(tǒng)的流是參數(shù)為的泊松流；在混合制與損失制時，進入系統(tǒng)的流是參數(shù)為(1-pm)的泊松流），如果把混合制與損失制時的損失流也看作系統(tǒng)的輸出，則系統(tǒng)的輸出是參數(shù)為的泊松流。證明略35隊長分布與顧客到達時刻看到的隊長分布的

12、關系設統(tǒng)計平衡條件下，顧客到達時看到的隊長為ls-（不包括到達的這個顧客）， ls-與平穩(wěn)隊長ls的分布相同嗎？平穩(wěn)分布記做：排隊系統(tǒng)36隊長分布與顧客到達時刻看到的隊長分布的關系舉例D/D/1排隊系統(tǒng)假定顧客到達間隔時間=服務時間=并且到達的間隔時間大于服務時間到達的顧客不需要等待，所以有：到達的顧客看到的隊長分布系統(tǒng)中最多有一個顧客，所以有：系統(tǒng)隊長分布：看到D/D/1排隊系統(tǒng)中：37到達與離開時的隊長分布的關系下面我們研究三種時刻隊長分布的關系pn-=P(顧客到達時系統(tǒng)中已有n個顧客)pn=P(N=n)=平穩(wěn)分布=系統(tǒng)隊長為n的概率pn+=P(顧客離開系統(tǒng)時系統(tǒng)還留下n個顧客的概率)38

13、到達與離開時的隊長分布的關系能達到平穩(wěn)的G/G系統(tǒng)pn- =pn+ ,顧客在極短時間內(nèi)只能到達一個，或離開一個N(t)tn+1n跟蹤N(t)實際走過的一條路線39到達與離開時的隊長分布的關系假定從狀態(tài)n上跳到狀態(tài)n+1的次數(shù)為An(t)從狀態(tài)n+1下跳到狀態(tài)n的次數(shù)為Dn(t)由于到達與離去是一個一個發(fā)生的，并且n-n+1與n+1-n是交錯發(fā)生的。所以到t時刻為止，An(t)與Dn(t)至多相差1設A(t)、D(t)為從任何狀態(tài)開始上跳一步的總次數(shù)和下跳一步的總次數(shù)，在統(tǒng)計平衡條件下，有：40到達與離開時的隊長分布的關系41M/G系統(tǒng)顧客到達時刻看到的的隊長分布與隊長分布的關系M/G系統(tǒng)有pn

14、-(t)= pn(t)，即任意時刻，到達的顧客看到的隊長分布等于系統(tǒng)隊長的分布證明令A(t, t+t)表示在t, t+t)時間內(nèi)到達了一個顧客，則 因為輸入流是泊松流，所以A(t, t+t)發(fā)生的概率是 t+o(t)，與N(t)=n這個事件無關。所以42結(jié)論G/G排隊系統(tǒng)pn- =pn+ 即到達的顧客與離開的顧客所看到的隊長分布是相等的M/G排隊系統(tǒng)中pn- =pn+ =pn即在顧客為泊松流到達的排隊系統(tǒng)中，到達的顧客與離開的顧客看到的隊長分布與系統(tǒng)的隊長分布都相等 43第三節(jié) M/G/1排隊模型嵌入式馬氏鏈的來源在任何時候，如果總結(jié)排隊系統(tǒng)狀態(tài)的”歷史”,必須使用二維的狀態(tài)X(t),X0(t

15、)，其中X(t)是t時刻系統(tǒng)中的顧客數(shù)， X0(t)是t時刻正在服務的顧客已經(jīng)服務了的時間。我們希望還是采用一維變量X(t)來描述系統(tǒng)狀態(tài)，并且希望去掉X0(t)這個連續(xù)變量。因此，我們不要關注時間軸上的每一個點，而是選擇一系列我們需要的點。我們選擇的就是“顧客離開時刻”這一系列時間點t，在這些點上X0(t)=0。而X(t)則是在剛服務完的顧客離開時，留在排隊系統(tǒng)中的顧客數(shù)44M/G/1排隊模型對于時間點的選擇，使我們關注的目標變成了一系列間隔不定的離散的點。關注的問題這一系列時間點上，顧客數(shù)變化是不是馬爾可夫鏈？這一系列時間點的平穩(wěn)分布是不是整個系統(tǒng)的顧客數(shù)的平穩(wěn)分布？tn-1tntn+1t

16、n+2XnXn1空Xn0Xn=045M/G/1排隊模型單服務窗等待制排隊模型顧客到達間隔時間負指數(shù)分布顧客服務時間一般分布Xn：第n個顧客剛離開系統(tǒng)的瞬間，系統(tǒng)內(nèi)留有的顧客數(shù)Tn：第n1個顧客的服務時間Yn：第n1個顧客的服務期間到達的顧客數(shù) Yn0tn-1tntn+1tn+2XnXn1空Xn0Xn=046M/G/1排隊模型系統(tǒng)狀態(tài)Xn可以看到Xn的變化與Xn-1，Xn-2，沒有關系，因此Xn的變化具有無記憶性，是一個嵌入式馬爾可夫鏈，而且發(fā)現(xiàn)此嵌入式馬氏鏈的分布就是系統(tǒng)內(nèi)顧客數(shù)的分布。下面開始分析嵌入式馬氏鏈的轉(zhuǎn)移矩陣假定47M/G/1排隊模型一步轉(zhuǎn)移概率：一步轉(zhuǎn)移矩陣：48M/G/1排隊模型i+1i+2ii-1ji-2a0a1a2a3aj-i+1a2a3a0120ja0a0a1aja049M/G/1排隊模型Tn為第n1個顧客的服務時間，Tn是獨立同分布的隨機變量序列，記其公共分布函數(shù)為G(t)=P(Tnt)求aj，即一個服務時間期間到達j個顧客的概率書P170 5.3-650M/G/1排隊模型平衡方程（離散馬爾可夫鏈的公式）接下來可以根據(jù)求平穩(wěn)分