1排隊論1排隊論2第8章排隊論(QueuingTheory)

排隊論（queuing),也稱隨機服務(wù)系統(tǒng)理論，是運籌學(xué)的一個主要分支。

1909年，丹麥哥本哈根電子公司電話工程師A.K.Erlang的開創(chuàng)性論文“概率論和電話通訊理論”標(biāo)志此理論的誕生。排隊論的發(fā)展最早是與電話，通信中的問題相聯(lián)系的，并到現(xiàn)在是排隊論的傳統(tǒng)的應(yīng)用領(lǐng)域。近年來在計算機通訊網(wǎng)絡(luò)系統(tǒng)、交通運輸、醫(yī)療衛(wèi)生系統(tǒng)、庫存管理、作戰(zhàn)指揮等各領(lǐng)域中均得到應(yīng)用。2第8章排隊論(QueuingTheory)38排隊論8-1前言8-2基本概念8-3輸入過程和服務(wù)時間分布8-4泊松輸入—指數(shù)服務(wù)排隊模型8-5M/M/1無限源系統(tǒng)8-6系統(tǒng)容量有限的排隊系統(tǒng)8-7顧客源有限的排隊系統(tǒng)38排隊論8-1前言4

排隊是我們在日常生活和生產(chǎn)中經(jīng)常遇到的現(xiàn)象。例如，上、下班搭乘公共汽車；顧客到商店購買物品；病員到醫(yī)院看病；旅客到售票處購買車票；學(xué)生去食堂就餐等就常常出現(xiàn)排隊和等待現(xiàn)象。前言4排隊是我們在日常生活和生產(chǎn)中經(jīng)常遇5

除了上述有形的排隊之外，還有大量的所謂“無形”排隊現(xiàn)象。如幾個顧客打電話到出租汽車站要求派車，如果出租汽車站無足夠車輛、則部分顧客只得在各自的要車處等待，他們分散在不同地方，卻形成了一個無形隊列在等待派車。

前言5除了上述有形的排隊之外，還有大量的所謂6

排隊的不一定是人，也可以是物：例如，通訊衛(wèi)星與地面若干待傳遞的信息；生產(chǎn)線上原料、半成品等待加工；因故障停止運轉(zhuǎn)的機器等待修理；碼頭的船只等待裝卸貨物；要降落的飛機因跑道不空而在空中盤旋等等。前言6排隊的不一定是人，也可以是物：前言7

上述各種問題雖互不相同，但卻都有要求得到某種服務(wù)的人或物和提供服務(wù)的人或機構(gòu)。排隊論里把要求服務(wù)的對象統(tǒng)稱為“顧客”,提供服務(wù)的人或機構(gòu)稱為“服務(wù)臺”或“服務(wù)員”。前言7上述各種問題雖互不相同，但卻都有要求得到某種8

不同的顧客與服務(wù)組成了各式各樣的服務(wù)系統(tǒng)。顧客為了得到某種服務(wù)而到達系統(tǒng)、若不能立即獲得服務(wù)而又允許排隊等待，則加入等待隊伍，待獲得服務(wù)后離開系統(tǒng)，見圖8-1至圖8-5。圖8-1單服務(wù)臺排隊系統(tǒng)前言8不同的顧客與服務(wù)組成了各式各樣的服務(wù)系統(tǒng)。顧客9圖8-2單隊列——S個服務(wù)臺并聯(lián)的排隊系統(tǒng)圖8-3S個隊列——S個服務(wù)臺的并聯(lián)排隊系統(tǒng)前言9圖8-2單隊列——S個服務(wù)臺并聯(lián)的排隊系統(tǒng)圖8-310圖8-4單隊——多個服務(wù)臺的串聯(lián)排隊系統(tǒng)

圖8-5多隊——多服務(wù)臺混聯(lián)網(wǎng)絡(luò)系統(tǒng)前言10圖8-4單隊——多個服務(wù)臺的串聯(lián)排隊系統(tǒng)

圖8-511圖8-6隨機服務(wù)系統(tǒng)前言一般的排隊系統(tǒng)，都可由下面圖加以描述。通常稱由圖8-6表示的系統(tǒng)為一隨機聚散服務(wù)系統(tǒng)。任一排隊系統(tǒng)都是一個隨機聚散服務(wù)系統(tǒng)。“聚”表示顧客的到達，“散”表示顧客的離去。11圖8-6隨機服務(wù)系統(tǒng)前言一般的排隊系統(tǒng)，都可由下12

面對擁擠現(xiàn)象，人們總是希望盡量設(shè)法減少排隊，通常的做法是增加服務(wù)設(shè)施。但是增加的數(shù)量越多，人力、物力的支出就越大，甚至?xí)霈F(xiàn)空閑浪費。如果服務(wù)設(shè)施太少，顧客排隊等待的時間就會很長，這樣對顧客會帶來不良影響。前言12面對擁擠現(xiàn)象，人們總是希望盡量設(shè)法減少排隊，13

顧客排隊時間的長短與服務(wù)設(shè)施規(guī)模的大小，就構(gòu)成了設(shè)計隨機服務(wù)系統(tǒng)中的一對矛盾。如何做到既保證一定的服務(wù)質(zhì)量指標(biāo)，又使服務(wù)設(shè)施費用經(jīng)濟合理，恰當(dāng)?shù)亟鉀Q顧客排隊時間與服務(wù)設(shè)施費用大小這對矛盾。這就是隨機服務(wù)系統(tǒng)理論——排隊論所要研究解決的問題。前言13顧客排隊時間的長短與服務(wù)設(shè)施規(guī)模的大小，就構(gòu)14一、排隊系統(tǒng)的組成與特征排隊系統(tǒng)一般有三個基本組成部分：1.輸入過程；2.排隊規(guī)則；3.服務(wù)機構(gòu)。§8-2排隊系統(tǒng)的基本概念14一、排隊系統(tǒng)的組成與特征§8-2排隊系統(tǒng)的基本概念15

輸入即為顧客的到達，可有下列情況：

1）顧客源可能是有限的，也可能是無限的。

2）顧客是成批到達或是單個到達。

3）顧客到達間隔時間可能是隨機的或確定的。

4）顧客到達可能是相互獨立或關(guān)聯(lián)的。所謂獨立就是以前顧客的到達對以后顧客的到達無影響。

5）輸入過程可以是平穩(wěn)的（stationary）或說是對時間齊次的（Homogeneousintime），也可以是非平穩(wěn)的。輸入過程平穩(wěn)的指顧客相繼到達的間隔時間分布和參數(shù)（均值、方差）與時間無關(guān)；非平穩(wěn)的則是與時間相關(guān)，非平穩(wěn)的處理比較困難。

1.輸入過程15輸入即為顧客的到達，可有下列情況：1.輸入過程16這是指服務(wù)臺從隊列中選取顧客進行服務(wù)的順序。可以分為損失制、等待制、混合制3大類。

(1)損失制。這是指如果顧客到達排隊系統(tǒng)時，所有服務(wù)臺都已被先來的顧客占用，那么他們就自動離開系統(tǒng)永不再來。典型例子是，如電話拔號后出現(xiàn)忙音，顧客不愿等待而自動掛斷電話，如要再打，就需重新拔號，這種服務(wù)規(guī)則即為損失制。2.排隊規(guī)則16這是指服務(wù)臺從隊列中選取顧客進行服務(wù)的順序。2.排隊規(guī)17

(2)等待制。指當(dāng)顧客來到系統(tǒng)時，所有服務(wù)臺都不空，顧客加入排隊行列等待服務(wù)。例如，排隊等待售票，故障設(shè)備等待維修等。等待制中，服務(wù)臺在選擇顧客進行服務(wù)時，常有如下四種規(guī)則：

①先到先服務(wù)（FCFS）。按顧客到達的先后順序?qū)︻櫩瓦M行服務(wù)，這是最普遍的情形。②后到先服務(wù)（LCFS）。倉庫中迭放的鋼材，后迭放上去的都先被領(lǐng)走，就屬于這種情況。2.排隊規(guī)則17(2)等待制。指當(dāng)顧客來到系統(tǒng)時，所有服務(wù)臺18③隨機服務(wù)（RAND）。即當(dāng)服務(wù)臺空閑時，不按照排隊序列而隨意指定某個顧客去接受服務(wù)，如電話交換臺接通呼叫電話就是一例。

④優(yōu)先權(quán)服務(wù)（PR）。如老人、兒童先進車站；危重病員先就診；遇到重要數(shù)據(jù)需要處理計算機立即中斷其他數(shù)據(jù)的處理等，均屬于此種服務(wù)規(guī)則。2.排隊規(guī)則18③隨機服務(wù)（RAND）。即當(dāng)服務(wù)19

(3)混合制．這是等待制與損失制相結(jié)合的一種服務(wù)規(guī)則，一般是指允許排隊，但又不允許隊列無限長下去。具體說來，大致有三種：

