1、.排排 隊隊 論論 模模 型型 .排隊論模型排隊論模型 一、排隊論的基本概念一、排隊論的基本概念 二、單通道等待制排隊問題二、單通道等待制排隊問題 （MM1排隊系統）排隊系統）三、多通道等待制排隊問題三、多通道等待制排隊問題 （MMc排隊系統）排隊系統） .一、排隊論的基本概念一、排隊論的基本概念（一）排隊過程（一）排隊過程 1.1.排隊系統排隊系統 “排隊排隊”是指在服務機構處要求服務對象的一個是指在服務機構處要求服務對象的一個等待隊列，而等待隊列，而“排隊論排隊論”則是研究各種排隊現象的理則是研究各種排隊現象的理論。論。 到來 服服務務規規則則 服服 離離去去 顧顧客客源源 排排隊隊機機構

2、構 務務 機機 構構 排排隊隊系系統統 . 在排隊論中，我們把要求服務的對象稱為在排隊論中，我們把要求服務的對象稱為“顧客顧客”，而將從事服務的機構或人稱為，而將從事服務的機構或人稱為“服務服務臺臺”。 在顧客到達服務臺時，可能立即得到服在顧客到達服務臺時，可能立即得到服務，也可能要等待到可以利用服務臺的時候為止。務，也可能要等待到可以利用服務臺的時候為止。. 排隊系統隊列除了有形的還有無形的排隊系統隊列除了有形的還有無形的。 排隊系統中的排隊系統中的“顧客顧客”與與“服務臺服務臺”這兩個名這兩個名詞可以從不同的角度去理解。詞可以從不同的角度去理解。排隊系統排隊系統顧客顧客服務臺服務臺上、下班

3、的工人乘公共汽車上、下班的工人乘公共汽車工人工人公共汽車公共汽車病人到醫院看病病人到醫院看病病人病人醫生醫生高炮擊退敵機高炮擊退敵機敵機敵機高炮高炮機器發生故障需要維修機器發生故障需要維修機器機器修理工修理工. 在上述顧客在上述顧客- -服務臺組成的排隊系統中，顧客到服務臺組成的排隊系統中，顧客到來的時刻與服務臺進行服務的時間一般來說是隨不來的時刻與服務臺進行服務的時間一般來說是隨不同的時機與條件而變化的，往往預先無法確定。因同的時機與條件而變化的，往往預先無法確定。因此，系統的狀態是隨機的，故而排隊論也稱此，系統的狀態是隨機的，故而排隊論也稱隨機服隨機服務系統務系統。. 各式各樣的排隊現象呈

4、現的基本特征：排隊系統各式各樣的排隊現象呈現的基本特征：排隊系統由輸入過程、排隊規則及服務機構三部分組成。由輸入過程、排隊規則及服務機構三部分組成。(1)(1)輸入過程輸入過程 輸入過程就是顧客按怎樣的規律到達輸入過程就是顧客按怎樣的規律到達包括顧客總體數，是有限的還是無限的；包括顧客總體數，是有限的還是無限的；顧客到達的方式，是成批到達顧客到達的方式，是成批到達( (每批數量是隨機的每批數量是隨機的還是確定性的還是確定性的) )還是單個到達；還是單個到達；相繼到達的顧客相繼到達的顧客( (或批或單個或批或單個) )之間的時間間隔的分之間的時間間隔的分布是什么。布是什么。 2.2.排隊系統的組

5、成和特征排隊系統的組成和特征. 排隊規則是指到達的顧客以怎樣的規則接受服務。排隊規則是指到達的顧客以怎樣的規則接受服務。 1 1）損失制：）損失制：顧客到達，服務臺不空立即離去，顧客到達，服務臺不空立即離去，另求服務。另求服務。 2 2）等待制：）等待制：顧客到達，排隊等待。對等待制服顧客到達，排隊等待。對等待制服務可分為：先到先服務，后到先服務，優先服務，隨務可分為：先到先服務，后到先服務，優先服務，隨機服務，成批服務等。機服務，成批服務等。 3 3）混合制：）混合制：在現實生活中，很多服務系統介于在現實生活中，很多服務系統介于損失制和等待制之間，當顧客到達時，服務臺不空就損失制和等待制之間

