非馬爾可夫排隊模型

1、12l排隊系統(tǒng)中的顧客數(shù)變化不具有馬爾可夫性排隊系統(tǒng)中的顧客數(shù)變化不具有馬爾可夫性l顧客服務時間分布、服務時間分布其中之一或兩顧客服務時間分布、服務時間分布其中之一或兩者都不是負指數(shù)分布的（時間分布不具有無記憶者都不是負指數(shù)分布的（時間分布不具有無記憶性），則此排隊模型為非馬爾可夫排隊模型性），則此排隊模型為非馬爾可夫排隊模型l例如例如一條流水線，每一條流水線，每2分鐘到達一個半成品，加工一個半分鐘到達一個半成品，加工一個半成品的時間服從負指數(shù)分布，成品的時間服從負指數(shù)分布，D/M/1電話網(wǎng)中，電話網(wǎng)中，20的用戶需要撥號上網(wǎng)，上網(wǎng)時間為的用戶需要撥號上網(wǎng)，上網(wǎng)時間為平均平均30分鐘的負指數(shù)分

2、布，如何設(shè)計交換機？分鐘的負指數(shù)分布，如何設(shè)計交換機？M/H2/m/m3l顧客到達間隔時間顧客到達間隔時間負指數(shù)分布負指數(shù)分布l顧客服務時間顧客服務時間k階愛爾蘭分布階愛爾蘭分布l單個服務窗單個服務窗l(fā)等待制排隊模型等待制排隊模型不具有無記憶性不具有無記憶性采用采用相位法相位法解決解決422服務時間為：一個負指數(shù)分布服務時間為：一個負指數(shù)分布服務時間為：兩個獨立負指數(shù)分布時間的和服務時間為：兩個獨立負指數(shù)分布時間的和2( )11tf teETDT22( )2 (2)11212tf tt eETDTDTET5l類似的我們可以表示類似的我們可以表示k階愛爾蘭分布的服務時間階愛爾蘭分布的服務時間kk

3、kk122()( )(1)!11()()kk tkk tf tektD tktkD t服服服服概率密度：顧客服務時間是顧客服務時間是k階愛爾蘭分布，相當于階愛爾蘭分布，相當于k個同參數(shù)的負指數(shù)分布的個同參數(shù)的負指數(shù)分布的時間階段之和，稱每一個負指數(shù)分布的時間階段為一個時間階段之和，稱每一個負指數(shù)分布的時間階段為一個相位相位。返回6l因此，如果一個顧客正在接受服務，他可能處于因此，如果一個顧客正在接受服務，他可能處于k個相位中的任意一個相位。個相位中的任意一個相位。l一個相位的服務時間服從負指數(shù)分布。一個相位的服務時間服從負指數(shù)分布。l服務完一個相位，就接著進入下一個相位進行服服務完一個相位，就

4、接著進入下一個相位進行服務。務。l一個顧客服務完全部相位才離開服務窗，這時候一個顧客服務完全部相位才離開服務窗，這時候下一個顧客進入服務窗開始服務。下一個顧客進入服務窗開始服務。l雖然顧客數(shù)的減少不具有無記憶性，但是相位數(shù)雖然顧客數(shù)的減少不具有無記憶性，但是相位數(shù)的減少具有無記憶性的減少具有無記憶性kkkk單個相位：服務率k平均服務時間1/k7l相位法：相位法：把系統(tǒng)中當前所有顧客全部被服務完畢離開系統(tǒng)把系統(tǒng)中當前所有顧客全部被服務完畢離開系統(tǒng)應通過的相位數(shù)作為系統(tǒng)狀態(tài)。應通過的相位數(shù)作為系統(tǒng)狀態(tài)。正在服務的顧客通過一個相位，則相位數(shù)減正在服務的顧客通過一個相位，則相位數(shù)減1到達一個顧客，則相

5、位數(shù)加到達一個顧客，則相位數(shù)加k因此系統(tǒng)增加因此系統(tǒng)增加k個相位和減少一個相位所需時間個相位和減少一個相位所需時間都是負指數(shù)分布的，系統(tǒng)相位數(shù)的變化是馬爾可都是負指數(shù)分布的，系統(tǒng)相位數(shù)的變化是馬爾可夫鏈夫鏈8l相位法分析相位法分析在足夠短時間在足夠短時間 t內(nèi)，能夠發(fā)生的事件只有兩種內(nèi)，能夠發(fā)生的事件只有兩種l到達一個顧客，相位數(shù)加到達一個顧客，相位數(shù)加k，概率為，概率為t+o( t)l如果有顧客在接受服務，服務完一個相位，概率為如果有顧客在接受服務，服務完一個相位，概率為kt+o( t)因此得到因此得到Q矩陣：矩陣：,1,001()0 其他i ii i kiii jqkiqQqkqq9l畫出

