運籌學 第十章 排隊論PPT學習教案

1、會計學1第1頁/共87頁第一節(jié) 引言一、排隊系統(tǒng)的特征及排隊論排隊論(Queuing Theory)，又稱隨機服務系統(tǒng)理論(Random Service System Theory),是一門研究擁擠現(xiàn)象(排隊、等待)的科學。具體地說，它是在研究各種排隊系統(tǒng)概率規(guī)律性的基礎上，解決相應排隊系統(tǒng)的最優(yōu)設計和最優(yōu)控制問題。第2頁/共87頁排隊是我們在日常生活和生產(chǎn)中經(jīng)常遇到的現(xiàn)象。例如，上、下班搭乘公共汽車；顧客到商店購買物品；病員到醫(yī)院看??；旅客到售票處購買車票；學生去食堂就餐等就常常出現(xiàn)排隊和等待現(xiàn)象。除了上述有形的排隊之外，還有大量的所謂“無形”排隊現(xiàn)象，如幾個顧客打電話到出租汽車站要求派車，

2、如果出租汽車站無足夠車輛、則部分顧客只得在各自的要車處等待，他們分散在不同地方，卻形成了一個無形隊列在等待派車。排隊的不一定是人，也可以是物：第3頁/共87頁例如，通訊衛(wèi)星與地面若干待傳遞的信息；生產(chǎn)線上的原料、半成品等待加工；因故障停止運轉(zhuǎn)的機器等待工人修理；碼頭的船只等待裝卸貨物；要降落的飛機因跑道不空而在空中盤旋等等。顯然，上述各種問題雖互不相同，但卻都有要求得到某種服務的人或物和提供服務的人或機構。第4頁/共87頁排隊論里把要求服務的對象統(tǒng)稱為“顧客”,而把提供服務的人或機構稱為“服務員”或“服務機構”。實際的排隊系統(tǒng)可以千差萬別，但都可以一般地描述如下：顧客為了得到某種服務而到達系統(tǒng)

3、、若不能立即獲得服務而又允許排隊等待，則加入等待隊伍，待獲得服務后離開系統(tǒng)，見圖10-1至10-4第5頁/共87頁圖10-1 單服務臺排隊系統(tǒng)圖10-2 單隊列S個服務臺并聯(lián)的排隊系統(tǒng)第6頁/共87頁圖10-3 S個隊列S個服務臺的并聯(lián)排隊系統(tǒng)圖10-4 單隊多個服務臺的串聯(lián)排隊系統(tǒng)第7頁/共87頁類似地還可畫出許多其他形式的排隊系統(tǒng)，如串并混聯(lián)的系統(tǒng)，網(wǎng)絡排隊系統(tǒng)等第8頁/共87頁盡管各種排隊系統(tǒng)的具體形式不同，但都可以由圖10-5加以描述圖10-5 隨機服務系統(tǒng)通常稱上圖表示的系統(tǒng)為一隨機聚散服務系統(tǒng)，任一排隊系統(tǒng)都是一個隨機聚散服務系統(tǒng)。這里，“聚”表示顧客的到達，“散”表示顧客的離去。

4、第9頁/共87頁所謂隨機性則是排隊系統(tǒng)的一個普遍特點，是指顧客的到達情況(如相繼到達時間間隔)與每個顧客接受服務的時間往往是事先無法確切知道的，或者說是隨機的。一般來說，排隊論所研究的排隊系統(tǒng)中，顧客到來的時刻和服務臺提供服務的時間長短都是隨機的，因此這樣的服務系統(tǒng)被稱為隨機服務系統(tǒng)第10頁/共87頁小結排隊系統(tǒng)又稱隨機服務系統(tǒng)排隊系統(tǒng)又稱隨機服務系統(tǒng)有請求服務的人或物；有請求服務的人或物；有為顧客服務的人或物；有為顧客服務的人或物；顧客到達時間與接受服務時間是隨機的。顧客到達時間與接受服務時間是隨機的。結構：結構：顧客到達顧客到達-排隊排隊-服務機構服務服務機構服務-顧客離去顧客離去第11頁

