第六章排隊論模型

第六章排隊論模型1第1頁，共67頁。排隊論簡介：排隊論(QueuingTheory)，又稱隨機服務系統(tǒng)理論(RandomServiceSystemTheory),是運籌學的一個主要分支，是一門研究擁擠現(xiàn)象(排隊、等待)的科學。具體地說，它是在研究各種排隊系統(tǒng)概率規(guī)律性的基礎(chǔ)上，解決相應排隊系統(tǒng)的最優(yōu)設計和最優(yōu)控制問題。主要包含以下三個方面的研究內(nèi)容：(1)性態(tài)問題，即研究各種排隊系統(tǒng)的概率規(guī)律性，如隊長、等待時間、忙期等要素滿足的分布。有瞬態(tài)和穩(wěn)態(tài)兩種情況。(2)最優(yōu)化問題，包括最優(yōu)設計下的靜態(tài)最優(yōu)和現(xiàn)有排隊系統(tǒng)的最優(yōu)運營下的動態(tài)最優(yōu)。(3)排隊系統(tǒng)的統(tǒng)計推斷，即判斷一個給定的排隊系統(tǒng)符合何種模型，以便進一步根據(jù)排隊理論進行分析研究。

前言2第2頁，共67頁。

起源于1909年在丹麥哥本哈根電子公司工作的電話工程師A.K.Erlang(A.K.愛爾朗)對電話通話擁擠問題的研究工作，其開創(chuàng)性論文---概率論和電話通訊理論則標志此理論的誕生。表明了排隊論的發(fā)展最早是與電話，通信中的問題相聯(lián)系的，并到現(xiàn)在也還是排隊論的傳統(tǒng)的應用領(lǐng)域。近年來在計算機通訊網(wǎng)絡系統(tǒng)、交通運輸、醫(yī)療衛(wèi)生系統(tǒng)、各類生產(chǎn)服務、庫存管理等等各領(lǐng)域中均得到廣泛的應用。排隊論歷史：

排隊是我們在日常生活和生產(chǎn)中經(jīng)常遇到的現(xiàn)象。例如：搭乘公共汽車；顧客到商店購買物品；病員到醫(yī)院看?。宦每偷绞燮碧庂徺I車票；學生去食堂就餐等就常常出現(xiàn)排隊和等待現(xiàn)象。除了上述有形的排隊之外，還有大量的所謂“無形”排隊現(xiàn)象，如幾個顧客打電話到出租汽車站要求派車，如果出租汽車站無足夠車輛、則部分顧客只得在各自的要車處等待，他們分散在不同地方，卻形成了一個無形隊列在等待派車。排隊的不一定是人，也可以是物：例如：通訊衛(wèi)星與地面若干待傳遞的信息；生產(chǎn)線上的原料、半成品等待加工；因故障停止運轉(zhuǎn)的機器等待工人修理；碼頭的船只等待裝卸貨物；要降落的飛機因跑道不空而在空中盤旋等等。排隊論具體事例：

3第3頁，共67頁。

上述事例中的各種問題雖互不相同，但卻都有要求得到某種服務的人或物和提供服務的人或機構(gòu)。排隊論里把要求服務的對象統(tǒng)稱為“顧客”,而把提供服務的人或機構(gòu)稱為“服務臺”或“服務員”。不同的顧客與服務組成了各式各樣的服務系統(tǒng)。顧客為了得到某種服務而到達系統(tǒng)、若不能立即獲得服務而又允許排隊等待，則加入等待隊伍，待獲得服務后離開系統(tǒng)。4第4頁，共67頁。模型1單服務臺排隊模型排隊模型及類型根據(jù)顧客到達和服務臺數(shù)，排隊過程可用下列模型表示：模型2單隊列多服務臺并聯(lián)的排隊模型5第5頁，共67頁。模型3多隊列多服務臺的并聯(lián)排隊模型模型4單隊多個服務臺的串聯(lián)排隊模型6第6頁，共67頁。

模型5多隊列多服務臺混聯(lián)網(wǎng)絡模型縱觀上述排隊模型，實際上都可由下面模型加以統(tǒng)一描述：稱該統(tǒng)一模型為隨機聚散服務系統(tǒng)。由于顧客到來的時刻和服務臺提供服務的時間長短都是隨機的，因此任一排隊系統(tǒng)都是一個隨機聚散服務系統(tǒng)?！熬邸北硎绢櫩偷牡竭_,“散”表示顧客的離去。7第7頁，共67頁。

