運籌學(xué)第五章排隊論完整版

1、 2 排隊結(jié)構(gòu)服務(wù)機構(gòu)顧客源 顧客到達 排隊規(guī)則 服務(wù)規(guī)則離去 圖1 排 隊系統(tǒng)示意圖 排隊系統(tǒng)一般有三個基本組成部分：排隊系統(tǒng)一般有三個基本組成部分：1.1.輸輸 入過程；入過程；2.2.排隊規(guī)則；排隊規(guī)則；3.3.服務(wù)機構(gòu)?，F(xiàn)分別說服務(wù)機構(gòu)?，F(xiàn)分別說 明：明： 3 輸入即為顧客的到達，可有下列情況：輸入即為顧客的到達，可有下列情況： 1）顧客源可能是有限的，也可能是無限的。顧客源可能是有限的，也可能是無限的。 2）顧客是成批到達或是單個到達。顧客是成批到達或是單個到達。 3）顧客到達的間隔時間可能是隨機的或確定的。顧客到達的間隔時間可能是隨機的或確定的。 4）顧客到達可能是相互獨立的或關(guān)聯(lián)

2、的。所謂顧客到達可能是相互獨立的或關(guān)聯(lián)的。所謂 獨立就是以前顧客的到達對以后顧客的到達無影響。獨立就是以前顧客的到達對以后顧客的到達無影響。 5）輸入過程可以是平穩(wěn)的（輸入過程可以是平穩(wěn)的（stationarystationary）或說）或說 是對時間齊次的（是對時間齊次的（Homogeneous in timeHomogeneous in time），也可以），也可以 是非平穩(wěn)的。輸入過程是平穩(wěn)的是指顧客相繼到達是非平穩(wěn)的。輸入過程是平穩(wěn)的是指顧客相繼到達 的間隔時間分布和參數(shù)（均值、方差）與時間無關(guān)；的間隔時間分布和參數(shù)（均值、方差）與時間無關(guān)； 非平穩(wěn)的則是與時間相關(guān)，非平穩(wěn)的處理比較困

3、難。非平穩(wěn)的則是與時間相關(guān)，非平穩(wěn)的處理比較困難。 4 1）顧客到達后接受服務(wù)分為即時制（損失制）顧客到達后接受服務(wù)分為即時制（損失制） 和等待制。即時制不形成隊列，而對于等待制將和等待制。即時制不形成隊列，而對于等待制將 會形成隊列，顧客可以按下規(guī)則接收服務(wù)：會形成隊列，顧客可以按下規(guī)則接收服務(wù)： （1 1）先到先服務(wù)先到先服務(wù) FCFS FCFS （2 2）后到先服務(wù)后到先服務(wù) LCFS LCFS （3 3）隨機服務(wù)隨機服務(wù)RAND RAND （4 4）有優(yōu)先權(quán)服務(wù)有優(yōu)先權(quán)服務(wù) PRPR。 2）從隊列的空間可分為有容量限制和無容量從隊列的空間可分為有容量限制和無容量 限制。限制。 3 3）

4、從隊列數(shù)可分為單列和多列。）從隊列數(shù)可分為單列和多列。 5 1 1）服務(wù)機構(gòu)可以是單服務(wù)員和多服務(wù)員服務(wù)，）服務(wù)機構(gòu)可以是單服務(wù)員和多服務(wù)員服務(wù)， 這種服務(wù)形式與隊列規(guī)則聯(lián)合后形成了多種不同隊這種服務(wù)形式與隊列規(guī)則聯(lián)合后形成了多種不同隊 列，不同形式的排隊服務(wù)機構(gòu)，如：列，不同形式的排隊服務(wù)機構(gòu)，如： 1 1 2 n . . . . 1 2 n 。 單隊單服務(wù)臺多隊多服務(wù)臺（并列)單隊多服務(wù)臺（并列） 12n . 1 2 3 1 2 單隊多服務(wù)臺（串列）混合形式 6 上述特征中最主要的、影響最大的是：上述特征中最主要的、影響最大的是： 顧客相繼到達的間隔時間分布顧客相繼到達的間隔時間分布 服務(wù)