6、狀態(tài)流圖（現(xiàn)在的狀態(tài)是系統(tǒng)內(nèi)相位數(shù)）畫出狀態(tài)流圖（現(xiàn)在的狀態(tài)是系統(tǒng)內(nèi)相位數(shù)）l例如一個例如一個M/E3/1排隊模型排隊模型012jkk+1j-kj+1012345678 k 3 k k k k k k k k k k 3 3 3 3 3 3 3 3 10l相位數(shù)與顧客數(shù)的對應關(guān)系相位數(shù)與顧客數(shù)的對應關(guān)系假定相位數(shù)的平穩(wěn)分布為假定相位數(shù)的平穩(wěn)分布為 ,而系統(tǒng)顧客數(shù)的平而系統(tǒng)顧客數(shù)的平穩(wěn)分布為穩(wěn)分布為則則例如，例如，M/E3/1系統(tǒng)中有同樣多顧客系統(tǒng)中有同樣多顧客對應有對應有3種不同的相位數(shù)種不同的相位數(shù)jpnp(1)1001,2,.j nknjjnkppnpp11l求平穩(wěn)分布求平穩(wěn)分布當當 時，

7、平穩(wěn)分布存在，時，平穩(wěn)分布存在，若若j0, pj=0l列出平衡方程列出平衡方程l利用母函數(shù)把線性方程組化為一個線性方利用母函數(shù)把線性方程組化為一個線性方程，并求解程，并求解1011()1jj kjpkpkppkpj12l相位平穩(wěn)分布的母函數(shù)：相位平穩(wěn)分布的母函數(shù)：將母函數(shù)展開成將母函數(shù)展開成s的冪級數(shù)，則的冪級數(shù)，則sj項的系數(shù)就是項的系數(shù)就是pj如何將母函數(shù)轉(zhuǎn)換為直觀的平穩(wěn)分布的表達式？如何將母函數(shù)轉(zhuǎn)換為直觀的平穩(wěn)分布的表達式？l將母函數(shù)拆分成部分分式，形如將母函數(shù)拆分成部分分式，形如 的和的和l將各個分式轉(zhuǎn)換為將各個分式轉(zhuǎn)換為s的冪級數(shù)的冪級數(shù)l將各個部分分式的冪級數(shù)相加將各個部分分式的冪

8、級數(shù)相加1(1)(1)( )()kksP sksks1AsB13l可以確定可以確定 分母中，分母中，s=1是它是它的一個根，另外還有的一個根，另外還有k個不同的實根，假設(shè)為個不同的實根，假設(shè)為s1,s2,skl將母函數(shù)拆分成部分分式：將母函數(shù)拆分成部分分式：l最終得到相位的平穩(wěn)分布：最終得到相位的平穩(wěn)分布：1(1)(1)( )()kksP sksks111( )(1)1/1/1kkllljlljj llAP sAs sssAkl =1且1(1)kjjlllpAs14l目標參量目標參量設(shè)一顧客到達時，系統(tǒng)中已有設(shè)一顧客到達時，系統(tǒng)中已有j個相位，且一個個相位，且一個相位平均需要服務時間為相位平均

9、需要服務時間為 。于是，。于是，j個相位平個相位平均需服務時間為均需服務時間為 ，故新到達系統(tǒng)的顧客平均，故新到達系統(tǒng)的顧客平均等候服務的時間為等候服務的時間為1 1k kj jk k0011(1)(1)(1)2(1)(1)2(1)qjjjjjWpjpPkkkkkkk15可見，k時，Ws，Wq， Ls，Lq，當k1時，為M/M/1排隊系統(tǒng)當k時，為M/D/1排隊系統(tǒng)22211(1)(1)2(1)(1)(1)12 (1)2 (1)(1)2 (1)sqssqqkWWkkkLWkkkLWk16lM/M/1lM/D/121(1)(1)11qsqsWWLL2222 (1)2 (1)22(1)2(1)qs

