運籌學教程課件七隨機服務(wù)理論概述

1第七章隨機服務(wù)理論概述確定型只是隨機現(xiàn)象的特例27.1隨機服務(wù)系統(tǒng)系統(tǒng)的輸入與輸出是隨機變量A.k.Erlang于1909~1920年發(fā)表了一系列根據(jù)話務(wù)量計算電話機鍵配置的方法，為隨機服務(wù)理論奠定了基礎(chǔ)又稱為排隊論(QueuingTheory)或擁塞理論(CongestionTheory)3

與服務(wù)系統(tǒng)性能相關(guān)的特性服務(wù)系統(tǒng)存在來自兩個矛盾方面的要求顧客希望服務(wù)質(zhì)量好，如排隊等待時間短，損失率低系統(tǒng)運營方希望設(shè)備利用率高給用戶一個經(jīng)濟上能夠承受的滿意的質(zhì)量哪些系統(tǒng)特性會影響系統(tǒng)的性能？服務(wù)機構(gòu)的組織方式與服務(wù)方式顧客的輸入過程和服務(wù)時間分布系統(tǒng)采用的服務(wù)規(guī)則

7.1.1服務(wù)機構(gòu)的組織方式與服務(wù)方式單臺制和多臺制并聯(lián)服務(wù)串聯(lián)服務(wù)串并聯(lián)服務(wù)、網(wǎng)絡(luò)服務(wù)全利用度、部分利用度4

與服務(wù)系統(tǒng)性能相關(guān)的特性7.1.2輸入過程和服務(wù)時間顧客單個到達或成批到達顧客到達時間間隔的分布和服務(wù)時間的分布顧客源是有限的還是無限的

7.1.3服務(wù)規(guī)則損失制等待制：先到先服務(wù)(FIFO)，后到先服務(wù)，隨機服務(wù)，優(yōu)先權(quán)服務(wù)混合制逐個到達，成批服務(wù)；成批到達，逐個服務(wù)57.2

隨機服務(wù)過程單臺服務(wù)系統(tǒng)、等待制、先到先服務(wù)顧客在系統(tǒng)中的總時長：逗留時間=等待時長+服務(wù)時長等待時長與顧客到達率和服務(wù)時長有關(guān)6當服務(wù)臺連續(xù)不斷服務(wù)時，有如下關(guān)系：wi+1+i+1=wi+hiwi+hi

表示了累計的未完成的服務(wù)時長，一般地有

忙期和忙時系統(tǒng)連續(xù)不斷服務(wù)的時期稱為忙期。而系統(tǒng)最繁忙的一個小時稱為忙時。排隊系統(tǒng)的指標及其關(guān)系1）Wq

、Wd分別是顧客的平均排隊等待時間和平均逗留時間2）Lq

、Ld分別是系統(tǒng)平均排隊的顧客數(shù)和系統(tǒng)的平均顧客數(shù)3）h

是顧客的平均服務(wù)時長，是顧客的平均到達率。4）Ln

是同時接受服務(wù)的平均顧客數(shù)(即平均服務(wù)臺占用數(shù))5）Ld=

Wd=

(Wq+h)=Lq+Ln，Lq=

Wq，Ln=

h77.3服務(wù)時間與間隔時間

7.3.1概述顧客的服務(wù)時間由于多種原因具有不確定性，最好的描述方法就是概率分布；同樣顧客到達的間隔時間也具有一定的概率分布服務(wù)時間和到達間隔時間服從什么分布？可以先通過統(tǒng)計得到經(jīng)驗分布，然后再做理論假設(shè)和檢驗經(jīng)驗分布一般采用直方圖來表示，如下圖8若統(tǒng)計區(qū)間分得越細，樣本越多，則經(jīng)驗分布的輪廓越接近曲線一般服務(wù)時間和間隔時間都是非負的連續(xù)實變量，令h

代表服務(wù)時間，代表間隔時間，t

為給定的時間，則它們的概率分布函數(shù)分別表示為

F(t)=P{ht} F(t)=P{

t}它們的概率密度函數(shù)為 f(t)=F(t)，具有性質(zhì)：

f(t)0，f(t)dt=1服務(wù)時間落在區(qū)間(a,c)的概率為服務(wù)時間落在區(qū)間(t,t+t)的概率為P{t<ht+t}=f(t)t平均服務(wù)時長和平均間隔時長平均服務(wù)時長的倒數(shù)為服務(wù)率，平均間隔時長的倒數(shù)為到達率97.3.2常用的概率分布1、定長分布流水線的加工時間2、負指數(shù)分布一類最常用的分布，如上述通話時長，可靠性107.3.2常用的概率分布3、愛爾蘭分布一種代表性更廣的分布k

為整數(shù)，稱為

k

階愛爾蘭分布；當k=1

時，退化為負指數(shù)分布；k

時趨向定長分布愛爾蘭分布實際上是k

個獨立同分布的負指數(shù)分布隨機變量的和的分布，即k

個服務(wù)臺的串聯(lián)，每個服務(wù)臺的平均服務(wù)時長為1/k117.3.3負指數(shù)分布的特點負指數(shù)分布之所以常用，是因為它有很好的特性，使數(shù)學分析變得方便無記憶性。指的是不管一次服務(wù)已經(jīng)過去了多長時間，該次服務(wù)所剩的服務(wù)時間仍服從原負指數(shù)分布127.3.3負指數(shù)分布的特點一個服從負指數(shù)分布的服務(wù)，在下一瞬間結(jié)束的概率在t

