（概率論與數(shù)理統(tǒng)計專業(yè)論文）離散時間smkphkc（c12）fcfs排隊系統(tǒng)的年齡過程.pdf

摘要 本文是研究這樣一個離散時間的排隊系統(tǒng)；顧客有著多種類型，成批到達(dá)，到 達(dá)過程是個半馬爾可夫過程，按照先來先服務(wù)的服務(wù)準(zhǔn)則，并且每一個顧客的服 務(wù)時間服從各自的尸日分布 文章開始部分是引言，對當(dāng)前有著多種類型顧客的離散時間的排隊模型的研 究做了介紹和分析第一章是對這篇文章的一些知識點和計算工具的介紹第二 章是對s m k i p h k i 1 f c f s 排隊系統(tǒng)的描述，以及對其年齡過程做了詳細(xì)分 析，并引進(jìn)一些附加變量構(gòu)造個關(guān)于年齡過程的馬爾可夫鏈，從而計算出年齡過 程的轉(zhuǎn)移矩陣第三章是本文的重點，首先還是對s m k p h k 2 f c f s 排隊 系統(tǒng)的描述，接著分析了年齡過程為了降低計算的復(fù)雜，我們巧妙地選取了系統(tǒng) 中某一個顧客批的年齡作為系統(tǒng)的年齡，并引進(jìn)一些附加變量構(gòu)造一個關(guān)于年齡過 程的馬爾可夫鏈，最后對這個馬爾可夫鏈的轉(zhuǎn)移矩陣進(jìn)行了詳細(xì)計算第四章是對 s m k p h k 2 f c f s 排隊系統(tǒng)的年齡過程的甲穩(wěn)分布的分析，在計算出甲穩(wěn) 分布的假定下。對排隊系統(tǒng)的另外一些信息做了初步推導(dǎo) 關(guān)鍵詞：排隊系統(tǒng)，半馬爾可夫過程，j 口h 分布，馬爾可夫鏈，年齡過程 i i 摘 要 a b s t r a c t i n t h i st h e s i s ，w es t u d yad i s c r e t et i m eq u e u e i n gs y s t e mw i t hm u l t i p l et y p e s o fc u s t o m e r sa n daf i r s t - c o m e - f i r s t - s e r v e d ( f c f s ) s e r v i c ed i s c i p l i n e c u s t o m e r sa r - r i v ea c c o r d i n gt oas e m i - m a r k o va r r i v a lp r o c e s sa n dt h es e r v i c et i m e so fi n d i v i d u a l c u s t o m e r sh a v ep 日d i s t r i b u t i o n s i nt h i st h e s i sa tf i r s ti st h ei n t r o d u c t i o n ，w h i c hi n t r o d u c e sa n da n a l y s e st h es t u d y n o w a d a y so fd i s c r e t et i m eq u e u i n gm o d e l sw i t hm u l t i p l et y p e so fc u s t o m e r s t h e f i r s tc h a p t e rg i v c * a ni n t r o d u c t i o na b o u tt h ek n o w l e d g eo ft h i st h e s i sa n dc m c u l p t i o n a lm e t h o d s t h es e c o n dc h a p t e rd e s c r i b e ss m k p h k 1 f c f s q u e u ea n d a n a l y s e si t sg e n e r a l i z e da g ep r o c e s sp a r t i c u l a r l y w ei n t r o d u c es o m ea u x i l i a r yv a r i - a b l e st oc o n s t r u c tam a r k o vc h a i na s s o c i a t e dw i t ha 9 ( ) a n do b t a i nt h et r a n s i t i o n p r o b a b i l i t ym a t r i xo ft h i sm a r k o vc h a i n t h ep i v o to ft h i st h e s i si st h et h i r dc h a p t e r w h i c ha tf i r s td e s c r i b e ss m k p h k 2 f c f sq u e u ea n dt h e na n a l y s e si t sg e n - e r a l i z e da g ep r o c e s s ，w ec h o o s et i l ea g eo fs o n i cb a t c hi nq u e u e i n gs y s t e ma st h ea g e o ft h i ss y s t e ms k i l l f l l l l yt or e d u c et h ec a l c u l a t i o n a lc o m p l e x i t y w ei n t r o d u c es o m e a t t x i l i a r yv a r i a b l e st oc o n s t r u c tam a r k o vc h a i na s s o c i a t e dw i t ha 9 ( ) a n df i n dt h e t r a n s i t i o np r o b a b i l i t ym a t r i xo ft h i sm a r k o vc h a i ni nd e t a i l t h ef o u r t hc h a p t e ra n a l y s e st h es t e a d ys t a t ed i s t r i b u t i o no ft h ea g ep r o c e s so fs m k j p h k 2 f c f s q u e u e g i v e nt h es t e a d ys t a t ed i s t r i b u t i o n ，w eh a v ep i l o ts t u d yo fo t h e ri n f o r n m t i o n i naq u e u e i n gs y s t e m k e yw o r d s ：q u e u e i n gs y s t e m s ，s e m i - m a r k o vp r o c e s s ，尸日一d i s t r i b u t i o n ，m a r k o v c h a i n ，a g ep r o c e s s 首都師范大學(xué)學(xué)位論文原創(chuàng)性聲明 本人鄭重聲明：所呈交的學(xué)位論文，是本人在導(dǎo)師的指導(dǎo)1 - ，獨立進(jìn)行研究工 作所取得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本論文不含任何其他個人或集體 已經(jīng)發(fā)表或撰寫過的作品成果對本文的研究做出重要貢獻(xiàn)的個人和集體，均已在 文中以明確方式標(biāo)明本人完全意識到本聲明的法律結(jié)果由本人承擔(dān)。 學(xué)位論文作者簽名 ?；锰\ 日期：問年朗j a 日 首都師范大學(xué)學(xué)位論文授權(quán)使用聲明 本人完全了解苒都師范大學(xué)有關(guān)保留，使用學(xué)位論文的規(guī)定，學(xué)校有權(quán)保留學(xué) 位論文并向國家主管部門或其指定機(jī)構(gòu)送交淪文的電子版和紙質(zhì)版。有權(quán)將學(xué)位論 文用于非贏利目的的少量復(fù)制并允許淪文進(jìn)入學(xué)校圖書館被查閱。有權(quán)將學(xué)位論文 的內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索。有權(quán)將學(xué)位論文的標(biāo)題和摘要匯編出版。保密的 學(xué)位論文在解密后適用本規(guī)定。 學(xué)位論文作者簽名： 南蘚 日期：j 司年恥月2 淵 引言 現(xiàn)代通訊網(wǎng)絡(luò)需要處理各類數(shù)據(jù)，這些數(shù)據(jù)在容量等方面是各不相同的現(xiàn)代 供應(yīng)鏈的設(shè)計也是要滿足顧客的不同需要這相當(dāng)于在排隊系統(tǒng)中顧客是有類型 的又在現(xiàn)實生活中我們還經(jīng)常遇到成批到達(dá)的現(xiàn)象，例如在生產(chǎn)制造系統(tǒng)中需要 加工的部件成批到達(dá)加工車問。再如在庫存系統(tǒng)中，顧客的需求按照復(fù)合泊松過程 到達(dá)系統(tǒng)以上這些現(xiàn)象都可以描述成成批到達(dá)的排隊系統(tǒng)。而多服務(wù)臺問題由于 其應(yīng)用的廣泛而也備受關(guān)注，很多排隊論的著作中都有多服務(wù)臺的內(nèi)容，尤其是在 呼叫中心的設(shè)計方面多服務(wù)臺排隊模型更是必不可少的，但現(xiàn)在呼叫中心的設(shè)計多 采用單個到達(dá)的多服務(wù)臺模型，而隨著呼叫中心應(yīng)用的越來越廣泛，單個到達(dá)在實 際應(yīng)用中漸顯不足，因此引入了批量到達(dá)模式，使得模型更加貼近實際情況由于 這些隨機(jī)系統(tǒng)的設(shè)計和功能分析的需要，在這篇論文中，我們將研究一類有著多種 類型顧客的離散時問的排隊模型，其顧客是批到達(dá)，且有兩個服務(wù)臺 因為各種實際應(yīng)用以及可用于連續(xù)時間排隊系統(tǒng)逼近問題的研究，所以對于離 散時間排隊模型的研究很廣在那些經(jīng)典的論文中，很多對離散時間排隊的研究都 集中在單一類型或者多類型的顧客，并且有著不同的服務(wù)先后順序的情況顧客的 到達(dá)過程通常假定為獨立的泊松過程在劉【1 3 中，主要討論了離散時間狀態(tài)下的 批量到達(dá)排隊系統(tǒng)，推廣了經(jīng)典的離散時問排隊模型，考慮單個服務(wù)臺的情形，假 設(shè)顧客批的到達(dá)服從幾何分布每批到達(dá)的顧客數(shù)服從一般的離散分布，顧客的服 務(wù)時間也服從幾何分布，使用嵌入馬爾可夫鏈的方法，分析得到了該隨機(jī)排隊系統(tǒng) 的隊長、等待隊長等待時間以及忙期等關(guān)鍵指標(biāo)的母函數(shù)這些結(jié)論與經(jīng)典排隊 系統(tǒng)中相對應(yīng)的結(jié)論在形式上十分相似，并且將經(jīng)典排隊系統(tǒng)作為其特例，從而推 廣了隨機(jī)排隊系統(tǒng)的研究框架 對于有標(biāo)記轉(zhuǎn)移( 即顧客有各種類型) 的馬爾可夫到達(dá)過程( m m a p k 1 ) 的研究，在h e 2 1 中，詳細(xì)介紹了從不同類型的顧客觀點出發(fā)的排隊系統(tǒng)，并給出 了到達(dá)時刻不同類型顧客的隊長和等待時間在【2 】中引出了m m a p g 1 排隊系 2 引言 統(tǒng)，并得到了一個能給出在m m a p c 1 排隊系統(tǒng)的忙期服務(wù)的顧客數(shù)的期望值 的新的公式【2 】還將這一結(jié)果在m m a p ( k ) g k 1 排隊系統(tǒng)中進(jìn)行了概括在 h e 3 】，h e 4 】中也都給出了有標(biāo)記轉(zhuǎn)移的馬爾可夫到達(dá)過程的介紹在 4 】中， 與【2 不同的是，【4 】在m m a p k 】模型的問題上給出了更詳細(xì)的討論并且f 2 】 討論的是每一個顧客批只有一個顧客的情形，而【4 】是通常的顧客批 4 】考慮了每 個顧客批中顧客的服務(wù)順序，這是其他論文中很少討論到的問題另外， 【4 】中用 了很正式的方式給出了 2 】中的一些證明【4 給出了一些關(guān)于忙期和虛等待時問 的l a p l a c e s t i e l t j e s 變換的結(jié)論，并研究了每一類顧客的實等待時間 有了這些介紹，那么對于有多種類型的顧客的復(fù)雜排隊也就變得可以解決了 比如在h e 5 】和h e 6 中都給出了很好的結(jié)果在這篇論文中，我們用的是有標(biāo)記 轉(zhuǎn)移的半馬爾可夫到達(dá)過程，這比m m a p k 1 顯然要更普遍我們假定在不同類 型的顧客間是沒有服務(wù)優(yōu)先權(quán)的，這樣的排隊模型仍然是可以解決的 對于多種類型的顧客沒有服務(wù)優(yōu)先權(quán)的排隊系統(tǒng)來說，我們叮以根據(jù)顧客個體 的服務(wù)順序進(jìn)行分類在h e 5 1 和h e 6 1 中排隊系統(tǒng)就足按照后來先服務(wù)的服務(wù) 順序進(jìn)行研究的在【5 中，研究了一個這佯的排隊系統(tǒng)：有標(biāo)記轉(zhuǎn)移的馬爾可夫 到達(dá)過程，對每一類型顧客的服務(wù)時問都服從各自的p h 分布根據(jù)每一侖顧客的 類型，采取后來先服務(wù)的優(yōu)先服務(wù)準(zhǔn)則重點研究了系統(tǒng)忙期時隊長的穩(wěn)態(tài)分布， 給出了汁算隊長穩(wěn)態(tài)分布，忙期服務(wù)的顧客甲均數(shù)、忙期的乎均長度效率高的汁算 方法在h e 2 和h e 4 1 中每個類型的顧客的等待時間就是按照先來先服務(wù)順序 進(jìn)行研究的但是，對于先來先服務(wù)的排隊模型來說，隊長卻屜很難分析的，因為 得記住隊內(nèi)顧客的類型在t a k i n e 7 】中，通過利用等待時問的信息而得到隊長 然而通常對于一些有趣的排隊系統(tǒng)，不像在一些經(jīng)典的排隊系統(tǒng)中分析等待時間那 樣，在等待時間的分析中對于隊長足沒有信息可利用的幸運的是，構(gòu)造一個與正 在服務(wù)中的顧客批的年齡有關(guān)的馬爾可夫鏈，從而能夠分析等待時間，逗留時間， 這篇論文中正是運用了這種方法 等待時間和逗留時問在排隊模型中是很重要的，并且關(guān)于對它們的研究也是很 引言 3 深的s e n g u p t a 在【8 】、 9 】和【1 0 】中證明了在連續(xù)時間g i i p h l l 排隊的等待時 間和逗留時間有矩陣指數(shù)分布a s m u s s e n 和0 c i n n e i d e 在【1 1 】中將s e n g u p t a 的結(jié)論擴(kuò)展到了連續(xù)時間a x l p h i c 排隊中現(xiàn)在，又有一些人研究離散時間有 著多種類型顧客的排隊系統(tǒng)的等待時間和逗留時間在v a n h o u d t 和b l o n d i a 1 2 l 中，構(gòu)造了一個類似在這篇論文中用到的用年齡過程得到的馬爾可夫鏈，從年齡過 程的穩(wěn)態(tài)分布得到逗留時間的分布當(dāng)然在【1 2 】中的到達(dá)過程是馬爾可夫過程， 這是與這篇論文最大的不同之處因此，這篇論文我們考慮的是一個離散時間的更 普遍的排隊模型我們構(gòu)造一個廣義的年齡過程，這個過程是沒有水甲0 這個邊 界的在一個服務(wù)臺的情形下我們可以從這個年齡過程的平穩(wěn)分布得到等待時間和 逗留時間的分布而【1 2 】提供了一個研究兩個服務(wù)臺的很好的方法，就是研究系 統(tǒng)中在服務(wù)的顧客批中年齡較小的顧客批的年齡這篇論文就是依據(jù)這個思路對 s m k p h i 引2 f c f s 進(jìn)行研究的 在h e 1 1 中，研究的是一個離散時間的排隊系統(tǒng)，有著多種類型的顧客并且按照 先來先服務(wù)的服務(wù)準(zhǔn)則顧客到達(dá)是一個半馬爾可夫過程，并且每一個顧客的服務(wù)時 間服從p h 分布引進(jìn)一個由顧客批的年齡過程構(gòu)造的g 1 m 1 型的馬爾可夫鏈這 個g i m 1 型的馬爾可夫鏈的穩(wěn)態(tài)分布可以精確計算出來，從而正在服務(wù)的顧客批 的年齡。系統(tǒng)總的工作量，等待時間，不同批不同類型的顧客的逗留時間等這些變量 的穩(wěn)態(tài)分布也可以得到并且【1 證明出廣義的年齡過程和廣義的總的工作量過程有 相同的穩(wěn)態(tài)分布，等待時間和逗留時間的分布為p h 分布并得到這些p h 分布的矩 陣表示【1 】還將到達(dá)過程深入到更特殊的情況：有標(biāo)記轉(zhuǎn)移的馬爾可夫到達(dá)過程，從 而構(gòu)造一個年齡過程和總的工作量過程的q b d 過程( 擬生滅過程) ，由這個q b d 過程的穩(wěn)態(tài)分布得到了顧客批和顧客個體的等待時間和逗留時間的穩(wěn)態(tài)分布 1 】 對s m k i p h k i 1 f c f s 和m m a p i k i p h k 1 f c f s 這兩類型的排隊系 統(tǒng)做出了很詳細(xì)的分析，也得到了一些很好的結(jié)果并且對s m k p h k c ( c 2 ) f c f s 這類型的排隊系統(tǒng)也作了簡要分析，認(rèn)為對于個服務(wù)臺的排隊系統(tǒng)的 使用方法能夠推廣到多個服務(wù)臺的排隊系統(tǒng)中，這也為多個服務(wù)臺的排隊系統(tǒng)提供 4 引言 了工具和證明了可行性 這篇論文的基本思想就是采用 1 】的方法，對于s m k p h k 1 f c f s 型 的排隊系統(tǒng)，我們構(gòu)造的與顧客批的年齡過程相關(guān)的馬爾可夫鏈與 1 】稍有不同，不 同在于附加變量的定義但最后結(jié)果一樣，從而對于年齡過程的穩(wěn)態(tài)分布以及后面 其他變量的穩(wěn)態(tài)分布的分析都是不受影響的對于s m k p h i k 2 f c f s 型的 排隊系統(tǒng)，我們參照 1 】1 的方法，將一個服務(wù)臺的情況擴(kuò)展到兩個服務(wù)臺的情況 在這個過程中難點在于由顧客批的年齡過程怎么去構(gòu)造一個馬爾可夫鏈，尤其當(dāng)年 齡是負(fù)數(shù)的時候這篇論文得到了由年齡過程構(gòu)造的馬爾可夫鏈的轉(zhuǎn)移矩陣，可以 看到矩陣的結(jié)果很復(fù)雜，從而給后面穩(wěn)態(tài)分布的求解帶來了困難后面關(guān)于排隊系 統(tǒng)的其他信息，我們都是在已知年齡過程的穩(wěn)態(tài)分布的前提下推導(dǎo)的 這篇論文的余下部分足這樣組織的：第一章，我們對一些預(yù)備知識作簡要介紹 第二章，是對s m i k p h k 1 f c f s 型的排隊系統(tǒng)的分析及由其年齡過程構(gòu)造 的馬爾可夫鏈的轉(zhuǎn)移矩陣的計算第三章，對s m k i p h k 2 f c f s 型的排隊 系統(tǒng)的分析及由其年齡過程構(gòu)造的馬爾可夫鏈的轉(zhuǎn)移矩陣的計算第四章，在假定 第三章構(gòu)造的年齡過程的馬爾可夫鏈的甲穩(wěn)分布已經(jīng)求出的情況下，能得到的一些 排隊系統(tǒng)的有用的信息 第一章預(yù)備知識 1 1g i m 1 型馬爾可夫鏈( 過程) 在排隊論中矩陣解析方法很好的利用了g r ，m 1 型馬爾可夫鏈和m a a 型 馬爾可夫鏈，在這我們只介紹g u m a 型馬爾可夫鏈 定義1 若狀態(tài)空間e = ( t ，j ) ：t 0 ，1sjsm ) 上的馬爾可夫鏈 ：n o 的概率轉(zhuǎn)移矩陣具有如下形式； p = 玩a o0 b la 1a o j 島a 2a l 鼠a 3a 2 00 00 a o 0 a 1 , 4 0 其中a k ，b k ( k 0 ) 均為m m 階非負(fù)矩陣，則稱馬爾可夫鏈 ：n 0 ) 為 g i m 1 型馬爾可夫鏈。有時，也稱p 為g x m 1 型馬爾可夫鏈狀態(tài)集 ( ，j ) ： i 0 ，1 j m ) 稱為水平i 1 2離散型p 日分布 文中排隊系統(tǒng)的服務(wù)過程是一個尸日分布，我們簡單地介紹一下離散型p h 分布 考慮狀態(tài)集1 ，2 ， l + 1 上的m a r k o v 過程，狀態(tài)1 ，2 ，m 都是非常返 的，狀態(tài)m + 1 是吸收的狀態(tài)概率陣是 p = tt o 01 ，m 。是隨機(jī)子陣，元素20 ，并有t ese 列向量t o = ( i t ) e ，i t 是 非奇異的 6 第一章預(yù)備知識 定義2 非負(fù)整值上的離散分布p k ：k 0 稱為p 日分布，當(dāng)且僅當(dāng)它是上述 m a r k o v 鏈達(dá)到吸收時的轉(zhuǎn)移步數(shù)的分布 若m a r k o v 鏈的初始概率向量是( o ，o z 。+ 1 ) ，則 p o = o t 。+ l ，p a = o t 一1 t o ( k 2 1 ) 離散p 日分布p k ：k 0 的母函數(shù)為：p ( z ) = q 。+ 1 + z o ( 一z t ) 一1 t o ； 離散p h 分布p k ：k 0 的階乘矩為：p ( ( 1 ) = k ! a t k 一1 ( ，一t ) 一e ，k 0 1 3k r o n e c k e r 乘積 在涉及p h 分布時，經(jīng)常發(fā)生不同階數(shù)矩陣的運算，它們是通過k r o n e c k e r 乘積實現(xiàn)的設(shè)有k 1x 如，k ：砬矩陣a 和b ，其k r o n e c k e r 乘積定義為 a 固b = ( 4 u b ) a l l ba 1 2 b a l k 2 b a 幻l ba k l 2 b a k l 乜b 可以，爵出a o b 的維數(shù)為( - ：) ( 乜k ：) k r o n e c k e r 乘積有如下性質(zhì)： 1 p ( a 8 b ) = ( p 4 ) 8 b = a o ( 肛b ) ；2 ( a + b ) o c = a c + b o g ； 3 a o ( b c ) = ( a b ) o e ；4 ( a o b ) t = a t b t ； 5 ( a 口) ( g 圓d ) = ( a c ) 圓( b d ) ；6 a _ 1 g b 川= ( a 圓b ) _ 1 ； 7 a ，堤列向量，b a 7 = a t 圓b = b oa t ； 對于以上的性質(zhì)的證明，我們只需按照k r o n e c k e r 乘積的定義很容易得到 在這我們不給出證明，在文中直接加以應(yīng)用 第二章s m k p h 網(wǎng)1 f c f s 排隊系統(tǒng) 2 1系統(tǒng)介紹 排隊系統(tǒng)有k 個類型的顧客( 其中k 為正整數(shù)) ，所有的顧客都加入一個隊列， 采取“先到先服務(wù)。的規(guī)則由一個服務(wù)臺進(jìn)行服務(wù) 2 1 1顧客的到達(dá)過程 顧客的到達(dá)過程是一個離散的半馬爾可夫過程顧客分成k 個類型，并且成批 到達(dá)( 我們暫且稱為顧客批) 為了描述顧客批的性質(zhì)，先定義一個整數(shù)串的集合； n = j k ：矗= j 1 如矗。，1s 置1 i s 竹k ，1 k s 冊 其中，是集合r 中不同整數(shù)串的總數(shù)，n k 是第k 個批中顧客總數(shù)我們假 定是有限的對于一個到達(dá)過程，一個串j 一l j 2 靠r 表示一個有n 個顧 客的批，這n 個顧客分別為類型，矗矗我們稱j 為這個批的串表示因此， 一共有個不同的批表示 考慮一個有m 。個位相的半馬爾可夫鏈 ( 矗，h ) ，n o ) ，其中矗指第n 個 批到達(dá)瞬間半馬爾可夫鏈的位相，是第n 一1 個批和第n 個批到達(dá)之間的時間 ( 即轉(zhuǎn)移時問間隔) 顧客批的到達(dá)與下面方式的半馬爾可夫過程的轉(zhuǎn)移聯(lián)系在一 起令 為與第r t 次轉(zhuǎn)移相聯(lián)系的顧客批的串表示，即：一個顧客批厶在轉(zhuǎn)移時 刻到達(dá)定義： p 島= j ，t n = t ，厶= ，i 矗一1 = i ) = p 卻j ( ) ，1 t ，j m 。，禮1 ，r ， 其中t 是個正整數(shù)，變量以臼( t ) 是在位相為i 的條件上，從上一個批到達(dá)后經(jīng)過 時問t ，顧客批j n 達(dá)，并且半馬爾可夫過程的位相變?yōu)閖 的條件概率令現(xiàn)，j ( t ) 是個( i ，j ) 元素為p j , i d ( ) 的m 。m a 矩陣于是，矩陣序列 d d ，j ( ) ，t 1 ，j 杖) 提供了關(guān)于有標(biāo)記轉(zhuǎn)移半馬爾可夫到達(dá)過程的所有信息定義： d o ( t ) = 拒r 取，j ( t ) ，t 1 ，眈，= b o o l 玩，j ( ) ，t ，k ； 現(xiàn)= e 倒見j = 墨。見( t ) 8 笙三皇蘭絲【絲! ! 里【絲! 蘭里! 蘭堡墜墨絲 于是，矩陣墳為半馬爾可夫鏈“靠，h ) ，n2o ) 的嵌入馬爾可夫鏈在轉(zhuǎn)移時 刻的轉(zhuǎn)移矩陣我們假定墳是不可約的靠是隨機(jī)矩陣見的不變概率向量，即 有：以玩= 以，口。e = 1 ，其中e 是一個元素全都為1 的列向量 在穩(wěn)定狀態(tài)，半馬爾科夫鏈的轉(zhuǎn)移間隔時間( 即顧客批的到達(dá)間隔) 可以通過 下式計算； 玩( r ) = 以( t d 。( t ) ) e = l 那么顧客批的到達(dá)速率為a = ( e o o ( r ) ) 一，即每個時刻到達(dá)的顧客批平均數(shù)任意 一個顧客批類型為了的的概率為以d 口、e ，j r 類型為，的顧客批的到達(dá)速率 為b = a d 。j e ，即每時刻到達(dá)的類型為j 的顧客批的個數(shù)類型為k 的顧客 的到達(dá)速率為 a ( 的= ( z ) a ，1 k s k d e n 其中( zk ) 指類型為j 的顧客批中類型為k 的顧客的個數(shù)注意：k 為類型為 k 的顧客批的到達(dá)速率， 1 為類型為k 的顧客的到達(dá)速率不失一般性，我們假 定a ， b ，j r ， a ( ) ，1 k k ) 都足正的并且有限 2 1 2 顧客的隊列過程 個顧客批到達(dá)后，所有的顧客根據(jù)在批中的順序加入隊列中所有的批采取 。先來先服務(wù)”的方式由兩個服務(wù)臺服務(wù)對每一批顧客來說，顧客按他們在批中 的順序依次服務(wù)令g ( ) 為t 時刻隊列中顧客類型的數(shù)列串，它可以由在t 一1 時刻 可能完成服務(wù)的顧客和到達(dá)的顧客得到如果q ( t ) = j l j ：矗，那么系統(tǒng)中在t 時 刻有n 個顧客， 類型顧客在接受服務(wù)，而j z 類型顧客為第一個在排隊等候的顧 客，j 。類型顧客為最后一個排隊等候的顧客這n 個顧客將按照扎如，j 。 的順序接受服務(wù)。如果接著一個j 類型的顧客批到達(dá)，那么隊列將變?yōu)間 ( ) + j 如果接著一個顧客完成了服務(wù)，那么隊列將變?yōu)椋? ，j 3 ，j并且五開始接受服 務(wù)。在這我們不對某類型顧客在其顧客批中擁有優(yōu)先服務(wù)權(quán)的情況進(jìn)行討論 2 1 3 服務(wù)時間 墨三塞蘭坐【絲j ! 星l 絲! ! ! 旦蘭蘭堡墜墨絲 9 每個顧客的服務(wù)時間服從離散的p 分布，它們相互獨立并且與其到達(dá)過程 相互獨立對一個類型為k 的顧客來說，它的服務(wù)時間磯服從p 日分布，其矩陣 表示為 m k ，o l k ，t k ) ，其中”i 是p h 分布的位相個數(shù)，o k 是初始概率向量，孔 是個次隨機(jī)矩陣我們假定任意一個顧客的服務(wù)時問至少為1 這是因為對于離 散p h 分布來說，一個位相的轉(zhuǎn)移的時間為1 。而o z k e = 1 ( 1 ksk ) ，所以顧 客不能一接受服務(wù)就被服務(wù)完記露= ( i 一孔) e ，其中，是單位矩陣我們假定 每個p h 分布矩陣表示都是不可約的，即死+ 霹a k 是不可約的那么一個顧客 批的服務(wù)時間就是這個顧客批中所有顧客的服務(wù)時問的總和由于p h 分布的結(jié) 構(gòu)在卷積作用下是閉的，故一個類型為t ，的顧客批的服務(wù)時間8 j 也有離散時問的 p h 分布，矩陣表示為 l j ，o t j ，t j ) ，其中對j = j l 如矗，有 n m j = ：。； o c j = ( o f 9 l ，0 ，o ) ； t j = 乃。壤 喂 一，豫一； 乃。 刀= o 0 臻 由離散p h 分布的性質(zhì)有，一個類型為k 的顧客的平均服務(wù)時間為e ( s k ) = n ( j 一死) - 1 e 那么一個類型為，的顧客批的甲均服務(wù)時間：e ( s j ) = i j ie ( ) ， 其中川是類型為j 的顧客批的顧客數(shù)類型為，的顧客批的服務(wù)速率為= ( e ( s j ) ) 根據(jù)顧客批的到達(dá)速率和服務(wù)速率，排隊系統(tǒng)的交通強(qiáng)度為 i j i耳 p = b = e o j , ) = b ) e ( s k ) j 6 m7 ” 。1 o “ 2 1 ( 2 1 ) = b n ( j , k ) e ( s k ) = a ( 耐鯫 1 0 簍三童蘭坐【絲! ! 堡【絲! ! 蘭竺! 蘭堡墜墨絲 我們知道排隊系統(tǒng)穩(wěn)定當(dāng)且僅當(dāng)p 1 ，于是我們?yōu)榱讼到y(tǒng)的穩(wěn)定性假定p 可定義為： a g ( ) = w n ( t ) + 8 j n 一7 i ( t ) + l + t 一7 7 n ( t ) ，( 2 3 ) 其中n ( t ) 為在t 時刻或t 時刻之前最后一個服務(wù)完的顧客批的標(biāo)號， 仉m 是 指第n ( ) 批顧客離開系統(tǒng)的時段于是，在t 時刻若有一個顧客批離開，那么 n ( ) ，w 。( t ) ，( t ) 這些值就會發(fā)生改變，其中( c ) 可通過( 2 2 ) 計算得到 廣義的年齡過程 ( ) ，t 0 ) 分析如下：在一個顧客批的服務(wù)時間里， a g ( t ) 每過一個時刻增加1 ；當(dāng)?shù)趎 個顧客批完成服務(wù)，則要服務(wù)的顧客批的等待時問 笙三蘭蘭絲! 堅! 蘭絲【絲1 ! ! 蘭堡墜墨絲 1 1 可以通過計算這個得到；+ s j = 一+ 1 當(dāng)+ 3 一+ 1 是非負(fù)的，那么 這就是正要接受服務(wù)的顧客批的等待時間，也是它在這個時刻的年齡，即這個時刻 a g ( t ) 的值在第n + 1 個顧客批的服務(wù)期間，( t ) 每過一個時刻增加1 ，一直持 續(xù)8 矗+ ，個時刻到結(jié)束服務(wù)這種情況下，a g ( t ) 為正在服務(wù)的的顧客批的年齡當(dāng) + 8 厶一釓 l 是負(fù)數(shù)，那么表明下一個要接受服務(wù)的顧客批還沒有到來，還需要 一o 。( ) = 一( 。+ 8 厶一+ 1 ) 個時刻才能到達(dá)在( ) 為負(fù)的這段時聞內(nèi)，系統(tǒng)為 空的，還剩一( ) 長的閑期總之，如果時刻t 有a g ( t ) 0 ，那么變量a g ( t ) 記錄 的是正在接受服務(wù)的顧客批的年齡；如果a g ( t ) 0 ，那么一n ，( t ) 記錄的是閑期的 剩余時問我們稱a g ( t ) 為服務(wù)中顧客批的廣義年齡方程( 2 2 ) 和( 2 3 ) 表明了過 程 ，n20 ) 是 n 口( t ) ，t o 在顧客批離開點的嵌入過程 在一個顧客批離開的時刻，下個接受服務(wù)的顧客批的逗留時問可由方程( 2 2 ) 可得為；+ 5 對于a g ( t ) 20 來說，如果+ 5 厶一 r n + 1 0 ，則需5 個 時刻完成一個循環(huán)在這8 個時刻中，每過一個時刻，a g ( t ) 的值就增加1 基于以上分析，很容易看出a g ( ) 滿足以下方程； r ia g ( t ) + 1 ，如果t + l 時刻服務(wù)繼續(xù)進(jìn)行； a a ( t + 1 ) = ia g ( t ) + 1 一( t + 1 ) + l ，如果t + 1 時刻服務(wù)完成 、 為了構(gòu)造一個與a g ( ) 有關(guān)的的馬爾可夫鏈，我t f g l 進(jìn)一些與到達(dá)位相和服務(wù)過程 相關(guān)的附加變量引進(jìn)附加變量分情況i - i - i 侖如下： ( 1 ) a g ( t ) 0 時，我們引進(jìn)三個附加變量l ( ) ，j ( ) ，l ( t ) 我們由a g ( t ) 0 可得，此時系統(tǒng)為空，下一個顧客批還需要一a g ( t ) 個時刻才能到達(dá)我們由馬爾 可夫鏈 矗，n2o ) 來定義厶( ) ，l ( t ) = 矗，如果第n 個顧客批為將要接受服 務(wù)的顧客批，那么l ( t ) 表示將要達(dá)到的顧客批到達(dá)系統(tǒng)時半馬爾可夫鏈的狀態(tài)， j ( t ) ，l ( ) 則分別表示這個顧客批的類型和其初始服務(wù)位相。 ( 2 ) a g ( t ) 20 時，我們?nèi)砸M(jìn)三個附加變量：l ( ) ，( ) ，厶( t ) 因為這個時 候系統(tǒng)中有顧客存在，那么1 0 ( t ) = 矗，如果第n 個顧客批為正在接受服務(wù)的顧客 1 2 笙三皇蘭絲【絲絲【絲! 里! 墮壁墜墨竺 批，那么厶( ) 表示正在接受服務(wù)的那個顧客批到達(dá)系統(tǒng)時半馬爾可夫鏈的狀態(tài)， j ( t ) ，l ( t ) 則分別表示正在接受服務(wù)的那個顧客批的類型和在t 時刻的服務(wù)位相 可以看到，雖然在 z + 1 時， 這個概率是零根據(jù)從一個年齡到另一個年齡的轉(zhuǎn)移，以及每一個年齡馬爾科夫鏈的 附加變量的取值范圍，可得矩陣只的每個矩陣塊元素都為( m 。m “) ( m 。m “) 維 ( 1 ) 當(dāng)a g ( t ) = z ，z s 一1 時，此時系統(tǒng)中為空，下一批顧客還要經(jīng)過一z 個 時刻才能到達(dá)，在t - f1 時刻，顧客批要么還沒有到達(dá)，要么剛到達(dá)系統(tǒng)開始接受 服務(wù)，但至少能肯定這個顧客批沒有服務(wù)完離開系統(tǒng)那么應(yīng)該有( ) 隨時間應(yīng) 該增加1 ，而厶( t ) ，l 0 + 1 ) 都是指將要到達(dá)的這個顧客批到達(dá)系統(tǒng)時半馬爾可夫 鏈的狀態(tài)，j ( ) ，j ( t + 1 ) 都是表示這個顧客批的類型，h ( 0 ，l 0 + 1 ) 也都表示其 1 4 第二章 s m k p h k i 1 f c f s 排隊系統(tǒng) 初始服務(wù)位相于是，當(dāng)( t ) = z ，zs - 1 時 p a 9 ( + 1 ) = ，d 0 + 1 ) = j 7 ，j ( t + 1 ) = ，l o + 1 ) = i i ( ) = 一1 ，l ( t ) = j ，j ( t ) = z 厶( t ) 一磅 r i1 ，如果= 。+ 1 ，j = j 7 ，j = ，i = i = 10 ，否則 、 于是，由狀態(tài)按字典排序以及只有當(dāng)y = z + 1 ，j = j ，j = j 7 ，i = i 7 時概率為1 ， 則b = 厶。) 。( 。) ，而從( ) = z 轉(zhuǎn)到其他年齡的概率都為零 ( 2 ) 當(dāng)a g ( t ) = 墨z 三0 時，此時系統(tǒng)中至少有一個顧客批在接受服務(wù)，在 t + 1 時刻，這個顧客批可能繼續(xù)接受服務(wù)，也可能服務(wù)完畢離開系統(tǒng) 如果t 時刻接受服務(wù)的顧客批在t + 1 時刻繼續(xù)接受服務(wù)，此時轉(zhuǎn)移矩陣塊為 ao ，那么應(yīng)該有： a g ( + 1 ) = z + 1 ，而厶( z ) ，i o ( t + 1 ) 都是指這個顧客批到達(dá)系統(tǒng) 時半馬爾可夫鏈的狀態(tài)，j ( ) ，j ( t + 1 ) 都足表示這個顧客批的類型，但是厶( t ) 表 示t 時刻的服務(wù)位相，l 0 + 1 ) 表示t + 1 時刻的服務(wù)位相，這兩者的變化由服務(wù) 位相的轉(zhuǎn)移矩陣決定于是， p ( ( + 1 ) = z + 1 ，i a ( t + 1 ) = j 7 ，d ( t + 1 ) = j ，l ( + 1 ) = i ( t ) = z ，厶( ) = j ，j ( t ) = z 厶( ) = z = h n 簍：2 ，j = 了7 z 4 a o = a j 1a j ” a ：1 m 。 a i 1a ：一a i ”。 a 孑“，1a ：2 - - a 孑?！?。 簦三皇蘭絲! 絲! ! 絲l 絲j ! ! 竺蘭蘭堡墜墨堡 1 5 其中鴦( 1s ，jsm 。) 為維數(shù)為m t “m 的矩陣子塊分析每個a ，由( 2 4 ) 以及2 k 定義有： a 擴(kuò)： 忙工1 一 s 以 d 吃 o 0 n d m l | a 第三章 s m k i p h k i 2 f c f s 排隊系統(tǒng) 3 1系統(tǒng)介紹 跟前面一個服務(wù)臺一樣，排隊系統(tǒng)有k 個類型的顧客( 其中k 為正整數(shù)) ，所有 的顧客都加入個隊列，采取“先到先服務(wù)。的規(guī)則但由兩個服務(wù)臺進(jìn)行服務(wù)， 并且假定同一批中的顧客由同一個服務(wù)臺進(jìn)行服務(wù) 3 1 1 顧客的到達(dá)過程 兩個服務(wù)臺的排隊系統(tǒng)的到達(dá)過程與一個服務(wù)臺是一樣的，過程分析見2 1 i 3 1 2顧客的隊列過程 一個顧客批到達(dá)后，所有的顧客根據(jù)在批中的順序加入隊列中所有的批采取 “先來先服務(wù)”的方式由兩個服務(wù)臺進(jìn)行服務(wù)并且假定同一批顧客由同一個服務(wù) 臺進(jìn)行服務(wù)，對每一批顧客來說，顧客按他們在批中的順序依次服務(wù)令q ( t ) 為t 時刻隊列中顧客類型的數(shù)列串，它可以由在t 一1 時刻可能完成服務(wù)的顧客和到達(dá) 的顧客得到如果q ( t ) = j 。如矗，那么系統(tǒng)中在t 時刻有n 個顧客， 類型顧 客在一個服務(wù)臺接受服務(wù)，兩另一個服務(wù)臺的情況分析有： ( 1 ) 若口( ) 正好為一個批的顧客，則另一個服務(wù)臺為空五類型顧客為第一個 在排隊等候的顧客，矗類型顧客為最后一個排隊等侯的顧客這n 個顧客 將按照j - ，如，a 的順序接受服務(wù) ( 2 ) 若q ( ) 中顧客所屬批的個數(shù)大于1 ，即：j - 如五為一個批，扎1 j 沖2 a 為第二個批，則盔+ l 類型的顧客在另個服務(wù)臺接受服務(wù)并且第個服務(wù) 臺按照j - 如五的順序服務(wù)，第二個服務(wù)臺按照 + - 五+ 2 靠的順序服務(wù) 如果接著一個。，類型的顧客批到達(dá)，那么隊列將變?yōu)間 ( ) + j 如果接著一個 顧客完成了服務(wù)，假定為類型為j t 的顧客，那么隊列將變?yōu)槲?，矗? 一，矗，并且虎 類型顧客開始接受服務(wù)此時，五必須與j l 同屬一個批否則這個服務(wù)臺將對如 后面第1 個與矗不同屬一個批的顧客進(jìn)行服務(wù)，當(dāng)然，如果如后面的顧客與如都 同屬一個批，則這個服務(wù)臺此時為空 1 8 笙三皇蘭! ! i 絲! 里 絲3 絲旦蘭壁墜墨絲 3 1 3服務(wù)時間 兩個服務(wù)臺的排隊系統(tǒng)的服務(wù)時間與一個服務(wù)臺是一樣的，分析見2 1 3 那么根據(jù)顧客批的到達(dá)速率和服務(wù)速率，兩個服務(wù)臺排隊系統(tǒng)的交通強(qiáng)度為 1 1 1 1 1 p = 沁( 2 p ，) = ；a ，e ( ) = ；( z 南) e ( 軋) j e r j r2 2 l。j rk 。1 f 3 1 ) = ；h j n c j , k ) e ( 船) = ；a 一k = lj k一七= 1 為了系統(tǒng)的穩(wěn)定性我們假定p 1 3 1 4服務(wù)時間顧客批的實等待時間 令為第n 個顧客批到達(dá)后第個服務(wù)臺的剩余工作時間( 即第k 個 服務(wù)臺在第n 個顧客批到達(dá)后還需多長時聞輪到第n 個顧客批服務(wù)) 記w n = ( w 蚶，“k ，2 ) ，其中w n ，l 。，2 ，則服務(wù)臺的標(biāo)記1 ，2 是可以改變的，隨著其剩 余工作時間的變化而變化那么，我們應(yīng)有： 叫。+ l = o ( ( 叫。1 + 8 一+ 1 ) + ，( w n ，2 7 k + 1 ) + ) ，n 0 其中，礦= m a x o ，。1 ，o ( y ) 表示將n i l l9 的兩個元索按非降的順序重新排列得到 的新的向量，+ i 表示第n 個顧客批和第n + 1 個顧客批到達(dá)的間隔時間，。厶是 第n 個顧客批的類型，5 上是第”個顧客批的服務(wù)時間于是，”n l 為第n 個顧 客批的實等待時問，并且有 w n + 1 1 = m i n ( w n ，1 + s 一7 k + 1 ) + ，( w n 2 一十1 ) + ) 3 ，2廣義的年齡過程的分析 對于兩個服務(wù)臺，年齡分析比一個服務(wù)臺顯然要復(fù)雜一些，每個服務(wù)臺都可能 有個顧客批，每個顧客批都有一個年齡當(dāng)然分析每個正在接受服務(wù)的顧客批的 年齡肯定能像一個服務(wù)臺那樣能分析系統(tǒng)的其他指標(biāo)，但足那樣會增加計算的復(fù)雜 性，關(guān)于年齡過程的馬爾可夫過程維數(shù)很高，所以我們必須對系統(tǒng)分析清楚，從中 找出一個有利于分析系統(tǒng)其他指標(biāo)的年齡過程，降低計算的復(fù)雜性 苧三蘭蘭絲i 絲! ! 里【絲j 絲! 竺! 蘭堡墜墨絲 1 9 參考【12 】，我們可以考慮正在服務(wù)的兩個顧客批中年齡較小的那個顧客批，記 t 時刻的它為系統(tǒng)的年齡a g ( t ) 那么當(dāng)a g ( t ) 20 ，系統(tǒng)出于繁忙期( 即兩個服務(wù)臺 都有顧客批接受服務(wù)) ，此時系統(tǒng)中至少有兩個顧客批當(dāng)a g ( t ) 0 時，那么系統(tǒng) 中至少有一個服務(wù)臺為空，即系統(tǒng)中至多有一個顧客批，那么a g ( t ) 為t 時刻之后 第個到達(dá)系統(tǒng)的顧客批的年齡這個顧客批還要一( ) 個時刻才能到達(dá)系統(tǒng) 我們記n ( t ) = n 為t 時刻a g ( t ) 為第n 個顧客批的年齡 我們來分析一下這個年齡過程 ( ) ，t 之o ) ： 當(dāng)a g ( t ) 0 ，那么在t + 1 時刻 1 當(dāng)兩個顧客批都未完成服務(wù)，則有n ( t + 1 ) = u ( t ) ，于是a g ( t + 1 ) = ( ) + 1 ； 2 當(dāng)有一個顧客批完成服務(wù)，另一個顧客批繼續(xù)接受服務(wù)， ( a ) 等待的一個顧客批開始接受服務(wù)，則有( + 1 ) = n ( t ) + 1 ，于是 ( + 1 ) = a g ( t ) + 1 一t w ( t ) + 1 ； ( b ) 系統(tǒng)中沒有等待的顧客批，則有( f + 1 ) = n ( t ) + 1 ，于是a g ( t + 1 ) = a g ( t ) + 1 一 r n ( o + i ； 3 當(dāng)兩個顧客批都完成服務(wù)離開了系統(tǒng)， ( a ) 系統(tǒng)中等待的兩個顧客批開始接受服務(wù)，則有n ( t + 1 ) = l v ( t ) + 2 ， 于是a g ( t + 1 ) = a g ( t ) + 1 一r c t ) + l t n c t ) + 2 ； ( b ) 等待的一個顧客批接受服務(wù)，而另一個顧客批還未到達(dá)系統(tǒng)，則有0 + 1 ) = n ( t ) + 2 ，于是a g ( t + 1 ) = ( ) + 1 一r n ( o + l 一1 ( t ) + 2 ； ( c ) 系統(tǒng)中沒有等待的顧客批，此時顧客批都還沒有到達(dá)系統(tǒng)，則有( t + 1 ) = ( ) 4 - 1 ，于是a g ( t + 1 ) = a g ( t ) + 1 一r n ( o + 1 當(dāng)a g ( t ) 0 且系統(tǒng)中只有個顧客批時，那么在+ 1 時刻： 2 0 笙三童蘭! ! 絲! 堅f 絲! ! ! g 蘭蘭簍墜墨簍 1 當(dāng)t 時刻接受服務(wù)的顧客批未完成服務(wù)，則有n ( t + 1 ) = n ( t ) ，于是 + 1 ) = ( ) + 1 ； 2 當(dāng)t 時刻接受服務(wù)的顧客批完成服務(wù)離開系統(tǒng)， ( a ) 第n ( t ) 個顧客批還沒有到達(dá)系統(tǒng)，則有p + 1 ) = n ( t ) ，于是a g ( t + 1 ) = ( ) + 1 ； ( b ) 第g ( t ) 個顧客批正好到達(dá)系統(tǒng)，則有n ( t + 1 ) = n ( t ) + 1 ，于是 ( t + 1 ) = a g ( t ) + 1 一r ( t ) + 1 當(dāng)( ) 0 且系統(tǒng)中沒有顧客批時，那么在t + 1b f 麴j ： 1 第n ( t ) 個顧客批正好到達(dá)系統(tǒng)，則有( + 1 ) = ( ) + 1 ，于是( + 1 ) = ( ) + 1 一t n ( t ) q - 1 ； 2 第n ( t ) 個顧客批還沒有到達(dá)系統(tǒng)，則有( + 1 ) = n ( t ) ，于是( + 1 ) = ( t )