運籌學第11章 排隊論

1、作為排隊系統(tǒng)（隨機服務系統(tǒng)）的數學理論和方法，是作為排隊系統(tǒng)（隨機服務系統(tǒng)）的數學理論和方法，是運籌學的一個重要分支運籌學的一個重要分支。 排隊是日常生活中經常遇到的現象，如進餐館就餐、圖排隊是日常生活中經常遇到的現象，如進餐館就餐、圖書館借書、在車站候車、售票處購票等等。排隊問題的表現形式往往是擁擠現象，書館借書、在車站候車、售票處購票等等。排隊問題的表現形式往往是擁擠現象，隨著生產與服務的日益社會化，由排隊引起的擁擠現象會越來越普遍隨著生產與服務的日益社會化，由排隊引起的擁擠現象會越來越普遍。下面。下面我們列我們列舉出部分形形色色的排隊舉出部分形形色色的排隊系統(tǒng)。系統(tǒng)。達到的顧客達到的顧客

2、要求服務的內容要求服務的內容服務的機構服務的機構出故障的機器出故障的機器修理技工修理技工病人病人電話呼叫電話呼叫進港貨船進港貨船入水庫河水入水庫河水達到機場上空的飛機達到機場上空的飛機刑事案件刑事案件達到路口的車輛達到路口的車輛來犯敵機來犯敵機修理修理領取修配零件領取修配零件診斷（或治療）診斷（或治療）通話通話裝（卸）貨裝（卸）貨放水、調整水位放水、調整水位降落降落偵破偵破通過路口通過路口截擊截擊修理技工修理技工發(fā)放發(fā)放修配零件修配零件的管理員的管理員醫(yī)生（或治療設備）醫(yī)生（或治療設備）交換臺交換臺裝（卸）貨碼頭（泊位）裝（卸）貨碼頭（泊位）水閘、管理員水閘、管理員跑道跑道刑偵部門刑偵部門交通

3、信號燈交通信號燈我防空部隊我防空部隊排隊排隊可以是有形的隊列，也可以是無形的隊列。排隊可以是人，也可以是物?？梢允怯行蔚年犃校部梢允菬o形的隊列。排隊可以是人，也可以是物。 顧客源顧客源排隊結構排隊結構服服務務機機構構顧客到來顧客到來排隊規(guī)則排隊規(guī)則服務規(guī)則服務規(guī)則顧客離去顧客離去1單隊單隊 單服務臺系統(tǒng)單服務臺系統(tǒng)1單隊單隊多服務臺（并聯）系統(tǒng)多服務臺（并聯）系統(tǒng)2S.1S單隊單隊多服務臺（串聯）系統(tǒng)多服務臺（串聯）系統(tǒng)1多隊多隊多服務臺（并聯）系統(tǒng)多服務臺（并聯）系統(tǒng).2S多隊多隊多服務臺（混聯、網絡）系統(tǒng)多服務臺（混聯、網絡）系統(tǒng)說明說明顧客按怎樣的規(guī)律達到系統(tǒng)，通常從顧客按怎樣的規(guī)律達

4、到系統(tǒng)，通常從 3 個方面刻畫個方面刻畫：n 顧客顧客總體（顧客源）總體（顧客源）數數n 達到方式達到方式n 顧客顧客相繼達到的時間間隔分布相繼達到的時間間隔分布。二二、排隊及、排隊及排隊規(guī)則排隊規(guī)則排隊排隊n 損失損失制制排隊排隊n 等待等待制制排隊排隊n 混合混合制制排隊排隊排隊規(guī)則排隊規(guī)則n 先到先服務先到先服務FCFSn 后到先服務后到先服務LCFSn 有有優(yōu)先權服務優(yōu)先權服務PSn 隨機隨機服務服務RF三三、服務、服務機制機制說明說明顧客按怎樣的規(guī)律接受服務，通常從顧客按怎樣的規(guī)律接受服務，通常從 3 個方面刻畫：個方面刻畫：n 服務員服務員的數量及其連接形式（并聯或串聯的數量及其連

