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

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

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

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

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

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

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

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

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

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

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

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

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

Wd=

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

Wq，Ln=

h77.3服務時間與間隔時間

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

代表服務時間，代表間隔時間，t

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

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

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

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

為整數(shù)，稱為

k

階愛爾蘭分布；當k=1

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

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

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

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

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

成正比，與t0

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

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

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

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

在t

內(nèi)有k>1個服務臺終結(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ū)間長度有關(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)有關，與Xn

前的狀態(tài)無關，具有無記憶性，或無后效性，又稱馬氏性狀態(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ù)馬氏鏈，應用全概率公式，有狀態(tài)轉(zhuǎn)移概率方程另有兩個邊界方程19

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

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

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

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

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