1、12 排隊論簡介： 排隊論(Queuing Theory)，又稱隨機服務系統理論(Random Service System Theory),是運籌學的一個主要分支，是一門研究擁擠現象(排隊、等待)的科學。具體地說，它是在研究各種排隊系統概率規律性的基礎上，解決相應排隊系統的最優設計和最優控制問題。主要包含以下三個方面的研究內容： (1)性態問題，即研究各種排隊系統的概率規律性，如隊長、等待時間、忙期等要素滿足的分布。有瞬態和穩態兩種情況。 (2)最優化問題，包括最優設計下的靜態最優和現有排隊系統的最優運營下的動態最優。 (3)排隊系統的統計推斷，即判斷一個給定的排隊系統符合何種模型，以便進一

2、步根據排隊理論進行分析研究。 前前 言言3 起源于起源于19091909年在丹麥哥本哈根電子公司工作的電話工程年在丹麥哥本哈根電子公司工作的電話工程師師A. K. Erlang(A.KA. K. Erlang(A.K. .愛爾朗愛爾朗) )對電話通話擁擠問題的研究工作，對電話通話擁擠問題的研究工作，其開創性論文其開創性論文-概率論和電話通訊理論則標志此理論的誕生。概率論和電話通訊理論則標志此理論的誕生。表明了排隊論的發展最早是與電話，通信中的問題相聯系的，表明了排隊論的發展最早是與電話，通信中的問題相聯系的，并到現在也還是排隊論的傳統的應用領域。近年來在計算機通并到現在也還是排隊論的傳統的應用

3、領域。近年來在計算機通訊網絡系統、交通運輸、醫療衛生系統、各類生產服務、庫存訊網絡系統、交通運輸、醫療衛生系統、各類生產服務、庫存管理等等各領域中均得到廣泛的應用。管理等等各領域中均得到廣泛的應用。 排隊論歷史： 排隊是我們在日常生活和生產中經常遇到的現象。例如：搭乘公共排隊是我們在日常生活和生產中經常遇到的現象。例如：搭乘公共汽車；顧客到商店購買物品；病員到醫院看病；旅客到售票處購買車票；汽車；顧客到商店購買物品；病員到醫院看病；旅客到售票處購買車票；學生去食堂就餐等就常常出現排隊和等待現象。除了上述學生去食堂就餐等就常常出現排隊和等待現象。除了上述有形的排隊有形的排隊之外，之外，還有大量的

4、所謂還有大量的所謂“無形無形”排隊排隊現象，如幾個顧客打電話到出租汽車站要求現象，如幾個顧客打電話到出租汽車站要求派車，如果出租汽車站無足夠車輛、則部分顧客只得在各自的要車處等待，派車，如果出租汽車站無足夠車輛、則部分顧客只得在各自的要車處等待，他們分散在不同地方，卻形成了一個無形隊列在等待派車。排隊的不一定他們分散在不同地方，卻形成了一個無形隊列在等待派車。排隊的不一定是人，也可以是物：例如：通訊衛星與地面若干待傳遞的信息；生產線上是人，也可以是物：例如：通訊衛星與地面若干待傳遞的信息；生產線上的原料、半成品等待加工；因故障停止運轉的機器等待工人修理；碼頭的的原料、半成品等待加工；因故障停止

5、運轉的機器等待工人修理；碼頭的船只等待裝卸貨物；要降落的飛機因跑道不空而在空中盤旋等等。船只等待裝卸貨物；要降落的飛機因跑道不空而在空中盤旋等等。 排隊論具體事例： 4 上述事例中的各種問題雖互不相同，但卻都上述事例中的各種問題雖互不相同，但卻都有要求得到某種服務的人或物和提供服務的人或有要求得到某種服務的人或物和提供服務的人或機構。排隊論里把要求服務的對象統稱為機構。排隊論里把要求服務的對象統稱為“顧顧客客”, ,而把提供服務的人或機構稱為而把提供服務的人或機構稱為“服務臺服務臺”或或“服務員服務員”。不同的顧客與服務組成了各式各樣。不同的顧客與服務組成了各式各樣的服務系統。顧客為了得到某種

6、服務而到達系統、的服務系統。顧客為了得到某種服務而到達系統、若不能立即獲得服務而又允許排隊等待，則加入若不能立即獲得服務而又允許排隊等待，則加入等待隊伍，待獲得服務后離開系統。等待隊伍，待獲得服務后離開系統。5模型模型1 1 單服務臺排隊模型單服務臺排隊模型排隊模型及類型排隊模型及類型 根據顧客到達和服務臺數，排隊過程可用下列模型表示：模型模型2 2 單隊列多服務臺并聯的排隊模型單隊列多服務臺并聯的排隊模型6模型模型3 3 多隊列多服務臺的并聯排隊模型多隊列多服務臺的并聯排隊模型模型模型4 4 單隊多個服務臺的串聯排隊模型單隊多個服務臺的串聯排隊模型7 模型模型5 5 多隊列多服務臺混聯網絡模

