運(yùn)籌學(xué)第11章 排隊(duì)論

1、作為排隊(duì)系統(tǒng)（隨機(jī)服務(wù)系統(tǒng)）的數(shù)學(xué)理論和方法，是作為排隊(duì)系統(tǒng)（隨機(jī)服務(wù)系統(tǒng)）的數(shù)學(xué)理論和方法，是運(yùn)籌學(xué)的一個(gè)重要分支運(yùn)籌學(xué)的一個(gè)重要分支。 排隊(duì)是日常生活中經(jīng)常遇到的現(xiàn)象，如進(jìn)餐館就餐、圖排隊(duì)是日常生活中經(jīng)常遇到的現(xiàn)象，如進(jìn)餐館就餐、圖書(shū)館借書(shū)、在車(chē)站候車(chē)、售票處購(gòu)票等等。排隊(duì)問(wèn)題的表現(xiàn)形式往往是擁擠現(xiàn)象，書(shū)館借書(shū)、在車(chē)站候車(chē)、售票處購(gòu)票等等。排隊(duì)問(wèn)題的表現(xiàn)形式往往是擁擠現(xiàn)象，隨著生產(chǎn)與服務(wù)的日益社會(huì)化，由排隊(duì)引起的擁擠現(xiàn)象會(huì)越來(lái)越普遍隨著生產(chǎn)與服務(wù)的日益社會(huì)化，由排隊(duì)引起的擁擠現(xiàn)象會(huì)越來(lái)越普遍。下面。下面我們列我們列舉出部分形形色色的排隊(duì)舉出部分形形色色的排隊(duì)系統(tǒng)。系統(tǒng)。達(dá)到的顧客達(dá)到的顧客

2、要求服務(wù)的內(nèi)容要求服務(wù)的內(nèi)容服務(wù)的機(jī)構(gòu)服務(wù)的機(jī)構(gòu)出故障的機(jī)器出故障的機(jī)器修理技工修理技工病人病人電話呼叫電話呼叫進(jìn)港貨船進(jìn)港貨船入水庫(kù)河水入水庫(kù)河水達(dá)到機(jī)場(chǎng)上空的飛機(jī)達(dá)到機(jī)場(chǎng)上空的飛機(jī)刑事案件刑事案件達(dá)到路口的車(chē)輛達(dá)到路口的車(chē)輛來(lái)犯敵機(jī)來(lái)犯敵機(jī)修理修理領(lǐng)取修配零件領(lǐng)取修配零件診斷（或治療）診斷（或治療）通話通話裝（卸）貨裝（卸）貨放水、調(diào)整水位放水、調(diào)整水位降落降落偵破偵破通過(guò)路口通過(guò)路口截?fù)艚負(fù)粜蘩砑脊ば蘩砑脊ぐl(fā)放發(fā)放修配零件修配零件的管理員的管理員醫(yī)生（或治療設(shè)備）醫(yī)生（或治療設(shè)備）交換臺(tái)交換臺(tái)裝（卸）貨碼頭（泊位）裝（卸）貨碼頭（泊位）水閘、管理員水閘、管理員跑道跑道刑偵部門(mén)刑偵部門(mén)交通

3、信號(hào)燈交通信號(hào)燈我防空部隊(duì)我防空部隊(duì)排隊(duì)排隊(duì)可以是有形的隊(duì)列，也可以是無(wú)形的隊(duì)列。排隊(duì)可以是人，也可以是物?？梢允怯行蔚年?duì)列，也可以是無(wú)形的隊(duì)列。排隊(duì)可以是人，也可以是物。 顧客源顧客源排隊(duì)結(jié)構(gòu)排隊(duì)結(jié)構(gòu)服服務(wù)務(wù)機(jī)機(jī)構(gòu)構(gòu)顧客到來(lái)顧客到來(lái)排隊(duì)規(guī)則排隊(duì)規(guī)則服務(wù)規(guī)則服務(wù)規(guī)則顧客離去顧客離去1單隊(duì)單隊(duì) 單服務(wù)臺(tái)系統(tǒng)單服務(wù)臺(tái)系統(tǒng)1單隊(duì)單隊(duì)多服務(wù)臺(tái)（并聯(lián)）系統(tǒng)多服務(wù)臺(tái)（并聯(lián)）系統(tǒng)2S.1S單隊(duì)單隊(duì)多服務(wù)臺(tái)（串聯(lián)）系統(tǒng)多服務(wù)臺(tái)（串聯(lián)）系統(tǒng)1多隊(duì)多隊(duì)多服務(wù)臺(tái)（并聯(lián)）系統(tǒng)多服務(wù)臺(tái)（并聯(lián)）系統(tǒng).2S多隊(duì)多隊(duì)多服務(wù)臺(tái)（混聯(lián)、網(wǎng)絡(luò)）系統(tǒng)多服務(wù)臺(tái)（混聯(lián)、網(wǎng)絡(luò)）系統(tǒng)說(shuō)明說(shuō)明顧客按怎樣的規(guī)律達(dá)到系統(tǒng)，通常從顧客按怎樣的規(guī)律達(dá)

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

