1、1第第8 8章章 排隊論排隊論本章內容重點本章內容重點 排隊論基本概念排隊論基本概念 基本問題與求解思路基本問題與求解思路 泊松輸入泊松輸入指數服務排隊模型指數服務排隊模型 其他模型選介其他模型選介 排隊系統的優化排隊系統的優化3 排隊論排隊論(Queuing Theory)(Queuing Theory)，又，又稱 隨 機 服 務 系 統 理 論稱 隨 機 服 務 系 統 理 論 ( R a n d o m ( R a n d o m Service System Theory),Service System Theory),是一門研是一門研究擁擠現象究擁擠現象( (排隊、等待排隊、等待)

2、)的科學。具的科學。具體地說，它是在研究各種排隊系統概體地說，它是在研究各種排隊系統概率規律性的基礎上，解決相應排隊系率規律性的基礎上，解決相應排隊系統的最優設計和最優控制問題。統的最優設計和最優控制問題。前前 言言4 排隊論是排隊論是19091909年由丹麥工程師愛年由丹麥工程師愛爾朗爾朗(A.K(A.KErlangErlang) )在研究電活系統時在研究電活系統時創立的，幾十年來排隊論的應用領域創立的，幾十年來排隊論的應用領域越來越廣泛，理論也日漸完善。特別越來越廣泛，理論也日漸完善。特別是自二十世紀是自二十世紀6060年代以來，由于計算年代以來，由于計算機的飛速發展，更為排隊論的應用開機

3、的飛速發展，更為排隊論的應用開拓了寬闊的前景。拓了寬闊的前景。前前 言言51. 1. 排隊論基本概念排隊論基本概念 排隊是我們在日常生活和生產中經常排隊是我們在日常生活和生產中經常遇到的現象遇到的現象: :上、下班搭乘公共汽車；上、下班搭乘公共汽車；顧客到商店購買物品；顧客到商店購買物品；病員到醫院看病；病員到醫院看??；旅客到售票處購買車票；旅客到售票處購買車票；學生去食堂就餐等就常常出現排隊和等學生去食堂就餐等就常常出現排隊和等待現象。待現象。排隊的不一定是人，也可以是物：排隊的不一定是人，也可以是物： 通訊衛星與地面待傳遞的信息；通訊衛星與地面待傳遞的信息； 生產線上的原料、半成品等待加工

4、；生產線上的原料、半成品等待加工； 因故障停止運轉的機器等待工人修理；因故障停止運轉的機器等待工人修理； 碼頭的船只等待裝卸貨物；碼頭的船只等待裝卸貨物； 要降落的飛機因跑道不空而在空中盤要降落的飛機因跑道不空而在空中盤旋等等。旋等等。71.1 排隊系統特征與基本過程排隊系統特征與基本過程1) 排隊問題的共同特征排隊問題的共同特征 有要求某種服務的人或物。排隊論里有要求某種服務的人或物。排隊論里把要求服務的對象統稱為把要求服務的對象統稱為“顧客顧客” 有提供服務的人或機構。把提供服務有提供服務的人或機構。把提供服務的人或機構稱為的人或機構稱為“服務臺服務臺”或或“服務員服務員” 顧客的到達、服

5、務的時間至少有一個顧客的到達、服務的時間至少有一個是是隨機隨機的，服從某種分布。的，服從某種分布。82) 基本排隊過程基本排隊過程 任何一個排隊問題的基本排隊任何一個排隊問題的基本排隊過程都可以用圖過程都可以用圖 8-18-1表示：每個顧表示：每個顧客由顧客源按照一定方式到達服務客由顧客源按照一定方式到達服務系統，首先加入隊列排隊等待接受系統，首先加入隊列排隊等待接受服務，然后服務臺按一定規則從隊服務，然后服務臺按一定規則從隊列中選擇顧客進行服務，獲得服務列中選擇顧客進行服務，獲得服務后的顧客立即離開。后的顧客立即離開。一般排隊系統都可由下圖（一般排隊系統都可由下圖（圖圖8-1）描述）描述圖圖

6、8-1 8-1 隨機服務系統隨機服務系統排隊系統示意圖排隊系統示意圖10 面對擁擠現象，顧客排隊時間的長短面對擁擠現象，顧客排隊時間的長短與服務設施規模的大小，就構成了設計與服務設施規模的大小，就構成了設計隨機服務系統中的一對矛盾。隨機服務系統中的一對矛盾。 如何做到既保證一定的服務質量指標，如何做到既保證一定的服務質量指標，又使服務設施費用經濟合理，恰當地解又使服務設施費用經濟合理，恰當地解決顧客排隊時間與服務設施費用大小這決顧客排隊時間與服務設施費用大小這對矛盾，這就是排隊論所要研究解決的對矛盾，這就是排隊論所要研究解決的問題之一。問題之一。11 通常，排隊系統都有通常，排隊系統都有輸入過

7、程輸入過程、服務規則服務規則和和服務臺服務臺等等3 3個組成部分：個組成部分： 1) 1) 輸入過程輸入過程這是指要求服務的顧這是指要求服務的顧客是按怎樣的規律到達排隊系統的過程，客是按怎樣的規律到達排隊系統的過程，有時也把它稱為顧客流一般可以從有時也把它稱為顧客流一般可以從3 3個方面來描述一個輸入過程。個方面來描述一個輸入過程。1.2 1.2 排隊系統的基本組成部分排隊系統的基本組成部分121) 1) 輸入過程輸入過程 顧客總體數顧客總體數( (又稱又稱顧客源顧客源、輸、輸入源入源) )。這是指顧客的來源。顧。這是指顧客的來源。顧客源可以是客源可以是有限有限的，也可以是的，也可以是無無限限