面對擁擠現(xiàn)象，人們總是希望盡量設法減少排隊，通常的做法是增加服務設施，但是增加的數(shù)量越多，人力、物力的支出就越大，甚至會出現(xiàn)空閑浪費，如果服務設施太少，顧客排隊等待的時間就會很長，這樣對顧客會帶來不良影響。

顧客排隊時間的長短與服務設施規(guī)模的大小，就構(gòu)成了設計隨機服務系統(tǒng)中的一對矛盾。

如何做到既保證一定的服務質(zhì)量指標，又使服務設施費用經(jīng)濟合理，恰當?shù)亟鉀Q顧客排隊時間與服務設施費用大小這對矛盾。這就是隨機服務系統(tǒng)理論——排隊論所要研究解決的問題。8第8頁，共67頁。一、排隊系統(tǒng)的組成與特征排隊系統(tǒng)一般有三個基本組成部分：1.輸入過程；2.排隊規(guī)則；3.服務機構(gòu)。如下圖所示：排隊系統(tǒng)的基本概念9第9頁，共67頁。

1、輸入過程輸入即為顧客的到達，可有下列情況：1）顧客源可能是有限的，也可能是無限的。2）顧客是成批到達或是單個到達。3）顧客到達間隔時間可能是隨機的或確定的。4）顧客到達可能是相互獨立或關(guān)聯(lián)的。所謂獨立就是以前顧客的到達對以后顧客的到達無影響。5）輸入過程可以是平穩(wěn)的，也可以是非平穩(wěn)的。輸入過程平穩(wěn)的是指顧客相繼到達的間隔時間分布和參數(shù)（均值、方差）與時間無關(guān)；非平穩(wěn)的則是與時間相關(guān)，非平穩(wěn)的處理比較困難。10第10頁，共67頁。這是指服務臺從隊列中選取顧客進行服務的順序?？梢苑譃閾p失制、等待制、混合制3大類。(1)損失制。這是指如果顧客到達排隊系統(tǒng)時，所有服務臺都已被先來的顧客占用，那么他們就自動離開系統(tǒng)永不再來。典型例子是，如電話拔號后出現(xiàn)忙音，顧客不愿等待而自動掛斷電話，如要再打，就需重新拔號，這種服務規(guī)則即為損失制。2、排隊規(guī)則11第11頁，共67頁。

(2)等待制。指當顧客來到系統(tǒng)時，所有服務臺都不空，顧客加入排隊行列等待服務。例如，排隊等待售票，故障設備等待維修等。等待制中，服務臺在選擇顧客進行服務時，常有如下四種規(guī)則：

①先到先服務（FCFS）。按顧客到達的先后順序?qū)︻櫩瓦M行服務，這是最普遍的情形。②后到先服務（LCFS）。倉庫中迭放的鋼材，后迭放上去的都先被領(lǐng)走，就屬于這種情況。12第12頁，共67頁。

③隨機服務(RAND)。即當服務臺空閑時，不按照排隊序列而隨意指定某個顧客去接受服務，如電話交換臺接通呼叫電話就是一例。

④優(yōu)先權(quán)服務(PR)。如老人、兒童先進車站；危重病員先就診；遇到重要數(shù)據(jù)需要處理計算機立即中斷其他數(shù)據(jù)的處理等，均屬于此種服務規(guī)則。13第13頁，共67頁。

(3)混合制．這是等待制與損失制相結(jié)合的一種服務規(guī)則，一般是指允許排隊，但又不允許隊列無限長下去。具體說來，大致有三種：

①隊長有限。當排隊等待服務顧客人數(shù)超過規(guī)定數(shù)量時，后來顧客就自動離去，另求服務，即系統(tǒng)的等待空間是有限的。例如最多只能容納N個顧客在系統(tǒng)中，當新顧客到達時，若系統(tǒng)中的顧客數(shù)(又稱為隊長)小于N，則可進入系統(tǒng)排隊或接受服務；否則，便離開系統(tǒng)，并不再回來。再如水庫的庫容是有限的，旅館的床位是有限的。14第14頁，共67頁。

