運籌學第8章：標準服務系統(tǒng)MMn系統(tǒng)

1、管理與人文學院管理與人文學院 忻展紅忻展紅 1999，4第八章第八章 標準服務系統(tǒng)標準服務系統(tǒng)M/M/n 系統(tǒng)系統(tǒng)魚與熊掌兼得？魚與熊掌兼得？18.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è)務量業(yè)務量(traffic)，是無量綱量是無量綱量；表示單位時間表示

2、單位時間內(nèi)要求系統(tǒng)提供的服務時間；內(nèi)要求系統(tǒng)提供的服務時間； 和和 的單位必須一致；由于的單位必須一致；由于紀念紀念Erlang，用用愛爾蘭愛爾蘭作單位作單位 (Erl) njkjpkpppjpjppnkkjjnkknjjjjjjjjjj, 2 , 1! 1 !0100000011120 得得由由2 系統(tǒng)的服務質量系統(tǒng)的服務質量系統(tǒng)的質量用顧客的損失率來度量，有兩種度量方法系統(tǒng)的質量用顧客的損失率來度量，有兩種度量方法 按時間計算的按時間計算的損失率損失率 pn，即即單位時間內(nèi)服務臺全被占用的單位時間內(nèi)服務臺全被占用的時間時間 按顧客計算的按顧客計算的損失率損失率 B，即單位時間內(nèi)損失的顧客數(shù)

