1、第七章連續(xù)時(shí)間馬爾科夫過程,第七章 連續(xù)時(shí)間馬爾科夫過程,7.1、Ito過程,7.2、增量過程,7.3、泊松過程,7.4、排隊(duì)論與生滅過程,7.4、排隊(duì)論與生滅過程,排隊(duì)論（Queuing theory），又稱隨機(jī)服務(wù)系統(tǒng)，是通過研究各種服務(wù)系統(tǒng)在排隊(duì)等待現(xiàn)象中的概率特性，解決服務(wù)系統(tǒng)最優(yōu)設(shè)計(jì)與最優(yōu)控制的一種理論。,4,排隊(duì)論起源于20世紀(jì)初的電話通話。9091920年丹麥數(shù)學(xué)家、電氣工程師愛爾朗（A.K.Erlang）用概率論方法研究電話通話問題， 20世紀(jì)30年代，費(fèi)勒(W.Feller)引進(jìn)了生滅過程 20世紀(jì)50年代，D.G.Kendall用嵌入馬爾柯夫鏈方法研究排隊(duì)論,7.4、排隊(duì)論

2、與生滅過程,7.4、排隊(duì)論與生滅過程,排隊(duì)系統(tǒng)的例子,(1)單服務(wù)臺單隊(duì),圖7.4.1 單服務(wù)臺單隊(duì)系統(tǒng),7.4、排隊(duì)論與生滅過程,根據(jù)服務(wù)臺的數(shù)量及排隊(duì)方式，排隊(duì)系統(tǒng)可以分為四類,(2)多服務(wù)臺單隊(duì),顧客到達(dá),服務(wù)臺,顧客離去,服務(wù)臺,服務(wù)臺,圖7.4.2 多服務(wù)臺單隊(duì)系統(tǒng),7.4、排隊(duì)論與生滅過程,根據(jù)服務(wù)臺的數(shù)量及排隊(duì)方式，排隊(duì)系統(tǒng)可以分為四類,(3)多隊(duì)多服務(wù)臺,圖7.4.3 多服務(wù)臺多隊(duì)系統(tǒng),顧客到達(dá),服務(wù)臺,顧客離去,服務(wù)臺,服務(wù)臺,7.4、排隊(duì)論與生滅過程,根據(jù)服務(wù)臺的數(shù)量及排隊(duì)方式，排隊(duì)系統(tǒng)可以分為四類,(4)多服務(wù)臺串聯(lián)服務(wù),圖7.4.4 多服務(wù)臺串聯(lián)系統(tǒng),顧客到達(dá),顧客離去

3、,7.4、排隊(duì)論與生滅過程,根據(jù)服務(wù)臺的數(shù)量及排隊(duì)方式，排隊(duì)系統(tǒng)可以分為四類,排隊(duì)過程的組成部分,實(shí)際中的排隊(duì)系統(tǒng)各有不同，但概括起來都由三個(gè)基本部分組成： 輸入過程、 排隊(duì)及排隊(duì)規(guī)則、 服務(wù)機(jī)制,7.4、排隊(duì)論與生滅過程,排隊(duì)過程的組成部分,1、輸入過程,（1）顧客總體數(shù)，又稱顧客源、輸入源。,顧客源可以是有限的，也可以是無限的。如到售票處購票的顧客總數(shù)可以認(rèn)為是無限的，而某個(gè)工廠因故障待修的機(jī)床則是有限的,7.4、排隊(duì)論與生滅過程,排隊(duì)過程的組成部分,1、輸入過程,（1）顧客總體數(shù)，又稱顧客源、輸入源。,（2）顧客到達(dá)的形式,單個(gè)到達(dá)，還是成批到達(dá)。如大學(xué)生到圖書館借書是單個(gè)到達(dá)，而購買的

4、材料入庫則可以看成成批到達(dá)。,7.4、排隊(duì)論與生滅過程,排隊(duì)過程的組成部分,1、輸入過程,顧客總體數(shù)，又稱顧客源、輸入源,顧客到達(dá)的形式,顧客流的概率分布，即單位時(shí)間內(nèi)到達(dá)的顧客數(shù)，也可用顧客相繼到達(dá)的時(shí)間間隔描述,這是刻畫輸入過程的最重要的內(nèi)容。排隊(duì)論中常用的分布：,定長分布(D)，這種分布顧客相繼到達(dá)的時(shí)間間隔是確定的，如產(chǎn)品通過傳送帶進(jìn)入包裝箱就是定長分布的例子。,泊松流(M), 在一定時(shí)間區(qū)間內(nèi)，恰好到達(dá)k個(gè)顧客的概率僅與區(qū)間長度有關(guān)，而與區(qū)間起始時(shí)刻無關(guān),7.4、排隊(duì)論與生滅過程,排隊(duì)過程的組成部分,2、排隊(duì)規(guī)則,排隊(duì)系統(tǒng),7.4、排隊(duì)論與生滅過程,排隊(duì)分為有限排隊(duì)和無限排隊(duì)兩類。前