5、接形式（并聯或串聯）n 顧客顧客接受服務的方式（單個或成批接受服務的方式（單個或成批）n 服務時間分布服務時間分布其中其中服務時間分布是最重要因素，其常見的分布有服務時間分布是最重要因素，其常見的分布有：n 定定長分布（長分布（D）n 負負指數分布（指數分布（M）n k 階愛爾朗分布（階愛爾朗分布（Ek）一般一般形式：形式： X / Y / Z / A / B / C X 顧客相繼達到時間間隔的顧客相繼達到時間間隔的概率分布概率分布 Y 服務時間的服務時間的概率分布概率分布 Z 服務臺的服務臺的個數個數 A 服務機構的容量（容納所有顧客的數量服務機構的容量（容納所有顧客的數量） B 顧客源的容

6、量顧客源的容量 C 排隊規(guī)則排隊規(guī)則衡量衡量一個排隊系統(tǒng)的好壞以及對一個排隊系統(tǒng)作經濟分析，需要一系列描述排隊系一個排隊系統(tǒng)的好壞以及對一個排隊系統(tǒng)作經濟分析，需要一系列描述排隊系統(tǒng)特征的數量指標，主要的數量指標通常有：統(tǒng)特征的數量指標，主要的數量指標通常有：n Ls：系統(tǒng)：系統(tǒng)中中顧客數顧客數的期望（平均）值。的期望（平均）值。n Lq：系統(tǒng)：系統(tǒng)中中排隊顧客數排隊顧客數的期望（平均）值。的期望（平均）值。n Ws：顧客：顧客在系統(tǒng)中在系統(tǒng)中逗留時間逗留時間的期望（平均）值。的期望（平均）值。n Wq：顧客：顧客在系統(tǒng)中在系統(tǒng)中排隊等待時間排隊等待時間的期望（平均）值。的期望（平均）值。n

7、Pl：系統(tǒng)：系統(tǒng)損失概率（系統(tǒng)滿容量的概率）。損失概率（系統(tǒng)滿容量的概率）。n A：占用：占用服務臺的平均數。服務臺的平均數。n ：服務臺服務臺的利用率。的利用率。研究研究主要數量指標在瞬時或平穩(wěn)狀態(tài)下的概率分布及其數字特征，主要數量指標在瞬時或平穩(wěn)狀態(tài)下的概率分布及其數字特征，了解系統(tǒng)的基本運行特征。了解系統(tǒng)的基本運行特征。檢驗檢驗系統(tǒng)是否達到平穩(wěn)狀態(tài)；檢驗顧客達到間隔的獨立性；確定服系統(tǒng)是否達到平穩(wěn)狀態(tài)；檢驗顧客達到間隔的獨立性；確定服務時間分布及參數。務時間分布及參數。：系統(tǒng)：系統(tǒng)的最優(yōu)設計和最優(yōu)運營問題。的最優(yōu)設計和最優(yōu)運營問題。一類一類重要且廣泛存在的排隊系統(tǒng)是重要且廣泛存在的排隊系

8、統(tǒng)是生滅過程生滅過程排隊系統(tǒng)。排隊系統(tǒng)。生滅過程生滅過程是一類特殊的隨機是一類特殊的隨機過程。在排隊論中，過程。在排隊論中，“生生”表示顧客的達到，表示顧客的達到，“滅滅”表示顧客的離去。表示顧客的離去。定義：定義：設設N（t），），t 0 是一個隨機過程（其中是一個隨機過程（其中N（t）表示時刻）表示時刻 t 系統(tǒng)中的顧系統(tǒng)中的顧客數）。若的概率分布具有如下性質：客數）。若的概率分布具有如下性質：n 假設假設N（t） = n ，則從時刻，則從時刻 t 起到下一個顧客起到下一個顧客達到達到時刻止的時間服從參數為時刻止的時間服從參數為 n 的負指數的負指數分布，分布，n = 0，1，2，。n 假

