排隊論排隊論的基本知識1排隊論模型2第一頁，共45頁。1背景介紹有形的隊伍超市出口處排隊付款餐廳排隊買飯公共電話亭打電話無形的隊伍114查號臺等待服務網絡中數(shù)據包傳輸報告等首長批示一、排隊論的基本知識第二頁，共45頁。排隊論研究的內容有三部分1.性態(tài)問題：即研究排隊系統(tǒng)中的概率分布規(guī)律2.最優(yōu)化問題：分為靜態(tài)最優(yōu)化和動態(tài)最優(yōu)化，即為系統(tǒng)的最優(yōu)設計和系統(tǒng)的最優(yōu)運營3.排隊系統(tǒng)的統(tǒng)計推斷：判斷一個給定的排隊系統(tǒng)符合于哪種模型，以便于根據排隊理論進行分析研究

第三頁，共45頁。2.排隊系統(tǒng)描述

排隊系統(tǒng)又稱為隨機服務系統(tǒng)，是研究服務請求服務的人或者物——顧客；排隊系統(tǒng)的共同特征：顧客到達系統(tǒng)的時刻是隨機的，為每一位顧客有為顧客服務的人或者物，即服務員或服務臺；過程和擁擠現(xiàn)象的隨機模型.提供服務的時間是隨機的，因而整個排隊系統(tǒng)的狀態(tài)也是隨機的.第四頁，共45頁。2.顧客是怎樣排隊的排隊模型服務窗服務規(guī)則排隊排隊規(guī)則顧客源排隊系統(tǒng)1.顧客是怎樣到達的3.顧客是怎樣接受服務第五頁，共45頁。排隊系統(tǒng)的幾種形式：第六頁，共45頁。第七頁，共45頁。第八頁，共45頁。第九頁，共45頁。第十頁，共45頁。基本排隊過程：

從圖6—6可知，每個顧客由顧客源按一定方式到達服務系統(tǒng)，首先加入隊列排隊等待接受服務，然后服務臺按一定規(guī)則從隊列中選擇顧客進行服務，獲得服務的顧客立即離開.第十一頁，共45頁。排隊論所要研究解決的問題：面對擁擠現(xiàn)象，人們通常的做法是增加服務設施但是增加的數(shù)量越多，人力、物力的支出就越大，甚至會出現(xiàn)空閑浪費，如果服務設施太少，顧客排隊等待的時間就會很長，這樣對顧客會帶來不良影響.如何做到既保證一定的服務質量指標，又使服務設施費用經濟合理，恰當?shù)亟鉀Q顧客排隊時間與服務設施費用大小這對矛盾，就是隨機服務系統(tǒng)理論——排隊論所要研究解決的問題。第十二頁，共45頁。3.排隊系統(tǒng)的基本組成部分排隊系統(tǒng)是由輸入過程、排對規(guī)則和服務機構組成.(1).輸入過程

指要求服務的顧客是按怎樣的規(guī)律(i)

顧客總體數(shù).又稱顧客源、輸入源.這是指顧客(ii)

顧客到達方式.這是描述顧客是怎樣來到系統(tǒng)到達排隊系統(tǒng)的過程，有時也把它稱為顧客流.一般可以從3個方面來描述—個輸入過程.

的來源.顧客源可以是有限的，也可以是無限的.的，是單個到達，還是成批到達.

第十三頁，共45頁。

(iii)

顧客流的概率分布.或稱相繼顧客到達的時間(2).排對規(guī)則

指服務臺從隊列中選取顧客進行

(i)損失制

指如果顧客到達排隊系統(tǒng)時，所有間隔的分布.這是求解排隊系統(tǒng)有關運行指標問題時，首先需要確定的指標.顧客流的概率分布一般有定長分布、二項分布、泊松流(最簡單流)、愛爾朗分布等若干種.服務的順序.一般可以分為損失制、等待制和混合制等3大類.服務臺都被先到的顧客占用，那么他們就自動離開系統(tǒng)永不再來.第十四頁，共45頁。(ii)等待制

指當顧客來到系統(tǒng)時，所有服務臺a.先到先服務FCFS按顧客到達的先后順序對顧客b.先到后服務LCFSc.隨機服務即當服務臺空閑時，不按照排隊d.優(yōu)先權服務都不空，顧客加入排隊行列等待服務.等待制中，服務臺在選擇顧客進行服務時常有如下四種規(guī)則：進行服務.序列而隨意指定某個顧客接受服務.第十五頁，共45頁。(iii)混合制

這是等待制與損失制相結合的一種服a.隊長有限.當排隊等待服務的顧客人數(shù)超b.等待時間有限.即顧客在系統(tǒng)中的等待時c.逗留時間(等待時間與服務時間之和)有限.務規(guī)則，一般是指允許排隊，但又不允許隊列無限長下去.具體說來，大致有三種：過規(guī)定數(shù)量K時，后來的顧客就自動離去，另求服務，即系統(tǒng)的等待空間是有限的.間不超過某一給定的長度T，當?shù)却龝r間超過T時，顧客將自動離去，并不再回來.第十六頁，共45頁。(3).服務機構

