運籌學教程課件八-生滅服務系統(tǒng)

1、1,第八章 生滅服務系統(tǒng)M/M/n 系統(tǒng),魚與熊掌兼得？,2,8.1 M/M/n 損失制,8.1.1 M/M/n 損失制，無限源 (M/M/n: /n/FIFO) 令從顧客源來的顧客到達率為 ，每臺的服務率為 則有 j = , j=0,1, . , n1; n=0， j = j, j=0,1, . , n 將j , j 代入生滅方程，得,式中 =/ 稱為業(yè)務量(traffic)，是無量綱量；表示單位時間內(nèi)要求系統(tǒng)提供的服務時間； 和 的單位必須一致；由于紀念Erlang，用愛爾蘭作單位 (Erl),3,系統(tǒng)的服務質(zhì)量,系統(tǒng)的質(zhì)量用顧客的損失率來度量，有兩種度量方法 按時間計算的損失率 pn，即

2、單位時間內(nèi)服務臺全被占用的時間 按顧客計算的損失率 B，即單位時間內(nèi)損失的顧客數(shù)與到達顧客數(shù)之比 在本系統(tǒng)中有 B=pn=En()，稱為愛爾蘭損失公式,不是所有系統(tǒng)都有 B=pn 的性質(zhì) 工程上經(jīng)常是已知 ，給定 B，求所需最少的服務臺 n 求 n 一般有三種方法：迭代計算，查圖，查表,4,求所需服務臺的方法,1、查圖，如書上P186頁 2、迭代計算 無法由 En() 給出 n 的逆函數(shù)，因此采用逐次試算的方法 注意， En() 有較簡單的遞推公式,3、工程上經(jīng)常采用查表的方法 愛爾蘭表最左邊一列為服務臺數(shù) n，最上面一行為服務質(zhì)量的不同等級，即 B 愛爾蘭表中元素的值為 ，表示服務臺數(shù)為 n

3、，服務質(zhì)量為 B時，系統(tǒng)最大所能承擔的業(yè)務量；工程上經(jīng)常用A表示 ，A 是加入話務量,5,愛爾蘭損失表,n=3, B=0.01, 查表得 =0.455 已知 n 和 如何求 B，線性內(nèi)插法；例： n=3， =2.5，由表可知 B 落在 0.20.3 之間，若假設(shè)在這區(qū)間所承擔的業(yè)務量與 B 成線性關(guān)系，則有線性內(nèi)插公式 B 2.5=0.2+(0.3-0.2)(2.5-1.930)/(2.633-1.930)=0.281,6,例1 M/M/n 損失制無限源系統(tǒng)，已知 n=3，=5人/小時，平均服務時長30分鐘/人，試求：(1)系統(tǒng)中沒有顧客的概率；(2)只有一個服務臺被占用的概率；(3)系統(tǒng)的損

4、失率 解：由題意可知 =60/30=2人/小時，所以 =/ =2.5Erl (1) p0=(1+2.5+2.52/2+2.53/3!)1=0.108 (2) p1= p0=2.50.108=0.27 (3) B=E3(2.5)=p0 3/3!=0.108 2.604=0.28 例2 兩市話局間的忙時平均呼叫次數(shù)為240，每次通話平均時長為 5 分鐘，規(guī)定兩局間中繼線的服務等級為 B 0.01,問：(1) 應配備多少條中繼線？(2)中繼線群的利用率為多少？ 解：中繼線群上的加入話務量為 =240 5/60= 20Erl， (1)查186頁圖，n=30條； (2)查愛爾蘭表可知： n=30，B=0

