忻展紅-運籌學-課件運籌七

1、管理與人文學院1999，4忻展紅第七章隨機服務(wù)理論概述確定型只是隨機現(xiàn)象的特例7.1 隨機服務(wù)系統(tǒng) 系統(tǒng)的輸入與輸出是隨量 A.k.Erlang 于19091920年發(fā)表了一系列根據(jù)話務(wù)量計算電話機鍵配置的方法，為隨機服務(wù)理論奠定了基礎(chǔ) 又稱為排隊論(Queuing Theory)或擁塞理論(Congestion Theory)三個服務(wù)臺隨機服務(wù)系統(tǒng)離去的顧客.排隊等待顧客2顧客源與服務(wù)系統(tǒng)性能相關(guān)的特性 服務(wù)系統(tǒng)存在來自兩個矛盾方面的要求 顧客希望服務(wù)質(zhì)量好，如排隊等待時間短，損失率低 系統(tǒng)運營方希望設(shè)備利用率高 給用戶一個經(jīng)濟上能夠承受的滿意的質(zhì)量 哪些系統(tǒng)特性會影響系統(tǒng)的性能？ 服務(wù)機構(gòu)

2、的組織方式與服務(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ù) 全利用度、部分利用度3與服務(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ù)47.2隨機服務(wù)過程 單臺服務(wù)系統(tǒng)、等待制、先到先服務(wù) 顧客在系統(tǒng)中的總時長：逗留時間=等待時長+服務(wù)時長 等待時長與顧客

3、到達率和服務(wù)時長有關(guān)51234顧客t1t2t3t4到達時刻開始服務(wù)時刻w2w3服務(wù)t終結(jié)時刻h1h2h3空h41234當服務(wù)臺連續(xù)不斷服務(wù)時，有如下關(guān)系：wi+1+ti+1= wi+hiwi+hi 表示了累計的未完成的服務(wù)時長，一般地有ti , wi , hi 可通過寫實來獲得，另一種寫實法a(t) 代表時段(0, t)中累計到達顧客數(shù)b(t) 代表時段(0, t)中累計接受服務(wù)的顧客數(shù)g(t) 代表時段(0, t)中累計服務(wù)完畢的顧客數(shù)則在任意考察時刻 t，有正在等待的顧客數(shù)：L(t)= a(t) - b(t)正在接受服務(wù)的顧客數(shù)：Ls(t)= b(t) - g(t)系統(tǒng)中逗留的顧客數(shù)：N(

4、t)= a(t) - g(t)6w= wi + hi - t i+1if wi + hi - t i+1 0i+10if wi + hi - t i+1 0 上述關(guān)系是普遍成立的，與服務(wù)臺設(shè)置和服務(wù)規(guī)則無關(guān) 下面分析等待顧客數(shù)、等待時間和顧客到達率的關(guān)系 到達率定義為單位時間內(nèi)平均到達的顧客數(shù)，即lt= a(t) / t 令 d(t) 表示在時段(0, t)內(nèi)到達系統(tǒng)內(nèi)顧客的總逗留時長 則每一個顧客的平均逗留時間為Wdt= d(t) /a(t) 系統(tǒng)中平均逗留顧客數(shù)可表達為Ldt= d(t) / t = (a(t) / t )(d(t) /a(t) ) = lt Wdt(Little form

5、ula)7系統(tǒng)中逗留顧客數(shù)平均逗留顧客數(shù)t 系統(tǒng)處于穩(wěn)態(tài)時的利特爾公式：Ld= l Wd 利特爾公式也是普遍成立的，已知其中任兩個量，可以求出另一個量 利特爾公式的分解：Ld = l Wd = l (Wq + h ) = Lq+ LnLq = l WqLn = l hWq 是顧客的平均排隊等待時間Lq 是排隊等待的平均隊長h是顧客的平均服務(wù)時長Ln 是同時接受服務(wù)的平均顧客數(shù)(即平均服務(wù)臺占用數(shù))87.3 服務(wù)時間與間隔時間7.3.1 概述 顧客的服務(wù)時間由于多種原因具有不確定性，最好的描述方法就是概率分布；同樣顧客到達的間隔時間也具有一定的概率分布 服務(wù)時間和到達間隔時間服從什么分布？可以先