②等待時間有限。即顧客在系統(tǒng)中的等待時間不超過某一給定的長度T，當?shù)却龝r間超過T時，顧客自動離去，不再回來。如易損壞的電子元器件的庫存問題，超過一定存儲時間被自動認為失效。又如顧客到飯館就餐，等了一定時間后不愿再等而自動離去另找飯店用餐。15第15頁，共67頁。

③逗留時間(等待時間與服務時間之和)有限。例如用高射炮射擊敵機，當敵機飛越高射炮射擊有效區(qū)域的時間為t時，若在這個時間內(nèi)未被擊落，也就不可能再被擊落了。不難注意到，損失制和等待制可看成是混合制的特殊情形，如記c為系統(tǒng)中服務臺的個數(shù)，則當K=c時，混合制即成為損失制；當K=∞時，混合制即成為等待制。16第16頁，共67頁。3、服務臺服務臺可以從以下3方面來描述：(1)服務臺數(shù)量及構(gòu)成形式。從數(shù)量上說，服務臺有單服務臺和多服務臺之分。從構(gòu)成形式上看，服務臺有：①單隊——單服務臺式；②單隊——多服務臺并聯(lián)式；③多隊——多服務臺并聯(lián)式；④單隊——多服務臺串聯(lián)式；⑤單隊——多服務臺并串聯(lián)混合式,以及多隊列多服務臺并串聯(lián)混合式等等。

如之前的分類模型圖所示。17第17頁，共67頁。(2)服務方式。這是指在某一時刻接受服務的顧客數(shù)，它有單個服務和成批服務兩種。如公共汽車一次就可裝載一批乘客就屬于成批服務。(3)服務時間的分布。一般來說，在多數(shù)情況下，對每一個顧客的服務時間是一隨機變量，其概率分布有定長分布、負指數(shù)分布、K階愛爾朗分布、一般分布(所有顧客的服務時間都是獨立同分布的)等等。18第18頁，共67頁。排隊系統(tǒng)的描述符號與模型分類為了區(qū)別各種排隊系統(tǒng)，根據(jù)輸入過程、排隊規(guī)則和服務機制的變化對排隊模型進行描述或分類，可給出很多排隊模型(見前面分析與圖示)。為了方便對眾多模型的描述,D．G．肯道爾（D．G．Kendall）提出了一種目前在排隊論中被廣泛采用的“Kendall記號”，完整的表達方式通常用到6個符號并取如下固定格式：X/Y/Z/A/B/C各符號的意義如下：X---表示顧客相繼到達間隔時間分布，常用下列符號：M——表示到達過程為泊松過程或(負指數(shù)分布Markov)；D——表示定長輸入(確定型分布Deterministic)；EK——表示k階愛爾朗分布；GI——一般相互獨立的隨機分布(GeneralIndependent)G——表示一般的隨機分布。19第19頁，共67頁。Y---表示服務時間分布，所用符號與表示顧客到達間隔時間分布相同。

Z---表示服務臺(員)個數(shù)：“1”則表示單個服務臺，“s”。(s＞1)表示多個服務臺。A---表示系統(tǒng)中顧客容量限額，或稱等待空間容量；如系統(tǒng)有K個等待位子，則0<K<∞，當K=0時，說明系統(tǒng)不允許等待，即為損失制。K=∞時為等待制系統(tǒng)，此時∞般省略不寫。K為有限整數(shù)時，表示為混合制系統(tǒng)。B---表示顧客源限額。分有限與無限兩種，∞表示顧客源無限，此時一般∞也可省略不寫。C---表示服務規(guī)則，常用下列符號：FCFS：表示先到先服務的排隊規(guī)則；LCFS：表示后到先服務的排隊規(guī)則；PR：表示優(yōu)先權(quán)服務的排隊規(guī)則。20第20頁，共67頁。例如：某排隊問題為M／M／S／∞／∞／FCFS，則表示顧客到達間隔時間為負指數(shù)分布(泊松流)；服務時間為負指數(shù)分布；有s(s＞1)個服務臺；系統(tǒng)等待空間容量無限(等待制)；顧客源無限，采用先到先服務規(guī)則。