8、的。例如，到售票處購票的顧的。例如，到售票處購票的顧客總數可以認為是無限的，而某客總數可以認為是無限的，而某個工廠因故障待修的機床則是有個工廠因故障待修的機床則是有限的。限的。13 顧客到達方式顧客到達方式。描述顧客是怎描述顧客是怎樣來到系統的，他們是單個到達，還樣來到系統的，他們是單個到達，還是成批到達。病人到醫院看病是顧客是成批到達。病人到醫院看病是顧客單個到達的例子。在庫存問題中如將單個到達的例子。在庫存問題中如將生產器材進貨或產品入庫看作是顧客，生產器材進貨或產品入庫看作是顧客，那么這種顧客則是成批到達的。那么這種顧客則是成批到達的。1) 1) 輸入過程輸入過程141) 輸入過程輸入過

9、程 顧客流的概率分布顧客流的概率分布，或稱，或稱相繼顧相繼顧客到達的時間間隔的分布客到達的時間間隔的分布。這是求這是求解排隊系統有關運行指標問題時，首先解排隊系統有關運行指標問題時，首先需要確定的指標。流可以理解為在一定需要確定的指標。流可以理解為在一定的時間間隔內到達的時間間隔內到達k個顧客個顧客(k =1、2、)的概率是多大。的概率是多大。顧客流的概率分布一般顧客流的概率分布一般有定長分布、二項分布、泊松流有定長分布、二項分布、泊松流( (最簡最簡單流單流) )、愛爾朗分布等若干種。、愛爾朗分布等若干種。15 指服務臺從隊列中選取顧客進指服務臺從隊列中選取顧客進行服務的順序。一般可以分為行

10、服務的順序。一般可以分為損失損失制制、等待制等待制和和混合制混合制等等3 3大類。大類。 損失制損失制。如果顧客到達排隊系統如果顧客到達排隊系統時，所有服務臺都已被占用，那么他時，所有服務臺都已被占用，那么他們就自動離開系統永不再來。們就自動離開系統永不再來。2) 服務規則服務規則 等待制等待制。當顧客來到系統時，所有服務當顧客來到系統時，所有服務臺都不空，顧客加入排隊行列等待服務。等臺都不空，顧客加入排隊行列等待服務。等待制中，服務臺在選擇顧客進行服務時，常待制中，服務臺在選擇顧客進行服務時，常有如下四種規則：有如下四種規則： 先到先服務。先到先服務。按顧客到達的先后順序對顧按顧客到達的先后

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

12、斷其他數據的處理等，均屬計算機立即中斷其他數據的處理等，均屬于此種服務規則。于此種服務規則。2) 服務規則服務規則(等待制等待制-續續)18 混合制混合制等待制與損失制相結合的等待制與損失制相結合的一種服務規則，一般是指允許排隊，但一種服務規則，一般是指允許排隊，但又不允許隊列無限長下去。具體說來，又不允許隊列無限長下去。具體說來，大致有三種：大致有三種： 隊長有限隊長有限。當排隊系統中的顧客人數當排隊系統中的顧客人數K超過規定數量時，后來的顧客就自動超過規定數量時，后來的顧客就自動離去，另求服務，即系統的容量是有限離去，另求服務，即系統的容量是有限的。的。2) 服務規則服務規則19 等待時間

13、有限等待時間有限。顧客在系統中的等待顧客在系統中的等待時間不超過某一給定的長度時間不超過某一給定的長度T，當等待時，當等待時間超過間超過T 時，顧客將自動離去，并不再回時，顧客將自動離去，并不再回來。如易損壞的電子元器件的庫存問題，來。如易損壞的電子元器件的庫存問題，超過一定存儲時間的元器件被自動認為失超過一定存儲時間的元器件被自動認為失效。又如顧客到飯館就餐，等了一定時間效。又如顧客到飯館就餐，等了一定時間后不愿再等而自動離去另找飯店用餐。后不愿再等而自動離去另找飯店用餐。2) 服務規則服務規則（混合制（混合制-續）續） 逗留時間有限逗留時間有限。例如用高射炮射擊敵機，例如用高射炮射擊敵機，

14、當敵機飛越高射炮射擊有效區域的時間為當敵機飛越高射炮射擊有效區域的時間為 t 時，若在這個時間內未被擊落，就不可能再時，若在這個時間內未被擊落，就不可能再被擊落了。被擊落了。 注意注意：損失制和等待制可看成是混合損失制和等待制可看成是混合制的特殊情形，如記制的特殊情形，如記 s 為系統中服務臺的個為系統中服務臺的個數，則當數，則當 N = s 時，混合制即成為損失制；時，混合制即成為損失制；當當N = 時，混合制即成為等待制。時，混合制即成為等待制。2) 服務規則服務規則（混合制（混合制-續）續）服務臺可從以下三方面來描述：服務臺可從以下三方面來描述：1.1. 服務臺數量及構成形式；服務臺數量

