排隊論-1-2ppt課件

1、 排隊論排隊論 1;.2一一、M/M/1/GD/排隊系統(tǒng)排隊系統(tǒng) M M/ /M M/1/1/GDGD/排隊系統(tǒng)的顧客到達間隔時間和服務(wù)時間都服從參數(shù)分別為排隊系統(tǒng)的顧客到達間隔時間和服務(wù)時間都服從參數(shù)分別為 （單位時（單位時間段內(nèi)平均到達顧客數(shù)量）間段內(nèi)平均到達顧客數(shù)量） 和和 （單位時間段內(nèi)平均顧客服務(wù)顧客數(shù)量）的指數(shù)分（單位時間段內(nèi)平均顧客服務(wù)顧客數(shù)量）的指數(shù)分布。布。 我們可以用具有下列參數(shù)的生滅過程建立我們可以用具有下列參數(shù)的生滅過程建立M M/ /M M/1/1/GDGD/排隊系統(tǒng)的模型排隊系統(tǒng)的模型： 。，)1,2,3( 0)0,1,2,( 0jjjj3穩(wěn)態(tài)概率的推導穩(wěn)態(tài)概率的推

2、導jjj01)1(201021S11S10)1 (jj) 10(11jjc0jjjc21110定義定義排隊系統(tǒng)的通行強度排隊系統(tǒng)的通行強度 系統(tǒng)將不存在穩(wěn)定狀態(tài)系統(tǒng)將不存在穩(wěn)定狀態(tài) 4系統(tǒng)中的平均顧客數(shù)量系統(tǒng)中的平均顧客數(shù)量L L的推導的推導 假設(shè)系統(tǒng)已經(jīng)達到穩(wěn)定狀態(tài)，系統(tǒng)中存在顧客的平均數(shù)量，即系統(tǒng)達到穩(wěn)定狀態(tài)時假設(shè)系統(tǒng)已經(jīng)達到穩(wěn)定狀態(tài)，系統(tǒng)中存在顧客的平均數(shù)量，即系統(tǒng)達到穩(wěn)定狀態(tài)時顧客數(shù)量的期望值。有時我們將稱為平均隊長。顧客數(shù)量的期望值。有時我們將稱為平均隊長。 定義： 則： 。000)1()1(jjjjjjjjjL32032jjjS43232S132SS2)1 (S2)1 ()1 (L

3、15隊列中的平均顧客數(shù)量隊列中的平均顧客數(shù)量 的推導的推導 我們有時把等待在隊列中的人數(shù)的期望值稱為平均隊列長，或平均等待隊長，并用 來表示這個值。如果系統(tǒng)中只有0或1個人，則隊列中沒有人等待；如果系統(tǒng)中有j （ ）個人，則隊列中將有j-1個人處在等待狀態(tài)。因此，如果系統(tǒng)已經(jīng)達到穩(wěn)定狀態(tài)，有 又因為 ，上式可以寫成：qLqL1j1) 1(jjqjL11jjjjj)1 (0L，L)1 (L1qL12)(26服務(wù)中的平均顧客數(shù)量服務(wù)中的平均顧客數(shù)量 的推導的推導 系統(tǒng)中正接受服務(wù)的人數(shù)的期望值為系統(tǒng)中正接受服務(wù)的人數(shù)的期望值為 。對于一個。對于一個M M/ /M M/1/1/GDGD/排隊系統(tǒng)，當

4、它達排隊系統(tǒng)，當它達到穩(wěn)定狀態(tài)時到穩(wěn)定狀態(tài)時， 由于一名顧客要么在隊列中等待，要么正在接受服務(wù)，所以任何排隊系統(tǒng)（不僅僅是由于一名顧客要么在隊列中等待，要么正在接受服務(wù)，所以任何排隊系統(tǒng)（不僅僅是M M/ /M M/1/1/GDGD/ / / / 排隊系統(tǒng)）都應有，排隊系統(tǒng)）都應有， 所以sLsL)( 10210sL01)1 (1qsLLL112sqLLL 只有一個服務(wù)臺，一名顧只有一個服務(wù)臺，一名顧客接受服務(wù)客接受服務(wù)7隊列公式隊列公式 設(shè)某一顧客在排隊系統(tǒng)中逗留時間的期望值為設(shè)某一顧客在排隊系統(tǒng)中逗留時間的期望值為 （包括在排隊等待的時間和接受服務(wù)的（包括在排隊等待的時間和接受服務(wù)的時間）

5、，顧客的平均排隊等時間），顧客的平均排隊等 待時間為待時間為 。只有在穩(wěn)定狀態(tài)已經(jīng)達到時，才能計算。只有在穩(wěn)定狀態(tài)已經(jīng)達到時，才能計算 和和 的值。的值。 單位時間內(nèi)進入系統(tǒng)的平均顧客數(shù)量，單位時間內(nèi)進入系統(tǒng)的平均顧客數(shù)量， 系統(tǒng)中平均顧客數(shù)量，系統(tǒng)中平均顧客數(shù)量， 系統(tǒng)中正在排隊的平均顧客數(shù)量，系統(tǒng)中正在排隊的平均顧客數(shù)量， 系統(tǒng)中正在接受服務(wù)的平均顧客數(shù)量，系統(tǒng)中正在接受服務(wù)的平均顧客數(shù)量， 顧客在系統(tǒng)的平均總逗留時間，顧客在系統(tǒng)的平均總逗留時間， 顧客在隊列中等待的平均逗留時間，顧客在隊列中等待的平均逗留時間， 顧客接受服務(wù)的平均時間。顧客接受服務(wù)的平均時間。WLWqWWqWsWqWWs

6、LqLL8定理定理3 3（LittleLittle公式）公式） p對于任何存在穩(wěn)態(tài)概率分布的排隊系統(tǒng)，下列公式成立：對于任何存在穩(wěn)態(tài)概率分布的排隊系統(tǒng)，下列公式成立：WLqqWLssWL91L12qL)(2sLWLqqWLssWL10)1 (jj系統(tǒng)中沒有顧客的概率系統(tǒng)中j個顧客的概率系統(tǒng)中平均顧客的數(shù)量正在排隊的平均顧客數(shù)量正在接受服務(wù)的平均顧客數(shù)量單位時間內(nèi)進入系統(tǒng)的平均顧客數(shù)量單位時間內(nèi)進入系統(tǒng)的平均顧客數(shù)量單位時間內(nèi)接受服務(wù)的平均顧客數(shù)量單位時間內(nèi)接受服務(wù)的平均顧客數(shù)量sqLLL10例例1、儲蓄所的排隊系統(tǒng)、儲蓄所的排隊系統(tǒng) 某儲蓄所只有某儲蓄所只有1 1個柜臺處理個人儲蓄業(yè)務(wù)，平均每

7、小時有個柜臺處理個人儲蓄業(yè)務(wù)，平均每小時有1010名顧客來存取，平均每位顧名顧客來存取，平均每位顧客的服務(wù)時間為客的服務(wù)時間為4 4分鐘。顧客到達間隔時間和服務(wù)時間均服從指數(shù)分布。分鐘。顧客到達間隔時間和服務(wù)時間均服從指數(shù)分布。 求求 a)a)該柜臺空閑的概率該柜臺空閑的概率. . b) b)在隊列中等待的顧客平均數(shù)量（不包在隊列中等待的顧客平均數(shù)量（不包 括正在接受服務(wù)的顧客）括正在接受服務(wù)的顧客）. . c) c)每位顧客在銀行的平均逗留時間（包括服務(wù)時間）每位顧客在銀行的平均逗留時間（包括服務(wù)時間）. . d) d)該柜臺平均每小時服務(wù)的人數(shù)該柜臺平均每小時服務(wù)的人數(shù). .11儲蓄所的排