10、qsWWLL17l某半成品檢驗站設(shè)一名檢驗員進行質(zhì)量檢查。假某半成品檢驗站設(shè)一名檢驗員進行質(zhì)量檢查。假定半成品以每小時定半成品以每小時75件的平均速率按泊松分布到件的平均速率按泊松分布到達，檢驗員檢驗每件半成品的時間平均為達，檢驗員檢驗每件半成品的時間平均為0.75分分鐘，且服從鐘，且服從k=25階愛爾蘭分布，試回答：階愛爾蘭分布，試回答：在檢驗站前等候檢驗的半成品的平均件數(shù)在檢驗站前等候檢驗的半成品的平均件數(shù)分別采用以下措施時，等候檢驗的半成品數(shù)各降低分別采用以下措施時，等候檢驗的半成品數(shù)各降低到多少？到多少？l降低生產(chǎn)速率，使半成品到達的時間間隔服從平均值降低生產(chǎn)速率，使半成品到達的時間間

11、隔服從平均值為為1.2的負指數(shù)分布的負指數(shù)分布l更換一名更熟練的檢驗員，使對每件半成品的檢驗時更換一名更熟練的檢驗員，使對每件半成品的檢驗時間縮短為服從均值間縮短為服從均值0.72分鐘、分鐘、k2的愛爾蘭分布；的愛爾蘭分布；l配備兩名檢驗員，每名檢驗員檢驗一件半成品時間為配備兩名檢驗員，每名檢驗員檢驗一件半成品時間為0.75分鐘，且服從負指數(shù)分布。分鐘，且服從負指數(shù)分布。18l設(shè)某電話間只有一部公用電話，顧客按泊設(shè)某電話間只有一部公用電話，顧客按泊松流到達，平均每小時到達松流到達，平均每小時到達6人，每次通話人，每次通話時間平均為時間平均為8分鐘，方差為分鐘，方差為16平方分鐘，通平方分鐘，通

12、話時間服從愛爾蘭分布。試求：話時間服從愛爾蘭分布。試求：平均等候排隊長度平均等候排隊長度顧客平均等候時間顧客平均等候時間怎么確定愛爾蘭分布的階數(shù)19l分析分析單個服務窗的等待制排隊模型單個服務窗的等待制排隊模型顧客到達間隔時間顧客到達間隔時間愛爾蘭分布愛爾蘭分布服務時間服務時間負指數(shù)分布負指數(shù)分布平均到達間隔時間平均到達間隔時間平均服務時間平均服務時間l到達與服務相獨立，假定到達與服務相獨立，假定1 11 111()( )(1)!kk tkk ta tek( )tb te20l將愛爾蘭分布的顧客到達時間看作是將愛爾蘭分布的顧客到達時間看作是k個相互獨立個相互獨立的負指數(shù)分布的時間段之和的負指數(shù)

13、分布的時間段之和l每個負指數(shù)分布的時間段視作一個每個負指數(shù)分布的時間段視作一個“相位相位”l這樣，下一個顧客通過一個相位所需的時間是負指這樣，下一個顧客通過一個相位所需的時間是負指數(shù)分布的，是具有無記憶性的數(shù)分布的，是具有無記憶性的k k k k 通過每個相位的平均時間：1/k 通過全部k個相位的平均時間：1/ 21l將某時刻所有顧客已經(jīng)通過的相位數(shù)之和看作系將某時刻所有顧客已經(jīng)通過的相位數(shù)之和看作系統(tǒng)狀態(tài)（所有顧客包括的是排隊系統(tǒng)內(nèi)的全部顧統(tǒng)狀態(tài)（所有顧客包括的是排隊系統(tǒng)內(nèi)的全部顧客和客和下一個即將到達的顧客下一個即將到達的顧客）則，系統(tǒng)中的顧客已經(jīng)通過了則，系統(tǒng)中的顧客已經(jīng)通過了k個相位個

14、相位即將到達的顧客已經(jīng)通過了即將到達的顧客已經(jīng)通過了0k-1個相位個相位l下一個到達的顧客通過一個相位下一個到達的顧客通過一個相位相位總數(shù)加相位總數(shù)加1l正在服務的顧客服務完畢正在服務的顧客服務完畢相位數(shù)減相位數(shù)減kl相位數(shù)的變化是一個馬爾可夫鏈相位數(shù)的變化是一個馬爾可夫鏈22l畫出狀態(tài)流圖（現(xiàn)在的狀態(tài)是系統(tǒng)內(nèi)相位數(shù)）畫出狀態(tài)流圖（現(xiàn)在的狀態(tài)是系統(tǒng)內(nèi)相位數(shù)）l例如一個例如一個E3/M/1的排隊模型的排隊模型012jkk+1j-kj+1k k k k k k k k k k 012345678 k k k k k k k k k 23l相位數(shù)與顧客數(shù)的對應關(guān)系相位數(shù)與顧客數(shù)的對應關(guān)系假定相位數(shù)的