5、接形式（并聯(lián)或串聯(lián)）n 顧客顧客接受服務(wù)的方式（單個(gè)或成批接受服務(wù)的方式（單個(gè)或成批）n 服務(wù)時(shí)間分布服務(wù)時(shí)間分布其中其中服務(wù)時(shí)間分布是最重要因素，其常見(jiàn)的分布有服務(wù)時(shí)間分布是最重要因素，其常見(jiàn)的分布有：n 定定長(zhǎng)分布（長(zhǎng)分布（D）n 負(fù)負(fù)指數(shù)分布（指數(shù)分布（M）n k 階愛(ài)爾朗分布（階愛(ài)爾朗分布（Ek）一般一般形式：形式： X / Y / Z / A / B / C X 顧客相繼達(dá)到時(shí)間間隔的顧客相繼達(dá)到時(shí)間間隔的概率分布概率分布 Y 服務(wù)時(shí)間的服務(wù)時(shí)間的概率分布概率分布 Z 服務(wù)臺(tái)的服務(wù)臺(tái)的個(gè)數(shù)個(gè)數(shù) A 服務(wù)機(jī)構(gòu)的容量（容納所有顧客的數(shù)量服務(wù)機(jī)構(gòu)的容量（容納所有顧客的數(shù)量） B 顧客源的容

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

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

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

9、設(shè)假設(shè)N（t） = n ，則從時(shí)刻，則從時(shí)刻 t 起到下一個(gè)顧客起到下一個(gè)顧客離去離去時(shí)刻止的時(shí)間服從參數(shù)為時(shí)刻止的時(shí)間服從參數(shù)為 n 的負(fù)指數(shù)的負(fù)指數(shù)分布，分布，n = 0，1，2，。n 同一時(shí)刻只有一個(gè)顧客同一時(shí)刻只有一個(gè)顧客達(dá)到達(dá)到或或離去離去。則稱(chēng)則稱(chēng)N（t），），t 0 是一個(gè)生滅過(guò)程。是一個(gè)生滅過(guò)程。 N n+1 n n-1 n N-1 0 1 01n-1nn+1NN-1有限狀態(tài)有限狀態(tài)生滅過(guò)程：生滅過(guò)程：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 )無(wú)限狀態(tài)無(wú)限狀態(tài)生滅過(guò)程：生滅過(guò)程：排隊(duì)論排隊(duì)論 Queuing Theory（QT）生滅過(guò)程簡(jiǎn)介生滅過(guò)程簡(jiǎn)介無(wú)限狀態(tài)無(wú)限狀態(tài)生滅過(guò)程的解生滅過(guò)程的解 記記 Cn = n-1 n-2 1 0 n n-1 2 1 n = 1，2

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

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

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

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

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

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

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

18、態(tài)可以推斷未來(lái)的狀態(tài)。但是，當(dāng)系統(tǒng)不是“M/M/”型時(shí)，僅僅知道系統(tǒng)內(nèi)當(dāng)前的顧客數(shù)，對(duì)于推斷系統(tǒng)未來(lái)型時(shí)，僅僅知道系統(tǒng)內(nèi)當(dāng)前的顧客數(shù)，對(duì)于推斷系統(tǒng)未來(lái)的狀態(tài)是不充足的，因?yàn)檎诮邮芊?wù)的顧客，已經(jīng)被服務(wù)了多長(zhǎng)的狀態(tài)是不充足的，因?yàn)檎诮邮芊?wù)的顧客，已經(jīng)被服務(wù)了多長(zhǎng)時(shí)間，將影響其離開(kāi)系統(tǒng)的時(shí)間。因此，須引入新的方法來(lái)分析具時(shí)間，將影響其離開(kāi)系統(tǒng)的時(shí)間。因此，須引入新的方法來(lái)分析具有有非非負(fù)指數(shù)分布的排隊(duì)系統(tǒng)。負(fù)指數(shù)分布的排隊(duì)系統(tǒng)。 一般而言，具有一般而言，具有非非負(fù)指數(shù)分布的排隊(duì)系統(tǒng)的分析是非常困難的負(fù)指數(shù)分布的排隊(duì)系統(tǒng)的分析是非常困難的。排隊(duì)論排隊(duì)論 Queuing Theory（QT）常見(jiàn)

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

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

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

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