1、4.5 4.5 排隊系統模型排隊系統模型 K K n n n nn n n n n n n nn n n n n n n n n n s s 0n nS nPL N n nS nPL 0 或 q q 0 )( n nq PcnL s s s ss s n n= = s s (1(1 n n) ) s s s ss s n n= = s s (1(1 n n) ) s s s ss s n n= = s s (1(1 n n) ) s s s ss s n n= = s s (1(1 n n) ) s s s ss s n n= = s s (1(1 n n) ) n n 0 )( n nq P

2、cnL t tt t t t)(),( 1 tttttP 其中其中00是常數，它表示單位時間內有一個顧客到的概率是常數，它表示單位時間內有一個顧客到的概率. . 的高階無窮小量關于時是當ttt,0)( （3 3）普通型普通型. .對于充分小的對于充分小的t，在時間區間，在時間區間t,t+t,t+t) )內有內有2 2個個 或或2 2個以上顧客到達的概率是極小的個以上顧客到達的概率是極小的. .即即 2 )(),( n n ttttP , 2 , 1 , 0 ! )( )(1lim ! )( )1 (lim ! )( )1 ( ) 1 1).( 1 1)(1lim( ! )( )1 ()1 (

3、) 1 ).( 1 )(lim( ! )( )1 ( ) 1() 1( lim ! )( )1 ()( ! ) 1() 1( lim )1 ()(lim)( K e K t n t K t n t K t n t n K nK t n t n t n Kn n n n n K t n t n Knnn K t n t n t K Knnn n t n t CtP t K t n t n K n n K n n K kn n K kn n k K KnK n KnKk n n K 1) 1 ()1 (lim kk n n t , 2 , 1 , 0, ! )( )1 ()(lim)( Ke K

4、t n t n t CtP t K KnKk n n K 0, 0 0, )( t te tf t T 它的分布函數它的分布函數 0, 0 0,1 )( t te tF t T 數學期望數學期望, ,記成記成ET=1/,ET=1/,方差記成方差記成DT=1/DT=1/2 2 負指數分布有下面的一些性質負指數分布有下面的一些性質: : (1) (1)由條件概率公式很容易證明由條件概率公式很容易證明: : PTt+s|Ts=PTt PTt+s|Ts=PTt st+s 0, 0 0, )( t te tf t T 它的分布函數它的分布函數 0, 0 0,1 )( t te tF t T (1) (1

5、)由條件概率公式很容易證明由條件概率公式很容易證明: : PTt+s|Ts=PTt PTt+s|Ts=PTt st+s tTPtTPe e e e e e sTP stTP sTP stTP sTP sTPstTP sTstTP t t s st s st 1)1 (1 )1 (1 )1 (1 1 1 | )()( 0, 0 0, )( t te tf t T 它的分布函數它的分布函數 0, 0 0,1 )( t te tF t T 數學期望數學期望, ,記成記成ET=1/,ET=1/,方差記成方差記成DT=1/DT=1/2 2 負指數分布有下面的一些性質負指數分布有下面的一些性質: : (1

6、) (1)由條件概率公式很容易證明由條件概率公式很容易證明: : PTt+s|Ts=PTt PTt+s|Ts=PTt 這個性質叫做這個性質叫做無記憶性無記憶性, ,或馬爾柯夫性或馬爾柯夫性. .若若T T表示排隊系統中表示排隊系統中, , 顧客到達的間隔時間顧客到達的間隔時間, ,那么這個性質說明一個顧客到達的時間與那么這個性質說明一個顧客到達的時間與 過去一個顧客到達所需的時間過去一個顧客到達所需的時間s s無關無關, , 所以在這種情況下所以在這種情況下, ,顧客到顧客到 達是純隨機的達是純隨機的. . st+s (2) (2)當輸入過程是當輸入過程是泊松流泊松流的時候的時候, ,那么顧客

7、相繼到達的間隔時那么顧客相繼到達的間隔時 間間T T就服從就服從負指數分布負指數分布. . 實際上實際上, ,對于泊松流對于泊松流, ,如果顧客到達的間隔時間如果顧客到達的間隔時間T Tt ,t ,則在則在 0,t)0,t)間內至少有一個顧客到達間內至少有一個顧客到達, ,從而從而 t e -1(t)P-1tPT 0 即即T T就服從參數為就服從參數為的負指數分布的負指數分布. . 因此因此, ,相繼到達的間隔時間是獨立的相繼到達的間隔時間是獨立的, ,且為相同參數的的負且為相同參數的的負 指數分布指數分布, ,與輸入過程為泊松流與輸入過程為泊松流( (它的參數是它的參數是)是等價的是等價的.

8、 . 根據負指數分布與泊松流的關系可以推出根據負指數分布與泊松流的關系可以推出, ,當服務機構對顧當服務機構對顧 客的服務時間服從參數客的服務時間服從參數的負指數分布的負指數分布, ,如果服務機構處于忙如果服務機構處于忙 期期, ,則服務機構的輸出則服務機構的輸出, ,也就是服務完畢離開服務機構的顧客數也就是服務完畢離開服務機構的顧客數 服從泊松分布的泊松流服從泊松分布的泊松流; ; 其中其中為每個顧客的平均服務時間為每個顧客的平均服務時間, , 也就是顧客相繼離開的時間間隔也就是顧客相繼離開的時間間隔. . i i 1 12 2k k 1 12 2+ +k k 服從密度函數服從密度函數 的概

9、率分布的概率分布, ,稱稱 T T服從服從k k階的愛爾朗分布階的愛爾朗分布. . 數學期望數學期望,E(T)=1/, ,E(T)=1/, 方差方差D(T)=1/kD(T)=1/k2 2 0, )!1( )( )( 1 te k tkk tb kt k k 3 3生滅過程生滅過程 生滅過程就是用來處理輸入是泊松流生滅過程就是用來處理輸入是泊松流, ,服務時間是服務時間是 負指數分布的這樣一類最簡單的排隊模型的方法負指數分布的這樣一類最簡單的排隊模型的方法. . 什么是生滅過程什么是生滅過程? ?舉例來說舉例來說, ,假如有一堆細菌假如有一堆細菌, ,每個細每個細 菌在時間菌在時間t t內內,

10、,它分裂成兩個的概率是它分裂成兩個的概率是t+o(t+o(t).t). 在時間在時間t t內死亡的概率是內死亡的概率是t+o(t+o(t).t). 各個細菌在任何時間段內的分裂和死亡都是獨立的各個細菌在任何時間段內的分裂和死亡都是獨立的, ,并并 且把細菌的分裂和死亡都看成一個事件的話且把細菌的分裂和死亡都看成一個事件的話, ,則在則在t t內發內發 生兩個或兩個以上的事件概率為生兩個或兩個以上的事件概率為o(o(t).t). 假如已知初始時刻假如已知初始時刻, ,細菌的個數細菌的個數, ,要問經過時間要問經過時間t t后細菌后細菌 將變成多少個將變成多少個? ?如把細菌的分裂看成是一個新顧客

11、的到達如把細菌的分裂看成是一個新顧客的到達, , 細菌的死亡看成一個服務完畢的顧客離去細菌的死亡看成一個服務完畢的顧客離去, ,則生滅過程恰好則生滅過程恰好 反映了一個排隊服務系統的瞬時狀態反映了一個排隊服務系統的瞬時狀態N(t)-N(t)-在時刻在時刻t t服務系服務系 統中的顧客數統中的顧客數, ,將怎樣隨時間將怎樣隨時間t t而變化而變化. . 在生滅過程中在生滅過程中, ,生與死的發生都是隨機的生與死的發生都是隨機的. .它們的平均發生它們的平均發生 率依賴于現有的細菌數率依賴于現有的細菌數, ,即系統現處的狀態即系統現處的狀態. .假定假定: : (a) (a) 給定給定N(t)=n

12、,N(t)=n,到下一個生到下一個生( (顧客到達顧客到達) )的時間間隔是具有的時間間隔是具有 參數參數n n(n=0,1,2,.)(n=0,1,2,.)的負指數分布的負指數分布. . (b) (b) 給定給定N(t)=n,N(t)=n,到下一個死到下一個死( (顧客離去顧客離去) )的間隔時間是具有的間隔時間是具有 參數參數n n(n=1,2,.)(n=1,2,.)的負指數分布的負指數分布. . (c) (c) 系統狀態在時間區間系統狀態在時間區間t t內只能轉移到相鄰的狀態內只能轉移到相鄰的狀態, ,即只即只 能發生一個生或一個死能發生一個生或一個死. . 根據上述負指數分布的性質根據上

13、述負指數分布的性質, ,n n就是系統處于就是系統處于N(t)N(t)時單位時時單位時 間內顧客的平均到達率間內顧客的平均到達率,n n就是單位時間內顧客的平均離去率就是單位時間內顧客的平均離去率. . 將上面幾個假定結合在一起將上面幾個假定結合在一起, ,則可以用生滅過程的狀態轉移則可以用生滅過程的狀態轉移 圖來表示圖來表示. . 012n-2n-1n 1 2 3 n-1 n n+1 要求系統的瞬時狀態要求系統的瞬時狀態N(t)N(t)的概率分布是很困難的的概率分布是很困難的, , 所以下面只考慮系統處于穩定狀態時的情形所以下面只考慮系統處于穩定狀態時的情形. . 先考慮系統處于一個特定的狀

14、態先考慮系統處于一個特定的狀態 N(t)=n,(n=0,1,2,.)N(t)=n,(n=0,1,2,.)我們計算過程進入這個狀態和離開我們計算過程進入這個狀態和離開 這個狀態的次數這個狀態的次數, ,因為在同一時刻因為在同一時刻, ,這兩個事件都只能發生這兩個事件都只能發生 一次一次, ,因此進入和離開這個狀態的次數或者是相等的因此進入和離開這個狀態的次數或者是相等的, ,或者或者 剛好差一次剛好差一次. . 對穩定系統來說對穩定系統來說, ,在很長一段時間內在很長一段時間內, ,進出系統的顧客進出系統的顧客 數保持平衡數保持平衡, ,即對系統的任何狀態即對系統的任何狀態N(t)=n,(n=0

15、,1,2,.),N(t)=n,(n=0,1,2,.), 進入事件率進入事件率( (單位事件平均到達的顧客數單位事件平均到達的顧客數) )等于離去事件率等于離去事件率 ( (單位時間平均離開的顧客數單位時間平均離開的顧客數),),這就是這就是輸入率等于輸出率的輸入率等于輸出率的 原則原則. .用來表示這個原則的方程稱為系統的用來表示這個原則的方程稱為系統的狀態平衡方程狀態平衡方程. . 下面就是要通過建立系統的平衡方程來處理一些比較簡下面就是要通過建立系統的平衡方程來處理一些比較簡 單的排隊模型單的排隊模型. . 設處于狀態設處于狀態i i時系統的穩定狀態概率為時系統的穩定狀態概率為P Pi i

16、. .先考慮先考慮 n=0n=0的狀態的狀態, ,狀態狀態0 0的輸入僅僅來自狀態的輸入僅僅來自狀態1,1,而從狀態而從狀態1 1進進 入狀態入狀態0 0的平均轉換率為的平均轉換率為1 1, ,因此從狀態因此從狀態1 1進入狀態進入狀態0 0的的 輸入率為輸入率為1 1P P1 1, ,又從其它狀態直接進入狀態又從其它狀態直接進入狀態0 0的概率為的概率為0,0, 所以狀態所以狀態0 0的總輸入率為的總輸入率為1 1P P1 1. .根據根據, ,輸入率等于輸出率輸入率等于輸出率 的原則的原則,1 1P P1 1=0 0P P0 0. . 012n-2n-1n 1 2 3 n-1 n n+1

17、1 1P P1 1=0 0P P0 0 012n-2n-1n 1 2 3 n-1 n n+1 由上述方程組可解得由上述方程組可解得: : 0 1 0 1 PP 0 12 01 1 2 1 2 PPP 0 123 012 2 3 2 3 PPP 0 11 021 1 1 . . PPP nn nn n n n n 0 0P P0 0+2 2P P2 2=(=(1 1+1 1)P)P1 1 1 1P P1 1+3 3P P3 3=(=(2 2+2 2)P)P2 2 n-2 n-2P Pn-2n-2+ +n nP Pn n=(=(n-1 n-1+ +n-1 n-1)P )Pn-1 n-1 n-1 n

18、-1P Pn-1n-1+ +n+1 n+1P Pn+1n+1=( =(n n+n n)P)Pn n 如令如令: : 0 11 021 1 1 . . PPP nn nn n n n n ,.)2 , 1( , . . 11 021 nC nn nn n 則以上各式可以寫為一個通式則以上各式可以寫為一個通式: :Pn=CnP0 (n=1,2,.) 00 0 1 nn nn PCP 0 0 1 n n C P 求得求得P P0 0后后, ,可以推得可以推得P Pn n,(n=1,2,.),(n=1,2,.) 在輸入是泊松流在輸入是泊松流, ,服務時間為負指數分布的服務系統中服務時間為負指數分布的服

19、務系統中, ,顧顧 客的到達和離去的規律完全符合生滅過程的條件客的到達和離去的規律完全符合生滅過程的條件, ,因此因此,M/M,M/M類型類型 的服務系統可以用生滅過程方法求得穩態概率的服務系統可以用生滅過程方法求得穩態概率, ,進而求出排隊系進而求出排隊系 統中的各項指標統中的各項指標. . Ls( Ls(系統中顧客數的平均值系統中顧客數的平均值);); Lq( Lq(隊列中顧客數的平均值隊列中顧客數的平均值); ); Ws( Ws(每個顧客在系統中平均逗留的時間每個顧客在系統中平均逗留的時間);); Wq( Wq(每個顧客在隊列中平均逗留的時間每個顧客在隊列中平均逗留的時間).). 4 4

20、單服務臺排隊系統模型單服務臺排隊系統模型(M/M/1)(M/M/1) 本節將討論輸入是泊松流本節將討論輸入是泊松流, ,服務時間為負指數分布的單服務時間為負指數分布的單 服務臺排隊系統模型服務臺排隊系統模型. .因為這類模型都符合生滅過因為這類模型都符合生滅過 程程, ,所以可以將生滅過程的結論搬過來應用所以可以將生滅過程的結論搬過來應用. . 下面分成幾種類型來討論下面分成幾種類型來討論. . 4.1 M/M/1/ 4.1 M/M/1/模型模型 該模型是指顧客按泊松流到達該模型是指顧客按泊松流到達, ,到達的速率是到達的速率是, , 服務時服務時 間服從負指數分布間服從負指數分布, ,服務率

21、是服務率是,單個服務臺單個服務臺, ,系統對顧客無系統對顧客無 限制限制, ,顧客源也無限制顧客源也無限制, ,先到先服務的服務系統先到先服務的服務系統. .其系統狀態其系統狀態 是無限的是無限的, ,即即n=0,1,2,.n=0,1,2,.下圖表示系統的狀態轉移圖下圖表示系統的狀態轉移圖. . 因為對所有狀態因為對所有狀態n,n,n n=, =, n n=,=,所以所以 .)2 , 1()/(nC nn n 1 11 , 00 000 n n n n n nn C PPPCP n n P)1 ( 這里這里=/1=/1是單位時間內顧客平均到達率與平均服務率的比是單位時間內顧客平均到達率與平均服

22、務率的比 值值, ,反映了服務機構的忙碌或利用程度反映了服務機構的忙碌或利用程度, ,稱稱為服務強度或服務忙期為服務強度或服務忙期. . 因為因為1 1時時, ,系統中的顧客數會越來越多系統中的顧客數會越來越多, ,系統不會進入穩定狀態系統不會進入穩定狀態. . 所以所以設設 1 1. . 下面推導服務系統中的其它指標下面推導服務系統中的其它指標. . (1) (1)系統內平均的顧客數系統內平均的顧客數 s n nn ns L nnPL 或 1 . .)32(.)32()1 ( 32 43232 00 (2)(2)隊列中等待的平均顧客數隊列中等待的平均顧客數 1 11 )1 (1 ()1 ()

23、 1( 2 0 111 s ss n n n n n nq L LPLPnPPnL (3)(3)顧客在系統中平均等待的時間顧客在系統中平均等待的時間 1 / sS LW (4)(4)平均排隊的時間平均排隊的時間 / qq LW 例例3 3 某醫院手術室根據病人來診和完成手術時間的記錄，某醫院手術室根據病人來診和完成手術時間的記錄， 任意抽查任意抽查100100個工作小時。每小時來就診的病人數個工作小時。每小時來就診的病人數n n出現的次出現的次 數如表數如表12-812-8所示。又任意抽查了所示。又任意抽查了100100個完成手術的病歷，所個完成手術的病歷，所 用時間用時間v(v(小時小時)

24、)的次數如表的次數如表12-912-9所示。所示。 n n n n 0.00.00.23838 0.20.20.42525 0.40.40.61717 0.60.60.89 9 0.80.81.06 6 1.01.01.25 5 1.21.2以上以上0 0 合計合計100100 例例3 3 某醫院手術室根據病人來診和完成手術時間的記錄，任意抽某醫院手術室根據病人來診和完成手術時間的記錄，任意抽 查查100100個工作小時。每小時來就診的病人數個工作小時。每小時來就診的病人數n n出現的次數如表出現的次數如表 12-812-8所示。又任意抽查了所示。又任意抽查了100100個完成手術的病歷，所用

25、時間個完成手術的病歷，所用時間 v(v(小時小時) )的次數如表的次數如表12-912-9所示。所示。 (1)每小時到病人平均到達率每小時到病人平均到達率 )/( 1 . 2 100 小時人 n nf 每次手術平均時間每次手術平均時間 )/(4 . 037. 0 100 人小時 v vf 每小時完成手術人數=1/0.4=2.5(人/小時)。 (2)我們取我們取=2.1,=2.5,=2.1,=2.5,可以通過統計檢驗的方法可以通過統計檢驗的方法, ,認為病人到認為病人到 達數服從參數為達數服從參數為2.12.1的泊松分布的泊松分布, ,手術時間服從參數為手術時間服從參數為2.52.5的負指數的負

26、指數 分布分布. . (3)服務強度服務強度=/=2.1/2.5=0.84. =/=2.1/2.5=0.84. 服務機構有服務機構有8484的時間的的時間的 繁忙的，有繁忙的，有1616的時間是空閑的。的時間是空閑的。 (4)病房內平均的病人數病房內平均的病人數.Ls=/(-)=2.1/(2.5-2.1)=5.25.Ls=/(-)=2.1/(2.5-2.1)=5.25人人. . (5)排隊等待的病人數排隊等待的病人數.Lq=Ls-=Ls-/5.25-0.844.41人人. (6)病人在病房中逗留的時間病人在病房中逗留的時間.Ws =Ls/=1/(-) = 1/(2.5-2.1)=2.5(小時小

27、時). 例例3 3 某醫院手術室根據病人來診和完成手術時間的記錄，任意抽某醫院手術室根據病人來診和完成手術時間的記錄，任意抽 查查100100個工作小時。每小時來就診的病人數個工作小時。每小時來就診的病人數n n出現的次數如表出現的次數如表 12-812-8所示。又任意抽查了所示。又任意抽查了100100個完成手術的病歷，所用時間個完成手術的病歷，所用時間 v(v(小時小時) )的次數如表的次數如表12-912-9所示。所示。 (2)我們取我們取=2.1,=2.5,=2.1,=2.5,可以通過統計檢驗的方法可以通過統計檢驗的方法, ,認為病人到認為病人到 達數服從參數為達數服從參數為2.12.

28、1的泊松分布的泊松分布, ,手術時間服從參數為手術時間服從參數為2.52.5的負指數的負指數 分布分布. . (3)服務強度服務強度=/=2.1/2.5=0.84. =/=2.1/2.5=0.84. 服務機構有服務機構有8484的時間的的時間的 繁忙的，有繁忙的，有1616的時間是空閑的。的時間是空閑的。 (4)病房內平均的病人數病房內平均的病人數.Ls=/(-)=2.1/(2.5-2.1)=5.25.Ls=/(-)=2.1/(2.5-2.1)=5.25人人. . (5)排隊等待的病人數排隊等待的病人數.Lq=Ls-=Ls-/5.25-0.844.41人人. (6)病人在病房中逗留的時間病人在

29、病房中逗留的時間.Ws =Ls/=1/(-) = 1/(2.5-2.1)=2.5(小時小時). (7)病人排隊等待時間病人排隊等待時間.Wq=Lq/=/(-) =0.84/(2.5-2.1)=2.1(小時小時)。 4.2 M/M/1/N/4.2 M/M/1/N/模型模型 在實際生活中經常碰到排隊長度有限制的服務系統。在實際生活中經常碰到排隊長度有限制的服務系統。 如醫院規定每天掛如醫院規定每天掛100100個號，那么個號，那么100100以后到達醫院者會自以后到達醫院者會自 動離開服務系統；理發店等待的座位都滿員時，后來的顧動離開服務系統；理發店等待的座位都滿員時，后來的顧 客就會離開，等等。

30、客就會離開，等等。 因為隊長有限制因為隊長有限制, ,所以系統的狀態只能取從所以系統的狀態只能取從0,1,2,.N0,1,2,.N 這些值這些值, ,系統的狀態轉移圖如圖系統的狀態轉移圖如圖12-912-9所示。所示。 4.2 M/M/1/N/4.2 M/M/1/N/模型模型 Nn Nn n 0 1,.1 , 0 Nn n ,.1 , 0, Nn Nn C nn nn nn n 0 ,.1 , 0)/( . . 11 021 NnPPCP CC P n nn N NnN n n N n n n n ,.,1 , 0, )1 ( 1 1 )1 ( 1 1 .1 1111 00 1 12 000

31、0 由此，可得各個系統的各種指標：由此，可得各個系統的各種指標： （1 1）隊長）隊長( (系統中平均的顧客數系統中平均的顧客數 ) ) n N n N n N n s nPnL 0 1 0 )1 ( 1 N n N n N n nn N n n N n d d d d d d nn 0 1 0 1 00 1 )1 ( 1 11 1 0 1 ) 1( 11 )1 ( )1 ( 1 N NN N n N n s N d d PnL 現在的現在的LsLs與與M/M/1/M/M/1/中的中的LsLs相比較相比較 1 s L 由于由于1,1,可以看出，隊長在受限制的情況下，系統中顧客數可以看出，隊長在

32、受限制的情況下，系統中顧客數 一定小于隊長不受限制時的顧客數。另外當一定小于隊長不受限制時的顧客數。另外當NN時，時， 1 s L 與隊長不受限制時的系統中平均顧客數完全一致。因此隊長不受與隊長不受限制時的系統中平均顧客數完全一致。因此隊長不受 限制的系統可以看作是隊長受限制的系統的一種特例。限制的系統可以看作是隊長受限制的系統的一種特例。 為了計算系統中其它各項指標，先要引入有效輸入率為了計算系統中其它各項指標，先要引入有效輸入率 e e的概念。因為在隊長受限制的情況下，當到達的顧客數的概念。因為在隊長受限制的情況下，當到達的顧客數 n nN N的時候，新到的顧客就會自動離去。因此雖然顧客是

33、以的時候，新到的顧客就會自動離去。因此雖然顧客是以 平均速度平均速度的速率來到服務系統，但由于的速率來到服務系統，但由于N N0 0，真正進入，真正進入 服務系統的顧客平均到達率卻是比服務系統的顧客平均到達率卻是比小的小的e e 。 )1 ( 1 00 n N n n N n nne PPP 可以驗證可以驗證)1 ( 0 P e )1 () 1 1 1 ( 1 )1 (1 1 , 1 1 1 1 ) )1 ( 1 1 ()1 ()1 ( 0 11 1 1 1 11 11 1 0 P PP NN N N N N N N NNN N NN ne （2 2）隊列長）隊列長( (顧客在排隊時平均等待的

34、時間顧客在排隊時平均等待的時間) ) /)P-(1- 0essq LLL （3 3）顧客在系統中逗留的時間）顧客在系統中逗留的時間WsWs ess LW/ （4 4）顧客等待排隊的時間）顧客等待排隊的時間Wq Wq 1/ s e es e q q W L L W 例例4 4 單人理發館有單人理發館有6 6個椅子接待人們排隊等待理發。當個椅子接待人們排隊等待理發。當6 6 個椅子都坐滿時，后來到的顧客不進店就離開。顧客平均個椅子都坐滿時，后來到的顧客不進店就離開。顧客平均 到達率為到達率為3 3人人/ /小時，每名顧客理發需時平均小時，每名顧客理發需時平均1515分鐘。分鐘。 （1 1）求某顧客

35、一到達就能理發的概率。）求某顧客一到達就能理發的概率。 （2 2）需要等待的顧客平均數。）需要等待的顧客平均數。 （3 3）有效到達率。）有效到達率。 （4 4）顧客在店內平均逗留的時間。）顧客在店內平均逗留的時間。 （5 5）顧客等待理發的平均時間。）顧客等待理發的平均時間。 （6 6）在可能到來的顧客中不等待就離開的概率。）在可能到來的顧客中不等待就離開的概率。 解：這個問題可以歸結為解：這個問題可以歸結為M/M/1/7/M/M/1/7/模型。顧客的平均到達模型。顧客的平均到達 率率3 3人人/ /小時，平均服務率小時，平均服務率4 4人人/ /小時。小時。 2778. 0 )4/3(1

36、4/31 , 4/3, 1 1 17 0 1 0 PP N （1 1）求）求 例例4 4 單人理發館有單人理發館有6 6個椅子接待人們排隊等待理發。當個椅子接待人們排隊等待理發。當6 6 個椅子都坐滿時，后來到的顧客不進店就離開。顧客平均個椅子都坐滿時，后來到的顧客不進店就離開。顧客平均 到達率為到達率為3 3人人/ /小時，每名顧客理發需時平均小時，每名顧客理發需時平均1515分鐘。分鐘。 解：這個問題可以歸結為解：這個問題可以歸結為M/M/1/7/M/M/1/7/模型。顧客的平均到達模型。顧客的平均到達 率率3 3人人/ /小時，平均服務率小時，平均服務率4 4人人/ /小時。小時。 )1

37、 ( 0 PLL sq 人11. 2 )4/3(1 )4/3(8 4/31 4/3 1 ) 1( 1 8 8 1 1 N N s N L 人39. 1)2778. 01 (11. 2 q L （2 2）需要等待的顧客平均數就是）需要等待的顧客平均數就是LqLq。 LsLs就是店內顧客的平均數就是店內顧客的平均數 （3 3）有效到達率）有效到達率ee。 小時人/89. 2)2778. 01 (4)1 ( 0 P e 例例4 4 單人理發館有單人理發館有6 6個椅子接待人們排隊等待理發。當個椅子接待人們排隊等待理發。當6 6 個椅子都坐滿時，后來到的顧客不進店就離開。顧客平均個椅子都坐滿時，后來到

38、的顧客不進店就離開。顧客平均 到達率為到達率為3 3人人/ /小時，每名顧客理發需時平均小時，每名顧客理發需時平均1515分鐘。分鐘。 解：這個問題可以歸結為解：這個問題可以歸結為M/M/1/7/M/M/1/7/模型。顧客的平均到達模型。顧客的平均到達 率率3 3人人/ /小時，平均服務率小時，平均服務率4 4人人/ /小時。小時。 （4 4）顧客在店內平均逗留的時間就是）顧客在店內平均逗留的時間就是WsWs。 分鐘小時8 .4373. 089. 2/11. 2/ ess LW （5 5）顧客等待理發的平均時間）顧客等待理發的平均時間WqWq， 分鐘8 .28158 .43 1 sq WW （

39、6 6）在可能到來的顧客中不等待就離開的概率。）在可能到來的顧客中不等待就離開的概率。 %7 . 32778. 0)4/3( 7 0 7 7 PP 4.3 M/M/1/m4.3 M/M/1/m模型模型( (顧客源是有限制的模型顧客源是有限制的模型) ) 這類排隊問題的主要特征就是顧客數有限，如只有這類排隊問題的主要特征就是顧客數有限，如只有m m個個 顧客。每個顧客來到系統中接受服務后仍回到原來的總體，顧客。每個顧客來到系統中接受服務后仍回到原來的總體， 還可能再來。還可能再來。 最典型的例子就是機器看管的問題。如一個工人同時最典型的例子就是機器看管的問題。如一個工人同時 看管看管m m臺機器

40、，當機器發生故障即停下來等待修理，修好后臺機器，當機器發生故障即停下來等待修理，修好后 再投入使用，但仍然可能再發生故障。類似的例子還有再投入使用，但仍然可能再發生故障。類似的例子還有m m個個 打字員共用一臺計算機，打字員共用一臺計算機，m m個終端共用一臺打印機等等。個終端共用一臺打印機等等。 關于顧客的平均到達率，在無限源的情形中是按全體關于顧客的平均到達率，在無限源的情形中是按全體 顧客來考慮的。而在有限源的情形下，必須按每一顧客來顧客來考慮的。而在有限源的情形下，必須按每一顧客來 考慮。假定每個顧客來到服務系統的時間間隔服從參數為考慮。假定每個顧客來到服務系統的時間間隔服從參數為 的

41、負指數分布，則的負指數分布，則表示單個顧客平均的到達率表示單個顧客平均的到達率( (其含義其含義 是指單位時間內該顧客來到系統請求服務的次數是指單位時間內該顧客來到系統請求服務的次數) )。當顧客。當顧客 總數為總數為m m，而系統內有，而系統內有n n個顧客時，顧客總的平均到達率為個顧客時，顧客總的平均到達率為 (m(mn)n). .因此顧客源有限的排隊模型也可以用生滅過程的因此顧客源有限的排隊模型也可以用生滅過程的 狀態轉移圖來表示。狀態轉移圖來表示。 m(m-1) (m-2) 2 mn mnnm n 0 ,.1 , 0)( mn n ,.1 , 0, mC mn nm m nmmm mm

42、nmnm C n nn n nn nn n n0 ,.,2 , 1,)( )!( ! )(1).(1( ) 1.()2() 1( . . 11 021 ， m(m-1) (m-2) 2 m n n n n nm m C P 0 0 0 )( )!( ! 11 mnP nm m P n n ,.,2 , 1,)( )!( ! 0 由于顧客的輸入率由于顧客的輸入率nn隨著系統的變化而變化的，因此有隨著系統的變化而變化的，因此有 效輸入率效輸入率ee可按下式計算?？砂聪率接嬎?。 )()()( 0000 s n n n n n n n nne LmnPmPPnmP )()1( 0se LmP , )1

43、 ()1 ( 00 P m P mLs )1 (,)1 ( 00 PLPLL e e ssq ess LW/ 1 / )(/ se e seqq WLLW 例例5 5某車間有某車間有5 5臺機器，每臺機器的連續運轉時間服從負指數臺機器，每臺機器的連續運轉時間服從負指數 分布，平均連續運轉時間分布，平均連續運轉時間1515分鐘，有一個修理工，每次修理時分鐘，有一個修理工，每次修理時 間服從負指數分布，平均每次間服從負指數分布，平均每次1212分鐘。分鐘。 解：解：m m5 5。1/151/15。1/121/12。 (1) (1) 修理工空閑的概率。修理工空閑的概率。 0073. 08 .136/

44、1 )8 . 0( ! 0 ! 5 )8 . 0( ! 1 ! 5 )8 . 0( ! 2 ! 5 )8 . 0( ! 3 ! 5 )8 . 0( ! 4 ! 5 )8 . 0( ! 5 ! 5 )( )!( ! 11 1 543210 0 0 0 m n n n n nm m C P (2) 5 (2) 5臺機器都出故障的概率。臺機器都出故障的概率。 287. 0)8 . 0( )!55( ! 5 0 5 5 PP 例例5 5某車間有某車間有5 5臺機器，每臺機器的連續運轉時間服從負指數臺機器，每臺機器的連續運轉時間服從負指數 分布，平均連續運轉時間分布，平均連續運轉時間1515分鐘，有一個

45、修理工，每次修理時分鐘，有一個修理工，每次修理時 間服從負指數分布，平均每次間服從負指數分布，平均每次1212分鐘。分鐘。 解：解：m m5 5。1/151/15。1/121/12。 (1) (1) 修理工空閑的概率。修理工空閑的概率。 0073. 0 0 P (2) 5 (2) 5臺機器都出故障的概率。臺機器都出故障的概率。 287. 0 5 P (3) (3) 出故障的平均臺數。出故障的平均臺數。 )(76. 3)0073. 01 ( 8 . 0 1 5 )1 ( 0 臺 P mLs (4) (4) 等待修理的平均臺數。等待修理的平均臺數。 )(77. 2)0073. 01 (76. 3)

46、1 ( 0 臺PLL sq ee(m-Ls)=(1/15)(5-3.76)=0.083(m-Ls)=(1/15)(5-3.76)=0.083 例例5 5某車間有某車間有5 5臺機器，每臺機器的連續運轉時間服從負指數臺機器，每臺機器的連續運轉時間服從負指數 分布，平均連續運轉時間分布，平均連續運轉時間1515分鐘，有一個修理工，每次修理時分鐘，有一個修理工，每次修理時 間服從負指數分布，平均每次間服從負指數分布，平均每次1212分鐘。分鐘。 解：解：m m5 5。1/151/15。1/121/12。 (1) (1) 修理工空閑的概率。修理工空閑的概率。 0073. 0 0 P (2) 5 (2)

47、 5臺機器都出故障的概率。臺機器都出故障的概率。 287. 0 5 P (3) (3) 出故障的平均臺數。出故障的平均臺數。 )(76. 3臺 s L (4) (4) 等待修理的平均臺數。等待修理的平均臺數。 )(77. 2臺 q L ee0.0830.083 (5) (5) 平均的機器停工時間。平均的機器停工時間。 分鐘46083. 0/76. 3/ ess LW (6) (6) 平均的等待修理時間。平均的等待修理時間。 分鐘341246 1 sq WW 例例5 5某車間有某車間有5 5臺機器，每臺機器的連續運轉時間服從負指數臺機器，每臺機器的連續運轉時間服從負指數 分布，平均連續運轉時間分

48、布，平均連續運轉時間1515分鐘，有一個修理工，每次修理時分鐘，有一個修理工，每次修理時 間服從負指數分布，平均每次間服從負指數分布，平均每次1212分鐘。分鐘。 解：解：m m5 5。1/151/15。1/121/12。 (1) (1) 修理工空閑的概率。修理工空閑的概率。 0073. 0 0 P (2) 5 (2) 5臺機器都出故障的概率。臺機器都出故障的概率。 287. 0 5 P (3) (3) 出故障的平均臺數。出故障的平均臺數。 )(76. 3臺 s L (4) (4) 等待修理的平均臺數。等待修理的平均臺數。 )(77. 2臺 q L ee0.0830.083 (5) (5) 平

49、均的機器停工時間。平均的機器停工時間。分鐘46 s W (6) (6) 平均的等待修理時間。平均的等待修理時間。分鐘34 q W (7) (7)工人的忙期工人的忙期 1-P0=1-0.00730.9927。 從這個概率可以看出工人幾乎沒有空閑時間，而且機器停工的從這個概率可以看出工人幾乎沒有空閑時間，而且機器停工的 時間太長時間太長WsWs4646分鐘，所以應當提高服務率減少修理時間或者增加分鐘，所以應當提高服務率減少修理時間或者增加 修理工人。修理工人。 5 5 多服務臺排隊系統模型多服務臺排隊系統模型(M/M/C)(M/M/C) M/M/C M/M/C系統是指顧客按系統是指顧客按泊松流輸入

50、泊松流輸入, ,服務時間為負指數服務時間為負指數 分布分布, ,有有C C個服務臺的單隊多臺并列服務系統。它的結構如個服務臺的單隊多臺并列服務系統。它的結構如 圖圖. .在這種系統在這種系統, ,顧客到達系統后排成一個隊列，然后到能顧客到達系統后排成一個隊列，然后到能 給以服務的服務臺接受服務給以服務的服務臺接受服務, ,而每個服務臺的服務時間都服而每個服務臺的服務時間都服 從相同參數從相同參數的負指數分布的負指數分布, ,服務完畢后顧客自動離去服務完畢后顧客自動離去 由于顧客的到達間隔和服務時間都服從負指數分布由于顧客的到達間隔和服務時間都服從負指數分布,所所 以這種系統象以這種系統象M/M

51、/1M/M/1系統一樣系統一樣, ,能直接利用生滅過程的計算能直接利用生滅過程的計算 方法計算穩態概率方法計算穩態概率. .下面分別討論下面分別討論M/M/CM/M/C模型的幾種模型模型的幾種模型. . 5.1 M/M/C/5.1 M/M/C/ /模型模型 這是系統對顧客無限制這是系統對顧客無限制, ,顧客源也無限制的多服務臺模顧客源也無限制的多服務臺模 型型, ,其狀態轉移圖如下其狀態轉移圖如下: : 0 01 12 2 c-1c-1 c cc+1c+1 ,.2 , 1 , 0,n n Cn CC cn n C cn n n nn nn n 當 當 , ! )( 1,.,2 , 1, ! )

52、( . . 11 021 CnC Cnn n 當 當 , 1,.,2 , 1, 5.1 M/M/C/5.1 M/M/C/ /模型模型 這是系統對顧客無限制這是系統對顧客無限制, ,顧客源也無限制的多服務臺模顧客源也無限制的多服務臺模 型型, ,其狀態轉移圖如下其狀態轉移圖如下: : 0 01 12 2 c-1c-1 c cc+1c+1 ,.2 , 1 , 0,n n CnC Cnn n 當 當 , 1,.,2 , 1, 1,.,2 , 1, ! )( ! 2.) 1(. . 11 021 cn nn nn C n n n n nn nn n 當 5.1 M/M/C/5.1 M/M/C/ /模型

53、模型 這是系統對顧客無限制這是系統對顧客無限制, ,顧客源也無限制的多服務臺模顧客源也無限制的多服務臺模 型型, ,其狀態轉移圖如下其狀態轉移圖如下: : 0 01 12 2 c-1c-1 c cc+1c+1 ,.2 , 1 , 0,n n CnC Cnn n 當 當 , 1,.,2 , 1, Cn CC CC C cn n ccncn n nn nn n 當, ! )( !. . 11 021 5.1 M/M/C/5.1 M/M/C/ /模型模型 這是系統對顧客無限制這是系統對顧客無限制, ,顧客源也無限制的多服務臺模顧客源也無限制的多服務臺模 型型, ,其狀態轉移圖如下其狀態轉移圖如下:

54、: 0 01 12 2 c-1c-1 c cc+1c+1 ,.2 , 1 , 0,n n Cn CC cn n C cn n n nn nn n 當 當 , ! )( 1,.,2 , 1, ! )( . . 11 021 CnC Cnn n 當 當 , 1,.,2 , 1, 設設= =/c/c1 1時時, ,系統無穩定狀態系統無穩定狀態) )則則: : 1 0 1 0 0 1 1 ! )( ! )( 11 c n cn c ncn nn Cn CC P CnP CC cnP n PCP cn n n nn 當 當 , ! )( 1,.,2 , 1, ! )( 0 0 0 2 0 )1 ( !

55、)( )( C Pc PcnL c cn nq 設設= =/c/c1 1時時, ,系統無穩定狀態系統無穩定狀態) )則則: : 2 00 0 0 1 0 0 0 0 0 0 0 0 0 0 0 00 )1 ( ! )( ) 1 1 ( ! )( ! ! )( ! )( ! )( ! )( )( C Pu C PC C PC j C PC j C PC P C C j P CC c jP CCC C j P CC jjPPcnL ccc j j cc j j cc j j cccjc j c jc j jcj jcjc j j jc jj jc cn nq cnj令 設設= =/c/c1 1時時

56、, ,系統無穩定狀態系統無穩定狀態) )則則: : 1 0 1 0 0 1 1 ! )( ! )( 11 c n cn c ncn nn Cn CC P CnP CC cnP n PCP cn n n nn 當 當 , ! )( 1,.,2 , 1, ! )( 0 0 0 2 0 )1 ( ! )( )( C Pu PcnL c cn nq / qs LL /LsWs /1/ Sqq WLW 例例6.6.某售票處有三個窗口某售票處有三個窗口, ,顧客的到達服從泊松過程顧客的到達服從泊松過程, ,平均平均 到達率是每分鐘到達率是每分鐘=0.9=0.9人人, ,假定每次服務的時間服從負指數分假定每

57、次服務的時間服從負指數分 布布, ,平均服務率是每分鐘平均服務率是每分鐘=0.4=0.4人人. . (1)(1)整個窗口的空閑概率整個窗口的空閑概率 0748. 0 75. 01 1 ! 3 )25. 2( ! 2 )25. 2( ! 1 )25. 2( ! 0 )25. 2( 1 1 1 ! )( ! )( 1 3210 1 0 0 c n cn Cn P 售票窗口處有一個顧客的概率售票窗口處有一個顧客的概率 0748. 025. 2)( ! )( 010 PPP n P n n 75. 0 c (2)(2)平均隊長平均隊長 顧客在買票過程平均停留的時間顧客在買票過程平均停留的時間 70.

58、10748. 0 )4/ 1 ( ! 3 4/ 3)25. 2( )1 (! )( 2 3 2 0 C Pc L c q 售票窗口買票的以及排隊等待的總平均人數售票窗口買票的以及排隊等待的總平均人數 95. 325. 270. 1/ qs LL (3)(3)平均顧客排隊等待買票的平均時間平均顧客排隊等待買票的平均時間 )(89. 19 . 0/70. 1/分鐘 qq LW )(39. 49 . 0/95. 3/分鐘LsWs 顧客到達后必須等待的概率顧客到達后必須等待的概率 57. 0)( ! 2 1 )(1 1)3( 0 2 00 210 PPP PPPnP 5.2 M/M/C5.2 M/M/

59、C型系統和型系統和c c個個M/M/1M/M/1型系統比較型系統比較 結合剛才的例子結合剛才的例子, ,如果原問題中其他條件都不變如果原問題中其他條件都不變, ,但顧客到但顧客到 達以后在每個售票窗口前各排一隊達以后在每個售票窗口前各排一隊, ,且進入隊列后堅持不變且進入隊列后堅持不變,這這 就形成了就形成了3 3個個M/M/1M/M/1型系統型系統, ,而每個隊列的平均到達率是而每個隊列的平均到達率是 1 1=2 2=3 3=0.9/3=0.3(=0.9/3=0.3(人人/ /分鐘分鐘).).計算這個計算這個M/M/1M/M/1模型模型, ,并于并于 M/M/3M/M/3模型比較模型比較,

60、,結果如下表結果如下表: : M/M/1M/M/1型型M/M/3M/M/3型型 服務臺空閑的概率服務臺空閑的概率P P0 00.250.250.07480.0748 顧客必須等待的概率顧客必須等待的概率0.750.75P(NP(N33)=0.57)=0.57 平均隊長平均隊長Lq Lq 2.252.251.701.70 平均顧客數平均顧客數LsLs 9.009.00或或3.003.003.953.95 平均逗留時間平均逗留時間WsWs 1010分鐘分鐘4.394.39分鐘分鐘 平均等待時間平均等待時間WqWq 7.57.5分鐘分鐘1.891.89分鐘分鐘 5.2 M/M/C5.2 M/M/C型