（概率論與數(shù)理統(tǒng)計專業(yè)論文）mxmc→mr1k排隊系統(tǒng)概率分析.pdf

順l j 淪義m “) m c m o ) i k 州1 j 人系統(tǒng)概率分析 摘要 本文一i - 嬰研究彳限弈l j l - i l z j 兩級小聯(lián)排隊系統(tǒng)m u ) i m i c 專i m p ) 1 1 1k ，對于串聯(lián) f i z j - j l l ! 隊模型u 經(jīng)紺劍i l l ：多學析的研究，并兒狀得了不少成果，但是對于成批到達、成 批服務的小f f ) - j - i i ! l a 系統(tǒng)f 內研究并不多見。本文用矩陣幾何解方法得到系統(tǒng)模型的狀念 轉移概率知i 陣、穩(wěn)態(tài)隊長及典算法。通過嵌入馬爾科夫鏈方法求出：i 繳服務系統(tǒng)受 m 時問及典分斫j 、受6 l 【概率、“笫一類成批等待的時問和“第二類成批等待的時問” 及乓他們的分斫j 、逗剛l i , j l , j 的分斫i 、以及i 級服務系統(tǒng)與系統(tǒng)的忙期分布。 關鍵詞：爿j 聯(lián)- t ：i i ! i a成批到達成批服務矩陣幾何解 a b s t r a c t 碩士論文 a b s t r a c t t h e t w o s t a g e t a n d e m q u e u e i n gs y s t e mm ( 。) m c 一m ( 7 ) 1 ki sm a i n l y s t u d i e di nt h i sp a p e r m a n ys c h o l a r sr e s e a r c h e dt h et a n d e mq u e u e i n gs y s t e m ，a n dr e c e i v e d al o to f c o n s e q u e n c e s ，b u tf o rt h ed i s c u s s i o no ft h ec u s t o m e r sa r r i v i n gi nb a t c ha n ds e r v e d i nb a t c hi sl i t t l e t h es u f f i c i e n t n e c e s s a r yc o n d i t i o n sf o rt h es y s t e m s t a b i l i t yw e r e p r e s e n t e db ym e a n so fm a t r i xa n a l y s i st h e o r ya n dp r o b a b i l i t yt h e o r y ，a n dt h ed i s t r i b u t i o n o fs t a t i o n a r yq u e u el e n g t ha n di t sa l g o r i t h mw e r eo b t a i n e d a tt h es a m et i m e ，t h ep a p e r i n t r o d u c e st h ed e f i n i t i o n so ft h es t a g e is e r v i c eb l o c k e dt i m e ，t h ef i r s t c l a s sa n dt h e s e c o n d - c l a s sb a t c ho fw a i t i n gt i m e s ，t h eb a t c ho fs o j o u r nt i m e ，a n do b t a i nt h e i r d i s t r i b u t i o n sr e s p e c t i v e l y w ec a na l s og e tb u s yt i m ed i s t r i b u t i o n so ft h es t a g e ia n dt h e w h o l es y s t e m k e yw o r d s ：t a n d e mq u e u e i n g ，a r r i v i n gi nb a t c h ，s e r v e di nb a t c h ，m a t r t i x g e m e t r i c s o l u t i o n s i i 聲明 本學位論文是我在導師的指導下取得的研究成果，盡我所知，在本學 位論文中，除了加以標注和致謝的部分外，不包含其他人已經(jīng)發(fā)表或公布 過的研究成果，也不包含我為獲得任何教育機構的學位或學歷而使用過的 材料。與我一同工作的同事對本學位論文做出的貢獻均已在論文中作了明 確的說明。 研究生簽名：4 刨掣 、1 知洚石月矽日 學位論文使用授權聲明 南京理工大學有權保存本學位論文的電子和紙質文檔，可以借閱或上 網(wǎng)公布本學位論文的部分或全部內容，可以向有關部門或機構送交并授權 其保存、借閱或上網(wǎng)公布本學位論文的部分或全部內容。對于保密論文， 按保密的有關規(guī)定和程序處理。 研究生簽名：乏翌望蘭訇 q 年6 旯哆b 傾i j 論義 m “) m c m i i k 州| j 人系統(tǒng)概；卒，分析 1 引言 奉章我們將簡，n 的來介紹排隊論的發(fā)展歷程和f | j 聯(lián)排隊例絡系統(tǒng)，成批到達 和成批j j 技務的：f i i i l s a 系統(tǒng)的研究內密、背景和現(xiàn)狀，同時指小本文的叢本結構和i 主 要內容。 1 1 排隊論及應用 1 1 1 排隊論發(fā)展簡介 排隊v e l 2 p = l r - - 隊理論，它是運籌學的一個重要方向，它主要的是研究由于顧客 的到達和離丌以及服務臺的工作和休假，而引起的排隊隊伍的積累和消散問題。 二十世紀初期，一位丹麥的數(shù)學家、電氣工程師愛爾朗( a k e r l a n g ) 用概率的 方法對f t i 話通話問題做了深入的研究，從而開創(chuàng)了這門新學科，并且建立了包括 先到先j j i i 務等許多叢本規(guī)則。在3 0 年代中期，當費勒( w f e l l e r ) 引進了生滅 過私! 時，排隊淪才被數(shù)學界承認為- 1 3 重要的學科。在二戰(zhàn)期間和以后，排隊論 越米越多的被人研究，在運籌學這個新領域中成為一個必不可少的重要內容。2 0 ：紀5 0 年代初肯德爾( d g k e n d a l l ) 對排隊論作了比較系統(tǒng)的研究，他采用嵌 入馬爾可夫鏈( a m a r k o v ) 方法研究了排隊問題，使排隊論得到了進一步發(fā)展。 排隊系統(tǒng)模型盡管千差萬別，但我們都可以把它抽象為由顧客和服務臺構 成，它有三個組成部分：顧客進入過程、顧客排隊等待規(guī)則和服務機構。顧客進 入過程足拙述顧客的米源和顧客是按怎樣的規(guī)律到達排隊系統(tǒng)的；顧客排隊等待 艦則一般分為等待規(guī)則、損失規(guī)則和混合規(guī)則，在等待規(guī)則和混合規(guī)則中通常又 可分為后來先服務、先來先服務、優(yōu)先非搶占服務、優(yōu)先搶占服務、隨機服務等； 服務機構主要是指服務臺的數(shù)目，可以分為無限多個服務臺、有限個服務臺和單 服務臺。進行服務時服務的方式可分為串聯(lián)和并聯(lián)，接受服務的顧客可以是單個 的也可以是成批的，服務時間可以服從不同的分布，一般分為指數(shù)分布、定長分 布、一般分布與幾何分布等。 沿用k e n d a l l ( 1 9 5 1 ) 采用的表示排隊系統(tǒng)的方法，一個排隊過程通常采用符 號m n p x y 其中m 代表顧客到達間隔時間分布的類型，n 代表服務臺服務時間 分布的類型，p 表示服務臺的臺數(shù)，x 表示隊伍的容量，y 表示排隊規(guī)則。如m m c 表示顧客按泊松分布到達，服務時間服從負指數(shù)分布、有c 個服務臺、無限等待 空間的排隊系統(tǒng)。 分布 排隊規(guī)則 符號解釋 符號l 解釋 1 引言 碩士論文 m 指數(shù)分布 f c f s先來先服務 e n e r l a n g 分布 l c f s 后來先服務 pp a r e t o 分布r o s 隨機服務 p h p h 分布 p r 優(yōu)先權服務 g 一般分布 g 1 ) 一般規(guī)律 表1 1 1 排隊常用記號 一個排隊系統(tǒng)要從兩方面考慮，即服務機構和顧客的利益來考慮，顧客希望 的等待時間越短越好，那就需要服務機構的服務臺越多越好，而服務機構要想獲 得很高的利益就必須限制服務臺的個數(shù)。綜合考慮排隊的幾個指標：隊長、等待 時間、和服務臺的忙期，成為排隊論的主要研究內容。 1 1 2 排隊論的應用 隨著研究的深入，排隊理論日益得到廣泛應用。人們發(fā)現(xiàn)通信系統(tǒng)、網(wǎng)絡設 計、計算機存儲、交通系統(tǒng)、物流調度等各種現(xiàn)象都可以通過排隊模型來描述， 同時應用相應排隊理論的研究成果，可以指導各種策略設計，給國民經(jīng)濟的發(fā)展 帶來巨大的貢獻。 比如銀行的排隊問題：“我算過一筆賬，工商銀行現(xiàn)在每天平均辦理4 3 0 0 萬筆業(yè)務，電子銀行的代率( 電子銀行代替人工完成交易的比率) 為3 0 ，扣除 這1 3 0 0 萬筆經(jīng)由電子銀行辦理的業(yè)務，以1 7 0 0 0 個網(wǎng)點計算，一線柜員每人每 天需辦理2 0 0 筆業(yè)務。以8 小時工作日計，平均每筆的辦理速度是2 分4 0 秒不 到。從工作效率和處理速度上看，確實值得肯定。工商銀行辦公室新聞處處長 謝泰峰告訴記者：“對銀行排隊問題，工商銀行上至行長下到基層柜員，沒有一 個不在殫精竭慮，不在冥思苦想 。不斷梳理和改造服務流程，也有利于提高服 務效率，緩解排長隊嚴重現(xiàn)象。據(jù)了解，不少銀行目前正在加快現(xiàn)有網(wǎng)點綜合化 建設進程，使對公業(yè)務和個人業(yè)務能在同一個電子平臺進行，預計網(wǎng)點綜合化后 將使工作效率提高三分之二。銀行排隊現(xiàn)象：是個管理問題。排隊，事實上就是 等待。對于到窗口辦事的客戶來說，等待，恐怕是最讓人難以忍受的事了。在我 國的大城市，在銀行營業(yè)網(wǎng)點排隊超過一個小時以上幾乎成為家常便飯，對大多 數(shù)客戶而言，排隊是他們別無選擇的，只能忍受。 有研究企業(yè)管理和行為科學的專家曾經(jīng)對客戶在銀行長久排隊后的心理承 受力進行調查，研究結果的數(shù)據(jù)表明，在銀行排隊以3 分鐘和3 分鐘以后為界， 客戶對排隊時間和實際排隊時間的感知有很大的差距。通常情況下，排隊等待2 分鐘后，客戶感覺比較接近實際，感覺就是等了2 分鐘。但等待5 分鐘后，客戶 會感覺就像是等了1 0 分鐘。這就是說，5 分鐘的排隊時間是滿意與否的臨界點。 傾j ：論義 m “m c m ( r l i k 州隊系統(tǒng)概率分析 美罔一家分門研究顧客行為的公i 對惜釗對積i 餓行嘲點等候的鬻，1 進行凋研， = i e i i l9 0 的受訪桿表示，他們能夠接受的蜮長等待時問足5 分鐘、能夠接受的最 長交易時| 、i j j 足3 5 分鐘、) 以能夠接受的隊伍長度最多為5 人。4 i 少銀行為了解決 這個5 分鐘的心理臨界點，采取了叫號機j j 陵務措施，hf 內就足為改善客戶的滿意 度進行努力。顯然，排隊問題，真的不是一個簡單的服務問題。專家說，這是一 個管理問題。表面j ：n 勺排隊問題背后，實際上隱藏著銀行改善管理的”大文章”。 在西方發(fā)達國家，也曾經(jīng)歷過銀行排隊的難題。國外那些老牌的商業(yè)銀行，早就 通過引入技術和管理創(chuàng)新來解決這個難題，比如通過調查社區(qū)人員流量，合理設 計網(wǎng)點布局，來減少客戶排隊等待時間。 1 2 排隊論的經(jīng)典研究方法 自從排隊論這門學科形成以來，逐漸出現(xiàn)了許多新的研究方向和研究方法。 大景的科研工作輯在此領域取得了豐碩的成果。排隊論方面的專家田乃碩等將矩 阼解析法引入到g i m 1 型的休假排隊模型，并研究了部分服務臺同步的休假排 隊理論模型，極大私度上豐富了排隊模型的理論；經(jīng)典的排隊理論主要是建立在 模型滿足馬爾科夫盹的占 i j j 卜，研究平穩(wěn)狀態(tài)下系統(tǒng)的等待隊長、等待時問等統(tǒng) 計特征量。一般來說，經(jīng) j i 豐- i i 隊理論的求解方法主要有以下幾種： 一、1 茨入馬氏鏈法( e m b e d d e dm a r k o vc h a i n ) ，現(xiàn)在已經(jīng)被發(fā)展至馬氏更新法。 這種方法的關鍵是通過尋找過程的馬氏點或再生點，運用馬氏鏈的特性或建立更 新方程來得到排隊系統(tǒng)的統(tǒng)計特征量。由于該方法較多地用到排隊模型的概率意 義解釋，從而需要較多的概率論知識作為基礎，并且各指標的求解比較復雜。 二、補充變量法。該方法通過增加變量，構造向量馬氏過程( v m p ) 從而建立密 度演化方程，并求解各種統(tǒng)計特征量。該方法將隨機性的、不確定的排隊論問題 轉化為確定性的方程來求解，極大地降低了求解過程的復雜程度，但對方程求解 的技巧要求較高且通常僅可得到解的拉普拉斯變換，而且關注的只是過程的狀態(tài) 概率而非轉移概率。具體方法精髓可參考徐光輝 1 1 三、n n e u t s 教授提出的擬生滅過程理論，他將生滅過程的方法加以推廣和引申， 逐漸形成了一套可以處理一系列相關于p h 、m a p ( 馬氏到達) 及b m a p ( 批馬氏到達) 分布所構成的排隊模型。尤其值得提出的是擬生滅過程理論已形成了完整的算法 程序，為排隊論模型的研究提供了較好的實證結果。其余的還有國內侯振挺教授 提出的馬氏骨架方法 2 1 、國外b r i l l 教授提出的水平穿越方法 5 1 等。 1 3 串聯(lián)開排隊網(wǎng)絡系統(tǒng)的研究 排隊網(wǎng)絡指的是由一些服務點和聯(lián)結這些服務點的路徑所構成的總體，其中 1 引言 碩士論文 每個服務點相當于一個單臺或多臺的排隊系統(tǒng)，顧客在一個服務點接受完服務后 按照定的規(guī)律沿著路徑到下一個服務點接受服務，一直到接受完所有的服務點 的服務。 j a c k s o n ( 1 9 5 7 ) 2 8 最早開始研究排隊網(wǎng)絡模型，后來被稱為j a c k s o n 網(wǎng)絡， 或稱指數(shù)開網(wǎng)絡，或是j a c k s o n 開網(wǎng)絡，它是由m 個編號為1 ，2 ，m 的服務點所 組成，其中第f 個服務點包括朋，個服從獨立同分布的指數(shù)分布服務時間的服務 臺，第f 個服務點的外部顧客輸入服從參數(shù)為無的泊松流，各服務點的外部顧客 輸入與各服務時間為相互獨立。顧客在第f 個服務點接受完服務后立即以概率p ；， 沿路徑轉移到第j 個服務點進行排隊等待，而以概率g ，= 1 一二p ，離開該系 統(tǒng)，對于j a c k s o n 開網(wǎng)絡，容易證明它具有乘積型解，也即網(wǎng)絡的平穩(wěn)分布等于 各服務點平穩(wěn)分布的乘積。如果在指數(shù)開網(wǎng)絡中令所有z = 0 ，即沒有外部輸入： 令所有q ，= 0 即沒有輸出：同時假定系統(tǒng)中的顧客總數(shù)為固定的n ，這樣得到排隊 模型稱之為指數(shù)閉網(wǎng)絡，或j a c k s o n 閉網(wǎng)絡，或g o r d o n n e w e l l 網(wǎng)絡( g o r d o n & n e w e l l ( 1 9 6 7 ) 3 9 ) 對于指數(shù)閉網(wǎng)絡，它的平穩(wěn)分布也是乘積型的，此時各乘積 項可以看成是帶有p o i s s o n 輸入的各服務點單獨存在時的平穩(wěn)分布，但并非是網(wǎng) 絡中各服務點的邊緣分布，也就是說，這些服務點中的顧客數(shù)相互不獨立。各服 務點中顧客數(shù)的不獨立性是顯而易見的，因為此網(wǎng)絡中顧客總數(shù)固定。此后，逐 漸開始研究非指數(shù)網(wǎng)絡是否能具有乘積型解。 m u n t z ( 1 9 7 2 ) 4 0 研究了泊松輸入蘊涵p o i s s o n 輸出這種性質，記為 mjm ，證明了服務點具有m m 性質的網(wǎng)絡是具有乘積型解的，同時該網(wǎng) 絡也具備mjm 性質。b a s k e t t 等( 1 9 7 5 ) 4 1 證明對服從一般服務分布的多類 顧客網(wǎng)絡，只要排隊的規(guī)則為處理機分享( p r o c e s s o r s h a r i n g ) ，后來先服務的 強占繼續(xù)型( l a s t - c o m e f i r s t s e r v e d p r e e m p t i v e r e s u m e ) 、或無窮多個服務 臺，平穩(wěn)分布仍有乘積解c h a n d y 等( 1 9 7 7 ) 4 2 證明了在非指數(shù)服務的情形，具 有乘積型解的網(wǎng)絡的排隊規(guī)則必須是立刻服務規(guī)則，即顧客在到達時刻必須立刻 開始接受服務。因此，像優(yōu)先權服務、先來先服務等非立刻服務規(guī)則不能產(chǎn)生乘 積型解。n o e t z e t ( 1 9 7 9 ) 4 3 提出了一種更為一般的排隊規(guī)貝j j l b p s ( 末批分享處理 l a s t b a t c h p r o c e s s o r - s h a r i n g ) ，包括上述處理機分享、后來先服務的強占繼 續(xù)型、和無窮多個服務臺為特例，證明了在一類更廣泛的對稱排隊規(guī)則中，l b p s 類是唯一的對所有服務分布都能產(chǎn)生乘積型解的類。另外，k e l l y ( 1 9 7 6 ) 4 4 與 b a r b o u r ( 1 9 7 6 ) 2 9 則考慮了包括多種路徑方式，多種排隊規(guī)則在內的多類顧客， 一般服務分布的網(wǎng)絡，利用可逆性得出了一種乘積型解。 最近，s e r f o z o ( 1 9 8 9 ) 4 5 研究了路徑與服務速度依賴于系統(tǒng)顧客等待長度 的m a r k o v 網(wǎng)絡，它把通常所考慮的各顧客選擇路徑相互獨立、各服務點的服務相 4 傾i ：論義 m “) m c m ( 7 j k 柵隊系統(tǒng)概率分析 = f 獨立f j 網(wǎng)絡包含和! 內作為特例，而兒現(xiàn)和：n 勺模型更易。卜姚述：并行處理，避免 擁擠而改變路徑、容呲| - i - 行i 駁的轉移掰i 塞、和增加或絎f 減處列! 速度以適應后而路徑 的擁擠等現(xiàn)緣。他j i 進了批寫符服務點顧祥數(shù)的一般網(wǎng)絡過程，導出了它的平穩(wěn) 概率分和，此分f l i - j ：有向：饜函數(shù)的乘積型解。v a nd i j k & r a m a s e w i c z ( 1 9 9 1 ) 4 6 考慮了具有般服務需求的網(wǎng)絡，其路徑依賴j ：顧客在下圳! i 務點所需的服務時 間，求得了非標準的乘積型解。 服務點容量有限的網(wǎng)絡一般都沒有乘積型解，除非路徑可逆( 見k e l l y ( 1 9 7 9 ) 4 7 ) ，或者遇到服務點的容量達到飽和時顧客會越過此服務點，如同此時的服 務速度等于0 0 對后面這種情形，以前文獻中的證明都是直觀的，而v a n d i j k ( 1 9 8 8 ) 3 6 則給出了簡單、嚴格的證明。 對于有阻塞的非指數(shù)網(wǎng)絡，v a n di j k ( 1 9 9 1 ) 4 8 研究了顧客遇到阻塞時服 務“重復”或“停止 兩利，類型。在一定條件下，兩種類型被證明是等價的，而 且可導出乘積型解。 串聯(lián)排隊網(wǎng)絡系統(tǒng)在海港、航空港運輸、計算機通訊、交通控制、存儲系統(tǒng)、 柔性制造系統(tǒng)、生產(chǎn)箭恥、生產(chǎn)流程等領域中的應用非常廣泛，特別是有限容量 的排隊系統(tǒng)網(wǎng)絡。對于有限容適的串聯(lián)排隊網(wǎng)絡系統(tǒng)，人們研究得較多的是用逼 近的方法，求系統(tǒng)指標的近似數(shù)值解。如：a l t i o k 2 3 ( 1 9 8 9 ) ， 1 3 r a n d w a l n j o w 2 5 ( 1 9 8 8 ) ，g e r s h w i n 2 4 ( 1 9 8 7 ) ，h i l l i e r b o l i n g 2 6 ( 1 9 6 7 ) 等，這些方法在計算上具有不同程度的精確性和復雜性。關于有限容量的串聯(lián)排 隊網(wǎng)絡系統(tǒng)指標的精確求解，這方面的工作不多，而且大多考慮比較簡單的系統(tǒng)， 如：k o n h e i m & r e i s e r 3 1 ( 1 9 7 6 ) 考慮了系統(tǒng)m m 1 專m i k ，用復分析的方法給 出了系統(tǒng)平穩(wěn)的充要條件及平穩(wěn)概率分布；l a t o u c h e n e u t s ( 1 9 8 0 ) 用矩陣分析 理淪給出了系統(tǒng)，m m r 專m c k o h 平穩(wěn)隊長分布。賈波、周家良 8 在p h 型 級串聯(lián)反饋開排隊網(wǎng)絡系統(tǒng)分析中研究了朋型級串聯(lián)反饋開排隊網(wǎng)絡系 統(tǒng)，采用遞推方式給出了馬爾可夫過程的轉移矩陣，并利用矩陣分析方法進行求 解，得到了該系統(tǒng)的穩(wěn)態(tài)解和相應的忙期長度；周家良 1 7 基于朋型級串聯(lián) 反饋開排隊網(wǎng)絡系統(tǒng)分析中對隊長和忙期的研究方法，在冊朋1 n 反饋排 隊系統(tǒng)的逗留時間的文章中，接著給出了逗留時間穩(wěn)態(tài)分布。周家良 3 ( 1 9 9 8 1 ) 在上述排隊模型的基礎上又增加了閉鎖規(guī)則，研究了有阻塞的多級串聯(lián)排隊系 統(tǒng)，得到了該系統(tǒng)的隊長、忙期長度、逗留時間等分布的簡明精確顯式解；周家 良、賈波 1 3 研究了具有n 個有限容量服務節(jié)點的j a c k s o n 網(wǎng)絡，運用馬爾可夫過 程的狀態(tài)空間及q 矩陣的遞推表示方法，富有技巧性的給出了相應的穩(wěn)態(tài)顯式精 確解。 1 4 成批到達與成批服務的排隊系統(tǒng)的探討 l 引言碩：l 二論文 成批到達、服務排隊模型常用于港口、鐵路等裝運系統(tǒng)此時，以成批到達的 貨物為顧客，大型裝載車輛為服務臺。為了降低成本，每次需盡量滿足車輛的裝 載能力，當待運的貨物太少時，大車或或取消此次運輸，等待新的貨物到來，運 輸過程延遲或中斷后重新啟動，需增加設備的調配、準備時間。以此類實際問題 為背景。 對于批量到達的排隊系統(tǒng)，在排隊論基礎上就有討論，在這本書上，共討論 了這樣幾種批到達的排隊模型：彰m 1 、m f g 1 、g 1 ，用嵌入馬爾 科夫過程得到了他們的平穩(wěn)分布，隊長分布以及等待時間分布等：蘇時光、陳薇 1 4 研究了m 工m c 專p h l l k 的有限容量兩級串聯(lián)開排隊系統(tǒng)，并給出了 排隊平穩(wěn)條件以及用矩陣迭代法得到了平穩(wěn)隊長分布和受阻概率分布。 對于批量服務系統(tǒng)，許多學者做了研究。l e o n a r dk l e i n r o c k 5 2 3 給出了一種特 11 殊的批量服務系統(tǒng)m m 置1 的平穩(wěn)概率分布：= ( 1 一二) ( 二) ，其中z 0 滿足 z oz o 允r 一( 旯+ ) z x + = 0 以及 2 0 | 1 的解。徐光輝也對m m k 1 坐了探討，給出 了類似的結果；j m e d h i c s 5 3 給出了這類服務系統(tǒng)概率母函數(shù)的形式，但未 能進一步探討母函數(shù)中未知數(shù)的求法。j w c o h e n e t 在其經(jīng)典著作t h es i n g l e s e r v e rq u e u e ) ) 中給出批量服務系統(tǒng)各項指標的精確數(shù)學表達形式， j w c o h e n 5 4 在求解中使用了大量艱澀難懂的數(shù)學工具，因此所得結果也僅 有理論上的意義。在2 0 0 0 年周志中、周亞平給出了一類批量服務的排隊系統(tǒng)求解， 這是一個比較特殊的批量服務排隊系統(tǒng)一公交系統(tǒng)的穩(wěn)態(tài)概率分布的求解過程， 并在此基，礎上給出這類服務系統(tǒng)平均隊長的算法。 徐光輝、袁學明 7 更為一般地推廣了有限容量的成批到達成批服務的兩級 串聯(lián)排隊網(wǎng)絡系統(tǒng)模型，用矩陣分析理論對系統(tǒng)m ( 。) m c 寸跗( 7 ) 1 k 進行 了研究，得到了其狀態(tài)過程的q 一矩陣，給出了系統(tǒng)平穩(wěn)的充要條件、平穩(wěn)隊長分 布及其算法等系統(tǒng)的平穩(wěn)性態(tài)指標。 1 5 本文的主要研究內容和結構 本文是在m m 1 哼m m 1 的基礎上進行改進，將顧客的到達改為成批 到達，并且i 及服務系統(tǒng)有c 個服務臺，i i 級服務系統(tǒng)是成批服務，用矩陣幾何 解方法得到系統(tǒng)模型的狀態(tài)轉移概率q 一矩陣、穩(wěn)態(tài)隊長及其算法，通過嵌入馬 爾科夫鏈方法求出：i 級服務系統(tǒng)受阻時間其分布及受阻概率、“第一類成批等 待時間”和“第二類成批等待的時間 及其他們的分布、逗留時間的分布、以及 6 頌j ：論文m “) m c m “) i l k 排隊系統(tǒng)概牢分析 l 級服務系統(tǒng)與i i 級服務系統(tǒng)的柏：期分斫j 。 小義的結構： 第一章足弓i 苦。主要介紹論文的選題背烏及研究現(xiàn)狀，以及本文的研究內容和結 構。 第二章是預備知識。只要介紹生滅過程、擬生滅過程、矩阼解析法、概率守恒原 理等。 第三章是m ( 。i mi coi m ( 7 li i l k 系統(tǒng)分析，主要是介紹狀念轉移的q 矩陣、穩(wěn) 態(tài)隊長及其算法、i 級服務系統(tǒng)受阻時間其分布及受阻概率、“第一類成批等待 時間 和“第二類成批等待的時間 及其他們的分布、逗留時問的分布、以及i 級服務系統(tǒng)與系統(tǒng)的忙期分布。 第四章是總結與展望 7 2 預備結論 碩士論文 2 預備結論 2 1p h 分布的相關定義 2 1 1 連續(xù)型朋分布 我們考慮系統(tǒng)狀態(tài)集 1 ，2 ，m ，m + l 上的m a r k o v 過程，狀態(tài)l ，l 都是非 常返的，狀態(tài)所+ 1 是吸收態(tài)狀態(tài)過程的無窮小生成元是 q = l ：卅 肌階方陣丁= ( 乃) 滿足毛 o ，乃o ，j j f t o 是非負列向量， t o = ( 互o ，露) 。，t e + t o = o ，過程的初始概率向量是 ( 口，+ 1 ) ，口= ( ，o c m ) ，口口+ + l = 1 引理l 狀態(tài)過程o 以初始概率向量 ，+ 。) 出發(fā)直到吸收于狀態(tài)m + l 為止的 時間有分布函數(shù) f ( x ) = 1 - a e x p ( t x ) e ，x 0 ( 2 1 ) 定義1 f o ，) 上的概率分布，( ) 稱為朋分布，當且僅當它是一個有 m a r k o v 過程的吸收時間分布，有分布函數(shù)( 2 1 ) ，位，丁) 稱為它的m 階表示 2 1 2 離散型陽分布 對于離散型p h 分布，與連續(xù)時間m a r k o v 過程相似，考慮狀態(tài)集 1 , 2 ，m ，m + l 上的離散時間m a r k o v 鏈仍設m + l 是吸收狀態(tài)轉移概率矩陣為 肚h 0 1 l， ii 瓦。是隨機子陣，元素巧0 , 9 精t e e 列向量? o = ( j t ) e ，j t 是非奇異的 定義2 非負整值上的離散分布 見 稱為跗分布，當且僅當它是上述m a r k o v 鏈 達到吸收狀態(tài)時的轉移步數(shù)的分布。 若m a r k o v 鏈的初始概率向量是 ，+ 。) ，則 p o2a ，肼+ 1 ， 仇= a t 一1 t o , k 1 ，t ) 稱為它的m 階的陽表示。 2 2 生滅過程 2 2 1 生滅過程的定義 塒 i j 淪艾 m ( “) m c m ( ) il k 州：隊系統(tǒng)概水分析 改m a r k o v 鏈x = ( ，) ，o ，狀態(tài)空1 1 i js = o ，1 ，2 ，) ，特轉移概率矩陣 p q ) = ( 島( ，) ) 滿足： 當h 允分d x l l i - ， 只，+ l ( 五) = 五 + d ( ) ， 屆，1 ( 辦) = p i h + o ( h ) ， 只，( 庇) = 1 一( 丑+ “) 矗+ d ( 廳) ， n ( 辦) = d ( 辦) ， i 一，j 2 2 丑0 ，i 0 ， “0 ，i 1 ， 觴= o ，i 0 f 0 稱x 為生滅過程 2 2 2 生滅過程的微分方程組 設只( f ) 為系統(tǒng)在時刻f 處于狀態(tài)f 的概率，即 只( f ) = 以( f ) = f ) 系統(tǒng)在時刻f + f 處于f ( 有限狀態(tài)時0 i k ：可數(shù)狀態(tài)時0 i ) 這一事件 可以在下列互斥情形下發(fā)生： ( 1 ) 當系統(tǒng)在時刻f 處于狀態(tài)i ，而在時刻o + & ) 內沒有變化。其概率為 只( t ) ( 1 一五出- a ，a t ) + o ( m ) ( 2 ) 當系統(tǒng)在時刻f 處于狀態(tài)f 一1 ，而在( f + a t ) 內由f 一1 轉移到i ，其概率 為 e l ( f ) 丑一i a t + d ( f ) ( 3 ) 當系統(tǒng)在時刻f 處于狀態(tài)i + 1 ，而在o + 出) 內由i + 1 轉移到i ，其概率 為 + l ( t ) 1 t + la t + o ( a t ) ； ( 4 ) 當系統(tǒng)在( ，+ a t ) 內發(fā)生兩次或兩次以上轉移，其概率為o ( a t ) 。 故由全概率定理，在有限狀態(tài)時， 只o + a t ) = 只 ) ( 1 一乃f 一，a t ) + 只一l o ) 丑一l a t + 氣l ( f ) f + l a t + o ( m ) ，0 i k ， 移項后，兩端都除以出得 p j ( t + a _ t ) _ - p 一，( t ) ： 一1 只一lo ) 一( + ，) 只( f ) 忑_ 一= 一l 一l u j l + ，) u j + m e + l ) + o ( a t ) ，0 f k ， 令岔一0 即得 只。= 以一1 只一l ( r ) 一( 乃+ f ) o ) + t f + l + l ( f ) + o ( a t ) ，0 f 0 ( 2 7 ) 存在，且與初始條件無關。 2 3 矩陣解析法與擬生滅過程 2 3 1 矩陣解析法 在這十多年來，n e u t s 研究的矩陣解析法得到空前的發(fā)展，他的兩本專著 ( 1 9 8 1 ，1 9 8 9 ) 3 5 就是關于這一方法的理論基礎和應用領域的代表作。這兩本專 著分別討論了擬生滅過程于m g 1 型馬爾科夫過程的基本周期( 特別包括忙期 在內) ，以及它們的矩公式。以朋分布為基礎，n e u t s 引進了g i m 1 型與 m g i 型兩類m a r k o v 過程，使得原來在指數(shù)分布假定下才能分析的很多隨機模 型推廣到朋分布的情形。由于朋分布可以逼近任意非負隨機變量的分布，從 而使一般分布假定下的隨機模型能夠得到易于計算的逼近。 2 3 2 擬生滅過程 擬生滅過程( q u a s ib i r t ha n dd e a t hp r o c e s s ) 是經(jīng)典生滅過程( 王梓坤， 1 9 8 0 2 2 ) 從一維狀態(tài)空間到多維狀態(tài)空間的推廣，是經(jīng)典生滅過程的最新發(fā)展。 正如生滅過程的生成元具有三對角形式一樣，擬生滅過程的生成元是分塊的三對 1 0 f ! i i j 論義 m x ) l m i c m i 。) i k4 | | ：隊系統(tǒng)概率分析 角甜i 陣。近二十年l 二成為分析復雜隨機模型的亟安工具 ，：。- ，血1 2 一個二維脅砌v 過私! ( ，) j ( 講，狀念空i 、j i j 是 q = ( 后，歹) ，k 0 , i j ， ， 稱口( 吐，( 班是一個擬生滅過程，如果其生成元可寫成下列分塊三對角形式 q = 玩t 1 民a i( 2 1 4 ) a 2a ia ol i 其中所有子塊都是m 階方陣，滿足 ( a o + c o ) g = ( b l + a + c ) e = ( a + b + c ) e = 0 a 。和a 有負的對角元素和非負的非對角元素，其余子塊均是非負陣，稱狀態(tài)集 ( 七，1 ) ，( 后，2 ) ，( j | ， ) 為水平k 。若過程是正常返的，以( x ，j ) 表示過程( r ) ，( 講的極限變量，并記 = l i m e x ( t ) = 七，( f ) = = 尸似= 七，j = ， 其中k 0 ，1 j m 為適應q 的分塊形式，將穩(wěn)態(tài)概率按水平寫成分段形式 鞏2 ( 以，以：，) ，k 0 我們直接引j 玎下列結果， 設連續(xù)時f n j 馬氏過程 令 q = f b 。l 1 研剛2 i 羔尺扣t b k 。妻尺扛- 反。l = l k = l 其中r 是方程羅x a i = 0 的最小非負解。 ，鼠1 分別是。面l - m ) x ( m 1 - m ) 、( 聊l - m ) x m 階矩陣，b o 是m x ( m i m ) 階矩陣， 反l 、以一l 均為m 階方陣，且b 0 0 、b l l 、彳l 均為非奇異矩陣，聊l m ，k = 1 ，2 ，。 類似于n e u t s 3 5 ( 1 9 8 1 ) 關于離散時間馬氏鏈的引理1 5 。1 和定理1 5 1 ，并采 用類似于定理1 7 1 的證明，我們有下面兩個定理。 定理2 3 1 若印( r ) 1 ，貝l j m ，階方陣研r 】為一生成子。 定理2 3 2 不可約馬氏過程q 是正常返的充要條件為印( r ) 0 ，使得 也 ) l a 色； 磊4 4 ；歷屆歷歷； m o 加 m 踟耶勵踟； 2 預備結論 碩士論文 ( r o ，彳1 ) b 【r 】= 0 此時q 有平穩(wěn)向量( k ，x l ，x l r ，x l r 2 ，) ，且k e ( 塒r 冊) + 置( i - r ) e m = 1 。 我們記e ，= ( 1 ，l ，1 ) r 為i 維列向量，f - 1 , 2 ， 令a = ya ，朋維行向量7 滿足： n a = o ：茄。：1 ，顯然向量萬、矩陣r 均與馬氏過程q 的邊界條件有關，從而， 由n e u t s 3 5 ( 1 9 8 1 ) 的定理3 1 1 有： 定理2 3 3 擬生滅過程( q b d ) q = 若a = a o + 4 + 么2 不可約，則印( 固 1 ，的充要條件為z a o 口腫 鵬p 朋。 2 4m i m l l j m m 1 的討論 假設隨機服務系統(tǒng)是由兩個串聯(lián)的等待制服務臺構成，顧客輸入是參數(shù)為名 的泊松流，顧客到達后在i 級服務臺接受服務，然后進入i i 級服務臺等待接受服 務，在i i 級服務臺服務完后顧客離開系統(tǒng)。兩個服務臺的服務時間分別是參數(shù)為 “，鸕的負指數(shù)分布，而且兩個服務臺的服務時間和到達時間間隔是相互獨立的。 設隨機服務系統(tǒng)在時刻t 的狀態(tài)為n ( t ) = 似力，若此時i 級服務臺前等待的 顧客數(shù)和正在被服務的顧客數(shù)之和為i ，i i 級服務臺前等待的顧客數(shù)和正在被服 務的顧客數(shù)之和為j ，狀態(tài)空間為 ( f ，) ，i ，j = o ，1 ，) ，令 p ( i ，f i t ) = p n ( t ) = ( f ，) ) 容易證明n ( t ) 為一馬爾科夫過程，利用馬爾科夫的極限定理，可以得到 l i m p ( i , j ；t ) = p g ) 是存在的，且與初始條件無關。 定理2 4 1 統(tǒng)計平衡下，兩個等待空間為無限的串聯(lián)排隊系統(tǒng)i 級服務臺 前等待的顧客數(shù)和正在被服務的顧客數(shù)之和為i ，i i 級服務臺等待的顧客數(shù)和正 在被服務的顧客數(shù)之和為j 的平穩(wěn)概率為 p ( i ，) = ( 1 一p 1 ) ( 1 一島) 爿 其中序：三且辟 0 ，使得 x a = o ，石= 1 定理3 3 1系統(tǒng)m “) l m i c 專m 7 i i i k 的狀態(tài)過程q 是正常返的充要條件為 萬a e 刀4 e ， 其中p 為p 砌的略寫， 證明：設 勾階方陣r 為方程y 2 4 十m + 以= 0 的最小非負解， es p ( r ) l 時， 為一生成子 又矩陣 玩。1 罵。+ 鮑j 為不可約矩陣，矩陣月及4 均為非負矩陣，故研r 】為不可約的。因而存在正向 似忸 ，。l = 1 j 足 口 形 | 論義 m “) m c m “9 i k 排隊系統(tǒng)概率分析 蜓jz i ( 餼，x ) ，使( x o ，x i ) 研尺】2 0 。由定理2 2 2 、定理2 2 3 即得證。 推論1系統(tǒng)肘( j m c 一m 7 i i l k 的狀念過程是f 常返的充要條件是 p 0 滿足萬o b = o ，萬o = 1 ，其中b = 研+ 毯+ 名， 則系統(tǒng)m ( 。m c 一m ( 7 ) i i l k 的狀態(tài)過程q 是正常返的充要條件是： p y 萬? 證明：由于彳= 4 + 4 + 4 ，將其代入我們得到 b p + j l p n i q 黿。+ 名所一l 九p n 2 i q 2 p l l q a = 五 + + 耳“a p 。a p ： 黿。耳。 名p 。 砭。耳。 2 p , i q 即+ 九p n l q 硅+ a 肌一l 九p iq oo 九p 2 i q 久p l l q 畔+ 九p n l q 九p i l 3 厶 a p n l 五p _ 2 九p n - 3 l q 硅。+ 見肌一l 2 p u 一2 2 p 一3 j 耳“+ 2 p 1 9 孵 h = 、，伍 e 中其 0 o o ；臥 一 一 一； 一 0 o 臥；oo肌趾；o詈趾跏；o 9 q q q硝蛄； q ； 鏟 明 鏟； ” 0 0 0 0 m m m 祥 驢 鏟； 0 0 0 0 x x 吣崢；岫 3m ( x ) m c m “ i k 排隊系統(tǒng)概率分析 碩士論文 其中 所以 ( 萬。萬o ，萬o ) 彳= ( 口，口，口) 。 k 。 口= 刀。( 硝“+ 2 p + 黿。+ 兄肌一l 厶+ 2 p 一2 + + 2 p l 厶) = 萬o 廚+ 硅+ 2 ( p i + p 2 + + p ) 厶】 - n o ( 科+ 黿。+ 名厶) = 萬o b = o 所以( n o , 萬o ，萬o ) 彳= 0 、。i _ 。、，。， ， 從而畝協(xié)。，萬。，力。) 為矩陣a 的左平穩(wěn)概率向量，由定理1 有： q 正常返 營專( 萬。，萬。，刀。) 4 口 專( 礦，礦，萬。) 鳴e ( 萬o ，萬o ，萬o ) a o e ( 萬o ，刀o ，萬o ) 鳴e 營名城 c 朋礦 p 群 結論比較直觀，我們知道在系統(tǒng)m ( 。m c 寸i m ( 7 1 k 中，去掉i i 級服務系統(tǒng)， 即考慮排隊系統(tǒng)m ”m c ，由經(jīng)典排隊論知：p 1 即為排隊系統(tǒng)m ( 。i m i c 平 穩(wěn)的充要條件，從而對系統(tǒng)m 。) m c _ m l k ，平穩(wěn)的充要條件為：p 小 于一個小于1 的常數(shù)，這是很自然的。 3 4 平穩(wěn)隊長分布及其算法 由第三節(jié)的定理3 3 1 或者定理3 3 2 ，：芷n - a o e 萬4 p ，或p m ( 7 ) 1 k 平衡狀態(tài)下，i 級服務系統(tǒng)的 忙期9 的l s t + ( s ) = r ( b p + 名一五y ( 護( s ) ) ) 證明：由于c 個服務臺獨立工作，每個服務臺的服務時間相互獨立且都服從 參數(shù)為“的負指數(shù)分布，所以當c 個服務臺都進入工作時，這c 個服務臺可以看 成服務時間為m i p 哆 的一個服務臺，其中e 表示笫f 個服務臺的服務時間，由 指數(shù)分布的性質知： 靶啦 e ) 一r ( 1 ，c , u 1 ) i s ，s 一 這樣當c 個服務臺都進入工作時，i 級服務系統(tǒng)m 7 m c 可以看成m p m 1 系統(tǒng)。 對于m ( 。m c 來說。忙期由兩種不同的含義，第一種含義是：由一批( i 個) 顧客引出的忙期。它是指：系統(tǒng)本來處于閑期，從系統(tǒng)開始到達一批顧客時起一 直到系統(tǒng)中又沒有顧客時止這段時間，用 表示其長。o 是m ( 一m c 系統(tǒng)的 頌i ：淪義 m “) l m i c m c 7 ) i k 排隊系統(tǒng)概率分析 忙期，到達的i 個顧客分別記為4 ，4 ，4 。由于忙期與服務的順序無關，所以 在討論忙期時，有時依先來后服務的規(guī)則處理，l j i 】先為4 服務，然后為在服務a ， 期間到達的顧客( 這些顧客可以視為a 。的第一代“子女) 服務，然后為a ，的第 一代“子女”服務期問到達的顧客( 這些顧客可以視為a 的第二代“子女”) 服 務，如此等等，當a 。及其各代“子女 都服務完時，再為4 及其各代“子女” 服務，以此類推。由此又引出第二種忙期，它是指：從開始為一個顧客服務時起 一直到該顧客以及各代“子女都服務完時止這段時間，用0 表示其長。 用礦( j ) ， ( s ) 表示0 ， 的l s t ，有： = 島 其中日，0 2 ，繡，相互獨立且均與0 同分布，從而有 o 0 ) = x o o ) 】( 其中x ( z ) 為x 的p g f ) 又 0 = b + o l + 0 2 + + o ( 歷， = u + o i + 2 + + ( u ) 其中 。， ：，o ，相互獨立均與。同分布，u = 馬，馬，b 2 ，島，相互獨立均與 i = 1 b 同分布，( 功為在占中到達的批數(shù)所以有 口+ 0 ) = e 一卵) = e e 一。b + e l + e 2 + 。+ 。川j ，1 ) = f e - e p 一5 m l + 咿伯蒯) 咖 召 ，) = f p 一耐蘭e 和叫肼q + 島+ + 們1in ( t ) ：硒p p ) = 后 劫 曰 吩 = p 鼢叫吣+ e 2 + + 剛，警p 礎擲叫 = p 驢 等p 確椰叫 = c 0 8 一e - 耐o ) 1 f d p b m i c 寸膨( ，l 五系統(tǒng)，我們定義從某批顧客到 達i 級服務系統(tǒng)開始，到該批第一個顧客接受服務這期間的時間為第一類成批等 待時間。 3 7 1 先到先服務規(guī)則的第一類成批等待時間 對于m