15、及構成形式；2.2. 服務方式；服務方式；3.3. 服務時間分布服務時間分布3) 服務臺情況服務臺情況 服務臺數量及構成形式（圖服務臺數量及構成形式（圖8-28-6）單隊單隊單服務臺式；單服務臺式；單隊單隊多服務臺并聯式；多服務臺并聯式；多隊多隊多服務臺并聯式；多服務臺并聯式；單隊單隊多服務臺串聯式；多服務臺串聯式；單隊單隊多服務臺并串聯混合式及多隊多服務臺并串聯混合式及多隊多服多服務臺并串聯混合式等等。務臺并串聯混合式等等。圖圖8-2 8-2 單服務臺排隊系統單服務臺排隊系統23圖圖8-3 8-3 單隊列單隊列-S-S個服務臺并聯的排隊系統個服務臺并聯的排隊系統圖圖8-4 S8-4 S個隊列

16、個隊列-S-S個服務臺的并聯排隊系統個服務臺的并聯排隊系統24圖圖8-5 8-5 單隊單隊- -多個服務臺的串聯排隊系統多個服務臺的串聯排隊系統圖圖8-6 8-6 多隊多隊- -多服務臺混聯、網絡系統多服務臺混聯、網絡系統25 服務方式服務方式。這是指在某一時刻接受這是指在某一時刻接受服務的顧客數，它有單個服務和成批服務服務的顧客數，它有單個服務和成批服務兩種。兩種。 服務時間的分布服務時間的分布。在多數情況下，在多數情況下，對每一個顧客的服務時間是一隨機變量，對每一個顧客的服務時間是一隨機變量，其概率分布有定長分布、負指數分布、其概率分布有定長分布、負指數分布、K級愛爾朗分布、一般分布級愛爾

17、朗分布、一般分布( (所有顧客的服務所有顧客的服務時間都是獨立同分布的時間都是獨立同分布的) )等等。等等。3) 服務臺情況服務臺情況26 為了區別各種排隊系統，根據輸為了區別各種排隊系統，根據輸入過程、排隊規則和服務機制的變化入過程、排隊規則和服務機制的變化對排隊模型進行描述或分類，肯道爾對排隊模型進行描述或分類，肯道爾（DGKendall）提出了一種目前提出了一種目前在排隊論中被廣泛采用的在排隊論中被廣泛采用的“Kendall記記號號”，完整的表達方式通常用到，完整的表達方式通常用到6個個符號并取如下固定格式：符號并取如下固定格式：A/B/C/D/E/F 各符號的意義為：各符號的意義為：1

18、.3 排隊系統的描述符號與分類排隊系統的描述符號與分類A表示顧客相繼到達間隔時間分布，表示顧客相繼到達間隔時間分布，常用下列符號：常用下列符號： M 表示到達過程為泊松過程或負表示到達過程為泊松過程或負指數分布；指數分布； D 表示定長輸入；表示定長輸入； Ek 表示表示k階愛爾朗分布；階愛爾朗分布； G 表示一般相互獨立的隨機分布。表示一般相互獨立的隨機分布。Kendall記號含義記號含義Kendall記號含義記號含義B 表示服務時間分布表示服務時間分布。所用符號與表所用符號與表示顧客到達間隔時間分布相同。示顧客到達間隔時間分布相同。 M 表示服務過程為泊松過程或負表示服務過程為泊松過程或負

19、指數分布；指數分布； D 表示定長分布；表示定長分布； Ek 表示表示k階愛爾朗分布；階愛爾朗分布； G 表示一般相互獨立的隨機分布。表示一般相互獨立的隨機分布。 C表示服務臺表示服務臺(員員)個數個數： “1”則表示單個服務臺，則表示單個服務臺，“s”(s1)表示多表示多個服務臺。個服務臺。D表示系統中顧客容量限額表示系統中顧客容量限額： 如系統有如系統有N個位子，則個位子，則 s N00為一常數，表示單位時為一常數，表示單位時間內到達顧客的平均數，又稱為顧客的平間內到達顧客的平均數，又稱為顧客的平均到達率。均到達率。 負指數分布。負指數分布。對于泊松流，可以證明其對于泊松流，可以證明其相繼

20、顧客到達時間間隔相繼顧客到達時間間隔 i，i = 1,2,是相互是相互獨立同分布的，其分布函數為負指數分布：獨立同分布的，其分布函數為負指數分布：0, 00,1)(ttetFti ), 2 , 1(i1) 重要的概率分布重要的概率分布 poisson流流 k階階愛爾朗分布愛爾朗分布. . 這是指相繼顧客到達這是指相繼顧客到達時間間隔時間間隔 相互獨立，具有相同的分布，其分相互獨立，具有相同的分布，其分布密度為布密度為其中其中k為非負整數。為非負整數。 可以證明，在參數為可以證明，在參數為 的泊松輸人中，對任的泊松輸人中，對任意的意的j與與k,設第設第j與第與第j+k個顧客之間的到達間隔個顧客之

21、間的到達間隔為為則隨機變量則隨機變量Tk的分布必遵從參數為的分布必遵從參數為 的愛爾朗的愛爾朗分布。分布。1()( )0(1)!Kttf tetK )(21kkkTT 例：某排隊系統有并聯的例：某排隊系統有并聯的k個服務臺，顧個服務臺，顧客流為泊松流，規定第客流為泊松流，規定第i, k+i, 2k+i 個顧個顧客排入第客排入第i號臺號臺 ( i = 1,2,k )，則第，則第k臺所臺所獲得的顧客流，即為獲得的顧客流，即為k階愛爾朗輸入流，階愛爾朗輸入流，其他各臺，從它的第一個顧客到達以后開其他各臺，從它的第一個顧客到達以后開始所獲得的流也為愛爾朗輸入流。始所獲得的流也為愛爾朗輸入流。 此外，愛

22、爾朗分布中，當此外，愛爾朗分布中，當k1時將化時將化為負指數分布。為負指數分布。1) 重要的概率分布重要的概率分布 愛爾朗分布愛爾朗分布592) 生滅過程與狀態轉移速度圖生滅過程與狀態轉移速度圖 生滅過程。生滅過程。 假定一個系統具有狀態集假定一個系統具有狀態集 S = 0, 1, 2, , N , 并存在常數并存在常數 n0 和和 n0，n = 1,2,N 當當 t (t 0) 時刻，記狀態隨機變量時刻，記狀態隨機變量為為K(t)，系統內有，系統內有n個顧客的概率為個顧客的概率為Pn(t)，經過，經過t 時間，如果滿足時間，如果滿足60 則稱這個隨機過程則稱這個隨機過程 K(t) ：t 0