5、者是指系統(tǒng)的空間是有限的，當(dāng)系統(tǒng)被占滿時(shí)，后面再來的顧客將不能進(jìn)入系統(tǒng)；后者是指系統(tǒng)中的顧客數(shù)可以是無限的，隊(duì)列可以排到無限長，顧客到達(dá)后均可進(jìn)入系統(tǒng)排隊(duì)或接受服務(wù)。具體又分為：,等待制：即無限排隊(duì),損失制：這種系統(tǒng)是指排隊(duì)空間為零的系統(tǒng)，實(shí)際上是不允許排隊(duì)。當(dāng)顧客到大系統(tǒng)時(shí)，如果所有服務(wù)臺均被占用，則自動離去，并不再回來，這部分顧客就被損失掉了。,混合制：該系統(tǒng)是等待制和損失制系統(tǒng)的結(jié)合，一般是指允許排隊(duì)，但又不允許隊(duì)列無限長下去,排隊(duì)過程的組成部分,2、排隊(duì)規(guī)則,排隊(duì)規(guī)則,7.4、排隊(duì)論與生滅過程,先來先服務(wù)(FCFS),后來先服務(wù)(LCFS) ：在許多庫存系統(tǒng)中會出現(xiàn)這種情形，如鋼板存入

6、倉庫后，需要時(shí)總是從最上面的取出；又如在情報(bào)系統(tǒng)中，后來到達(dá)的信息往往更加重要，應(yīng)首先加以分析和利用。,具有優(yōu)先權(quán)的服務(wù)(PS)：如病危的患者應(yīng)優(yōu)先治療，加急的電報(bào)電話應(yīng)優(yōu)先處理等,隨機(jī)服務(wù)(SIRO),排隊(duì)過程的組成部分,3、服務(wù)機(jī)制,服務(wù)員的數(shù)量及構(gòu)成形式,7.4、排隊(duì)論與生滅過程,從數(shù)量上說，服務(wù)臺有單臺和多臺之分。從構(gòu)成形式上看，有單隊(duì)單服務(wù)臺式、單隊(duì)多服務(wù)臺并聯(lián)式、多隊(duì)多服務(wù)臺并聯(lián)式、單隊(duì)多服務(wù)臺串聯(lián)式等。,排隊(duì)過程的組成部分,3、服務(wù)機(jī)制,服務(wù)員的數(shù)量及構(gòu)成形式,7.4、排隊(duì)論與生滅過程,服務(wù)方式,指在某一時(shí)刻接受服務(wù)的顧客數(shù)，有單個(gè)服務(wù)和成批服務(wù)兩種。,排隊(duì)過程的組成部分,3、服

7、務(wù)機(jī)制,服務(wù)員的數(shù)量及構(gòu)成形式,7.4、排隊(duì)論與生滅過程,服務(wù)方式,服務(wù)時(shí)間的分布,定長分布(D) 指每個(gè)顧客接受服務(wù)的時(shí)間是一個(gè)確定的常數(shù)。,排隊(duì)過程的組成部分,3、服務(wù)機(jī)制,服務(wù)員的數(shù)量及構(gòu)成形式,7.4、排隊(duì)論與生滅過程,服務(wù)方式,服務(wù)時(shí)間的分布,定長分布(D),負(fù)指數(shù)分布(M),負(fù)指數(shù)概率分布能較好地描述一些排隊(duì)系統(tǒng)里服務(wù)時(shí)間的概率分布情況。在負(fù)指數(shù)分布里，服務(wù)時(shí)間小于或等于時(shí)間長度t的概率： F（t）=P（服務(wù)時(shí)間t）=1-e-t 這里的為單位時(shí)間里被服務(wù)完的平均顧客數(shù)。,排隊(duì)過程的組成部分,3、服務(wù)機(jī)制,服務(wù)員的數(shù)量及構(gòu)成形式,7.4、排隊(duì)論與生滅過程,服務(wù)方式,服務(wù)時(shí)間的分布,定

8、長分布(D),負(fù)指數(shù)分布(M),K階愛爾朗分布,K階愛爾朗分布 設(shè)X1，X2，Xk是k個(gè)互相獨(dú)立的，具有相同參數(shù)的負(fù)指數(shù)分布隨機(jī)變量，則隨機(jī)變量：X=X1+X2+X3+Xk 服從k階愛爾朗分布，X的密度函數(shù)為： 隨機(jī)變量X的均值和方差分別為： E(X)=1/，Var(X)=1/k2 如果顧客連續(xù)接受串聯(lián)的k個(gè)服務(wù)臺的服務(wù)，各服務(wù)臺的服務(wù)時(shí)間相互獨(dú)立，且均服從參數(shù)為的負(fù)指數(shù)分布，則顧客接受k個(gè)服務(wù)臺總共所需的時(shí)間就服從k階愛爾朗分布。,7.4、排隊(duì)論與生滅過程,當(dāng)一個(gè)排隊(duì)服務(wù)系統(tǒng)開始運(yùn)轉(zhuǎn)時(shí)，系統(tǒng)狀態(tài)很大程度上取決于系統(tǒng)的初始狀態(tài)和運(yùn)轉(zhuǎn)經(jīng)歷的時(shí)間，但過了一段時(shí)間后，系統(tǒng)的狀態(tài)將獨(dú)立于初始狀態(tài)及經(jīng)歷

9、的時(shí)間，這時(shí)稱系統(tǒng)處于平穩(wěn)狀態(tài)。由于對系統(tǒng)的瞬時(shí)狀態(tài)研究分析起來很困難，所以排隊(duì)論中主要研究系統(tǒng)處于平穩(wěn)狀態(tài)的工作情況。,排隊(duì)過程的平穩(wěn)狀態(tài),7.4、排隊(duì)論與生滅過程,X/Y/Z/A/B/C 這里的X記顧客相繼到達(dá)的時(shí)間間隔的分布，M表示服從泊松分布或負(fù)指數(shù)分布，D表示定長分布，Ek表示愛爾朗分布，G表示一般相互獨(dú)立任意分布； Y記服務(wù)時(shí)間的分布，類型同X； Z記服務(wù)臺數(shù)目，取正整數(shù)； A記系統(tǒng)的容量，表示系統(tǒng)中顧客容量限額，若系統(tǒng)中有k個(gè)等待位子(0k)，當(dāng)k=0時(shí)，說明系統(tǒng)不允許等待，即為損失制。 k=為等待制系統(tǒng)。k為有限整數(shù)時(shí)，則為混合制 ； B記顧客源的數(shù)目，可取正整數(shù)或 ，即有限與

