運籌學排隊論1

1、,第十章 排隊論,,引 言 排隊論是研究排隊系統(tǒng)（又稱隨機服務系統(tǒng)）的數學理論和方法，是運籌學的一個重要分支。 有形排隊現象：進餐館就餐，到圖書館借書，車站等車，去醫(yī)院看病，售票處售票，到工具房領物品等現象。 無形排隊現象：如幾個旅客同時打電話訂車票；如果有一人正在通話，其他人只得在各自的電話機前等待，他們分散在不同的地方，形成一個無形的隊列在等待通電話。 排隊的不一定是

2、人，也可以是物。如生產線上的原材料，半成品等待加工；因故障而停止運行的機器設備在等待修理；碼頭上的船只等待裝貨或卸貨；要下降的飛機因跑道不空而在空中盤旋等。,,,當然，進行服務的也不一定是人，可以是跑道，自動售貨機，公共汽車等。顧客可以走向服務機構，也可以相反（如送貨上門）。 顧客——要求服務的對象。 服務員——提供服務的服務者（也稱服務機構）。 顧客、服務員的含義是廣義的。

3、 如果增添服務設備，就要增加投資或發(fā)生空閑浪費 ；如果 服務設備太少，排隊現象就會嚴重，對顧客個人和對社會都會帶來不利影響。因此，管理人員必須考慮如何在這兩者之間取得平衡，經常檢查目前處理是否得當，研究今后改進對策，以期提高 服務質量，降低成本。,,2、排隊系統(tǒng)類型：,單服務臺排隊系統(tǒng),S個服務臺，一個隊列的排隊系統(tǒng),,S個服務臺， S個隊列的排隊系統(tǒng),多服務臺串聯排隊系統(tǒng),,,隨機聚散服務系統(tǒng),隨機性——顧客到達情況與顧客接受服務的

4、時間是隨機的。 一般來說，排隊論所研究的排隊系統(tǒng)中，顧客相繼到達時間間隔和服務時間這兩個量中至少有一個是隨機的，因此，排隊論又稱隨機服務理論。,,3、排隊系統(tǒng)的組成和特征 實際中的排隊系統(tǒng)各不相同，但概括起來都由三個基本部分組成：輸入過程，排隊規(guī)則和服務機構。輸入過程—即顧客到達排隊系統(tǒng)。 顧客總體（顧客源）數：可能是有限，也可能是無限。河流上游流入水庫的水量可認為是無限的；車間內停機待修的機器顯然

5、是有限的。到達方式：是單個到達還是成批到達。庫存問題中，若把進來的貨看成顧客，則為成批到達的例子。,,顧客（單個或成批）相繼到達的時間間隔，可以是確定型的，也可以是隨機型的。這是刻劃輸入過程的最重要內容。令T0=0，Tn表示第n顧客到達的時刻，則有T0?T1 ? T2….. ? Tn ? …… 記Xn= Tn –Tn-1 n=1,2,…,則Xn是第n顧客與第n-1顧客到達的時間間隔。對于隨機型的，要知道其分布：一般假定{Xn

6、}是獨立（非關聯）同分布，并記分布函數為A(t)。{Xn}的分布A(t)常見的有：定常分布（D）：顧客相繼到達的時間間隔為確定的。如產品通過傳送帶進入包裝箱就是定常分布。最簡流（或稱Poisson)（M）：顧客相繼到達的時間間隔{Xn}為獨立的，同為負指數分布，其密度函數為：,,a(t)=,?e- ?t t?0,0 t < 0,,排隊規(guī)則排隊有限排隊——排隊系統(tǒng)中顧客數是有限的。有限排

7、隊還可以分成：損失制排隊系統(tǒng)：排隊空間為零的系統(tǒng)，即不允許排隊。（顧客到達時，服務臺占滿，顧客自動離開，不再回來）（電話系統(tǒng)）混合制排隊系統(tǒng)：是等待制與損失制結合，即允許排隊，但不允許隊列無限長。,,混合制排隊系統(tǒng)：隊長有限。即系統(tǒng)等待空間是有限的。例：最多只能容納K個顧客在系統(tǒng)中，當新顧客到達時，若系統(tǒng)中的顧客數（又稱為隊長）小于K，則可進入系統(tǒng)排隊或接受服務；否則，便離開系統(tǒng)，并不再回來。如水庫的庫容是有限的，旅館的床位是有限

8、的。等待時間有限。即顧客在系統(tǒng)中等待時間不超過某一給定的長度T，當等待時間超過T時，顧客將自動離開，不再回來。如易損失的電子元件的庫存問題，超過一定存儲時間的元器件被自動認為失效。逗留時間（等待時間與服務時間之和）有限。例：用高射炮射擊飛機，當敵機飛越射擊有效區(qū)域的時間為t時，若這個時間內未被擊落，也就不可能再被擊落了。,,損失制和等待制可看成是混合制的特殊情形，如記s為系統(tǒng)中服務臺個數，則當k=s時，混合制即為損失制；當k=?時，即