5、時間的分布服務(wù)時間的分布 服務(wù)臺數(shù)服務(wù)臺數(shù) D.G.KendallD.G.Kendall，19531953提出了分類法，稱為提出了分類法，稱為KendallKendall 記號記號( (適用于并列服務(wù)臺適用于并列服務(wù)臺) )即：即：X/Y/Z:A/B/CX/Y/Z:A/B/C 2)2)服務(wù)方式分為單個顧客服務(wù)和成批顧客服務(wù)。服務(wù)方式分為單個顧客服務(wù)和成批顧客服務(wù)。 3)3)服務(wù)時間分為確定型和隨機型。服務(wù)時間分為確定型和隨機型。 4)4)服務(wù)時間的分布在這里我們假定是平穩(wěn)的。服務(wù)時間的分布在這里我們假定是平穩(wěn)的。 7 式中：式中：X顧客相繼到達間隔時間分布。顧客相繼到達間隔時間分布。 M負(fù)指數(shù)

6、分布負(fù)指數(shù)分布Markov，D確定型分布確定型分布Deterministic， EkK階愛爾朗分布階愛爾朗分布Erlang， GI 一般相互獨立隨一般相互獨立隨 機分布機分布(General Independent)， G 一般隨機分布。一般隨機分布。 Y填寫服務(wù)時間分布（與上同）填寫服務(wù)時間分布（與上同） Z填寫并列的服務(wù)臺數(shù)填寫并列的服務(wù)臺數(shù) A排隊系統(tǒng)的最大容量排隊系統(tǒng)的最大容量 B顧客源數(shù)量顧客源數(shù)量 C排隊規(guī)則排隊規(guī)則 如如 即為顧客到達為泊松過即為顧客到達為泊松過 程，服務(wù)時間為負(fù)指數(shù)分布，單臺，無限容量，無程，服務(wù)時間為負(fù)指數(shù)分布，單臺，無限容量，無 限源，先到先服務(wù)的排隊系統(tǒng)模

7、型。限源，先到先服務(wù)的排隊系統(tǒng)模型。 8 1.1.排隊系統(tǒng)的統(tǒng)計推斷排隊系統(tǒng)的統(tǒng)計推斷: :即通過對排隊系統(tǒng)主即通過對排隊系統(tǒng)主 要參數(shù)的統(tǒng)計推斷和對排隊系統(tǒng)的結(jié)構(gòu)分析，判要參數(shù)的統(tǒng)計推斷和對排隊系統(tǒng)的結(jié)構(gòu)分析，判 斷一個給定的排隊系統(tǒng)符合于哪種模型，以便根斷一個給定的排隊系統(tǒng)符合于哪種模型，以便根 據(jù)排隊理論進行研究。據(jù)排隊理論進行研究。 2.2.系統(tǒng)性態(tài)問題系統(tǒng)性態(tài)問題: :即研究各種排隊系統(tǒng)的概率即研究各種排隊系統(tǒng)的概率 規(guī)律性，主要研究隊長分布、等待時間分布和忙規(guī)律性，主要研究隊長分布、等待時間分布和忙 期分布等統(tǒng)計指標(biāo)期分布等統(tǒng)計指標(biāo), ,包括了瞬態(tài)和穩(wěn)態(tài)兩種情形。包括了瞬態(tài)和穩(wěn)態(tài)兩

8、種情形。 3.3.最優(yōu)化問題：即包括最優(yōu)設(shè)計最優(yōu)化問題：即包括最優(yōu)設(shè)計( (靜態(tài)優(yōu)化靜態(tài)優(yōu)化) )， 最優(yōu)運營（動態(tài)優(yōu)化）。最優(yōu)運營（動態(tài)優(yōu)化）。 9 求解一般排隊系統(tǒng)問題的目的主要是通過求解一般排隊系統(tǒng)問題的目的主要是通過 研究排隊系統(tǒng)運行的效率指標(biāo)，估計服務(wù)質(zhì)研究排隊系統(tǒng)運行的效率指標(biāo)，估計服務(wù)質(zhì) 量，確定系統(tǒng)的合理結(jié)構(gòu)和系統(tǒng)參數(shù)的合理量，確定系統(tǒng)的合理結(jié)構(gòu)和系統(tǒng)參數(shù)的合理 值，以便實現(xiàn)對現(xiàn)有系統(tǒng)合理改進和對新建值，以便實現(xiàn)對現(xiàn)有系統(tǒng)合理改進和對新建 系統(tǒng)的最優(yōu)設(shè)計等。系統(tǒng)的最優(yōu)設(shè)計等。 排隊問題的一般步驟：排隊問題的一般步驟： 1 1. . 確定或擬合排隊系統(tǒng)顧客到達的時間確定或擬合排隊