7、型多隊列多服務臺混聯網絡模型縱觀上述排隊模型，實際上都可由下面模型加以統一描述：縱觀上述排隊模型，實際上都可由下面模型加以統一描述： 稱該統一模型為隨機聚散服務系統。稱該統一模型為隨機聚散服務系統。由于顧客到來的時刻和服務臺提由于顧客到來的時刻和服務臺提供服務的時間長短都是隨機的，因此供服務的時間長短都是隨機的，因此任一排隊系統都是一個隨機聚散任一排隊系統都是一個隨機聚散服務系統。服務系統。 “聚聚”表示顧客的到達表示顧客的到達,“,“散散”表示顧客的離去。表示顧客的離去。8 面對擁擠現象，人們總是希望盡量設法減少排隊，面對擁擠現象，人們總是希望盡量設法減少排隊，通常的做法是增加服務設施，但是

8、增加的數量越多，通常的做法是增加服務設施，但是增加的數量越多，人力、物力的支出就越大，甚至會出現空閑浪費，如人力、物力的支出就越大，甚至會出現空閑浪費，如果服務設施太少，顧客排隊等待的時間就會很長，這果服務設施太少，顧客排隊等待的時間就會很長，這樣對顧客會帶來不良影響。樣對顧客會帶來不良影響。 顧客排隊時間的長短與服務設施規模的大小，就顧客排隊時間的長短與服務設施規模的大小，就構成了設計隨機服務系統中的一對矛盾。構成了設計隨機服務系統中的一對矛盾。 如何做到既保證一定的服務質量指標，又使服務如何做到既保證一定的服務質量指標，又使服務設施費用經濟合理，恰當地解決顧客排隊時間與服務設施費用經濟合理

9、，恰當地解決顧客排隊時間與服務設施費用大小這對矛盾。這就是隨機服務系統理論設施費用大小這對矛盾。這就是隨機服務系統理論排隊論所要研究解決的問題。排隊論所要研究解決的問題。9 一、排隊系統的組成與特征一、排隊系統的組成與特征 排隊系統一般有三個基本組成部分：排隊系統一般有三個基本組成部分：1.1.輸輸入過程；入過程；2.2.排隊規則；排隊規則；3.3.服務機構。如下圖所服務機構。如下圖所示：示： 排隊系統的基本概念排隊系統的基本概念10 1、輸入過程 輸入即為顧客的到達，可有下列情況：輸入即為顧客的到達，可有下列情況： 1 1）顧客源可能是有限的，也可能是無限的。）顧客源可能是有限的，也可能是無

10、限的。 2 2）顧客是成批到達或是單個到達。）顧客是成批到達或是單個到達。 3 3）顧客到達間隔時間可能是隨機的或確定的。）顧客到達間隔時間可能是隨機的或確定的。 4 4）顧客到達可能是相互獨立或關聯的。所謂獨）顧客到達可能是相互獨立或關聯的。所謂獨立就是以前顧客的到達對以后顧客的到達無影響。立就是以前顧客的到達對以后顧客的到達無影響。 5 5）輸入過程可以是平穩的，也可以是非平穩的。）輸入過程可以是平穩的，也可以是非平穩的。輸入過程平穩的是指顧客相繼到達的間隔時間分布和輸入過程平穩的是指顧客相繼到達的間隔時間分布和參數（均值、方差）與時間無關；非平穩的則是與時參數（均值、方差）與時間無關；非

11、平穩的則是與時間相關，非平穩的處理比較困難。間相關，非平穩的處理比較困難。11 這是指服務臺從隊列中選取顧客進行服務的順這是指服務臺從隊列中選取顧客進行服務的順序。可以分為序。可以分為損失制、等待制、混合制損失制、等待制、混合制3 3大類。大類。 (1)(1)損失制。損失制。這是指如果顧客到達排隊系統時，這是指如果顧客到達排隊系統時，所有服務臺都已被先來的顧客占用，那么他們就自所有服務臺都已被先來的顧客占用，那么他們就自動離開系統永不再來。動離開系統永不再來。 典型例子是，如電話拔號后出現忙音，顧客不典型例子是，如電話拔號后出現忙音，顧客不愿等待而自動掛斷電話，如要再打，就需重新拔愿等待而自動