5、/共87頁二、排隊系統(tǒng)的描述實際中的排隊系統(tǒng)各有不同，但概括起來都由三個基本部分組成：1輸入過程；輸入過程；2排隊及排隊規(guī)則排隊及排隊規(guī)則3服務機制服務機制第12頁/共87頁1輸入過程這是指要求服務的顧客是按怎樣的規(guī)律到達排隊系統(tǒng)的過程，有時也把它稱為顧客流一般可以從3個方面來描述一個輸入過程。(1)顧客總體數(shù)又稱顧客源、輸入源。這是指顧客的來源。顧客源可以是有限的，也可以是無限的。例如，到售票處購票的顧客總數(shù)可以認為是無限的，而車間內(nèi)停機待修得機器顯然是有限的。第13頁/共87頁(2)顧客到達方式這是描述顧客是怎樣來到系統(tǒng)的，他們是單個到達，還是成批到達。病人到醫(yī)院看病是顧客單個到達的例子。

6、在庫存問題中如將生產(chǎn)器材進貨或產(chǎn)品入庫看作是顧客，那么這種顧客則是成批到達的。第14頁/共87頁(3)顧客流的概率分布，或稱相繼顧客到達的時間間隔的分布。這是求解排隊系統(tǒng)有關運行指標問題時，首先需要確定的指標。這也可以理解為在一定的時間間隔內(nèi)到達K個顧客(K=1、2、)的概率是多大。顧客流的概率分布一般有定長分布、二項分布、泊松流(最簡單流)、愛爾朗分布等若干種。第15頁/共87頁2排隊及排隊規(guī)則排隊排隊分為有限排隊有限排隊和無限排隊無限排隊兩類。有限排隊有限排隊是指排隊系統(tǒng)中的顧客數(shù)是有限的，即系統(tǒng)的空間是有限的，當系統(tǒng)被被占滿時，后面再來的顧客將不能進入系統(tǒng)；無限排隊無限排隊是指系統(tǒng)中顧客

7、數(shù)可以是無限的，隊列可以排到無限長，顧客到達系統(tǒng)后均可進入系統(tǒng)排隊或接受服務，這類系統(tǒng)又稱為等待制排隊系統(tǒng)。第16頁/共87頁有限排隊系統(tǒng)有限排隊系統(tǒng)損失制排隊系統(tǒng)混合制排隊系統(tǒng)（排隊空間為0的系統(tǒng)）（允許排隊，但又不允許隊列無限長）第17頁/共87頁這是指如果顧客到達排隊系統(tǒng)時，所有服務臺都已被先來的顧客占用，那么他們就自動離開系統(tǒng)永不再來。典型例子是，如電話拔號后出現(xiàn)忙音，顧客不愿等待而自動掛斷電話，如要再打，就需重新拔號，這種服務規(guī)則即為損失制。損失制排隊系統(tǒng)損失制排隊系統(tǒng)（排隊空間為0的系統(tǒng)）第18頁/共87頁混合制排隊系統(tǒng)混合制排隊系統(tǒng)這是等待制與損失制相結合的一種服務規(guī)則，一般是指

8、允許排隊，但又不允許隊列無限長下去。具體說來，大致有三種： 隊長有限。當排隊等待服務的顧客人數(shù)超過規(guī)定數(shù)量時，后來的顧客就自動離去，另求服務，即系統(tǒng)的等待空間是有限的。 如旅館的床位是有限的。 等待時間有限。即顧客在系統(tǒng)中的等待時間不超過某一給定的長度T，當?shù)却龝r間超過T 時，顧客將自動離去，并不再回來。如顧客到飯館就餐，等了一定時間后不愿再等而自動離去另找飯店用餐。（允許排隊，但又不允許隊列無限長）第19頁/共87頁 逗留時間(等待時間與服務時間之和)有限。例如用高射炮射擊敵機，當敵機飛越高射炮射擊有效區(qū)域的時間為t 時，若在這個時間內(nèi)未被擊落，也就不可能再被擊落了。不難注意到，損失制和等待