10、無限； C記排隊(duì)服務(wù)規(guī)則，F(xiàn)CFS先到先服務(wù)，LCFS后到先服務(wù)，SIRO隨機(jī)服務(wù)，PR有優(yōu)先權(quán)的服務(wù)。,排隊(duì)過程的符號表示,7.4、排隊(duì)論與生滅過程,研究排隊(duì)系統(tǒng)的目的是通過了解系統(tǒng)運(yùn)行的狀況，對系統(tǒng)進(jìn)行調(diào)整和控制，使系統(tǒng)處于最優(yōu)運(yùn)行狀態(tài)。因此，首先需要弄清系統(tǒng)的運(yùn)行狀況。描述一個(gè)排隊(duì)系統(tǒng)運(yùn)行狀況的主要數(shù)量指標(biāo)有： Pn：系統(tǒng)中恰好有n個(gè)顧客的概率，這n個(gè)顧客包括排隊(duì)和正在被服務(wù)的顧客；在系統(tǒng)里沒有顧客的概率，即所有服務(wù)設(shè)施空閑的概率，記為P0。 Pw顧客到達(dá)系統(tǒng)時(shí)，得不到及時(shí)服務(wù)，必須排隊(duì)等待服務(wù)的概率。,7.4、排隊(duì)論與生滅過程,排隊(duì)過程的主要數(shù)量指標(biāo),Ls在系統(tǒng)里的平均顧客數(shù)，包括排隊(duì)

11、的顧客數(shù)和正在被服務(wù)的顧客數(shù)。 Lq排隊(duì)的平均長度，即排隊(duì)的平均顧客數(shù)。 Wq平均一位顧客花在排隊(duì)上的時(shí)間。 Ws平均一位顧客在系統(tǒng)里的平均逗留時(shí)間，它包括排隊(duì)時(shí)間和被服務(wù)的時(shí)間。 Little公式，L=W。為單位時(shí)間內(nèi)到達(dá)的顧客數(shù)。,7.4、排隊(duì)論與生滅過程,排隊(duì)過程的主要數(shù)量指標(biāo),生滅過程 生滅過程是一類非常簡單具有廣泛應(yīng)用的一類隨機(jī)過程，很多排隊(duì) 模型中都假設(shè)其狀態(tài)過程為生滅過程；這樣的排隊(duì)子系統(tǒng)如：M/M/C和 M/M/C/R，我們也可稱之為生滅過程的排隊(duì)系統(tǒng)。在這樣的排隊(duì)系統(tǒng)中， 一個(gè)新顧客的到達(dá)看作“生”，一個(gè)顧客服務(wù)完之后離開系統(tǒng)看作是 “死”，設(shè)N(t)的任意時(shí)刻t排隊(duì)系統(tǒng)的狀

12、態(tài)（即排隊(duì)子系統(tǒng)中的總顧客 數(shù)），則對M/M/C/K系統(tǒng)N(t)具有有限個(gè)狀態(tài)0，1，,k,對M/M/C來說 N(t)具有可列個(gè)狀態(tài)0，1，2。,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,若排隊(duì)系統(tǒng)具有下列性質(zhì): (1) 顧客到達(dá)為泊松流，時(shí)間間隔服從參 數(shù)為n的負(fù)指數(shù)分布; (2) 顧客服務(wù)時(shí)間服從參數(shù)為 n的負(fù)指 數(shù)分布; 則排隊(duì)系統(tǒng)的隨機(jī)過程N(yùn)(t),t=0具有馬 爾可夫性質(zhì), 為一個(gè)生滅過程.,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,設(shè)某系統(tǒng)具有狀態(tài)集S=0,1,2,或S=0,1,2,k, N(t)表示系統(tǒng)在時(shí)刻 t (t=0) 的狀態(tài)。若在N(t)=n的條件下,隨機(jī)過程N(yùn)(

13、t),t=0滿足以下條件: (1) N(t+t)轉(zhuǎn)移到“n+1”的概率為Pn,n+1(t )=nt ; (2) N(t+t)轉(zhuǎn)移到“n-1”的概率為Pn,n-1(t )= nt ); (3) N(t+t)轉(zhuǎn)移到其他狀態(tài)“S-n+1,n-1”的概 率為o(t )(高階無窮小) ; 則稱隨機(jī)過程N(yùn)(t),t=0為生滅過程。,Definition 7.2(Birth-deathprocess),7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,(1) 在無窮小t內(nèi),系統(tǒng)或生長1個(gè);或滅亡1個(gè);或既 不生長又不滅亡的概率: 1- n(t ) -n(t ); (2)系統(tǒng)生長一個(gè)的概率n(t )與t有關(guān)，而與