23、為為有限狀態有限狀態S上的上的生滅過程生滅過程。當系統具有。當系統具有可列無限狀態集可列無限狀態集S = 0, 1, 2, 時時,則則稱為無限狀態的生滅過程。稱為無限狀態的生滅過程。2) 生滅過程與狀態轉移速度圖生滅過程與狀態轉移速度圖1, 1,),()()()()()(11nnnkSktottPtotttPtotttPknnnn 狀態轉移速度圖。狀態轉移速度圖。我們把充分小的我們把充分小的t 固定，直接用參數固定，直接用參數 n 和和 n 表示表示 n t 和和 n t，生滅過程可利用狀態轉移速度圖來描，生滅過程可利用狀態轉移速度圖來描述述“生生”、“滅滅”導致狀態轉移的過程。注導致狀態轉移

24、的過程。注意，在實際上，意，在實際上， n和和 n的取值不需要考慮的取值不需要考慮t的大小，只要保證二者的基礎時段一致即可的大小，只要保證二者的基礎時段一致即可（計算中考慮的是二者的比率）。（計算中考慮的是二者的比率）。2) 生滅過程與狀態轉移速度圖生滅過程與狀態轉移速度圖無限狀態生滅過程的狀態轉移速度無限狀態生滅過程的狀態轉移速度圖如圖圖如圖：狀態轉移速度圖狀態轉移速度圖0n123021n-1n1n32n+1狀態轉移速度圖狀態轉移速度圖 根據泊松流的普通性，當根據泊松流的普通性，當t充分小充分小時，在時，在 (t,t+t) 時間段內有一個顧客到時間段內有一個顧客到達的概率為達的概率為 nt

25、+ o (t ) ，而無顧客，而無顧客到達的概率為到達的概率為1- nt + o(t )，故泊松，故泊松輸入輸入指數服務排隊系統的狀態轉指數服務排隊系統的狀態轉移過程是生滅過程。因此，可以通過移過程是生滅過程。因此，可以通過狀態轉移速度圖研究狀態概率之間的狀態轉移速度圖研究狀態概率之間的關系。關系。2.2 泊松輸入泊松輸入-指數服務排隊系統的求解指數服務排隊系統的求解 1) 狀態概率之間的關系狀態概率之間的關系: 可以通過兩種方式推導這種關系：可以通過兩種方式推導這種關系： 直接通過概率發生情況討論系統直接通過概率發生情況討論系統狀態概率之間的關系。狀態概率之間的關系。 利用狀態轉移速度圖導出

26、各狀態利用狀態轉移速度圖導出各狀態概率之間的關系。概率之間的關系。 直接通過概率發生情況討論系統狀態直接通過概率發生情況討論系統狀態概率之間的關系：概率之間的關系： n：系統狀態為系統狀態為n時，顧客進入系統的平均速度時，顧客進入系統的平均速度 n：系統狀態系統狀態為為n時，顧客離開系統的平均速度時，顧客離開系統的平均速度 Pn(t)：t 時刻，系統內有時刻，系統內有n個顧客的概率。個顧客的概率。 那么，在那么，在 (t, t+ t) 有一個顧客到達概率為有一個顧客到達概率為 n t，無顧客到達的概率為，無顧客到達的概率為 1- n t（根據普（根據普通性）。通性）。 各種方式發生概率表各種方

27、式發生概率表 Pn(t+ t) = Pn(t)(1- n t)(1- n t) +Pn-1(t) n-1 t(1- n-1 t) +Pn+1(t)(1- n+1 t) n+1 t +Pn(t) n t n tdPn(t)/dt = lim t-0(Pn(t+ t)-Pn(t)/ t) =Pn-1(t) n-1-Pn(t)( n+ n)+Pn+1(t) n+1 (其中其中 t2項都變為零項都變為零)方式方式1, 2, 3, 4互不相容且完備互不相容且完備,于是于是68 當當n=0時，只有方式時，只有方式1和和3，4發生，且方式發生，且方式1中無離去的概率為中無離去的概率為1，則，則 dP0(t)