9、系統(tǒng)顧客到達的時間 間隔分布和服務(wù)時間分布間隔分布和服務(wù)時間分布( (可實測可實測) )。 2. 2. 研究系統(tǒng)狀態(tài)的概率。系統(tǒng)狀態(tài)是指研究系統(tǒng)狀態(tài)的概率。系統(tǒng)狀態(tài)是指 系統(tǒng)中顧客數(shù)。狀態(tài)概率用系統(tǒng)中顧客數(shù)。狀態(tài)概率用P Pn n(t)(t)表示表示, ,即在即在t t 時刻系統(tǒng)中有時刻系統(tǒng)中有n n個顧客的概率，也稱瞬態(tài)概率。個顧客的概率，也稱瞬態(tài)概率。 10 求解狀態(tài)概率求解狀態(tài)概率P Pn n(t)(t)方法是建立含方法是建立含P Pn n(t)(t)的微分差的微分差 分方程，通過求解微分差分方程得到系統(tǒng)瞬態(tài)解，由分方程，通過求解微分差分方程得到系統(tǒng)瞬態(tài)解，由 于瞬態(tài)解一般求出確定值比較

10、困難，即便求得一般也于瞬態(tài)解一般求出確定值比較困難，即便求得一般也 很難使用。因此我們常常使用它的極限很難使用。因此我們常常使用它的極限( (如果存在的如果存在的 話話) )： n t t n p)(plim 穩(wěn)態(tài)的物理意義見右圖，穩(wěn)態(tài)的物理意義見右圖， 系統(tǒng)的穩(wěn)態(tài)一般很快都系統(tǒng)的穩(wěn)態(tài)一般很快都 能達到，但實際中達不能達到，但實際中達不 到穩(wěn)態(tài)的現(xiàn)象也存在。到穩(wěn)態(tài)的現(xiàn)象也存在。 值得注意的是求穩(wěn)態(tài)概值得注意的是求穩(wěn)態(tài)概 率率P Pn n并不一定求并不一定求t的的 極限極限,而只需求而只需求P Pn n (t)=0 (t)=0 即可。即可。 過渡狀態(tài) 穩(wěn)定狀態(tài) pn t 圖3 排隊系統(tǒng)狀態(tài)變化示

11、意圖 稱為穩(wěn)態(tài)稱為穩(wěn)態(tài)( (steady state)steady state)解，解，或稱統(tǒng)計平衡狀態(tài)或稱統(tǒng)計平衡狀態(tài) ( (Statistical Equilibrium State)Statistical Equilibrium State)的解。的解。 11 3 3. .根據(jù)排隊系統(tǒng)對應(yīng)的理論模型求出用以判斷系統(tǒng)根據(jù)排隊系統(tǒng)對應(yīng)的理論模型求出用以判斷系統(tǒng) 運行優(yōu)劣的基本數(shù)量指標(biāo)的概率分布或特征數(shù)。運行優(yōu)劣的基本數(shù)量指標(biāo)的概率分布或特征數(shù)。 數(shù)量指標(biāo)主要包括數(shù)量指標(biāo)主要包括: : (1)(1)平均隊長（平均隊長（L Ls s）: :系統(tǒng)中的顧客數(shù)。系統(tǒng)中的顧客數(shù)。 平均隊列長（平均隊列長

12、（L Lq q）: :系統(tǒng)中排隊等待服務(wù)的顧客數(shù)。系統(tǒng)中排隊等待服務(wù)的顧客數(shù)。 系統(tǒng)中顧客數(shù)系統(tǒng)中顧客數(shù)L Ls s = =系統(tǒng)中排隊等待服務(wù)的顧客數(shù)系統(tǒng)中排隊等待服務(wù)的顧客數(shù)L Lq q + +正被正被 服務(wù)的顧客數(shù)服務(wù)的顧客數(shù)c c (2)(2)平均逗留時間平均逗留時間(Ws)(Ws): :指一個顧客在系統(tǒng)中的停留時間。指一個顧客在系統(tǒng)中的停留時間。 平均等待時間平均等待時間(Wq)(Wq): :指一個顧客在系統(tǒng)中排隊等待的時間。指一個顧客在系統(tǒng)中排隊等待的時間。 (3)(3)忙期忙期：指從顧客到達空閑服務(wù)機構(gòu)起到服務(wù)機構(gòu)再次為：指從顧客到達空閑服務(wù)機構(gòu)起到服務(wù)機構(gòu)再次為 空閑這段時間長度

13、。（忙期和一個忙期中平均完成服務(wù)顧客空閑這段時間長度。（忙期和一個忙期中平均完成服務(wù)顧客 數(shù)都是衡量服務(wù)機構(gòu)效率的指標(biāo)，忙期關(guān)系到工作強度）數(shù)都是衡量服務(wù)機構(gòu)效率的指標(biāo)，忙期關(guān)系到工作強度） 4. .排隊系統(tǒng)指標(biāo)優(yōu)化排隊系統(tǒng)指標(biāo)優(yōu)化 含優(yōu)化設(shè)計與優(yōu)化運營。含優(yōu)化設(shè)計與優(yōu)化運營。 問題問題1 1 系統(tǒng)中顧客數(shù)系統(tǒng)中顧客數(shù)= =平均隊列長（平均隊列長（L Lq q）+1+1？ 12 排隊系統(tǒng)的組成與特征排隊系統(tǒng)的組成與特征 排隊系統(tǒng)的模型分類排隊系統(tǒng)的模型分類 顧客到達間隔時間和服務(wù)時間的經(jīng)驗分布與顧客到達間隔時間和服務(wù)時間的經(jīng)驗分布與 理論分布理論分布 穩(wěn)態(tài)概率穩(wěn)態(tài)概率P Pn n的計算的計算

14、標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1M/M/1模型模型( (M/M/1:/FCFS)/FCFS) 系統(tǒng)容量有限制的系統(tǒng)容量有限制的模型模型M/M/1:N/FCFS/FCFS 顧客源有限模型顧客源有限模型M/M/1/M/M/ FCFSFCFS 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/CM/M/C模型模型M/M/C:/FCFS/FCFS 13 M/M/C型系統(tǒng)和型系統(tǒng)和C個個M/M/1型系統(tǒng)型系統(tǒng) 系統(tǒng)容量有限制的多服務(wù)臺模型系統(tǒng)容量有限制的多服務(wù)臺模型(M/M/C/N/) 顧客源為有限的顧客源為有限的多服務(wù)臺模型多服務(wù)臺模型(M/M/C/M)(M/M/C/M) 一般服務(wù)時間的（一般服務(wù)時間的（M/G/1M/G/1）模型）模型 P

15、ollaczek-Khintchine(P-K) 公式公式 定長服務(wù)時間定長服務(wù)時間 M/D/1M/D/1模型模型 愛爾朗服務(wù)時間愛爾朗服務(wù)時間M/Ek/1模型模型 排隊系統(tǒng)優(yōu)化排隊系統(tǒng)優(yōu)化 M/M/1 模型中的最優(yōu)服務(wù)率模型中的最優(yōu)服務(wù)率u 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1Model 系統(tǒng)容量為系統(tǒng)容量為N的情形的情形 M/M/C模型中最優(yōu)服務(wù)臺數(shù)模型中最優(yōu)服務(wù)臺數(shù)C 14 一個排隊系統(tǒng)的最主要特征參數(shù)是一個排隊系統(tǒng)的最主要特征參數(shù)是 顧客的到達間隔時間分布與服務(wù)時間分顧客的到達間隔時間分布與服務(wù)時間分 布。要研究到達間隔時間分布與服務(wù)時布。要研究到達間隔時間分布與服務(wù)時 間分布需要首先根據(jù)現(xiàn)存系統(tǒng)原

16、始資料間分布需要首先根據(jù)現(xiàn)存系統(tǒng)原始資料 統(tǒng)計出它們的統(tǒng)計出它們的經(jīng)驗分布經(jīng)驗分布（見（見P315319P315319），）， 然后與理論分布然后與理論分布擬合擬合，若能照應(yīng)，我們，若能照應(yīng)，我們 就可以得出上述的分布情況。就可以得出上述的分布情況。 15 經(jīng)驗分布是對排隊系統(tǒng)的某些時間參數(shù)根據(jù)經(jīng)驗分布是對排隊系統(tǒng)的某些時間參數(shù)根據(jù) 經(jīng)驗數(shù)據(jù)進行統(tǒng)計分析，并依據(jù)統(tǒng)計分析結(jié)果假經(jīng)驗數(shù)據(jù)進行統(tǒng)計分析，并依據(jù)統(tǒng)計分析結(jié)果假 設(shè)其統(tǒng)計樣本的總體分布，選擇合適的檢驗方法設(shè)其統(tǒng)計樣本的總體分布，選擇合適的檢驗方法 進行檢驗，當(dāng)通過檢驗時，我們認(rèn)為時間參數(shù)的進行檢驗，當(dāng)通過檢驗時，我們認(rèn)為時間參數(shù)的 經(jīng)驗數(shù)

17、據(jù)服從該假設(shè)分布。經(jīng)驗數(shù)據(jù)服從該假設(shè)分布。 分布的擬合檢驗一般采用分布的擬合檢驗一般采用 2檢驗。由數(shù)理統(tǒng)檢驗。由數(shù)理統(tǒng) 計的知識我們知：若樣本量計的知識我們知：若樣本量n充分大充分大(n50)，則則 當(dāng)假設(shè)當(dāng)假設(shè)H0為真時，統(tǒng)計量總是近似地服從自由度為真時，統(tǒng)計量總是近似地服從自由度 為為k-r-1的的 2分布，其中分布，其中k為分組數(shù)，為分組數(shù)，r為檢驗分為檢驗分 布中被估計的參數(shù)個數(shù)。布中被估計的參數(shù)個數(shù)。 16 t n ne n t tP ! )( 式中式中為常數(shù)為常數(shù)(0)0)，稱，稱X X服從參數(shù)為服從參數(shù)為的泊松分布，的泊松分布， 若在上式中引入時間參數(shù)若在上式中引入時間參數(shù)t