某些情況下，排隊問題僅用上述表達形式中的前3個、4個、5個符號。如不特別說明則均理解為系統(tǒng)等待空間容量無限；顧客源無限，先到先服務，單個服務的等待制系統(tǒng)。21第21頁，共67頁。排隊問題求解(主要指性態(tài)問題)求解一般排隊系統(tǒng)問題的目的主要是通過研究排隊系統(tǒng)運行的效率指標，估計服務質(zhì)量，確定系統(tǒng)的合理結(jié)構(gòu)和系統(tǒng)參數(shù)的合理值，以便實現(xiàn)對現(xiàn)有系統(tǒng)合理改進和對新建系統(tǒng)的最優(yōu)設計等。排隊問題的一般步驟：1、確定或擬合排隊系統(tǒng)顧客到達的時間間隔分布和服務時間分布(可實測)。2、研究分析排隊系統(tǒng)理論分布的概率特征。3、研究系統(tǒng)狀態(tài)的概率。系統(tǒng)狀態(tài)是指系統(tǒng)中顧客數(shù),用n表示。狀態(tài)概率用Pn(t)表示,即在t時刻系統(tǒng)中有n個顧客的概率，也稱瞬態(tài)概率。22第22頁，共67頁。求解狀態(tài)概率Pn(t)方法是建立含Pn(t)的微分差分方程，通過求解微分差分方程得到系統(tǒng)瞬態(tài)解，由于瞬態(tài)解一般求出確定值比較困難，即便求得一般也很難使用。因此常常使用它的極限(如果存在的話)：穩(wěn)態(tài)的物理意義圖，系統(tǒng)的穩(wěn)態(tài)一般很快都能達到，但實際中達不到穩(wěn)態(tài)的現(xiàn)象也存在。要注意的是求穩(wěn)態(tài)概率Pn并不一定求t→∞的極限,只需求Pn’(t)=0。過渡狀態(tài)穩(wěn)定狀態(tài)pnt排隊系統(tǒng)狀態(tài)變化示意圖稱為穩(wěn)態(tài)解，或稱統(tǒng)計平衡狀態(tài)解。23第23頁，共67頁。

4、根據(jù)排隊系統(tǒng)對應的理論模型求用以判斷系統(tǒng)運行優(yōu)劣的基本數(shù)量指標的概率分布或特征數(shù)。數(shù)量指標主要包括:(1)平均隊長(Ls):系統(tǒng)中的顧客數(shù)(包括被服務和正在排隊的顧客)。

平均隊列長(Lq):系統(tǒng)中排隊等待服務的顧客數(shù)。系統(tǒng)中顧客數(shù)Ls=系統(tǒng)中排隊等待服務的顧客數(shù)Lg+正被服務的顧客數(shù)c(2)平均逗留時間(Ws):指一個顧客在系統(tǒng)中的停留時間(含等待時間和被服務時間)。

平均等待時間(Wq):一個顧客在系統(tǒng)中排隊等待的時間。(3)平均忙期(Tb)：指從顧客到達空閑服務機構(gòu)起到服務機構(gòu)再次為空閑這段時間平均長度。(忙期和一個忙期中平均完成服務顧客數(shù)都是衡量服務機構(gòu)效率的指標，忙期關(guān)系到工作強度)

24第24頁，共67頁。5、排隊系統(tǒng)指標優(yōu)化

含優(yōu)化設計與優(yōu)化運營。

與忙期相對的是閑期，即服務機構(gòu)連續(xù)保持空閑的時間。在排隊系統(tǒng)中，忙期和閑期總是交替出現(xiàn)的。除了上述幾個基本數(shù)量指標外，還會用到其他一些重要的指標，如在損失制或系統(tǒng)容量有限的情況下，由于顧客被拒絕，而使服務系統(tǒng)受到損失的顧客損失率及服務強度等，也都是十分重要的數(shù)量指標。計算上述指標的基礎(chǔ)是表達系統(tǒng)狀態(tài)(系統(tǒng)中的顧客數(shù)n)的概率[與顧客到達(輸入過程)間隔時間分布與服務時間分布有關(guān)]。顧客數(shù)n的可能取值是：(1)隊長沒有限制時，n=0，1，2，…(2)隊長有限制、最大數(shù)為N時，n=0，1，2，…，N(3)損失制且服務臺個數(shù)為c時，n=0，1，2，…，c系統(tǒng)處于這些狀態(tài)的概率一般是隨時間t變化的，所以在時刻t、系統(tǒng)狀態(tài)為n的瞬態(tài)概率可用Pn(t)表示，穩(wěn)態(tài)概率用Pn表示。25第25頁，共67頁。輸入過程與服務時間的分布