①隊長有限。當(dāng)排隊等待服務(wù)顧客人數(shù)超過規(guī)定數(shù)量時，后來顧客就自動離去，另求服務(wù)。如水庫的庫容、旅館的床位等都是有限的。2.排隊規(guī)則19(3)混合制．這是等待制與損失制相結(jié)合的一種20

②等待時間有限。即顧客在系統(tǒng)中的等待時間不超過某一給定的長度T，當(dāng)?shù)却龝r間超過T時，顧客自動離去，不再回來。如易損壞的電子元器件的庫存問題，超過一定存儲時間被自動認為失效。又如顧客到飯館就餐，等了一定時間后不愿再等而自動離去另找飯店用餐。2.排隊規(guī)則20②等待時間有限。即顧客在系統(tǒng)中的等待時間不21

③逗留時間(等待時間與服務(wù)時間之和)有限。例如用高射炮射擊敵機，當(dāng)敵機飛越高射炮射擊有效區(qū)域的時間為t時，若在這個時間內(nèi)未被擊落，也就不可能再被擊落了。不難注意到，損失制和等待制可看成是混合制的特殊情形，如記c為系統(tǒng)中服務(wù)臺的個數(shù)，則當(dāng)K=c

時，混合制即成為損失制；當(dāng)K=∞時，混合制即成為等待制。2.排隊規(guī)則21③逗留時間(等待時間與服務(wù)時間之和)有限。223.服務(wù)機構(gòu)1）服務(wù)機構(gòu)可以是單服務(wù)員和多服務(wù)員服務(wù)，這種服務(wù)形式與隊列規(guī)則聯(lián)合后形成了多種不同隊列，不同形式的排隊服務(wù)機構(gòu)。如前圖8-1到8-5：2)服務(wù)方式分為單個顧客服務(wù)和成批顧客服務(wù)。3)服務(wù)時間分為確定型和隨機型。4)服務(wù)時間的分布在這里我們假定是平穩(wěn)的。223.服務(wù)機構(gòu)1）服務(wù)機構(gòu)可以是單服務(wù)員和多服務(wù)員23上述特征中最主要的、影響最大的是：顧客相繼到達的間隔時間分布服務(wù)時間的分布服務(wù)臺數(shù)D.G.Kendall，1953提出了分類法，稱為Kendall記號(適用于并列服務(wù)臺)即：[X/Y/Z]:[d/e/f]二、排隊系統(tǒng)的描述符號與模型分類23上述特征中最主要的、影響最大的是：二、排隊系統(tǒng)的描述符號24式中：X——顧客相繼到達間隔時間分布。M—負指數(shù)分布Markov，D—確定型分布Deterministic，Ek—K階愛爾朗分布Erlang，GI—一般相互獨立隨機分布(GeneralIndependent)，G—一般隨機分布。Y——填寫服務(wù)時間分布（與上同）Z——填寫并列的服務(wù)臺數(shù)d——排隊系統(tǒng)的最大容量e——顧客源數(shù)量f——排隊規(guī)則如[M/M/1]:[∞/∞/FCFS]即為顧客到達為泊松過程，服務(wù)時間為負指數(shù)分布，單臺，無限容量，無限源，先到先服務(wù)的排隊系統(tǒng)模型。24式中：X——顧客相繼到達間隔時間分布。25三、排隊論研究的基本問題

1.排隊系統(tǒng)的統(tǒng)計推斷:即通過對排隊系統(tǒng)主要參數(shù)的統(tǒng)計推斷和對排隊系統(tǒng)的結(jié)構(gòu)分析，判斷一個給定的排隊系統(tǒng)符合于哪種模型，以便根據(jù)排隊理論進行研究。

2.系統(tǒng)性態(tài)問題:即研究各種排隊系統(tǒng)的概率規(guī)律性，主要研究隊長分布、等待時間分布和忙期分布等統(tǒng)計指標(biāo),包括了瞬態(tài)和穩(wěn)態(tài)兩種情形。

3.最優(yōu)化問題：即包括最優(yōu)設(shè)計(靜態(tài)優(yōu)化)，最優(yōu)設(shè)計是指在一定質(zhì)量指標(biāo)下要求機構(gòu)最經(jīng)濟，如輸入結(jié)構(gòu)與服務(wù)系統(tǒng)的最優(yōu)設(shè)計，排隊規(guī)則的最優(yōu)設(shè)計等。最優(yōu)運營（動態(tài)優(yōu)化），最優(yōu)運營是指對給定的系統(tǒng)，如何經(jīng)營可使目標(biāo)函數(shù)達到最優(yōu)值。25三、排隊論研究的基本問題26排隊問題求解(主要指性態(tài)問題)

求解一般排隊系統(tǒng)問題的目的主要是通過研究排隊系統(tǒng)運行的效率指標(biāo)，估計服務(wù)質(zhì)量，確定系統(tǒng)的合理結(jié)構(gòu)和系統(tǒng)參數(shù)的合理值，以便實現(xiàn)對現(xiàn)有系統(tǒng)合理改進和對新建系統(tǒng)的最優(yōu)設(shè)計等。排隊問題的一般步驟：

1.確定或擬合排隊系統(tǒng)顧客到達的時間間隔分布和服務(wù)時間分布(可實測)。

2.研究分析排隊系統(tǒng)理論分布的概率特征。

3.研究系統(tǒng)狀態(tài)的概率。系統(tǒng)狀態(tài)是指系統(tǒng)中顧客數(shù)。狀態(tài)概率用Pn(t)表示,即在t時刻系統(tǒng)中有n個顧客的概率，也稱瞬態(tài)概率。26排隊問題求解(主要指性態(tài)問題)求解一般排隊系統(tǒng)問題27

求解狀態(tài)概率Pn(t)方法是建立含Pn(t)的微分差分方程，通過求解微分差分方程得到系統(tǒng)瞬態(tài)解，由于瞬態(tài)解一般求出確定值比較困難，即便求得一般也很難使用。因此常常使用它的極限(如果存在的話)：穩(wěn)態(tài)的物理意義圖，系統(tǒng)的穩(wěn)態(tài)一般很快都能達到，但實際中達不到穩(wěn)態(tài)的現(xiàn)象也存在。要注意的是求穩(wěn)態(tài)概率Pn并不一定求t→∞的極限,只需求Pn’(t)=0。過渡狀態(tài)穩(wěn)定狀態(tài)pnt圖3排隊系統(tǒng)狀態(tài)變化示意圖

稱為穩(wěn)態(tài)(steadystate)解，或稱統(tǒng)計平衡狀態(tài)(StatisticalEquilibriumState)的解。27求解狀態(tài)概率Pn(t)方法是建立含Pn(t)的微28

4.根據(jù)排隊系統(tǒng)對應(yīng)的理論模型求用以判斷系統(tǒng)運行優(yōu)劣的基本數(shù)量指標(biāo)的概率分布或特征數(shù)。數(shù)量指標(biāo)主要包括:(1)平均隊長（Ls）:系統(tǒng)中的顧客數(shù)。

平均隊列長（Lg）:系統(tǒng)中排隊等待服務(wù)的顧客數(shù)。系統(tǒng)中顧客數(shù)Ls=系統(tǒng)中排隊等待服務(wù)的顧客數(shù)Lg+正被服務(wù)的顧客數(shù)c(2)平均逗留時間(Ws):指一個顧客在系統(tǒng)中的停留時間。

平均等待時間(Wg):一個顧客在系統(tǒng)中排隊等待的時間。(3)忙期：指從顧客到達空閑服務(wù)機構(gòu)起到服務(wù)機構(gòu)再次為空閑這段時間長度。（忙期和一個忙期中平均完成服務(wù)顧客數(shù)都是衡量服務(wù)機構(gòu)效率的指標(biāo)，忙期關(guān)系到工作強度）

5.排隊系統(tǒng)指標(biāo)優(yōu)化含優(yōu)化設(shè)計與優(yōu)化運營（見25頁）。問題1