9、制可看成是混合制的特殊情形，如記s為系統(tǒng)中服務臺的個數(shù)，則當K=s時，混合制即成為損失制；當K=時，混合制即成為等待制。(K為系統(tǒng)中可容納的顧客數(shù))第20頁/共87頁(2)排隊規(guī)則當顧客到達時，若所有服務臺都被占用且又允許排隊，則該顧客將進入隊列等待。例如，排隊等待售票，故障設備等待維修等。服務臺對顧客進行服務所遵循的規(guī)則通常有：先到先服務（FCFS）后到先服務（LCFS）優(yōu)先權（PS）隨機服務倉庫中迭放的鋼材，后迭放上去的都先被領走，就屬于這種情況。即當服務臺空閑時，不按照排隊序列而隨意指定某個顧客去接受服務，如電話交換臺接通呼叫電話就是一例。第21頁/共87頁3服務機制排隊系統(tǒng)的服務機制可

10、以從以下3方面來描述：服務臺數(shù)量及構成形式。從數(shù)量上說，服務臺有單服務臺和多服務臺之分。從構成形式上看，服務臺有： 單隊單服務臺式； 單隊多服務臺并聯(lián)式； 多隊多服務臺并聯(lián)式； 單隊多服務臺串聯(lián)式； 單隊多服務臺并串聯(lián)混合式 以及多隊多服務臺并串聯(lián)混合式等等。第22頁/共87頁(2) 服務方式。這是指在某一時刻接受服務的顧客數(shù)，它有單個服務和成批服務兩種。如公共汽車一次就可裝載一批乘客就屬于成批服務。(3) 服務時間的分布一般來說，在多數(shù)情況下，對每一個顧客的服務時間是一隨機變量，其概率分布有定長分布、負指數(shù)分布、K階愛爾朗分布、一般分布(所有顧客的服務時間都是獨立同分布的)等等。第23頁/共

11、87頁三、排隊系統(tǒng)的符號表示肯道爾（）分類：X / Y / Z / A / B /C 其中： X 顧客到達的分布； Y 服務時間的分布； Z 服務臺數(shù)； A 系統(tǒng)容量； B 顧客源的個體數(shù)。 C 服務規(guī)則表示分布的符號：M-負指數(shù)分布或泊松輸入；D-定長分布；Ek-k階愛爾朗分布；GI-一般獨立隨機分布；G-一般隨機分布 第24頁/共87頁例如：某排隊問題為MMSFCFS，則表示顧客到達間隔時間為負指數(shù)分布(泊松流)；服務時間為負指數(shù)分布；有s(s1)個服務臺；系統(tǒng)等待空間容量無限(等待制)；顧客源無限，采用先到先服務規(guī)則。某些情況下，排隊問題僅用上述表達形式中的前3個、4個、5個符號。如不特

12、別說明則均理解為系統(tǒng)等待空間容量無限；顧客源無限，先到先服務，單個服務的等待制系統(tǒng)第25頁/共87頁四、排隊系統(tǒng)的主要數(shù)量指標評價排隊系統(tǒng)的優(yōu)劣。評價排隊系統(tǒng)的優(yōu)劣。下面給出的這些數(shù)量指標一般都是和系統(tǒng)運行的時刻有關的隨機變量，求這些隨機變量的瞬時分布一般是很困難的。為了分析上的簡便，并注意到相當一部分排隊系統(tǒng)在運行了一定時間后，都會趨于一個平衡狀態(tài)(或稱平穩(wěn)狀態(tài))。在平衡狀態(tài)下，隊長的分布、等待時間的分布和忙期的分布都和系統(tǒng)所處的時刻無關，而且系統(tǒng)的初始狀態(tài)的影響也會消失。因此，我們在本章中將主要討論與系統(tǒng)所處時刻無關的性質(zhì)，即統(tǒng)計平衡性質(zhì)。第26頁/共87頁1、隊長與排隊長、隊長與排隊長(

13、1)隊長隊長: 系統(tǒng)中的顧客數(shù)（n）； N(t)-N-L (2)排隊長排隊長: 系統(tǒng)中排隊等待服務的顧客數(shù); Nq(t)- Nq-Lq第27頁/共87頁2、逗留時間與等待時間、逗留時間與等待時間(1)逗留時間逗留時間: 指一個顧客在系統(tǒng)中的全部停留時間； T(t)-T-W(2)等待時間等待時間: 指一個顧客在系統(tǒng)中的排隊等待時間；Tq(t)- Tq-Wq這四項主要性能指標(又稱主要工作指標)的值越小，說明系統(tǒng)排隊越少，等待時間越少，因而系統(tǒng)性能越好。顯然，它們是顧客與服務系統(tǒng)的管理者都很關注的。第28頁/共87頁2、忙期和閑期、忙期和閑期(1)忙期忙期: 是指從顧客到達空閑著的服務機構起，到服