9、設假設N（t） = n ，則從時刻，則從時刻 t 起到下一個顧客起到下一個顧客離去離去時刻止的時間服從參數為時刻止的時間服從參數為 n 的負指數的負指數分布，分布，n = 0，1，2，。n 同一時刻只有一個顧客同一時刻只有一個顧客達到達到或或離去離去。則稱則稱N（t），），t 0 是一個生滅過程。是一個生滅過程。 N n+1 n n-1 n N-1 0 1 01n-1nn+1NN-1有限狀態(tài)有限狀態(tài)生滅過程：生滅過程：p0p1pn-1pnpn+1pN-1pN穩(wěn)態(tài)方程組：穩(wěn)態(tài)方程組： 0 p0 - 1 p1 = 0 ( n = 0 ) N-1 pN-1 - N pN = 0 ( n = N )(

10、 n-1 pn-1 + n+1 pn+1 ) ( n pn + n pn ) = 0 ( 1 n N-1 ) n n-1 n 0 1 01n-1nn+1N n+1p0p1pn-1pnpn+1pN穩(wěn)態(tài)方程組：穩(wěn)態(tài)方程組： 0 p0 - 1 p1 = 0 ( j = 0 ) ( n-1 pn-1 + n+1 pn+1 ) ( n pn + n pn ) = 0 ( j 1 )無限狀態(tài)無限狀態(tài)生滅過程：生滅過程：排隊論排隊論 Queuing Theory（QT）生滅過程簡介生滅過程簡介無限狀態(tài)無限狀態(tài)生滅過程的解生滅過程的解 記記 Cn = n-1 n-2 1 0 n n-1 2 1 n = 1，2

11、，則平穩(wěn)狀態(tài)時則平穩(wěn)狀態(tài)時生滅過程的解為：生滅過程的解為： Pn = CnP0 n = 1，2，其中其中 P0 = 11 + Cn n=1注意！無窮級數注意！無窮級數Cn 收斂時上式方有意義，這點可由系統(tǒng)進入平收斂時上式方有意義，這點可由系統(tǒng)進入平穩(wěn)狀態(tài)得到保證。穩(wěn)狀態(tài)得到保證。排隊論排隊論 Queuing Theory（QT）Poisson 過程和負指數分布過程和負指數分布Poisson 過程過程 Poisson 過程（又稱為過程（又稱為 Poisson 流、最簡流）是排隊論中最為常流、最簡流）是排隊論中最為常見的一種描述顧客達到規(guī)律的特殊隨機過程。見的一種描述顧客達到規(guī)律的特殊隨機過程。定

12、義：設定義：設 N（t）為時間）為時間 0，t 內達到系統(tǒng)的顧客數，如果滿足下內達到系統(tǒng)的顧客數，如果滿足下面三個條件：面三個條件：1.平穩(wěn)性：在平穩(wěn)性：在 t ， t + t 內有一個內有一個顧客達到的概率為顧客達到的概率為 t + ( t ) ；2.獨立性：在任意兩個不相交時間區(qū)間獨立性：在任意兩個不相交時間區(qū)間內內顧客達到相互獨立；顧客達到相互獨立；3.普通性：在普通性：在 t ， t + t 內多于一個內多于一個顧客達到的概率為顧客達到的概率為 ( t ) 。則稱則稱 N（t），），t 0 為為Poisson 過程。過程。排隊論排隊論 Queuing Theory（QT）Poisson

13、 過程和負指數分布過程和負指數分布Poisson 過程與負指數分布過程與負指數分布定理定理1 設設 N（t）為時間）為時間 0，t 內達到系統(tǒng)的顧客數，則內達到系統(tǒng)的顧客數，則N（t），t 0 為為Poisson 過程的充要條件是：過程的充要條件是： PN（t）= n = （ t ）n / n！ e- t n = 1，2，定理定理2 設設 N（t）為時間）為時間 0，t 內達到系統(tǒng)的顧客數，則內達到系統(tǒng)的顧客數，則N（t），t 0 為參數為為參數為 的的Poisson 過程的充要條件是：過程的充要條件是： 相繼達到時間間隔服從相互獨立的相繼達到時間間隔服從相互獨立的參數為參數為 的負指數分布。