14、t無 關(guān); 與系統(tǒng)當(dāng)前狀態(tài)n有關(guān)，而與以前的狀態(tài)無關(guān)； (3)系統(tǒng)滅亡一個(gè)的概率n(t )與t有關(guān)，而與t無 關(guān); 與系統(tǒng)當(dāng)前狀態(tài)n有關(guān)，而與以前的狀態(tài)無關(guān)；,馬爾可夫性,生滅過程狀態(tài)變化的性質(zhì),7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,生滅過程的狀態(tài)平衡方程,狀態(tài),輸入率=輸出率,0,1,2,n-1,n,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,生滅過程的跳躍強(qiáng)度矩陣,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,生滅過程的狀態(tài)轉(zhuǎn)移圖,無限狀態(tài)的： m個(gè)狀態(tài)的：,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,排隊(duì)系統(tǒng)狀態(tài)轉(zhuǎn)移圖,生滅過程的穩(wěn)態(tài)概率,一般來說，得到N(t)的分布Pn(t

15、)=PN(t)=n,n=0,1,2,是比較困難的，因此通常是求當(dāng)系統(tǒng)運(yùn)行一段時(shí)間達(dá)到平穩(wěn)狀態(tài)后的狀態(tài)分布，記為Pn。 當(dāng)系統(tǒng)運(yùn)行長時(shí)間達(dá)到平穩(wěn)狀態(tài)后，對于任一個(gè)狀態(tài)n，單位時(shí)間內(nèi)進(jìn)入該狀態(tài)的平均次數(shù)和單位時(shí)間離開該狀態(tài)的平均次數(shù)應(yīng)該相等，這就是系統(tǒng)的統(tǒng)計(jì)平衡下的“流入=流出”原理。,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,2. 生滅過程穩(wěn)態(tài)方程,輸入（出）率=某一穩(wěn)態(tài)概率平均轉(zhuǎn)換率,2. 生滅過程穩(wěn)態(tài)方程,方程為：,由此可求得生滅過程的平穩(wěn)狀態(tài)分布：,由于,即有,即有,即有,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,即當(dāng),時(shí)，此生滅過程存在平穩(wěn)狀態(tài)分布：,7.4、排隊(duì)論與生滅過程-（

16、生滅過程排隊(duì)論）,基于生滅過程的排隊(duì)系統(tǒng)的六個(gè)模型,3. M/M/1/m/FCFS （單服務(wù)臺無限隊(duì)列）,到達(dá)過程/服務(wù)時(shí)間/系統(tǒng)容量/顧客源/排隊(duì)規(guī)則,M/M/1/FCFS（單服務(wù)臺無限隊(duì)列）,2. M/M/1/N/FCFS （單服務(wù)臺無限隊(duì)列）,5. M/M/s/N/FCFS,4. M/M/s/FCFS,6. M/M/s/m/FCFS,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,設(shè)單位時(shí)間到達(dá)系統(tǒng)的顧客數(shù)為 ，單位時(shí)間被服務(wù)完的顧客數(shù)為。由于是單服務(wù)臺，且顧客源無限，因此，在各種狀態(tài)的情況下，系統(tǒng)的“出生率”為，系統(tǒng)的“死亡率”為。系統(tǒng)在穩(wěn)態(tài)情況下的狀態(tài)轉(zhuǎn)移如圖9-6所示,圖9-6,7.

17、4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,根據(jù)以上狀態(tài)轉(zhuǎn)移圖，可以得出如下平衡方程,系統(tǒng)狀態(tài)概率Pn(t)的計(jì)算,狀態(tài),輸入率=輸出率,0,1,2,n-1,n,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,根據(jù)平衡方程，可遞推得到各狀態(tài)概率為：,系統(tǒng)狀態(tài)概率Pn(t)的計(jì)算,狀態(tài),概率,0,1,2,n-1,n,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,上面兩式做差，得,表示平均到達(dá)率與平均服務(wù)率之比，稱為服務(wù)強(qiáng)度,系統(tǒng)狀態(tài)概率Pn(t)的計(jì)算,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,根據(jù)平衡方程，可遞推得到各狀態(tài)概率為：,系統(tǒng)狀態(tài)概率Pn(t)的計(jì)算,狀態(tài),概率,0,1,2,n-1,

18、n,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,高速公路收費(fèi)處設(shè)有一個(gè)收費(fèi)通道，汽車到達(dá)服從泊松分布，平均到達(dá)速率為150輛小時(shí)，收費(fèi)時(shí)間服從負(fù)指數(shù)分布，平均收費(fèi)時(shí)間為15秒輛。求,(4)系統(tǒng)中的平均顧客數(shù)（系統(tǒng)中顧客數(shù)的期望值）Ls,(5)隊(duì)列中的平均顧客數(shù)（等待）,(6)服務(wù)中的平均顧客數(shù),(7)顧客在系統(tǒng)中的平均逗留時(shí)間W,(8)顧客在隊(duì)列中的平均逗留時(shí)間 Wq,(1)收費(fèi)處空閑的概率；,(2)收費(fèi)處忙的概率；,(3)系統(tǒng)中分別有1，2，3輛車的概率,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,根據(jù)題意, =150輛/小時(shí), 1/=15秒=1/240（小時(shí)/輛）,即240（輛/小時(shí)）

19、 /=150/240=5/8，,高速公路收費(fèi)處設(shè)有一個(gè)收費(fèi)通道，汽車到達(dá)服從泊松分布，平均到達(dá)速率為150輛小時(shí)，收費(fèi)時(shí)間服從負(fù)指數(shù)分布，平均收費(fèi)時(shí)間為15秒輛。求,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,高速公路收費(fèi)處設(shè)有一個(gè)收費(fèi)通道，汽車到達(dá)服從泊松分布，平均到達(dá)速率為150輛小時(shí)，收費(fèi)時(shí)間服從負(fù)指數(shù)分布，平均收費(fèi)時(shí)間為15秒輛。求,(1)系統(tǒng)空閑的概率為：,P0=1=1(5/8)=3/8=0.375,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,(2)系統(tǒng)忙的概率為：,1-P0=5/8=0.625,高速公路收費(fèi)處設(shè)有一個(gè)收費(fèi)通道，汽車到達(dá)服從泊松分布，平均到達(dá)速率為150輛小時(shí)，收

