排隊論在實際當中的應(yīng)用

1、第一章排隊論問題的基本理論知識排隊是日常生活中經(jīng)常遇到的現(xiàn)象，本章將介紹排隊論的一些基本知識和常見的 排隊論的模型，使我們對排隊論有一個基本的認識。1.1 預(yù)備知識下圖是排隊過程的一般模型：各個顧客由顧客源（總體）出發(fā)，到達服務(wù)機構(gòu)（服務(wù)臺、服務(wù)員）前排隊等候接受服務(wù)，服務(wù)完成后離開。我們說的排隊系統(tǒng)就是圖中虛線所包括的部分顧客源顧客到達排隊規(guī)則排隊系統(tǒng)示意圖一般的排隊系統(tǒng)都有三個基本組成部分：輸入過程；排隊規(guī)則；服務(wù)機構(gòu)。1輸入過程輸入過程考察的是顧客到達服務(wù)系統(tǒng)的規(guī)律。可以用一定時間內(nèi)顧客到達數(shù) 或前后兩個顧客相繼到達的間隔時間來描述，一般分為確定型和隨機型兩種。對 于隨機型的情形，要知道

2、單位時間內(nèi)的顧客到達數(shù)或到達的間隔時間的概率分 布。2. 排隊規(guī)則排隊規(guī)則分為等待制、損失制和混合制三種。當顧客到達時，所有服務(wù)機構(gòu) 都被占用，貝U顧客排隊等候，即為等待制。在等待制中，為顧客進行服務(wù)的次序 可以是先到先服務(wù)，或后到先服務(wù)，或是隨機服務(wù)和有優(yōu)先權(quán)服務(wù)。如果顧客來 到后看到服務(wù)機構(gòu)沒有空閑立即離去，則為損失制。有些系統(tǒng)因留給顧客排隊等 待的空間有限，因此超過所能容納人數(shù)的顧客必須離開系統(tǒng)，這種排隊規(guī)則就是 混合制。3. 服務(wù)機構(gòu)可以是一個或多個服務(wù)臺。服務(wù)時間一般也分成確定型和隨機型兩種。但大 多數(shù)情形服務(wù)時間是隨機型的。對于隨機型的服務(wù)時間，需要知道它的概率分布。1.2 模型理

3、論分析1.2.1 模型分類排隊模型的表示：X/Y/Z/A/B/CX顧客相繼到達的間隔時間的分布；丫一服務(wù)時間的分布；M負指數(shù)分布、D確定型、Ek k階愛爾朗分布。Z服務(wù)臺個數(shù)；A系統(tǒng)容量限制（默認為）；B顧客源數(shù)目（默認為）；C服務(wù)規(guī)則（默認為先到先服務(wù)FCFS）。1.2.2 模型求解一個實際問題作為排隊問題求解時，只有顧客到達的間隔時間分布和服務(wù)時 間的分布須要實測的數(shù)據(jù)來確定，其他的因素都是在問題提出時給定的。并且必 須確定用以判斷系統(tǒng)運行優(yōu)劣的基本數(shù)量指標，解排隊問題就是首先求出這些數(shù) 量指標的概率分布或特征值。這些指標通常是：（1 ）隊長：系統(tǒng)中排隊等待服務(wù)和正在服務(wù)的顧客總數(shù)，其期望

4、值記為Ls ；排隊長（隊列長）：系統(tǒng)中排隊等待服務(wù)的顧客數(shù)，其期望值記為Lg ；系統(tǒng)中顧客數(shù)=在隊列中等待服務(wù)的顧客數(shù) 田 正被服務(wù)的顧客數(shù)（2）逗留時間：一個顧客在系統(tǒng)中停留時間，包括等待時間和服務(wù)時間，其 其期望值記為Ws ；等待時間：一個顧客在系統(tǒng)中排隊等待時間，其期望值記為 Wg ； 逗留時間=等待時間+服務(wù)時間（3）忙期：從顧客到達空閑服務(wù)機構(gòu)起到服務(wù)機構(gòu)再次為空閑這段時間長度； 系統(tǒng)狀態(tài)：即指系統(tǒng)中的顧客數(shù)；狀態(tài)概率：用Pn t表示，即在t時刻系統(tǒng)中有n個顧客的概率；要解決排隊問題，首先要確定排隊系統(tǒng)的到達間隔時間分布與服務(wù)時間分 布。要研究到達間隔時間分布與服務(wù)時間分布需要首先根

