1、1,第十四章.排隊.論,1排隊過程的組成部分 2單服務臺泊松到達、負指數服務時間的排隊模型 3多服務臺泊松到達、負指數服務時間的排隊模型 4排隊系統的經濟分析 5單服務臺泊松到達、任意服務時間的排隊模型 6單服務臺泊松到達、定長服務時間的排隊模型 7多服務臺泊松到達、任意的服務時間、損失制排隊模型 8顧客來源有限制排隊模型 9單服務臺泊松到達、負指數服務時間、系統容量有限制的排隊模型 10多服務臺泊松到達、負指數服務時間、系統容量有限制的排隊模型 *11生滅過程及生滅過程排隊系統,2,一、基本概念 一些排隊系統的例子 排隊系統 顧 客 服務臺 服 務 電話系統 電話呼叫 電話總機 接通呼叫或取

2、消呼叫 售票系統 購票旅客 售票窗口 收款、售票 設備維修 出故障的設備 修理工 排除設備故障 防空系統 進入陣地的敵機 高射炮 瞄準、射擊，敵機被擊落或離開 排隊的過程可表示為：,排隊,服務機構服務,服務后顧客離去,排隊系統,顧客到達,1排隊過程的組成部分,3,考慮要點： 1、服務臺（或通道）數目：單服務臺（單通道）、多服務臺（多通道）。 2、顧客到達過程：本教材主要考慮顧客的泊松到達情況。 滿足以下四個條件的輸入流稱為泊松流（泊松過程）。 *平穩性：在時間區間 t, t+t) 內到達k個顧客的概率與t無關，只與 t 有關，記為 pk(t）； *無后效性：不相交的時間區間內到達的顧客數互相獨

3、立； *普通性：在足夠短的時間內到達多于一個顧客的概率可以忽略； *有限性：任意有限個區間內到達有限個顧客的概率等于1。 泊松分布 為單位時間平均到達的顧客數 P (x) = x e- / x! (x = 0, 1, 2,),1排隊過程的組成部分,4,1排隊過程的組成部分,3、服務時間分布： 服從負指數分布， 為平均服務率，即單位時間服務的顧客數， P（服務時間 t ) = 1- e- t 。 4、排隊規則分類 (1) 等待制： 顧客到達后，一直等到服務完畢以后才離去， 先到先服務，后到先服務，隨機服務，有優先權的服務； (2) 損失制： 到達的顧客有一部分未接受服務就離去。 5、平穩狀態：

4、業務活動與時間無關。,5,排隊系統的符號表示: 一個排隊系統的特征可以用五個參數表示，形式為： ABCDE 其中 A 顧客到達的概率分布，可取M、 D、G 、Ek等； B 服務時間的概率分布，可取M、D、 G 、 Ek等； C 服務臺個數，取正整數； D 排隊系統的最大容量，可取正整數或； E 顧客源的最大容量，可取正整數或。 例如 M / M / 1 / / 表示顧客到達過程服從泊松分布，服務時間服從負指數分布，一個服務臺，排隊的長度無限制和顧客的來源無限制。,1排隊過程的組成部分,6,M / M / 1 / / 單位時間顧客平均到達數 ，單位平均服務顧客數 ( ) 數量指標公式: 1. 系

5、統中無顧客的概率 P0 =1 / 2. 平均排隊的顧客數 Lq =2/( ) 3. 系統中的平均顧客數 Ls = Lq + / 4. 顧客花在排隊上的平均等待時間 Wq = Lq / 5. 顧客在系統中的平均逗留時間 Ws = Wq+ 1/ 6. 顧客得不到及時服務必須排隊等待的概率 Pw = / 7. 系統中恰好有 n 個顧客的概率 Pn =( /)n P0,1 排隊過程的組成部分,2單服務臺泊松到達、負指數服務時間的排隊模型,7,2單服務臺泊松到達、負指數服務時間的排隊模型,在上面的公式中，我們都認定 ,即到達率小于服務率，如果沒有這個條件，則排隊的長度將無限制地增加，服務機構根本沒有能力