5、.01時可承擔 A=20.337，B=0.005 時可承擔 A=19.034，因此， E30(20)=0.005+0.005 (2019.034)/(20.33719.034)=0.008707 中繼線群利用率 = (1B)/n=20(1-0.008707)/30=0.660862,7,服務臺利用率與服務臺數(shù)量的關(guān)系 n 圖,當給定 n 和 B 后，系統(tǒng)所能承擔的業(yè)務量 可以通過愛爾蘭公式求出，從而可計算出服務臺利用率 ；若保持 B 不變，不斷增加服務臺數(shù) n， 也會發(fā)生變化，就可以得到n 圖如下；通過觀察，有幾點結(jié)論：,1、B不變時， 隨 n 增加；說明大電路群效率高 2、n 不變時， 隨

6、B 增加；說明效率與質(zhì)量是矛盾的；(高效路由) 3、 具有邊際遞減規(guī)律 4、 越大，系統(tǒng)抗過負荷能力越差,8,系統(tǒng)過負荷特性 B 圖,過負荷是指系統(tǒng)加入的業(yè)務量 A, 超過給定服務質(zhì)量所能承擔的業(yè)務量 A 過負荷用過載業(yè)務量與標準應承擔的業(yè)務量的比值來表示，即 = (AA)/A = A/A En(A) = B, En(A) = B 由圖可見，在同樣標準的服務質(zhì)量和同樣的過負荷率下，大系統(tǒng)的質(zhì)量劣化嚴重；說明效率與可靠性是矛盾的,9,例3 某服務部門把顧客分為兩組，分別組成兩個單獨的服務系統(tǒng)。各系統(tǒng)的到達率分別為 1 =4人/小時， 2 =8人/小時，每人的平均占用時長都為 6 分鐘；給定損失率

7、為 B 0.01 ，試求：(1)分組服務時每組應配備的服務臺數(shù)；(2)合并為一個服務系統(tǒng)時，各種條件不變，應配備的服務臺數(shù)；(3)比較兩種組織方式的服務臺利用率。 解：(1) 分組時： 1=4 0.1=0.4Erl, 2=8 0.1=0.8Erl 查愛爾蘭表，得 n1=3臺， n2=4臺，共需 7臺。 B1=0.005+0.005 (0.40.349)/(0.455 0.349)=0.0074 B2=0.005+0.005 (0.80.701)/(0.869 0.701)=0.00795 = 1(1 B1)+2(1 B2)/(n1+n2)=0.17 (2) 合組時： =12 0.1=1.2Er

8、l, 查愛爾蘭表，得 n =5臺，節(jié)省了 2臺。 B =0.005+0.005 (1.21.132)/(1.3611.132)=0.006485 = (1 B)/n=0.238,10,8.2.1 M/M/n 損失制，有限源 (M/M/n: N/n/FIFO),例 交換機內(nèi)部有 n 條繩路，N條入中繼線，N n；每條入中繼線上的呼叫到達強度為 ，且為波松分布，通話時長為負指數(shù)分布(參數(shù)為 m )，問入中繼線上呼叫的損失率為多少？ 上述例子就是一個 M/M/n 損失制，有限源系統(tǒng)。當已經(jīng)接受繩路服務的中繼線在通話中，該中繼線上就不會有新的呼叫。因此，整個系統(tǒng)的呼叫到達率是與系統(tǒng)中被服務的中繼線數(shù)相

9、關(guān)的。這就是有限源系統(tǒng)的特點 顯然，系統(tǒng)在各狀態(tài)下的到達率和離去率分別為 j =(N j), j=0,1, . , n1, n=0， j = j, j=1, . , n 將j , j 代入生滅方程，得,11,當 j=n 時，pn表示按時間計算的損失率,下面分析按顧客計算的損失率 B B=單位時間平均損失顧客數(shù)/單位時間平均到達顧客數(shù) 在有限源系統(tǒng)中，顧客到達率隨系統(tǒng)狀態(tài)變化，因此有平均顧客到達率 ，又稱為有效到達率,12,可見，在有限源情況下，系統(tǒng)按時間計算的損失率 pn 和按顧客計算的損失率 B 是不相等的；其原因就是輸入過程隨系統(tǒng)狀態(tài)而變 從一個極端情況看，若 N=n，則 B=0，但 pn