20、費(fèi)時(shí)間服從負(fù)指數(shù)分布，平均收費(fèi)時(shí)間為15秒輛。求,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,(3)系統(tǒng)中有1輛車的概率為：,高速公路收費(fèi)處設(shè)有一個(gè)收費(fèi)通道，汽車到達(dá)服從泊松分布，平均到達(dá)速率為150輛小時(shí)，收費(fèi)時(shí)間服從負(fù)指數(shù)分布，平均收費(fèi)時(shí)間為15秒輛。求,P1=(1)=0.6250.375=0.234,P2= 2(1)= 0.2340.625=0.146,P3=3(1)=0.1460.625=0.091,系統(tǒng)中有3輛車的概率為：,系統(tǒng)中有2輛車的概率為：,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,(4)系統(tǒng)中的平均顧客數(shù)（系統(tǒng)中顧客數(shù)的期望值）Ls,即隊(duì)長為系統(tǒng)中顧客數(shù)的期望值（系統(tǒng)

21、中各種狀態(tài)的加權(quán)平均值）,高速公路收費(fèi)處設(shè)有一個(gè)收費(fèi)通道，汽車到達(dá)服從泊松分布，平均到達(dá)速率為150輛小時(shí)，收費(fèi)時(shí)間服從負(fù)指數(shù)分布，平均收費(fèi)時(shí)間為15秒輛。求,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,(5)隊(duì)列中的平均顧客數(shù)（等待）,高速公路收費(fèi)處設(shè)有一個(gè)收費(fèi)通道，汽車到達(dá)服從泊松分布，平均到達(dá)速率為150輛小時(shí)，收費(fèi)時(shí)間服從負(fù)指數(shù)分布，平均收費(fèi)時(shí)間為15秒輛。求,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,57,(6)服務(wù)中的平均顧客數(shù),高速公路收費(fèi)處設(shè)有一個(gè)收費(fèi)通道，汽車到達(dá)服從泊松分布，平均到達(dá)速率為150輛小時(shí)，收費(fèi)時(shí)間服從負(fù)指數(shù)分布，平均收費(fèi)時(shí)間為15秒輛。求,7.4、排隊(duì)論

22、與生滅過程-（生滅過程排隊(duì)論）,(7)顧客在系統(tǒng)中的平均逗留時(shí)間W,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,高速公路收費(fèi)處設(shè)有一個(gè)收費(fèi)通道，汽車到達(dá)服從泊松分布，平均到達(dá)速率為150輛小時(shí)，收費(fèi)時(shí)間服從負(fù)指數(shù)分布，平均收費(fèi)時(shí)間為15秒輛。求,(8)顧客在隊(duì)列中的平均逗留時(shí)間 Wq,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,高速公路收費(fèi)處設(shè)有一個(gè)收費(fèi)通道，汽車到達(dá)服從泊松分布，平均到達(dá)速率為150輛小時(shí)，收費(fèi)時(shí)間服從負(fù)指數(shù)分布，平均收費(fèi)時(shí)間為15秒輛。求,60,(6)服務(wù)中的平均顧客數(shù) Lf=0P0+1（P1+ P2+ P3+）=1-P0=1-（1-）= =/,Little公式:,7.

23、4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,61,(6)服務(wù)中的平均顧客數(shù) Lf=0P0+1（P1+ P2+ P3+）=1-P0=1-（1-）= =/,Little公式:,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,【例9.2】輕軌進(jìn)站口售票處設(shè)有一個(gè)售票窗口，乘客到達(dá)服從泊松分布，平均到達(dá)速率為200人/小時(shí)，售票時(shí)間服從負(fù)指數(shù)分布，平均售票時(shí)間為15秒/人。求L、Lq、W和Wq。 【解】根據(jù)題意，=200人/小時(shí)，=240人/小時(shí)，=5/6。,如果系統(tǒng)的最大容量為N，對于單服務(wù)臺的情形，排隊(duì)等待的顧客最多為N-1，在某一時(shí)刻一顧客到達(dá)時(shí)，如系統(tǒng)中已有N個(gè)顧客，那么這個(gè)顧客就被拒絕進(jìn)入系統(tǒng)。

24、系統(tǒng)狀態(tài)轉(zhuǎn)移如圖9-7,圖97,根據(jù)平衡方程，可遞推得到各狀態(tài)概率為：,系統(tǒng)狀態(tài)概率Pn(t)的計(jì)算,狀態(tài),概率,0,1,2,n,N,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,根據(jù)平衡方程，可遞推得到各狀態(tài)概率為：,系統(tǒng)狀態(tài)概率Pn(t)的計(jì)算,狀態(tài),概率,0,1,2,n,N,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,根據(jù)平衡方程，可遞推得到各狀態(tài)概率為：,系統(tǒng)狀態(tài)概率Pn(t)的計(jì)算,狀態(tài),概率,0,1,2,n,N,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,系統(tǒng)中的平均顧客數(shù)L,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,隊(duì)列中的平均顧客數(shù)Lq,7.4、排隊(duì)論與生滅過程-（生滅

