[研究生入學(xué)考試]上海交大運籌學(xué)期末考試考研復(fù)習(xí)珍貴ppt資料適合全國高?？佳泻推谀┛荚?排隊論

1、運 籌 學(xué) 課 件,Queueing Theory,一般的排隊過程為：顧客由顧客源出發(fā)，到達服務(wù)機構(gòu)（服務(wù)臺、服務(wù)員）前，按排隊規(guī)則排隊等待接受服務(wù)，服務(wù)機構(gòu)按服務(wù)規(guī)則給顧客服務(wù)，顧客接受完服務(wù)后就離開。排隊過程的一般過程可用下圖表示。我們所說的排隊系統(tǒng)是指圖中虛線所包括的部分。,在現(xiàn)實生活中的排隊現(xiàn)象是多種多樣的，對上面所說的“顧客”和“服務(wù)員”要作廣泛的理解。它們可以是人，也可以是某種物質(zhì)或設(shè)備。排隊可以是有形的，也可以是無

2、形的。,基本概念 排隊過程的一般表示,排隊系統(tǒng)的組成和特征,盡管排隊系統(tǒng)是多種多樣的，但從決定排隊系統(tǒng)進程的因素來看，它有三個基本的組成部分，這就是輸入過程、排隊規(guī)則及服務(wù)機構(gòu)。,1)輸入過程：描述顧客來源以及顧客到達排隊系統(tǒng)的規(guī)律。包括： 顧客源中顧客的數(shù)量是有限還是無限； 顧客到達的方式是單個到達還是成批到達； 顧客相繼到達的間隔時間分布是確定型的還是隨機型的，分布參數(shù)是什么，是否獨立，是否平穩(wěn)。,

3、2)排隊規(guī)則：描述顧客排隊等待的隊列和接受服務(wù)的次序。包括： 即時制還是等待制； 等待制下隊列的情況（是單列還是多列，顧客能不能中途退出，多列時各列間的顧客能不能相互轉(zhuǎn)移）； 等待制下顧客接受服務(wù)的次序（先到先服務(wù)，后到先服務(wù)，隨機服務(wù)，有優(yōu)先權(quán)的服務(wù)）。,3)服務(wù)機構(gòu)：描述服務(wù)臺(員)的機構(gòu)形式和工作情況。包括： 服務(wù)臺（員）的數(shù)目和排列情況； 服務(wù)臺（員）的服務(wù)方式； 服務(wù)時間是確定型

4、的還是隨機型的，分布參數(shù)是什么，是否獨立，是否平穩(wěn)。,排隊模型的分類,D.G.Kendall在1953年提出了一個分類方法，按照系統(tǒng)的三個最主要的、影響最大的三個特征要素進行分類，它們是：顧客相繼到達的間隔時間分布、服務(wù)時間的分布、并列的服務(wù)臺個數(shù)。按照這三個特征要素分類的排隊系統(tǒng)，用符號（稱為Kendall記號）表示為 X/Y/Z其中X處填寫顧客相繼到達的間隔時間分布，Y處填寫服務(wù)時間的分布，Z處填寫并列的服

5、務(wù)臺個數(shù)。 例如M/M/1，表示顧客相繼到達的間隔時間為負指數(shù)分布、服務(wù)時間為負指數(shù)分布、單服務(wù)臺的模型。,后來，在1971年關(guān)于排隊論符號標(biāo)準(zhǔn)化的會議上決定，將Kendall符號擴充為： X/Y/Z/A/B/C 其中前三項意義不變。 A處填寫系統(tǒng)容量限制; B處填寫顧客源中的顧客數(shù)目; C處填寫服務(wù)規(guī)則（如先到先服務(wù)FCFS，后到先服務(wù)LCFS）。 約定，如略去后