8、隊系統(tǒng)儲蓄所的排隊系統(tǒng)p解：由已知，我們可以把該柜臺看作一個 10人/小時，15人/小時的M/M/1/GD/排隊系統(tǒng)。因此， 。pa） ，該柜臺將以 的概率處于空閑狀態(tài)。 pb） 。pc） 。 pd）如果該柜臺一直處在繁忙狀態(tài)，那么平均每小時可以服務(wù)15人。由（a）可知，該柜臺只有 的時間處在繁忙狀態(tài)。因此每小時該柜臺平均服務(wù) 人。321510313201131 3411322322qL2113232L51102W3210)15)(3212加油站的排隊系統(tǒng)加油站的排隊系統(tǒng)p假設(shè)車主在汽車油量正好消耗至油箱一半時給汽車加油。某一單泵加油站平均每小時假設(shè)車主在汽車油量正好消耗至油箱一半時給汽車加油

9、。某一單泵加油站平均每小時有有7.57.5輛車來加油。平均每輛車需要輛車來加油。平均每輛車需要4 4分鐘完成整個加油過程。設(shè)汽車的到達間隔時間分鐘完成整個加油過程。設(shè)汽車的到達間隔時間和服務(wù)時間均服從指數(shù)分布。和服務(wù)時間均服從指數(shù)分布。pa a）求當前狀況下的）求當前狀況下的L L和和W W。pb b）假設(shè)車主改成當油量消耗至）假設(shè)車主改成當油量消耗至3/43/4時加油。由于每位加油的顧客需要購買的油量變少，時加油。由于每位加油的顧客需要購買的油量變少，每位顧客的平均服務(wù)時間減少至每位顧客的平均服務(wù)時間減少至10/310/3分鐘。求情況改變后的分鐘。求情況改變后的L L和和W W。13加油站的

10、排隊系統(tǒng)加油站的排隊系統(tǒng)p解：a）該加油站可以看作一個 7.5輛/小時， 15輛/小時的M/M/1/GD/排隊系統(tǒng)。p因此， ，p在這種情況下加油站運行良好，基本不會出現(xiàn)很長得隊列在這種情況下加油站運行良好，基本不會出現(xiàn)很長得隊列。 pb）在這種情況下， 27.5=15輛/小時，p 輛/小時的M/M/1/GD/排隊系統(tǒng)。516565L31155LW5 . 0155 . 715.015.0L13.05 .71LW18333. 360651815這是由于盲目的搶購，導致較長的隊列。這是由于盲目的搶購，導致較長的隊列。 （小時）（小時） 小時小時 14例例2、配件中心的管理員、配件中心的管理員 在一

11、個制造工廠工作的機械師必須從一個配件中心獲取配件。平均每小時有在一個制造工廠工作的機械師必須從一個配件中心獲取配件。平均每小時有1010名機械名機械師來尋找配件。目前配件中心有一名管理員，該管理員工資為師來尋找配件。目前配件中心有一名管理員，該管理員工資為6 6元元/ /小時，他為一位機小時，他為一位機械師尋找配件平均需要械師尋找配件平均需要5 5分鐘。由于一名機械師每小時可以制造價值分鐘。由于一名機械師每小時可以制造價值1010元的產(chǎn)品，因此元的產(chǎn)品，因此機械師每在配件中心逗留機械師每在配件中心逗留1 1小時就相當于花費了該廠小時就相當于花費了該廠1010元。該廠正在決策是否花元。該廠正在決

12、策是否花4 4元元/ /小小時雇傭一名管理員助手。如果雇傭，那么管理員為每位機械師的尋找配件只要平均時雇傭一名管理員助手。如果雇傭，那么管理員為每位機械師的尋找配件只要平均4 4分分鐘。設(shè)機械師的到達間隔時間和管理員尋找配件的時間都服從指數(shù)分布。是否應該雇鐘。設(shè)機械師的到達間隔時間和管理員尋找配件的時間都服從指數(shù)分布。是否應該雇傭該助手？傭該助手？ 解：這種選擇一個排隊系統(tǒng)中的決策問題被稱為排隊最優(yōu)化問題（解：這種選擇一個排隊系統(tǒng)中的決策問題被稱為排隊最優(yōu)化問題（queuing queuing optimization problemoptimization problem）。）。 在本題中，

13、該廠的目標是最小化服務(wù)成本和機械師空閑成本之和。在排隊最優(yōu)化問題在本題中，該廠的目標是最小化服務(wù)成本和機械師空閑成本之和。在排隊最優(yōu)化問題中，由于顧客等待而造成的成本叫做延遲成本（中，由于顧客等待而造成的成本叫做延遲成本（delay costdelay cost）。因此，該廠的目標是）。因此，該廠的目標是最小化最小化時間期望延遲成本時間服務(wù)成本時間期望成本15配件中心的管理員配件中心的管理員p計算單位時間的服務(wù)成本往往很簡單。最簡單的計算單位時間延遲成本的方法如下所計算單位時間的服務(wù)成本往往很簡單。最簡單的計算單位時間延遲成本的方法如下所示：示：時間顧客數(shù)量顧客數(shù)量期望延遲成本時間期望延遲成本

14、均逗留時間）（機械師在系統(tǒng)中的平人小時元顧客數(shù)量期望延遲成本 10W10時間期望延遲成本現(xiàn)在比較雇傭和不雇傭該助手的情況下的單位時間期望成本?，F(xiàn)在比較雇傭和不雇傭該助手的情況下的單位時間期望成本。w16 p如果不雇傭助手，如果不雇傭助手， 1010人人/ /小時小時 ， 1212人人/ /小時。小時。 小時。由于管理員工資為小時。由于管理員工資為6 6元元/ /小時，小時， 每小時的期望成本為每小時的期望成本為6+506+505656（元）。（元）。2110121W6時間服務(wù)成本50101021時間期望延遲成本配件中心的管理員配件中心的管理員17 p如果雇傭助手，則如果雇傭助手，則 1010人

15、人/ /小時，小時， 1515人人/ /小時，小時， 小時，小時， +4=10+4=10（元），（元）， p雇傭助手后每小時的期望成本為雇傭助手后每小時的期望成本為20+1020+103030元。因此，應該雇傭該助手，因為平均每小元。因此，應該雇傭該助手，因為平均每小時可以節(jié)約時可以節(jié)約50-2050-203030元的延遲成本，大于元的延遲成本，大于4 4元元/ /小時的助手工資。小時的助手工資。5110151W6時間服務(wù)成本20101051時間期望延遲成本配件中心的管理員配件中心的管理員18pM/M/1/GD/排隊系統(tǒng)排隊系統(tǒng) pM/M/1/GD/c/排隊系統(tǒng)排隊系統(tǒng) pM/M/s/GD/排

16、隊系統(tǒng)排隊系統(tǒng) pM/M/s/GD/c/排隊系統(tǒng)排隊系統(tǒng)19M/M/1/GD/c/排隊系統(tǒng)排隊系統(tǒng)pM M/ /M M/1/1/GDGD/c/c/排隊系統(tǒng)與排隊系統(tǒng)與M M/ /M M/1/1/GDGD/排隊系統(tǒng)的差別僅在于：該系統(tǒng)的最大容量排隊系統(tǒng)的差別僅在于：該系統(tǒng)的最大容量為為c c個顧客，即如果系統(tǒng)中已經(jīng)有個顧客，即如果系統(tǒng)中已經(jīng)有c c個顧客，那么新到達的顧客將不能進入系統(tǒng)，并永個顧客，那么新到達的顧客將不能進入系統(tǒng)，并永遠不會再回來。假設(shè)顧客到達間隔時間和服務(wù)時間分別服從參數(shù)為遠不會再回來。假設(shè)顧客到達間隔時間和服務(wù)時間分別服從參數(shù)為 和和 的指數(shù)分布。的指數(shù)分布。 狀態(tài)012c-

17、1c20M/M/1/GD/c/排隊系統(tǒng)排隊系統(tǒng)pM M/ /M M/1/1/GDGD/ /c c/排隊系統(tǒng)的生排隊系統(tǒng)的生/ /滅率滅率p由于由于 0 0，因此，系統(tǒng)永遠不會達到狀態(tài)，因此，系統(tǒng)永遠不會達到狀態(tài)c c1 1或者其它數(shù)值更大的狀態(tài)。或者其它數(shù)值更大的狀態(tài)。，),1,2,( 001)-,0,1,( 0ccjcjjjc21M/M/1/GD/c/排隊系統(tǒng)排隊系統(tǒng)p定義定義 。p如果如果 ，則，則M M/ /M M/1/1/GDGD/c/c/系統(tǒng)的穩(wěn)態(tài)概率：系統(tǒng)的穩(wěn)態(tài)概率： ，p所以所以1011c),1,2,( cjojj)2,1,( 0ccjj)1)(1 () 1(111cccccLc

18、jjjL0jjc0jjjc2111022M/M/1/GD/c/排隊系統(tǒng)排隊系統(tǒng)p如果如果 ，則，則c=1.c=1.M M/ /M M/1/1/GDGD/c/c/排隊系統(tǒng)的穩(wěn)態(tài)概率：排隊系統(tǒng)的穩(wěn)態(tài)概率： p對對M M/ /M M/1/1/GDGD/c/c/排隊系統(tǒng)，即使排隊系統(tǒng)，即使 時，系統(tǒng)也存在穩(wěn)定狀態(tài)。時，系統(tǒng)也存在穩(wěn)定狀態(tài)。11cj), 1 , 0(cj2cL 02101)( 10sLsqLLL)1 (cLW)1 (cqqLW100ciiii0jjjL23例例3、理發(fā)店的排隊系統(tǒng)、理發(fā)店的排隊系統(tǒng)p某理發(fā)店只有一名理發(fā)師，共有10個座位。顧客的到達間隔時間服從指數(shù)分布，平均每小時有20名

19、潛在顧客到達。當?shù)昀镒鴿M時，顧客將離開。理發(fā)師為一位顧客理發(fā)平均要12分鐘。理發(fā)時間服從指數(shù)分布。求：a）理發(fā)師平均每小時為多少位顧客服務(wù)？b）進入理發(fā)店的顧客平均逗留多長時間？p解：a）該理發(fā)店坐滿的概率為 ，則平均每小時進入理發(fā)店的顧客數(shù)量為 。所有進入理發(fā)店的顧客都要理發(fā)，因此，理發(fā)師平均每小時為 位顧客理發(fā)。由已知得 20人/小時，5人/小時。則 ，得： 因此，平均每小時有 名顧客接受理發(fā)服務(wù)。10)1 (10)1(104520110414175. 041434141411101110105)1 (204324理發(fā)店的排隊系統(tǒng)理發(fā)店的排隊系統(tǒng)這意味著每小時有20515名潛在顧客不能進入

20、理發(fā)店。b） （人）， （小時） 可以得出結(jié)論，這個理發(fā)店十分擁擠，建議至少再雇傭一名理發(fā)師。 67. 9)41 ()41 (41041114111110L93. 1)1 (2067. 943W25pM/M/1/GD/排隊系統(tǒng)排隊系統(tǒng) pM/M/1/GD/c/排隊系統(tǒng)排隊系統(tǒng) pM/M/s/GD/排隊系統(tǒng)排隊系統(tǒng) pM/M/s/GD/c/排隊系統(tǒng)排隊系統(tǒng)26M/M/s/GD/排隊系統(tǒng)排隊系統(tǒng)p設(shè)顧客到達間隔時間服從參數(shù)為設(shè)顧客到達間隔時間服從參數(shù)為 的指數(shù)分布，服務(wù)時間服從參數(shù)為的指數(shù)分布，服務(wù)時間服從參數(shù)為 的指數(shù)分布，的指數(shù)分布，系統(tǒng)中有系統(tǒng)中有s s個并行的服務(wù)臺，但是只有一個隊列。個并

21、行的服務(wù)臺，但是只有一個隊列。，),2, 1( ), 1 ,0( ), 1 ,0( ssjssjjjjjj如果系統(tǒng)中有如果系統(tǒng)中有j 個服務(wù)臺被占用，則系統(tǒng)服務(wù)完成率為個服務(wù)臺被占用，則系統(tǒng)服務(wù)完成率為 ),.,1 ,0(sjjj 個如果系統(tǒng)中有如果系統(tǒng)中有j 個顧客，則個顧客，則 個服務(wù)臺將被占用個服務(wù)臺將被占用 ,min sj,minsjj27M/M/s/GD/排隊系統(tǒng)排隊系統(tǒng)M M/ /M M/ /s s/ /GDGD/排隊系統(tǒng)的生排隊系統(tǒng)的生/ /滅率滅率 定義定義 ，當，當 時時 。，), 2, 1( ), 1 , 0( ), 1 , 0( ssjssjjjjjjjjc010jj11

22、10jjc1011jjcs128M/M/s/GD/排隊系統(tǒng)排隊系統(tǒng)p定義定義 ，當，當 時，得到下列穩(wěn)定狀態(tài)概率：時，得到下列穩(wěn)定狀態(tài)概率： ), 2 , 1(sj), 2, 1,(sssjs1)1 ( !)()(1100ssisssii！jsjj0)(sjjjsss!)(029M/M/s/GD/排隊系統(tǒng)排隊系統(tǒng)p如果如果 ，則系統(tǒng)不存在穩(wěn)定狀態(tài)。所有服務(wù)臺均被占用的穩(wěn)態(tài)概率為，則系統(tǒng)不存在穩(wěn)定狀態(tài)。所有服務(wù)臺均被占用的穩(wěn)態(tài)概率為p可以得到可以得到： 1)1 ( !)()(0sssjPs1)(sjPLqssjPLWqq)(30系統(tǒng)中沒有顧客的概率系統(tǒng)中j個顧客的概率所有服務(wù)臺均被占用的穩(wěn)態(tài)概率

23、所有服務(wù)臺均被占用的穩(wěn)態(tài)概率 ！jsjj0)(), 2 , 1(sjsjjjsss!)(0), 2, 1,(sssj)1( !)()(1100ssisssii！)1 ( !)()(0sssjPs1)(sjPLqssjPLWqq)(sLqLLs1穩(wěn)定狀態(tài)穩(wěn)定狀態(tài) 31例例4、銀行的排隊系統(tǒng)、銀行的排隊系統(tǒng) 某銀行有兩個柜臺，平均每小時有某銀行有兩個柜臺，平均每小時有8080名顧客到達，并在同一隊列中等待接受服務(wù)。平均名顧客到達，并在同一隊列中等待接受服務(wù)。平均每位顧客服務(wù)需要每位顧客服務(wù)需要1.21.2分鐘。設(shè)顧客到達間隔時間和服務(wù)時間均服從指數(shù)分布。求：分鐘。設(shè)顧客到達間隔時間和服務(wù)時間均服從

24、指數(shù)分布。求： a)a)銀行中的平均顧客數(shù)量；銀行中的平均顧客數(shù)量； b)b)每位顧客逗留在銀行的平均時間；每位顧客逗留在銀行的平均時間；32銀行的排隊系統(tǒng)銀行的排隊系統(tǒng)解：解：a a）由已知得，本題為一個）由已知得，本題為一個 8080人人/ /小時，小時， 5050人人/ /小時的小時的M/M/2/GD/M/M/2/GD/排隊系統(tǒng)。排隊系統(tǒng)。因因 ，所以系統(tǒng)存在穩(wěn)定狀態(tài)。，所以系統(tǒng)存在穩(wěn)定狀態(tài)。pb b）因為）因為 ，所以，所以18 . 05028084. 28 . 0171. 08 . 0qL44. 484. 25080LLW （分鐘）（小時） 3 . 3055. 08044. 4W33例例5、銀行的柜員人數(shù)、銀行的柜員人數(shù)p某銀行經(jīng)理需要決策周五應該有多少柜員上班。經(jīng)理認為每位顧客在隊列中等待1分鐘，銀行就會損失0.25元。平均每分鐘有2名顧客到達銀行，每位柜員每2分鐘可以完成對一名顧客的服務(wù)。柜員的工資為45元/小時。設(shè)顧客的到達間隔時間和柜員的服務(wù)時間服從指數(shù)分布。為了最小化銀行的工資成本和延遲成本，該銀行周五應該有多少柜員上