(i)服務臺數(shù)量及構成形式.從數(shù)量上說，服務臺有單(ii)服務方式.這是指在某一時刻接受服務的顧客數(shù)，(iii)服務時間的分布.在多數(shù)情況下，對每一個顧客的服務臺和多服務臺之分.從構成形式上看，服務臺有：①單隊一---單服務臺式；②單隊一---多服務臺并聯(lián)式；③多隊一---多服務臺并聯(lián)式；④單隊一---多服務臺串聯(lián)式；⑤單隊一---多服務臺并串聯(lián)混合式，以及多隊多服務臺并串聯(lián)混合式等等.它有單個服務和成批服務兩種.服務時間是一隨機變量.第十七頁，共45頁。常見顧客的服務時間分布有：

定長分布D(Deterministic)、負指數(shù)分布M(Markov)、k階Erlang分布(Ek)、一般相互獨立的時間間隔分布GI(GeneralIndependent).第十八頁，共45頁。顧客到達時間間隔的分布:假定是獨立同分布，分布函數(shù)為，排隊論中常用的有兩種：（2）最簡流（即Poisson流）（M）：顧客到達時間間隔為獨立的，服從負指數(shù)分布，其密度函數(shù)為（1）定長分布（D）顧客到達時間間隔為確定的。第十九頁，共45頁。服務時間分布:

設某服務臺的服務時間為V，其密度函數(shù)為b（t），常見的分布有：（1）定長分布（D）：每個顧客接受服務的時間是一個確定的常數(shù)。（2）負指數(shù)分布（M）：每個顧客接受服務時間相互獨立，具有相互的負指數(shù)分布：

其中，為一常數(shù)。第二十頁，共45頁。（3）k階愛爾朗（Erlang）分布：每個顧客接受服務時間服從k階愛爾朗分布，其密度函數(shù)為：μ--單位時間平均服務完成的顧客數(shù)1/μ--每個顧客的平均服務時間第二十一頁，共45頁。4.排隊系統(tǒng)的主要數(shù)量指標

排隊論主要研究系統(tǒng)的性態(tài)，即與排隊有關(1).排隊系統(tǒng)主要數(shù)量指標等待時間、忙期、隊長.的數(shù)量指標的概率規(guī)律性；系統(tǒng)的優(yōu)化問題；統(tǒng)計推斷，根據資料合理建立模型.目的是正確設計和有效運行各個服務系統(tǒng)，使之發(fā)揮最佳效益.所以必須確定判斷系統(tǒng)運行優(yōu)劣的基本數(shù)量指標.第二十二頁，共45頁。(i).等待時間

從顧客到達時刻起到他開始接受服務止這(ii).忙期

忙期是指從顧客到達空閑著的服務機構起，到(iii).隊長

隊長是指系統(tǒng)中的顧客數(shù)(排隊等待的顧客數(shù)與段時間稱為等待時間.等待時間是個隨機變量.從顧客到達時刻起到他接受服務完成止這段時間稱為逗留時間，也是隨機變量.服務機構再次成為空閑止的這段時間，即服務機構連續(xù)忙的時間.這是個隨機變量，是服務員最為關心的指標，因為它關系到服務員的服務強度.與忙期相對的是閑期,即服務機構連續(xù)保持空閑的時間.在排隊系統(tǒng)中，忙期和閑期總是交替出現(xiàn)的.正在接受服務的顧客數(shù)之和)；排隊長是指系統(tǒng)中正在排隊等待服務的顧客數(shù).隊長和排隊長一般都是隨機變量.第二十三頁，共45頁。(2).數(shù)量指標的常用記號(i).主要數(shù)量指標Ws——平均逗留時間，即(在任意時刻)進入的所有顧客數(shù)的期望值；等待服務的顧客數(shù)的期望值；穩(wěn)態(tài)系統(tǒng)的顧客逗留時間的期望值；穩(wěn)態(tài)系統(tǒng)的顧客等待時間的期望值.Ls-----平均隊長，即穩(wěn)態(tài)系統(tǒng)任一時刻——平均等待時間，即(在任意時刻)進入

——平均等待隊長，即穩(wěn)態(tài)系統(tǒng)任一時刻第二十四頁，共45頁。(ii).其它常用數(shù)量指標s

——系統(tǒng)中并聯(lián)服務臺的數(shù)目；N——穩(wěn)態(tài)系統(tǒng)任一時刻的狀態(tài)（即系統(tǒng)中U

——任一顧客在穩(wěn)態(tài)系統(tǒng)中的逗留時間；Q——任一顧客在穩(wěn)態(tài)系統(tǒng)中的等待時間；所有顧客數(shù)）；——平均到達率；——平均到達間隔；——平均服務率；——平均服務時間；第二十五頁，共45頁。有服務臺全部空閑的概率；繁忙程度的重要尺度.——服務強度，即每個服務臺單位時間內的平均服務時間，一般有，這是衡量排隊系統(tǒng):穩(wěn)態(tài)系統(tǒng)任意時刻狀態(tài)為n的概率；特別當n=0時(系統(tǒng)中顧客數(shù)為0)，即穩(wěn)態(tài)系統(tǒng)所損失率：由于系統(tǒng)的條件限制，使顧客被拒絕服務而使服務部門受到損失的概率。第二十六頁，共45頁。

