我的運(yùn)籌課件排隊(duì)論

我的運(yùn)籌課件排隊(duì)論第一頁，共二十一頁，2022年，8月28日

一般的排隊(duì)過程為：顧客由顧客源出發(fā)，到達(dá)服務(wù)機(jī)構(gòu)（服務(wù)臺、服務(wù)員）前，按排隊(duì)規(guī)則排隊(duì)等待接受服務(wù)，服務(wù)機(jī)構(gòu)按服務(wù)規(guī)則給顧客服務(wù)，顧客接受完服務(wù)后就離開。排隊(duì)過程的一般過程可用下圖表示。我們所說的排隊(duì)系統(tǒng)就是指圖中虛線所包括的部分。

在現(xiàn)實(shí)生活中的排隊(duì)現(xiàn)象是多種多樣的，對上面所說的“顧客”和“服務(wù)員”要作廣泛的理解。它們可以是人，也可以是某種物質(zhì)或設(shè)備。排隊(duì)可以是有形的，也可以是無形的。6.1基本概念

6.1.1排隊(duì)過程的一般表示第二頁，共二十一頁，2022年，8月28日

6.1.2排隊(duì)系統(tǒng)的組成和特征

盡管排隊(duì)系統(tǒng)是多種多樣的，但從決定排隊(duì)系統(tǒng)進(jìn)程的因素來看，它有三個基本的組成部分，這就是輸入過程、排隊(duì)規(guī)則及服務(wù)機(jī)構(gòu)。1)輸入過程：描述顧客來源以及顧客到達(dá)排隊(duì)系統(tǒng)的規(guī)律。包括：顧客源中顧客的數(shù)量是有限還是無限；顧客到達(dá)的方式是單個到達(dá)還是成批到達(dá)；顧客相繼到達(dá)的間隔時間分布是確定型的還是隨機(jī)型的，分布參數(shù)是什么，是否獨(dú)立，是否平穩(wěn)。第三頁，共二十一頁，2022年，8月28日

2)排隊(duì)規(guī)則：描述顧客排隊(duì)等待的隊(duì)列和接受服務(wù)的次序。包括：即時制還是等待制；等待制下隊(duì)列的情況（是單列還是多列，顧客能不能中途退出，多列時各列間的顧客能不能相互轉(zhuǎn)移）；等待制下顧客接受服務(wù)的次序（先到先服務(wù)，后到先服務(wù)，隨機(jī)服務(wù)，有優(yōu)先權(quán)的服務(wù)）。3)服務(wù)機(jī)構(gòu)：描述服務(wù)臺(員)的機(jī)構(gòu)形式和工作情況。包括：服務(wù)臺（員）的數(shù)目和排列情況；服務(wù)臺（員）的服務(wù)方式；服務(wù)時間是確定型的還是隨機(jī)型的，分布參數(shù)是什么，是否獨(dú)立，是否平穩(wěn)。第四頁，共二十一頁，2022年，8月28日

6.1.3排隊(duì)模型的分類

D.G.Kendall在1953年提出了一個分類方法，按照系統(tǒng)的三個最主要的、影響最大的三個特征要素進(jìn)行分類，它們是：顧客相繼到達(dá)的間隔時間分布、服務(wù)時間的分布、并列的服務(wù)臺個數(shù)。按照這三個特征要素分類的排隊(duì)系統(tǒng)，用符號（稱為Kendall記號）表示為X/Y/Z其中X處填寫顧客相繼到達(dá)的間隔時間分布，Y處填寫服務(wù)時間的分布，Z處填寫并列的服務(wù)臺個數(shù)。例如M/M/1，表示顧客相繼到達(dá)的間隔時間為負(fù)指數(shù)分布、服務(wù)時間為負(fù)指數(shù)分布、單服務(wù)臺的模型。第五頁，共二十一頁，2022年，8月28日

后來，在1971年關(guān)于排隊(duì)論符號標(biāo)準(zhǔn)化的會議上決定，將Kendall符號擴(kuò)充為：X/Y/Z/A/B/C其中前三項(xiàng)意義不變。A處填寫系統(tǒng)容量限制;

B處填寫顧客源中的顧客數(shù)目;C處填寫服務(wù)規(guī)則（如先到先服務(wù)FCFS，后到先服務(wù)LCFS）。約定，如略去后三項(xiàng)，即指X/Y/Z/∞/∞/FCFS的情形。后面我們只討論先到先服務(wù)FCFS的情形，所以略去第六項(xiàng)。第六頁，共二十一頁，2022年，8月28日

6.1.4排隊(duì)系統(tǒng)的求解

