（應(yīng)用數(shù)學(xué)專業(yè)論文）mxmc→mmnk串聯(lián)排隊(duì)系統(tǒng)分析.pdf

碩十論文 m 。i m c 一( m ) m n l k 串聯(lián)排隊(duì)系統(tǒng)分析 摘要 本文研究了含特殊類顧客的m ( 曲m c 一( m ) im 刀k 有限容量的串聯(lián)排隊(duì)系 統(tǒng)，這一模型在銀行排隊(duì)服務(wù)系統(tǒng)、公共服務(wù)系統(tǒng)、通訊問題、計(jì)算機(jī)配置問題等方面 有著廣泛的應(yīng)用。 本文共分四章，第一章簡(jiǎn)要介紹了排隊(duì)論的發(fā)展進(jìn)程、串聯(lián)排隊(duì)模型和成批到達(dá)排 隊(duì)系統(tǒng)的背景、研究歷程等相關(guān)內(nèi)容，同時(shí)還闡明本論文模型的基本內(nèi)容和主要指標(biāo)的 計(jì)算。第二章給出了本論文所需要的理論知識(shí)和基本方法。第三章是在經(jīng)典的模型 m m 1jm m 1 的基礎(chǔ)上，添加了批量到達(dá)、特殊類顧客到達(dá)，即模型 m “m cj ( m ) m 療k 。本章用矩陣幾何分析的方法得出了系統(tǒng)模型的q 一矩陣， 運(yùn)用擬生滅過程的方法給出了系統(tǒng)平穩(wěn)的充要條件、平穩(wěn)隊(duì)長(zhǎng)分布及其算法，i 級(jí)服務(wù) 系統(tǒng)的忙期分布及其在忙期內(nèi)服務(wù)完的顧客數(shù)的概率母函數(shù)，i 級(jí)服務(wù)系統(tǒng)受阻時(shí)間分 布的拉普拉斯一司蒂階變換。 最后，第四章本章對(duì)本文所作的研究工作和取得的進(jìn)展，以及進(jìn)一步研究的方向作 一些簡(jiǎn)要的概述。 關(guān)鍵詞：串聯(lián)排隊(duì)系統(tǒng)，擬生滅過程，特殊服務(wù)，成批到達(dá)，矩陣幾何分析 a b s t r a c t n e 。s t a g et a n d e mq u e u e i n gs y s t e m m j m c 專( m ) m ，z kw i t hs p e c i a l c u s t o m e r si sm a i n l ys t u d i e di nt h i sp a p e r t h et a n d e mq u e u e i n gs y s t e mi sw i d e l yu s e di i lt h e s e r v i c i n ga n dq u e u e i n gs y s t e mo fb a n k ， d e p l o y m e n tp r o b l e m sa n ds oo n p u b l i cs e r v i c es y s t e m ，t r a f f i cp r o b l e m s ，c o m p u t e r t h ew h o l et h e s i si n c l u d e sf o u rc h a p t e r s i nt h ef i r s tc h a p t e r ，t h ed e v e l o p m e n t h i s t o r ya n d s m t a so ft h eq u e u et h e o r y ，t h er e s e a r c hb a c k g r o u n do f t h et a n d e mq u e u em o d e la n dt h eq u e u e s y s t e mw h o s ec u s t u m e r sa r ea r r i v i n gi n b a t c h s i m u l t a n e o u s l yt h eb a s i cc o n t e n ta n dt h e p r i m a r yi n d e x e so ft h i sp a p e ra r ep r e s e n t e d i nt h es e c o n dc h a p t e r , t h eb a s i so ft h e o r e t i c a l k n o w l e d g eo ft h eq u e u et h e o r yi si n t r o d u c e dw h i c hw o u l db eu s e di nt h i s p a p e r i nt h e 恤d c h a p t e r ，a r r i v i n gi nb a t c ha n ds p e c i a ls e r v i c eo ft h es p e c i a lc u s t o m e r sa r ea d d e di nt h ea u e u e s y s t e mm i m 1 寸m m 1 ，n a m e l ym x m c _ ( m ) m 刀k i nt h i sc h 印t e lt h e t r a n s f e r r i n gp r o b a b i l i t ym a t r i xo ft h et a n d e mq u e u e i n gs y s t e mi s p r e s e n t e db ym e a n so f m a t n xa n a l y s i st h e o r y t h e s 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 ya r c p r e s e n t e db yq u a s i _ b i r t h - d e a t h p r o c e s st h e o r y a n dt h ed i s t r i b u t i o no f s t a t i o n a r yq u e u el e n g t h a n di t sa l g o r i t h ma r eo b t a i n e d t h eb u s yt i m ed i s t r i b u t i o no ft h e s t a g e i ，t h ep r o b a b i l i t y g e n e r a lf u n c t i o no ft h en u m b e ro fc u s t o m e r ss e r v e r e di nb u s yt i m eo ft h es t a g e ia 】o b t a i n e d b ym e a n so ft h ei m b e d d e dm a r k o vc h a i n a n dt h ed i s t r i b u t i o no f t h es t a g e is e r v i c eb l o c k e d t i m ei sf u r t h e ra n a l y z e d h a el a s tc h a p t e rp r o v i d e sa n a l y s i sa n ds u m m a r ya b o u tt h e r e s e a r c hs u b je c ta n dr e s e a r c h p r o g r e s s i na d d i t i o n ，t h ef u r t h e rr e s e a r c hd i r e c t i o n sa r es u g g e s t e d k e yw o r d s ：t h er a n d e mq u e u e i n g ，q u a s i - b i r t h d e a t h p r o c e s s ，a r r i v i n gi nb a t c l l ，s p e c i a l s e r v i c e ，m a t r t i x - g e m e t r i cs o l u t i o n s 聲明尸i j j 了 本學(xué)位論文是我在導(dǎo)師的指導(dǎo)下取得的研究成果，盡我所知，在 本學(xué)位論文中，除了加以標(biāo)注和致謝的部分外，不包含其他人已經(jīng)發(fā) 表或公布過的研究成果，也不包含我為獲得任何教育機(jī)構(gòu)的學(xué)位或?qū)W 歷而使用過的材料。與我一同工作的同事對(duì)本學(xué)位論文做出的貢獻(xiàn)均 已在論文中作了明確的說明。 研究生簽名：0 咖年多月矽日 學(xué)位論文使用授權(quán)聲明 南京理工大學(xué)有權(quán)保存本學(xué)位論文的電子和紙質(zhì)文檔，可以借閱 或上網(wǎng)公布本學(xué)位論文的部分或全部?jī)?nèi)容，可以向有關(guān)部門或機(jī)構(gòu)送 交并授權(quán)其保存、借閱或上網(wǎng)公布本學(xué)位論文的部分或全部?jī)?nèi)容。對(duì) 于保密論文，按保密的有關(guān)規(guī)定和程序處理。 研究生簽名：_ 氫險(xiǎn)盈 一 少盧年6 月杉日 碩士論文 m m c 一( m ) m n k 串聯(lián)排隊(duì)系統(tǒng)分析 第一章引言 本章簡(jiǎn)要地介紹排隊(duì)論的發(fā)展進(jìn)程及應(yīng)用、串聯(lián)排隊(duì)模型和成批到達(dá)排隊(duì)系統(tǒng)的背 景、研究歷程等相關(guān)內(nèi)容，同時(shí)還闡明本論文模型的基本內(nèi)容和主要指標(biāo)的計(jì)算。 1 1 排隊(duì)論發(fā)展進(jìn)程 排隊(duì)論是具有特殊實(shí)際價(jià)值的現(xiàn)代應(yīng)用數(shù)學(xué)分支之一，是集概率論、數(shù)理統(tǒng)計(jì)、隨 機(jī)過程之一體，成功地解決現(xiàn)實(shí)生活中形形色色的實(shí)際問題的面鏡子。它是運(yùn)籌學(xué)中 內(nèi)容異常豐富的一個(gè)精華部分；是研究系統(tǒng)受隨機(jī)因素的影響而產(chǎn)生排隊(duì)現(xiàn)象，進(jìn)而揭 示其概率規(guī)律性的一門科學(xué)。 自從19 0 9 年丹麥電話工程師愛爾朗( 么k e r l a n g ) 的開創(chuàng)性論文“概率論和電話通 話”發(fā)表以來，愛爾朗創(chuàng)立了一套關(guān)于隨機(jī)過程方面的理論，進(jìn)而以“排隊(duì)論”命名的 一門新的學(xué)科誕生了。2 0 世紀(jì)3 0 年代中期，費(fèi)勒f 形f e l l e r ) 把生滅過程引進(jìn)排隊(duì)論之 時(shí)，數(shù)學(xué)界才把排隊(duì)論認(rèn)同是一門重要學(xué)科。在第二次大戰(zhàn)以前，其研究多側(cè)重于電話 與遠(yuǎn)距離通信方面，發(fā)展也比較緩慢；但二戰(zhàn)以后，排隊(duì)論滲透到軍事、經(jīng)濟(jì)、生產(chǎn)與 服務(wù)等多種部門，它的理論和應(yīng)用得到了快速地發(fā)展，迅速成為了運(yùn)籌學(xué)和管理學(xué)的一 個(gè)熱門分支。2 0 世紀(jì)5 0 年代初，英國(guó)學(xué)者肯德爾( d g k e n d a l l ) 引入了嵌入馬爾科夫鏈 的方法，成為研究排隊(duì)理論的經(jīng)典方法。 7 0 年代以來，隨著電子計(jì)算機(jī)的不斷更新與發(fā)展，通信網(wǎng)的建立與完善，信息科學(xué)、 生命科學(xué)及控制理論的蓬勃發(fā)展，在許多場(chǎng)合下所涉及到的最優(yōu)設(shè)計(jì)與最佳服務(wù)問題均 構(gòu)成了排隊(duì)問題。對(duì)這些問題的行為分析、統(tǒng)計(jì)分析、運(yùn)行分析、計(jì)算機(jī)仿真，使排隊(duì) 理論與應(yīng)用獲得了質(zhì)和量上的飛速發(fā)展。 排隊(duì)論是研究服務(wù)過程的概率特性的數(shù)學(xué)理論。在各個(gè)領(lǐng)域內(nèi)，排隊(duì)內(nèi)容雖然不同， 但是排隊(duì)過程都可以由三個(gè)特征來定義：輸入過程、服務(wù)過程、排隊(duì)規(guī)則。 ( 1 ) 輸入過程：描述有關(guān)服務(wù)請(qǐng)求的序列，在一般情況下，輸入過程即為由顧客 相繼到達(dá)的時(shí)刻之間的間隔分布束確定的。 ( 2 ) 服務(wù)過程：具有服務(wù)臺(tái)的數(shù)量以及顧客占用服務(wù)臺(tái)的服務(wù)時(shí)間長(zhǎng)度等特征。 譬如：顧客可以由單個(gè)服務(wù)設(shè)備處理( 單服務(wù)臺(tái)) ，亦可以由有限個(gè)服務(wù)臺(tái) 或無限個(gè)服務(wù)臺(tái)處理。每個(gè)顧客占用服務(wù)設(shè)備或被服務(wù)的時(shí)間可以是相同的 時(shí)長(zhǎng)( 即定長(zhǎng)時(shí)間) ，服務(wù)時(shí)間亦可以具有指數(shù)分布、幾何分布、一般分布 世 寸o ( 3 )排隊(duì)規(guī)則：確定對(duì)阻塞顧客的安排( 當(dāng)顧客發(fā)現(xiàn)所有服務(wù)設(shè)備全忙時(shí)) ，例 如它可以假設(shè)被阻塞顧客立即離丌系統(tǒng)，或被阻塞顧客在一個(gè)隊(duì)列內(nèi)等待服 第一章引言碩f ：論文 務(wù)并且按照f c f s ( 先到先服務(wù)) 方式給予服務(wù)。故排隊(duì)規(guī)則可以分為三種 制式：即等待制、損失制和混合制。 對(duì)于一個(gè)排隊(duì)系統(tǒng)，主要以顧客和服務(wù)機(jī)構(gòu)兩方面的利益來權(quán)衡它的好壞。一方面， 就顧客利益來說，他們總是希望等待時(shí)間或是逗留時(shí)間越短越好，即要求服務(wù)臺(tái)的個(gè)數(shù) 盡可能多些；另一方面，對(duì)于服務(wù)機(jī)構(gòu)來說，服務(wù)臺(tái)個(gè)數(shù)的增加就意味著增加投資，勢(shì) 必會(huì)對(duì)服務(wù)機(jī)構(gòu)的利潤(rùn)產(chǎn)生影響。因此，排隊(duì)論的主要內(nèi)容，就是要研究排隊(duì)系統(tǒng)的以 下幾個(gè)指標(biāo)：系統(tǒng)隊(duì)長(zhǎng)、顧客的等待時(shí)間、服務(wù)臺(tái)的忙期長(zhǎng)度等指標(biāo)。對(duì)于經(jīng)典的排隊(duì) 論研究主要有以下幾種常用的方法：嵌入馬爾可夫法、補(bǔ)充變量法、擬生滅過程理論、 半馬爾可夫過程理論，還有國(guó)內(nèi)侯振挺教授提出的馬氏骨架方法、國(guó)外b r i l l 教授提出 的水平穿越方法等。 1 2 排隊(duì)論的應(yīng)用問題 排隊(duì)論應(yīng)用的具體案例不勝枚舉，主要應(yīng)用在如下幾個(gè)方面。 ( 1 ) 通訊問題 電話交換機(jī)通常僅由有限條電話線供用戶通話，如果在某一時(shí)刻所有的電話線均被 占用，那么新的用戶就必須等到有一條線路空下來才能通話，此時(shí)用戶對(duì)電話線的使用 就是排隊(duì)問題，電話線為服務(wù)臺(tái)，用戶占用電話線的時(shí)間為服務(wù)時(shí)間，而一般情況下， 使用電話線的排列規(guī)則為“先到先占”。在人造衛(wèi)星通訊方面，通訊衛(wèi)星是服務(wù)臺(tái)，地 面上通訊站的使用要求可以視為顧客的到達(dá)，服務(wù)時(shí)間依據(jù)通訊站發(fā)射訊息的長(zhǎng)度和衛(wèi) 星轉(zhuǎn)播訊息的時(shí)間而定，排隊(duì)規(guī)則可以是先到先占或者是用戶依次輪流使用。 ( 2 ) 公共服務(wù)問題 許多公共服務(wù)事業(yè)對(duì)群眾提供依次服務(wù)、群眾對(duì)公共服務(wù)設(shè)施的使用情況也可以納 入排隊(duì)問題。例如在銀行、郵局，他們的的服務(wù)人員可以看作服務(wù)臺(tái)，在醫(yī)院，病床可 以看作服務(wù)臺(tái)，他們的服務(wù)時(shí)間和到達(dá)顧客則與實(shí)際的情況完全一致，一般情況下排隊(duì) 規(guī)則均為先到先服務(wù)，但是在某些場(chǎng)合下也可以有優(yōu)先權(quán)的出現(xiàn)，例如病危的患者就有 優(yōu)先占用空閑病床的權(quán)利。 ( 3 ) 救護(hù)，公安服務(wù)系統(tǒng) 警察、消防人員、消防車、醫(yī)院的救護(hù)車均可以當(dāng)作服務(wù)臺(tái)，緊急事故的發(fā)生可視 為顧客的到達(dá)，通常這類問題都要求極低的服務(wù)臺(tái)使用率，因而當(dāng)一件緊急事故發(fā)生時(shí) 有足夠的應(yīng)付能力。 ( 4 ) 存量問題 儲(chǔ)存系統(tǒng)中存量變化的隨機(jī)行為和排隊(duì)論中的隊(duì)長(zhǎng)變化的隨機(jī)行為有相似的地方。 一般情況下商店進(jìn)貨的策略是根據(jù)貨物銷售情況來決定的，商店一方面力求減輕存貨的 壓積；另一方面要想方設(shè)法地滿足顧客的需求。圖書館根據(jù)藏書庫的容量及書籍的使用 2 碩：l ：論文 m i m c 斗( m ) m 一k 串聯(lián)排隊(duì)系統(tǒng)分析 率來淘汰無用的舊書；水庫管理部門需要制定放水的策略，一方面提供發(fā)電，灌溉的需 要；另一方面要盡量把水源枯竭、由于連續(xù)暴雨而造成的積水過多，這兩種情形的發(fā)生 率減至最低。 ( 5 ) 生產(chǎn)流水線問題 在工廠生產(chǎn)流水線上，為了保證生產(chǎn)線的水平，必須合理安排機(jī)器、工人及物料運(yùn) 輸設(shè)備，降低生產(chǎn)過程中原料和半成品的存量，往往也可以通過對(duì)相應(yīng)排隊(duì)問題的研究 來獲得解決。在這類問題里，顧客為工廠的產(chǎn)品，機(jī)器、工人及有關(guān)生產(chǎn)和運(yùn)輸設(shè)備可 視為服務(wù)臺(tái)。 ( 6 ) 計(jì)算機(jī)的配置問題 計(jì)算機(jī)內(nèi)部的中央處理機(jī)、輸入和輸出設(shè)備可以看作服務(wù)臺(tái)，顧客則為計(jì)算機(jī)程序， 在計(jì)算機(jī)網(wǎng)絡(luò)問題里，計(jì)算機(jī)本身也可以當(dāng)作服務(wù)臺(tái)，計(jì)算機(jī)程序或指令通過網(wǎng)絡(luò)可由 個(gè)計(jì)算機(jī)傳送至另一計(jì)算機(jī)，這類問題通常都以網(wǎng)絡(luò)隊(duì)列形式出現(xiàn)。 排隊(duì)論的應(yīng)用遠(yuǎn)不止上述的幾種。有些時(shí)候在一個(gè)排隊(duì)問題里，顧客和服務(wù)臺(tái)也并 不是一成不變，甚至可以互相顛倒。例如：有時(shí)出租車排隊(duì)等候乘客，而有時(shí)乘客也排 隊(duì)等侯出租車，汽車駕駛員和乘客都關(guān)心自己的等待時(shí)間而相互以對(duì)方為服務(wù)臺(tái)。因此 在排隊(duì)系統(tǒng)中，如何決定何者為顧客、何者為服務(wù)臺(tái)，通常是看問題的性質(zhì)或者如何方 便j 。能地解決問題。排隊(duì)論運(yùn)用起來是非常靈活的；此外排隊(duì)論使用的模型和其它數(shù)學(xué) 模型一樣，模型本身只是現(xiàn)實(shí)問題的一個(gè)數(shù)學(xué)表示方法，因而永遠(yuǎn)不能代表實(shí)際本身， 排隊(duì)模型的解也總是一個(gè)對(duì)實(shí)際問題的近似。因此數(shù)學(xué)模型提供給我們的是一個(gè)客觀的 理論根據(jù)，在數(shù)學(xué)模型的解加上，人們能夠?qū)?yīng)地作出正確的判斷才是明智的決策。 1 3 串聯(lián)排隊(duì)網(wǎng)絡(luò)系統(tǒng)的研究 一個(gè)排隊(duì)網(wǎng)絡(luò)是由多個(gè)服務(wù)設(shè)備組成的一個(gè)系統(tǒng)，在系統(tǒng)中的顧客可以屬于不同的 類別，他們除了可以有不同的服務(wù)時(shí)間分布外，還可以在服務(wù)臺(tái)之間相互轉(zhuǎn)移，并且可 以有不同路徑的轉(zhuǎn)移概率。排隊(duì)網(wǎng)絡(luò)按照客源的情況，可以分為下面三類：開網(wǎng)、閉網(wǎng) 以及混合網(wǎng)絡(luò)。在一個(gè)開排隊(duì)網(wǎng)絡(luò)中，顧客從外面到達(dá)網(wǎng)絡(luò)，并最終離開網(wǎng)絡(luò)：在一個(gè) 閉排隊(duì)網(wǎng)絡(luò)中，顧客在服務(wù)臺(tái)之間循環(huán)，無顧客到達(dá)和離開；在一個(gè)混合排隊(duì)網(wǎng)絡(luò)中， 有一些顧客類相對(duì)于網(wǎng)絡(luò)是丌的，而另一些顧客類相對(duì)于網(wǎng)絡(luò)是閉的。另外，按照網(wǎng)絡(luò) 狀態(tài)過程描述的情況，又可以分為m a r k o v 型的和非m a r k o v 型的。 在排隊(duì)論里有關(guān)網(wǎng)絡(luò)的研究晟早見之于1 9 5 7 年杰克遜所發(fā)表的論文，在這篇文章 里，網(wǎng)絡(luò)本身包括有m 個(gè)服務(wù)站，其中每個(gè)服務(wù)站有一定個(gè)數(shù)的相同服務(wù)臺(tái)，但是每 個(gè)服務(wù)臺(tái)都具有指數(shù)分布的服務(wù)時(shí)間，顧客到達(dá)網(wǎng)絡(luò)依循參數(shù)為a 的p o s s i o n 流，各服 務(wù)站的外部輸入與各服務(wù)時(shí)間相互獨(dú)立。進(jìn)入服務(wù)站i 的概率為a ，當(dāng)顧客在服務(wù)站f 完 成服務(wù)后可以加入隊(duì)列，也可以離開服務(wù)系統(tǒng)。而q ，= l 一 ：p 。就是離開服務(wù)系統(tǒng)的 _ - v j 3 第一章引言 碩士論文 概率。在開放網(wǎng)絡(luò)里，由于各個(gè)隊(duì)列的長(zhǎng)度是相互獨(dú)立的，故容易證明網(wǎng)絡(luò)的平穩(wěn)分布 等于各服務(wù)點(diǎn)平穩(wěn)分布的乘積。假如在j a c k s o n 開網(wǎng)絡(luò)中，顧客既不能由外界到達(dá)，也 不能離開到別處去，而其顧客在網(wǎng)絡(luò)上的總數(shù)為一常數(shù)，則稱為指數(shù)閉網(wǎng)絡(luò)，或稱 j a c k s o n 閉網(wǎng)絡(luò)。由于在密閉的網(wǎng)絡(luò)里，顧客的總數(shù)為固定的，因此隊(duì)列長(zhǎng)度不是互 相獨(dú)立的。雖然可以先求出各個(gè)隊(duì)列的邊際分布，但是由于各分布并非是互相獨(dú)立的， 因此聯(lián)合分布不能用此方法得到。但是我們可以通過假設(shè)將閉網(wǎng)絡(luò)改為一個(gè)開放的網(wǎng) 絡(luò)，進(jìn)而求解得出其平穩(wěn)分布仍為一乘積型的。 那么非指數(shù)網(wǎng)絡(luò)是否也具有乘積型的解? 許多學(xué)者作了研究。如：m u n t z ( 1 9 7 2 ) 、 b a s k e t t ( 1 9 7 5 ) 、c h a n d y ( 1 9 7 7 ) 、n o e t z e t ( 1 9 7 9 ) 等對(duì)在不同的服務(wù)時(shí)間分布、不同的服 務(wù)規(guī)則下的網(wǎng)絡(luò)排隊(duì)作了詳細(xì)的研究，得出非指數(shù)網(wǎng)絡(luò)排隊(duì)的平穩(wěn)分布仍具有乘積型 解。另外l l y ( 1 9 7 6 ) 與b a r b o u r ( 1 9 7 6 ) 研究了有多種排隊(duì)規(guī)則在內(nèi)的多種種類顧客、 一般服務(wù)分布的排隊(duì)網(wǎng)絡(luò)，巧妙地運(yùn)用可逆性得出了一種乘積型解。 串聯(lián)排隊(duì)網(wǎng)絡(luò)系統(tǒng)是模擬交通運(yùn)輸、計(jì)算機(jī)網(wǎng)絡(luò)的一個(gè)很好的數(shù)字化模型。因此， 對(duì)于串聯(lián)排隊(duì)的理論與應(yīng)用的研究是非常重要的。簡(jiǎn)單地說，在醫(yī)院看病，需經(jīng)掛號(hào)、 候診看病、檢查( 拍片、抽血、驗(yàn)?zāi)虻? ，劃價(jià)、交費(fèi)、取藥等一系列窗口；大學(xué)新生 入學(xué)，需辦理注冊(cè)、戶口、住宿、圖書證等一系列手續(xù)等均屬于串聯(lián)排隊(duì)模型。在國(guó)外 m a n d j e s ，m a n n e r s a l & n o r r o s 4 3 ( 2 0 0 7 ) 研究了高斯輸入( g a u s s i a n ) 的兩級(jí)串聯(lián)排隊(duì) 網(wǎng)絡(luò)，并且兩隊(duì)列以常數(shù)c i ，江1 ，2 ，( c l c 2 ) 的概率服務(wù)，得出了平穩(wěn)隊(duì)長(zhǎng)的分布。 b o x m a 1 8 1 研究了兩級(jí)串聯(lián)排隊(duì)系統(tǒng)，且i 級(jí)服務(wù)臺(tái)的服務(wù)時(shí)間是同分布的，得出了串 聯(lián)系統(tǒng)平穩(wěn)的充要條件、等待時(shí)間的分布，以及在i i 級(jí)服務(wù)系統(tǒng)逗留時(shí)間、等待時(shí)間分 布的精確表達(dá)式。m i t c h e l l ，v a n d el i e f v o o r t 3 6 ( 2 0 0 3 1 考慮了g g 1 型的串聯(lián)排隊(duì) 網(wǎng)絡(luò)，該文章通過分析每個(gè)隊(duì)列變化的特征及損失概率分布得出了離去過程的一種近似 模型。m o r r i s o n 3 7 1 & b o x m a ( 1 9 7 9 ) 4 1 1 分別研究了獨(dú)立的p o s s i o n 流與b e r n o u l l i 到達(dá)過 程的串聯(lián)排隊(duì)系統(tǒng)，這種假設(shè)對(duì)交通排隊(duì)網(wǎng)絡(luò)非常適用；d a d u n a ( 1 9 9 7 ) 3 8 1 探討了狀態(tài) 獨(dú)立的b e r n o u l l i 到達(dá)過程的串聯(lián)排隊(duì)系統(tǒng)，服務(wù)時(shí)間遵循不同參數(shù)的幾何分布，得出了 隊(duì)長(zhǎng)的聯(lián)合分布及等待時(shí)間分布。 對(duì)于有限容量的串聯(lián)排隊(duì)網(wǎng)絡(luò)系統(tǒng)，在數(shù)據(jù)傳輸、生產(chǎn)線等模型中應(yīng)用非常廣泛 的。早在二十世紀(jì)六十年代，就有許多學(xué)者對(duì)有阻塞的排隊(duì)網(wǎng)絡(luò)作了簡(jiǎn)要的研究。 a v i l t z h a k & y a d i n 2 9 1 和s u z u k i 2 1 1 考慮了泊松流( p o s s i o n ) 到達(dá)、一般服務(wù)時(shí)間的兩 級(jí)串聯(lián)排隊(duì)，并得出了等待時(shí)間的表達(dá)式。p r a b h u 2 2 1 分析了文獻(xiàn)f 2 1 ，2 9 1 中模型的隨 機(jī)過程的一些瞬時(shí)結(jié)果。近來l a n g a r i s 2 3 1 假設(shè)i i 級(jí)服務(wù)系統(tǒng)具有伽馬分布輸入、服務(wù) 時(shí)間服從伽馬分布的情況下，也得出了一些相似的結(jié)果，相關(guān)的結(jié)果還可參照文獻(xiàn) 1 2 9 ，3 0 ，3 1 3 2 1 。此外還有學(xué)者運(yùn)用逼近的方法研究有限容量的串聯(lián)排隊(duì)系統(tǒng)，并求出了 系統(tǒng)指標(biāo)的近似數(shù)值解。如：a 1 t i o k f 4 0 1 、b r a n d w a i n & j o w 4 4 1 、g e r s h w i n 4 8 1 、 4 碩上論文 m i m i c - - ( m i i m i n l k 串聯(lián)排隊(duì)系統(tǒng)分析 h i l l i e r & b o l i n g ( 1 9 6 7 ) 4 6 1 。但是，關(guān)于有限容量的串聯(lián)排隊(duì)網(wǎng)絡(luò)系統(tǒng)指標(biāo)的精確求解 方面的工作不多，而且大多考慮比較簡(jiǎn)單的系統(tǒng)，如：k o n l e i m & r e i s e r ( 1 9 7 6 ) 1 5 5 l 考慮 了系統(tǒng)m m 1 - - - m 1 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 1 用矩陣分析理論給出了系統(tǒng)m m ，一m c k 的平穩(wěn)隊(duì) 長(zhǎng)分布。此后月a 刀& s r i s k a n d a r a j a h 2 8 1 對(duì)有阻塞、無等待空間的串聯(lián)排隊(duì)系統(tǒng)作了詳細(xì) 的研究( 此類機(jī)制排隊(duì)模型的相關(guān)文獻(xiàn)，可參看p e r r o s l 3 9 i 和p e r r o s & a l t i o k l 3 5 1 ) 。 g e m e z c o r r a l 1 9 1 在2 0 0 2 年研究了i 級(jí)服務(wù)系統(tǒng)排隊(duì)等待空間無限、級(jí)服務(wù)系統(tǒng)沒有 排隊(duì)等待空間的串聯(lián)排隊(duì)模型，即m a p 尸日lj g 1 模型。只有在u 級(jí)服務(wù)系統(tǒng)把 服務(wù)臺(tái)前顧客服務(wù)完時(shí)，i 級(jí)服務(wù)系統(tǒng)服務(wù)完的顧客才可以到級(jí)服務(wù)系統(tǒng)要求服務(wù)， 顧客以馬爾可夫過程到達(dá)串聯(lián)系統(tǒng)，主要運(yùn)用了嵌入馬爾可夫鏈的方法、馬爾可夫更新 過程基本理論研究了該模型。k o n h e i m & r e 括e r 4 2 ，4 9 1 研究了有阻塞的串聯(lián)排隊(duì)系統(tǒng)， 他們把概率分布所滿足的平穩(wěn)方程通過z 變換，進(jìn)而研究了概率分布的母函數(shù)的一些性 質(zhì)，得出了模型穩(wěn)念存在的充要條件及計(jì)算概率分布的算法，另外l a t o u c h e & n e u t s1 5 6 l 運(yùn)用擬生滅過程的方法得出了這個(gè)模型以及相關(guān)模型的穩(wěn)態(tài)條件。 在國(guó)內(nèi)，賈波、周家良f 1 2 1 5 1 對(duì)串聯(lián)開排隊(duì)網(wǎng)絡(luò)作了詳細(xì)的研究，先后在串聯(lián)機(jī) 制中加入反饋、有限容量規(guī)則，富有技巧性地求得了多級(jí)串聯(lián)、串聯(lián)反饋、并聯(lián)排隊(duì)系 統(tǒng)的有關(guān)概率指標(biāo)，并給出了相應(yīng)的穩(wěn)態(tài)分布的顯式精確解及相關(guān)的指標(biāo)。聶盼紅 f 5 8 1 ( 2 0 0 4 1 在串聯(lián)開排隊(duì)網(wǎng)絡(luò)系統(tǒng)分析中，研究了兩級(jí)杰克遜j a c k s o n 串聯(lián)開排隊(duì)模型， 并給出了m 級(jí)j a c k s o n 串聯(lián)系統(tǒng)的平穩(wěn)隊(duì)長(zhǎng)分布，此外，該論文還研究了兩類有限容量 的級(jí)串聯(lián)開排隊(duì)系統(tǒng)，并分別給出了它們的穩(wěn)態(tài)結(jié)果及忙期分布。郭志芳1 5 9 i ( 2 0 0 6 ) 在級(jí)串聯(lián)開排隊(duì)系統(tǒng)網(wǎng)絡(luò)中，又添加了休假機(jī)制，并得出了穩(wěn)態(tài)隊(duì)長(zhǎng)、忙期長(zhǎng)度與逗 留時(shí)間分布，并進(jìn)行了計(jì)算機(jī)模擬與仿真。王松建( 2 0 0 7 ) 在級(jí)串聯(lián)丌排隊(duì)系統(tǒng)網(wǎng)絡(luò)中， 又分別添加了反饋規(guī)則、啟動(dòng)機(jī)制，在模型一中用矩陣分析方法，得出了系統(tǒng)穩(wěn)態(tài)解及 相關(guān)指標(biāo)；在模型二中運(yùn)用了遞推方法，亦求出了穩(wěn)態(tài)概率解，還得到了逗留時(shí)間、忙 期長(zhǎng)度分布。 1 4 成批到達(dá)的排隊(duì)系統(tǒng) 一 成批到達(dá)的排隊(duì)模型，在多姿多彩的現(xiàn)實(shí)世界中比比皆是。諸如：郵政中成袋的郵 件運(yùn)送、鐵路或海運(yùn)中的集裝箱運(yùn)轉(zhuǎn)、高樓電梯為人或貨物的運(yùn)行系統(tǒng)等都是成批到達(dá) 的排隊(duì)系統(tǒng)。 關(guān)于此類排隊(duì)系統(tǒng)的研究，在李建平的排隊(duì)論基礎(chǔ)一書中就有探討，書中主要介 紹了幾類批到達(dá)的排隊(duì)模型：彰m 1 、m s g 1 、g p g 1 ，用嵌入馬爾科夫鏈的 方法給出模型的平穩(wěn)分布、等待時(shí)間分布等；在國(guó)內(nèi)，研究的批量到達(dá)的串聯(lián)排隊(duì)系統(tǒng) 一般都是輸入過程是p o s s i o n 流到達(dá)、服務(wù)時(shí)間服從指數(shù)分布或p h 分布。如：蘇時(shí)光、 氣 第一章引言碩上論文 陳薇f 5 7 1 探討了有限容量的m 肘c 專p h 1 k 兩級(jí)串聯(lián)開排隊(duì)模型，得到了系統(tǒng)的 平穩(wěn)條件，并且用矩陣迭代法給出了平穩(wěn)隊(duì)長(zhǎng)分布和受阻概率的l s t 。徐光輝、袁學(xué)明 n 6 1 更為一般地研究了有限容量的成批到達(dá)、成批服務(wù)的兩級(jí)串聯(lián)排隊(duì)網(wǎng)絡(luò)模型，用矩 陣幾何解的方法對(duì)m 似) m c 專p h ( r ) 1 k 進(jìn)行了探討，得出了m a r k o v 過程的q 一矩 陣，給出了系統(tǒng)平穩(wěn)的充要條件、平穩(wěn)隊(duì)長(zhǎng)分布及其算法。 近年來，許多國(guó)外學(xué)者研究了批量馬爾可夫到達(dá)過程( b 心尸) 的串聯(lián)排隊(duì)系統(tǒng)，所 謂的b m a p 準(zhǔn)確地說包括多種輸入流，譬如：泊松流輸入( p o s s i o n ) 、愛爾朗輸入 ( e r l i n g ) 、高維的馬爾可夫輸入、朋型更新過程、馬爾可夫調(diào)制泊松流輸入f 腳p 1 等 等。對(duì)于b m a p 型輸入的串聯(lián)排隊(duì)，文獻(xiàn)1 9 ，2 7 ，5 0 一5 4 1 作了簡(jiǎn)要研究。其中b r e u e r 和 d “講胛1 5 0 l 于2 0 0 4 年研究了b m a p g 1 一朋1 m 一1 型有阻塞的串聯(lián)排隊(duì)系統(tǒng)， 分別給出了i 級(jí)服務(wù)系統(tǒng)等待空間在有限和無限兩種情況下，兩級(jí)系統(tǒng)的穩(wěn)態(tài)隊(duì)長(zhǎng)概率 分布，以及i 級(jí)服務(wù)系統(tǒng)的等待時(shí)間分布。k l i m e n o k & t a r a m i n 2 4 1 ( 2 0 0 7 ) 研究了有 損失制的兩級(jí)串聯(lián)系統(tǒng)，用嵌入馬爾科夫鏈的方法得出了系統(tǒng)的穩(wěn)態(tài)條件、穩(wěn)態(tài)分布， 探討了系統(tǒng)狀態(tài)過程在任意時(shí)刻的隊(duì)長(zhǎng)分布及其他相關(guān)指標(biāo)。2 0 1 0 年 k l i m e n o k & t a r a m i n 2 5 1 在【2 4 的基礎(chǔ)上，又將反饋機(jī)制加入了串聯(lián)排隊(duì)系統(tǒng)，相應(yīng)的 研究了q 一矩陣的正常返性、穩(wěn)態(tài)分布及相關(guān)指標(biāo)。c h es o o n gk i m 2 6 1 等人在2 0 0 6 年 研究了含反饋的b m a p g l 專朋1 m ( 批量馬爾可夫到達(dá)) 的串聯(lián)損失制排隊(duì)系 統(tǒng)，并給出了平穩(wěn)條件存在的充要條件、系統(tǒng)隊(duì)長(zhǎng)的概率分布、等待時(shí)間的分布。 c h es o o n gk i m 1 7 1 等人在2 0 1 0 年研究了含有優(yōu)先權(quán)顧客的和重試機(jī)制的有限容量的兩 級(jí)串聯(lián)系統(tǒng)，顧客以批量馬爾可夫過程到達(dá)( b 心尸) i 級(jí)服務(wù)系統(tǒng)，i 級(jí)服務(wù)系統(tǒng)的服務(wù) 時(shí)間服從一般分布，級(jí)服務(wù)系統(tǒng)服務(wù)時(shí)間服從p h 分布。即 b m a p g l 專跗1 m ，當(dāng)重試區(qū)域有f 個(gè)顧客時(shí)，重試時(shí)間遵循參數(shù)為鞏的指數(shù)分 布。該文還探討了當(dāng)i i 級(jí)服務(wù)系統(tǒng)中顧客數(shù)達(dá)到m 個(gè)時(shí)，經(jīng)i 級(jí)服務(wù)系統(tǒng)服務(wù)完的顧客 損失情況；考察了以i 級(jí)服務(wù)系統(tǒng)服務(wù)完成時(shí)刻為嵌入點(diǎn)的嵌入馬爾科夫鏈以及在任意 時(shí)刻系統(tǒng)狀態(tài)過程，研究了顧客直接進(jìn)入i 級(jí)服務(wù)系統(tǒng)并得到服務(wù)的概率、級(jí)服務(wù)系 統(tǒng)損失顧客的概率；此外還給出了模擬準(zhǔn)確的到達(dá)過程和服務(wù)過程的一個(gè)可行性的算 法。 最近，g o m e z c o r r a l 2 7 1 、m o w t z o u m s & l a n g a r i s 3 3 1 首次將重試排隊(duì)加入了串聯(lián) 排隊(duì)系統(tǒng)中，并作了簡(jiǎn)單的研究。其中g(shù) o m e z c o r r a l 2 7 1 在2 0 0 2 年研究了 m a p 尸h 1 斗p h l k + 1 重試串聯(lián)排隊(duì)模型，主要運(yùn)用了擬生滅過程方法，探討了 馬氏過程的無窮小生成元的正常返性，并用算法給出了一個(gè)近似解和一個(gè)修正的矩陣幾 何穩(wěn)態(tài)向量。m o w t z o u k i s & l a n g a r i s 3 3 1 研究了含有重試顧客的兩級(jí)串聯(lián)排隊(duì)模型，以 母函數(shù)的方式得到了系統(tǒng)穩(wěn)態(tài)概率分布及系統(tǒng)性能的一些相關(guān)的數(shù)字性結(jié)果，還討論了 在無重試情形下的一些結(jié)果，并以指數(shù)服務(wù)作為特例進(jìn)行了研究。c h es o o n gk i m 3 4 1 6 碩士論文 m m c 寸( m ) m i n l k 串聯(lián)排隊(duì)系統(tǒng)分析 等人在2 0 0 9 年又研究了含反饋的b m a p g 1 _ ( m a p ) i m c 的重試串聯(lián)排隊(duì)模型，這 種排隊(duì)模型在遠(yuǎn)程數(shù)據(jù)傳輸及銀行服務(wù)系統(tǒng)中的應(yīng)用非常廣泛，該文獻(xiàn)運(yùn)用嵌入馬爾科 夫鏈的方法求出了穩(wěn)態(tài)隊(duì)長(zhǎng)分布，馬氏鏈遍歷的充要條件及任意時(shí)刻的穩(wěn)態(tài)隊(duì)長(zhǎng)分布； 任意時(shí)刻i 級(jí)服務(wù)系統(tǒng)的平均顧客數(shù)，i 級(jí)服務(wù)系統(tǒng)忙著的服務(wù)臺(tái)數(shù)，優(yōu)先權(quán)顧客與無 優(yōu)先權(quán)顧客的損失率等相關(guān)指標(biāo)。 1 5 本文的主要研究?jī)?nèi)容 本文主要研究了含特殊類顧客的m o ) m c f m ) m 以k 有限容量的串聯(lián)排隊(duì) 模型，它是在經(jīng)典的m m 1jm m 1 的基礎(chǔ)上，在i i 級(jí)服務(wù)系統(tǒng)等待空間內(nèi)除了 i 級(jí)服務(wù)系統(tǒng)服務(wù)完的普通類顧客外，又添加了特殊類顧客的到達(dá)；將到達(dá)i 級(jí)服務(wù)系 統(tǒng)的普通類顧客改為成批到達(dá)，并且i 級(jí)、級(jí)服務(wù)系統(tǒng)各有c 、刀個(gè)并聯(lián)的服務(wù)臺(tái)，該 模型在分析公共服務(wù)排隊(duì)系統(tǒng)中有著直接的應(yīng)用日訂景。論文用矩陣幾何分析的方法得出 了系統(tǒng)模型的q 一矩陣，運(yùn)用擬生滅過程的方法給出了系統(tǒng)平穩(wěn)的充要條件、平穩(wěn)隊(duì)長(zhǎng) 分布及其算法，i 級(jí)服務(wù)系統(tǒng)的平均隊(duì)長(zhǎng)；另外，由模型的特征還求出了i 級(jí)服務(wù)系統(tǒng) 的忙期分布( l s t l 及其在忙期內(nèi)服務(wù)完的顧客數(shù)的p g f ，i 級(jí)服務(wù)系統(tǒng)受阻時(shí)間的l s t ( 或u 級(jí)服務(wù)系統(tǒng)的繁忙期) 。 7 第二章預(yù)備知識(shí)碩i ：論文 第二章預(yù)備知識(shí) 2 1 生滅過程 2 1 1 生滅過程的定義 設(shè) x ( ，) ，t o ) 為具有狀態(tài)空間，( 或如) 的連續(xù)參數(shù)齊次脅砌v 鏈，如果其轉(zhuǎn)移 概率矩陣尸( ，) = ( 島( 滿足： 對(duì)任意的i ，j ， i b ，f + l ( ，) = 4 t + d ( r ) ， i b f - l ( f ) = 鸕f + d ( f ) ， i 既( ，) = 1 一( 五+ 以) f + d ( f ) ， l p o , ( t ) = d ( ，) ， 則 x ( ，) ，r o ) 為生滅過程。 2 1 2 生滅過程的微分方程組 丑 0 1 a o = o ，當(dāng)f 1 時(shí)，鸕 0 1 2 0 = o ，i 0 i j - i i 2 如果系統(tǒng)在時(shí)刻f 處于狀態(tài)，的概率，記為尸( f ) ，即 p ( r ) = 尸 ( ，) = f ) ， 經(jīng)過無窮小時(shí)間缸，系統(tǒng)仍處于狀態(tài)f ( 當(dāng)狀態(tài)空間有限時(shí)0 f k ；當(dāng)狀態(tài)空間 可數(shù)時(shí)0 f o o ) ，則可以用以下互斥事件來描述這一事件： ( 1 ) 在時(shí)刻，時(shí)，系統(tǒng)處于狀態(tài)f ，經(jīng)過缸時(shí)間后，狀態(tài)無變化。則它的概率為 只( ，) ( 1 一以，一，a t ) + o ( a t ) ， ( 2 ) 在時(shí)刻，時(shí)，系統(tǒng)處于狀態(tài)f 一1 ，經(jīng)過出時(shí)間后，狀態(tài)轉(zhuǎn)移到f ，則它的概率 為 p l ( r ) 以一l a t + o ( a t ) ， ( 3 ) 在時(shí)刻，時(shí)，系統(tǒng)處于狀態(tài)i + l ，經(jīng)過f 時(shí)間后，狀態(tài)轉(zhuǎn)移到，則它的概率 為 只+ l ( ，) f + l a t + o ( a t ) ； ( 4 ) 系統(tǒng)在( t + a t ) 內(nèi)發(fā)生兩次或兩次以上轉(zhuǎn)移，它的概率為o ( m ) 。 當(dāng)狀態(tài)空間為有限狀態(tài)時(shí)，由全概率定理可得： 只( t + f ) = o ) ( 1 一丑f 一，a t ) + p lo ) 丑一l a t + 只+ l ( ，) ，+ l a t - i - 0 ( 6 0 ，0 i k ， 方程兩邊同除以f ，整理后得 蘭皇! 蘭掣：五一，只一。( f ) 一( 丑+ ，) p ( f ) f 一一、一。 + 鸕+ 1 只+ l ( f ) + o ( a t ) ，0 f k ， 8 碩十論文 m 。m i c - ( m ) m i n l k 串聯(lián)排隊(duì)系統(tǒng)分析 兩邊對(duì)，取極限，即令f 一0 可得 只。= 乃一1 只一1 0 ) 一( 丑+ a ，) 只( f ) + k t + l + l ( t ) + d ( 址) ，0 f 0 ， ( 2 6 ) 存在，且與初始條件無關(guān)。 2 2 矩陣解析法與擬生滅過程 2 2 1 矩陣解析法 矩陣解析法是n e u t s 發(fā)明并創(chuàng)立起來的，這些年來在排隊(duì)論研究中發(fā)揮了極其重要 的作用。有關(guān)這一方法的理論與應(yīng)用，他分別在1 9 8 1 年和1 9 8 9 年發(fā)表了兩本著作，用 心分布取代了指數(shù)分布，使傳統(tǒng)的生滅過程發(fā)展成了q b d ，嵌入m a r k o v 鏈法發(fā)展成 了結(jié)構(gòu)矩陣分析。在這一變化過程中，矩陣幾何分布和矩陣指數(shù)分布應(yīng)運(yùn)而生，在隨機(jī) 模型的分析中起著重要作用。由于朋分布可以逼近任意非負(fù)隨機(jī)變量的分布，從而使 一般分布假定下的隨機(jī)模型能夠得到易于計(jì)算的逼近。 2 2 2 擬生滅過程 對(duì)于多服務(wù)臺(tái)休假排隊(duì)的研究一般選用擬生滅過程來處理，而q b d 過程這一術(shù)語 首先是e he v a n s ( 1 9 6 7 1 和w a l l a c e ( 1 9 6 9 ) 引用到排隊(duì)論中的。它是經(jīng)典生滅過程的最新發(fā) 展，也是經(jīng)典生滅過程的一個(gè)新的推廣，它把隨機(jī)過程的狀態(tài)空間由一維推廣到多維， 這時(shí)矩陣的形式也為三對(duì)角形式，不過q b d 過程的生成元是分塊的三對(duì)角矩陣而非數(shù) q 第二章預(yù)備知識(shí) 碩 ：論文 字。由于各種多因素、變動(dòng)參數(shù)、隨機(jī)環(huán)境模型分析的需要，q 肋過程已成為當(dāng)代隨 機(jī)模型分析的重要工具。 設(shè)一個(gè)脅砌v 過程似( ，) ，( ，) ) ，其狀態(tài)空間為 q = ( 后，力，k 0 ，1 m ， 若其狀態(tài)過程的q 一矩陣能劃分為分塊三對(duì)角形式 q = a oc o 蜀 彳c ba c ( 2 7 ) 其中所有子塊都是m 階方陣，且 ( 4 + c 0 ) p = ( 盡+ a + c ) e = ( b + 彳+ c ) p = 0 ， a 和a 有負(fù)的對(duì)角元素和非負(fù)的非對(duì)角元素，其余子塊均是非負(fù)陣，稱( ，) ，( ，) ) 是一 個(gè)q s d 。 定理2 2 1 【2 】過程q 正常返，當(dāng)且僅當(dāng)矩陣方程 】，2 召+ 剛+ c = 0 ， 的最小非負(fù)解為r 的譜半徑s p ( r ) l ，并且線性齊次方程組 ( 4 + r b , ) = 0 ， 有正解。 這罩鞏= ( 死1 ，死2 ，2 k m ) ，七0 為過程9 平穩(wěn)概率向量。 參考文獻(xiàn)m 擾船 6 0 9 8 1 ) 中的引理1 5 1 與定理1 5 1 ，并引用類似于定理1 7 1 的證 明方法，我們有如下敘述： 對(duì)于m a r k o v 過程的9 一矩陣有如下形式： q = 彳o a la o a 2a 1a o b o ，b 0 1 分別是( 朋l - m ) x ( 肌l - m ) 、( 所l - m ) xm 階矩陣，反。是m ( 一所) 階矩陣， b 。、4 均為, r 階方陣，且、罵。、么。均為非奇異矩陣，碼聊，七= 1 , 2 ， 記 f， 玩。 1 研捌2 l 壹驢色。童臚- b k 。| ， 、膏= l七= l 其中月是方程x 4 = 0 的最小非負(fù)解。 定理2 2 2 6 0 】若印( r ) l ，則階方陣b 【r 】是一個(gè)生成子。 碩士論文 m 。m c _ ( 肘) m n k 串聯(lián)排隊(duì)系統(tǒng)分析 定理2 2 3 川q 是正常返的充要條件為印( r ) 0 ，使得 ( x o ，置) 研月】= 0 ， 此時(shí)q 有平穩(wěn)概率向量( x o ，x 1 ，x l r ，x 1 r 2 ，) ，且x o p ( 。訓(xùn)4 - x l ( ，一r ) - 1 p 。= l 。 此處i s e , = ( 1 ，1 ，1 ) 7 為i 維列向量，江1 , 2 ， 令彳= a 。，m 維行向量萬滿足： 七= o n a = o ，恐。= 1 ， 顯然向量萬、矩陣r 均與馬爾可夫過程q 的邊界條件有關(guān)，從而有 定理2 2 。4 對(duì)于馬氏過程 q = 玩4 罵a la o 4a 1 a o 若a = 鴿+ a i + 么2 不可約，則印( 月) 0 存在時(shí)，我們稱f ( s ) 為廠( f ) 的拉普拉斯變換，簡(jiǎn)記為l s t 。 性質(zhì)1 ：當(dāng)隨機(jī)變量彳的概率密度為廠( f ) ( f 0 ) ，且e x ”存在時(shí)，n - 倒= 一f 一( 0 ) e x 2 = f 礦( 0 ) e x ”= ( 一1 ) ”f ( 帕( 0 ) 性質(zhì)2 - ( 卷積性質(zhì)) 設(shè)隨機(jī)變量x 、y 的概率密度分別為廠( f ) 和g ( ，) ，其相應(yīng)的l s t 分別為f ( s ) 與g ( s ) ，若存在z 的概率密度為乃( ，) ，且 廳( ，) = 廠( ，) 宰g ( ，) = 上( f f ) g ( f ) d f ， 則廳( f ) 的l s t 為： 日( f ) = f ( t ) o ( ，) 1 2 碩十論文 m 。i m i c - ( m ) i m i n l k 串聯(lián)排隊(duì)系統(tǒng)分析 第三章含特殊類顧客i r m j m cj ( m ) m 聆k 串聯(lián)排隊(duì)系統(tǒng)概率分 析 3 1 模型描述 論文研究的是含特殊類顧客的m i m i c 一( m ) m i u k 兩級(jí)串聯(lián)排隊(duì)系統(tǒng)，模型 如圖所示。 m 工眾 i心 力1 普通； 蹶徽莎 批輸入 i 級(jí)服務(wù)臺(tái) 圖1 模型假定： ( 1 ) 顧客以參數(shù)為見的p o s s i o n 流成批到達(dá)i 級(jí)服務(wù)系統(tǒng)，每批的批量為一隨機(jī)變量 x ，且p ( x = f ) = p ，= 1 , 2 ，n ，n 為一正整數(shù)，此類顧客稱為普通類顧客。 ( 2 ) 設(shè)e ( x ) = b ，d ( x ) = 盯2 ，且x 的概率母函數(shù)( 尸甜) 為x ( z ) 。 ( 3 )i 級(jí)服務(wù)系統(tǒng)有c 個(gè)服務(wù)臺(tái)，每個(gè)服務(wù)臺(tái)的服務(wù)時(shí)間獨(dú)立同分布，均服從參數(shù)為期 的負(fù)指數(shù)分布，不妨設(shè)1 c n 。 ( 4 )i 級(jí)排隊(duì)系統(tǒng)的等待空間為。 ( 5 )級(jí)服務(wù)系統(tǒng)有刀個(gè)服務(wù)臺(tái)，每個(gè)服務(wù)臺(tái)的服務(wù)時(shí)間獨(dú)立同分布，均服從參數(shù)為 ：的負(fù)指數(shù)分布。 ( 6 ) 特殊類顧客為不經(jīng)過i 級(jí)服務(wù)系統(tǒng)，直接進(jìn)入i i 級(jí)服務(wù)系統(tǒng)接受服務(wù)的顧客，特 殊類顧客以參數(shù)為厶的p o s s i o n 流到達(dá)i i 級(jí)服務(wù)系統(tǒng)。 ( 7 ) i 級(jí)服務(wù)系統(tǒng)的服務(wù)時(shí)問記為置，其分布函數(shù)為蜀( ，) ，i i 級(jí)服務(wù)系統(tǒng)的服務(wù)時(shí)間 記為e 。，其分布為e 。( ，) 。 ( 8 )i i 級(jí)服務(wù)系統(tǒng)的容量有限，且設(shè)為k 。當(dāng)級(jí)服務(wù)系統(tǒng)中少于，2 個(gè)服務(wù)臺(tái)服務(wù)時(shí)， 經(jīng)i 級(jí)服務(wù)系統(tǒng)服務(wù)完的普通類顧客可以進(jìn)入級(jí)服務(wù)系統(tǒng)，要求服務(wù)；當(dāng)i i 級(jí) 服務(wù)系統(tǒng)中服務(wù)臺(tái)都處于服務(wù)時(shí)，經(jīng)i 級(jí)服務(wù)系統(tǒng)服務(wù)完的普通類顧客不能進(jìn)入 1 3 第三章含特殊類顧客的m m c _ ( m ) i m i n l k 的串聯(lián)排隊(duì)概率系統(tǒng) 碩十論文 級(jí)服務(wù)系統(tǒng)，這時(shí)該普通類顧客暫時(shí)停留在i 級(jí)服務(wù)系統(tǒng)服務(wù)臺(tái)前，同時(shí)其他 c 一1 個(gè)服務(wù)臺(tái)立即中斷服務(wù)，直至該普通類顧客離開被占的i 級(jí)服務(wù)臺(tái)；但此時(shí) 特殊類顧客可以進(jìn)入級(jí)服務(wù)系統(tǒng)要求服務(wù)，即特殊類顧客最多到達(dá)k 一刀一1 。 ( 9 )當(dāng)級(jí)服務(wù)系統(tǒng)的容量達(dá)到k 時(shí)，到達(dá)的特殊類顧客必須離開i 級(jí)服務(wù)系統(tǒng)或整 個(gè)串聯(lián)服務(wù)系統(tǒng)，永不再來。 ( 1 0 ) 普通類、特殊類顧客到達(dá)間隔，普通類到達(dá)批量，i 級(jí)服務(wù)系統(tǒng)服務(wù)時(shí)間，級(jí) 服務(wù)系統(tǒng)服務(wù)時(shí)間均相互獨(dú)立。 設(shè)厶o ) ，l 2o ) 分別為時(shí)刻f 時(shí)，i 級(jí)服務(wù)系統(tǒng)的隊(duì)長(zhǎng)( 包括正在接受i 級(jí)服務(wù)臺(tái)服 務(wù)的普通類顧客) ，i i 級(jí)服務(wù)系統(tǒng)的隊(duì)長(zhǎng)( 包括正在接受級(jí)服務(wù)臺(tái)服務(wù)的顧客以及接 受完i 級(jí)服務(wù)臺(tái)的服務(wù)，因受阻而未離開i 級(jí)服務(wù)系統(tǒng)的那個(gè)普通類顧客) 。于是它們就 構(gòu)成系統(tǒng)的二維狀態(tài)過程 仁。( ，) ，三：o ) ；f o ) ， 狀態(tài)空間為 e = 砸，) ：f 0 ；0 歹k 各個(gè)狀態(tài)可以按下列規(guī)則排列： ( o ，o ) ，( o ，1 ) ，( o ，甩) ，0 1 9 ( 0 ，k ) ， ( 1 ，o ) ，( 1 ，1 ) ，( 1 ，刀) ，( 1 ，k ) ， ( 2 ，0 ) ，( 2 ，1 ) ，( 2 ，玎) ，( 2 ，k ) ， g ，o ) ，i 9 1 ) ，( f ，刀) ，o ，k ) i = 0 , 1 2 ， 由系統(tǒng)的模型假設(shè)可知， 厶( ，l l ：o ) ；，o ) 是一個(gè)尬砌v 過程。 3 2 狀態(tài)過程的o 一矩陣 各變量可能的變化情況為：由于普通類顧客成批到達(dá)，此時(shí)i 級(jí)服務(wù)系統(tǒng)的隊(duì)長(zhǎng) 厶o ) 以概率p ，增加f 普通類顧客；或者c 個(gè)服務(wù)臺(tái)服務(wù)完一個(gè)普通類顧客，此時(shí)厶( f ) 減 少1 ，1 f