28、/dt = -P0(t) 0+P1(t) 1 我們假設系統是穩態的，即我們假設系統是穩態的，即與時刻無關，于是可得：與時刻無關，于是可得： d Pn(t) / d t = 0；公式推導如下：公式推導如下：2323332221112122211100010111000)(0)(0pppppppppppppp 根據此根據此各事件兩兩不相容，且完各事件兩兩不相容，且完備，有備，有 pn=1，于是于是 可求出可求出 pn, n=0, 1, 2, 01101111110)(ppppppinijnjnnnnnnnnnnn 利用狀態轉移速度圖得到概率公式利用狀態轉移速度圖得到概率公式由此圖易得：轉入率由此圖

29、易得：轉入率=轉出率轉出率n=0 ， 0P0= 1P1n0 ， n-1Pn-1+ n+1Pn+1=( n+ n)Pn0n123021n-1n1n32n+172公式推導如下：公式推導如下：2323332221112122211100010111000)(0)(0pppppppppppppp 73 根據此根據此各事件兩兩不相容，且完各事件兩兩不相容，且完備，有備，有 pn=1，于是于是 可求出可求出 pn, n=0, 1, 2, 01101111110)(ppppppinijnjnnnnnnnnnnn 對排隊系統運行情況的分析，對排隊系統運行情況的分析，通常是在給定輸入與服務條件下，通常是在給定輸

30、入與服務條件下，通過求解系統狀態為通過求解系統狀態為n的概率的概率Pn(t)，再計算其主要的運行指標，再計算其主要的運行指標:75 根據已知條件繪制狀態轉移速根據已知條件繪制狀態轉移速度圖。度圖。 依據狀態轉移速度圖寫出各穩依據狀態轉移速度圖寫出各穩態概率之間的關系。態概率之間的關系。 求出求出 P0 及及 Pn 。2)泊松輸入泊松輸入負指數分布服務的排隊負指數分布服務的排隊系統的一般決策過程：系統的一般決策過程：762)泊松輸入泊松輸入負指數分布服務的負指數分布服務的排隊系統的一般決策過程（續）排隊系統的一般決策過程（續） 計算各項數量運行指標計算各項數量運行指標。 用系統運行指標構造目標函

31、數，用系統運行指標構造目標函數，對系統進行優化。對系統進行優化。77泊松輸入泊松輸入-指數服務指數服務穩態穩態排隊系統排隊系統的運行指標的運行指標 系統中顧客數系統中顧客數( (隊長隊長) )的期望值的期望值 排隊等待的顧客數排隊等待的顧客數( (排隊長排隊長) )的期望值的期望值0nnnpL1)(snnqpsnL78 求出平均有效到達率求出平均有效到達率 e，再再利用利用Little公式計算：公式計算： 顧客在系統中全部時間顧客在系統中全部時間(逗留逗留時間時間)的期望值的期望值W； 顧客在系統中排隊等待時間顧客在系統中排隊等待時間的期望值的期望值Wq。79例例某汽車加油站有兩臺加油泵為汽車

32、加某汽車加油站有兩臺加油泵為汽車加油，加油站內最多能容納油，加油站內最多能容納6輛汽車。已輛汽車。已知顧客到達的時間間隔服從負指數分知顧客到達的時間間隔服從負指數分布，平均每小時到達布，平均每小時到達18輛汽車。若輛汽車。若加加油站中已油站中已有有K輛車，當輛車，當K 2時，有時，有K/6的顧客將自動離去的顧客將自動離去。加油時間服從負。加油時間服從負指數分布，平均每輛車需要指數分布，平均每輛車需要5分鐘。試分鐘。試求：求：非標準的非標準的M/M/2/NM/M/2/N模型模型801）系統空閑的概率為多少？）系統空閑的概率為多少？ P02）求系統滿的概率是多少？）求系統滿的概率是多少？ P63）

33、求系統服務臺不空的概率）求系統服務臺不空的概率 P2+P3+P4+P5+P6=1- P0-P1 4）若服務一個顧客）若服務一個顧客,加油站可以獲加油站可以獲得利潤得利潤10元元,問平均每小時可獲得利問平均每小時可獲得利潤為多少元？潤為多少元？ 10 e5）求每小時損失掉的顧客數？）求每小時損失掉的顧客數？ 損損= - e 816）加油站平均有多少輛車在等待）加油站平均有多少輛車在等待加油？加油？ Lq 平均有多少個車位被占？平均有多少個車位被占？ L7）進入加油站的顧客需要等多長）進入加油站的顧客需要等多長的時間才能開始加油？的時間才能開始加油？ Wq 進入加進入加油站的顧客需要多長時間才能離

34、去？油站的顧客需要多長時間才能離去？ W82穩態概率關系：穩態概率關系：P1= / P0=1.5P0 =(3/2)P0P2= /(2 )P1=0.75*1.5P0 =(9/8)P0解：狀態轉移速度圖解：狀態轉移速度圖 以小時為單位以小時為單位 =18 =60/5=1222 2205124632(1-2/6)(1-3/6) (1-4/6) (1-5/6) P3=(4/6)/(2)P2=(1/2)(9/8)P0 = (9/16)P0 P4=(3/6)/(2)P3=(3/8)(9/16)P0 = (27/128)P0P5=(2/6)/(2)P4=(1/4)(27/128)P0 = (27/512)P

35、0P6=(1/6)/(2)P5=(1/8)(27/512)P0 = (27/4096)P084由由 P0+P1+P2+P3+P4+P5+P6=1解得：解得：P0=0.22433P1= 0.33649 ，P2= 0.25237 ，P3= 0.12618 ，P4= 0.04732 ，P5= 0.01183 ，P6=0.00148。851) P0=0.224332) P6=0.001483) P忙忙=1-P0-P1=0.439184) e= 0P0+ P1+2 (P2+P3+P4+P5+P6) = 14.578（輛（輛/h） 10 e= 145.78(元元/小時）小時）運行指標：運行指標：865)

36、損損= - e =18-14.5782 =3.4218（輛（輛/h）6)Lq=(3-2)P3+(4-2)P4+(5-2)P5+(6-2)P6 = 0.26223 L=Lq+ e/ =0.26223+1.21485 =1.47708運行指標（續）運行指標（續）87運行指標（續）運行指標（續）7)7)W Wq q= =L Lq q/ / e e = 0.018h = 1.08= 0.018h = 1.08分鐘分鐘 W W= =W Wq q+1/+1/ = 0.101h = 6.08= 0.101h = 6.08分鐘分鐘88 車站候車室在某段時間旅客到達車站候車室在某段時間旅客到達服從泊松分布，平均