對于一個排隊(duì)系統(tǒng)，運(yùn)行狀況的好壞既涉及到顧客的利益，又涉及到服務(wù)機(jī)構(gòu)的利益，還有社會效果好壞的問題。為了研究排隊(duì)系統(tǒng)運(yùn)行的效率、估計服務(wù)質(zhì)量、研究設(shè)計改進(jìn)措施，必須確定一些基本指標(biāo)，用以判斷系統(tǒng)運(yùn)行狀況的優(yōu)劣。下面介紹幾種常用的指標(biāo)。1)隊(duì)長：把系統(tǒng)中的顧客數(shù)稱為隊(duì)長，它的期望值記作Ls。而把系統(tǒng)中排隊(duì)等待服務(wù)的顧客數(shù)稱為排隊(duì)長（隊(duì)列長），它的期望值記作Lq。顯然有

隊(duì)長＝排隊(duì)長＋正被服務(wù)的顧客數(shù)。第七頁，共二十一頁，2022年，8月28日

2)逗留時間：一個顧客從到達(dá)排隊(duì)系統(tǒng)到服務(wù)完畢離去的總停留時間稱為逗留時間，它的期望值記作Ws。

一個顧客在系統(tǒng)中排隊(duì)等待的時間稱為等待時間，它的期望值記作Wq。顯然有

逗留時間＝等待時間＋服務(wù)時間。3)瞬態(tài)和穩(wěn)態(tài)把系統(tǒng)中的顧客數(shù)稱為系統(tǒng)的狀態(tài)?？紤]在t時刻系統(tǒng)的狀態(tài)為n的概率，它是隨時刻t而變化的，用Pn(t)表示，稱為系統(tǒng)的瞬態(tài)。求瞬態(tài)解是很不容易的，一般即使求出也很難利用，因此我們常用它的極限limPn(t)＝Pnt→∞稱為穩(wěn)態(tài)或稱統(tǒng)計平衡狀態(tài)的解。第八頁，共二十一頁，2022年，8月28日6.2幾個主要概率分布

6.2.1經(jīng)驗(yàn)分布

在處理實(shí)際排隊(duì)系統(tǒng)時，需要把有關(guān)的原始資料進(jìn)行統(tǒng)計，確定顧客到達(dá)間隔和服務(wù)時間的經(jīng)驗(yàn)分布，然后按照統(tǒng)計學(xué)的方法確定符合哪種理論分布。經(jīng)驗(yàn)分布的主要指標(biāo)如下：總時間平均間隔時間=

到達(dá)顧客總數(shù)服務(wù)時間總和平均服務(wù)時間=

顧客總數(shù)

到達(dá)顧客總數(shù)平均到達(dá)率=

總時間顧客總數(shù)平均服務(wù)率=

服務(wù)時間總和第九頁，共二十一頁，2022年，8月28日

6.2.2普阿松分布

設(shè)N(t)表示在時間區(qū)間[t0,t0+t)內(nèi)到達(dá)的顧客數(shù)，是隨機(jī)變量。當(dāng)N(t)滿足下列三個條件時，我們說顧客的到達(dá)符合普阿松分布。這三個條件是：(1)平穩(wěn)性在時間區(qū)間[t0,t0+t)內(nèi)到達(dá)的顧客數(shù)N(t)，只與區(qū)間長度t有關(guān)而與時間起點(diǎn)t0無關(guān)。(2)無后效性在時間區(qū)間[t0,t0+t)內(nèi)到達(dá)的顧客數(shù)N(t)，與t0以前到達(dá)的顧客數(shù)獨(dú)立。(3)普通性在充分短的時間區(qū)間Δt內(nèi)，到達(dá)兩個或兩個以上顧客的概率極小，可以忽略不計，即

∞∑Pn(Δt)＝o(Δt)

n=2

第十頁，共二十一頁，2022年，8月28日

在上述三個條件下可以推出(λt)nPn(t)＝———e-λtn=0,1,2,……n!其中λ表示單位時間平均到達(dá)的顧客數(shù)，即為到達(dá)率。不難算出，N(t)的數(shù)學(xué)期望和方差分別是：E[N(t)]＝λtVar[N(t)]＝λt第十一頁，共二十一頁，2022年，8月28日

6.2.3負(fù)指數(shù)分布

隨機(jī)變量T的概率密度若是λe-λtt≥0fT(t)＝0t0則稱T服從負(fù)指數(shù)分布，它的分布函數(shù)是1-e-λtt≥0FT(t)＝0t0T的數(shù)學(xué)期望和方差分別為：

E[T]＝1/λ，Var(T)＝1/λ2負(fù)指數(shù)分布具有下列性質(zhì)：(1)無記憶性或馬爾柯夫性，即P{T>t+s/T>s}＝P{T>t}(2)當(dāng)顧客到達(dá)符合普阿松分布時，顧客相繼到達(dá)的間隔時間T必服從負(fù)指數(shù)分布。第十二頁，共二十一頁，2022年，8月28日