內(nèi)服務(wù)終結(jié)的概率只與和t

成正比，與t0

無關(guān)；因此又稱為終結(jié)率，或離去率同理，在t

內(nèi)服務(wù)不終結(jié)的概率為1–t+o(t)n

個獨立同分布(負指數(shù))的服務(wù)臺同時被占用，在t

內(nèi)只有一個服務(wù)臺終結(jié)的概率為

在t

內(nèi)有k>1個服務(wù)臺終結(jié)的概率為o(t)，稱為普通性

137.4輸入過程即顧客到達的分布，可用相繼到達顧客的間隔時間描述，也可以用單位時間內(nèi)到達的顧客數(shù)描述間隔時間服從定長分布單位時間內(nèi)到達的顧客數(shù)服從波松分布(法國數(shù)學家Poisson,1837)間隔時間服從愛爾蘭分布一般獨立同分布

7.4.1波松輸入過程及其特點(0,t)時間內(nèi)到達

k

個顧客的個數(shù)服從波松分布，若為到達率電話呼叫的到達，商店的顧客到達，十字路口的汽車流，港口到達的船只，機場到達的飛機等147.4.1波松輸入過程及其特點(1)平穩(wěn)性：顧客到達數(shù)只與時間區(qū)間長度有關(guān)(2)無后效性：不相交的時間區(qū)間內(nèi)所到達的顧客數(shù)是獨立的(3)普通性：在t

時間內(nèi)到達一個顧客的概率為t+o(t)，到達兩個或兩個以上顧客的概率為o(t)；即兩個顧客不可能同時到達(4)有限性：在有限的時間區(qū)間內(nèi)，到達的顧客數(shù)是有限的。波松過程具有可迭加性即獨立的波松分布變量的和仍為波松分布157.4.1波松輸入過程及其特點波松過程的到達間隔時間為負指數(shù)分布令代表間隔時間，則概率P{>t}代表時間區(qū)間(0,t)內(nèi)沒有顧客來的概率；由波松分布可知

P0(t)=P{>t}=et故間隔時間的分布為P{t}=1et

7.4.2馬爾科夫鏈馬爾科夫鏈(MarkovChain)又簡稱馬氏鏈，是一種離散事件隨機過程。用數(shù)學式表達為P{Xn+1=xn+1|X1=x1,X2=x2,...,Xn=xn}=P{Xn+1=xn+1|Xn=xn}Xn+1的狀態(tài)只與Xn的狀態(tài)有關(guān)，與Xn

前的狀態(tài)無關(guān)，具有無記憶性，或無后效性，又稱馬氏性狀態(tài)轉(zhuǎn)移是一步一步發(fā)生的，一步狀態(tài)轉(zhuǎn)移概率

Pij(t)=P{Xn+1=j|Xn=i}16

例7.4.2

一售貨員出售兩種商品A和B，每日工作8小時。購買每種商品的顧客到達過程為波松分布，到達率分別為A=8人/日，B=16人/日，試求：(1)1小時內(nèi)來到顧客總數(shù)為3人的概率；(2)三個顧客全是購買B類商品的概率。解：(1)總到達率為A+B=24人/日，1小時=1/8日，故(2)3個顧客全是購買B類商品的概率為177.5生滅過程一種描述自然界生滅現(xiàn)象的數(shù)學方法，如細菌的繁殖和滅亡，人口的增減，生物種群的滅種現(xiàn)象等采用馬氏鏈令N(t)代表系統(tǒng)在時刻

t

的狀態(tài)，下一瞬間t+t

系統(tǒng)的狀態(tài)只能轉(zhuǎn)移到相鄰狀態(tài)，或維持不變，如圖所示三種轉(zhuǎn)移是不相容的，三者必居其一只有具有無記憶性和普通性的過程(分布)才適用馬氏鏈令Pj(t)=P{N(t)=j}代表系統(tǒng)在時刻t

處于狀態(tài)

j

的概率18

生滅過程的馬氏鏈根據(jù)馬氏鏈，應(yīng)用全概率公式，有狀態(tài)轉(zhuǎn)移概率方程另有兩個邊界方程19

生滅方程的推導(dǎo)過程將上述三個差分方程化為微分方程上述三個方程是動態(tài)方程，當系統(tǒng)處于穩(wěn)態(tài)時，系統(tǒng)處于統(tǒng)計平衡狀態(tài)，即狀態(tài)概率不隨時間變化，從而狀態(tài)概率導(dǎo)數(shù)為0；令上三個方程左側(cè)為0，得穩(wěn)態(tài)方程組20

生滅過程穩(wěn)態(tài)解方程(1),(2),(3)與穩(wěn)態(tài)狀態(tài)轉(zhuǎn)移圖一一對應(yīng)；遞歸解如下：21

滿足生滅過程的條件系統(tǒng)的輸入過程和服務(wù)過程具有平穩(wěn)、無記憶性和普通性服務(wù)臺是獨立的、相同的、并聯(lián)的波松輸入過程和負指數(shù)服務(wù)時長就具有這些性質(zhì)可以用馬氏鏈來描述系統(tǒng)的狀態(tài)轉(zhuǎn)移這種系統(tǒng)稱為生滅服務(wù)系統(tǒng)，一般用M/M/n

表示，又稱為標準服務(wù)系統(tǒng)；標準服務(wù)系統(tǒng)的形式很多，但都是基于生滅方程，關(guān)鍵是找出j,j

的不同表達式，將它們代入生滅方程