25、過程排隊(duì)論）,隊(duì)列中的平均顧客數(shù)Lq,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,在我們的有限容量模型中，每單位時(shí)間平均有名到達(dá)者到達(dá)，但是這些到達(dá)者中有PN的概率不能進(jìn)入系統(tǒng)，因?yàn)榇藭r(shí)系統(tǒng)已滿，所以有 PN名到達(dá)者無法進(jìn)入系統(tǒng)而離開。,e 稱為有效到達(dá)率，即單位時(shí)間內(nèi)到達(dá)并能進(jìn)入隊(duì)列的平均顧客數(shù)。e 稱為有效服務(wù)強(qiáng)度 。對于有限容量系統(tǒng)，即使，系統(tǒng)的有限容量也會阻止系統(tǒng)中的人數(shù)爆炸，穩(wěn)態(tài)存在。,顧客在隊(duì)列中的平均逗留時(shí)間,顧客在系統(tǒng)中的平均逗留時(shí)間W,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,咨詢中心有一位咨詢工作人員，每次只能咨詢一人，另外有4個(gè)座位供前來咨詢的人等候。某人到來發(fā)現(xiàn)沒

26、有座位，就不再等待而離去。前來咨詢者到達(dá)服從泊松流，到達(dá)的平均速率為4人/小時(shí)，咨詢?nèi)藛T的平均咨詢時(shí)間為10分鐘/人。咨詢時(shí)間服從負(fù)指數(shù)分布。求： (1)咨詢者到達(dá)不用等待就可咨詢的概率 (2)咨詢中心的平均人數(shù)以及等待咨詢的平均人數(shù) (3)咨詢者來咨詢中心一次平均花費(fèi)的時(shí)間以及平均等待的時(shí)間 (4)咨詢者到達(dá)后因客滿而離去的概率 (5)增加一個(gè)座位可以減少的顧客損失率,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,【解】N=4+1=5，=4人/小時(shí)，=6人/小時(shí)，=2/3,咨詢中心有一位咨詢工作人員，每次只能咨詢一人，另外有4個(gè)座位供前來咨詢的人等候。某人到來發(fā)現(xiàn)沒有座位，就不再等待而離去。

27、前來咨詢者到達(dá)服從泊松流，到達(dá)的平均速率為4人/小時(shí)，咨詢?nèi)藛T的平均咨詢時(shí)間為10分鐘/人。咨詢時(shí)間服從負(fù)指數(shù)分布。求：,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,(1)咨詢者到達(dá)不用等待就可咨詢的概率,咨詢中心有一位咨詢工作人員，每次只能咨詢一人，另外有4個(gè)座位供前來咨詢的人等候。某人到來發(fā)現(xiàn)沒有座位，就不再等待而離去。前來咨詢者到達(dá)服從泊松流，到達(dá)的平均速率為4人/小時(shí)，咨詢?nèi)藛T的平均咨詢時(shí)間為10分鐘/人。咨詢時(shí)間服從負(fù)指數(shù)分布。求：,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,(2)咨詢中心的平均人數(shù)以及等待咨詢的平均人數(shù),咨詢中心有一位咨詢工作人員，每次只能咨詢一人，另外有4個(gè)

28、座位供前來咨詢的人等候。某人到來發(fā)現(xiàn)沒有座位，就不再等待而離去。前來咨詢者到達(dá)服從泊松流，到達(dá)的平均速率為4人/小時(shí)，咨詢?nèi)藛T的平均咨詢時(shí)間為10分鐘/人。咨詢時(shí)間服從負(fù)指數(shù)分布。求：,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,(3)咨詢者來咨詢中心一次平均花費(fèi)的時(shí)間以及平均等待的時(shí)間,咨詢中心有一位咨詢工作人員，每次只能咨詢一人，另外有4個(gè)座位供前來咨詢的人等候。某人到來發(fā)現(xiàn)沒有座位，就不再等待而離去。前來咨詢者到達(dá)服從泊松流，到達(dá)的平均速率為4人/小時(shí)，咨詢?nèi)藛T的平均咨詢時(shí)間為10分鐘/人。咨詢時(shí)間服從負(fù)指數(shù)分布。求：,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,(4)咨詢者到達(dá)后因

29、客滿而離去的概率,當(dāng)N=6時(shí),咨詢中心有一位咨詢工作人員，每次只能咨詢一人，另外有4個(gè)座位供前來咨詢的人等候。某人到來發(fā)現(xiàn)沒有座位，就不再等待而離去。前來咨詢者到達(dá)服從泊松流，到達(dá)的平均速率為4人/小時(shí)，咨詢?nèi)藛T的平均咨詢時(shí)間為10分鐘/人。咨詢時(shí)間服從負(fù)指數(shù)分布。求：,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,(5)增加一個(gè)座位可以減少的顧客損失率,即增加一個(gè)座位可以減少顧客損失率1.6%,有限顧客源排隊(duì)系統(tǒng)模型,在無限源顧客系統(tǒng)中，顧客的平均到達(dá)速率是整個(gè)顧客源的性質(zhì)，與單獨(dú)的顧客無關(guān)。即使有顧客反復(fù)接受服務(wù)，對于本來就是無窮大的顧客源影響不大。,7.4、排隊(duì)論與生滅過程-（生滅過程排