對于普阿松分布，λ表示單位時間平均到達(dá)的顧客數(shù)，所以1/λ表示顧客相繼到達(dá)的平均間隔時間，而這正和E[T]的意義相符。服務(wù)時間符合負(fù)指數(shù)分布時，設(shè)它的概率密度函數(shù)和分布函數(shù)分別為fv(t)＝μe-μt；Fv(t)＝1-e-μt(t≥0)其中μ表示單位時間能夠服務(wù)完的顧客數(shù)，為服務(wù)率；而1/μ表示一個顧客的平均服務(wù)時間，正是v的期望值。第十三頁，共二十一頁，2022年，8月28日系統(tǒng)的運(yùn)行指標(biāo)：（1）、系統(tǒng)中顧客數(shù)的期望值Ls（2）、系統(tǒng)中排隊(duì)等待顧客數(shù)的期望值Lq（3）、系統(tǒng)中顧客平均的排隊(duì)等待時間Wq（4）、系統(tǒng)中顧客的平均逗留時間Ws（5）、有效到達(dá)率e

第十四頁，共二十一頁，2022年，8月28日（6）、系統(tǒng)中Ls，Lq，Wq，Ws，e

之間的關(guān)系

Ls=npn，Lq=(n-c)pn，

Ws=Ls/e，Wq=Lq/e，

Ws=Wq+1/，

e=

npn=

npn

，

Ls=Lq+e/。

第十五頁，共二十一頁，2022年，8月28日6.3單服務(wù)臺負(fù)指數(shù)分布排隊(duì)系統(tǒng)分析

6.3.1標(biāo)準(zhǔn)M/M/1模型(M/M/1/∞/∞)

排隊(duì)系統(tǒng)的狀態(tài)n隨時間變化的過程稱為生滅過程，設(shè)平均到達(dá)率為λ,平均服務(wù)率為μ,負(fù)指數(shù)分布排隊(duì)系統(tǒng)（M/M/1/∞/∞）的生滅過程可用下面的狀態(tài)轉(zhuǎn)移圖表示：01

n-1n

n+1...

λλλλλλ

μμμμμμ

穩(wěn)態(tài)概率方程如下：

-λP0=μP1λPn-1+μPn+1=λPn+μPn設(shè)ρ=λ/μ<1，考慮到Pn=1，解得P0=1-ρPn=(1-ρ)ρn,n≥1這里的ρ稱為服務(wù)強(qiáng)度，也稱話務(wù)強(qiáng)度，它刻劃了服務(wù)機(jī)構(gòu)的繁忙程度，所以又稱服務(wù)機(jī)構(gòu)的利用率。第十六頁，共二十一頁，2022年，8月28日

系統(tǒng)的各項(xiàng)運(yùn)行指標(biāo)計算如下：平均隊(duì)長：

Ls=ΣnPn=λ(μ–λ)平均排隊(duì)長：

Lq=Σ(n–1)Pn=ρλ(μ-λ)=Ls–ρ=Ls–(1-P0)逗留時間分布函數(shù)為:F(ω)=1–e－(μ－λ)ω平均逗留時間:Ws=1(μ–λ)=Lsλ平均等待時間:Wq=Ws–1μ=Lqλ

例：第十七頁，共二十一頁，2022年，8月28日

6.3.2系統(tǒng)容量有限制的情形(M/M/1/N/∞)

當(dāng)系統(tǒng)的容量有限制(為N)時，設(shè)平均到達(dá)率為λ、平均服務(wù)率為μ，排隊(duì)系統(tǒng)（M/M/1/N/∞）的生滅過程可用下面的狀態(tài)轉(zhuǎn)移圖表示：01

n+1

λλλλλλλλ

μμμμμμμμ

系統(tǒng)處于穩(wěn)態(tài)時的概率方程如下：

λP0=μP1λPn-1+μPn+1=λPn+μPn

（n<N)μPN=λPN-1

設(shè)ρ=λ/μ≠1，考慮到P0+P1+…+PN=1,解得

P0=(1-ρ)(1-ρN+1)Pn=P0ρn,n≤N...N

N-1...n

n-1第十八頁，共二十一頁，2022年，8月28日

系統(tǒng)的各項(xiàng)運(yùn)行指標(biāo)計算如下：平均隊(duì)長：

Ls=ρ(1-ρ)–(N+1)ρN+1(1-ρN+1)平均排隊(duì)長：

Lq=Ls–(1-P0)有效到達(dá)率：

λe=λ(1-PN)=μ(1-P0)平均逗留時間:Ws=Lsλe平均等待時間:Wq=Ws–1μ=Lqλe

例:第十九頁，共二十一頁，2022年，8月28日

6.3.3顧客源為有限的情形(M/M/1/∞/m)

當(dāng)系統(tǒng)的顧客源為有限(為m)時，設(shè)各個顧客的平均到達(dá)率都為λ、服務(wù)臺的平均服務(wù)率為μ，排隊(duì)系統(tǒng)（M/M/1/∞/m）的生滅過程可用下面的狀態(tài)轉(zhuǎn)移圖表示：01

n+1

mλ(m-1)λ(m-n+1)λ(m-n)λλ