14、務機構再次 成為空閑止的這段時間，即服務機構連續(xù)忙的時間。 (2)閑期閑期: 與忙期相對的是閑期，即服務機構連續(xù)保持空閑的時間。 在排隊系統(tǒng)中，忙期和閑期總是交替出現(xiàn)的。BBII第29頁/共87頁3、其他相關指標、其他相關指標 (1)(1)忙期服務量：忙期服務量：指一個忙期內(nèi)系統(tǒng)平均完成 服務的顧客數(shù)；(2)損失率損失率: 指顧客到達排隊系統(tǒng)，未接受服務 而離去的概率; （對損失制或系統(tǒng)容量有限而言） (3)服務強度：服務強度： = = /s/s ；第30頁/共87頁根據(jù)前面的約定，我們將主要分析系統(tǒng)的平穩(wěn)分布。于是記：Pn ：當系統(tǒng)達到統(tǒng)計平衡時處于狀態(tài)n的概率（pn(t)）n :當系統(tǒng)處于

15、狀態(tài)n時，新來顧客的平均到達率(單位 時間內(nèi)來到系統(tǒng)的平均顧客數(shù))n：當系統(tǒng)處于狀態(tài)n時，整個系統(tǒng)的平均服務率。 （單位時間內(nèi)可以服務完的顧客數(shù)）第31頁/共87頁當n為常數(shù)時，記為；當每個服務臺的平均服務率為常數(shù)時，記每個服務臺的服務率為。S表示系統(tǒng)中并行的服務臺數(shù)則當ns時，有ns ,于是令 = /s ， 稱為服務強度 （traffic intensity）第32頁/共87頁密度函數(shù)0for t00 )(tforetftT均值1)(TE方差21)(TVar隨機變量 T分布函數(shù)tetTP1)(fT(t)t1)(TE第33頁/共87頁)()0(ttTtPtTPfT(t)tttfT(t) 是一個

16、嚴格下降函數(shù)第34頁/共87頁第二節(jié) 生滅過程和Poisson過程一、生滅過程簡介一類非常重要其廣泛存在的排隊系統(tǒng)是生滅過程排隊系統(tǒng)。生滅過程是一類特殊的隨機過程，在生物學、物理學、運籌學中有廣泛的應用。第35頁/共87頁定義定義1 設N(t)，t0 為一個隨機過程。如N(t)的概率分布具有以下性質(zhì)： （1）假設N(t)= n，則從時刻 t 起到下一個顧客到達時刻止的時 間服從參數(shù)為n 的負指數(shù)分布，n=0，1，2，。 （2）假設N(t)= n，則從時刻 t 起到下一個顧客離去時刻止的時間服從參數(shù)為n的負指數(shù)分布，n=0，1，2，。 （3）同一時刻只有一個顧客到達或離去。則稱設N(t)， t0

17、 為一個生滅過程。第36頁/共87頁v顧客到達“生”；v顧客離開“滅”顧客到達顧客到達顧客離去顧客離去n ， n ，生滅過程示意圖：第37頁/共87頁為求平穩(wěn)分布，考慮系統(tǒng)在 t+t 時刻可能處的任一狀態(tài)n的概率。狀態(tài)轉(zhuǎn)移圖狀態(tài)轉(zhuǎn)移圖一般說來，得到 是比較困難的，因此通常是求當系統(tǒng)達到平穩(wěn)狀態(tài)后的狀態(tài)分布，記為 , n=0,1,2 ( )( )( )nN tp tP N tn的分布np第38頁/共87頁方式 T時刻狀態(tài)概率（t,t+t）內(nèi)發(fā)生的事件發(fā)生的概率1nPn(t)無到達，無離去 （1-nt） (1-nt) 2n -1Pn-1(t)到達一個，無離去 n-1t (1-n-1t) 3n +1

18、Pn+1(t)無到達，離去一個(1-n+1t) n+1t 4nPn(t)到達一個，離去一個 (nt) (nt) 各種方式發(fā)生概率表各種方式發(fā)生概率表第39頁/共87頁方式1，2，3，4互不相容且完備，于是：111111()( ) (1)(1)( ) ()(1)( ) (1)()( ) ()()nnnnnnnnnnnnnP ttP tttPtttPtttP ttt0()()( )limnnntdP ttP ttP td tt1111( )( )()( )nnnnnnnPtP tPtt2項都變?yōu)榱沩椂甲優(yōu)榱銓ι鲜角髮в校旱?0頁/共87頁當n=0時，只有方式1和3，4發(fā)生，且方式1中無離去的概率為