9、成為等待制。 無限排隊——顧客數是無限，隊列可以排到無限長（等待制排隊系統(tǒng)）。 當顧客到達時，若所有服務臺都被占有且又允許排隊，則該顧客將進入隊列等待。服務臺對顧客進行服務所遵循的規(guī)則通常有：先來先服務（FCFS）后來先服務（LCFS）。在許多庫存系統(tǒng)中就會出現這種情況，如鋼板存入倉庫后，需要時總是從最上面取出；又如在情報系統(tǒng)中，后來到達的信息往往更重要，首先要加以分析和利用。,,具有優(yōu)先權的服務（PS）。服務

10、臺根據顧客的優(yōu)先權的不同進行服務。如病危的病人應優(yōu)先治療；重要的信息應優(yōu)先處理；出價高的顧客應優(yōu)先考慮。隨機服務，指服務員從等待的顧客中隨機地選取其一進行服務，而不管到達的先后。如電話交換臺接通呼喚的電話就是如此。 從占有空間來看，隊列可以排在具體的處所，也可以是抽象的；有的系統(tǒng)要規(guī)定容量的，有的容量沒有限制。 從隊列的數目來看，可以是單列的，也可以是多列的；在多列的情形中，各列的顧客有的是可以互相轉移的，

11、有的不能互相轉移；有的可以中途退出，有的必須堅持到被服務為止。,,服務機制：包括：服務員的數量及其連接方式（串聯還是并聯）；顧客是單個還是成批接受服務；服務時間的分布。記某服務臺的服務時間為V，其分布函數為B(t),密度函數為b(t),則常見的分布有： 定長分布（D）：每個顧客接受的服務時間是一個確定的常數。 負指數分布（M）：每個顧客接受的服務時間相互獨立，具有相同的負指數分布：其中?>0為一常數

12、。,b(t)=,?e- ?t t?0,0 t<0,,,K階愛爾朗分布（Ek）：,b(t)=,k?(k?t)k-1(K-1)!,= e- k?t,當k=1時即為負指數分布；k ? 30,近似于正態(tài)分布。當 k?? 時，方差 ? 0 即為完全非隨機的。排隊系統(tǒng)的符號表示：“Kendall”記號：X / Y/ Z / A/B/C其中：X表示顧客相繼到達的分布； Y表示服

13、務時間的分布； Z表示服務臺個數； A表示系統(tǒng)的容量，即可容納的最多顧客數。 B表示顧客客源數目。 C表示服務規(guī)則。,,例 13-1 M /M/ 1 / ?/? M表示顧客相繼到達的時間間隔服從負指數分布； M表示服務時間為負指數分布；單個服務臺；系統(tǒng)容量為無限（等待制）的排隊模型 。例 13-2 M /M/ S / K/? 表示顧客到達的時間間隔服從負指數分

14、布； 服務時間為負指數分布；S個服務臺；系統(tǒng)容量為K的排隊模型 。當 K= S 時為損失制排隊模型；當 K= ? 時為等待制排隊模型。,,3、排隊系統(tǒng)的主要數量指標：系統(tǒng)狀態(tài)：也稱為隊長，指排隊系統(tǒng)中的顧客數（排隊等待的顧客數與正在接受服務的顧客數之和）。它的期望值記作LS。排隊長：系統(tǒng)中正在排隊等待服務的顧客數。它的期望值記作Lq 系統(tǒng)中顧客數=在隊列中等待服務的顧客數+正被服務的顧客數逗留時間：指一個顧客在系統(tǒng)中

15、停留的時間，它的期望值記作Ws。等待時間：指一個顧客在系統(tǒng)中排隊等待的時間，它的期望值記作Wq。逗留時間=等待時間 +服務時間,,4、排隊論研究的基本問題：通過研究主要數量指標在瞬時或平穩(wěn)狀態(tài)下的概率分布及數字特征，了解系統(tǒng)運行的基本特征。統(tǒng)計推斷問題：建立適當的排隊模型是排隊論研究的第一步，建立模型過程中，系統(tǒng)是否達到平穩(wěn)狀態(tài)的檢驗；顧客相繼到達時間間隔相互獨立性的檢驗，服務時間的分布及有關參數的確定等。系統(tǒng)優(yōu)化問題：又稱為

16、系統(tǒng)控制問題或系統(tǒng)運營問題，其基本目的是使系統(tǒng)處于最優(yōu)的或最合理的狀態(tài)。包括：最優(yōu)設計問題和最優(yōu)運營問題。,,5、M/M/1/?/?排隊模型 標準的M/M/1?/?模型是指適合下列條件的排隊系統(tǒng)：輸入過程——顧客源是無限的，顧客單個到來，相互獨立，一定時間的到達數服從泊松分布，到達過程已是平衡的。排隊規(guī)則——單隊，且對 隊長沒有限制，先到先服務。服務機構——單服務臺，各顧客的服務時間是相互獨立的，服從相同的負指數分布。此