3、與到即單位時間內(nèi)損失的顧客數(shù)與到達顧客數(shù)之比達顧客數(shù)之比 在本系統(tǒng)中有在本系統(tǒng)中有 B=pn=En( )，稱為稱為愛爾蘭損失公式愛爾蘭損失公式不是所有系統(tǒng)都有不是所有系統(tǒng)都有 B=pn 的性質的性質工程上經(jīng)常是已知工程上經(jīng)常是已知 ，給定，給定 B，求所需最少的服務臺求所需最少的服務臺 n求求 n 一般有三種方法：迭代計算，查圖，查表一般有三種方法：迭代計算，查圖，查表)(!0 nnnnkknnEppBknp 3 求所需服務臺的方法求所需服務臺的方法1、查圖，如書上、查圖，如書上262頁頁2、迭代計算迭代計算 無法由無法由 En( ) 給出給出 n 的的逆函數(shù)，因此采用逐次試算的方法逆函數(shù)，因

4、此采用逐次試算的方法 注意，注意， En( ) 有較簡單的遞推公式有較簡單的遞推公式3、工程上經(jīng)常采用查表的方法、工程上經(jīng)常采用查表的方法 愛爾蘭表最左邊一列為服務臺數(shù)愛爾蘭表最左邊一列為服務臺數(shù) n，最上面一行為服務最上面一行為服務質量的不同等級，即質量的不同等級，即 B 愛爾蘭表中元素的值為愛爾蘭表中元素的值為 ，表示服務臺數(shù)為，表示服務臺數(shù)為 n，服務質服務質量為量為 B時，系統(tǒng)最大所能承擔的業(yè)務量；工程上經(jīng)常用時，系統(tǒng)最大所能承擔的業(yè)務量；工程上經(jīng)常用A表示表示 ，A 是是加入話務量加入話務量即即為為所所求求則則迭迭代代直直到到首首次次滿滿足足 ,)( 1)()()()(011nBEE

5、EnEEnnnn 4愛爾蘭損失表愛爾蘭損失表A n B0.0050.010.050.10.20.310.005 0.010 0.053 0.111 0.2500.42920.105 0.153 0.381 0.595 1.0001.44930.349 0.455 0.899 1.271 1.9302.63340.701 0.869 1.525 2.045 2.9453.89151.132 1.361 2.218 2.881 4.0105.18961.622 1.909 2.960 3.758 5.1096.51472.157 2.501 3.738 4.666 6.2307.85782.730

6、 3.128 4.543 5.597 7.3699.21393.333 3.783 5.370 6.546 8.522 10.579103.961 4.461 6.216 7.511 9.685 11.953 n=3, B=0.01, 查表得查表得 =0.455 已知已知 n 和和 如何求如何求 B，線性內(nèi)插法線性內(nèi)插法；例：；例： n=3， =2.5，由表可知由表可知 B 落在落在 0.20.3 之間，若假設在這區(qū)間所承擔之間，若假設在這區(qū)間所承擔的業(yè)務量與的業(yè)務量與 B 成線性關系，則有成線性關系，則有線性內(nèi)插公式線性內(nèi)插公式 B 2.5=0.2+(0.3-0.2)(2.5-1.930)/

7、(2.633-1.930)=0.2815例例1 M/M/n 損失制無限源系統(tǒng)，已知損失制無限源系統(tǒng)，已知 n=3， =5人人/小時，平均服小時，平均服務時長務時長30分鐘分鐘/人人，試求：，試求：(1)系統(tǒng)中沒有顧客的概率；系統(tǒng)中沒有顧客的概率；(2)只有只有一個服務臺被占用的概率；一個服務臺被占用的概率；(3)系統(tǒng)的損失率系統(tǒng)的損失率解解：由題意可知：由題意可知 =60/30=2人人/小時，所以小時，所以 = / =2.5Erl (1) p0=(1+2.5+2.52/2+2.53/3!) 1=0.108 (2) p1= p0=2.5 0.108=0.27 (3) B=E3(2.5)=p0 3

8、/3!=0.108 2.604=0.28例例2 兩市話局間的忙時平均呼叫次數(shù)為兩市話局間的忙時平均呼叫次數(shù)為240，每次通話平均時長每次通話平均時長為為 5 分鐘，規(guī)定兩局間中繼線的服務等級為分鐘，規(guī)定兩局間中繼線的服務等級為 B 0.01,問：問：(1) 應配備多少條中繼線？應配備多少條中繼線？(2)中繼線群的中繼線群的利用率利用率為多少？為多少？解解：中繼線群上的加入話務量為：中繼線群上的加入話務量為 =240 5/60= 20Erl， (1)查查262頁圖，頁圖，n=30條；條； (2)查愛爾蘭表可知：查愛爾蘭表可知： n=30，B=0.01時時可承擔可承擔 A=20.337，B=0.0

9、05 時時可承擔可承擔 A=19.034，因此，因此， E30(20)=0.005+0.005 (20 19.034)/(20.337 19.034)=0.008707 中繼線群利用率中繼線群利用率 = (1 B)/n=20(1-0.008707)/30=0.6608626 服務臺利用率與服務臺數(shù)量的關系服務臺利用率與服務臺數(shù)量的關系 n 圖圖當給定當給定 n 和和 B 后，系統(tǒng)所能承擔的業(yè)務量后，系統(tǒng)所能承擔的業(yè)務量 可以通過愛爾可以通過愛爾蘭公式求出，從而可計算出服務臺利用率蘭公式求出，從而可計算出服務臺利用率 ；若保持；若保持 B 不不變，不斷增加服務臺數(shù)變，不斷增加服務臺數(shù) n， 也會

10、發(fā)生變化，就可以得到也會發(fā)生變化，就可以得到 n 圖如下；通過觀察，有幾點結論：圖如下；通過觀察，有幾點結論：210864122018161410203040506070800 nB=0.01B=0.05B=0.10B=0.151 1、B不變時，不變時， 隨隨 n 增加；增加；說明大電路群效率高說明大電路群效率高2、n 不變時，不變時， 隨隨 B 增加；增加；說明效率與質量是矛盾說明效率與質量是矛盾的；的；(高效路由高效路由)3、 具有具有邊際遞減邊際遞減規(guī)律規(guī)律4、 越大，系統(tǒng)抗過負荷越大，系統(tǒng)抗過負荷能力越差能力越差7 系統(tǒng)過負荷特性系統(tǒng)過負荷特性 B 圖圖過負荷過負荷是指系統(tǒng)加入的業(yè)是指

11、系統(tǒng)加入的業(yè)務量務量 A , 超過給定服務質量超過給定服務質量所能承擔的業(yè)務量所能承擔的業(yè)務量 A過負荷用過載業(yè)務量與標過負荷用過載業(yè)務量與標準應承擔的業(yè)務量的比值準應承擔的業(yè)務量的比值來表示，即來表示，即 = (A A)/A = A/A En(A) = B, En(A ) = B 由圖可見，在同樣標準的由圖可見，在同樣標準的服務質量和同樣的過負荷服務質量和同樣的過負荷率下，大系統(tǒng)的質量劣化率下，大系統(tǒng)的質量劣化嚴重；說明效率與可靠性嚴重；說明效率與可靠性是矛盾的是矛盾的0.0020 n=50.0040.0060.0085101520n=10n=1525BB=8例例3 某服務部門把顧客分為兩組

12、，分別組成兩個單獨的服務系統(tǒng)。某服務部門把顧客分為兩組，分別組成兩個單獨的服務系統(tǒng)。各系統(tǒng)的到達率分別為各系統(tǒng)的到達率分別為 1 =4人人/小時，小時， 2 =8人人/小時，每人的小時，每人的平均占用時長都為平均占用時長都為 6 分鐘；給定損失率為分鐘；給定損失率為 B 0.01 ，試求：試求：(1)分組服務時每組應配備的服務臺數(shù)；分組服務時每組應配備的服務臺數(shù)；(2)合并為一個服務系統(tǒng)合并為一個服務系統(tǒng)時，各種條件不變，應配備的服務臺數(shù)；時，各種條件不變，應配備的服務臺數(shù)；(3)比較兩種組織方比較兩種組織方式的服務臺利用率。式的服務臺利用率。解解：(1) 分組時：分組時： 1=4 0.1=0

13、.4Erl, 2=8 0.1=0.8Erl 查愛爾蘭表，得查愛爾蘭表，得 n1=3臺，臺， n2=4臺，共需臺，共需 7臺。臺。 B1=0.005+0.005 (0.4 0.349)/(0.455 0.349)=0.0074 B2=0.005+0.005 (0.8 0.701)/(0.869 0.701)=0.00795 = 1(1 B1)+ 2(1 B2)/(n1+n2)=0.17 (2) 合組時：合組時： =12 0.1=1.2Erl, 查愛爾蘭表，得查愛爾蘭表，得 n =5臺，節(jié)省了臺，節(jié)省了 2臺。臺。 B =0.005+0.005 (1.2 1.132)/(1.361 1.132)=

14、0.006485 = (1 B)/n=0.23898.2.1 M/M/n 損失制，有限源損失制，有限源 (M/M/n: N/n/FIFO)例例 交換機內(nèi)部有交換機內(nèi)部有 n 條繩路，條繩路，N條入中繼線，條入中繼線，N n；每條入中每條入中繼線上的呼叫到達強度為繼線上的呼叫到達強度為 ，且為波松分布，通話時長為負，且為波松分布，通話時長為負指數(shù)分布指數(shù)分布(參數(shù)為參數(shù)為 )，問入中繼線上呼叫的損失率為多少？問入中繼線上呼叫的損失率為多少？上述例子就是一個上述例子就是一個 M/M/n 損失制，有限源系統(tǒng)。當已經(jīng)接損失制，有限源系統(tǒng)。當已經(jīng)接受繩路服務的中繼線在通話中，該中繼線上就不會有新的受繩路

15、服務的中繼線在通話中，該中繼線上就不會有新的呼叫。因此，整個系統(tǒng)的呼叫到達率是與系統(tǒng)中被服務的呼叫。因此，整個系統(tǒng)的呼叫到達率是與系統(tǒng)中被服務的中繼線數(shù)相關的。這就是有限源系統(tǒng)的特點中繼線數(shù)相關的。這就是有限源系統(tǒng)的特點顯然，系統(tǒng)在各狀態(tài)下的到達率和離去率分別為顯然，系統(tǒng)在各狀態(tài)下的到達率和離去率分別為 j =(N j) , j=0,1, . , n1, n=0， j = j , j=1, . , n將將 j , j 代入生滅方程，得代入生滅方程，得 qqkNppqjNpjjNNNpnkkjjjj10000!)1()1(10 當當 j=n 時，時，pn表示按時間計算的損失率表示按時間計算的損失

16、率 nkknnqkNqnNp0下面分析按顧客計算的損失率下面分析按顧客計算的損失率 BB=單位時間平均損失顧客數(shù)單位時間平均損失顧客數(shù)/單位時間平均到達顧客數(shù)單位時間平均到達顧客數(shù)在有限源系統(tǒng)中，顧客到達率隨系統(tǒng)狀態(tài)變化，因此有在有限源系統(tǒng)中，顧客到達率隨系統(tǒng)狀態(tài)變化，因此有平平均顧客到達率均顧客到達率 ，又稱為，又稱為有效到達率有效到達率 njjnnjjpjNpnNBpjN00)()()( jNNjNjNqjNjNqnNnNBnjjn1)()()(0由由11可見，在有限源情況下，系統(tǒng)按時間計算的損失率可見，在有限源情況下，系統(tǒng)按時間計算的損失率 pn 和按和按顧客計算的損失率顧客計算的損失率

17、 B 是不相等的；其原因就是輸入過程隨是不相等的；其原因就是輸入過程隨系統(tǒng)狀態(tài)而變系統(tǒng)狀態(tài)而變從一個極端情況看，若從一個極端情況看，若 N=n，則則 B=0，但但 pn 0雖然愛爾蘭損失公式和恩格謝特損失公式都是在負指數(shù)服雖然愛爾蘭損失公式和恩格謝特損失公式都是在負指數(shù)服務時長假設下推導出來的，但已證明服務時間是其它一般務時長假設下推導出來的，但已證明服務時間是其它一般平穩(wěn)分布，結論仍是正確的平穩(wěn)分布，結論仍是正確的服務臺利用率：服務臺利用率：)(110恩格謝特損失公式恩格謝特損失公式得得 njjnqjNqnNBnjpnjj 1 12例例4 有一電話查詢服務處集中答復三個查詢點的所有查詢事項。

18、有一電話查詢服務處集中答復三個查詢點的所有查詢事項。查詢服務處與查詢點之間用電話聯(lián)系。查詢服務處只有一名查詢服務處與查詢點之間用電話聯(lián)系。查詢服務處只有一名值班員答復所有的查詢。已知每個查詢點平均每小時有兩次值班員答復所有的查詢。已知每個查詢點平均每小時有兩次查詢，每次平均通話查詢，每次平均通話12分鐘，問：分鐘，問：(1)值班員空閑的概率；值班員空閑的概率；(2)值班員打電話的概率；值班員打電話的概率；(3)查詢時值班員忙的概率；查詢時值班員忙的概率；(4)服務處服務處查詢電話的平均到達率；查詢電話的平均到達率；(5)值班員的工時利用率。值班員的工時利用率。解解：系統(tǒng)是有限源：系統(tǒng)是有限源

19、M/M/1 損失制。損失制。q= / =(2/60) 12=0.4Erl(1) p0=1/(1+Nq)=0.45455455. 0)5(/91. 423)()4(444. 04 . 0214 . 02212)3(5455. 01)2(1101010001 ppppjNqjqBNqpqpNpjjejj 小小時時次次138.2 M/M/n 等待制，無限源，無限容量等待制，無限源，無限容量(M/M/n: / /FIFO) 8.2.1 系統(tǒng)穩(wěn)態(tài)概率及系統(tǒng)穩(wěn)態(tài)概率及等待概率等待概率令從顧客源來的顧客到達率為令從顧客源來的顧客到達率為 ，每臺的服務率為，每臺的服務率為 則有則有 j = , j 0; j

20、= j , jn； j = n , j n將將 j , j 代入生滅方程，得代入生滅方程，得 nnnnnnnnnjppnjpnnpnjpjpjpnkknnjnjjnjnjjnjjnjjnjjjjjjj! 1 !011000000得得由由14當當 n 時，則時，則 p0 中第二項不收斂，系統(tǒng)中隊長將趨于無窮中第二項不收斂，系統(tǒng)中隊長將趨于無窮當當 0，但在很多情況下但在很多情況下我們希望知道等待時長的分布，即我們希望知道等待時長的分布，即 PWt系統(tǒng)中有系統(tǒng)中有 j 個顧客，個顧客， j n 時，新來顧客要排隊等待，采用時，新來顧客要排隊等待，采用FIFO規(guī)則；令新顧客到達時為規(guī)則；令新顧客到達

21、時為 0 時刻，顯然，只有服務臺時刻，顯然，只有服務臺上離去上離去 j n個顧客時，新顧客才排到隊首個顧客時，新顧客才排到隊首當當 n 個服務臺連續(xù)服務時，顧客離去率為個服務臺連續(xù)服務時，顧客離去率為 n ，因此服務臺因此服務臺空出的過程是空出的過程是波松流波松流，在，在(0, t)內(nèi)空出內(nèi)空出 i 次的概率為次的概率為tnnjjjnjitnijtniieWPtWPtwPptWPjeitntWPtWeitntP )(00 , ,!)( ,!)()( 經(jīng)經(jīng)推推導導可可得得應應用用全全概概率率公公式式可可以以是是任任何何值值系系統(tǒng)統(tǒng)狀狀態(tài)態(tài)新新顧顧客客到到達達時時的的概概率率等等效效為為故故等等待

22、待時時間間17 等待時長分布的推導等待時長分布的推導tniitnnkkiiitnnkiikktnntnnjiinjnjjnjjjeWPitepnnnnnitnepnitnnepnknjeitnpnntWPptWP )(00000000000!)(!)(!)( !)(!) (!)(! 坐標變換坐標變換令令ki 00000kkiiiiikikkiikkxxyyxyx18例例6 某儲蓄所內(nèi)，已知忙時顧客到達率某儲蓄所內(nèi)，已知忙時顧客到達率 =40人人/小時，窗口營業(yè)小時，窗口營業(yè)員服務率為員服務率為 =16人人/小時小時，要求：，要求：(1)工時利用率不低于工時利用率不低于 60%；(2)顧客平均等

23、待時間不超過顧客平均等待時間不超過 5 分鐘；問：設幾個窗口適當。分鐘；問：設幾個窗口適當。解解：系統(tǒng)是無限源：系統(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分分鐘鐘小小時時時時分分鐘鐘小小時時8 . 0013328. 00737. 05 . 1! 3405 . 2)()!1(07370. 0 , 4 )3(27. 508789. 040163703125. 0/703125. 0045. 05 . 233! 35 . 2!25021030 pnnWpnnDLWpnnnDnqqqn 19例例7 興建一座港口碼頭，只有一個裝卸泊位，要求設計泊位的生興建一座港口碼頭，只有一個裝卸泊位，要求設計泊位的生產(chǎn)能力，能力用日裝卸船只數(shù)表示。已知單位