排隊系統(tǒng)的主要數(shù)據(jù)是顧客到達流和服務時間流，而這都與時間有關(guān)且是不確定的。根據(jù)有關(guān)概率知識，與時間有關(guān)的隨機變量的概率分布是一類非負的隨機變量分布，是一個隨機過程，即泊松過程。常用的非負隨機變量分布有泊松分布、指數(shù)分布、愛爾朗分布、確定型分布等。

現(xiàn)設顧客到達過程是一個隨機過程。令N(t)表示在時間區(qū)間[0,t)內(nèi)到達的顧客數(shù)(t>0),Pn(t1,t2)表示在時間區(qū)間[t1,t2)(t2>t1)內(nèi)有n(≥0)個顧客到達的概率。即：（t2>t1，n≥0）當Pn(t1,t2)同時符合下述三個條件時，顧客到達過程就是泊松過程(顧客到達形成泊松流)。1、泊松分布26第26頁，共67頁。①

無后效性：各區(qū)間的到達相互獨立,即Markov性。也就是說過程在t+Δt所處的狀態(tài)與t以前所處的狀態(tài)無關(guān)。②平穩(wěn)性：即對于足夠小的Δt，有：泊松流具有如下特性：在[t,t+Δt]內(nèi)有一個顧客到達的概率與t無關(guān),而與Δt成正比。27第27頁，共67頁。

③普通性：對充分小的Δt,在時間區(qū)間（t,t+Δt）內(nèi)有2個或2個以上顧客到達的概率是一高階無窮小.由此知，在(t，t+Δt)區(qū)間內(nèi)沒有顧客到達的概率為：令t1=0,t2=t,則P(t1,t2)=Pn(0,t)=Pn(t)λ>0是常數(shù)，它表示單位時間到達的顧客數(shù)，稱為概率強度。即P0+P1+P≥2=1下面將討論求關(guān)鍵的Pn(t)。

28第28頁，共67頁。在[0，t+Δt]內(nèi)到達n個顧客應是上面三種互不相容的情況之一，所以有：

為了求Pn(t),即Pn(0,t)，需要研究它在（t，t+Δt）上的改變量,建立Pn(t)的微分方程。對于區(qū)間[0,t+Δt)可以分成[0，t)和[t，t+Δt),其到達總數(shù)是n，不外有下列三種情況：29第29頁，共67頁。令Δt→0取極限（并注意初始條件）得：………(3)當n=0時，沒有B，C兩種情況，則：………(4)湊微分區(qū)間長度（0，0）有n個顧客到達(0,t)有n-1,n-2個顧客到達即：30第30頁，共67頁。∴C=0（3）式兩端乘et并移項得：∴……(5)（沒有顧客到達的概率）兩邊積分得：代入初始條件(t=0)有：P0(0)=131第31頁，共67頁。將n=1,2,3…代入（6）得：∴………(6)(注意利用(5)式)湊成Pn(t)et兩項乘積的微分兩邊積分32第32頁，共67頁。如此繼續(xù)遞推下去得：∴（2個顧客到達的概率）（n個顧客到達的概率）即隨機變量N(t)=n服從泊松分布。它的數(shù)學期望和方差為：∴（1個顧客到達的概率）33第33頁，共67頁。引入級數(shù)∴令k=n-1，則：34第34頁，共67頁。即：同理方差為：說明顧客到達過程確實是一個泊松過程(泊松流)，這也是泊松分布的數(shù)學推導。35第35頁，共67頁。其概率密度函數(shù)為：t>02、負指數(shù)分布當輸入過程是泊松流時，我們研究兩顧客相繼到達的時間間隔的概率分布。設T為時間間隔，分布函數(shù)為FT（t），則：FT（t）=P{T≤t}此概率等價于在[0,t)區(qū)間內(nèi)至少有1個顧客到達的概率?！鄑>0

∵沒有顧客到達的概率為：(由（5）式而來)間隔：間隔：間隔對分布函數(shù)微分36第36頁，共67頁。

λ表示單位時間內(nèi)顧客平均到達數(shù)。

1/λ表示顧客到達的平均間隔時間。可以證明，間隔時間T獨立且服從負指數(shù)分布與顧客到達形成泊松流是等價的。負指數(shù)分布是一種無記憶性的分布。對顧客的服務時間：系統(tǒng)處于忙期時兩顧客相繼離開系統(tǒng)的時間間隔，一般地也服從負指數(shù)分布。即T服從負指數(shù)分布，它的期望及方差為：接受服務，然后離開服務時間的分布：即：P(X>t+s|X>t)=P(X>s)37第37頁，共67頁。其中：μ表示單位時間內(nèi)能被服務的顧客數(shù)，即平均服務率。1/μ表示一個顧客的平均服務時間。3、愛爾朗(Erlang)分布設v1,v2，…,vk是k個獨立的隨機變量，服從相同參數(shù)