6、處理所有到達的顧客， 也就是 / 1,我們稱 / 為服務強度。 例 某儲蓄所只有一個服務窗口。根據統計分析，顧客的到達過程服從泊松分布，平均每小時到達顧客36人；儲蓄所的服務時間服從負指數分布，平均每小時能處理48位顧客的業務。試求這個排隊系統的數量指標。 解 平均到達率 = 36/60 = 0.6， 平均服務率 = 48/60 = 0.8。 P0 =1 / = 10.6/0.8 = 0.25, Lq =2/( ) = (0.6)2 / 0.8(0.8 0.6) =2.25 (個顧客),8,Ls = Lq + / = 2.25+ 0.6/0.8 =3 (個顧客), Wq = Lq / = 2.

7、25/0.6 = 3.75（分鐘）, Ws = Wq+ 1/ = 3.75+1/0.8 =5 （分鐘）, Pw = / = 0.6/0.8 = 0.75, Pn =( /)n P0 = (0.75)n 0.25, n=1, 2, 。 通過計算，可知儲蓄所的排隊系統里有n個顧客的概率，見表14-1。,2單服務臺泊松到達、負指數服務時間的排隊模型,表14-1,9,2單服務臺泊松到達、負指數服務時間的排隊模型,通過計算數據與表中數據，可知儲蓄所的排隊系統并不盡如人意，到達儲蓄所有75%的概率要排隊等待，排隊的長度平均為2.25個人，排隊的平均時間為3.75分鐘，是1.25分鐘的3倍，而且儲蓄所里有7

8、個或更多的顧客的概率為13.35%，這個概率太高了。而要提高服務水平，減少顧客的平均排隊時間和平均服務時間，一般可采用兩種措施：第一，減少服務時間，提高服務率；第二，增加服務臺即增加服務窗口。 如采取第一種方法，不增加服務窗口，而增加新型點鈔機，建立儲戶管理信息系統，可以縮短儲蓄所每筆業務的服務時間，使每小時平均服務的顧客數目從原來的48人提高到60人，即每分鐘平均服務的顧客數從0.8人提高到1人，這時 仍然為0.6， 為1，通過計算得到的結果如表14-2所示：,10,2單服務臺泊松到達、負指數服務時間的排隊模型,從上表我們可以看出由于把服務率從0.8提高到1，其排隊系統有了很大的改進，顧客平

9、均排隊時間由3.75分鐘減少到1.5分鐘，顧客平均逗留時間從5分鐘減少到2.5分鐘，在系統里有7個或更多顧客的概率有大幅度的下降，從13.35%下降到2.79%。 如果采用第二種方法，再設一個服務窗口，排隊的規則為每個窗口排一個隊，先到先服務，并假設顧客一旦排了一個隊，就不能再換到另一個隊上去（譬如，當把這個服務臺設在另一個地點，上述假設就成立了）。這種處理方法就是把顧客分流，把一個排隊系統分成兩個排隊系,表14-2,11,2單服務臺泊松到達、負指數服務時間的排隊模型,統，每個排隊系統中有一個服務臺，每個系統的服務率仍然為0.8，但到達率由于分流，只有原來的一半了， =0.3，這時我們可求得每

10、一個排隊系統的數量指標如表14-3所示：,表14-3,我們比較表14-1和14-3，知道采用第二個方法的服務水平也使得原來的服務水平有了很大的提高，采用第二種方法顧客平均排隊時間減少到了0.75分鐘，顧客平均逗留時間減少到了2分鐘，第二種排隊系統為兩個M/M/1排隊系統。如果在第二種方法中把排隊的規則變一下，在儲蓄所里只排一個隊，這樣的排隊系統就變成了 M/M/2排隊系統。,12,M / M / C / / 單位時間顧客平均到達數 ，單位平均服務顧客數 。 1. 系統中無顧客的概率 2. 平均排隊的顧客數 3. 系統中的平均顧客數 Ls = Lq + / , 4. 顧客花在排隊上的平均等待時間