30、隊(duì)論）,在有限源系統(tǒng)中，由于一個(gè)顧客要反復(fù)接受服務(wù)，因此有必要假定每一個(gè)顧客在單位時(shí)間內(nèi)需要接受服務(wù)的平均次數(shù)是相同的，設(shè)為。這樣，有限源系統(tǒng)顧客的平均到達(dá)速率就與顧客源中的顧客數(shù)有關(guān)。,設(shè)顧客總數(shù)為m。當(dāng)顧客需要服務(wù)時(shí)，就進(jìn)入隊(duì)列等待；服務(wù)完畢后，重新回到顧客源中，如此循環(huán)往復(fù)。由于顧客源的數(shù)量有限，因此隊(duì)列的長度也是有限的，并且隊(duì)列的長度必定小于顧客源總數(shù) 。,78,以機(jī)器維修問題為例，設(shè)機(jī)器總數(shù)為m臺，每臺機(jī)器在單位時(shí)間內(nèi)發(fā)生故障的平均次數(shù)為，已經(jīng)發(fā)生故障正在等待修理及正在接受修理的機(jī)器數(shù)為n。試想，由于機(jī)器需要反復(fù)修理，所以可以把單位時(shí)間內(nèi)需要修理的機(jī)器總數(shù)看成是一共m 臺（一臺只修理

31、一次），其中有n 臺在系統(tǒng)中，所以單位時(shí)間內(nèi)將要到達(dá)的機(jī)器數(shù)（剩余的）可以看成（m - n ）臺。,有限源系統(tǒng)顧客的平均到達(dá)速率：為每個(gè)顧客在單位時(shí)間內(nèi)到達(dá)的平均次數(shù)， n為在系統(tǒng)中的顧客數(shù)。,有限顧客源排隊(duì)系統(tǒng)模型,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,有限顧客源排隊(duì)系統(tǒng)模型,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,0,1,2,n-1,n,n+1,m-1,m,圖9-8 有限顧客源模型狀態(tài)轉(zhuǎn)移圖,狀態(tài)轉(zhuǎn)移圖如圖9-8,由圖9-8得到系統(tǒng)穩(wěn)態(tài)概率平衡方程組,系統(tǒng)狀態(tài)概率的計(jì)算,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,用遞推方法解該方程組，得到,不要求=/1,系統(tǒng)中的平均顧客數(shù)

32、L,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,隊(duì)列中的平均顧客數(shù)Lq,顧客在隊(duì)列中的平均逗留時(shí)間,顧客在系統(tǒng)中的平均逗留時(shí)間W,在機(jī)器維修問題中，L是待檢修及正在檢修的平均機(jī)器數(shù)，而,表示正常運(yùn)行的平均機(jī)器數(shù)。,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,某車間有5臺機(jī)器，每臺機(jī)器的連續(xù)運(yùn)轉(zhuǎn)時(shí)間服從負(fù)指數(shù)分布，一天（8小時(shí)）平均連續(xù)運(yùn)行時(shí)間120分鐘。有一個(gè)修理工，每次修理時(shí)間服從負(fù)指數(shù)分布，平均每次96分鐘。求： (1)修理工忙的概率(記為Pb)； (2)五臺機(jī)器都出故障的概率； (3)出故障的平均臺數(shù)； (4)平均停工時(shí)間； (5)平均等待修理時(shí)間； (6)評價(jià)這個(gè)系統(tǒng)的運(yùn)行情況,7

33、.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,【解】一天為一個(gè)單位時(shí)間。認(rèn)為一天內(nèi)來修理的機(jī)器數(shù)平均為4臺，修理工一天平均修理機(jī)器數(shù)為5臺。m=5，=4，=5，=0.8,某車間有5臺機(jī)器，每臺機(jī)器的連續(xù)運(yùn)轉(zhuǎn)時(shí)間服從負(fù)指數(shù)分布，一天（8小時(shí)）平均連續(xù)運(yùn)行時(shí)間120分鐘。有一個(gè)修理工，每次修理時(shí)間服從負(fù)指數(shù)分布，平均每次96分鐘。求：,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,(1)修理工忙的概率(記為Pb)；,某車間有5臺機(jī)器，每臺機(jī)器的連續(xù)運(yùn)轉(zhuǎn)時(shí)間服從負(fù)指數(shù)分布，一天（8小時(shí)）平均連續(xù)運(yùn)行時(shí)間120分鐘。有一個(gè)修理工，每次修理時(shí)間服從負(fù)指數(shù)分布，平均每次96分鐘。求：,7.4、排隊(duì)論與生滅過

34、程-（生滅過程排隊(duì)論）,(2)五臺機(jī)器都出故障的概率；,某車間有5臺機(jī)器，每臺機(jī)器的連續(xù)運(yùn)轉(zhuǎn)時(shí)間服從負(fù)指數(shù)分布，一天（8小時(shí)）平均連續(xù)運(yùn)行時(shí)間120分鐘。有一個(gè)修理工，每次修理時(shí)間服從負(fù)指數(shù)分布，平均每次96分鐘。求：,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,(3)出故障的平均臺數(shù)；,某車間有5臺機(jī)器，每臺機(jī)器的連續(xù)運(yùn)轉(zhuǎn)時(shí)間服從負(fù)指數(shù)分布，一天（8小時(shí)）平均連續(xù)運(yùn)行時(shí)間120分鐘。有一個(gè)修理工，每次修理時(shí)間服從負(fù)指數(shù)分布，平均每次96分鐘。求：,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,(4)平均停工時(shí)間；,某車間有5臺機(jī)器，每臺機(jī)器的連續(xù)運(yùn)轉(zhuǎn)時(shí)間服從負(fù)指數(shù)分布，一天（8小時(shí)）平均連