19、1，則:00011( )( )( )dP tP tP tdt 第41頁/共87頁我們假設系統(tǒng)是穩(wěn)態(tài)的，即與時刻無關，于是可得：( )0ndPtdt00110PP1111()0nnnnnnnPPPn=1,2,3.00110PP0101()PP0011122()0PPP1111122()0PPP012011122()PPP 第42頁/共87頁繼續(xù)迭代：120011.nnnnnPP記12011.nnnnnC則平穩(wěn)狀態(tài)的分布為：0nnPC P如何求P0?第43頁/共87頁由概率分布的要求：01nnP0111nnCP有：0111nnPC于是：第44頁/共87頁小結120011.nnnnnPP 0111n

20、nPC系統(tǒng)達到平穩(wěn)狀態(tài)后的狀態(tài)分布-Pn第45頁/共87頁舉例某小型超市有一個收款臺。交款顧客以每小時30人的負指數(shù)分布到達。當收款臺前只有一名顧客時，有一名收款員單獨服務，收款時間為平均的負指數(shù)分布；當有2名或以上顧客時，將增加一名助手共同為顧客服務，收款時間將縮短至平均1min的負指數(shù)分布。求 收款臺前有n 名顧客的概率Pn01.30/nh人16040/1.5h人260.60/1nh人第46頁/共87頁解： 1011112.303 1( ).(40)(60)4 2nnnnnnC n=1,2.0111113111.( )42nnnnPC=則有由級數(shù)可知：11nna q當|q| 0稱為過程N(

21、t)的強度，而o(t)為當t-0時關于t 的高階無窮小。( ,)1()P N t tttot00( )( )( , )( ),0N tN tN t tN t t 表示在時間間隔0,t內(nèi)出現(xiàn)的質(zhì)點數(shù)注：第49頁/共87頁（2） 獨立性任意兩個不相交區(qū)間內(nèi)顧客到達情況相互獨立（3） 普通性在 t, t+t 內(nèi)多于一個顧客到達的概率為()ot亦即對于充分小的t，在 t, t+t 內(nèi)出現(xiàn)2個或2個以上質(zhì)點的概率與出現(xiàn)一個質(zhì)點的概率相比可以忽略不計。則稱 N(t), t 0 為Poisson過程（強度為 ）。()otj=2P N(t, t+ t)=j第50頁/共87頁定理1 設N(t)為時間 0, t

22、內(nèi)到達系統(tǒng)的顧客數(shù)，則 N(t), t 0 為Poisson過程的充分必要條件是：()( )!nttP N tnenn=1,2定理1說明，如果顧客的到達為Poisson流的話，則到達顧客數(shù)的分布恰為Poisson分布。第51頁/共87頁舉例顧客按泊松流到達餐廳，平均每小時20人，在上午11：07餐廳內(nèi)有18人試求：到11：12餐廳內(nèi)有20名顧客的概率分析：依題意知 20（人（人/小時）小時）()( )!nttP N tnen由公式可知：21(20)121(20)112 ()20.2623122!P Ne在（1/12）h內(nèi)到達顧客2人的概率為：第52頁/共87頁但無論是從Poisson過程的定義