10、 0 雖然愛爾蘭損失公式和恩格謝特損失公式都是在負指數(shù)服務時長假設(shè)下推導出來的，但已證明服務時間是其它一般平穩(wěn)分布，結(jié)論仍是正確的 服務臺利用率：,13,例4 有一電話查詢服務處集中答復三個查詢點的所有查詢事項。查詢服務處與查詢點之間用電話聯(lián)系。查詢服務處只有一名值班員答復所有的查詢。已知每個查詢點平均每小時有兩次查詢，每次平均通話12分鐘，問：(1)值班員空閑的概率；(2)值班員打電話的概率；(3)查詢時值班員忙的概率；(4)服務處查詢電話的平均到達率；(5)值班員的工時利用率。 解：系統(tǒng)是有限源 M/M/1 損失制。q= / =(2/60)12=0.4Erl (1) p0=1/(1+Nq)

11、=0.4545,14,8.2 M/M/n 等待制，無限源，無限容量(M/M/n: /FIFO),8.2.1 系統(tǒng)穩(wěn)態(tài)概率及等待概率 令從顧客源來的顧客到達率為 ，每臺的服務率為 則有 j = , j0; j = j, jn； j = n, jn 將j , j 代入生滅方程，得,15,當 n 時，則 p0 中第二項不收斂，系統(tǒng)中隊長將趨于無窮 當 n 時，系統(tǒng)有穩(wěn)態(tài)，處于動態(tài)平衡；無限容量等待制，每個顧客早晚都會得到服務，因此系統(tǒng)完成的業(yè)務量也是 顧客進入系統(tǒng)必須排隊等待的概率為,D 愛爾蘭等待公式 排隊等待的概率是等待制系統(tǒng)的重要指標之一 n=1 時，D= 公式 D 的記憶法,16,8.2.2

12、 系統(tǒng)的各種指標,等待制系統(tǒng)的指標有：平均逗留隊長；平均等待隊長；平均逗留時長；平均等待時長和服務臺利用率等,n=1 時，D= ，Ld = /(1)， Lq = 2/(1)，Wq= /() 例5 書上 195頁,17,8.2.3 等待時間的概率分布,前面只推導了要等待的概率 D=PW0，但在很多情況下我們希望知道等待時長的分布，即 PWt 系統(tǒng)中有 j 個顧客， jn 時，新來顧客要排隊等待，采用FIFO規(guī)則；令新顧客到達時為 0 時刻，顯然，只有服務臺上離去 jn個顧客時，新顧客才排到隊首 當 n 個服務臺連續(xù)服務時，顧客離去率為 n，因此服務臺空出的過程是波松流，在(0, t)內(nèi)空出 i

13、次的概率為,18,等待時長分布的推導,19,例6 某儲蓄所內(nèi)，已知忙時顧客到達率 =40人/小時，窗口營業(yè)員服務率為 =16人/小時，要求：(1)工時利用率不低于 60%；(2)顧客平均等待時間不超過 5 分鐘；問：設(shè)幾個窗口適當。 解：系統(tǒng)是無限源 M/M/n 等待制。= / =40/16=2.5Erl (1) = /n 0.6，解出 n 4.17，故 n 可取值 3， 4 (2) n=3 時，p0=(1+2/2! + (3/3!)(3/(3-2.5)1=0.045,20,例7 興建一座港口碼頭，只有一個裝卸泊位，要求設(shè)計泊位的生產(chǎn)能力，能力用日裝卸船只數(shù)表示。已知單位裝卸能力日平均生產(chǎn)費用為 a=2000元；船只到港后若不能及時裝卸，逗留一日要損失運輸費 b=1500元；預計船只的平均到達率為 =3 只/日。設(shè)船只到達的間隔時間和裝卸時間都服從負指數(shù)分布，