14、的負指數分布。上述定理闡述了上述定理闡述了Poisson 過程與過程與負指數分布的等價性。負指數分布的等價性。排隊論排隊論 Queuing Theory（QT）常見常見排隊系統(tǒng)排隊系統(tǒng)生滅過程生滅過程排隊系統(tǒng)排隊系統(tǒng) M / M / n / n 損失制損失制排隊系統(tǒng)排隊系統(tǒng) M / M / n / 等待制等待制排隊系統(tǒng)排隊系統(tǒng) M / M / n / N 混合制混合制排隊系統(tǒng)排隊系統(tǒng) M / M / n / N 顧客源有限顧客源有限排隊系統(tǒng)排隊系統(tǒng)排隊論排隊論 Queuing Theory（QT）常見常見排隊系統(tǒng)排隊系統(tǒng)單服務臺模型單服務臺模型M / M / 1 （M / M / 1 / ）

15、01n-1nn+1N p0p1pn-1pnpn+1pN解為：解為： P0 = 1- ， （ = / ） Pn =（1- ） n ， （n 1 ）排隊論排隊論 Queuing Theory（QT）常見常見排隊系統(tǒng)排隊系統(tǒng)M / M / 1 （M / M / 1 / ）主要系統(tǒng)指標主要系統(tǒng)指標1.Ls = /（ 1- ）= /（ - ） 其中其中 0 12.Lq = Ls - = 2 /（ 1- ）3.Ws = Ls / = 1 /（ - ） 4.Wq = Lq / = Ws - 1 / = /（ - ） 排隊論排隊論 Queuing Theory（QT）常見常見排隊系統(tǒng)排隊系統(tǒng)多服務臺模型多服務

16、臺模型M / M / s （M / M / s / ）s 01s-1ss+1Ns p0p1ps-1psps+1pN解為：解為：排隊論排隊論 Queuing Theory（QT）常見常見排隊系統(tǒng)排隊系統(tǒng)多服務臺系統(tǒng)與單多服務臺系統(tǒng)的比較多服務臺系統(tǒng)與單多服務臺系統(tǒng)的比較一個一個M / M / 3 與三個與三個M / M / 1 的比較的比較 臺臺1 臺臺2 臺臺3 臺臺1 臺臺2 臺臺3 一個一個M / M / 3三個三個M / M / 1 從這兩個系統(tǒng)的主要指標比較可以看出混合排隊比獨立排隊具有顯著的優(yōu)越性，這一點從這兩個系統(tǒng)的主要指標比較可以看出混合排隊比獨立排隊具有顯著的優(yōu)越性，這一點是在

17、排隊系統(tǒng)的排隊方式的設計時應該注意的。是在排隊系統(tǒng)的排隊方式的設計時應該注意的。排隊論排隊論 Queuing Theory（QT）常見常見排隊系統(tǒng)排隊系統(tǒng)非生滅過程非生滅過程排隊系統(tǒng)排隊系統(tǒng) 一個排隊系統(tǒng)的特征是由輸入過程、服務機制和排隊規(guī)則三大一個排隊系統(tǒng)的特征是由輸入過程、服務機制和排隊規(guī)則三大要素決定的。前面所討論的排隊模型要素決定的。前面所討論的排隊模型 “M / M /” 型的，這類排隊系型的，這類排隊系統(tǒng)的一個主要特征是馬爾可夫性，而馬爾可夫性的一個主要性質是統(tǒng)的一個主要特征是馬爾可夫性，而馬爾可夫性的一個主要性質是由系統(tǒng)當前的狀態(tài)可以推斷未來的狀態(tài)。但是，當系統(tǒng)不是由系統(tǒng)當前的狀

18、態(tài)可以推斷未來的狀態(tài)。但是，當系統(tǒng)不是“M/M/”型時，僅僅知道系統(tǒng)內當前的顧客數，對于推斷系統(tǒng)未來型時，僅僅知道系統(tǒng)內當前的顧客數，對于推斷系統(tǒng)未來的狀態(tài)是不充足的，因為正在接受服務的顧客，已經被服務了多長的狀態(tài)是不充足的，因為正在接受服務的顧客，已經被服務了多長時間，將影響其離開系統(tǒng)的時間。因此，須引入新的方法來分析具時間，將影響其離開系統(tǒng)的時間。因此，須引入新的方法來分析具有有非非負指數分布的排隊系統(tǒng)。負指數分布的排隊系統(tǒng)。 一般而言，具有一般而言，具有非非負指數分布的排隊系統(tǒng)的分析是非常困難的負指數分布的排隊系統(tǒng)的分析是非常困難的。排隊論排隊論 Queuing Theory（QT）常見