15、平穩(wěn)分布為假定相位數(shù)的平穩(wěn)分布為 ,而系統(tǒng)顧客數(shù)的平而系統(tǒng)顧客數(shù)的平穩(wěn)分布為穩(wěn)分布為 則則例如系統(tǒng)中有例如系統(tǒng)中有3個顧客時的相位數(shù)就有可能是：個顧客時的相位數(shù)就有可能是：jpnp(1)10,1,2,.jnknjj nkppn已經(jīng)通過的相位數(shù)為3已經(jīng)通過的相位數(shù)為124l求平穩(wěn)分布求平穩(wěn)分布當當 時，平穩(wěn)分布存在時，平穩(wěn)分布存在l列出平衡方程列出平衡方程l利用母函數(shù)把線性方程組化為一個線性方利用母函數(shù)把線性方程組化為一個線性方程，并求解程，并求解10110()kjjj kjjj kkppkpkppjkkpkppjk25l相位平穩(wěn)分布的母函數(shù)：相位平穩(wěn)分布的母函數(shù)：l經(jīng)過整理得：經(jīng)過整理得：其中

16、其中s0是方程是方程 的一個在的一個在單位圓外的根單位圓外的根101(1)( )(1)1kkjjjkksp sP sk sks00(1)(1)( )(1)() kssP sk sss1(1)10 kkk sks26l相位的平穩(wěn)分布相位的平穩(wěn)分布l系統(tǒng)內(nèi)顧客數(shù)的平穩(wěn)分布系統(tǒng)內(nèi)顧客數(shù)的平穩(wěn)分布:10011100011(1)0(1)111()jjj kjjjkkspsjkk sss 0010(1)0nknknpssn27l目標參量目標參量平均系統(tǒng)隊長平均系統(tǒng)隊長系統(tǒng)隊長方差系統(tǒng)隊長方差平均等候隊長平均等候隊長000000(1)1kknksnknnsLnpsnss2200200(1)1( ).(1)k

17、kssnknssD ln pLs01qsskLLLLs服28l目標參量目標參量000(1)1(1)ksskqqkLsWsLWs29l在一個E3/M/1排隊模型中，已知服務窗的利用率為0.8，服務窗服務一個顧客所需的平均時間為10分鐘。試求顧客的平均等候隊長Lq，平均等候時間Wq以及np30l是否相位法只能使用在是否相位法只能使用在M/Ek/1和和Ek/M/1兩種排隊模型兩種排隊模型中呢？中呢？l回顧愛爾蘭分布：回顧愛爾蘭分布：l如果采用服務率不同的相位串連，則得到的變量其變?nèi)绻捎梅章什煌南辔淮B，則得到的變量其變異系數(shù)也異系數(shù)也1的分布，則用超指數(shù)分布（并的分布，則用超指數(shù)分布（并聯(lián)的相

18、位）聯(lián)的相位）l例如一個例如一個2個并聯(lián)相位的服務窗：個并聯(lián)相位的服務窗：12 1 2121122*121212( )( )ttb teeBxxx 1232lM/H2/1的狀態(tài)流圖的狀態(tài)流圖l使用使用ki表示系統(tǒng)中有表示系統(tǒng)中有k個顧客，而正在服務的顧客個顧客，而正在服務的顧客所在的是所在的是i (i=1,2)號相位號相位011122122 1 22 2 1 1 1 2 2 1 2133l為了繼續(xù)拓寬相位法的適用范圍，我們可以看看把相位串并組為了繼續(xù)拓寬相位法的適用范圍，我們可以看看把相位串并組合后的結(jié)果。如果每個串連相位的服務率也可以不同的話，就合后的結(jié)果。如果每個串連相位的服務率也可以不同

19、的話，就可以產(chǎn)生更復雜的分布?？梢援a(chǎn)生更復雜的分布。r11ri2 1 i11rR21 Rr11ri222rR22r11ri2r1rR2rirR*1( )()iRriiiiiirB xxr34l已經(jīng)證明，任何一種分布，都可以把這種分布拆分成串已經(jīng)證明，任何一種分布，都可以把這種分布拆分成串聯(lián)聯(lián)-并聯(lián)的相位組合。并聯(lián)的相位組合。l使用這種發(fā)法。首先，描述系統(tǒng)狀態(tài)必須包括使用這種發(fā)法。首先，描述系統(tǒng)狀態(tài)必須包括3個量：個量：系統(tǒng)中的顧客數(shù)系統(tǒng)中的顧客數(shù)下一個到達的顧客所在的相位下一個到達的顧客所在的相位正在接受服務的顧客所在的相位正在接受服務的顧客所在的相位l然后我們可以畫出狀態(tài)流圖（往往非常復雜的