系統(tǒng)中顧客數(shù)=平均隊長（Ls）+1？284.根據(jù)排隊系統(tǒng)對應(yīng)的理論模型求用以判斷系統(tǒng)運行29四、排隊論主要知識點排隊系統(tǒng)的組成與特征排隊系統(tǒng)的模型分類顧客到達間隔時間和服務(wù)時間的經(jīng)驗分布與理論分布穩(wěn)態(tài)概率Pn的計算標(biāo)準(zhǔn)的M/M/1模型([M/M/1]:[∞/∞/FCFS])系統(tǒng)容量有限制的模型[M/M/1]:[N/∞/FCFS]顧客源有限模型[M/M/1][∞/M/FCFS]標(biāo)準(zhǔn)的[M/M/C]模型[M/M/C]:[∞/∞/FCFS]29四、排隊論主要知識點排隊系統(tǒng)的組成與特征30M/M/C型系統(tǒng)和C個M/M/1型系統(tǒng)系統(tǒng)容量有限制的多服務(wù)臺模型(M/M/C/N/∞)顧客源為有限的多服務(wù)臺模型(M/M/C/∞/M)一般服務(wù)時間的（M/G/1）模型Pollaczek-Khintchine(P-K)公式定長服務(wù)時間M/D/1模型愛爾朗服務(wù)時間M/Ek/1模型排隊系統(tǒng)優(yōu)化M/M/1模型中的最優(yōu)服務(wù)率u標(biāo)準(zhǔn)的M/M/1Model系統(tǒng)容量為N的情形M/M/C模型中最優(yōu)服務(wù)臺數(shù)C30M/M/C型系統(tǒng)和C個M/M/1型系統(tǒng)318-3到達間隔時間分布和服務(wù)時間的分布一個排隊系統(tǒng)的最主要特征參數(shù)是顧客的到達間隔時間分布與服務(wù)時間分布。要研究到達間隔時間分布與服務(wù)時間分布需要首先根據(jù)現(xiàn)存系統(tǒng)原始資料統(tǒng)計出它們的經(jīng)驗分布，然后與理論分布擬合，若能照應(yīng)，我們就可以得出上述的分布情況。318-3到達間隔時間分布和服務(wù)時間的分布一個排隊系統(tǒng)的最32一、經(jīng)驗分布

經(jīng)驗分布是對排隊系統(tǒng)的某些時間參數(shù)根據(jù)經(jīng)驗數(shù)據(jù)進行統(tǒng)計分析，并依據(jù)統(tǒng)計分析結(jié)果假設(shè)其統(tǒng)計樣本的總體分布，選擇合適的檢驗方法進行檢驗，當(dāng)通過檢驗時，我們認為時間參數(shù)的經(jīng)驗數(shù)據(jù)服從該假設(shè)分布。分布的擬合檢驗一般采用χ2檢驗。由數(shù)理統(tǒng)計的知識我們知：若樣本量n充分大(n≥50)，則當(dāng)假設(shè)H0為真時，統(tǒng)計量總是近似地服從自由度為k-r-1的χ2分布，其中k為分組數(shù)，r為檢驗分布中被估計的參數(shù)個數(shù)。32一、經(jīng)驗分布經(jīng)驗分布是對排隊系統(tǒng)的某些時33式中：fi——實際頻數(shù)

ni——理論頻數(shù)上面方法的應(yīng)用必須注意n要足夠大，npi不能太小。一般地n要大于50，而分組的npi應(yīng)不小于5。例題：某公共汽車站，統(tǒng)計來站的乘客流，規(guī)定每隔1分鐘統(tǒng)計一次乘客到達情況，共統(tǒng)計100次，其結(jié)果如表所示，問顧客是否服從普阿松流。當(dāng)時，在顯著水平α下接受假設(shè)H033式中：fi——實際頻數(shù)當(dāng)時，在顯著水平α下接受假設(shè)H034解：先估計分布的參數(shù)λ，由極大似然估計法得：,并根據(jù)公式可計算出理論頻率、理論頻數(shù)及項

見下頁表所示查表知:故可接受泊松分布假設(shè)。34解：先估計分布的參數(shù)λ，由極大似然估計法得：,并根據(jù)公式35∑=6.2815K-r-1=8-1-135∑=6.2815K-r-1=8-1-136隨機變量數(shù)隨著實驗的結(jié)果的不同而變化離散型：的所有可能只有限或至多可列個連續(xù)型：（）取值于某個區(qū)間（a，b）分布函數(shù)(連續(xù)):的概率分布(離散):i=1,2,3……二、概率論知識復(fù)習(xí)36隨機變量數(shù)隨著實驗的結(jié)果的不同而變化37數(shù)學(xué)期望:(離散)E(ξ)=

(連續(xù))E(ξ)=