11、 Wq = Lq / ,3多服務臺泊松到達、負指數服務時間的排隊模型,13,5. 顧客在系統中的平均逗留時間 Ws = Wq+ 1/ , 6. 系統中顧客必須排隊等待的概率 7. 系統中恰好有 n 個顧客的概率,當nc時,當nc時,3多服務臺泊松到達、負指數服務時間的排隊模型,14,例 在前例的儲蓄所里多設一個服務窗口，即儲蓄所開設兩個服務窗口。顧客的到達過程仍服從泊松分布，平均每小時到達顧客仍是36人；儲蓄所的服務時間仍服從負指數分布，平均每小時仍能處理48位顧客的業務，其排隊規則為只排一個隊，先到先服務。試求這個排隊系統的數量指標。 解 C = 2， 平均到達率 = 36/60 = 0.6

12、， 平均服務率 = 48/60 = 0.8。 P0 =0.4545, Lq = 0.1227 (個顧客), Ls = Lq + / = 0.8727 (個顧客), Wq = Lq / = 0.2045（分鐘）, Ws = Wq+ 1/ = 1.4545 （分鐘）, Pw = 0.2045, P1 = 0.3409, P2 = 0.1278, P3 = 0.0479, P4 = 0.0180, P5 = 0.0067。 系統里有6個人的概率或多于6個人的概率為0.0040。,3多服務臺泊松到達、負指數服務時間的排隊模型,15,在儲蓄所里使用M / M / 2模型與使用兩個M / M / 1模型，

13、它們的服務臺數都是2，服務率和顧客到達率都一樣，只是在M / M / 2中只排一隊，在2個M / M / 1中排兩個隊，結果卻不一 樣。 M / M / 2使得服務水平有了很大的提高，每個顧客的平均排隊時間從0.75分鐘減少到0.2045分鐘，每個顧客在系統里逗留時間從2分鐘減少到1.4545分鐘，平均排隊的人數也從0.2250人減少到0.1227人，系統里平均顧客數也從0.6*2=1.2人減少到0.8727人。如果把M / M / 2與原先一個M / M / 1比較，那么服務水平之間的差別就更大了。 當然在多服務臺的M/M/C模型中，計算求得這些數量指標是很繁瑣的。管理運籌學軟件有排隊論的程

14、序，可以由它來計算。 我們在第二節與第三節發現公式有三個公式是完全相同的，實際上這三個公式表示了任一個排隊模型（不僅僅是M/M/1或M/M/2）中，Ls,Lq,Ws,Wq之間的關系，也就是說：,3多服務臺泊松到達、負指數服務時間的排隊模型,16,3多服務臺泊松到達、負指數服務時間的排隊模型,對任一個排隊模型成立，這里Ls,Lq,Ws,的定義如上所述，而 應為實際進入系統平均到達率，對于排隊長度有限制的模型，我們設因排隊長度的限制顧客被拒絕的概率為PN，則實際進入系統平均到達率應為 這時，原來公式中的 應改為 。,17,我們把一個排隊系統的單位時間的總費用TC定義為服務機構的單位時間的費用和顧客

15、在排隊系統中逗留單位時間的費用之和。即 TC = cw Ls + cs c 其中 cw為一個顧客在排隊系統中逗留單位時間付出的費用；Ls為在排隊系統中的平均顧客數；cs為每個服務臺單位時間的費用；c為服務臺的數目。 例 在前兩例中，設儲蓄所的每個服務臺的費用cs=18，顧客在儲蓄所中逗留一小時的成本cw =10。這樣，對儲蓄所M / M / 1 模型可知 Ls =3， c=1，得 TC = cw Ls + cs c=48 元/每小時。 對儲蓄所 M / M / 2 模型可知 Ls =0.8727， c=2，得 TC = cw Ls + cs c=44.73 元/每小時。,4排隊系統的經濟分析,