5.排隊系統(tǒng)的描述符號

描述符號：X/Y/Z/A/B/CX—顧客相繼到達的間隔時間的分布；常用下M——表示到達的過程為泊松過程或負指數(shù)分布；D——表示定長輸入；GI——表示一般相互獨立的時間間隔分布.Y—服務時間的分布；所用符號與表示顧客列符號：到達間隔時間分布相同.——表示K階愛爾朗分布；第二十七頁，共45頁。Z—服務臺個數(shù)；“1”表示單個服務臺，“s”(s>1)A－系統(tǒng)容量限制(默認為∞)；如系統(tǒng)有K個等待位子，則B－顧客源數(shù)目（默認為∞）；分有限與無限兩種，∞表C－服務規(guī)則；

常用下列符號：FCFS：表示先到先服務的排隊規(guī)則；LCFS：表示后到先服務的排隊規(guī)則；PR：表示優(yōu)先權服務的排隊規(guī)則。表示多個服務臺.0<K<∞，當K=0時，說明系統(tǒng)不允許等待，即為損失制.K=∞時為等待制系統(tǒng)，此時一般∞省略不寫.K為有限整數(shù)時，表示為混合制系統(tǒng).示顧客源無限，一般∞也可省略不寫.第二十八頁，共45頁。例如：某排隊問題為M／M／S／∞／∞/FCFS，則

某些情況下，排隊問題僅用上述表達形式

如不特別說明則均理解為系統(tǒng)等待空間容量表示顧客到達間隔時間為負指數(shù)分布(泊松流)；服務時間為負指數(shù)分布；有s(s>1)個服務臺；系統(tǒng)等待空間容量無限(等待制)；顧客源無限，采用先到先服務規(guī)則.中的前3個符號.例如，某排隊問題為M／M／S.無限；顧客源無限，先到先服務，單個服務的等待制系統(tǒng).第二十九頁，共45頁。

已知:顧客到達間隔時間分布,服務時間分布.求:隊長:Ls--系統(tǒng)中的顧客數(shù).排隊長(隊列長):Lq--隊列中的顧客數(shù).Ls=Lq+正在接受服務的顧客數(shù)逗留時間:WS--顧客在系統(tǒng)中的停留時間等待時間:Wq--顧客在隊列中的等待時間.WS=Wq+服務時間忙期,損失率,服務強度.排隊問題的求解第三十頁，共45頁。二、M/M/s排隊模型

M/M/s排隊模型是指s個服務員的排隊系統(tǒng)，顧客到來間隔時間是獨立同分布的；服務時間也是獨立同分布的；并且獨立于輸入過程；排隊規(guī)則是等待制；含假定：顧客到來間隔時間服從參數(shù)為的指數(shù)分布，服務時間服從參數(shù)為的負指數(shù)分布，且有隱第三十一頁，共45頁。

按排隊論的基本構成特征，來求解該排隊模型(1).基本構成(i)顧客到達規(guī)律的主要數(shù)量指標：平均到達率.表示在時間到達的顧客數(shù)，稱為排隊系統(tǒng)的輸入過程.其平均值為，即單位時間內到達的顧客數(shù)為，并稱為它服從參數(shù)為的泊松分布，即：第三十二頁，共45頁。(ii)服務時間服務率.表示顧客到達間隔時間序列，其中表示第n個顧客的到來時刻.

可以證明：服從參數(shù)為的泊松分布的充負指數(shù)分布.要條件是到達間隔時間序列獨立同分布且服從記Z為服務時間，Z服從參數(shù)為的負指數(shù)分布：則，即為每個顧客平均服務時間為，從而單位時間內被服務的顧客的平均數(shù)為，稱為平均第三十三頁，共45頁。

(iii)排隊規(guī)則按顧客的到達的先后順序服務，即先到先服務.

滿足以上三個條件的模型在排隊論中記為模型(2).數(shù)量特征(只討論s=1情形)(i)平均隊長

穩(wěn)態(tài)下系統(tǒng)內等待服務的顧客數(shù)，其數(shù)學期望稱為平均等待隊長，即M/M/s模型，其中s為服務員的個數(shù).(其中稱為服務強度.)第三十四頁，共45頁。(ii)平均逗留時間和平均等待時間平均逗留時間為平均等待時間為則公式稱為Little公式.第三十五頁，共45頁。(3).M/M/s排隊模型(i)當s=2時服務強度平均隊長平均等待時間(ii)當s是任意的服務強度平均隊長平均等待時間其中為所有服務員均空閑的概率.第三十六頁，共45頁。例1.某醫(yī)院急診室同時只能診治一個病人，診治時間服從指數(shù)分布，每個病人平均需要15分鐘。病人按泊松分布到達，平均每小時到達3人。試對此排隊系統(tǒng)進行分析.解對此排隊系統(tǒng)分析如下：①先確定參數(shù)值：這是單服務系統(tǒng)有，=3人/h=60/15人/h=4人/h第三十