23、，還是根據(jù)其概率分布去對顧客的到達情況進行分析，都有許多不便之處。實際問題中比較容易得到和進行分析的往往是顧客相繼到達系統(tǒng)的時刻，或相繼到達的時間間隔。第53頁/共87頁定理2設N(t)為時間 0, t 內(nèi)到達系統(tǒng)的顧客數(shù)，則 N(t), t 0 為參數(shù)為的Poisson過程的充分必要條件是：相續(xù)到達時間間隔服從相互獨立的參數(shù)為的負指數(shù)分布。定理2說明，顧客相續(xù)到達時間間隔服從相互獨立的參數(shù)為的負指數(shù)分布，與到達過程為參數(shù)的Poisson過程是等價的。第54頁/共87頁舉例某排隊系統(tǒng)，顧客到達為泊松流，平均1人/h。假如有一名顧客于中午12點到達該排隊系統(tǒng)情況下。試求：下一名分別于下午1點前、

24、12點間、2點后到達的概率。第55頁/共87頁分析：因顧客到達為泊松流，則說明顧客到達時間間隔T服從負指數(shù)分布，故T的概率密度fT(t)為：0( )00tTetftt（1）因下一名顧客在下午1:00前到達，有 0 T 1,則1100(01)0.6321ttPTe dte （2）下一名顧客在下午1:002:00之間達到，即 1 T 2,則2200(2)1(2)11 0.1353ttP TP Te dte 第56頁/共87頁第三節(jié) M/M/s等待制排隊模型一、單服務臺模型M/M/1/ 是指：顧客的相繼到達時間服從參數(shù)為的負指數(shù)分布，服務臺數(shù)為1，服務時間服從參數(shù)為的負指數(shù)分布，系統(tǒng)空間無限，允許無

25、限排隊。第57頁/共87頁1、隊長的分布由n =( n=0，1，2，) n =( n=0，1，2，)記 =/并設 4)；(7)在六天工作日內(nèi)系統(tǒng)中沒有顧客的小時數(shù)； (8)若決定當顧客平均逗留時間超過半個小時時，就應增加一個售票窗口，試問這相當于要求顧客的平均到達率是原有的幾倍？舉例第71頁/共87頁解：按題意可知=24人人/小時，小時，=40人人/小時，小時，（1）010 .4P（2）1 . 5 ()1L人（3）1W0.0625 =3.75 L小時分鐘（4）220.91()qL 人（5）W0.03752.25qqL小時分鐘第72頁/共87頁（6）550110.0781p 4nn=0p(L 4

26、)=1-p（7）因每天系統(tǒng)內(nèi)沒有顧客的小時數(shù)為8p0小時,故一周六天工作日內(nèi)沒有顧客的小時數(shù)為小時.（8）當1112W時1=38,于是138/241.58第73頁/共87頁3、忙期和閑期在平衡狀態(tài)下，忙期B和閑期I一般均為隨機變量，求它們的分布比較麻煩。因此我們一般考慮平均忙期 和平均閑期 BI第74頁/共87頁由于忙期和閑期出現(xiàn)的概率分布為和和1,所以在一段時間內(nèi)可以認為忙期和閑期的總長度之比為:1又因為忙期和閑期是交替出現(xiàn)的，所以在充分長的時間里，它們出現(xiàn)的平均次數(shù)應是相同的。于是，忙期的平均長度 和閑期的平均長度 之比也應是BI:11BI第75頁/共87頁1BI又因為在到達為Poisson流時，根據(jù)負指數(shù)分布的無記憶性和到達與服務相互獨立的假設，容易證明從系統(tǒng)空閑時刻起到下一個顧客到達時刻止（即閑期）的時間間隔仍服從參數(shù)為的負指數(shù)分布，且與到達時間間隔相互獨立。因此，平均閑期應為111.11BI 第76頁/共87頁11.11BI