6、三項，即指X/Y/Z/∞/∞/FCFS的情形。 后面我們只討論先到先服務(wù)FCFS的情形，所以略去第六項。,排隊系統(tǒng)的求解,對于一個排隊系統(tǒng)，運行狀況的好壞既涉及到顧客的利益，又涉及到服務(wù)機構(gòu)的利益，還有社會效果好壞的問題。為了研究排隊系統(tǒng)運行的效率、估計服務(wù)質(zhì)量、研究設(shè)計改進措施，必須確定一些基本指標(biāo)，用以判斷系統(tǒng)運行狀況的優(yōu)劣。下面介紹幾種常用的指標(biāo)。,1)隊長：把系統(tǒng)中的顧客數(shù)稱為隊長，它的期望值記作Ls。而把系統(tǒng)中排隊等待

7、服務(wù)的顧客數(shù)稱為排隊長（隊列長），它的期望值記作Lq。顯然有 隊長＝排隊長＋正被服務(wù)的顧客數(shù)。,2)逗留時間：一個顧客從到達排隊系統(tǒng)到服務(wù)完畢離去的總停留時間稱為逗留時間，它的期望值記作Ws。 一個顧客在系統(tǒng)中排隊等待的時間稱為等待時間，它的期望值記作Wq。顯然有 逗留時間＝等待時間＋服務(wù)時間。,3)瞬態(tài)和穩(wěn)態(tài) 把系統(tǒng)中的顧客數(shù)稱為系統(tǒng)的狀態(tài)?？紤]在t時刻系統(tǒng)的狀態(tài)為n的概率，它是隨時刻t而變化

8、的，用Pn(t)表示，稱為系統(tǒng)的瞬態(tài)。求瞬態(tài)解是很不容易的，一般即使求出也很難利用，因此我們常用它的極限 lim Pn(t)＝Pn t→∞稱為穩(wěn)態(tài)或稱統(tǒng)計平衡狀態(tài)的解。,統(tǒng)計平穩(wěn)條件下的記號,?n =系統(tǒng)有n個顧客時的平均到達率（單位時間平均到達的顧客人數(shù)即是平均到達率）?n =系統(tǒng)有n個顧客時的平均離開率? =對任何n都是常數(shù)的平均到達率. =

9、對任何n都是常數(shù)的平均離開率.1/? =期望到達間隔時間1/? =期望服務(wù)時間? =服務(wù)強度， 或稱使用因子, ?/(s?),統(tǒng)計平穩(wěn)條件下的記號,平均隊長,平均等待隊長,平均等待時間,平均逗留時間,Ls, Ws, Lq, Wq滿足,,所以，只需要求出Pn即可。,幾個主要概率分布一、POISSON分布,設(shè)N(t)表示在時間區(qū)間[t0,t0+t)內(nèi)到達的顧客數(shù)，是隨機變量。當(dāng)N(t)滿足下列三個條件時，我們說顧

10、客的到達符合Poisson分布。這三個條件是： (1)平穩(wěn)性 在時間區(qū)間[t0,t0+t)內(nèi)到達的顧客數(shù)N(t)，只與區(qū)間長度t有關(guān)而與時間起點t0無關(guān)。 (2)無后效性 在時間區(qū)間[t0,t0+t)內(nèi)到達的顧客數(shù)N(t)，與t0以前到達的顧客數(shù)獨立。 (3)普通性 在充分短的時間區(qū)間Δt內(nèi)，到達兩個或兩個以上顧客的概率極小，可以忽略不計，即 ∞ ∑Pn(Δt)＝o(

11、Δt) n=2,在上述三個條件下可以推出 (λt)n Pn(t)＝——— e-λt n=0,1,2,…… n!其中λ表示單位時間平均到達的顧客數(shù)，即為到達率。 不難算出，N(t)的數(shù)學(xué)期望和方差分別是： E[N(t)]＝λt Var[N(t)]＝λt,二、負指數(shù)分布,隨機變量T

12、的概率密度若是 λe-λt t≥0 fT(t)＝ 0 t?0則稱T服從負指數(shù)分布，它的分布函數(shù)是 1-e-λt t≥0 FT(t)＝ 0 t?0 T的數(shù)學(xué)期望和方差分別為：