35、續(xù)運(yùn)行時(shí)間120分鐘。有一個(gè)修理工，每次修理時(shí)間服從負(fù)指數(shù)分布，平均每次96分鐘。求：,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,(5)平均等待修理時(shí)間；,由計(jì)算結(jié)果看出，系統(tǒng)的修理工幾乎沒有空閑時(shí)間，機(jī)器的停工時(shí)間是平均運(yùn)行時(shí)間的三倍，系統(tǒng)的服務(wù)效率很低,某車間有5臺機(jī)器，每臺機(jī)器的連續(xù)運(yùn)轉(zhuǎn)時(shí)間服從負(fù)指數(shù)分布，一天（8小時(shí)）平均連續(xù)運(yùn)行時(shí)間120分鐘。有一個(gè)修理工，每次修理時(shí)間服從負(fù)指數(shù)分布，平均每次96分鐘。求：,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,(6)評價(jià)這個(gè)系統(tǒng)的運(yùn)行情況,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,這個(gè)系統(tǒng)的特點(diǎn)是，系統(tǒng)的服務(wù)速率與系統(tǒng)中的顧客數(shù)有關(guān)

36、。當(dāng)系統(tǒng)中的顧客數(shù)k不大于服務(wù)臺個(gè)數(shù)，即1ks時(shí)，系統(tǒng)中的顧客全部在服務(wù)臺中，這時(shí)系統(tǒng)的服務(wù)速率為k。當(dāng)系統(tǒng)中的顧客數(shù)ks時(shí)，因服務(wù)臺有限，系統(tǒng)的服務(wù)速率達(dá)最大為s。,規(guī)定各服務(wù)臺工作相互獨(dú)立且服務(wù)速率相同,系統(tǒng)的平均服務(wù)速率為 s,令,0,1,2,s-1,s,s+1,n-1,n,圖9-9 基本模型狀態(tài)轉(zhuǎn)移圖,系統(tǒng)的狀態(tài)轉(zhuǎn)移圖9-9。,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,穩(wěn)態(tài)概率方程,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,系統(tǒng)狀態(tài)概率的計(jì)算,系統(tǒng)中的平均顧客數(shù)L,隊(duì)列中的平均顧客數(shù)Lq,顧客在隊(duì)列中的平均逗留時(shí)間,顧客在系統(tǒng)中的平均逗留時(shí)間W,7.4、排隊(duì)論與生滅過程-（生滅

37、過程排隊(duì)論）,顧客需要等待 (系統(tǒng)已有s個(gè)顧客)的概率,銀行辦理個(gè)人儲蓄業(yè)務(wù)有三個(gè)窗口，顧客到達(dá)服從泊松流，到達(dá)速率為0.9人分，辦理業(yè)務(wù)時(shí)間服從負(fù)指數(shù)分布，每個(gè)窗口的平均服務(wù)速率為0.4人分。顧客到達(dá)后取得一個(gè)排隊(duì)號，依次由空閑窗口按號碼順序辦理儲蓄業(yè)務(wù)。求： (1)所有窗口都空閑的概率； (2)平均隊(duì)長； (3)平均等待時(shí)間及逗留時(shí)間； (4)顧客到達(dá)后必須等待的概率。,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,(1)所有窗口都空閑的概率；即求P0,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,銀行辦理個(gè)人儲蓄業(yè)務(wù)有三個(gè)窗口，顧客到達(dá)服從泊松流，到達(dá)速率為0.9人分，辦理業(yè)務(wù)時(shí)間服從負(fù)

38、指數(shù)分布，每個(gè)窗口的平均服務(wù)速率為0.4人分。顧客到達(dá)后取得一個(gè)排隊(duì)號，依次由空閑窗口按號碼順序辦理儲蓄業(yè)務(wù)。求：,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,銀行辦理個(gè)人儲蓄業(yè)務(wù)有三個(gè)窗口，顧客到達(dá)服從泊松流，到達(dá)速率為0.9人分，辦理業(yè)務(wù)時(shí)間服從負(fù)指數(shù)分布，每個(gè)窗口的平均服務(wù)速率為0.4人分。顧客到達(dá)后取得一個(gè)排隊(duì)號，依次由空閑窗口按號碼順序辦理儲蓄業(yè)務(wù)。求：,(2)平均隊(duì)長；先求Lq ,再求L,(3)平均等待時(shí)間和平均逗留時(shí)間，即求Wq和W的值,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,銀行辦理個(gè)人儲蓄業(yè)務(wù)有三個(gè)窗口，顧客到達(dá)服從泊松流，到達(dá)速率為0.9人分，辦理業(yè)務(wù)時(shí)間服從負(fù)指數(shù)分布，每個(gè)窗口的平均服務(wù)速率為0.4人分。顧客到達(dá)后取得一個(gè)排隊(duì)號，依次由空閑窗口按號碼順序辦理儲蓄業(yè)務(wù)。求：,(4)顧客到達(dá)后必須等待，即n3,7.4、排隊(duì)論與生滅過程-（生滅過程排隊(duì)論）,銀行辦理個(gè)人儲蓄業(yè)務(wù)有三個(gè)窗口，顧客到達(dá)服從泊松流，到達(dá)速率為0.9人分，辦理業(yè)務(wù)時(shí)間服從負(fù)指數(shù)分布，每個(gè)窗口的平均服務(wù)速率為0.4人分。顧客到達(dá)后取得一個(gè)排隊(duì)號，依次由空閑窗口按號碼順序辦理儲蓄業(yè)務(wù)。求：,7.4、排隊(duì)論與生