6、通過統(tǒng)計得到經(jīng)驗分布，然后再做理論假設(shè)和檢驗 經(jīng)驗分布一般采用直方圖來表示，如下圖頻率%302010通話分鐘24689 若統(tǒng)計區(qū)間分得越細，樣本越多，則經(jīng)驗分布的輪廓越接近曲線 一般服務(wù)時間和間隔時間都是非負的連續(xù)實變量，令 h 代表服務(wù)時間，t 代表間隔時間，t 為給定的時間，則它們的概率分布函數(shù)分別表示為F(t)=Pt tF(t)=Ph t 它們的概率密度函數(shù)為f(t)=F(t)，具有性質(zhì)：f(t)0，f(t)dt=1 服務(wù)時間落在區(qū)間(a, c)的概率為 服務(wù)時間落在區(qū)間(t, t+Dt)的概率為Pt h t+Dt= f(t)Dt 平均服務(wù)時長和平均間隔時長 平均服務(wù)時長的倒數(shù)為服務(wù)率，

7、平均間隔時長的倒數(shù)為到達率10m = 1 hl = 1 th = Eh = tf (t)dtt= Et = tf (t)dt00Pa h c= c f (t)dt = F(c) - F(a)a7.3.2 常用的概率分布1、定長分布流水線的加工時間2、負指數(shù)分布一類最常用的分布，如上述通話時長，可靠性m110lt0t定長分布負指數(shù)分布11f(t) F(t)F(t)f(t)F (t ) = 1 - e -mtf (t ) = me -mth = tme -mt dt = 1/ m0F (t) = 1當t l0當t t0 = Ph t + t0 h t0 =Pt0 t0 Ph t0 = 1 - e