13、 E[T]＝1/λ， Var(T)＝1/λ2 負指數(shù)分布具有下列性質(zhì)： (1)無記憶性或馬爾柯夫性，即 P{T>t+s / T>s}＝P{T>t} (2)當(dāng)顧客到達符合Poisson分布時，顧客相繼到達的間隔時間T必服從負指數(shù)分布。,,,對于Poisson分布，λ表示單位時間平均到達的顧客數(shù)，所以1/λ表示顧客相繼到達的平均間隔時間，而這正和E[T]的意義相符。

14、 服務(wù)時間符合負指數(shù)分布時，設(shè)它的概率密度函數(shù)和分布函數(shù)分別為 fv(t)＝μe-μt； Fv(t)＝1-e-μt (t≥0)其中μ表示單位時間能夠服務(wù)完的顧客數(shù)，為服務(wù)率；而1/μ表示一個顧客的平均服務(wù)時間，正是v的期望值。,指數(shù)分布性質(zhì),密度函數(shù),均值,方差,設(shè)隨機變量 T,分布函數(shù),性質(zhì)1,fT(t) 是一個嚴(yán)格下降函數(shù),性質(zhì)2,無后效性,不管多長時間(?t)已經(jīng)過去， 逗留時間的概率分布與下一個事件的相同

15、.,性質(zhì)3,幾個獨立的指數(shù)分布的隨機變量的最小有一個指數(shù)分布,幾個獨立的指數(shù)分布的隨機變量的和還是一個指數(shù)分?jǐn)?shù)的隨機變量,性質(zhì)4,指數(shù)分布,Poisson分布,服務(wù)時間的概率,在t時間內(nèi)已經(jīng)服務(wù)n個顧客的概率,排隊系統(tǒng)的狀態(tài)n隨時間變化的過程稱為生滅過程，設(shè)平均到達率為λn,平均服務(wù)率為μn,負指數(shù)分布排隊系統(tǒng)（M/M/1/∞/∞）的生滅過程可用下面的狀態(tài)轉(zhuǎn)移圖表示：,,,,,穩(wěn)態(tài)概率方程如下： λ0P0=μ1P1

16、 λn-1Pn-1+μn+1Pn+1=λnPn+μnPn,,,生滅過程,由前面的推導(dǎo)，可以求出另外的那些量的值。,最簡單的排隊系統(tǒng)的模型,最簡單的排隊系統(tǒng)：是指輸入為最簡單流，服務(wù)時間為負指數(shù)分布的排隊服務(wù)系統(tǒng),并且，此處我們假設(shè)：服務(wù)規(guī)則為：先到先服務(wù)；在多個服務(wù)站的情況，假設(shè)顧客排成一個單一的隊伍。,假定：1. 平均到達率為常數(shù)λ（對所有的n,有λn =λ ）2. 服務(wù)機構(gòu)的平均服務(wù)率也是常數(shù)

17、單個服務(wù)站時，有μn = μ，多個服務(wù)站時，若設(shè)S為并聯(lián)的服務(wù)站個數(shù)，則有,3.,即服務(wù)機構(gòu)總的服務(wù)效率應(yīng)高于顧客的平均到達率,保證系統(tǒng)最終能進入穩(wěn)定狀態(tài)。,這樣就可以把生滅過程的結(jié)論拿來用！,一、顧客源無限、隊長不受限制的排隊模型,穩(wěn)態(tài)概率方程如下： λP0=μP1 λPn-1+μPn+1=λPn+μPn設(shè)ρ=λ/μ<1，考慮到?Pn=1，解得

