我的運籌課件排隊論

我的運籌課件排隊論第一頁，共二十一頁，2022年，8月28日

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

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

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

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

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

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

6.1.3排隊模型的分類

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

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

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

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

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

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

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

一個顧客在系統(tǒng)中排隊等待的時間稱為等待時間，它的期望值記作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)驗分布

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

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

顧客總數(shù)

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

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

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

6.2.2普阿松分布

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

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

n=2

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

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

6.2.3負指數(shù)分布

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

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

對于普阿松分布，λ表示單位時間平均到達的顧客數(shù)，所以1/λ表示顧客相繼到達的平均間隔時間，而這正和E[T]的意義相符。服務(wù)時間符合負指數(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)的運行指標(biāo)：（1）、系統(tǒng)中顧客數(shù)的期望值Ls（2）、系統(tǒng)中排隊等待顧客數(shù)的期望值Lq（3）、系統(tǒng)中顧客平均的排隊等待時間Wq（4）、系統(tǒng)中顧客的平均逗留時間Ws（5）、有效到達率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ù)臺負指數(shù)分布排隊系統(tǒng)分析

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

排隊系統(tǒng)的狀態(tài)n隨時間變化的過程稱為生滅過程，設(shè)平均到達率為λ,平均服務(wù)率為μ,負指數(shù)分布排隊系統(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ù)強度，也稱話務(wù)強度，它刻劃了服務(wù)機構(gòu)的繁忙程度，所以又稱服務(wù)機構(gòu)的利用率。第十六頁，共二十一頁，2022年，8月28日

系統(tǒng)的各項運行指標(biāo)計算如下：平均隊長：

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

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è)平均到達率為λ、平均服務(wù)率為μ，排隊系統(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)的各項運行指標(biāo)計算如下：平均隊長：

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

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

λ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è)各個顧客的平均到達率都為λ、服務(wù)臺的平均服務(wù)率為μ，排隊系統(tǒng)（M/M/1/∞/m）的生滅過程可用下面的狀態(tài)轉(zhuǎn)移圖表示：01

n+1

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