37、速度為服從泊松分布，平均速度為50人人/h，每位旅客在候車室內停留的時間服從每位旅客在候車室內停留的時間服從負指數分布，平均停留時間為負指數分布，平均停留時間為0.5h，問候車室內平均人數為多少？問候車室內平均人數為多少？解：把旅客停留在候車室看做服務，解：把旅客停留在候車室看做服務，于是系統為于是系統為M/M/ = 50 =1/0.5 = 2例例89穩態概率關系：穩態概率關系：Pn= /(n )Pn-1=1/n!( / )nP0 記記 = / = 50/2 = 25 狀態轉移速度圖狀態轉移速度圖: :0n12n-1n2(n+1)n+13 (n-1)(n+2)90010100025!1)!1(

38、1!1,1nnnnnnnnnnnenenpLenpp 代入代入因此，候車室平均人數為因此，候車室平均人數為25人。人。 在排隊系統中，由于顧客到達在排隊系統中，由于顧客到達分布和服務時間分布不同、服務臺分布和服務時間分布不同、服務臺數不同、隊長有限無限、顧客源有數不同、隊長有限無限、顧客源有限無限等的不同組合，就會有不勝限無限等的不同組合，就會有不勝枚舉的不同排隊模型。枚舉的不同排隊模型。下面分析下面分析泊泊松輸入松輸入-指數服務指數服務排隊系統模型。排隊系統模型。3 3 泊松輸入泊松輸入-指數服務排隊模型指數服務排隊模型 921) M/M/1/: 參數參數 ， 穩態概率方程：穩態概率方程：

39、Pn=( / )Pn-1=( / )nP0 令令= / 當當 1時時, n不收斂，故應不收斂，故應1, n=0即即 k ) = k+1顧客逗留時間超過顧客逗留時間超過t的概率的概率 P( U t ) = e-()t 96 設忙期、閑期和忙的概率、閑的概設忙期、閑期和忙的概率、閑的概率分別為率分別為 T忙忙、T閑閑、 p忙忙、 p閑閑 ，那么可，那么可以計算忙期和閑期。注意，以計算忙期和閑期。注意， M/M/1/ / 系統系統 其他指標其他指標 11,1,0000ppppTTpppp忙忙閑閑忙忙閑閑忙忙閑閑又又 1閑閑T 11閑閑忙忙TT97例例82 P216 某醫院急診室同時只能診治1個病人，

40、診治時間服從指數分布，每個病人平均需要15分鐘。病人按泊松分布到達，平均每小時到達3人。983.1 單服務臺無限源系統單服務臺無限源系統2) M/M/1/N/ 參數參數 , 系統狀態轉移速度：系統狀態轉移速度：穩態概率方程：穩態概率方程：Pn=( / )Pn-1= ( / )nP0 , 1n N0N-112N-2N99 由由M/M/1/N/ 系統系統10 Nnnp Nnnp001 10011111NNnnNp100 e= npn= (1-pN)+0pN= (1-pN)(只有只有pN不再進人，故不再進人，故 N=0，其余均為，其余均為 ) e = npn=0p0+ (1-p0)（同理）（同理）W

41、 =L/ e , Wq=W -(1/ ), Lq=Wq e M/M/1/N/ 系統系統1,21,1)1(1110 NNnpLNNNnn1013) 損失制損失制M/M/1/1: 顧客到達若服顧客到達若服務臺被占用立即離開。直接可得：務臺被占用立即離開。直接可得：P1 = P0 ; P0+P1=1 P0 = 1 / (1+) = /( + ) P閑閑=P0= /( + )P損損=P忙忙=P1= /( + )3.1 單服務臺無限源系統單服務臺無限源系統102例例83 P2181) M/M/s/ / 系統系統 參數參數 ， 穩態概率應滿足的關系：穩態概率應滿足的關系：當當ns時，時， pn= /(n

42、) pn-1當當ns時，時， Pn = /(s ) pn-1 令令= /(s ) 系統負荷強度系數系統負荷強度系數3.2 多服務臺無限源系統多服務臺無限源系統012ns2cc-1ssc+13(s-1)ss104 此系統中，當此系統中，當= /(s )1時，不時，不收斂，設收斂，設1, M/M/s/ 系統系統1010,1!,!nnnsnssppnsnnpsppnss 105 根據根據 ，可得到，可得到 Lq = sss+1p0 / s! (1-)2利用利用 Little 公式得到公式得到 Wq = Lq / , W = Wq+ 1/ , L= W = Lq+ / M/M/s/ 系統系統10nnp

43、 essnsnnssnsp,1!1100106 某火車站售票處有三個窗口，同時售各某火車站售票處有三個窗口，同時售各車次的車票。顧客到達服從泊松分布，平車次的車票。顧客到達服從泊松分布，平均每分鐘到達均每分鐘到達 =0.9(人人)，服務時間服從負，服務時間服從負指數分布，平均服務率每小時指數分布，平均服務率每小時 =24(人人)，分兩種情況討論：分兩種情況討論：1. 顧客排成一隊，依次購票；顧客排成一隊，依次購票；2.顧客在每個窗口排一隊，不準串隊。顧客在每個窗口排一隊，不準串隊。 求求: 1）售票處空閑的概率。）售票處空閑的概率。 2）平均等待時間和逗留時間。）平均等待時間和逗留時間。 3）