18、 P0=1-ρ Pn=(1-ρ) ρn , n≥1 這里的ρ稱為服務(wù)強度，也稱話務(wù)強度，它刻劃了服務(wù)機構(gòu)的繁忙程度，所以又稱服務(wù)機構(gòu)的利用率。,此時的排隊系統(tǒng)(M/M/1/∞/∞）的生滅過程可用下面的狀態(tài)轉(zhuǎn)移圖表示：,1、S＝1時，即M/M/1模型,服務(wù)系統(tǒng)的其他各項運行指標(biāo)計

19、算如下：平均隊長：,,,,,,,平均排隊長：,平均逗留時間:,平均等待時間:,再計算（1）顧客在系統(tǒng)中停留時間超過t的概率？假定一個顧客來到系統(tǒng)時，系統(tǒng)中已有n個人，則該顧客在系統(tǒng)中的停留時間應(yīng)該是系統(tǒng)對前n個顧客的服務(wù)時間加上對他的服務(wù)時間。設(shè)T1，T2，…，Tn表示前n個顧客的服務(wù)時間，Tn+1表示對該顧客的服務(wù)時間。令Sn+1=T1+T2+…+Tn+Tn+1,則,此時是愛爾朗分布,顧客在系統(tǒng)中停留時間小于t的概率（Ws－平

20、均逗留時間）,顧客在系統(tǒng)中停留時間超過t的概率,（2）已經(jīng)有人等待的情況下還要等待多久？,M/M/1 舉例,2、有S個并聯(lián)服務(wù)站時，,因為此時有,所以,因為在多個服務(wù)站的情況下，,并令n-S=j,則有,平均排隊長：,其他參數(shù)如：平均隊長Ls，平均逗留時間Ws，平均等待時間Wq，都可以通過Little公式求出。,例：某廠有大量同一型號的車床，當(dāng)該種車床損壞后或送機修車間或由機修車間派人來修理。已知該種車床損壞率服從泊松分布，平均每天2臺。

21、又機修車間對每臺損壞車床的修理時間為負指數(shù)分布的隨機變量，平均每臺的修理時間為 天。但 是一個與機修人員編制及維修設(shè)備配備好壞（即與機修車間每年開支費用K）有關(guān)的函數(shù)。已知,又已知機器損壞后，每臺每天的生產(chǎn)損失為400元，試決定使該廠生產(chǎn)最經(jīng)濟的K及,解：問題包含兩個費用：機器損壞造成的生產(chǎn)損失S1＋機修車間的開支S2，要使整個系統(tǒng)最經(jīng)濟就是S＝S1＋S2最小。以下以一個月為期計算,S1＝正在修理和待修機器數(shù)×

22、每臺每天的生產(chǎn)損失 ×每個月的工作日數(shù),例：病人到達只有一個醫(yī)生的醫(yī)院門診部的時間平均每20分鐘一個，設(shè)對每個病人的診治時間平均為15分鐘，又知道以上兩種時間均為負指數(shù)的概率分布。若該門診部希望到達的病人90%以上能在候診室找到座位，則該醫(yī)院最少應(yīng)該設(shè)置多少座位？,解：設(shè)候診室有座位C個，再加上診治中的病人的座位共有C＋1個。按照題目要求，該醫(yī)院門診部內(nèi)病人總數(shù)不多于C＋1個的概率為0.90,即,二、顧客源無限、隊長受

23、限制的排隊模型,當(dāng)系統(tǒng)的容量有限制(為M)時，設(shè)顧客的平均到達率仍為常數(shù)，但由于系統(tǒng)中已有M個顧客時，新到的顧客將自動離去，所以有,1、 S＝1時,所以有,其他指標(biāo)的計算：先計算有效輸入率,由于在隊長受限的情況下，當(dāng)達到顧客數(shù)n大于或等于M時，新來顧客會自動離去。因此雖然顧客以平均為λ的速度來到服務(wù)系統(tǒng)，但由于一部分的顧客離去，真正進入系統(tǒng)的的顧客的輸入率是小于λ的。,由于系統(tǒng)中的平均排隊的顧客數(shù)總是等于系統(tǒng)中的平均顧客數(shù)－平均正在接

24、受服務(wù)的顧客數(shù)，即：,對于隊長受限制的排隊模型，當(dāng)系統(tǒng)中有M個顧客時，新到顧客會自動離開，故不一定要求,2、 S個并聯(lián)服務(wù)站時,對于隊長受限制的排隊模型，當(dāng)系統(tǒng)中有M個顧客時，新到顧客會自動離開，故當(dāng)n<M時， 和隊長不受限時一樣，但當(dāng) 所以有,平均排隊長：,由前面方法易求出其他結(jié)果。,當(dāng)M＝S時，是一種特殊情況。因為這是一種帶損失制的服務(wù)系統(tǒng)，此時，使用前面給出的公式，且令M=S，即可得到如下結(jié)果：

25、,例：某單位電話交換臺有一臺200門內(nèi)線的總機。已知在上班的8小時內(nèi)。有20%的內(nèi)線分機平均每40分鐘要一次外線電話，80%的分機平均每2小時要一次外線電話，又知從外單位打來的電話呼叫率平均每分鐘一次，設(shè)外線通話時間平均為3分鐘，以上兩個時間均屬于負指數(shù)分布。如果要求電話接通率95%,問該交換臺應(yīng)設(shè)置多少外線？,解：來到電話交換臺的的呼喚有2類：1，各分機往外打的電話；2，從外單位打進來的電話。,第1類：,第2類：,由possion分布

26、性質(zhì)，到交換臺的總呼喚流仍是possion分布：,這是一個具有多個服務(wù)站帶損失制的服務(wù)系統(tǒng)，要使電話接通率為95%，即損失低于5%，所以,將已知數(shù)值帶入后，得出應(yīng)不少于15條。,注：計算中沒有考慮全面的因素：如外單位打來時內(nèi)線是否占用，打不通時會不停撥打等，會使得實際的電話接通率達不到95%。,M/M/1/N/? 舉例,三、顧客源有限的排隊模型,設(shè)系統(tǒng)的顧客總數(shù)為有限(為N)，當(dāng)有n個顧客在服務(wù)系統(tǒng)內(nèi)時，在服務(wù)系統(tǒng)外的潛在顧客數(shù)就減少為

27、（N-n）。若設(shè)每個顧客來到服務(wù)系統(tǒng)的時間間隔為參數(shù)λ的負指數(shù)分布的話，則根據(jù)負指數(shù)分布的性質(zhì)有λn=(N-n) λ ，因此此排隊模型可用生滅過程的發(fā)生率圖表示如下：,S＝1時,S>1時,由上圖中知道，S＝1時，有,S>1時，有,由于當(dāng)n=N時， λn=0,所以系統(tǒng)最終一定能達到穩(wěn)定狀態(tài)，所以可用求解穩(wěn)定狀態(tài)的方法進行處理。,S＝1時,由于顧客輸入率λn隨系統(tǒng)狀態(tài)而變化，因此平均輸入率可按照下式計算：,且有,S>1時，

28、,例：設(shè)有一名工人負責(zé)照管6臺自動機床。當(dāng)機床需要加料、發(fā)生故障或刀具磨損時就自動停車，等待工人照管。設(shè)平均每臺機床兩次停車的時間間隔為1小時，又設(shè)每臺機床停車時，需要工人平均照管的時間為0.1小時。以上兩項時間均服從負指數(shù)分布，試計算該系統(tǒng)的各項指標(biāo)。解：,數(shù)據(jù)見下表,所以，系統(tǒng)中平均等待照管的機床數(shù)為：,系統(tǒng)中停車的機床數(shù)為：,例：上例中改為由三個工人聯(lián)合看管20臺自動機床，其他各項數(shù)據(jù)不變，試計算該系統(tǒng)的各項指標(biāo)。,數(shù)據(jù)見下表（

29、其中n>12時，Pn較小可忽略不計）,解,所以，系統(tǒng)中平均等待照管的機床數(shù)為：,系統(tǒng)中停車的機床數(shù)為：,其他模型,M/M/c/K/K顧客來源是有限的服務(wù)系統(tǒng). 例如： 一個飯店有 X 張桌子和 Y個服務(wù)生服務(wù)來源有限的顧客.M/D/1服務(wù)時間不變的服務(wù)系統(tǒng).D/M/1確定性到達模式, 及指數(shù)分布服務(wù)時間. 例如：醫(yī)生赴約治病的時間表.M/E k/1服務(wù)服從 Erlang 分布. 例如：用相同平均時間去完成一些程序。,