8、-m (t +t0 ) - (1 - e -m t0 ) =-m t1 - (1 - e -m t0 )1 - eQ.E.D7.3.3 負指數(shù)分布的特點 一個服從負指數(shù)分布的服務(wù)，在下一瞬間結(jié)束的概率 在Dt 內(nèi)服務(wù)終結(jié)的概率只與 m 和Dt 成正比，與 t0 無關(guān)；因此 m 又稱為終結(jié)率，或離去率 同理，在 Dt 內(nèi)服務(wù)不終結(jié)的概率為1m Dt +o(Dt ) n 個獨立同分布(負指數(shù))的服務(wù)臺同時被占用，在Dt 內(nèi)只有一個服務(wù)臺終結(jié)的概率為 C1(mD t + o(Dt)(1- m Dt + o(Dt)n-1 = nmD t + o(Dt)n 在Dt 內(nèi)有 k 1 個服務(wù)臺終結(jié)的概率為 o

9、(Dt )，稱為普通性 Ck (m Dt + o(Dt)k (1- mD t + o(Dt)n-k = o(Dt)n14應(yīng)用無記憶性Ph t0 + Dt h t0 = 1 - e -m Dt= 1 - 1 - m Dt + (m Dt )22! - (m Dt )33! + L= m Dt + o(Dt )7.4 輸入過程 即顧客到達的分布，可用相繼到達顧客的間隔時間描述， 也可以用單位時間內(nèi)到達的顧客數(shù)描述 間隔時間服從定長分布 單位時間內(nèi)到達的顧客數(shù)服從波松分布(法國數(shù)學家Poisson, 1837) 間隔時間服從愛爾蘭分布 一般獨立同分布7.4.1 波松輸入過程及其特點 (0, t)時間

10、內(nèi)到達 k 個顧客的個數(shù)服從波松分布，若l 為到達率電話呼叫的到達，商店的顧客到達，十字路口的汽車流，港口到達的船只，機場到達的飛機等15(l t )k-l tPk (t) =k!e7.4.1 波松輸入過程及其特點(1) 平穩(wěn)性：顧客到達數(shù)只與時間區(qū)間長度有關(guān)(2) 無后效性：不相交的時間區(qū)間內(nèi)所到達的顧客數(shù)是獨立的(3) 普通性：在Dt 時間內(nèi)到達一個顧客的概率為 l Dt +o(Dt )， 到達兩個或兩個以上顧客的概率為 o(Dt )；即兩個顧客不可能同時到達 波松過程具有可迭加性即獨立的波松分布變量的和仍為波松分布(l t )i-l t(l t ) j-l t設(shè)兩個波松分布為:P (t

11、) = 1e1, P (t ) = 2e2ii!jj!令 n = i + j, 在(0, t )內(nèi)兩個流共來到n 個顧客的概率為nPx+ x= n=Px=j Px= n - j1212j =0= n(l t ) j-l t (l t )n- j-l t = (l+ l)n t n-(l + l )t 1e1 2e2 12e12j=0j!(n - j)!n!167.4.1 波松輸入過程及其特點 波松過程的到達間隔時間為負指數(shù)分布 令 t 代表間隔時間，則概率 Pt t代表時間區(qū)間(0, t)內(nèi)沒有顧客來的概率；由波松分布可知P0(t)= Pt t=e-lt 故間隔時間 t 的分布為 Pt t=1

12、-e-lt7.4.2 馬爾科夫鏈 馬爾科夫鏈(Markov Chain)又簡稱馬氏鏈，是一種離散隨機過程。用數(shù)學式表達為PXn+1=xn+1| X1=x1, X2=x2, . , Xn=xn= PXn+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)=PXn+1=j| Xn=i17例 7.4.2一售貨員出售兩種商品A和B，每日工作 8 小時。購買每種 商品的顧客到達過程為波松分布，到達率分別為 lA=8人/日，lB=16人/日，試求：(1) 1小時內(nèi)來到顧客總數(shù)

13、為 3 人的概率；(2) 三個顧客全是購買B類商品的概率。解：(1)總到達率為 lA+ lB=24人/日，1 小時=1/8 日，故(2) 3 個顧客全是購買B 類商品的概率為18(16 1 / 8)3-161 / 8-81 / 8PB3 (1/ 8)PA0 (1/ 8) =3!e e= 0.0664(24 1/ 8)3-241 / 8P3 (1/ 8) =3!e= 0.2247.5 生滅過程 采用馬氏鏈 令 N(t)代表系統(tǒng)在時刻 t 的狀態(tài)，下一瞬間 t+Dt 系統(tǒng)的狀態(tài)只能轉(zhuǎn)移到相鄰狀態(tài)，或維持不變，如圖所示 三種轉(zhuǎn)移是不相容的，三者必居其一 只有具有無記憶性和普通性的過程(分布)才適用馬

14、氏鏈 令 Pj(t)=PN(t)=j代表系統(tǒng)在時刻 t 處于狀態(tài) j 的概率19ljDtj+11-(l j+mj)DtjjmjDtj-1tt+Dt生滅過程的馬氏鏈 根據(jù)馬氏鏈，應(yīng)用全概率公式，有狀態(tài)轉(zhuǎn)移概率方程 另有兩個邊界方程 p0 (t + Dt) = p1(t)m1Dt + p0 (t)(1 - l0Dt) + o(Dt) pn (t + Dt) = pn-1(t)ln-1Dt + pn (t)(1 - mnDt) + o(Dt)20p j (t + Dt ) = p j-1 (t)l j-1Dt + p j+1 (t)m j+1Dt+ p j (t)(1 - l jDt - m jDt

15、) + o(Dt)j = 1,2,L, n - 11-l0Dt1-(l1+m1)Dt1-(lj-1+mj-1)Dt1-(lj+mj)Dt1-(lj+1+mj+1)Dt1-mnDtl0Dtl1Dtlj-1DtljDtln-1Dt01.j-1jj+1.nm1Dtmj-1DtmjDtmj+1DtmnDt生滅方程的推導過程 將上述三個差分方程化為微分方程 上述三個方程是動態(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)方程組m1 p1 - l0 p0 = 0j = 0(1)m j+1 p j +1 + l j-1 p j -

16、1 - (l j + m j ) p j = 01 j n(2)mn pn - ln-1 pn-1 = 0j = n(3)21pj (t + Dt) - pj (t)lim= l j -1 pj -1(t) + m j +1 pj +1(t)Dt0Dt- (l j + m j ) pj (t)j = 1,2,L, n - 1即pj (t) = l j-1 pj -1(t) + m j+1 pj +1(t) - (l j + m j ) pj (t)同理有 p0 (t) = m1 p1 (t) - l0 p0 (t)pn (t) = ln-1 pn-1 (t) - mn pn (t)生滅過程穩(wěn)態(tài)

17、解 方程(1), (2), (3) 與穩(wěn)態(tài)狀態(tài)轉(zhuǎn)移圖一一對應(yīng)；遞歸解如下：= l0l0l1m1m2令 j = 1, 將p1 代入(2)式得:p2 =p1p0p0m1l j -1l0l1 Ll j -1p j =依次遞推, 得p j -1p0(歸納法)mmmLmj12j-1llLlnj -1 01n p jp0 = 1 + = 1,得由0m1m2 Lm j22j=1m1 p1 - l0 p0 = 0j = 0(1)m j+1 p j +1 + l j-1 p j -1 - (l j + m j ) p j = 01 j n(2)mn pn - ln-1 pn-1 = 0j = n(3)l0l1l

18、j-1ljln-101.j-1jj+1.nm1mj-1mjmj+1mn滿足生滅過程的條件 系統(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)鍵是找出 lj , mj 的不同表達式，將它們代入生滅方程 標準服務(wù)系統(tǒng)的表示法：(X/Y/Z: A/B/C)，X 表示輸入過程， Y 表示服務(wù)過程，Z 表示并聯(lián)服務(wù)臺的個數(shù)，A 表示顧客源， B 表示系統(tǒng)容量，C 表示服務(wù)規(guī)則 (M/M/n: /m/FIFO) 表示波松輸入，負指數(shù)服