k

的負指數(shù)分布，那么：，則令，則ρ稱為服務強度。令38第38頁，共67頁。

串列k個服務臺，每臺服務時間相互獨立，服從相同負指數(shù)分布（參數(shù)k），那么一顧客走完k個服務臺總共所需要服務時間服從上述k階Erlang分布。則稱T服從k階愛爾朗分布。其特征值為：,其概率密度是1/kμ表示一個顧客一個服務臺的平均服務時間。其他常用的分布參見教材P122-123，也可參見概率論與數(shù)理統(tǒng)計相關(guān)教程。39第39頁，共67頁。生滅過程1、生滅過程簡介一類非常重要且廣泛存在的排隊系統(tǒng)是生滅過程排隊系統(tǒng)。生滅過程是一類特殊的隨機過程，在生物學、物理學、運籌學中有廣泛的應用。2、生滅過程的定義

設{N(t),t≥0}為一個隨機過程。如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),t≥0}為一個生滅過程。40第40頁，共67頁。顧客到達——“生”；顧客離開——“滅”n，n，生滅過程示意圖：顧客到達顧客離去41第41頁，共67頁。

一般說來，得到是比較困難的或非理論作用不太大，因此通常是求當系統(tǒng)達到平穩(wěn)狀態(tài)后的狀態(tài)分布，記為,n=0,1,2,…為求平穩(wěn)分布，考慮系統(tǒng)在t+Δt時刻可能處的任一狀態(tài)n的概率?？山o出狀態(tài)轉(zhuǎn)移圖如下：狀態(tài)轉(zhuǎn)移圖說明：n狀態(tài)下，排隊系統(tǒng)中的人數(shù)穩(wěn)定為n,n=0,1,2,….,即進了多少個就要出去多少個。42第42頁，共67頁。方式

t時刻狀態(tài)t狀態(tài)的概率（t,t+Δt）內(nèi)發(fā)生的事件發(fā)生的概率1nPn(t)0人到達，0人離去

（1-λnΔt）×

(1-μnΔt)

2n-1Pn-1(t)1人到達，0人離去

λn-1Δt×(1-μn-1Δt)

3n+1Pn+1(t)0人到達，1人離去(1-λn+1Δt)×μn+1Δt

4nPn(t)1人到達，同時1人離去(λnΔt)×(μnΔt)