方差:=條件概率:密度函數(shù):(連續(xù)),,37數(shù)學(xué)期望:(離散)E(ξ)=(連續(xù)38三、理論分布

式中λ為常數(shù)(λ>0)，稱X服從參數(shù)為λ的泊松分布，若在上式中引入時間參數(shù)t，即令λt代替λ，則有：

1.泊松分布在概率論中，我們曾學(xué)過泊松分布，設(shè)隨機變量為X，則有：n=0,1,2,…（1）

與時間有關(guān)的隨機變量的概率，是一個隨機過程，即泊松過程。t>0，n=0,1,2,…（2）38三、理論分布式中λ為常數(shù)(λ>0)，39（t2>t1，n≥0）

若設(shè)N(t)表示在時間區(qū)間[0,t)內(nèi)到達的顧客數(shù)(t>0),Pn(t1,t2)表示在時間區(qū)間[t1,t2)(t2>t1)內(nèi)有n(≥0)個顧客到達的概率。即：

在一定的假設(shè)條件下顧客的到達過程就是一個泊松過程。

當(dāng)Pn(t1,t2)符合下述三個條件時，顧客到達過程就是泊松過程(顧客到達形成普阿松流)。39（t2>t1，n≥0）若設(shè)N(t)表示在時間區(qū)間40①

無后效性：各區(qū)間的到達相互獨立,即Markov性。

也就是說過程在t+Δt所處的狀態(tài)與t以前所處的狀態(tài)無關(guān)。②平穩(wěn)性：即對于足夠小的Δt，有：普阿松流具有如下特性：

在[t,t+Δt]內(nèi)有一個顧客到達的概率與t無關(guān),而與Δt成正比。40①無后效性：各區(qū)間的到達相互獨立,即Markov性。41

③

普通性：對充分小的Δt,在時間區(qū)間（t,t+Δt）內(nèi)有2個或2個以上顧客到達的概率是一高階無窮小.由此知，在(t，t+Δt)區(qū)間內(nèi)沒有顧客到達的概率為：

令t1=0,t2=t,則P(t1,t2)=Pn(0,t)=Pn(t)λ>0是常數(shù)，它表示單位時間到達的顧客數(shù)，稱為概率強度。即P0+P1+P≥2=141③普通性：對充分小的Δt,在時間區(qū)間（t,42

在[0，t+Δt]內(nèi)到達n個顧客應(yīng)是上面三種互不相容的情況之一，所以有：

為了求Pn(t),即Pn(0,t)，需要研究它在（t，t+Δt）上的改變量,建立Pn(t)的微分方程。對于區(qū)間[0,t+Δt)可以分成[0，t)和[t，t+Δt),其到達總數(shù)是n，不外有下列三種情況：42在[0，t+Δt]內(nèi)到達n個顧客應(yīng)是上面三種互不相43令Δt→0取極限（并注意初始條件）得：………(3)當(dāng)n=0時，沒有B，C兩種情況，則：………(4)湊微分43令Δt→0取極限（并注意初始條件）得：………(3)當(dāng)n=44∴

C

=0（3）式兩端乘et并移項得：∴……(5)（沒有顧客到達的概率）兩邊積分得：代入初始條件(t=0)有：P0(0)=144∴C=0（3）式兩端乘et并移項得：∴……(545將n=1,2,3…代入（6）得：∴………(6)(注意利用(5)式)湊成Pn(t)et兩項乘積的微分兩邊積分45將n=1,2,3…代入（6）得：∴………(6)(注意利用46如此繼續(xù)遞推下去得：∴（2個顧客到達的概率）（n個顧客到達的概率）

即隨機變量N(t)=n服從泊松分布。它的數(shù)學(xué)期望和方差為：∴（1個顧客到達的概率）46如此繼續(xù)遞推下去得：∴（2個顧客到達的概率）（n個顧客到47級數(shù)令k=n-1，則：47級數(shù)令k=n-1，則：48即：同理方差為：顧客到達過程是一個泊松過程(泊松流)。48即：同理方差為：顧客到達過程是一個泊松過程(泊松流)。49其概率密度函數(shù)為：t>0

2.負指數(shù)分布當(dāng)輸入過程是泊松流時，我們研究兩顧客相繼到達的時間間隔的概率分布。設(shè)T為時間間隔，分布函數(shù)為FT（t），則：FT（t）=P{T≤t}

此概率等價于在[0，t）區(qū)間內(nèi)至少有1個顧客到達的概率。∴t>0

∵沒有顧客到達的概率為：(由（5）式而來)49其概率密度函數(shù)為：t>02.負指數(shù)分布∴t>050

λ表示單位時間內(nèi)顧客平均到達數(shù)。

1/λ表示顧客到達的平均間隔時間。可以證明，間隔時間T獨立且服從負指數(shù)分布與顧客到達形成泊松流是等價的。對顧客的服務(wù)時間：系統(tǒng)處于忙期時兩顧客相繼離開系統(tǒng)的時間間隔，一般地也服從負指數(shù)分布，設(shè)：即T服從負指數(shù)分布，它的期望及方差為：接受服務(wù)，然后離開服務(wù)時間的分布：50λ表示單位時間內(nèi)顧客平均到達數(shù)。對顧客的服務(wù)時間51其中：μ表示單位時間內(nèi)能被服務(wù)的顧客數(shù)，即平均服務(wù)率。

1/μ表示一個顧客的平均服務(wù)時間。

3.愛爾朗(Erlang)分布設(shè)v1,v2，…,vk是k個獨立的隨機變量，服從相同參數(shù)

k

的負指數(shù)分布，那么：，則令，則ρ稱為服務(wù)強度。51其中：μ表示單位時間內(nèi)能被服務(wù)的顧客數(shù)，即平均352

串列k個服務(wù)臺，每臺服務(wù)時間相互獨立，服從相同負指數(shù)分布（參數(shù)k），那么一顧客走完k個服務(wù)臺總共所需要服務(wù)時間服從上述k階Erlang分布。則稱T服從k階愛爾朗分布。其特征值為：,其概率密度是1/kμ表示一個顧客一個服務(wù)臺的平均服務(wù)時間。52串列k個服務(wù)臺，每臺服務(wù)時間相互獨立，服從相同負指53

例:有易碎物品500件,由甲地運往乙地,根據(jù)以往統(tǒng)計資料,在運輸過程中易碎物品按普阿松流發(fā)生破碎,其概率為0.002,現(xiàn)求:1.破碎3件物品的概率;2.破碎少于3件的概率和多于3件的概率;3.至少有一件破損的概率.

解:∵λ=0.002×500=11．破碎3件物品的概率為:P(k=3)=(3/3！)e-=(13/3！)e-1=0.0613

即物品破碎3件的概率為6.132.破碎物品少于3件的概率:53例:有易碎物品500件,由甲地運往乙地,根據(jù)以往統(tǒng)54∴破碎物品少于3件的概率為91.97破碎物品多于3件的概率為:3.至少有一件破碎的概率為

P{k1}=1-(1k/k!)e-=1-(10/0!)e-1=0.63254∴破碎物品少于3件的概率為91.973.至少有一件破55

對排隊模型，在給定輸入和服務(wù)條件下，主要研究系統(tǒng)的下述運行指標(biāo)：

(1)系統(tǒng)的平均隊長Ls(期望值)和平均隊列長Lq(期望值)；

(2)系統(tǒng)中顧客平均逗留時間Ws與隊列中平均等待時間Wq；本節(jié)只研究M/M/1模型，下面分三種情況討論：8-5M/M/1無限源系統(tǒng)55對排隊模型，在給定輸入和服務(wù)條件下，主要研究系統(tǒng)56一、標(biāo)準(zhǔn)的M/M/1模型

系統(tǒng)中有n個顧客[M/M/1]:[∞/∞/FCFS]模型1.穩(wěn)態(tài)概率Pn的計算

在任意時刻t，狀態(tài)為n的概率Pn(t)（瞬態(tài)概率），它決定了系統(tǒng)的運行特征。

已知顧客到達服從參數(shù)為λ的泊松過程，服務(wù)時間服從參數(shù)為μ的負指數(shù)分布。現(xiàn)仍然通過研究區(qū)間[t，t+Δt）的變化來求解。在時刻t+Δt，系統(tǒng)中有n個顧客不外乎有下列四種情況（[t，t+Δt）內(nèi)到達或離開2個以上沒列入）。？56一、標(biāo)準(zhǔn)的M/M/1模型系統(tǒng)中有n個顧客[M/M57

由于這四種情況是互不相容的，所以Pn(t+Δt)應(yīng)是這四項之和，則有：57由于這四種情況是互不相容的，所以Pn(t+58令Δt→0，得關(guān)于Pn(t)的微分差分方程：……(1)

當(dāng)n=0時，只有表中的（A）、（B）兩種情況，因為在較小的Δt內(nèi)不可能發(fā)生（D）（到達后即離去），若發(fā)生可將Δt取小即可。58令Δt→0，得關(guān)于Pn(t)的微分差分方程：……(1)59∴∴………(2)

這種系統(tǒng)狀態(tài)(n)隨時間變化的過程就是生滅過程（BirthandDeathProcess）。方程(1)、(2)解是瞬態(tài)解,無法應(yīng)用。

它對時間的導(dǎo)數(shù)為0，所以由(1)、(2)兩式得：穩(wěn)態(tài)時，Pn(t)與時間無關(guān),可以寫成Pn,………(3)………(4)59∴∴………(2)這種系統(tǒng)狀態(tài)(n)隨時60由此可得該排隊系統(tǒng)的狀態(tài)轉(zhuǎn)移圖：由（4）得：其中ρ——服務(wù)強度

將其代入（3）式并令n=1,2,…(也可從狀態(tài)轉(zhuǎn)移圖中看出狀態(tài)平衡方程)得：………(3)………(4)n-1nn+1201……狀態(tài)轉(zhuǎn)移圖60由此可得該排隊系統(tǒng)的狀態(tài)轉(zhuǎn)移圖：由（4）得：其中ρ——服61n=1∴n=2∴61n=1∴n=2∴62以此類推…，當(dāng)n=n時，………(5)∵及概率性質(zhì)知：(數(shù)列的極限為)∴………(6)∴否則排隊無限遠系統(tǒng)穩(wěn)態(tài)概率系統(tǒng)的運行指標(biāo)62以此類推…，當(dāng)n=n時，………(5)∵及概率性質(zhì)知：(數(shù)632.系統(tǒng)的運行指標(biāo)計算

(1)系統(tǒng)中的隊長Ls（平均隊長）(0<ρ<1)即:………(7)期望632.系統(tǒng)的運行指標(biāo)計算(0<ρ<1)即:………(7)期64(2)隊列中等待的平均顧客數(shù)Lq………(8)(3)顧客在系統(tǒng)中的平均逗留時間Ws

顧客在系統(tǒng)中的逗留時間是隨機變量，可以證明，它服從參數(shù)為μ-λ的負指數(shù)分布，分布函數(shù)64(2)隊列中等待的平均顧客數(shù)Lq………(8)(3)65和密度函數(shù)為：（w≥0）∴(4)顧客在隊列中的平均逗留時間Wq

顧客在隊列中的平均逗留時間應(yīng)為Ws減去平均服務(wù)時間。考慮LS與WS的關(guān)系65和密度函數(shù)為：（w≥0）∴(4)顧客在隊列中的平均66四個指標(biāo)的關(guān)系為(Little公式)：

3.系統(tǒng)的忙期與閑期系統(tǒng)處于空閑狀態(tài)的概率：系統(tǒng)處于繁忙狀態(tài)的概率：服務(wù)強度66四個指標(biāo)的關(guān)系為(Little公式)：3.系統(tǒng)的忙67在繁忙狀態(tài)下，隊列中的平均顧客數(shù)Lb：顧客平均等待時間:忙期的平均長度:(由來)一個忙期平均服務(wù)顧客數(shù)為：Lb×P(N≥0)=Lq67在繁忙狀態(tài)下，隊列中的平均顧客數(shù)Lb：顧客平均等待時間:688-6系統(tǒng)容量有限制的模型

[M/M/1]：[N/∞/FCFS]

當(dāng)系統(tǒng)容量最大為N時，排隊多于N個的顧客將被拒絕。當(dāng)N=1時，即為瞬時制，N→∞時，即為容量無限制的情況。688-6系統(tǒng)容量有限制的模型

[M/M/1]69

現(xiàn)在研究系統(tǒng)中有n個顧客的概率Pn(t)。………(2)對于(1)式，當(dāng)n=1,2,…N-1時，仍能成立。……(1)(n=1,2,…N-1)但當(dāng)n=N時，有下面兩種情況：對于P0(t)，前面的（2）式仍然成立。69現(xiàn)在研究系統(tǒng)中有n個顧客的概率Pn(t)。………(70………(8)0N-112N-2λλλλμμμμN70………(8)0N-112N-2λλλλμμμμN71在穩(wěn)態(tài)情況下有：………(9)解（9）式得：………∵

而等比數(shù)列71在穩(wěn)態(tài)情況下有：………(9)解（9）式得：………∵而等72(ρ≠1,n≤N)……(10)∴

注：當(dāng)ρ=1時，試討論其概率Pn。(1)平均隊長Ls：(ρ≠1)試證ρ=1時,Ls=N/2其運行指標(biāo)：72(ρ≠1,n≤N)……(10)∴注：當(dāng)ρ=1時，試討論73(2)有效到達率λe

系統(tǒng)容量有限，當(dāng)滿員時，顧客將被拒絕，實際的顧客到達率與λ不一樣，還可驗證：∴

此種情況的公式與前類似,只有Ls不同,λe與λ不同。求λe必須先求得P0或PN才行。有效到達率為λe。

可以證明：Ls73(2)有效到達率λe還可驗證：∴74例2．某單人理發(fā)館共有六把椅子接待顧客排隊，無座時將離去，顧客平均到達率為3人/h，理發(fā)時間平均為15分鐘，求：(1)求某一顧客到達就能理發(fā)的概率;(2)求需要等待的顧客數(shù)的期望值;(3)求有效到達率;(4)求一顧客在系統(tǒng)中的逗留時間和排隊時間平均值;(5)在可能到來的顧客中，有百分之幾不等待就離開？解：N=6+1=7，λ=3，μ=474例2．某單人理發(fā)館共有六把椅子接待顧客排隊，無座時將離去75(1)求某一顧客到達就能理發(fā)的概率:(2)求需要等待的顧客數(shù)的期望值:(3)求有效到達率:(4)求一顧客在系統(tǒng)中的逗留時間和排隊時間平均值:75(1)求某一顧客到達就能理發(fā)的概率:(2)求需要等待76P0=0.27780P1=0.20836P2=0.15627P3=0.11720=0.9629=96.29%P4=0.08790故拒絕的概率為3.71%P5=0.06593P6=0.04944(5)在可能到來的顧客中，有百分之幾不等待就離開？76P0=0.27780(5)在可能到來的顧客中，有百分之778-7顧客源有限的模型

[M/M/1/∞/m]

以機器修理模型為例，設(shè)有m臺機器(總體)，故障待修表示機器到達，修理工是服務(wù)員。機器修好后有可能再壞，形成循環(huán)。雖然系統(tǒng)沒有容量限制，但系統(tǒng)中的顧客也不會超過m，故又可寫成：[M/M/1/m/m]778-7顧客源有限的模型

[M/M/1/∞78

對于有限源應(yīng)按每個顧客單獨考慮，求出其有效到達率λe。∴

這樣λe是隨系統(tǒng)內(nèi)顧客數(shù)而變化的。其狀態(tài)轉(zhuǎn)移圖為：設(shè)系統(tǒng)內(nèi)顧客數(shù)為Ls，則系統(tǒng)外的顧客為m-Ls。設(shè)每個顧客的平均到達率是相同的λ。

(這里λ的含義是單臺機器在單位時間里發(fā)生故障的概率或平均次數(shù))78對于有限源應(yīng)按每個顧客單獨考慮，求出其有效到達率λ79由狀態(tài)轉(zhuǎn)移圖可得狀態(tài)轉(zhuǎn)移方程：1≤n≤m-10狀態(tài)n狀態(tài)m狀態(tài)

用遞推方法解此差分方程，并注意條件，可以得到如下公式：10=?=miiP(1≤n≤m)79由狀態(tài)轉(zhuǎn)移圖可得狀態(tài)轉(zhuǎn)移方程：1≤n≤m-10狀態(tài)80各項運行指標(biāo)為：例3某車間有5臺機器，每臺機器的連續(xù)運轉(zhuǎn)時間服從負指數(shù)分布。平均連續(xù)運轉(zhuǎn)時間15分鐘，有一個修理工，修理時間服從負指數(shù)分布，平均每次12分鐘。求：(1)修理工空閑時間80各項運行指標(biāo)為：例3某車間有5臺機器，每臺機器的連續(xù)81解:(1)∵m=5,λ=1/15,μ=1/12,ρ=4/5=0.8(2)五臺機器都出現(xiàn)故障的概率81解:(1)∵m=5,λ=1/15,μ=1/12,ρ82臺臺(3)出故障的平均臺數(shù)(4)等待修理的平均臺數(shù)(5)平均停工時間分鐘82臺臺(3)出故障的平均臺數(shù)(4)等待修理的平均臺數(shù)(83分鐘

機器等待過長，忙期長，應(yīng)增加維修工人或提高效率。(6)平均等待修理時間(7)評價這些結(jié)果83分鐘機器等待過長，忙期長，應(yīng)增加維修工人或841.標(biāo)準(zhǔn)的M/M/C模型8-8多服務(wù)臺負指數(shù)分布排隊系統(tǒng)分析當(dāng)n<c時，Pn=[λ/(nμ)]Pn-1當(dāng)nc時，Pn=[λ/(cμ)]Pn-1標(biāo)準(zhǔn)的M/M/C模型個特征規(guī)定同M/M/1。另外規(guī)定各服務(wù)臺工作相互獨立且平均服務(wù)率相同μ1=μ2=μ3=……=μc=μ整個服務(wù)機構(gòu)的平均服務(wù)率為cμ(nc);nμ(n<c)令ρ=λ/（cμ）系統(tǒng)負荷強度系數(shù)841.標(biāo)準(zhǔn)的M/M/C模型8-8多服務(wù)臺負指數(shù)分布排隊858-8多服務(wù)臺負指數(shù)分布排隊系統(tǒng)分析0n12n-1λλλλμcμ2μcμn+1nn-1λλnμ(n+1)μn+1λλλλ

狀態(tài)轉(zhuǎn)移圖中：1轉(zhuǎn)移到0，即系統(tǒng)中有一名顧客被服務(wù)完離去的轉(zhuǎn)移率為μp1，狀態(tài)2轉(zhuǎn)移到1

，這就是在2個服務(wù)臺上被服務(wù)的顧客有1個被服務(wù)完離去。因為不限哪一個，那么這時的狀態(tài)轉(zhuǎn)移率為2μp2。n>cn

c同理考慮n轉(zhuǎn)移n-1的情況。nc時，轉(zhuǎn)移率為nμpnn>c時，有c個服務(wù)臺，最多有c個顧客被服務(wù),n-c個等待，則這時狀態(tài)轉(zhuǎn)移率為cμpn858-8多服務(wù)臺負指數(shù)分布排隊系統(tǒng)分析0n12n-1λλ86用遞推法解上差分方程，可求得狀態(tài)概率：86用遞推法解上差分方程，87M/M/C無限源系統(tǒng)系統(tǒng)運行指標(biāo)求得如下：87M/M/C無限源系統(tǒng)系統(tǒng)運行指標(biāo)求得如下：88例:某火車站售票處有三個窗口，同時售各車次的車票。顧客到達服從泊松布，平均每分鐘到達λ=0.9（人），服務(wù)時間服從負指數(shù)分布，平均服務(wù)率μ=24（人/h），分兩種情況：1.顧客排成一隊，依次購票；2.顧客在每個窗口排一隊，不準(zhǔn)串隊。求:（1）售票處空閑的概率。

（2）隊長和隊列長。例題解析（3）平均等待時間和逗留時間。88例:某火車站售票處有三個窗口，同時例題解89例題解析

解：1.M/M/3/∞/∞μ=0.4（人/分鐘）記ρ=λ/（3μ）=0.75本題屬于？n<cn>c則（1）售票處空閑的概率為：89例題解析解：1.M/M/3/∞/∞μ90例題解析

解：1.M/M/3/∞/∞（2）隊長和隊列長：90例題解析解：1.M/M/3/∞/∞（91例題解析售票處的空閑的概率為0.0748有1個窗口空閑0.18934有2個窗口空閑0.1683平均等待時間Wq=1.89分鐘，平均逗留時間Ws=4.39分鐘隊長Ls=3.95(人)Lq=1.70(人)91例題解析售票處的空閑的概率為0.074892

2.相當(dāng)于3個M/M/1/三個系統(tǒng)并聯(lián)：λ=0.3μ=0.4ρ=λ/μ=0.75P0=1-ρ=0.25

（每個子系統(tǒng)）三個服務(wù)臺都有空的時候，P03=0.0156Ls=ρ/(1-ρ)=3(子系統(tǒng)）整個系統(tǒng)為9Lq=Ls-λ/μ=2.25（每個子系統(tǒng)）Ws=Ls/λ=10Wq=Ws-1/μ=7.5例題解析922.相當(dāng)于3個M/M/1/三個系統(tǒng)并聯(lián)：例93故售票處空閑的概率為0.0156例題解析平均等待時間Wq=7.5分鐘平均逗留時間Ws=10分鐘隊長

Ls=3三個隊共3+3+3=9隊列長Lq=2.25共6.75（人）有1個窗口空閑0.25有2個窗口空閑0.0625相比之下，排一隊共享三個服務(wù)臺效率好93故售票處空閑的概率為0.0156例題解THANKYOU此課件下載可自行編輯修改，僅供參考！

感謝您的支持，我們努力做得更好！謝謝THANKYOU此課件下載可自行編輯修改，僅供參考！

95排隊論1排隊論96第8章排隊論(QueuingTheory)

排隊論（queuing),也稱隨機服務(wù)系統(tǒng)理論，是運籌學(xué)的一個主要分支。

1909年，丹麥哥本哈根電子公司電話工程師A.K.Erlang的開創(chuàng)性論文“概率論和電話通訊理論”標(biāo)志此理論的誕生。排隊論的發(fā)展最早是與電話，通信中的問題相聯(lián)系的，并到現(xiàn)在是排隊論的傳統(tǒng)的應(yīng)用領(lǐng)域。近年來在計算機通訊網(wǎng)絡(luò)系統(tǒng)、交通運輸、醫(yī)療衛(wèi)生系統(tǒng)、庫存管理、作戰(zhàn)指揮等各領(lǐng)域中均得到應(yīng)用。2第8章排隊論(QueuingTheory)978排隊論8-1前言8-2基本概念8-3輸入過程和服務(wù)時間分布8-4泊松輸入—指數(shù)服務(wù)排隊模型8-5M/M/1無限源系統(tǒng)8-6系統(tǒng)容量有限的排隊系統(tǒng)8-7顧客源有限的排隊系統(tǒng)38排隊論8-1前言98

排隊是我們在日常生活和生產(chǎn)中經(jīng)常遇到的現(xiàn)象。例如，上、下班搭乘公共汽車；顧客到商店購買物品；病員到醫(yī)院看病；旅客到售票處購買車票；學(xué)生去食堂就餐等就常常出現(xiàn)排隊和等待現(xiàn)象。前言4排隊是我們在日常生活和生產(chǎn)中經(jīng)常遇99

除了上述有形的排隊之外，還有大量的所謂“無形”排隊現(xiàn)象。如幾個顧客打電話到出租汽車站要求派車，如果出租汽車站無足夠車輛、則部分顧客只得在各自的要車處等待，他們分散在不同地方，卻形成了一個無形隊列在等待派車。

前言5除了上述有形的排隊之外，還有大量的所謂100

排隊的不一定是人，也可以是物：例如，通訊衛(wèi)星與地面若干待傳遞的信息；生產(chǎn)線上原料、半成品等待加工；因故障停止運轉(zhuǎn)的機器等待修理；碼頭的船只等待裝卸貨物；要降落的飛機因跑道不空而在空中盤旋等等。前言6排隊的不一定是人，也可以是物：前言101

上述各種問題雖互不相同，但卻都有要求得到某種服務(wù)的人或物和提供服務(wù)的人或機構(gòu)。排隊論里把要求服務(wù)的對象統(tǒng)稱為“顧客”,提供服務(wù)的人或機構(gòu)稱為“服務(wù)臺”或“服務(wù)員”。前言7上述各種問題雖互不相同，但卻都有要求得到某種102

不同的顧客與服務(wù)組成了各式各樣的服務(wù)系統(tǒng)。顧客為了得到某種服務(wù)而到達系統(tǒng)、若不能立即獲得服務(wù)而又允許排隊等待，則加入等待隊伍，待獲得服務(wù)后離開系統(tǒng)，見圖8-1至圖8-5。圖8-1單服務(wù)臺排隊系統(tǒng)前言8不同的顧客與服務(wù)組成了各式各樣的服務(wù)系統(tǒng)。顧客103圖8-2單隊列——S個服務(wù)臺并聯(lián)的排隊系統(tǒng)圖8-3S個隊列——S個服務(wù)臺的并聯(lián)排隊系統(tǒng)前言9圖8-2單隊列——S個服務(wù)臺并聯(lián)的排隊系統(tǒng)圖8-3104圖8-4單隊——多個服務(wù)臺的串聯(lián)排隊系統(tǒng)

圖8-5多隊——多服務(wù)臺混聯(lián)網(wǎng)絡(luò)系統(tǒng)前言10圖8-4單隊——多個服務(wù)臺的串聯(lián)排隊系統(tǒng)

圖8-5105圖8-6隨機服務(wù)系統(tǒng)前言一般的排隊系統(tǒng)，都可由下面圖加以描述。通常稱由圖8-6表示的系統(tǒng)為一隨機聚散服務(wù)系統(tǒng)。任一排隊系統(tǒng)都是一個隨機聚散服務(wù)系統(tǒng)。“聚”表示顧客的到達，“散”表示顧客的離去。11圖8-6隨機服務(wù)系統(tǒng)前言一般的排隊系統(tǒng)，都可由下106

面對擁擠現(xiàn)象，人們總是希望盡量設(shè)法減少排隊，通常的做法是增加服務(wù)設(shè)施。但是增加的數(shù)量越多，人力、物力的支出就越大，甚至?xí)霈F(xiàn)空閑浪費。如果服務(wù)設(shè)施太少，顧客排隊等待的時間就會很長，這樣對顧客會帶來不良影響。前言12面對擁擠現(xiàn)象，人們總是希望盡量設(shè)法減少排隊，107

顧客排隊時間的長短與服務(wù)設(shè)施規(guī)模的大小，就構(gòu)成了設(shè)計隨機服務(wù)系統(tǒng)中的一對矛盾。如何做到既保證一定的服務(wù)質(zhì)量指標(biāo)，又使服務(wù)設(shè)施費用經(jīng)濟合理，恰當(dāng)?shù)亟鉀Q顧客排隊時間與服務(wù)設(shè)施費用大小這對矛盾。這就是隨機服務(wù)系統(tǒng)理論——排隊論所要研究解決的問題。前言13顧客排隊時間的長短與服務(wù)設(shè)施規(guī)模的大小，就構(gòu)108一、排隊系統(tǒng)的組成與特征排隊系統(tǒng)一般有三個基本組成部分：1.輸入過程；2.排隊規(guī)則；3.服務(wù)機構(gòu)。§8-2排隊系統(tǒng)的基本概念14一、排隊系統(tǒng)的組成與特征§8-2排隊系統(tǒng)的基本概念109

輸入即為顧客的到達，可有下列情況：

1）顧客源可能是有限的，也可能是無限的。

2）顧客是成批到達或是單個到達。

3）顧客到達間隔時間可能是隨機的或確定的。

4）顧客到達可能是相互獨立或關(guān)聯(lián)的。所謂獨立就是以前顧客的到達對以后顧客的到達無影響。

5）輸入過程可以是平穩(wěn)的（stationary）或說是對時間齊次的（Homogeneousintime），也可以是非平穩(wěn)的。輸入過程平穩(wěn)的指顧客相繼到達的間隔時間分布和參數(shù)（均值、方差）與時間無關(guān)；非平穩(wěn)的則是與時間相關(guān)，非平穩(wěn)的處理比較困難。

1.輸入過程15輸入即為顧客的到達，可有下列情況：1.輸入過程110這是指服務(wù)臺從隊列中選取顧客進行服務(wù)的順序。可以分為損失制、等待制、混合制3大類。

(1)損失制。這是指如果顧客到達排隊系統(tǒng)時，所有服務(wù)臺都已被先來的顧客占用，那么他們就自動離開系統(tǒng)永不再來。典型例子是，如電話拔號后出現(xiàn)忙音，顧客不愿等待而自動掛斷電話，如要再打，就需重新拔號，這種服務(wù)規(guī)則即為損失制。2.排隊規(guī)則16這是指服務(wù)臺從隊列中選取顧客進行服務(wù)的順序。2.排隊規(guī)111

(2)等待制。指當(dāng)顧客來到系統(tǒng)時，所有服務(wù)臺都不空，顧客加入排隊行列等待服務(wù)。例如，排隊等待售票，故障設(shè)備等待維修等。等待制中，服務(wù)臺在選擇顧客進行服務(wù)時，常有如下四種規(guī)則：

①先到先服務(wù)（FCFS）。按顧客到達的先后順序?qū)︻櫩瓦M行服務(wù)，這是最普遍的情形。②后到先服務(wù)（LCFS）。倉庫中迭放的鋼材，后迭放上去的都先被領(lǐng)走，就屬于這種情況。2.排隊規(guī)則17(2)等待制。指當(dāng)顧客來到系統(tǒng)時，所有服務(wù)臺112③隨機服務(wù)（RAND）。即當(dāng)服務(wù)臺空閑時，不按照排隊序列而隨意指定某個顧客去接受服務(wù)，如電話交換臺接通呼叫電話就是一例。

④優(yōu)先權(quán)服務(wù)（PR）。如老人、兒童先進車站；危重病員先就診；遇到重要數(shù)據(jù)需要處理計算機立即中斷其他數(shù)據(jù)的處理等，均屬于此種服務(wù)規(guī)則。2.排隊規(guī)則18③隨機服務(wù)（RAND）。即當(dāng)服務(wù)113

(3)混合制．這是等待制與損失制相結(jié)合的一種服務(wù)規(guī)則，一般是指允許排隊，但又不允許隊列無限長下去。具體說來，大致有三種：

①隊長有限。當(dāng)排隊等待服務(wù)顧客人數(shù)超過規(guī)定數(shù)量時，后來顧客就自動離去，另求服務(wù)。如水庫的庫容、旅館的床位等都是有限的。2.排隊規(guī)則19(3)混合制．這是等待制與損失制相結(jié)合的一種114

②等待時間有限。即顧客在系統(tǒng)中的等待時間不超過某一給定的長度T，當(dāng)?shù)却龝r間超過T時，顧客自動離去，不再回來。如易損壞的電子元器件的庫存問題，超過一定存儲時間被自動認為失效。又如顧客到飯館就餐，等了一定時間后不愿再等而自動離去另找飯店用餐。2.排隊規(guī)則20②等待時間有限。即顧客在系統(tǒng)中的等待時間不115

③逗留時間(等待時間與服務(wù)時間之和)有限。例如用高射炮射擊敵機，當(dāng)敵機飛越高射炮射擊有效區(qū)域的時間為t時，若在這個時間內(nèi)未被擊落，也就不可能再被擊落了。不難注意到，損失制和等待制可看成是混合制的特殊情形，如記c為系統(tǒng)中服務(wù)臺的個數(shù)，則當(dāng)K=c

時，混合制即成為損失制；當(dāng)K=∞時，混合制即成為等待制。2.排隊規(guī)則21③逗留時間(等待時間與服務(wù)時間之和)有限。1163.服務(wù)機構(gòu)1）服務(wù)機構(gòu)可以是單服務(wù)員和多服務(wù)員服務(wù)，這種服務(wù)形式與隊列規(guī)則聯(lián)合后形成了多種不同隊列，不同形式的排隊服務(wù)機構(gòu)。如前圖8-1到8-5：2)服務(wù)方式分為單個顧客服務(wù)和成批顧客服務(wù)。3)服務(wù)時間分為確定型和隨機型。4)服務(wù)時間的分布在這里我們假定是平穩(wěn)的。223.服務(wù)機構(gòu)1）服務(wù)機構(gòu)可以是單服務(wù)員和多服務(wù)員117上述特征中最主要的、影響最大的是：顧客相繼到達的間隔時間分布服務(wù)時間的分布服務(wù)臺數(shù)D.G.Kendall，1953提出了分類法，稱為Kendall記號(適用于并列服務(wù)臺)即：[X/Y/Z]:[d/e/f]二、排隊系統(tǒng)的描述符號與模型分類23上述特征中最主要的、影響最大的是：二、排隊系統(tǒng)的描述符號118式中：X——顧客相繼到達間隔時間分布。M—負指數(shù)分布Markov，D—確定型分布Deterministic，Ek—K階愛爾朗分布Erlang，GI—一般相互獨立隨機分布(GeneralIndependent)，G—一般隨機分布。Y——填寫服務(wù)時間分布（與上同）Z——填寫并列的服務(wù)臺數(shù)d——排隊系統(tǒng)的最大容量e——顧客源數(shù)量f——排隊規(guī)則如[M/M/1]:[∞/∞/FCFS]即為顧客到達為泊松過程，服務(wù)時間為負指數(shù)分布，單臺，無限容量，無限源，先到先服務(wù)的排隊系統(tǒng)模型。24式中：X——顧客相繼到達間隔時間分布。119三、排隊論研究的基本問題

1.排隊系統(tǒng)的統(tǒng)計推斷:即通過對排隊系統(tǒng)主要參數(shù)的統(tǒng)計推斷和對排隊系統(tǒng)的結(jié)構(gòu)分析，判斷一個給定的排隊系統(tǒng)符合于哪種模型，以便根據(jù)排隊理論進行研究。

2.系統(tǒng)性態(tài)問題:即研究各種排隊系統(tǒng)的概率規(guī)律性，主要研究隊長分布、等待時間分布和忙期分布等統(tǒng)計指標(biāo),包括了瞬態(tài)和穩(wěn)態(tài)兩種情形。

3.最優(yōu)化問題：即包括最優(yōu)設(shè)計(靜態(tài)優(yōu)化)，最優(yōu)設(shè)計是指在一定質(zhì)量指標(biāo)下要求機構(gòu)最經(jīng)濟，如輸入結(jié)構(gòu)與服務(wù)系統(tǒng)的最優(yōu)設(shè)計，排隊規(guī)則的最優(yōu)設(shè)計等。最優(yōu)運營（動態(tài)優(yōu)化），最優(yōu)運營是指對給定的系統(tǒng)，如何經(jīng)營可使目標(biāo)函數(shù)達到最優(yōu)值。25三、排隊論研究的基本問題120排隊問題求解(主要指性態(tài)問題)

求解一般排隊系統(tǒng)問題的目的主要是通過研究排隊系統(tǒng)運行的效率指標(biāo)，估計服務(wù)質(zhì)量，確定系統(tǒng)的合理結(jié)構(gòu)和系統(tǒng)參數(shù)的合理值，以便實現(xiàn)對現(xiàn)有系統(tǒng)合理改進和對新建系統(tǒng)的最優(yōu)設(shè)計等。排隊問題的一般步驟：

1.確定或擬合排隊系統(tǒng)顧客到達的時間間隔分布和服務(wù)時間分布(可實測)。

2.研究分析排隊系統(tǒng)理論分布的概率特征。

3.研究系統(tǒng)狀態(tài)的概率。系統(tǒng)狀態(tài)是指系統(tǒng)中顧客數(shù)。狀態(tài)概率用Pn(t)表示,即在t時刻系統(tǒng)中有n個顧客的概率，也稱瞬態(tài)概率。26排隊問題求解(主要指性態(tài)問題)求解一般排隊系統(tǒng)問題121

求解狀態(tài)概率Pn(t)方法是建立含Pn(t)的微分差分方程，通過求解微分差分方程得到系統(tǒng)瞬態(tài)解，由于瞬態(tài)解一般求出確定值比較困難，即便求得一般也很難使用。因此常常使用它的極限(如果存在的話)：穩(wěn)態(tài)的物理意義圖，系統(tǒng)的穩(wěn)態(tài)一般很快都能達到，但實際中達不到穩(wěn)態(tài)的現(xiàn)象也存在。要注意的是求穩(wěn)態(tài)概率Pn并不一定求t→∞的極限,只需求Pn’(t)=0。過渡狀態(tài)穩(wěn)定狀態(tài)pnt圖3排隊系統(tǒng)狀態(tài)變化示意圖

稱為穩(wěn)態(tài)(steadystate)解，或稱統(tǒng)計平衡狀態(tài)(StatisticalEquilibriumState)的解。27求解狀態(tài)概率Pn(t)方法是建立含Pn(t)的微122

4.根據(jù)排隊系統(tǒng)對應(yīng)的理論模型求用以判斷系統(tǒng)運行優(yōu)劣的基本數(shù)量指標(biāo)的概率分布或特征數(shù)。數(shù)量指標(biāo)主要包括:(1)平均隊長（Ls）:系統(tǒng)中的顧客數(shù)。

平均隊列長（Lg）:系統(tǒng)中排隊等待服務(wù)的顧客數(shù)。系統(tǒng)中顧客數(shù)Ls=系統(tǒng)中排隊等待服務(wù)的顧客數(shù)Lg+正被服務(wù)的顧客數(shù)c(2)平均逗留時間(Ws):指一個顧客在系統(tǒng)中的停留時間。

平均等待時間(Wg):一個顧客在系統(tǒng)中排隊等待的時間。(3)忙期：指從顧客到達空閑服務(wù)機構(gòu)起到服務(wù)機構(gòu)再次為空閑這段時間長度。（忙期和一個忙期中平均完成服務(wù)顧客數(shù)都是衡量服務(wù)機構(gòu)效率的指標(biāo)，忙期關(guān)系到工作強度）

5.排隊系統(tǒng)指標(biāo)優(yōu)化含優(yōu)化設(shè)計與優(yōu)化運營（見25頁）。問題1

系統(tǒng)中顧客數(shù)=平均隊長（Ls）+1？284.根據(jù)排隊系統(tǒng)對應(yīng)的理論模型求用以判斷系統(tǒng)運行123四、排隊論主要知識點排隊系統(tǒng)的組成與特征排隊系統(tǒng)的模型分類顧客到達間隔時間和服務(wù)時間的經(jīng)驗分布與理論分布穩(wěn)態(tài)概率Pn的計算標(biāo)準(zhǔn)的M/M/1模型([M/M/1]:[∞/∞/FCFS])系統(tǒng)容量有限制的模型[M/M/1]:[N/∞/FCFS]顧客源有限模型[M/M/1][∞/M/FCFS]標(biāo)準(zhǔn)的[M/M/C]模型[M/M/C]:[∞/∞/FCFS]29四、排隊論主要知識點排隊系統(tǒng)的組成與特征124M/M/C型系統(tǒng)和C個M/M/1型系統(tǒng)系統(tǒng)容量有限制的多服務(wù)臺模型(M/M/C/N/∞)顧客源為有限的多服務(wù)臺模型(M/M/C/∞/M)一般服務(wù)時間的（M/G/1）模型Pollaczek-Khintchine(P-K)公式定長服務(wù)時間M/D/1模型愛爾朗服務(wù)時間M/Ek/1模型排隊系統(tǒng)優(yōu)化M/M/1模型中的最優(yōu)服務(wù)率u標(biāo)準(zhǔn)的M/M/1Model系統(tǒng)容量為N的情形M/M/C模型中最優(yōu)服務(wù)臺數(shù)C30M/M/C型系統(tǒng)和C個M/M/1型系統(tǒng)1258-3到達間隔時間分布和服務(wù)時間的分布一個排隊系統(tǒng)的最主要特征參數(shù)是顧客的到達間隔時間分布與服務(wù)時間分布。要研究到達間隔時間分布與服務(wù)時間分布需要首先根據(jù)現(xiàn)存系統(tǒng)原始資料統(tǒng)計出它們的經(jīng)驗分布，然后與理論分布擬合，若能照應(yīng)，我們就可以得出上述的分布情況。318-3到達間隔時間分布和服務(wù)時間的分布一個排隊系統(tǒng)的最126一、經(jīng)驗分布

經(jīng)驗分布是對排隊系統(tǒng)的某些時間參數(shù)根據(jù)經(jīng)驗數(shù)據(jù)進行統(tǒng)計分析，并依據(jù)統(tǒng)計分析結(jié)果假設(shè)其統(tǒng)計樣本的總體分布，選擇合適的檢驗方法進行檢驗，當(dāng)通過檢驗時，我們認為時間參數(shù)的經(jīng)驗數(shù)據(jù)服從該假設(shè)分布。分布的擬合檢驗一般采用χ2檢驗。由數(shù)理統(tǒng)計的知識我們知：若樣本量n充分大(n≥50)，則當(dāng)假設(shè)H0為真時，統(tǒng)計量總是近似地服從自由度為k-r-1的χ2分布，其中k為分組數(shù)，r為檢驗分布中被估計的參數(shù)個數(shù)。32一、經(jīng)驗分布經(jīng)驗分布是對排隊系統(tǒng)的某些時127式中：fi——實際頻數(shù)

ni——理論頻數(shù)上面方法的應(yīng)用必須注意n要足夠大，npi不能太小。一般地n要大于50，而分組的npi應(yīng)不小于5。例題：某公共汽車站，統(tǒng)計來站的乘客流，規(guī)定每隔1分鐘統(tǒng)計一次乘客到達情況，共統(tǒng)計100次，其結(jié)果如表所示，問顧客是否服從普阿松流。當(dāng)時，在顯著水平α下接受假設(shè)H033式中：fi——實際頻數(shù)當(dāng)時，在顯著水平α下接受假設(shè)H0128解：先估計分布的參數(shù)λ，由極大似然估計法得：,并根據(jù)公式可計算出理論頻率、理論頻數(shù)及項

見下頁表所示查表知:故可接受泊松分布假設(shè)。34解：先估計分布的參數(shù)λ，由極大似然估計法得：,并根據(jù)公式129∑=6.2815K-r-1=8-1-135∑=6.2815K-r-1=8-1-1130隨機變量數(shù)隨著實驗的結(jié)果的不同而變化離散型：的所有可能只有限或至多可列個連續(xù)型：（）取值于某個區(qū)間（a，b）分布函數(shù)(連續(xù)):的概率分布(離散):i=1,2,3……二、概率論知識復(fù)習(xí)36隨機變量數(shù)隨著實驗的結(jié)果的不同而變化131數(shù)學(xué)期望:(離散)E(ξ)=

(連續(xù))E(ξ)=

方差:=條件概率:密度函數(shù):(連續(xù)),,37數(shù)學(xué)期望:(離散)E(ξ)=(連續(xù)132三、理論分布

式中λ為常數(shù)(λ>0)，稱X服從參數(shù)為λ的泊松分布，若在上式中引入時間參數(shù)t，即令λt代替λ，則有：

1.泊松分布在概率論中，我們曾學(xué)過泊松分布，設(shè)隨機變量為X，則有：n=0,1,2,…（1）

與時間有關(guān)的隨機變量的概率，是一個隨機過程，即泊松過程。t>0，n=0,1,2,…（2）38三、理論分布式中λ為常數(shù)(λ>0)，133（t2>t1，n≥0）

若設(shè)N(t)表示在時間區(qū)間[0,t)內(nèi)到達的顧客數(shù)(t>0),Pn(t1,t2)表示在時間區(qū)間[t1,t2)(t2>t1)內(nèi)有n(≥0)個顧客到達的概率。即：

在一定的假設(shè)條件下顧客的到達過程就是一個泊松過程。

當(dāng)Pn(t1,t2)符合下述三個條件時，顧客到達過程就是泊松過程(顧客到達形成普阿松流)。39（t2>t1，n≥0）若設(shè)N(t)表示在時間區(qū)間134①

無后效性：各區(qū)間的到達相互獨立,即Markov性。

也就是說過程在t+Δt所處的狀態(tài)與t以前所處的狀態(tài)無關(guān)。②平穩(wěn)性：即對于足夠小的Δt，有：普阿松流具有如下特性：

在[t,t+Δt]內(nèi)有一個顧客到達的概率與t無關(guān),而與Δt成正比。40①無后效性：各區(qū)間的到達相互獨立,即Markov性。135

③

普通性：對充分小的Δt,在時間區(qū)間（t,t+Δt）內(nèi)有2個或2個以上顧客到達的概率是一高階無窮小.由此知，在(t，t+Δt)區(qū)間內(nèi)沒有顧客到達的概率為：

令t1=0,t2=t,則P(t1,t2)=Pn(0,t)=Pn(t)λ>0是常數(shù)，它表示單位時間到達的顧客數(shù)，稱為概率強度。即P0+P1+P≥2=141③普通性：對充分小的Δt,在時間區(qū)間（t,136

在[0，t+Δt]內(nèi)到達n個顧客應(yīng)是上面三種互不相容的情況之一，所以有：

為了求Pn(t),即Pn(0,t)，需要研究它在（t，t+Δt）上的改變量,建立Pn(t)的微分方程。對于區(qū)間[0,t+Δt)可以分成[0，t)和[t，t+Δt),其到達總數(shù)是n，不外有下列三種情況：42在[0，t+Δt]內(nèi)到達n個顧客應(yīng)是上面三種互不相137令Δt→0取極限（并注意初始條件）得：………(3)當(dāng)n=0時，沒有B，C兩種情況，則：………(4)湊微分43令Δt→0取極限（并注意初始條件）得：………(3)當(dāng)n=138∴

C

=0（3）式兩端乘et并移項得：∴……(5)（沒有顧客到達的概率）兩邊積分得：代入初始條件(t=0)有：P0(0)=144∴C=0（3）式兩端乘et并移項得：∴……(5139將n=1,2,3…代入（6）得：∴………(6)(注意利用(5)式)湊成Pn(t)et兩項乘積的微分兩邊積分45將n=1,2,3…代入（6）得：∴………(6)(注意利用140如此繼續(xù)遞推下去得：∴（2個顧客到達的概率）（n個顧客到達的概率）

即隨機變量N(t)=n服從泊松分布。它的數(shù)學(xué)期望和方差為：∴（1個顧客到達的概率）46如此繼續(xù)遞推下去得：∴（2個顧客到達的概率）（n個顧客到141級數(shù)令k=n-1，則：47級數(shù)令k=n-1，則：142即：同理方差為：顧客到達過程是一個泊松過程(泊松流)。48即：同理方差為：顧客到達過程是一個泊松過程(泊松流)。143其概率密度函數(shù)為：t>0

2.負指數(shù)分布當(dāng)輸入過程是泊松流時，我們研究兩顧客相繼到達的時間間隔的概率分布。設(shè)T為時間間隔，分布函數(shù)為FT（t），則：FT（t）=P{T≤t}

此概率等價于在[0，t）區(qū)間內(nèi)至少有1個顧客到達的概率。∴t>0

∵沒有顧客到達的概率為：(由（5）式而來)49其概率密度函數(shù)為：t>02.負指數(shù)分布∴t>0144

λ表示單位時間內(nèi)顧客平均到達數(shù)。

1/λ表示顧客到達的平均間隔時間。可以證明，間隔時間T獨立且服從負指數(shù)分布與顧客到達形成泊松流是等價的。對顧客的服務(wù)時間：系統(tǒng)處于忙期時兩顧客相繼離開系統(tǒng)的時間間隔，一般地也服從負指數(shù)分布，設(shè)：即T服從負指數(shù)分布，它的期望及方差為：接受服務(wù)，然后離開服務(wù)時間的分布：50λ表示單位時間內(nèi)顧客平均到達數(shù)。對顧客的服務(wù)時間145其中：μ表示單位時間內(nèi)能被服務(wù)的顧客數(shù)，即平均服務(wù)率。

1/μ表示一個顧客的平均服務(wù)時間。

3.愛爾朗(Erlang)分布設(shè)v1,v2，…,vk是k個獨立的隨機變量，服從相同參數(shù)

k

的負指數(shù)分布，那么：，則令，則ρ稱為服務(wù)強度。51其中：μ表示單位時間內(nèi)能被服務(wù)的顧客數(shù)，即平均3