17、外，還假定到達間隔時間和服務時間是相互獨立的。,,,例13-3：考慮一個鐵路列車編組站。設待編列車到達時間間隔服從負指數分布，平均每小時到達2列；服務臺是編組站，編組時間服從負指數分布，平均每20分鐘可編一組。已知編組站上共有2股道，當均被占用時，不能接車，再來的列車只能停在站外或前方站。求在平衡狀態(tài)下系統(tǒng)中列車的平均數；每一列車的平均逗留時間；等待編組的列車平均數。如果列車因站中2股道均被占用而停在站外或前方站時，每列車每小時費用為a

18、元，求每天由于列車在站外等待而造成的損失。,,解：本例可看成一個M/M/1/?/?排隊問題。 其中? =2， ? =3，?=?/?=2/3<1系統(tǒng)中列車的平均數 Ls= ?/ (1-?)=(2/3)/(1-2/3)=2（列）列車在系統(tǒng)中的平均停留時間 Ws=Ls/?= 2/2=1（小時）系統(tǒng)中等待編組的列車平均數 Lq=Ls-?= 2-2/3=4/3（列）,,列車在系統(tǒng)中的平均等待編組時間 Wq = L

19、q/ ?=(4/3)/(1/2)=2/3（小時） 每列車平均延誤（由于站內2股道均被占用而不能進站）時間為W0則W0 = WP{N>2}=W{1-P0-P1-P2} =W{1-(l-?)- (l-?) ?1 -(l-?) ?2} =1* ?3= ?3=(2/3)3=0.296（小時）故每天列車由于等待而支出的平均費用E=24?W0a=24*2*0.296*a=14.2a元,,例13-4：某修理店只

20、有一位修理工，來修理的顧客到達過程為Poisson流，平均每小時4人；修理時間服從負指數分布，平均需要6分鐘。試求：修理店空閑的概率；店內恰有3位顧客的概率；店內至少有一位顧客的概率；在店內平均顧客數；每位在店內平均逗留時間；等待服務的平均顧客數；每位顧客平均等待服務時間。,,解：本例可看成一個M/M/1/? /?排隊問題. 其中? =4， ? =1/0.1=10(人/小時）， ?= ?/?=2/5<1修理店內

21、空閑的概率 P0= 1-?= (1-2/5)=0.6店內恰有3個顧客的概率 P3= ?3(1-?)=(2/5)3(1-2/5)=0.038店內至少有1位顧客的概率 P {N?1}=1-P0=1- (1-?)= ? =2/5=0.4,,在店內平均顧客數 L= ?/ (1-?)=(2/5)/(1-2/5)= 0.67(人）每位顧客在店內平均逗留時間W=L/?=0.67/4=10分鐘等待服務的平均顧

22、客數 Lq=L-?=0.67-2/5=0.27(人)每個顧客平均等待服務時間 Wq = Lq/ ?=0.27/4=0.0675小時 =4分鐘,6、M/M/1/N/ ?/?排隊模型如果系統(tǒng)的最大容量為N，對于單服務臺的情形，排隊等待的顧客最多為N-1，在某時刻一顧客到達時，如系統(tǒng)中已有N個顧客，那么這個顧客就被的拒絕進入系統(tǒng)。,7、 M/M/1/?/M 等待制排隊模型,8、 M/M/C/?/ ? 排隊模型,,7

23、、 M/M/1/?/M 等待制排隊模型多服務臺問題，又表示為M/M/S/ ? ：顧客相繼到達時間服從參數為?的負指數分布；服務臺數為S；每個服務臺的服務時間相互獨立，且服從參數為?的負指數分布。當顧客到達時，若有空閑服務臺馬上被進行服務，否則便排成一隊列等待，等待空間為無限。,,隊長的分布 記Pn=p{N=n},n=0,1,2….為系統(tǒng)達到平衡狀態(tài)后隊長N的概率分布，對多服務臺有 ?n=?； n=0,1,2….

24、 ?n= n? n=0,1,2….s ?n= s? n=s,s+1,s+2….,,?s= ?/s= ?/s?, 當?s<1時，有,Cn=,(?/?)n n!,(?/?)s s!,(?/s?)n-s=,(?/?)n s!sn-s,n=1,2,…..s,n?s,,pn=,(p)n n!,n=1,2,…..s,?n s!sn

25、-s,n ? s,,p0,p0,,其中：p0=[?0s-1pn/n!+ ?s/s!(1- ?s)]-1當n ? s時，顧客必須等待，記C(s, ?)= ?s?pn= ?s/s!(1- ?s) p0稱為Erlang等待公式，它給出了顧客到達系統(tǒng)時，需要等待的概率。,,平均排隊長：Lq=?s?(n-s)pn = p0 ?s ?s /s!(1- ?s)2或Lq = C(s, ?) ?s / (1- ?s) 記系統(tǒng)中正在接受服務

26、的顧客平均數s,顯然s也是正在忙的服務臺平均數。S= ?0s-1npn+ s*?s?pn = ?,,平均隊長：L=平均排隊長+正在接受服務的顧客的平均數= Lq + ?對多服務臺，Little公式依然成立： W=L/? Wq=Lq/ ? =W-(1/?),,例13-5：考慮一個醫(yī)院急診室的管理問題，根據資料統(tǒng)計，急診病人相繼到達的時間間隔服從負指數分布，平均每半小時來一個；醫(yī)生