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

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