16、18,M / G / 1 / / 單位時間顧客平均到達數 ，單位平均服務顧客數 ， 一個顧客的平均服務時間 1 / ，服務時間的均方差。 數量指標公式: 1. 系統中無顧客的概率 P0=1 / 2. 平均排隊的顧客數 3. 系統中的平均顧客數 Ls = Lq + / 4. 顧客花在排隊上的平均等待時間 Wq = Lq / 5. 在系統中顧客的平均逗留時間 Ws = Wq+ 1/ 6. 系統中顧客必須排隊等待的概率 Pw = / 7. 系統中恰好有 n 個顧客的概率 Pn,5單服務臺泊松到達、任意服務時間的排隊模型,19,例1 某雜貨店只有一名售貨員，已知顧客的到達過程服從泊松分布，平均到達率為

17、每小時20人；不清楚這個系統的服務時間服從什么分布，但從統計分析知道售貨員平均服務一名顧客的時間為2分鐘，服務時間的均方差為1.5分鐘。試求這個排隊系統的數量指標。 解：這是一個 M / G / 1 的排隊系統，其中 = 20/60 = 0.3333 人/分鐘，1/ = 2分鐘， = =0.5 人/分鐘， =1.5。 P0 =1 / = 0.33334, Lq =1.0412 (人), Ls = Lq + / = 1. 7078 (人), Wq = Lq / = 2.25/0.6 = 3.1241（分鐘）, Ws = Wq+ 1/ =5.1241（分鐘）, Pw = / = 0.6666。,5

18、單服務臺泊松到達、任意服務時間的排隊模型,20,6單服務臺泊松到達、定長服務時間的排隊模型,M / D / 1 / / 注：它是 M / G / 1 / / 的特殊情況 = 0。 1. 系統中無顧客的概率 P0=1 / 2. 平均排隊的顧客數 3. 系統中的平均顧客數 Ls = Lq + / 4. 顧客花在排隊上的平均等待時間 Wq = Lq / 5. 在系統中顧客的平均逗留時間 Ws = Wq+ 1/ 6. 系統中顧客必須排隊等待的概率 Pw = / 7. 系統中恰好有 n 個顧客的概率 Pn,21,例2 某汽車沖洗服務營業部，有一套自動沖洗設備，沖洗每輛車需要6分鐘，到此營業部來沖洗的汽車

19、到達過程服從泊松分布，每小時平均到達6輛，試求這個排隊系統的數量指標。 解：這是一個 M / D / 1 排隊模型，其中 = 6輛/小時， = 60/6 =10輛/小時，得 P0 =1 / = 0.4, Lq =0.45, Ls = Lq + / = 1.05, Wq = Lq / = 0.0750， Ws = Wq+ 1/ =0.1750, Pw = / = 0.6。,6單服務臺泊松到達、定長服務時間的排隊模型,22,M / G / C / C / 注：不存在平均排隊的顧客數 Lq 和顧客平均的排隊等待時間 Wq。數量指標公式: 系統中的平均顧客數 Ls = / (1 Pc ) 其中Pc 是

20、系統中恰好有 c 個顧客的概率，也就是系統里c 個服務臺都被顧客占滿的概率。 系統中恰好有 n 個顧客的概率,7多服務臺泊松到達、任意的服務時間、損失制排隊模型,23,例3. 某電視商場專營店開展了電話訂貨業務，到達過程服從泊松分布，平均到達率為每小時16個，而一個接話員處理訂貨事宜的時間是隨著訂貨的產品、規格、數量及顧客的不同而變化的，但平均每個人每小時可以處理8個訂貨電話，在此電視商場專營店里安裝了一臺電話自動交換臺，它接到電話后可以接到任一個空閑的接話員的電話上，試問該公司應安裝多少臺接話員的電話，使得訂貨電話因電話占線而損失的概率不超過10%。 解：這是一個 M / G / C / C

21、 / 模型。當c=3時，即正好有3位顧客的情況，,7多服務臺泊松到達、任意的服務時間、損失制排隊模型,24,0.21050.1,所以不符合要求。 當c=4時， 因此，設置四個電話很合適。,7多服務臺泊松到達、任意的服務時間、損失制排隊模型,25,M / M / 1 / / m 條件：單位時間顧客平均到達數 單位平均服務顧客數 關心的項目: 1. 系統中無顧客的概率 P0 2. 系統中平均排隊的顧客數 Lq 3. 系統中的平均顧客數 Ls 4. 系統中顧客平均的排隊等待時間 Wq 5. 系統中顧客的平均逗留時間 Ws 6. 系統中顧客必須排隊等待的概率 Pw 7. 系統中恰好有 n 個顧客的概率