6、，當顧客到達時，服務臺不空就排隊，若排隊的位置已滿就離去。排隊，若排隊的位置已滿就離去。 (2)(2)排隊規則排隊規則.服務機構主要指服務臺的數目，服務機構主要指服務臺的數目，多個服務臺進行服務時，服務方式是并聯還多個服務臺進行服務時，服務方式是并聯還是串聯；是串聯；服務時間服從什么分布等。服務時間服從什么分布等。 (3)(3)服務機構服務機構. 1.1.排隊模型的分類排隊模型的分類這里僅針對并列的服務臺。這里僅針對并列的服務臺。 記記X X：顧客到達的時間間隔分布；顧客到達的時間間隔分布；Y Y：服務時間的服務時間的分布；分布；Z Z：服務臺數。則排隊模型：服務臺數。則排隊模型：X XY Y

7、Z Z。 常用的記號：常用的記號：M M負指數分布；負指數分布；D D確定型；確定型；EkEkk k階愛爾朗（階愛爾朗（ErlangErlang）分布；分布；GIGI一般相互獨立的隨一般相互獨立的隨機分布，機分布，G G一般隨機分布。這里主要討論一般隨機分布。這里主要討論M MM M1 1，M MM MC C。（二）排隊模型的分類及數量指標（二）排隊模型的分類及數量指標. (1)(1)隊長隊長隊長是指系統中的顧客數隊長是指系統中的顧客數( (包括排隊等候和正在包括排隊等候和正在接受服務的顧客數接受服務的顧客數) )；等待隊長是指系統中等待服務的顧客數。等待隊長是指系統中等待服務的顧客數。 2.

8、2.排隊模型的數量指標排隊模型的數量指標.逗留時間是指一顧客從進入系統起一直到接受服逗留時間是指一顧客從進入系統起一直到接受服務后離開系統為止所花費的時間；務后離開系統為止所花費的時間；等待時間是指一顧客從進入系統起到接受服務時等待時間是指一顧客從進入系統起到接受服務時所花費的時間。所花費的時間。 (2)(2)逗留時間逗留時間. 忙期是指從顧客到達空閑服務機構起到服務機構忙期是指從顧客到達空閑服務機構起到服務機構再次為空閑為止的這段時間，即服務機構連續繁忙的再次為空閑為止的這段時間，即服務機構連續繁忙的時間長度。時間長度。這是服務機構最關心的數量指標，因為它直接關系到這是服務機構最關心的數量指

9、標，因為它直接關系到服務員的工作強度，與忙期相對應的是閑期，即為服服務員的工作強度，與忙期相對應的是閑期，即為服務機構連續保持空閑的時間長度。顯然，在排隊系統務機構連續保持空閑的時間長度。顯然，在排隊系統中，忙期與閑期是交錯出現的。中，忙期與閑期是交錯出現的。 (3)(3)忙期忙期.1.1.最簡單流與最簡單流與PoissonPoisson過程過程 記隨機過程記隨機過程x x（t t）：）：t0t0為時間為時間0 0，t t內內流流( (事件事件) )發生的次數，例如對于隨機到來某電話交換發生的次數，例如對于隨機到來某電話交換臺的呼叫，以臺的呼叫，以x x（t t）表示該交換臺在表示該交換臺在0