44、隊長和隊列長。）隊長和隊列長。例例單位一致單位一致： =0.4(人人/分鐘分鐘)= /(3 )=0.75穩態概率：穩態概率：031232343解：情況解：情況1. M/M/3/)3(5 . 4! 33,53125. 22,25. 2003012001npppppppppnnn 108解：情況解：情況1. M/M/3/ 續續由由得得15 . 453125. 225. 2,130000nnnnpppp 1893. 0,1683. 0,0748. 015 . 453125. 225. 21 21130ppp ,)3(5 . 4)3(44044nnnnqnppnL 109解：情況解：情況1. M/M/

45、3/ 續續44)3(nnnS 1) 3(4434nnnndndSF,704. 1)1(5 . 4,)1(12042 pLddFSq記記 先求積分，再求微分先求積分，再求微分954. 3,393. 41,893. 1WLWWLWqqq 110解：情況解：情況1. M/M/3/ 續續售票處的空閑的概率為售票處的空閑的概率為0.0748平均等待時間平均等待時間 Wq=1.893分鐘，分鐘， 平均逗留時間平均逗留時間 W=4.393分鐘分鐘隊長隊長 L =3.954(人人) Lq=1.704(人人)111參數參數 =0.3 =0.4 = / = 0.75利用公式，利用公式，1個服務臺有空個服務臺有空

46、p0 = 1- = 0.25 2個、個、3個服務臺有空個服務臺有空: p02=0.0625 和和 p03=0.0156L =/(1-)=3 e= = 0.3用用Little公式：公式： Lq= L- / = 2.25, W =L / =10 , Wq=W-1/ =7.5情況情況2 M/M/1/ 3個系統并聯個系統并聯112故售票處空閑的概率為故售票處空閑的概率為 0.0156平均等待時間平均等待時間 Wq=7.5分鐘分鐘 平均逗留時間平均逗留時間 W=10分鐘分鐘隊長隊長 L=3 三個隊三個隊 共共3+3+3=9隊列長隊列長 Lq=2.25 共共6.75（人）（人） 顯然，排一隊共享顯然，排一

47、隊共享3個服務臺效率高。個服務臺效率高。解：情況解：情況2. M/M/1/ 續續1132) M/M/c/N/ 穩態概率應滿足的關系：穩態概率應滿足的關系：當當nc時，時，當當nc時，時，3.2 多服務臺無限源系統多服務臺無限源系統0N-112N-2c2cNcc-1ccc+1(c-1)cc111 nnnnnpnpp 111nnnnnpcpp 114令令= /(c )，根據，根據 pn=1，可得，可得M/M/c/N/ 系統系統Nncpccpcnpncpncpcnnnn,!1,!0101 1,!)1(!1,1!11011100 sssNnsssnsPsnsnNssnnsn115運行指標：運行指標：M

48、/M/c/N/ 系統系統1,!2) 1)(1,)1)(1(1)1 ( !0021 pcccNcNpcNccLccNccq116同單服務臺情況的分析，同單服務臺情況的分析， e= (1- pN)利用利用 Little 公式，可求得公式，可求得 Wq=Lq / e W=Wq+1/ L=We=Lq+e/M/M/c/N/ 系統系統117此即此即M/M/c/N中中 N=c 的情形的情形 損損= - e= pc ，損失率，損失率= 損損/ = pc 3) M/M/c/c/損失制系統損失制系統 cpncppnnnnnn,!0110,0,)1(,!100qqcecnnnWLpncp )1(,1cpLW 118

49、3.3 有限源排隊系統有限源排隊系統1) M/M/1/m/m系統系統顧客源是顧客源是m個，那么系統容量實質上最多有個，那么系統容量實質上最多有m個足夠。個足夠。0m-112m-2m(m-1)2m(m-2)3顧客源中剩余的顧客數顧客源中剩余的顧客數乘以每個顧客到達的概率乘以每個顧客到達的概率1191) M/M/1/m/m系統系統穩態概率方程：穩態概率方程：由概率性質，得由概率性質，得mnpnmmpnmpnnn, 2 , 1)()!(!)1(01 mnnnmmp010)!(!( )()()(0000Lmnppmpnmpmnnmnnmnmnnnne 1) M/M/1/m/m系統系統根據根據 e= (

50、m-L)= e= (1-p0), 得得 L=m- / (1-p0)再利用再利用Little公式，可求得公式，可求得 W=L/ e Wq=W-1/ Lq=Wq e1212) M/M/c/m/m系統系統0m-112m-2m(m-1)2c2cmcc-1(m(c-1)c穩態概率方程穩態概率方程1, 2 , 1!)!(!)1(01cnpnnmmpnnmpnnn mccnpccnmmpcnmpncnnn, 1,!)!(!)1(01 122代入代入 pn=1 得得,同前，同前，M/M/c/m/m系統系統mcnncncnnccnmmnnmmp1100!)!(!)!(! )()()(0000Lmnppmpnmp

51、mnnmnnmnmnnnne 123進一步可得進一步可得 ：可求出可求出L和和 e，再利用，再利用Little公式，得公式，得 M/M/c/m/m系統系統msnnsnneepspn11 qeqqeWLWWLW ,1,1244其他模型選介1) M/G/1排隊系統排隊系統 設顧客平均到達率為設顧客平均到達率為 ，服務時間為隨機，服務時間為隨機變量變量V，且，且E(V) = 1/ ，D(V) = 2 那么，服務強度那么，服務強度 ，當，當 1時時 p0 = 1 - 根據波拉切克根據波拉切克- -欣欽欣欽（Pollaczek-Khinchine）公式公式可導出可導出 Lq = ( 2+ ) / 2(1

52、- )其它量的計算同前。其它量的計算同前。1254 4 其他模型選介其他模型選介2) M/D/1排隊系統排隊系統 設顧客平均到達率為設顧客平均到達率為 ，服務時間為常數，服務時間為常數v，則，則 E( v ) = v = 1/ , D( v ) = 0那么，服務強度那么，服務強度 ，當，當 1時時 p0 = 1 - 根據上一模型的公式可直接得到根據上一模型的公式可直接得到 Lq = 2 / 2(1- )其它量的計算同前。其它量的計算同前。126 5 5 排隊系統的優化目標排隊系統的優化目標與最優化問題與最優化問題 從經濟角度考慮，排隊系統的從經濟角度考慮，排隊系統的費用應該包含以下兩個方面：一