12、掛斷電話，如要再打，就需重新拔號，這種服務規則即為損失制。號，這種服務規則即為損失制。 2 2、排隊規則、排隊規則12 (2)(2)等待制等待制。指當顧客來到系統時，所有服務臺。指當顧客來到系統時，所有服務臺都不空，顧客加入排隊行列等待服務。都不空，顧客加入排隊行列等待服務。 例如，排隊等待售票，故障設備等待維修等。例如，排隊等待售票，故障設備等待維修等。 等待制中，服務臺在選擇顧客進行服務時，常有等待制中，服務臺在選擇顧客進行服務時，常有如下四種規則：如下四種規則： 先到先服務（先到先服務（FCFS FCFS ）。按顧客到達的先后順。按顧客到達的先后順序對顧客進行服務，這是最普遍的情形。序對

13、顧客進行服務，這是最普遍的情形。 后到先服務（后到先服務（LCFSLCFS）。倉庫中迭放的鋼材，。倉庫中迭放的鋼材，后迭放上去的都先被領走，就屬于這種情況。后迭放上去的都先被領走，就屬于這種情況。13 隨機服務隨機服務(RAND) 。即當服務臺空閑。即當服務臺空閑時，不按照排隊序列而隨意指定某個顧客去時，不按照排隊序列而隨意指定某個顧客去接受服務，如電話交換臺接通呼叫電話就是接受服務，如電話交換臺接通呼叫電話就是一例。一例。 優先權服務優先權服務(PR)。如老人、兒童先進。如老人、兒童先進車站；危重病員先就診；遇到重要數據需要車站；危重病員先就診；遇到重要數據需要處理計算機立即中斷其他數據的處

14、理等，均處理計算機立即中斷其他數據的處理等，均屬于此種服務規則。屬于此種服務規則。14 (3)(3)混合制混合制這是等待制與損失制相結合的一種服務規則，一般是指允許排隊，但又不允許隊列無限長下去。具體說來，大致有三種： 隊長有限。隊長有限。當排隊等待服務顧客人數超過規定數量時，后來顧客就自動離去，另求服務，即系統的等待空間是有限的。例如最多只能容納N個顧客在系統中，當新顧客到達時，若系統中的顧客數(又稱為隊長)小于N，則可進入系統排隊或接受服務；否則，便離開系統，并不再回來。再如水庫的庫容是有限的，旅館的床位是有限的。15 等待時間有限等待時間有限。即顧客在系統中的。即顧客在系統中的等待時間不

15、超過某一給定的長度等待時間不超過某一給定的長度T T，當等待，當等待時間超過時間超過T T時，顧客自動離去，不再回來。時，顧客自動離去，不再回來。 如易損壞的電子元器件的庫存問題，如易損壞的電子元器件的庫存問題，超過一定存儲時間被自動認為失效。超過一定存儲時間被自動認為失效。 又如顧客到飯館就餐，等了一定時間后又如顧客到飯館就餐，等了一定時間后不愿再等而自動離去另找飯店用餐。不愿再等而自動離去另找飯店用餐。16 逗留時間逗留時間( (等待時間與服務時間之和等待時間與服務時間之和) )有有限。限。 例如用高射炮射擊敵機，當敵機飛越高射例如用高射炮射擊敵機，當敵機飛越高射炮射擊有效區域的時間為炮射

16、擊有效區域的時間為t t時，若在這個時間時，若在這個時間內未被擊落，也就不可能再被擊落了。內未被擊落，也就不可能再被擊落了。 不難注意到，損失制和等待制可看成是混不難注意到，損失制和等待制可看成是混合制的特殊情形，如記合制的特殊情形，如記c c為系統中服務臺的個為系統中服務臺的個數，則當數，則當K=cK=c 時，混合制即成為損失制；當時，混合制即成為損失制；當K=K=時，混合制即成為等待制。時，混合制即成為等待制。173 3、服務臺、服務臺 服務臺可以從以下3方面來描述： (1) 服務臺數量及構成形式服務臺數量及構成形式。從數量上說，服務臺有單服務臺和多服務臺之分。從構成形式上看，服務臺有：單

17、隊單服務臺式； 單隊多服務臺并聯式； 多隊多服務臺并聯式； 單隊多服務臺串聯式； 單隊多服務臺并串聯混合式,以及多隊列多服務臺并串聯混合式等等。 如之前的分類模型圖所示。如之前的分類模型圖所示。18 (2) 服務方式服務方式。這是指在某一時刻接受服務的顧客數，它有單個服務和成批服務兩種。如公共汽車一次就可裝載一批乘客就屬于成批服務。 (3) 服務時間的分布服務時間的分布。一般來說，在多數情況下，對每一個顧客的服務時間是一隨機變量，其概率分布有定長分布、負指數分布、K階愛爾朗分布、一般分布(所有顧客的服務時間都是獨立同分布的)等等。19排隊系統的描述符號與模型分類排隊系統的描述符號與模型分類 為

