非馬爾可夫排隊(duì)模型

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

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

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

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

5、位數(shù)加到達(dá)一個顧客，則相位數(shù)加k因此系統(tǒng)增加因此系統(tǒng)增加k個相位和減少一個相位所需時間個相位和減少一個相位所需時間都是負(fù)指數(shù)分布的，系統(tǒng)相位數(shù)的變化是馬爾可都是負(fù)指數(shù)分布的，系統(tǒng)相位數(shù)的變化是馬爾可夫鏈夫鏈8l相位法分析相位法分析在足夠短時間在足夠短時間 t內(nèi)，能夠發(fā)生的事件只有兩種內(nèi)，能夠發(fā)生的事件只有兩種l到達(dá)一個顧客，相位數(shù)加到達(dá)一個顧客，相位數(shù)加k，概率為，概率為t+o( t)l如果有顧客在接受服務(wù)，服務(wù)完一個相位，概率為如果有顧客在接受服務(wù)，服務(wù)完一個相位，概率為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排隊(duì)模型排隊(duì)模型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ù)的對應(yīng)關(guān)系相位數(shù)與顧客數(shù)的對應(yīng)關(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)中有同樣多顧客對應(yīng)有對應(yīng)有3種不同的相位數(shù)種不同的相位數(shù)jpnp(1)1001,2,.j nknjjnkppnpp11l求平穩(wěn)分布求平穩(wěn)分布當(dāng)當(dāng) 時，

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項(xiàng)的系數(shù)就是項(xiàng)的系數(shù)就是pj如何將母函數(shù)轉(zhuǎn)換為直觀的平穩(wěn)分布的表達(dá)式？如何將母函數(shù)轉(zhuǎn)換為直觀的平穩(wěn)分布的表達(dá)式？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è)為個不同的實(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目標(biāo)參量目標(biāo)參量設(shè)一顧客到達(dá)時，系統(tǒng)中已有設(shè)一顧客到達(dá)時，系統(tǒng)中已有j個相位，且一個個相位，且一個相位平均需要服務(wù)時間為相位平均

9、需要服務(wù)時間為 。于是，。于是，j個相位平個相位平均需服務(wù)時間為均需服務(wù)時間為 ，故新到達(dá)系統(tǒng)的顧客平均，故新到達(dá)系統(tǒng)的顧客平均等候服務(wù)的時間為等候服務(wù)的時間為1 1k kj jk k0011(1)(1)(1)2(1)(1)2(1)qjjjjjWpjpPkkkkkkk15可見，k時，Ws，Wq， Ls，Lq，當(dāng)k1時，為M/M/1排隊(duì)系統(tǒng)當(dāng)k時，為M/D/1排隊(duì)系統(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某半成品檢驗(yàn)站設(shè)一名檢驗(yàn)員進(jìn)行質(zhì)量檢查。假某半成品檢驗(yàn)站設(shè)一名檢驗(yàn)員進(jìn)行質(zhì)量檢查。假定半成品以每小時定半成品以每小時75件的平均速率按泊松分布到件的平均速率按泊松分布到達(dá)，檢驗(yàn)員檢驗(yàn)每件半成品的時間平均為達(dá)，檢驗(yàn)員檢驗(yàn)每件半成品的時間平均為0.75分分鐘，且服從鐘，且服從k=25階愛爾蘭分布，試回答：階愛爾蘭分布，試回答：在檢驗(yàn)站前等候檢驗(yàn)的半成品的平均件數(shù)在檢驗(yàn)站前等候檢驗(yàn)的半成品的平均件數(shù)分別采用以下措施時，等候檢驗(yàn)的半成品數(shù)各降低分別采用以下措施時，等候檢驗(yàn)的半成品數(shù)各降低到多少？到多少？l降低生產(chǎn)速率，使半成品到達(dá)的時間間隔服從平均值降低生產(chǎn)速率，使半成品到達(dá)的時間間

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

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

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

14、相位即將到達(dá)的顧客已經(jīng)通過了即將到達(dá)的顧客已經(jīng)通過了0k-1個相位個相位l下一個到達(dá)的顧客通過一個相位下一個到達(dá)的顧客通過一個相位相位總數(shù)加相位總數(shù)加1l正在服務(wù)的顧客服務(wù)完畢正在服務(wù)的顧客服務(wù)完畢相位數(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的排隊(duì)模型的排隊(duì)模型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ù)的對應(yīng)關(guān)系相位數(shù)與顧客數(shù)的對應(yīng)關(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)分布當(dāng)當(dāng) 時，平穩(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目標(biāo)參量目標(biāo)參量平均系統(tǒng)隊(duì)長平均系統(tǒng)隊(duì)長系統(tǒng)隊(duì)長方差系統(tǒng)隊(duì)長方差平均等候隊(duì)長平均等候隊(duì)長000000(1)1kknksnknnsLnpsnss2200200(1)1( ).(1)k

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

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

19、的話，就可以產(chǎn)生更復(fù)雜的分布?？梢援a(chǎn)生更復(fù)雜的分布。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ù)下一個到達(dá)的顧客所在的相位下一個到達(dá)的顧客所在的相位正在接受服務(wù)的顧客所在的相位正在接受服務(wù)的顧客所在的相位l然后我們可以畫出狀態(tài)流圖（往往非常復(fù)雜的

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

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

22、的顧客離開時，留在排隊(duì)系統(tǒng)中的顧客數(shù)的顧客離開時，留在排隊(duì)系統(tǒng)中的顧客數(shù)36l單服務(wù)窗等待制排隊(duì)模型單服務(wù)窗等待制排隊(duì)模型l顧客到達(dá)間隔時間顧客到達(dá)間隔時間負(fù)指數(shù)分布負(fù)指數(shù)分布l顧客服務(wù)時間顧客服務(wù)時間任意分布任意分布tn-1tntn+1tn+2Xn：第n個顧客剛離開系統(tǒng)的瞬間，系統(tǒng)內(nèi)留有的顧客數(shù)XnXn1Tn：第n1個顧客的服務(wù)時間Yn：第n1個顧客的服務(wù)期間到達(dá)的顧客數(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有 個顧客在第顧客服務(wù)期間到達(dá)的概率狀態(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