53、個費用應該包含以下兩個方面：一個是服務費用，它是服務水平的遞增是服務費用，它是服務水平的遞增函數；另一個是顧客等待的機會損函數；另一個是顧客等待的機會損失失( (費用費用) )，它是服務水平的遞減函，它是服務水平的遞減函數。兩者的總和呈一條數。兩者的總和呈一條U U形曲線。形曲線。127排隊系統優化問題排隊系統優化問題 系統最優化的目標就是尋求上述系統最優化的目標就是尋求上述合成費用曲線的最小點。合成費用曲線的最小點。 排隊系統的最優化問題通常分為排隊系統的最優化問題通常分為兩類：系統的靜態最優設計，目的在兩類：系統的靜態最優設計，目的在于使設備達到最大效益；系統動態最于使設備達到最大效益；系

54、統動態最優運營，是指一個給定排隊系統，如優運營，是指一個給定排隊系統，如何運營可使某個目標函數得到最優。何運營可使某個目標函數得到最優。128排隊系統常見的優化問題排隊系統常見的優化問題1)1)確定最優服務率確定最優服務率 * *；2)2)確定最佳服務臺數量確定最佳服務臺數量s s* *；3)3)選擇最為合適的服務規則；選擇最為合適的服務規則；4)4)或是確定上述幾個量的最優組合?；蚴谴_定上述幾個量的最優組合。 研究排隊系統的根本目的在于以研究排隊系統的根本目的在于以最少的設備得到最大的效益。最少的設備得到最大的效益。129本節討論的排隊系統優化問題本節討論的排隊系統優化問題 本章只討論系統靜

55、態的最優設計問題。本章只討論系統靜態的最優設計問題。這類問題一般可以借助于前面所得到的一這類問題一般可以借助于前面所得到的一些表達式來解決。些表達式來解決。 本節就本節就 ，s s 這兩個決策變量這兩個決策變量的分別單獨優化，介紹兩個較簡單的的分別單獨優化，介紹兩個較簡單的模型。模型。5.1 M/M/1/系統的最優平均服系統的最優平均服務率務率 * 設：設：c1 當當 =1時服務系統單位時間的時服務系統單位時間的平均費平均費 cw 平均每個顧客在系統逗留單位平均每個顧客在系統逗留單位時間的損失；時間的損失； y 系統單位時間的平均總費用。系統單位時間的平均總費用。其中其中 c1，cw 均為可知

56、。則目標函數為均為可知。則目標函數為Lccyw1求解過程求解過程將將L= ( -)，代入上式，得，代入上式，得 y 是關于決策變量是關于決策變量 的一元非線性函的一元非線性函數數,由一階條件由一階條件解得駐點解得駐點 11wccy1210()wdyccd1*/ ccw 132求解過程（續）求解過程（續） 根號前取正號是為了保證根號前取正號是為了保證 1 ，這樣，系統才能達到穩態。又由，這樣，系統才能達到穩態。又由二階條件二階條件 ( ( ) )可知求出的可知求出的 * *為為( (,),)上的全局唯一最上的全局唯一最小點。將小點。將 * *代入代入y中，可得最小總平均費中，可得最小總平均費用用

57、0)(2322 wcdyd wcccy11*2133求解過程（續）求解過程（續） 另外，若設另外，若設cw為平均每個顧客在為平均每個顧客在隊列中等待單位時間的損失，則需用隊列中等待單位時間的損失，則需用 取代前式中的取代前式中的L，這時，這時類似可得一階條件：類似可得一階條件： 這一般采用數值法這一般采用數值法(如牛頓法如牛頓法)確定其確定其根根 *。)(2 qL022322213141 wwccccc134 興建一座港口碼頭，只有一個裝卸興建一座港口碼頭，只有一個裝卸船只的泊位。要求設計裝卸能力船只的泊位。要求設計裝卸能力 ，單，單位為（只位為（只/日）船數。已知：單位裝卸日）船數。已知：單位裝卸能力的平均生產費用能力的平均生產費用a=2千元，船只逗千元，船只逗留每日損失留每日損失b=1.5千元。船只到達服從千元。船只到達服從泊松分布，平均速率泊松分布，平均速率 =3只只/日。船只裝日。船只裝卸時間服從負指數分布。目標是每日總卸時間服從負指數分布。目標是每日總支出最少。支出最少。例例 =3 待定待定 模型模型 M/M/1/ 隊長隊長 Ls = /( - )總費用總費用 c =a +bL=a +b /( - ) 求導求導 dc/d =a+(-b )/( - )2 = 0得得: - = (b /a