18、了區別各種排隊系統，根據輸入過程、排隊規則和服務機制的變化對排隊模型進行描述或分類，可給出很多排隊模型(見前面分析與圖示)。為了方便對眾多模型的描述,DG肯道爾（DGKendall）提出了一種目前在排隊論中被廣泛采用的“Kendall記號”，完整的表達方式通常用到6個符號并取如下固定格式：X X/Y/Z/A/B/C/Y/Z/A/B/C 各符號的意義如下：X X-表示顧客相繼到達間隔時間分布，表示顧客相繼到達間隔時間分布，常用下列符號：常用下列符號： M M表示到達過程為泊松過程或表示到達過程為泊松過程或( (負指數分布負指數分布Markov)Markov)； D D表示定長輸入表示定長輸入(

19、(確定型分布確定型分布Deterministic)Deterministic)； E EK K表示表示k k階愛爾朗分布；階愛爾朗分布； GI GI 一般相互獨立的隨機分布一般相互獨立的隨機分布(General Independent)(General Independent) G G表示一般的隨機分布。表示一般的隨機分布。20 Y Y-表示服務時間分布，表示服務時間分布，所用符號與表示顧客到達間隔時間分布相同。所用符號與表示顧客到達間隔時間分布相同。 Z-Z-表示服務臺表示服務臺( (員員) )個數：個數：“1”1”則表示單個服務臺，則表示單個服務臺，“s”s”。(s(s1)1)表表示多個服

