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

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