18、t，即令，即令tt代替代替，則有：，則有： 在概率論中，我們曾學(xué)過泊松分布，設(shè)隨機變在概率論中，我們曾學(xué)過泊松分布，設(shè)隨機變 量為量為X，則有：，則有： ! n e nxP n n=0,1,2, （1） 與時間有關(guān)的隨機變量的概率與時間有關(guān)的隨機變量的概率，是一個，是一個隨機過程隨機過程， 即即泊松過程泊松過程。 t0，n=0,1,2, （2） 17 )()(,1221ntNtNPttPn （t2t1，n0） 若設(shè)若設(shè)N(t)N(t)表示在時間區(qū)間表示在時間區(qū)間0,t)0,t)內(nèi)到達的顧客數(shù)內(nèi)到達的顧客數(shù) (t0),P(t0),Pn n(t(t1 1,t,t2 2) )表示在時間區(qū)間表示在時間

19、區(qū)間tt1 1,t,t2 2)(t)(t2 2tt1 1) )內(nèi)有內(nèi)有 n(0)n(0)個顧客到達的概率。即：個顧客到達的概率。即： 在一定的假設(shè)條件下在一定的假設(shè)條件下 顧客的到達過程就是顧客的到達過程就是 一個泊松過程。一個泊松過程。 當(dāng)當(dāng)P Pn n(t(t1 1,t,t2 2) )符合下述三個條件時，顧客到達過程符合下述三個條件時，顧客到達過程 就是泊松過程就是泊松過程( (顧客到達形成普阿松流顧客到達形成普阿松流) )。 18 無后效性：無后效性：各區(qū)間的到達相互獨立各區(qū)間的到達相互獨立, ,即即MarkovMarkov性。性。 . . . . . . . t 0 t1 t2 tn-

