第六章排隊(duì)論模型

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

前言2第2頁(yè)，共67頁(yè)。

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

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

3第3頁(yè)，共67頁(yè)。

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

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

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

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

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

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

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

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

③隨機(jī)服務(wù)(RAND)。即當(dāng)服務(wù)臺(tái)空閑時(shí)，不按照排隊(duì)序列而隨意指定某個(gè)顧客去接受服務(wù)，如電話交換臺(tái)接通呼叫電話就是一例。

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

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

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

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

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

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

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

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

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

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

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

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

含優(yōu)化設(shè)計(jì)與優(yōu)化運(yùn)營(yíng)。

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

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

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

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

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

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

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

∵沒(méi)有顧客到達(dá)的概率為：(由（5）式而來(lái))間隔：間隔：間隔對(duì)分布函數(shù)微分36第36頁(yè)，共67頁(yè)。

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

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

k

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

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

設(shè){N(t),t≥0}為一個(gè)隨機(jī)過(guò)程。如N(t)的概率分布具有以下性質(zhì)：(1)假設(shè)N(t)=n，則從時(shí)刻t起到下一個(gè)顧客到達(dá)時(shí)刻止的時(shí)間服從參數(shù)為λn的負(fù)指數(shù)分布，n=0，1，2，…。間隔時(shí)間分布(2)假設(shè)N(t)=n，則從時(shí)刻t起到下一個(gè)顧客離去時(shí)刻止的時(shí)間服從參數(shù)為μn的負(fù)指數(shù)分布，n=0，1，2，…。服務(wù)時(shí)間分布(3)同一時(shí)刻只有一個(gè)顧客到達(dá)或離去。則稱設(shè){N(t),t≥0}為一個(gè)生滅過(guò)程。40第40頁(yè)，共67頁(yè)。顧客到達(dá)——“生”；顧客離開(kāi)——“滅”n，n，生滅過(guò)程示意圖：顧客到達(dá)顧客離去41第41頁(yè)，共67頁(yè)。

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

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

（1-λnΔt）×

(1-μnΔt)

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

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

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

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

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

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

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

等待時(shí)間顧客在隊(duì)列中的平均逗留時(shí)間應(yīng)為Ws減去平均服務(wù)時(shí)間?？紤]LS與WS的關(guān)系54第54頁(yè)，共67頁(yè)。四個(gè)指標(biāo)的關(guān)系為(Little公式)：

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

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