5、據(jù)現(xiàn)有系統(tǒng)原始資料統(tǒng) 計出它們的經(jīng)驗分布，然后與理論分布擬合，若能對應(yīng)，我們就可以得出上述的 分布情況。1經(jīng)驗分布經(jīng)驗分布是對排隊系統(tǒng)的某些時間參數(shù)根據(jù)經(jīng)驗數(shù)據(jù)進行的統(tǒng)計分析，并依 據(jù)統(tǒng)計分析結(jié)果假設(shè)其統(tǒng)計樣本的總體分布，選擇合適的檢驗方法進行檢驗，當 通過檢驗時，我們認為時間參數(shù)的經(jīng)驗數(shù)據(jù)服從該假設(shè)分布。2、泊松分布下面我們在一定的假設(shè)條件下，推出顧客的到達過程就是一個泊松過程。若設(shè)N t表示在時間區(qū)間0,t)內(nèi)到達的顧客數(shù)(t0) ，Pn以2表示在時間區(qū)間ti,t2 (t2t1)內(nèi)有n( 0)個顧客到達的概率，即R ti ,t2P N t2N tin(t2t1 ， n 0)當Pn ti,t

6、2符合于下述三個條件時，我們說顧客到達過程就是泊松過程。(1) 再不相重疊的的時間區(qū)間內(nèi)顧客到達數(shù)是相互獨立的。(2) 對于足夠小的 t，在時間區(qū)間t，t+ t)內(nèi)有1個顧客到達的概率為P1 t,t t t t (入0是常數(shù)，稱為概率強度)。(3) 對充分小的 t,在時間區(qū)間t,t+ t )內(nèi)有2個或2個以上顧客到達的概率是 t 一高階無窮小，即Pn t,t ttn 2為了求Pn t，即R 0,t，需要研究它在時刻t到t+ t時刻的改變量，也就是要建立R t的微分方程。就可以得到：nR t 丄 I t t0，n=0,1,2,n!負指數(shù)分布設(shè)T為時間間隔，分布函數(shù)為Ft t P T t，即：Ft

7、 t P T t o此概率等 價于在0 , t）區(qū)間內(nèi)至少有1個顧客到達的概率。沒有顧客到達的概率為：P0 t I七，貝U Ft t 1 P0 t 1 I七（t0），其概 率密度函數(shù)為：fT t 吐 I t （t0）dt由前知，入表示單位時間內(nèi)顧客平均到達數(shù)，這里1/入表示顧客到達的平均間隔時間，兩者是吻合的。下面我們再談一下服務(wù)時間的分布：對顧客的服務(wù)時間V,實際是系統(tǒng)處于忙期時兩顧客相繼離開系統(tǒng)的時間間隔， 一般地也服從負指數(shù)分布，即：fv t 1 I t fV t I t。其中： 表示單位時間內(nèi)能被服務(wù)完成的顧客數(shù)，即平均服務(wù)率。1/表示一個顧客的平均服務(wù)時間。令一則P稱為服務(wù)強度。第二