22、 Pn,8顧客來源有限制的排隊模型,26,M /M / 1 / /m 數量指標公式: 1. 系統中無顧客的概率 2. 平均排隊的顧客數 3. 系統中的平均顧客數 Ls = Lq + (1-p0) 4. 顧客在排隊上的平均花費等待時間 Wq = Lq /（m-Ls) 5. 在系統中顧客的平均逗留時間 Ws = Wq+ 1/ 6. 系統中有 n 個顧客的概率, n=0,1,2,m,8顧客來源有限制的排隊模型,27,例4. 某車間有5臺機器，每臺機器連續運轉時間服從負指數分布，平均連續運轉時間為15分鐘，有一個修理工，每次修理時間服從負指數分布，平均每次12分鐘，求該排隊系統的數量指標P0,Lq,L

23、s,Wq,Ws,以及P5。 解：這是一個M/M/1/ /5系統。其中，m=5, =1/15, =1/12,/ =0.8。 Lq=2.766 ; Ls=3.759 Wq=33.43 ; Ws=45.43 P5=0.2870,=0.0073,8顧客來源有限制的排隊模型,28,9單服務臺泊松到達、負指數服務時間、系統容量有 限制的排隊模型,這種模型我們記為M/M/1/K/，這個記法中的第四位字母K表示這個系統的最大容量為N，因為這是一個單服務臺的情況，所以排隊的顧客服務最多為K-1，在某時刻一顧客到達時，如系統中已有N個顧客，那么這個顧客就被拒絕進入系統。 這個模型可簡寫為M/M/1/K。 由于所考

24、慮的排隊子系統中最多只能容納K個顧客（等待位置只有K-1個），因而有:,令 ， 有：,1.系統里沒有顧客的概率,2.在系統里的平均顧客數,3. 平均的排隊顧客數,29,9單服務臺泊松到達、負指數服務時間、系統容量有 限制的排隊模型,4.有效顧客到達率,5.一位顧客花在排隊上的平均時間,6.一位顧客在系統中的平均逗留時間,7.在系統里正好有n個顧客的概率,30,9單服務臺泊松到達、負指數服務時間、系統容量有 限制的排隊模型,例5 某理發店只有一個理發師，且店里最多可容納4名顧客，設顧客按泊松流到達，平均每小時5人，理發時間服從負指數分布，平均每15分鐘可為1名顧客理發，試求該系統的有關指標。 解

25、：該系統可以看成一個M/M/1/4排隊系統，其中,31,9單服務臺泊松到達、負指數服務時間、系統容量有 限制的排隊模型,系統里平均顧客數,=,平均的排隊顧客數,平均逗留時間,平均排隊時間,32,10多服務臺泊松到達、負指數服務時間、系統容量有限制的排隊模型,這種排隊模型我們記為M/M/C/K/，這與第九節單服務臺模型的 區別，就在于服務臺的數量為C，我們可以把這個模型簡記為M/M/C/K。 在此系統中到達率與服務率分別為:,1.系統里沒有顧客的概率 2.系統里正好有n個顧客的概率,33,10多服務臺泊松到達、負指數服務時間、系統容量有限制的排隊模型,3.平均排隊顧客數,4.系統里的平均排隊顧客數,5.有效到達率,6.顧客花在排隊上的平均時間,7.顧客在系統里的平均逗留時間,特別地，當k=c時即為第七節的M/M/C/C/的模型。,34,10多服務臺泊松到達、負指數服務時間、系統容量有限制的排隊模型,例6 某公司維修服務中心有兩名維修工，中心內至多可以停放6臺機 器（包括正在維修的兩臺機器）。假設待修機器按泊松分布過程到達此中 心。平均每小時3臺。維修每臺機器平均需要20分鐘，試求該系統的各項 性能指數。 解：該子系統可看成一個M/M/2/