20、務臺。示多個服務臺。 A-A-表示系統中顧客容量限額，表示系統中顧客容量限額，或稱等待空間容量；或稱等待空間容量； 如系統有如系統有K K個等待位子，則個等待位子，則 0K0K0),P(t0),Pn n(t1,t2)(t1,t2)表示在時間區間表示在時間區間t1,t2)(t2t1)t1,t2)(t2t1)內有內有n(0)n(0)個顧客到達的概率。即：個顧客到達的概率。即：)()(,1221ntNtNPttPn （t2t1，n0） 當當P Pn n(t1,t2)(t1,t2)同時符合下述三個條件時，顧客到達過程就是同時符合下述三個條件時，顧客到達過程就是泊松過程泊松過程( (顧客到達形成顧客到達

21、形成泊松泊松流流) )。 1 1、泊松分布、泊松分布27 無后效性：無后效性：各區間的到達相互獨立各區間的到達相互獨立, ,即即MarkovMarkov性。性。. . . . . . . t0 t1 t2 tn-1 tn|)(|)(11112211)()(,.,)(,)(nnnnxtxnxtxxtxxtxnntxPntxP 也就是說過程在也就是說過程在t+tt+t所處的狀態與所處的狀態與t t以前所處的狀以前所處的狀態無態無關。關。 平穩性：平穩性：即對于足夠小的即對于足夠小的tt，有：，有：)()(tttttP ，1泊松流具有如下特性：泊松流具有如下特性： 在在t,t+tt,t+t內有一個顧

22、客到達的概率與內有一個顧客到達的概率與t t無關無關, ,而與而與tt成正比。成正比。28 普通性：普通性：對充分小的對充分小的t,t,在時間區間（在時間區間（t,t+tt）內有內有2 2個或個或2 2個以上顧客到達的概率是一高階無窮小個以上顧客到達的概率是一高階無窮小. . 由此知，在由此知，在(t，t+t)t)區間內沒有顧客到達的概率為：區間內沒有顧客到達的概率為：)(1),(0tottttP 令令t1 1=0,t=0,t2 2=t,=t,則則P(tP(t1 1,t,t2 2)=P)=Pn n(0,t)=P(0,t)=Pn n(t)(t) 0 0 是常數，它是常數，它表示單位時間到達的顧客

23、數，稱表示單位時間到達的顧客數，稱為概率強度。為概率強度。2)(),(nntotttP 即即 P P0 0+P+P1 1+P+P22=1=1 下面將討論求關鍵的下面將討論求關鍵的P Pn n(t(t) )。 29情情 形形 0 0， t t) ) 概概 率率 t t， t t+ + t t) ) 概概 率率 0 0， t t+ + t t ） A A n n P Pn n( (t t) ) 0 0 1 1- - t t + + O O( ( t t) ) P Pn n( (t t) )( (1 1- - t t + + O O( ( t t) ) ) B B n n- -1 1 P Pn n-

24、 -1 1( (t t) ) 1 1 t t P Pn n- -1 1( (t t) ) t t n n- -2 2 P Pn n- -2 2( (t t) ) 2 2 n n- -3 3 P Pn n- -3 3( (t t) ) 3 3 . . . . . . . . . . . . C C 0 0 P P0 0( (t t) ) n O O( ( t t) ) O O( ( t t) ) 在在00，t+tt+t內到達內到達n n個顧客應是上面三種互不相個顧客應是上面三種互不相容的情況之一，所以有：容的情況之一，所以有： 為了求為了求Pn(t),即即Pn(0,t)，需要研究它在（，需要研究

25、它在（t，t+tt）上的改變）上的改變量量, ,建立建立P Pn n(t)(t)的微分方程。對于區間的微分方程。對于區間0,0,t+t)+t)可以分成可以分成00，t)t)和和tt，t+t),t+t),其到達總數是其到達總數是n n，不外有下列三種情況：，不外有下列三種情況：00,()0,nnnn kkkPttP ttPt P t tt30 令令t0t0取極限（并注意初始條件）得：取極限（并注意初始條件）得：)()()(1tPtPdttdPnnn (3)(3) 當當n=0時，沒有時，沒有B，C兩種情況，則：兩種情況，則：)()(00tPdttdP1)0(0P (4)(4)()()1)()(1t

26、OttPttPttPnnn)()()()()(1tOttPttPtPttPnnnnttOtPtPttPttPnnnn)()()()()(1 湊微分湊微分 區間長度（區間長度（0 0，0 0）有有n n個顧客到達個顧客到達 (0,t)(0,t)有有n-1,n-2n-1,n-2個個顧客到達顧客到達(0)0nP 即：即：31ln10tCC C C = 0= 00ln( )Ptt （3 3）式兩端乘）式兩端乘e e t t并移項得：并移項得： te)t(P 0 (5)(5) （沒有顧客到達的概率）（沒有顧客到達的概率）dtPtdP )()(0000ln( )P ttC 兩邊積分得：兩邊積分得： 代入初

27、始條件代入初始條件( (t=0)t=0)有有： P P0 0(0)=1(0)=1)t(P)t(Pdt)t(dPnnn1 )()(00tPdttdP(0)0nP32 將將n=1,2,3代入（代入（6）得：）得：tntnetPetPdtd )()(1 11101)()(dtetPetPtnttn (6)(6)110011)()(dtetPetPttt (注意利用注意利用(5)式式)tdteettt 1011tntntne )t (Pe )t (Pedt)t (dP 1tntnnte )t(Pe )t(Pdt)t(dPe 1 湊成湊成P Pn n(t)e(t)e t t兩兩項乘積的微分項乘積的微分

28、兩邊積分兩邊積分te)t(P 033 如此繼續遞推下去得：如此繼續遞推下去得：tettP !2)()(22 （2 2個顧客到達的概率）個顧客到達的概率） （n n個顧客到達的概率）個顧客到達的概率）tnnenttP !)()( 即隨機變量即隨機變量N(t)=n服從泊松分布。它的數學期望服從泊松分布。它的數學期望和方差為：和方差為：ttetP )(1 （1 1個顧客到達的概率）個顧客到達的概率）11011102111)()(dteetdtetPetPtttttt 2221t 34 引入級數引入級數.!nx.!xxenx 212 tkke!k)t( 0!)()()(11ntnetnPtNEnntn

29、n )!1()(11 nttennt 令令k=n-1，則：，則：!)()(0kttetNEkkt tetetNEtt )(352121)()!1()()!2()(tntntttennnt tttttettett 22)()1()1(ttar )(N(V 即即：21221)(!)()()(tntnnettPnnntnn 22E(N(t)EN(t)( tNVar 同理方差為：同理方差為：211121)()!1()()!1()() 1()()!1()(tntntntetntnnennntnnt 說明顧客到達過程確實是一個說明顧客到達過程確實是一個泊松過程泊松過程( (泊松泊松流流) )，這也是泊松分

30、布的數學推導。這也是泊松分布的數學推導。36 其概率密度函數為：其概率密度函數為：tTTedtdF)t(f t0t02 2、負指數分布、負指數分布 當輸入過程是泊松流時，我們研究兩顧客相繼到當輸入過程是泊松流時，我們研究兩顧客相繼到達的時間間隔的概率分布。達的時間間隔的概率分布。 設設T T為時間間隔，分布函數為為時間間隔，分布函數為F FT T（t t），則：），則：F FT T（t t）=PTt=PTt 此概率等價于在此概率等價于在0,t)0,t)區間內至少有區間內至少有1 1個顧客到達個顧客到達的概率。的概率。tTetPtF 1)(1)(0 t0t0tetP)(0 沒有顧客到達的概率沒有

31、顧客到達的概率為：為： (由（由（5）式而來）式而來) 間隔：間隔： 間隔：間隔： 間隔間隔 對分布函對分布函數微分數微分37 表示單位時間內顧客平均到達數。表示單位時間內顧客平均到達數。 1/表示顧客到達的平均間隔時間。表示顧客到達的平均間隔時間。 可以證明，間隔時間可以證明，間隔時間T T獨立且服從負指數分布與獨立且服從負指數分布與顧客到達形成泊松流是等價的。負指數分布是一種無顧客到達形成泊松流是等價的。負指數分布是一種無記憶性的分布。記憶性的分布。對顧客的服務時間對顧客的服務時間 ：系統處于忙期時系統處于忙期時兩顧客相繼離兩顧客相繼離開系統的時間間隔開系統的時間間隔，一般地也服從負指數分

32、布。，一般地也服從負指數分布。 即即T服從負指數分布，它的期望及方差為：服從負指數分布，它的期望及方差為： 1TE21 TVar 接受服務，然后離開接受服務，然后離開服務時間的分布：服務時間的分布：即：即：P(Xt+s|XP(Xt+s|Xt)=P(Xs)t)=P(Xs)38其中：其中：表示單位時間內能被服務的顧客數，即平均表示單位時間內能被服務的顧客數，即平均 服務率。服務率。 1/1/表示一個顧客的平均服務時間。表示一個顧客的平均服務時間。3 3、愛爾朗、愛爾朗(Erlang)(Erlang)分布分布 設設v v1 1, v, v2 2，, v, vk k是是k k個獨立的隨機變量，服從相同

33、個獨立的隨機變量，服從相同參數參數 k k 的負指數分布，那么：的負指數分布，那么：tetF 1)(tetf )( ，則，則 令令 ，則，則稱為服務強度稱為服務強度。kT 21 令令39 串列串列k k個服務臺個服務臺，每臺服務時間相互獨立，服從，每臺服務時間相互獨立，服從相同負指數分布（參數相同負指數分布（參數k k ），那么一顧客走完），那么一顧客走完k k個服個服務臺總共所需要服務時間服從上述務臺總共所需要服務時間服從上述k k階階ErlangErlang分布。分布。011 te)!k()kt(k)t (ftkkk 則稱則稱T服從服從k階階愛爾朗分布。其特征值為：愛爾朗分布。其特征值為：

34、 1TE21 kTVar ,其概率密度是其概率密度是1/ k1/ k表示一個顧客一個服務臺的平均服務時間。表示一個顧客一個服務臺的平均服務時間。 其他常用的分布參見教材其他常用的分布參見教材P122-123P122-123，也可參見概，也可參見概率論與數理統計相關教程。率論與數理統計相關教程。40生滅過程生滅過程1、生滅過程簡介、生滅過程簡介 一類非常重要且廣泛存在的排隊系統是生滅過程排隊系統。生滅過程是一類特殊的隨機過程，在生物學、物理學、運籌學中有廣泛的應用。 2 2、生滅過程的定義、生滅過程的定義 設N(t),t0 為一個隨機過程。 如N(t)的概率分布具有以下性質： (1)假設N(t)

35、=n，則從時刻t起到下一個顧客到達時刻止的時間服從參數為n的負指數分布，n=0，1，2，。間隔時間分布間隔時間分布 (2)假設N(t)=n，則從時刻t起到下一個顧客離去時刻止的時間服從參數為n的負指數分布，n=0，1，2，。服務時間分布服務時間分布 (3)同一時刻只有一個顧客到達或離去。 則稱設N(t),t0 為一個生滅過程。41 顧客到達“生”； 顧客離開“滅” n ， n ，生滅過程示意圖：顧客到達顧客到達顧客離去顧客離去42 一般說來，得到 是比較困難的或非理論作用不太大，因此通常是求當系統達到平穩狀態后的狀態分布，記為 , n=0,1,2, 為求平穩分布 ，考慮系統在 t+t 時刻可能

36、處的任一狀態n的概率。可給出狀態轉移圖如下：np( )( )( )nN tp tP N tn的分布np狀態轉移圖狀態轉移圖 說明：說明：n n狀態下，排隊系統中的人數穩定為狀態下，排隊系統中的人數穩定為n,nn,n=0,1,2,=0,1,2,.,.,即進了多少個就要出去多少個。即進了多少個就要出去多少個。43方式方式 t t時刻狀態時刻狀態t t狀態的狀態的概率概率（t,t+tt,t+t）內發生）內發生的事件的事件發生的概率發生的概率1n nP Pn n(t(t) )0 0人到達，人到達，0 0人離去人離去 （1-n nt） (1-n nt) 2n -1n -1P Pn-1n-1(t)(t)1

37、 1人到達，人到達，0 0人離去人離去 n-1n-1t (1-n-1n-1t) 3n +1n +1P Pn+1n+1(t)(t)0 0人到達，人到達，1 1人離去人離去(1-n+1n+1t) n+1n+1t 4n nP Pn n(t(t) )1 1人到達，同時人到達，同時1 1人離人離去去(n nt) (n nt) 各種方式下發生概率表（保證各種方式下發生概率表（保證n狀態狀態:t+tt時刻時刻穩定有穩定有n個人）個人） 說明：狀態說明：狀態n n下，下，1 1人到達的概率約為人到達的概率約為 n ntt，1 1人離去的概人離去的概率約為率約為 n ntt，0 0人到達的概率約為人到達的概率約

38、為1-1-n ntt，0 0人離去的概率約為人離去的概率約為1-1-n ntt。( (根據根據泊松流的特征得到泊松流的特征得到) )44又因為前述方式1，2，3，4是互不相容且完備互不相容且完備的，因此有：111111()( ) (1)(1)( ) ()(1)( ) (1)()( ) ()()nnnnnnnnnnnnnP ttP tttPtttPtttP ttt 0()( )limnntP ttP tt1111( )( )()( )nnnnnnnPtP tPt對上式展開并構造如下極限式： ，則有：，則有： 這剛好就是這剛好就是P Pn n(t(t) )對對t t的導數。的導數。 事件事件(0,

39、t+(0,t+t)t)發生可發生可看作事件看作事件(0,t(0,t）和事件）和事件(t,t+(t,t+t t) )同時發生。因同時發生。因此：此：P(0,t+P(0,t+t)= t)= P(0,t)P(t,t+P(0,t)P(t,t+t)t)45當n=0時，只有方式1和3，4發生，且方式1中無離去的概率為1，則:00011( )( )( )dP tP tP tdt 設系統是穩態的，即與時刻t無關，于是可得：( )0ndPtdt0011111100()0,1,2,nnnnnnnPPnPPPn令P0已知，可用遞推方法求得：4600110PP0101()PP0011122()0PPP1111122(

40、)0PPP012011122()PPP 120011.nnnnnPP記12011.nnnnnC則平穩狀態的分布為：0nnPC P 下面求下面求P P0 0。47由概率分布的要求：01nnP0111nnCP有：0111nnPC即綜上述，得到各狀態平衡時的概率分布遞推計算式如下：12001101.11nnnnnnnPPPC 所以關鍵是得到各狀態下單位時間單位時間到達和離開的人數：,0 , 1,nnn48例：某小型超市有一個收款臺。付款顧客以每小時30人的負指數分布到達。當收款臺前只有一名顧客時，有一名收款員單獨服務，收款時間為平均1.5min的負指數分布；當有2名或以上顧客時，將增加一名助手共同為

41、顧客服務，收款時間將縮短至平均1min的負指數分布。求收款臺前有n名顧客的概率Pn01.30/nh人16040/1.5h人260.60/1nh人解：這里的單位時間是1小時，所以491011112.303 1( ).(40)(60)4 2nnnnnnC n=1,2.=011111231511.( )42nnnnPC則有由0nnPC P可知：131231()()42552nnnP50 一般地，對排隊模型，在給定輸入和服務條件下，一般地，對排隊模型，在給定輸入和服務條件下，主要研究系統的下述運行指標：主要研究系統的下述運行指標： (1)(1)系統的系統的平均隊長平均隊長L Ls s( (期望值期望值

42、) )和和平均隊列長平均隊列長L Lq q( (期望值期望值) )； (2)(2)系統中系統中顧客平均逗留時間顧客平均逗留時間W Ws s與隊列中與隊列中平均等待平均等待時間時間W Wq q；M/M/sM/M/s等待制排隊模型等待制排隊模型單服務臺模型：單服務臺模型： M/M/1/ M/M/1/ 是指：顧客的相繼到達時間服從參數為的負指數分布，服務臺數為1，服務時間服從參數為的負指數分布，系統空間無限，允許無限排隊。511、隊長的分布、隊長的分布(參數、就是單位時間進入或被服務的人數)所以n =( n=0，1，2，)，n =( n=0，1，2，)記 = / ，并設 1 (否則隊列將排至無限遠)

43、， 則()nnC0nnppn= 1,2,.，n= 1,2,而1100111()()111nnnnpC 因此(1)nnP n=0,1,2是系統中至少有一個顧客的概率，也就是服務臺處于忙的狀態的概率，因而也稱為服務強度為服務強度，它反映了系統繁忙的程度。即為平衡條件下系統中顧客數為n的概率。522. 系統的運行指標計算系統的運行指標計算 (1) 系統中的隊長系統中的隊長Ls（平均隊長：排隊（平均隊長：排隊+被服務）被服務） nnnnsnPnL 001.)(n.)()()(n 11312132.nn.nn 1433223322 132.n (01) 1 期望期望53(2) 隊列中等待的平均顧客數隊列

44、中等待的平均顧客數Lq ：僅排隊：僅排隊 nnnnqnPnL 111) 1() 1( nnnn)(n 1111221sL (3) 顧客在顧客在系統中的平均逗留時間系統中的平均逗留時間Ws 顧客在系統中的逗留時間是隨機變量，可以證顧客在系統中的逗留時間是隨機變量，可以證明，它服從參數為明，它服從參數為-的負指數分布，分布函數的負指數分布，分布函數 11nn54 和密度函數為：和密度函數為：w)(e)w(F 1w)(e )()w( f （w00）()ssLW 1sWE w (4) (4)顧客在顧客在隊列中的平均逗留時間隊列中的平均逗留時間W Wq q 111qsWW ()qqLW 等待時等待時間間

45、 顧客在隊列中的平均逗留時間應為顧客在隊列中的平均逗留時間應為W Ws s減去平均服減去平均服務時間。務時間。 考慮考慮L LS S與與W WS S的關的關系系55 LsLsLLqs 12WsLs WqLq 四個指標的關系為四個指標的關系為(Little Little 公式公式)： 3. 系統的忙期與閑期系統的忙期與閑期 系統處于空閑狀態的概率：系統處于空閑狀態的概率： 10P 系統處于繁忙狀態的概率：系統處于繁忙狀態的概率： 010P)N(P服服務務強強度度56 在繁忙狀態下，隊列中的平均顧客數在繁忙狀態下，隊列中的平均顧客數L Lb b：(0)qbsLLLP N 顧客平均等待時間顧客平均等

46、待時間:1(0)qbsWWWP N 忙期的平均長度忙期的平均長度: 1B 1IB ( (由由 來來) ) 一個忙期平均服務顧客數為：一個忙期平均服務顧客數為： 111 L Lb bP P(N0)(N0)=L=Lq q57例：某修理店只有一個修理工，來修理的顧客到達過程為Poisson流，平均4人/h; 修理時間服從負指數分布，平均需要6min。試求：（1）修理店空閑的概率（2）店內恰有3個顧客的概率（3）店內至少有1個顧客的概率（4）在店內的平均顧客數（5）每位顧客在店內的平均逗留時間（6）等待服務的平均顧客數（7）每位顧客平均等待服務時間（8）顧客在店內等待時間超過10min的概率58解 本

47、例可看成一個M/M/1/排隊問題，其中124100.15（1）修理店空閑的概率02110.65p（2）店內恰有3個顧客的概率33322(1)() (1)0.03855p（3）店內至少有1個顧客的概率02110.45P Np 59（4）在店內的平均顧客數25250.6711L（5）每位顧客在店內的平均逗留時間0.67( )10(min)4LWh（人）（6）等待服務的平均顧客數2 22()5250.26711qLL（人）60（7）每位顧客平均等待服務的時間0.267( ) 4(min)4qqLWh（8）顧客在店內逗留時間超過10min的概率由于逗留時間服從參數 的負指數分布，即分布函數為()0tP

48、 Ttet 則10(1/6 1/15)1100.3679P Tee注：對于： 1小時 10 人 則 1分鐘 10/60=1/6(人)。同理61多服務臺模型：多服務臺模型： M/M/s/M/M/s/ M/M/s/ 是指：設顧客單個到達，相繼到達時間服從參數為的負指數分布，服務臺數為s，每個服務臺的服務時間相互獨立，且服從參數為的負指數分布，系統空間無限，允許無限排隊。當考慮系統處于平穩狀態后隊長N的概率分布,有(1,2. )(,1,2.)nnnnssss ss1、隊長的分布62記ssc且1s有( /)!( /)( /)()!nnsn sn snCsss s n=1,2,sns故00,1,2,!,!nnnn spnsnPpnss s其中1100)!(1nssnspns63上面兩個式子給出了平衡條件下系統中顧客數為n的概率，當ns時，即系統中顧客數大于服務臺個數，這時再來的顧客必須等待，因此記：0( ,)!(1)snn ssc sPPsErlang等待公式它給出了顧客到達系統時需要等待的概率。由平穩狀態下隊長N的概率分布，可得到平均排隊長Lq:021()!(1)ssqnnssPLns Ps 2、幾個主要數量指標640( ,)!(1