各種方式下發(fā)生概率表（保證n狀態(tài):t+Δt時刻穩(wěn)定有n個人）說明：狀態(tài)n下，1人到達的概率約為λnΔt，1人離去的概率約為μnΔt，0人到達的概率約為1-λnΔt，0人離去的概率約為1-μnΔt。(根據(jù)泊松流的特征得到)43第43頁，共67頁。又因為前述方式1，2，3，4是互不相容且完備的，因此有：對上式展開并構(gòu)造如下極限式：，則有：這剛好就是Pn(t)對t的導數(shù)。事件(0,t+?t)發(fā)生可看作事件(0,t）和事件(t,t+?t)同時發(fā)生。因此：P(0,t+?t)=P(0,t)P(t,t+?t)44第44頁，共67頁。當n=0時，只有方式1和3，4發(fā)生，且方式1中無離去的概率為1，則:設系統(tǒng)是穩(wěn)態(tài)的，即與時刻t無關(guān)，于是可得：令P0已知，可用遞推方法求得：45第45頁，共67頁。

記則平穩(wěn)狀態(tài)的分布為：下面求P0。46第46頁，共67頁。由概率分布的要求：有：即綜上述，得到各狀態(tài)平衡時的概率分布遞推計算式如下：所以關(guān)鍵是得到各狀態(tài)下單位時間到達和離開的人數(shù)：47第47頁，共67頁。例：某小型超市有一個收款臺。付款顧客以每小時30人的負指數(shù)分布到達。當收款臺前只有一名顧客時，有一名收款員單獨服務，收款時間為平均1.5min的負指數(shù)分布；當有2名或以上顧客時，將增加一名助手共同為顧客服務，收款時間將縮短至平均1min的負指數(shù)分布。求收款臺前有n名顧客的概率Pn解：這里的單位時間是1小時，所以48第48頁，共67頁。n=1,2…..則有由可知：49第49頁，共67頁。一般地，對排隊模型，在給定輸入和服務條件下，主要研究系統(tǒng)的下述運行指標：(1)系統(tǒng)的平均隊長Ls(期望值)和平均隊列長Lq(期望值)；(2)系統(tǒng)中顧客平均逗留時間Ws與隊列中平均等待時間Wq；M/M/s等待制排隊模型單服務臺模型：M/M/1/∞

M/M/1/∞是指：顧客的相繼到達時間服從參數(shù)為λ的負指數(shù)分布，服務臺數(shù)為1，服務時間服從參數(shù)為μ的負指數(shù)分布，系統(tǒng)空間無限，允許無限排隊。50第50頁，共67頁。1、隊長的分布(參數(shù)λ、μ就是單位時間進入或被服務的人數(shù))所以λn=λ(n=0，1，2，…)，μn=μ(n=0，1，2，…)記ρ=λ/μ，并設ρ<1(否則隊列將排至無限遠)，則n=1,2,…..，n=1,2,…而因此n=0,1,2ρ是系統(tǒng)中至少有一個顧客的概率，也就是服務臺處于忙的狀態(tài)的概率，因而也稱ρ為服務強度，它反映了系統(tǒng)繁忙的程度。即為平衡條件下系統(tǒng)中顧客數(shù)為n的概率。51第51頁，共67頁。2.系統(tǒng)的運行指標計算(1)系統(tǒng)中的隊長Ls（平均隊長：排隊+被服務）(0<ρ<1)期望52第52頁，共67頁。(2)隊列中等待的平均顧客數(shù)Lq：僅排隊(3)顧客在系統(tǒng)中的平均逗留時間Ws顧客在系統(tǒng)中的逗留時間是隨機變量，可以證明，它服從參數(shù)為μ-λ的負指數(shù)分布，分布函數(shù)53第53頁，共67頁。和密度函數(shù)為：（w≥0）∴(4)顧客在隊列中的平均逗留時間Wq

等待時間顧客在隊列中的平均逗留時間應為Ws減去平均服務時間。考慮LS與WS的關(guān)系54第54頁，共67頁。四個指標的關(guān)系為(Little公式)：

3.系統(tǒng)的忙期與閑期系統(tǒng)處于空閑狀態(tài)的概率：系統(tǒng)處于繁忙狀態(tài)的概率：服務強度55第55頁，共67頁。在繁忙狀態(tài)下，隊列中的平均顧客數(shù)Lb：顧客平均等待時間:忙期的平均長度:(由來)一個忙期平均服務顧客數(shù)為：Lb×P(N≥0)=Lq56第56頁，共67頁。例：某修理店只有一個修理工，來修理的顧客到達過程為Poisson流，平均4人/h;修理時間服從負指數(shù)分布，平均需要6min。試求：（1）修理店空閑的概率（2）店內(nèi)恰有3個顧客的概率（3）店內(nèi)至少有1個顧客的概率（4）在店內(nèi)的平均顧客數(shù)（5）每位顧客在店內(nèi)的平均逗留時間（6）等待服務的平均顧客數(shù)（7）每位顧客平均等待服務時間（8）顧客在店內(nèi)等待時間超過10min的概率57第57頁，共67頁。解本例可看成一個M/M/1/∞排隊問題，其中（1）修理店空閑的概率（2）店內(nèi)恰有3個顧客的概率（3）店內(nèi)至少有1個顧客的概率58第58頁，共67頁。（4）在店內(nèi)的平均顧客數(shù)（5）每位顧客在店內(nèi)的平均逗留時間（人）（6）等待服務的平均顧客數(shù)（人）59第59頁，共67頁。（7）每位顧客平均等待服務的時間（8）顧客在店內(nèi)逗留時間超過10min的概率由于逗留時間服從參數(shù)的負指數(shù)分布，即分布函數(shù)為則注：對于μ：1小時10人則1分鐘10/60=1/6(人)。λ同理60第60頁，共67頁。多服務臺模型：M/M/s/∞

M/M/s/∞是指：設顧客單個到達，相繼到達時間服從參數(shù)為λ的負指數(shù)分布