20、圖）然后我們可以畫出狀態(tài)流圖（往往非常復雜的圖）l然后通過研究分析，寫出平穩(wěn)方程（往往非常羅嗦的公然后通過研究分析，寫出平穩(wěn)方程（往往非常羅嗦的公式）式）l最后，使用計算機求解我們需要的結(jié)果最后，使用計算機求解我們需要的結(jié)果l這種方法的求解排隊模型，結(jié)果雖然不是像前面學習過這種方法的求解排隊模型，結(jié)果雖然不是像前面學習過的一樣可以預先得出，但這的確是一種理論上可行的方的一樣可以預先得出，但這的確是一種理論上可行的方法。法。35l嵌入式馬氏鏈的來源嵌入式馬氏鏈的來源在任何時候，如果總結(jié)馬氏鏈的在任何時候，如果總結(jié)馬氏鏈的”歷史歷史”,必須必須使用二維的狀態(tài)使用二維的狀態(tài)N(t),X0(t)，其中

21、，其中N(t)是是t時刻系時刻系統(tǒng)中的顧客數(shù)，統(tǒng)中的顧客數(shù)， X0(t)是是t時刻正在服務的顧客已時刻正在服務的顧客已經(jīng)服務了的時間。經(jīng)服務了的時間。l我們希望還是采用一維變量我們希望還是采用一維變量N(t)來描述系統(tǒng)狀態(tài)，并來描述系統(tǒng)狀態(tài)，并且希望去掉且希望去掉X0(t)這個連續(xù)變量。因此，我們不要關(guān)注這個連續(xù)變量。因此，我們不要關(guān)注時間軸上的每一個點，而是選擇一系列我們需要的點。時間軸上的每一個點，而是選擇一系列我們需要的點。我們選擇的就是我們選擇的就是“顧客離開時刻顧客離開時刻”這一系列時間這一系列時間點，在這些點上點，在這些點上X0(t)=0。而。而N(t)則是在剛服務完則是在剛服務完

22、的顧客離開時，留在排隊系統(tǒng)中的顧客數(shù)的顧客離開時，留在排隊系統(tǒng)中的顧客數(shù)36l單服務窗等待制排隊模型單服務窗等待制排隊模型l顧客到達間隔時間顧客到達間隔時間負指數(shù)分布負指數(shù)分布l顧客服務時間顧客服務時間任意分布任意分布tn-1tntn+1tn+2Xn：第n個顧客剛離開系統(tǒng)的瞬間，系統(tǒng)內(nèi)留有的顧客數(shù)XnXn1Tn：第n1個顧客的服務時間Yn：第n1個顧客的服務期間到達的顧客數(shù) Yn0空Xn0Xn=037l系統(tǒng)狀態(tài)系統(tǒng)狀態(tài)Xn可以看到可以看到Xn的變化與的變化與Xn-1，Xn-2，沒有關(guān)系，因此沒有關(guān)系，因此Xn的變化具有無記憶性，是一個嵌入式馬爾可夫鏈，而且的變化具有無記憶性，是一個嵌入式馬爾可夫鏈，而且發(fā)現(xiàn)此嵌入式馬氏鏈的分布就是系統(tǒng)內(nèi)顧客數(shù)的分布。發(fā)現(xiàn)此嵌入式馬氏鏈的分布就是系統(tǒng)內(nèi)顧客數(shù)的分布。l下面開始分析嵌入式馬氏鏈的轉(zhuǎn)移矩陣下面開始分析嵌入式馬氏鏈的轉(zhuǎn)移矩陣假定假定11010nnnnnnYXXXYX1()jn+1(|)jnijnnijjaP YjpP Xj Xipa有 個顧客在第顧客服務期間到達的概率狀態(tài)轉(zhuǎn)移的概率與 有密切的關(guān)系38l一步轉(zhuǎn)移概率：一步轉(zhuǎn)移概率：l一步轉(zhuǎn)移矩陣：一步轉(zhuǎn)移矩陣：0111(|0)()(|)(1|)(1|)011jnnnjijnnnnnnj ipP Xj XP YjapP Xj XiP iYj XiP YjiXiijaij 012012