8、章單服務(wù)員排隊模型在自動存取款機服務(wù)中的應(yīng)用2.1理論分析1.穩(wěn)態(tài)概率Pn t的計算已知顧客到達服從參數(shù)為入的泊松過程，服務(wù)時間服從參數(shù)為卩的負指數(shù)分布在間刻t+ t，系統(tǒng)中有n個顧客不外乎有下列四種情況。情況時刻的t顧客區(qū)間(t, t+ t)時刻t+ t的顧客(t, t+ t)的概率0, t+ t的概率(略去(t)到達離去AnXXn1-入t+ ( t)1卩t+ ( t)Pn(t)(1-入t)(1- 1 t)Bn+1XVn1-入t+ ( t)卩 t+ ( t)Pn+1(t)(1-入t)( 1 t)Cn-1VXn入 t+ ( t)1-1t+ ( t)Pn-1 (t)(入t)(1- 1 t)DnV

9、Vn入t+ ( t)1t+ ( t)Pn(t)(入t)( 1 t)由于這四種情況是互不相容的，所以Pn(t+ t)應(yīng)是這四項之和，將所有的高階無窮小合并，則有：Pn tt P t 1 t t Pm t t R i t t t令厶t -0,得關(guān)于Pn(t)的微分差分方程：dtPi 1 tPn i tdPn t當n=0時，只有表中的（A）、（B）兩種情況。F0 t tF0 1 t P t 1 t t所以dFn(t)dtdF0(t)dtPnl(t)Pn l(t)(P(t)Po(t)Pn(t)(1)穩(wěn)態(tài)時，Pn（t）與時間無關(guān)，可以寫成Pn,它對時間的導數(shù)為0,所以由、兩式得：Pn 1Pn 1Pn 。

10、 (3)YPoR 0 (4)上式即為關(guān)于Pn的差分方程。由此可得該排隊系統(tǒng)的狀態(tài)轉(zhuǎn)移圖:這種系統(tǒng)狀態(tài)（n）隨時間變化的過程就是生滅過程，它可以描述細菌的生滅過程n得到：Pn- RnR (5)-1 （否則排隊無限遠，無法服務(wù)完）P0 1Pn1上式就是系統(tǒng)穩(wěn)態(tài)概率，以它為基礎(chǔ)可以算出系統(tǒng)的運行指標2.系統(tǒng)的運行指標計算（1）系統(tǒng)中的平均顧客數(shù)（隊長期望值 Ls）:Ls n Pnn 1(0 P 1) 隊列中等待的平均顧客數(shù)Lq （隊列長期望值）：(8)2Lq n 1 Pnn 1 1 n Lsn 1n 11(3)顧客在系統(tǒng)中的平均逗留時間 WsWs（4）顧客在隊列中的等待時間的期望值 Wq :1 1

11、1Wq WsLqW3.系統(tǒng)的忙期與閑期：系統(tǒng)處于空閑狀態(tài)的概率：Po 1系統(tǒng)處于繁忙狀態(tài)的概率：P N 01 P02.2實例2.2.1問題提出與模型說明問題提出顧客排隊等待接受服務(wù)，在任何一個服務(wù)系統(tǒng)中都是不可避免的。在存取款機排 隊等待取錢或存錢的排隊問題也非常嚴重，為此，這里擬用排隊論的理論和方法，建 立評價指標，通過實例來探究如何提高工作效率？如何使系統(tǒng)更加優(yōu)化？模型說明某街道口只有一個自動存取款機，從而該種情況是單列單服務(wù)臺的情況，即為M/M/1模型的情況。2.2.2調(diào)查方法及數(shù)據(jù)處理調(diào)查內(nèi)容（1）顧客到達時間。（2）服務(wù)時間。調(diào)查方法顧客到達的頻率與時間段有關(guān)，一般在 9： 0010

12、: 30和下午2： 3O-4： 00顧客到 達率比其它的時間高。我們把時間分成兩段，考慮 08: 009： 00、9： 00- 1O 00的 情況，分別代表了一般情況和繁忙時的情況。(1服務(wù)時間：顧客開始用自動存取款機到服務(wù)完成。(2顧客到達時間：顧客進入排隊系統(tǒng)排隊。以上兩項調(diào)查，抽樣的時間均是分散的、隨機的。不可連續(xù)和集中抽樣。具體數(shù)據(jù)如下：其中，顧客編號i，到達時間T，服務(wù)時間S，到達間隔ti，排隊等待時間Wi表1 08 : 009： 00的統(tǒng)計123456789101112Ti028121925293442495460S325731624294ti23476458756wi010110

13、010003表2 09 : 0010： 00的統(tǒng)計12345678910111213141510Ti0269111519222836414548505660Si3247233251654325ti243344368543264wi01026544000246312.2.3模型求解1、根據(jù)表1計算得：平均時間間隔為60 11 5.45分鐘人平均到達率為12 60=0.2人分鐘平均服務(wù)時間為48 12=4.00分鐘；人平均服務(wù)率為12 48=0.25人j分鐘2、根據(jù)表2計算得：平均時間間隔為60 17 3.53分鐘人平均到達率為16 60=0.27人.分鐘平均服務(wù)時間為57 16=3.56分鐘；人

14、平均服務(wù)率為16 57=0.25人分鐘把以上兩表結(jié)合起來為表3,分析服務(wù)時間的分布規(guī)律，求出均值和方差。表3服務(wù)時間和頻數(shù)服務(wù)時間X12345679頻率P27644221服務(wù)時間的期望值為:X X p 222736445462729128 3.82服務(wù)率期望值：2822273644546272910.262.2.4討論理論上講，顧客到達會形成泊松流，因為：（1）在不相重疊的時間內(nèi)顧客到達數(shù)是 相互獨立的，即無后效性；（2）對于充分小的時間區(qū)間內(nèi)有一個顧客到達的概率與時刻 無關(guān)，而與區(qū)問長成正比；在我們把時問段分開之后來分析，這一點也是滿足的；（3）對于充分小的時間區(qū)間，有2個或2個以上顧客到達

15、的概率極小。顧客到達滿足以上三 個條件，形成泊松流；所以顧客到達率服從負指數(shù)分布。而服務(wù)時問可看作服從正態(tài) 分布。然而在統(tǒng)計數(shù)據(jù)比較少的情況下，并不能得出一一般規(guī)律，來精確的算出參數(shù) （到達率）和（服務(wù)率）。本文對此問題只做簡單的分析。從表1中可以看出，在8： 00 9： 00時間區(qū)問內(nèi)，有12個顧客到達，其中有5 個顧客必須等待，平均等待 Wq1 1 1 1+3 12 0.58分鐘。而在表2中可以得出，在9： 0010： 00時間區(qū)間內(nèi)，有16個顧客到達，有11個顧客必須等待，平均 等待時間：Wq 1 2 6 5 4+4+2+4+6+3+1 16 2.375 分鐘。根據(jù)以上分析，在8： 00

16、 9： 00時間區(qū)間內(nèi)，顧客平均到達率0.2人分鐘，平均服務(wù)率是0.25人:分鐘，在9： 00 10: 00時問區(qū)問內(nèi)分別為0.27人，分鐘和0.28人，分鐘?？梢钥闯?，平均服務(wù)律是高于平均到達率的。但是，通過表3的數(shù)據(jù)分析，在8： 0010: OO寸間區(qū)間內(nèi)平均服務(wù)率為0.26人分鐘，由于表3中的數(shù)據(jù)量比較 大，所以更具有代表性。如果這樣分析，平均服務(wù)率就小于9： 0010: O的顧客平均到達率0. 27,這樣就會使排隊越來越長而直到高峰期過后才能得到緩解。我們認為在 這個系統(tǒng)中，當平均等待時間超過1分鐘，系統(tǒng)被視為效率低下，而低于1分鐘被視為 系統(tǒng)有閑置。通過以上分析，在9: 0010:

17、00時間區(qū)間內(nèi)，等待問題比較嚴重，而在 8; 00 9: 00系統(tǒng)有閑置現(xiàn)象。現(xiàn)實中，合理的把等待時間控制在1 ,1 內(nèi)很難（為很小的數(shù)）。2.3MM1模型中的最優(yōu)服務(wù)率問題已知有設(shè)進入系統(tǒng)的顧客單位時間帶來的損失為d ,單位時間服務(wù)臺每服務(wù)一位顧客的服務(wù)成本為C2,則單位時間總費用的期望值為：C( ) c1L( ) c2c1c2dCC2d(2)2解得:/ 1最優(yōu)服務(wù)率隨著進入系統(tǒng)的顧客數(shù)和損失費G的增加而增加，隨著服務(wù)成本C2的增加而減小某生產(chǎn)廠家有多臺機器，每臺機器連續(xù)運轉(zhuǎn)的時間服從指數(shù)分布，平均為1小時, 每臺故障機器的損失費為3200元/小時.有1個維修工人，每次維修時間服從指數(shù)分布，

18、 每臺故障機器的修理費用為100元/小時,求最優(yōu)的每臺機器維修時間。由題意知：最優(yōu)服務(wù)率為：5（臺/小時）G !3200 c212 100即最優(yōu)的機器維修時間為：1 10.2小時12分鐘5第三章 中式快餐店排隊系統(tǒng)的優(yōu)化3.1 理論分析當系統(tǒng)容量最大為N時，排隊系統(tǒng)中多于N個的顧客將被拒絕。當N=1時，即 為瞬時制；NX時，即為容量無限制的情況。顧客 被拒絕N432排隊系統(tǒng)服務(wù)臺現(xiàn)在研究系統(tǒng)中有n個顧客的概率Pn t .對于F0 t ,前面的式子仍然成立，當n=1,2,N-1時，也仍能成立。dPN（t）dtPN （t）PN 1 （t）但當n=N時，有下面兩種情況:情況時刻t的顧客區(qū)間t, t+

19、 t時刻t+ t的顧客數(shù)概率AN無離去（冃疋不到達）NPN（t） （1-小 t）BN-1一人到達（無離去）NPN-1（t）入 tPN（tt）PN（t）（1 t）Fn 1（t）t其狀態(tài)轉(zhuǎn)移圖為N-1在穩(wěn)態(tài)情況下有:Pn 1P)Pn 1PnP(Pn0)Pn0P0解得：Pn1111F面計算其運行指標:（1）平均隊長Ls：LsPn(pM 1,n c時），n譏nc由上圖知，當nW c時，顧客被服務(wù)離去的速率為n ,當nc時，為c ，故可得差分方程：(n 1) Pn 1cPn 1PiPoPn 1 (nPn 1 (C)巳)Pn(1c)這里： P 1 , p 1i 0利用遞推法解該差分方程可求得狀態(tài)概率為:當

20、(n c），Pn()nn c 1c! cPo系統(tǒng)的運行指標為:LsLqLsLqn(n c)Fc 1(c )c c!(1)LsWqLq4.2實例4.2.1 問題提出排隊論，就是對排隊現(xiàn)象進行數(shù)學研究的理論，也稱隨機服務(wù)理論，是運籌學中 一個獨立的分支。作為一種工具或方法，已在許多行業(yè)的管理領(lǐng)域包括醫(yī)院的管理領(lǐng) 域應(yīng)用。門診注射室的服務(wù)工作，是一種隨機性服務(wù)，即患者的到達時間、到達數(shù)量、注 射所用時間，都是一種隨機現(xiàn)象。這種服務(wù)以什么指標才能比較客觀地表示、反映注 射室的工作質(zhì)、工作效率？如何評價注射室的人員、設(shè)備配備的合理性？為此 ，筆者 擬用排隊論的理論和方法，建立評價指標，為尋求既不使患者排

21、隊成龍，又不浪費醫(yī) 院人力物力的最優(yōu)方案，提供科學依據(jù)，使注射室管理從經(jīng)驗管理轉(zhuǎn)為科學管理。4.2.2調(diào)查方法及數(shù)據(jù)處理調(diào)查內(nèi)容：（1）單位時間內(nèi)到達的患者數(shù)。（2）服務(wù)時間。調(diào)查方法（1）服務(wù)時間：從某患者進人注射室開始記時，到該患者接受注射后走出注射室 止。共隨機記錄了 593人次的服務(wù)時間。單位時間內(nèi)到達的患者數(shù)：以5分鐘為一個時間單位，任意選取若干個時間單 位，記錄每個5分鐘到達的患者數(shù)。共隨機抽取了 168個時間單位。以上兩項調(diào)查，抽樣的時間均是分散的、隨機的，不可連續(xù)和集中抽樣。調(diào)查資 料經(jīng)統(tǒng)計處理后如下：1、單位時間內(nèi)到達的患者數(shù)單位時間（5分鐘）內(nèi)到達的患者數(shù)（人）頻數(shù)概率06

22、0.041150.092300.183340.204430.265160.096100.06790.05840.02910.01合計1681.002、服務(wù)時間服務(wù)時間（分鐘）頻數(shù)概率1 :1700.292:2030.343:1520.264：560.095:60.016:60.01合計5931.00經(jīng)曲線擬合檢驗，服務(wù)時間的概率分布服從負指數(shù)分布，單位時間內(nèi)到達患者數(shù) 的概率分布服從泊松分布。從而求出排隊系統(tǒng)的兩個重要參數(shù)，患者平均到達率和 平均服務(wù)率。又因注射室內(nèi)有兩個注射凳一服務(wù)臺 C=2故符合排隊論中M/M/C型排 隊模型。應(yīng)用M/M/C型計算公式計算各項指標4.2.3模型求解（1基本參

23、數(shù)1、 患者平均到達率0.71人分鐘2、 平均服務(wù)率=0.45人:分鐘（2）注射室運行狀態(tài)指標（C=2）1、服務(wù)強度0.712 0.450.79說明注射室有79%勺時間是忙期，21%勺時間是空閑的。2、空閑概率：即注射室沒有病人的概率。C 1K丄C!0 11.581.580! 1!21.5812!1 0.790.12(3)反映患者排隊情況指標隊列長：等待注射的患者數(shù)。C期望值Lq C! 12P02.68 人隊長：隊列長+正在接受注射的患者數(shù)。期望值 Ls Lq C 2.68 1.58 4.26平均等待時間WqLq2.680.713.77分鐘4 、平均逗留時間1 Ws Wq3.77 2.22 5

24、.99 分鐘現(xiàn)假設(shè)只配備一名護士負責注射,即C=1,那么服務(wù)強度=24=1.58。在排隊0.45論中，當1時，說明系統(tǒng)處于超負荷狀態(tài)，將會持續(xù)出現(xiàn)排隊成龍現(xiàn)象。故此時不可取的。4.2.4討論1、排隊論的應(yīng)用，可以為合理使用人力、物力提供客觀依據(jù)。由下表可見注射室現(xiàn)有的服務(wù)臺C=2時，注射室有71%勺時間被利用，在等注射的 人數(shù)為2.68個，等待時間為3.77分鐘。如果服務(wù)臺增為3個時，注射室將53%勺時間被 利用，排隊等待的平均人數(shù)小于1,平均等待時間不足半分鐘。若服務(wù)臺增為4個，排 隊人數(shù)和排隊時間幾乎為0,但是注射室被利用的時間只有39%, 61%勺時間處于空閑, 造成人力浪費。因此，設(shè)兩個服務(wù)臺，基本合理