10、 0，t t這段時這段時間內收到呼叫的次數；若是服務機構，可以用間內收到呼叫的次數；若是服務機構，可以用x x（t t）表示該機構在表示該機構在0 0，t t時間內來到的顧客數時間內來到的顧客數。（三）（三）PoissonPoisson流與指數分布流與指數分布.最簡單流應最簡單流應 具有以下特征稱具有以下特征稱0: )(ttx(1)(1)流具有平衡性流具有平衡性 對任何對任何 和和 , , 的分布只取決于的分布只取決于 而與而與 無關。無關。(2)(2)流具有無后效性流具有無后效性對互不交接的時間區間序列對互不交接的時間區間序列 ， 是一組相互獨立的隨機變量。是一組相互獨立的隨機變量。(3)(

11、3)流具有普通性流具有普通性即在即在 時間內，事件發生多于時間內，事件發生多于1 1次的概率為次的概率為 。 0anttt210)1 ()()(niaxtaxinttt,21a)1 (,nibaii)()(iiaxbx01)()(Prlimtaxtaxtt)( to .定理定理1 1設設 是最簡單流，則對任何是最簡單流，則對任何 和和都有都有 我們把滿足這一分布規律的隨機過程我們把滿足這一分布規律的隨機過程稱為稱為PoissonPoisson過程，最簡單流亦稱過程，最簡單流亦稱PoissonPoisson流，特別取流，特別取 得得故參數故參數表示單位時間內事件發生次數的平均數表示單位時間內事件

12、發生次數的平均數。0: )(ttx0a0t( t)P()( )(0,1,2,)!ktx atx akekk0: )(ttx( t)Pr( )(0,1,2,)!ktx tkekk0attxE)(.2.2.PoissonPoisson流的發生時間間隔分布流的發生時間間隔分布 當流當流( (過程過程) ) 構成構成PoissonPoisson過程時，就稱過程時，就稱為為PoissonPoisson流。設流發生的時刻依次為流。設流發生的時刻依次為 , ,，發生的時間間隔記為發生的時間間隔記為 ，其中其中 。定理定理2 2 事件流事件流 為為PoissonPoisson流的充要條件是流的充要條件是 的流

13、發生時間間隔的流發生時間間隔 相互獨立，且服從相互獨立，且服從相同的負指數分布，即相同的負指數分布，即0: )(ttxnttt,21), 2 , 1(1nttnnn00t0: )(ttx0: )(ttx n0001Prttettn. 對于單通道等待制排隊問題主要討論輸入過對于單通道等待制排隊問題主要討論輸入過程為程為PoissonPoisson流，服務時間服從負指數分布，單服流，服務時間服從負指數分布，單服務臺的情形，即務臺的情形，即M MM M1 1排隊系統。排隊系統。（一）標準模型（一）標準模型 即為即為M MM M1 1排隊系統。所謂標準模型，排隊系統。所謂標準模型，就是顧客的輸入流是參

14、數為就是顧客的輸入流是參數為的的PoissonPoisson流，每個流，每個顧客的服務時間是相互獨立的且服從參數為顧客的服務時間是相互獨立的且服從參數為的的負指數分布，單個服務臺且系統的容量無限負指數分布，單個服務臺且系統的容量無限( (排隊排隊模型分類第四個表示系統中允許的最大顧客數模型分類第四個表示系統中允許的最大顧客數) )。二、單通道等待制排隊問題二、單通道等待制排隊問題 （MMMM1 1排隊系統）排隊系統）.1.1.系統的系統的MarkovMarkov特性特性 考慮隨機過程考慮隨機過程 ，其中其中 為時刻為時刻 時時排隊系統中的顧客數。排隊系統中的顧客數。 對于任何對于任何 條件概率

15、條件概率由于輸入為由于輸入為PoissonPoisson流，服務時間服從負指數分布，流，服務時間服從負指數分布，則無論則無論 在在 處取何值，上式條件概率僅依處取何值，上式條件概率僅依賴于賴于 的值和區間的值和區間 的長度的長度 ，即即0: )(ttx)(txtnttt210112211)(,)(,)()(Prnnnnitxitxitxitx)(txnttt,21)(1ntx),(1nntt1nntt11112211)()(Pr)(,)(,)()(Prnnnnnnnnitxitxitxitxitxitx. 記時刻記時刻t t系統處于狀態系統處于狀態n n的概率的概率利用利用M MM M1 1對

16、輸入與服務時間分布的假設，在時間對輸入與服務時間分布的假設，在時間區間區間 內，新進入或離開顧客個數有以下結果：內，新進入或離開顧客個數有以下結果： 內沒有顧客進入內沒有顧客進入 內新進入一名顧客內新進入一名顧客 內多于一名顧客進入內多于一名顧客進入 內沒有顧客離開內沒有顧客離開 內有一名顧客離開內有一名顧客離開 內多于一名顧客離開內多于一名顧客離開2.2.排隊系統的穩態解排隊系統的穩態解ntxtPn)(Pr)(),(ttt)(1),(Prtotetttt)(),(Prtottetttt)(),(Prtottt)(1),(Prtotetttt)(),(Prtottetttt)(),(Prtot

17、tt. 當當 時有時有導出導出 滿足的微分方程組滿足的微分方程組)(tpn)()1 ()()1)()(100totttpttpttp)()()()()(1000tottpttptpttp0t)()()(100tptptp.故故 滿足的微分方程組滿足的微分方程組)()()1)(1)()()(11tottptttpttpttpnnnn)()()()()(11tptptptpnnnn對對1n)()()(, 2 , 1)()()()()(10011tptptpntptptptpnnnn)(tpn. 對于系統的穩定狀態情形，對于系統的穩定狀態情形， 與與t t無關，無關，故故 ，記記 ，從而有從而有對于

18、上述差分方程，利用歸納法不難求得對于上述差分方程，利用歸納法不難求得)(tpn0)( tpn)(tppnn0, 2 , 10)(1011ppnpppnnn0)(ppnn. 記記 為排隊系統的來往強度，當為排隊系統的來往強度，當 時，由時，由 可得可得 由于由于 構成概率分布，則構成概率分布，則 ，從而級數從而級數 必須收斂，故有必須收斂，故有 。 np01nnp0)(nn1101nnp, 2 , 1 , 0)1 (npnn.MMMM1 1系統的數量指標系統的數量指標 (1)(1)穩定狀態下系統中顧客數的數學期望的定義為穩定狀態下系統中顧客數的數學期望的定義為被稱為系統中顧客的平均數，簡稱被稱為

19、系統中顧客的平均數，簡稱平均隊長平均隊長。 0nnnpL1)(1(1000nnnnnnnnpL1)1(2000nnnnnnqpnppnL 穩定狀態下系統中等待服務顧客數的數學期望，穩定狀態下系統中等待服務顧客數的數學期望，簡稱平均簡稱平均等待隊長等待隊長。. (2)(2)顧客在系統中的顧客在系統中的平均逗留時間平均逗留時間 則顧客在系統中的則顧客在系統中的平均等待時間平均等待時間 可以證明，顧客在系統中逗留時間服從參數為可以證明，顧客在系統中逗留時間服從參數為-的負指數分布。的負指數分布。1)(11q. 與與 是衡量排隊系統質量的很重要的效是衡量排隊系統質量的很重要的效率度量率度量上式稱為上式

20、稱為LittleLittle公式。公式。 表明系統中的顧客數，等于一個顧客在表明系統中的顧客數，等于一個顧客在系統時間內來到的新的顧客數；系統時間內來到的新的顧客數； 表明系統中處于等待狀態的顧客數，表明系統中處于等待狀態的顧客數，等于一個顧客的等待時間內來到的新顧客數。等于一個顧客的等待時間內來到的新顧客數。 LittleLittle公式公式qqLLLqqLqLL,q,.(3)(3)穩定狀態下穩定狀態下忙期忙期的數學期望的數學期望由此可見，一個忙期中所服務顧客的平均數為由此可見，一個忙期中所服務顧客的平均數為1)(TE忙忙11)(TE.（二）系統容量有限的模型（二）系統容量有限的模型 即為即

21、為M MM M1 1N N排隊系統。考慮排隊系統的容排隊系統。考慮排隊系統的容量為量為N N，即若系統已有即若系統已有N N個顧客，則再來新顧客即被個顧客，則再來新顧客即被拒絕進入系統。對于拒絕進入系統。對于n nN N，與與M MM M1 1相類似，相類似， ，有有ntxtPn)(Pr)()()()(1, 2 , 1)()()()()(10011tptptpNntptptptpnnnn對于對于n nN N，)()1)()()(1tottpttpttpNNN)()()(1tptptpNNN. 即即 滿足微分方程滿足微分方程 在穩態情況下，在穩態情況下， ， ，則則)(tPn)()()()()()(1, 2 , 1)()()()()(110011tptptptptptpNntptptptpNNNnnnn