19、常見排隊系統(tǒng)排隊系統(tǒng)非生滅過程非生滅過程排隊系統(tǒng)排隊系統(tǒng)一般服務時間模型一般服務時間模型 M / G / 1 模型模型 M / G / 1 系統(tǒng)是顧客達到為系統(tǒng)是顧客達到為Poisson流，單服務臺，服務時間為流，單服務臺，服務時間為一般分布的排隊系統(tǒng)。一般分布的排隊系統(tǒng)。設：設： 顧客的平均達到率；顧客的平均達到率； T 服務時間；服務時間； E T 平均服務時間；平均服務時間； 2 Var T 方差；方差； E T ，為使系統(tǒng)達到穩(wěn)態(tài)，必須有，為使系統(tǒng)達到穩(wěn)態(tài)，必須有 1。 當時，系統(tǒng)可以達到平穩(wěn)狀態(tài)，而要給出平穩(wěn)分布的顯示是比當時，系統(tǒng)可以達到平穩(wěn)狀態(tài)，而要給出平穩(wěn)分布的顯示是比較困難的

20、。已有的幾個結果是：較困難的。已有的幾個結果是：排隊論排隊論 Queuing Theory（QT）常見常見排隊系統(tǒng)排隊系統(tǒng)非生滅過程非生滅過程排隊系統(tǒng)排隊系統(tǒng)波拉切克（波拉切克（Pollaczek） 欣欽（欣欽（Khintchine）公式）公式 （P- K）公式：）公式：Lq = 2 + 2 2 2（1- ）此外有：此外有： Ls = Lq + Ws = Ls / Wq = Lq / 排隊論排隊論 Queuing Theory（QT）常見常見排隊系統(tǒng)排隊系統(tǒng)非生滅過程非生滅過程排隊系統(tǒng)排隊系統(tǒng)波拉切克（波拉切克（Pollaczek） 欣欽（欣欽（Khintchine）公式）公式 由以上的（由以

21、上的（P K）公式可以看出）公式可以看出 Ls、Lq、Ws、Wq 等排隊系等排隊系統(tǒng)的重要指標僅僅依賴于統(tǒng)的重要指標僅僅依賴于 和服務時間的方差和服務時間的方差 2 ，而與分布的類型，而與分布的類型無關，這是排隊論中一個無關，這是排隊論中一個非常重要而又令人驚奇的結果！非常重要而又令人驚奇的結果！ 從（從（P K）公式不難看出，當公式不難看出，當 確定后，當方差確定后，當方差 2 減少時，減少時，平均隊長和等待時間都將減少。因此，可通過服務時間的平均隊長和等待時間都將減少。因此，可通過服務時間的方差來縮方差來縮短短平均隊長，當且僅當平均隊長，當且僅當 2 = 0 ，即服務時間為定長時，平均隊長

22、和，即服務時間為定長時，平均隊長和等待時間可減少到最少水平，這一點是符號直觀的，因為服務時間等待時間可減少到最少水平，這一點是符號直觀的，因為服務時間越有規(guī)律，等待的時間也就越短。越有規(guī)律，等待的時間也就越短。排隊論排隊論 Queuing Theory（QT）排隊系統(tǒng)的優(yōu)化排隊系統(tǒng)的優(yōu)化排隊系統(tǒng)的最優(yōu)化設計排隊系統(tǒng)的最優(yōu)化設計1、 以最少的以最少的“設備設備”獲得最大的效益，或者說，在一定的服務質獲得最大的效益，或者說，在一定的服務質量指標下要求服務機構最為經濟。量指標下要求服務機構最為經濟。2、 給出排隊系統(tǒng)的某種費用結構，要求總費用最優(yōu)的情況下對系給出排隊系統(tǒng)的某種費用結構，要求總費用最優(yōu)的情況下對系統(tǒng)的服務率統(tǒng)的服務率 、服務臺數服務臺數n、系統(tǒng)容量、系統(tǒng)容量N、以及排隊規(guī)則等等進行設、以及排隊規(guī)則等等進行