20、1 tn |)(|)( 11112211 )()(,.,)(,)( nnnn xtxnxtxxtxxtxn ntxPntxP 也就是說過程在也就是說過程在t+tt+t所處的狀態(tài)與所處的狀態(tài)與t t以前所處的狀以前所處的狀 態(tài)無關(guān)。態(tài)無關(guān)。 平穩(wěn)性：平穩(wěn)性：即對于足夠小的即對于足夠小的tt，有：，有： )()(tttttP ， 1 普阿松流具有如下特性：普阿松流具有如下特性： 在在t,t+tt,t+t內(nèi)有一個顧客到達的概率與內(nèi)有一個顧客到達的概率與t t無關(guān)無關(guān), , 而與而與tt成正比。成正比。 19 普通性：普通性：對充分小的對充分小的t,t,在時間區(qū)間（在時間區(qū)間（t,t+tt） 內(nèi)有內(nèi)有

21、2 2個或個或2 2個以上顧客到達的概率是一高階無窮小個以上顧客到達的概率是一高階無窮小. . 由此知，在由此知，在(t，t+t)t)區(qū)間內(nèi)沒有顧客到達的概率為：區(qū)間內(nèi)沒有顧客到達的概率為： )(1),( 0 tottttP 令令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 是常數(shù)，它是常數(shù)，它表示單位時間到達的顧客數(shù)，稱表示單位時間到達的顧客數(shù)，稱 為概率強度。為概率強度。 2 )(),( n n totttP 即即 P P0 0+P+P1 1+P+P2 2=1 =1 在上述假設(shè)下，在上

22、述假設(shè)下，t t時刻系統(tǒng)中有時刻系統(tǒng)中有n n個顧客的概率個顧客的概率p pn(t) n(t)： ： 20 )()( )( 1 tPtP dt tdP nn n 0)0( n P (1)(1) )( )( 0 0 tP dt tdP 1)0( 0 P (2)(2) 當(dāng)當(dāng)n=0時，則時，則 t e)t(P 0 (3)(3) （沒有顧客到達的概率）（沒有顧客到達的概率） （n n個顧客到達的概率）個顧客到達的概率） t n n e n t tP ! )( )( （4 4） 瞬態(tài)方瞬態(tài)方 程程 （1 1）、（）、（2 2）兩式求導(dǎo)并令導(dǎo)數(shù)為）兩式求導(dǎo)并令導(dǎo)數(shù)為0 0，得穩(wěn)態(tài)概率：，得穩(wěn)態(tài)概率： 21

23、 級數(shù)級數(shù). !n x . ! x xe n x 2 1 2 t k k e !k )t( 0 ! )( )()( 11 n t netnPtNE n n t n n )!1( )( 1 1 n t te n n t 令令k=n-1，則：，則： ! )( )( 0 k t tetNE k k t tetetNE tt )( ttar )(N(V 同理方差為：同理方差為： 顧客到達過程是一個顧客到達過程是一個泊松過程泊松過程( (泊松流泊松流) )。 期望期望 22 表示單位時間內(nèi)顧客平均到達數(shù)。表示單位時間內(nèi)顧客平均到達數(shù)。 1/表示顧客到達的平均間隔時間。表示顧客到達的平均間隔時間。 對顧客

24、的服務(wù)時間對顧客的服務(wù)時間 ：系統(tǒng)處于忙期時系統(tǒng)處于忙期時兩顧客相繼離兩顧客相繼離 開系統(tǒng)的時間間隔開系統(tǒng)的時間間隔，一般地也服從負(fù)指數(shù)分布，一般地也服從負(fù)指數(shù)分布， 1 TE 2 1 TVar 接受服務(wù)，然后離開接受服務(wù)，然后離開 服務(wù)時間的分布：服務(wù)時間的分布： 可以證明可以證明當(dāng)輸入過程是泊松流時，兩顧客相繼到當(dāng)輸入過程是泊松流時，兩顧客相繼到 達的時間間隔達的時間間隔T T獨立且服從負(fù)指數(shù)分布。（等價）獨立且服從負(fù)指數(shù)分布。（等價） t etF 1)( t etf )( ，則，則 23 其中：其中：表示單位時間內(nèi)能被服務(wù)的顧客數(shù)，即平均表示單位時間內(nèi)能被服務(wù)的顧客數(shù)，即平均 服務(wù)率。服

25、務(wù)率。 1/1/表示一個顧客的平均服務(wù)時間。表示一個顧客的平均服務(wù)時間。 設(shè)設(shè)v v1 1, v, v2 2， ，, v , vk k是是k k個獨立的隨機變量，服從相同個獨立的隨機變量，服從相同 參數(shù)參數(shù) k k 的負(fù)指數(shù)分布，那么：的負(fù)指數(shù)分布，那么： t etF 1)( t etf )( ，則，則 令令 ，則，則稱為服務(wù)強度稱為服務(wù)強度。 k T 21 24 串聯(lián)的串聯(lián)的k k個服務(wù)臺個服務(wù)臺，每臺服務(wù)時間相互獨立，服，每臺服務(wù)時間相互獨立，服 從相同的負(fù)指數(shù)分布（參數(shù)從相同的負(fù)指數(shù)分布（參數(shù)k k ），那么一顧客走完），那么一顧客走完k k 個服務(wù)臺總共所需要服務(wù)時間就服從上述的個服務(wù)

26、臺總共所需要服務(wù)時間就服從上述的k k階階 ErlangErlang分布。分布。 0 1 1 te )!k( )kt(k )t (f tk k k 則稱則稱T服從服從k階階愛爾朗分布。其特征值為：愛爾朗分布。其特征值為： 1 TE 2 1 k TVar , 其概率密度是其概率密度是 1/ k1/ k表示一個顧客的一個服務(wù)臺的平均服務(wù)時間。表示一個顧客的一個服務(wù)臺的平均服務(wù)時間。 25 例例: :有易碎物品有易碎物品500500件件, ,由甲地運往乙地由甲地運往乙地, ,根據(jù)以根據(jù)以 往統(tǒng)計資料往統(tǒng)計資料, ,在運輸過程中易碎物品按普阿松流發(fā)在運輸過程中易碎物品按普阿松流發(fā) 生破碎生破碎, ,其

27、破損率為其破損率為0.002,0.002,現(xiàn)求現(xiàn)求:1.:1.破碎破碎3 3件物品的件物品的 概率概率;2.;2.破碎少于破碎少于3 3件的概率和多于件的概率和多于3 3件的概率件的概率;3.;3. 至少有一件破損的概率至少有一件破損的概率. . 解解: : =0.002500=1 1 1破碎破碎3 3件物品的概率為件物品的概率為: : P(k=3)=( P(k=3)=( 3 3/3/3！)e)e- - =(1=(13 3/3/3！)e)e-1 -1=0.0613 =0.0613 即物品破碎即物品破碎3 3件的概率為件的概率為6.136.13 2. 2.破碎物品少于破碎物品少于3 3件的概率件

28、的概率: : 26 破碎物品少于破碎物品少于3 3件的概率為件的概率為91.9791.97 破碎物品多于破碎物品多于3 3件的概率為件的概率為: : 02. 098. 01 ! 13 3 0 k k e k p 3.3.至少有一件破碎的概率為至少有一件破碎的概率為 PkPk 1=1-(11=1-(1k k/k!)e/k!)e- - =1-(1=1-(10 0/0!)e/0!)e-1 -1=0.632 =0.632 9197. 0 2 1 112 1 2 0 ee k np 27 對排隊模型，在給定輸入和服務(wù)條件下，主要對排隊模型，在給定輸入和服務(wù)條件下，主要 研究系統(tǒng)的下述運行指標(biāo)：研究系統(tǒng)的

29、下述運行指標(biāo)： (1)(1)系統(tǒng)的系統(tǒng)的平均隊長平均隊長LsLs( (期望值期望值) )和和平均隊列長平均隊列長 LqLq( (期望值期望值) )； (2)(2)系統(tǒng)中系統(tǒng)中顧客平均逗留時間顧客平均逗留時間WsWs與隊列中與隊列中平均等平均等 待時間待時間WqWq； 本節(jié)只研究本節(jié)只研究M/M/1M/M/1模型，下面分三種情況討論：模型，下面分三種情況討論： 28 系統(tǒng)中有系統(tǒng)中有 n n個顧客個顧客 M/M/1:/FCFS/FCFS模型模型 在任意時刻在任意時刻t t，狀態(tài)為，狀態(tài)為n n的概率的概率P Pn n(t)(t)（瞬態(tài)概率），（瞬態(tài)概率）， 它決定了系統(tǒng)的運行特征。它決定了系統(tǒng)的

30、運行特征。 已知顧客到達服從參數(shù)為已知顧客到達服從參數(shù)為的泊松過程，服務(wù)時的泊松過程，服務(wù)時 間服從參數(shù)為間服從參數(shù)為的負(fù)指數(shù)分布?，F(xiàn)仍然通過研究區(qū)間的負(fù)指數(shù)分布?，F(xiàn)仍然通過研究區(qū)間 t，t+tt）的變化來求解。在時刻）的變化來求解。在時刻t+tt，系統(tǒng)中有，系統(tǒng)中有n n 個顧客不外乎有下列四種情況（個顧客不外乎有下列四種情況（ t，t+tt）內(nèi)到達）內(nèi)到達 或離開或離開2 2個以上個以上沒列入）。沒列入）。 ？ 29 區(qū)區(qū)間間( (t t, , t+t t) ) 情情況況 時時刻刻t t 的的顧顧客 客 到 到達達 離離去去 時時刻刻t+t t 的的顧顧客客 ( (t t, , t+t t

31、) )的的概概率率 0 0, , t+t t 的的概概率率 A n n 1-t+O(t) 1-t+O(t) Pn(1-t+O(t) （1-t+O(t)） B n+1 n 1-t+O(t) t+O(t) Pn+1(1-t+O(t) （t+O(t)） C n-1 n t+O(t) 1-t+O(t) Pn-1(t+O(t) （1-t+O(t)） D n n t+O(t) t+O(t) Pn(t+O(t) （t+O(t)） 由于這四種情況是互不相容的，所以由于這四種情況是互不相容的，所以Pn(t+t)t)應(yīng)應(yīng) 是這四項之和，則有：是這四項之和，則有： tttPtttPtttPttP nnnn )1)(

32、)()1)(1)()( 1 )()1 ()( 1 tOtttP n 所有的高階無所有的高階無 窮小合并窮小合并 30 ) t(Ot) t (Pt) t (P) tt)(t (P nnn 11 1 t ) t(O ) t (P)() t (P) t (P t ) t (P) tt (P nnn nn 11 令令t0t0，得關(guān)于，得關(guān)于P Pn n(t)(t)的微分差分方程：的微分差分方程： )()()()( )( 11 tPtPtP dt tdP nnn n (1) 當(dāng)當(dāng)n=0時，只有表中的（時，只有表中的（A）、（）、（B）兩種情況，）兩種情況， 因為在較小的因為在較小的tt內(nèi)不可能發(fā)生（內(nèi)不

33、可能發(fā)生（D D）（到達后即離）（到達后即離 去），若發(fā)生可將去），若發(fā)生可將tt取小即可。取小即可。 )t()t)(t (P)t)(t (P)tt (P 11 100 ) t (P) t (P dt ) t (dP 10 0 (2)(2) 生生 滅滅 過過 程程 瞬瞬 態(tài)態(tài) 解解 31 由此可得該排隊系統(tǒng)的由此可得該排隊系統(tǒng)的狀態(tài)轉(zhuǎn)移圖狀態(tài)轉(zhuǎn)移圖： 由（由（4）得：）得： 001 PPP 其中其中服務(wù)強度服務(wù)強度 將其代入（將其代入（3）式并令）式并令n=1,2,(也可從狀態(tài)轉(zhuǎn)移也可從狀態(tài)轉(zhuǎn)移 圖中看出狀態(tài)平衡方程圖中看出狀態(tài)平衡方程)得：得： 關(guān)于關(guān)于Pn的差的差 分方程分方程 n-1n-

34、1 n n n+1n+1 2 2 0 0 1 1 穩(wěn)態(tài)時，穩(wěn)態(tài)時， 它 對 時它 對 時 間的導(dǎo)數(shù)為間的導(dǎo)數(shù)為0，所以由，所以由(1)、(2)兩式得：兩式得： Pn(t)與時間無關(guān)與時間無關(guān), 可以寫成可以寫成Pn, 0 11 nnn P)(PP 0 10 PP (3)(3) (4)(4) 32 0 120 P)(PP n=1n=1 0 020 P)(PP 0 2 0 2 02 1 PP)(P )( P n=2n=2 0 231 P)(PP 0 0 2 30 P)(PP 0 3 0 3 0 2 2 2 3 1 PP)(P )( P 33 以此類推以此類推，當(dāng)，當(dāng)n=n時，時， 00 )(PPP

35、 nn n (5)(5) 1 1 0 n n P 以及概率性質(zhì)知：以及概率性質(zhì)知： 1 1 1 0 0 0 PP n n (數(shù)列的極限為數(shù)列的極限為 ) 1 1 1 0 P n n )(P 1 (6)(6) 否則排隊無限遠否則排隊無限遠 系統(tǒng)系統(tǒng) 穩(wěn)態(tài)穩(wěn)態(tài) 概率概率 系統(tǒng)的運行指標(biāo)系統(tǒng)的運行指標(biāo) 34 (1) 系統(tǒng)中的隊長系統(tǒng)中的隊長Ls（平均隊長）（平均隊長） n nn ns nPnL 00 1 .)(n.)()()( n 113121 32 .nn. nn 143322 3322 1 32 . n (01) 1 Ls 即即: : (7)(7) 期望期望 35 (2) 隊列中等待的平均顧客數(shù)隊列中等待的平均顧客數(shù)Lq n nn n qnPnL 11 1