第六章排隊論模型

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

2、步根據(jù)排隊理論進行分析研究。 前前 言言3 起源于起源于19091909年在丹麥哥本哈根電子公司工作的電話工程年在丹麥哥本哈根電子公司工作的電話工程師師A. K. Erlang(A.K.A. K. Erlang(A.K.愛爾朗愛爾朗) )對電話通話擁擠問題的研究工作，對電話通話擁擠問題的研究工作，其開創(chuàng)性論文其開創(chuàng)性論文-概率論和電話通訊理論則標(biāo)志此理論的誕生。概率論和電話通訊理論則標(biāo)志此理論的誕生。表明了排隊論的發(fā)展最早是與電話，通信中的問題相聯(lián)系的，表明了排隊論的發(fā)展最早是與電話，通信中的問題相聯(lián)系的，并到現(xiàn)在也還是排隊論的傳統(tǒng)的應(yīng)用領(lǐng)域。近年來在計算機通并到現(xiàn)在也還是排隊論的傳統(tǒng)的應(yīng)用領(lǐng)

3、域。近年來在計算機通訊網(wǎng)絡(luò)系統(tǒng)、交通運輸、醫(yī)療衛(wèi)生系統(tǒng)、各類生產(chǎn)服務(wù)、庫存訊網(wǎng)絡(luò)系統(tǒng)、交通運輸、醫(yī)療衛(wèi)生系統(tǒng)、各類生產(chǎn)服務(wù)、庫存管理等等各領(lǐng)域中均得到廣泛的應(yīng)用。管理等等各領(lǐng)域中均得到廣泛的應(yīng)用。 排隊論歷史： 排隊是我們在日常生活和生產(chǎn)中經(jīng)常遇到的現(xiàn)象。例如：搭乘公共排隊是我們在日常生活和生產(chǎn)中經(jīng)常遇到的現(xiàn)象。例如：搭乘公共汽車；顧客到商店購買物品；病員到醫(yī)院看??；旅客到售票處購買車票；汽車；顧客到商店購買物品；病員到醫(yī)院看??；旅客到售票處購買車票；學(xué)生去食堂就餐等就常常出現(xiàn)排隊和等待現(xiàn)象。除了上述學(xué)生去食堂就餐等就常常出現(xiàn)排隊和等待現(xiàn)象。除了上述有形的排隊有形的排隊之外，之外，還有大量的所

4、謂還有大量的所謂“無形無形”排隊排隊現(xiàn)象，如幾個顧客打電話到出租汽車站要求現(xiàn)象，如幾個顧客打電話到出租汽車站要求派車，如果出租汽車站無足夠車輛、則部分顧客只得在各自的要車處等待，派車，如果出租汽車站無足夠車輛、則部分顧客只得在各自的要車處等待，他們分散在不同地方，卻形成了一個無形隊列在等待派車。排隊的不一定他們分散在不同地方，卻形成了一個無形隊列在等待派車。排隊的不一定是人，也可以是物：例如：通訊衛(wèi)星與地面若干待傳遞的信息；生產(chǎn)線上是人，也可以是物：例如：通訊衛(wèi)星與地面若干待傳遞的信息；生產(chǎn)線上的原料、半成品等待加工；因故障停止運轉(zhuǎn)的機器等待工人修理；碼頭的的原料、半成品等待加工；因故障停止運

5、轉(zhuǎn)的機器等待工人修理；碼頭的船只等待裝卸貨物；要降落的飛機因跑道不空而在空中盤旋等等。船只等待裝卸貨物；要降落的飛機因跑道不空而在空中盤旋等等。 排隊論具體事例： 4 上述事例中的各種問題雖互不相同，但卻都上述事例中的各種問題雖互不相同，但卻都有要求得到某種服務(wù)的人或物和提供服務(wù)的人或有要求得到某種服務(wù)的人或物和提供服務(wù)的人或機構(gòu)。排隊論里把要求服務(wù)的對象統(tǒng)稱為機構(gòu)。排隊論里把要求服務(wù)的對象統(tǒng)稱為“顧顧客客”, ,而把提供服務(wù)的人或機構(gòu)稱為而把提供服務(wù)的人或機構(gòu)稱為“服務(wù)臺服務(wù)臺”或或“服務(wù)員服務(wù)員”。不同的顧客與服務(wù)組成了各式各樣。不同的顧客與服務(wù)組成了各式各樣的服務(wù)系統(tǒng)。顧客為了得到某種服

6、務(wù)而到達系統(tǒng)、的服務(wù)系統(tǒng)。顧客為了得到某種服務(wù)而到達系統(tǒng)、若不能立即獲得服務(wù)而又允許排隊等待，則加入若不能立即獲得服務(wù)而又允許排隊等待，則加入等待隊伍，待獲得服務(wù)后離開系統(tǒng)。等待隊伍，待獲得服務(wù)后離開系統(tǒng)。5模型模型1 1 單服務(wù)臺排隊模型單服務(wù)臺排隊模型排隊模型及類型排隊模型及類型 根據(jù)顧客到達和服務(wù)臺數(shù)，排隊過程可用下列模型表示：模型模型2 2 單隊列多服務(wù)臺并聯(lián)的排隊模型單隊列多服務(wù)臺并聯(lián)的排隊模型6模型模型3 3 多隊列多服務(wù)臺的并聯(lián)排隊模型多隊列多服務(wù)臺的并聯(lián)排隊模型模型模型4 4 單隊多個服務(wù)臺的串聯(lián)排隊模型單隊多個服務(wù)臺的串聯(lián)排隊模型7 模型模型5 5 多隊列多服務(wù)臺混聯(lián)網(wǎng)絡(luò)模型

7、多隊列多服務(wù)臺混聯(lián)網(wǎng)絡(luò)模型縱觀上述排隊模型，實際上都可由下面模型加以統(tǒng)一描述：縱觀上述排隊模型，實際上都可由下面模型加以統(tǒng)一描述： 稱該統(tǒng)一模型為隨機聚散服務(wù)系統(tǒng)。稱該統(tǒng)一模型為隨機聚散服務(wù)系統(tǒng)。由于顧客到來的時刻和服務(wù)臺提由于顧客到來的時刻和服務(wù)臺提供服務(wù)的時間長短都是隨機的，因此供服務(wù)的時間長短都是隨機的，因此任一排隊系統(tǒng)都是一個隨機聚散任一排隊系統(tǒng)都是一個隨機聚散服務(wù)系統(tǒng)。服務(wù)系統(tǒng)。 “聚聚”表示顧客的到達表示顧客的到達,“,“散散”表示顧客的離去。表示顧客的離去。8 面對擁擠現(xiàn)象，人們總是希望盡量設(shè)法減少排隊，面對擁擠現(xiàn)象，人們總是希望盡量設(shè)法減少排隊，通常的做法是增加服務(wù)設(shè)施，但是增

8、加的數(shù)量越多，通常的做法是增加服務(wù)設(shè)施，但是增加的數(shù)量越多，人力、物力的支出就越大，甚至?xí)霈F(xiàn)空閑浪費，如人力、物力的支出就越大，甚至?xí)霈F(xiàn)空閑浪費，如果服務(wù)設(shè)施太少，顧客排隊等待的時間就會很長，這果服務(wù)設(shè)施太少，顧客排隊等待的時間就會很長，這樣對顧客會帶來不良影響。樣對顧客會帶來不良影響。 顧客排隊時間的長短與服務(wù)設(shè)施規(guī)模的大小，就顧客排隊時間的長短與服務(wù)設(shè)施規(guī)模的大小，就構(gòu)成了設(shè)計隨機服務(wù)系統(tǒng)中的一對矛盾。構(gòu)成了設(shè)計隨機服務(wù)系統(tǒng)中的一對矛盾。 如何做到既保證一定的服務(wù)質(zhì)量指標(biāo)，又使服務(wù)如何做到既保證一定的服務(wù)質(zhì)量指標(biāo)，又使服務(wù)設(shè)施費用經(jīng)濟合理，恰當(dāng)?shù)亟鉀Q顧客排隊時間與服務(wù)設(shè)施費用經(jīng)濟合理，

9、恰當(dāng)?shù)亟鉀Q顧客排隊時間與服務(wù)設(shè)施費用大小這對矛盾。這就是隨機服務(wù)系統(tǒng)理論設(shè)施費用大小這對矛盾。這就是隨機服務(wù)系統(tǒng)理論排隊論所要研究解決的問題。排隊論所要研究解決的問題。9 一、排隊系統(tǒng)的組成與特征一、排隊系統(tǒng)的組成與特征 排隊系統(tǒng)一般有三個基本組成部分：排隊系統(tǒng)一般有三個基本組成部分：1.1.輸輸入過程；入過程；2.2.排隊規(guī)則；排隊規(guī)則；3.3.服務(wù)機構(gòu)。如下圖所服務(wù)機構(gòu)。如下圖所示：示： 排隊系統(tǒng)的基本概念排隊系統(tǒng)的基本概念10 1、輸入過程 輸入即為顧客的到達，可有下列情況：輸入即為顧客的到達，可有下列情況： 1 1）顧客源可能是有限的，也可能是無限的。）顧客源可能是有限的，也可能是無限

10、的。 2 2）顧客是成批到達或是單個到達。）顧客是成批到達或是單個到達。 3 3）顧客到達間隔時間可能是隨機的或確定的。）顧客到達間隔時間可能是隨機的或確定的。 4 4）顧客到達可能是相互獨立或關(guān)聯(lián)的。所謂獨）顧客到達可能是相互獨立或關(guān)聯(lián)的。所謂獨立就是以前顧客的到達對以后顧客的到達無影響。立就是以前顧客的到達對以后顧客的到達無影響。 5 5）輸入過程可以是平穩(wěn)的，也可以是非平穩(wěn)的。）輸入過程可以是平穩(wěn)的，也可以是非平穩(wěn)的。輸入過程平穩(wěn)的是指顧客相繼到達的間隔時間分布和輸入過程平穩(wěn)的是指顧客相繼到達的間隔時間分布和參數(shù)（均值、方差）與時間無關(guān)；非平穩(wěn)的則是與時參數(shù)（均值、方差）與時間無關(guān)；非平

11、穩(wěn)的則是與時間相關(guān)，非平穩(wěn)的處理比較困難。間相關(guān)，非平穩(wěn)的處理比較困難。11 這是指服務(wù)臺從隊列中選取顧客進行服務(wù)的順這是指服務(wù)臺從隊列中選取顧客進行服務(wù)的順序。可以分為序。可以分為損失制、等待制、混合制損失制、等待制、混合制3 3大類。大類。 (1)(1)損失制。損失制。這是指如果顧客到達排隊系統(tǒng)時，這是指如果顧客到達排隊系統(tǒng)時，所有服務(wù)臺都已被先來的顧客占用，那么他們就自所有服務(wù)臺都已被先來的顧客占用，那么他們就自動離開系統(tǒng)永不再來。動離開系統(tǒng)永不再來。 典型例子是，如電話拔號后出現(xiàn)忙音，顧客不典型例子是，如電話拔號后出現(xiàn)忙音，顧客不愿等待而自動掛斷電話，如要再打，就需重新拔愿等待而自動掛

12、斷電話，如要再打，就需重新拔號，這種服務(wù)規(guī)則即為損失制。號，這種服務(wù)規(guī)則即為損失制。 2 2、排隊規(guī)則、排隊規(guī)則12 (2)(2)等待制等待制。指當(dāng)顧客來到系統(tǒng)時，所有服務(wù)臺。指當(dāng)顧客來到系統(tǒng)時，所有服務(wù)臺都不空，顧客加入排隊行列等待服務(wù)。都不空，顧客加入排隊行列等待服務(wù)。 例如，排隊等待售票，故障設(shè)備等待維修等。例如，排隊等待售票，故障設(shè)備等待維修等。 等待制中，服務(wù)臺在選擇顧客進行服務(wù)時，常有等待制中，服務(wù)臺在選擇顧客進行服務(wù)時，常有如下四種規(guī)則：如下四種規(guī)則： 先到先服務(wù)（先到先服務(wù)（FCFS FCFS ）。按顧客到達的先后順。按顧客到達的先后順序?qū)︻櫩瓦M行服務(wù)，這是最普遍的情形。序?qū)︻?/p>

13、客進行服務(wù)，這是最普遍的情形。 后到先服務(wù)（后到先服務(wù)（LCFSLCFS）。倉庫中迭放的鋼材，。倉庫中迭放的鋼材，后迭放上去的都先被領(lǐng)走，就屬于這種情況。后迭放上去的都先被領(lǐng)走，就屬于這種情況。13 隨機服務(wù)隨機服務(wù)(RAND) 。即當(dāng)服務(wù)臺空閑。即當(dāng)服務(wù)臺空閑時，不按照排隊序列而隨意指定某個顧客去時，不按照排隊序列而隨意指定某個顧客去接受服務(wù)，如電話交換臺接通呼叫電話就是接受服務(wù)，如電話交換臺接通呼叫電話就是一例。一例。 優(yōu)先權(quán)服務(wù)優(yōu)先權(quán)服務(wù)(PR)。如老人、兒童先進。如老人、兒童先進車站；危重病員先就診；遇到重要數(shù)據(jù)需要車站；危重病員先就診；遇到重要數(shù)據(jù)需要處理計算機立即中斷其他數(shù)據(jù)的處理

14、等，均處理計算機立即中斷其他數(shù)據(jù)的處理等，均屬于此種服務(wù)規(guī)則。屬于此種服務(wù)規(guī)則。14 (3)(3)混合制混合制這是等待制與損失制相結(jié)合的一種服務(wù)規(guī)則，一般是指允許排隊，但又不允許隊列無限長下去。具體說來，大致有三種： 隊長有限。隊長有限。當(dāng)排隊等待服務(wù)顧客人數(shù)超過規(guī)定數(shù)量時，后來顧客就自動離去，另求服務(wù)，即系統(tǒng)的等待空間是有限的。例如最多只能容納N個顧客在系統(tǒng)中，當(dāng)新顧客到達時，若系統(tǒng)中的顧客數(shù)(又稱為隊長)小于N，則可進入系統(tǒng)排隊或接受服務(wù)；否則，便離開系統(tǒng)，并不再回來。再如水庫的庫容是有限的，旅館的床位是有限的。15 等待時間有限等待時間有限。即顧客在系統(tǒng)中的。即顧客在系統(tǒng)中的等待時間不超

15、過某一給定的長度等待時間不超過某一給定的長度T T，當(dāng)?shù)却?，?dāng)?shù)却龝r間超過時間超過T T時，顧客自動離去，不再回來。時，顧客自動離去，不再回來。 如易損壞的電子元器件的庫存問題，如易損壞的電子元器件的庫存問題，超過一定存儲時間被自動認(rèn)為失效。超過一定存儲時間被自動認(rèn)為失效。 又如顧客到飯館就餐，等了一定時間后又如顧客到飯館就餐，等了一定時間后不愿再等而自動離去另找飯店用餐。不愿再等而自動離去另找飯店用餐。16 逗留時間逗留時間( (等待時間與服務(wù)時間之和等待時間與服務(wù)時間之和) )有有限。限。 例如用高射炮射擊敵機，當(dāng)敵機飛越高射例如用高射炮射擊敵機，當(dāng)敵機飛越高射炮射擊有效區(qū)域的時間為炮射擊

16、有效區(qū)域的時間為t t時，若在這個時間時，若在這個時間內(nèi)未被擊落，也就不可能再被擊落了。內(nèi)未被擊落，也就不可能再被擊落了。 不難注意到，損失制和等待制可看成是混不難注意到，損失制和等待制可看成是混合制的特殊情形，如記合制的特殊情形，如記c c為系統(tǒng)中服務(wù)臺的個為系統(tǒng)中服務(wù)臺的個數(shù)，則當(dāng)數(shù)，則當(dāng)K=cK=c 時，混合制即成為損失制；當(dāng)時，混合制即成為損失制；當(dāng)K=K=時，混合制即成為等待制。時，混合制即成為等待制。173 3、服務(wù)臺、服務(wù)臺 服務(wù)臺可以從以下3方面來描述： (1) 服務(wù)臺數(shù)量及構(gòu)成形式服務(wù)臺數(shù)量及構(gòu)成形式。從數(shù)量上說，服務(wù)臺有單服務(wù)臺和多服務(wù)臺之分。從構(gòu)成形式上看，服務(wù)臺有：單隊

17、單服務(wù)臺式； 單隊多服務(wù)臺并聯(lián)式； 多隊多服務(wù)臺并聯(lián)式； 單隊多服務(wù)臺串聯(lián)式； 單隊多服務(wù)臺并串聯(lián)混合式,以及多隊列多服務(wù)臺并串聯(lián)混合式等等。 如之前的分類模型圖所示。如之前的分類模型圖所示。18 (2) 服務(wù)方式服務(wù)方式。這是指在某一時刻接受服務(wù)的顧客數(shù)，它有單個服務(wù)和成批服務(wù)兩種。如公共汽車一次就可裝載一批乘客就屬于成批服務(wù)。 (3) 服務(wù)時間的分布服務(wù)時間的分布。一般來說，在多數(shù)情況下，對每一個顧客的服務(wù)時間是一隨機變量，其概率分布有定長分布、負指數(shù)分布、K階愛爾朗分布、一般分布(所有顧客的服務(wù)時間都是獨立同分布的)等等。19排隊系統(tǒng)的描述符號與模型分類排隊系統(tǒng)的描述符號與模型分類 為了

18、區(qū)別各種排隊系統(tǒng)，根據(jù)輸入過程、排隊規(guī)則和服務(wù)機制的變化對排隊模型進行描述或分類，可給出很多排隊模型(見前面分析與圖示)。為了方便對眾多模型的描述,DG肯道爾（DGKendall）提出了一種目前在排隊論中被廣泛采用的“Kendall記號”，完整的表達方式通常用到6個符號并取如下固定格式：X X/Y/Z/A/B/C/Y/Z/A/B/C 各符號的意義如下：X X-表示顧客相繼到達間隔時間分布，表示顧客相繼到達間隔時間分布，常用下列符號：常用下列符號： MM表示到達過程為泊松過程或表示到達過程為泊松過程或( (負指數(shù)分布負指數(shù)分布Markov)Markov)； DD表示定長輸入表示定長輸入( (確定

19、型分布確定型分布Deterministic)Deterministic)； E EK K表示表示k k階愛爾朗分布；階愛爾朗分布； GI GI 一般相互獨立的隨機分布一般相互獨立的隨機分布( (General Independent)General Independent) G G表示一般的隨機分布。表示一般的隨機分布。20 Y Y-表示服務(wù)時間分布，表示服務(wù)時間分布，所用符號與表示顧客到達間隔時間分布相同。所用符號與表示顧客到達間隔時間分布相同。 Z-Z-表示服務(wù)臺表示服務(wù)臺( (員員) )個數(shù)：個數(shù)：“1”1”則表示單個服務(wù)臺，則表示單個服務(wù)臺，“s”s”。(s(s1)1)表表示多個服務(wù)臺

20、。示多個服務(wù)臺。 A-A-表示系統(tǒng)中顧客容量限額，表示系統(tǒng)中顧客容量限額，或稱等待空間容量；或稱等待空間容量； 如系統(tǒng)有如系統(tǒng)有K K個等待位子，則個等待位子，則 0K0K0),P(t0),Pn n(t1,t2)(t1,t2)表示在時間區(qū)間表示在時間區(qū)間t1,t2)(t2t1)t1,t2)(t2t1)內(nèi)有內(nèi)有n(0)n(0)個顧客到達的概率。即：個顧客到達的概率。即：)()(,1221ntNtNPttPn （t2t1，n0） 當(dāng)當(dāng)P Pn n(t1,t2)(t1,t2)同時符合下述三個條件時，顧客到達過程就是同時符合下述三個條件時，顧客到達過程就是泊松過程泊松過程( (顧客到達形成顧客到達形成

21、泊松泊松流流) )。 1 1、泊松分布、泊松分布27 無后效性：無后效性：各區(qū)間的到達相互獨立各區(qū)間的到達相互獨立, ,即即MarkovMarkov性。性。. . . . . . . t0 t1 t2 tn-1 tn|)(|)(11112211)()(,.,)(,)(nnnnxtxnxtxxtxxtxnntxPntxP 也就是說過程在也就是說過程在t+tt+t所處的狀態(tài)與所處的狀態(tài)與t t以前所處的狀以前所處的狀態(tài)無關(guān)。態(tài)無關(guān)。 平穩(wěn)性：平穩(wěn)性：即對于足夠小的即對于足夠小的tt，有：，有：)()(tttttP ，1泊松流具有如下特性：泊松流具有如下特性： 在在t,t+tt,t+t內(nèi)有一個顧客到

22、達的概率與內(nèi)有一個顧客到達的概率與t t無關(guān)無關(guān), ,而與而與tt成正比。成正比。28 普通性：普通性：對充分小的對充分小的t,t,在時間區(qū)間（在時間區(qū)間（t,t+tt）內(nèi)有內(nèi)有2 2個或個或2 2個以上顧客到達的概率是一高階無窮小個以上顧客到達的概率是一高階無窮小. . 由此知，在由此知，在(t，t+t)t)區(qū)間內(nèi)沒有顧客到達的概率為：區(qū)間內(nèi)沒有顧客到達的概率為：)(1),(0tottttP 令令t1 1=0,t=0,t2 2=t,=t,則則P(tP(t1 1,t,t2 2)=P)=Pn n(0,t)=P(0,t)=Pn n(t)(t) 0 0 是常數(shù)，它是常數(shù)，它表示單位時間到達的顧客數(shù)，

23、稱表示單位時間到達的顧客數(shù)，稱為概率強度。為概率強度。2)(),(nntotttP 即即 P P0 0+P+P1 1+P+P22=1=1 下面將討論求關(guān)鍵的下面將討論求關(guān)鍵的P Pn n(t)(t)。 29情情 形形 0 0， t t) ) 概概 率率 t t， t t+ + t t) ) 概概 率率 0 0， t t+ + t t ） A A n n P Pn n( (t t) ) 0 0 1 1- - t t + + O O( ( t t) ) P Pn n( (t t) )( (1 1- - t t + + O O( ( t t) ) ) B B n n- -1 1 P Pn n- -1

24、 1( (t t) ) 1 1 t t P Pn n- -1 1( (t t) ) t t n n- -2 2 P Pn n- -2 2( (t t) ) 2 2 n n- -3 3 P Pn n- -3 3( (t t) ) 3 3 . . . . . . . . . . . . C C 0 0 P P0 0( (t t) ) n O O( ( t t) ) O O( ( t t) ) 在在00，t+tt+t內(nèi)到達內(nèi)到達n n個顧客應(yīng)是上面三種互不相個顧客應(yīng)是上面三種互不相容的情況之一，所以有：容的情況之一，所以有： 為了求為了求Pn(t),即即Pn(0,t)，需要研究它在（，需要研究它在（

25、t，t+tt）上的改變）上的改變量量, ,建立建立P Pn n(t)(t)的微分方程。對于區(qū)間的微分方程。對于區(qū)間0,0,t+t)+t)可以分成可以分成00，t)t)和和tt，t+t),t+t),其到達總數(shù)是其到達總數(shù)是n n，不外有下列三種情況：，不外有下列三種情況：00,()0,nnnn kkkPttP ttPt P t tt30 令令t0t0取極限（并注意初始條件）得：取極限（并注意初始條件）得：)()()(1tPtPdttdPnnn (3)(3) 當(dāng)當(dāng)n=0時，沒有時，沒有B，C兩種情況，則：兩種情況，則：)()(00tPdttdP1)0(0P (4)(4)()()1)()(1tOtt

26、PttPttPnnn)()()()()(1tOttPttPtPttPnnnnttOtPtPttPttPnnnn)()()()()(1 湊微分湊微分 區(qū)間長度（區(qū)間長度（0 0，0 0）有有n n個顧客到達個顧客到達 (0,t)(0,t)有有n-1,n-2n-1,n-2個個顧客到達顧客到達(0)0nP 即：即：31ln10tCC C C = 0 = 00ln( )Ptt （3 3）式兩端乘）式兩端乘e e t t并移項得：并移項得： te)t(P 0 (5)(5) （沒有顧客到達的概率）（沒有顧客到達的概率）dtPtdP )()(0000ln( )P ttC 兩邊積分得：兩邊積分得： 代入初始條

27、件代入初始條件( (t=0)t=0)有：有： P P0 0(0)=1(0)=1)t(P)t(Pdt)t(dPnnn1 )()(00tPdttdP(0)0nP32 將將n=1,2,3代入（代入（6）得：）得：tntnetPetPdtd )()(1 11101)()(dtetPetPtnttn (6)(6)110011)()(dtetPetPttt (注意利用注意利用(5)式式)tdteettt 1011tntntne )t (Pe )t (Pedt)t (dP 1tntnnte )t(Pe )t(Pdt)t(dPe 1 湊成湊成P Pn n(t)e(t)e t t兩兩項乘積的微分項乘積的微分 兩

28、邊積分兩邊積分te)t(P 033 如此繼續(xù)遞推下去得：如此繼續(xù)遞推下去得：tettP !2)()(22 （2 2個顧客到達的概率）個顧客到達的概率） （n n個顧客到達的概率）個顧客到達的概率）tnnenttP !)()( 即隨機變量即隨機變量N(t)=n服從泊松分布。它的數(shù)學(xué)期望服從泊松分布。它的數(shù)學(xué)期望和方差為：和方差為：ttetP )(1 （1 1個顧客到達的概率）個顧客到達的概率）11011102111)()(dteetdtetPetPtttttt 2221t 34 引入級數(shù)引入級數(shù).!nx.!xxenx 212 tkke!k)t( 0!)()()(11ntnetnPtNEnntnn

29、 )!1()(11 nttennt 令令k=n-1，則：，則：!)()(0kttetNEkkt tetetNEtt )(352121)()!1()()!2()(tntntttennnt tttttettett 22)()1()1(ttar )(N(V 即即：21221)(!)()()(tntnnettPnnntnn 22E(N(t)EN(t)( tNVar 同理方差為：同理方差為：211121)()!1()()!1()() 1()()!1()(tntntntetntnnennntnnt 說明顧客到達過程確實是一個說明顧客到達過程確實是一個泊松過程泊松過程( (泊松泊松流流) )，這也是泊松分布

30、的數(shù)學(xué)推導(dǎo)。這也是泊松分布的數(shù)學(xué)推導(dǎo)。36 其概率密度函數(shù)為：其概率密度函數(shù)為：tTTedtdF)t(f t0t02 2、負指數(shù)分布、負指數(shù)分布 當(dāng)輸入過程是泊松流時，我們研究兩顧客相繼到當(dāng)輸入過程是泊松流時，我們研究兩顧客相繼到達的時間間隔的概率分布。達的時間間隔的概率分布。 設(shè)設(shè)T T為時間間隔，分布函數(shù)為為時間間隔，分布函數(shù)為F FT T（t t），則：），則：F FT T（t t）=PTt=PTt 此概率等價于在此概率等價于在0,t)0,t)區(qū)間內(nèi)至少有區(qū)間內(nèi)至少有1 1個顧客到達個顧客到達的概率。的概率。tTetPtF 1)(1)(0 t0t0tetP)(0 沒有顧客到達的概率為：沒

31、有顧客到達的概率為： (由（由（5）式而來）式而來) 間隔：間隔： 間隔：間隔： 間隔間隔 對分布函對分布函數(shù)微分?jǐn)?shù)微分37 表示單位時間內(nèi)顧客平均到達數(shù)。表示單位時間內(nèi)顧客平均到達數(shù)。 1/表示顧客到達的平均間隔時間。表示顧客到達的平均間隔時間。 可以證明，間隔時間可以證明，間隔時間T T獨立且服從負指數(shù)分布與獨立且服從負指數(shù)分布與顧客到達形成泊松流是等價的。負指數(shù)分布是一種無顧客到達形成泊松流是等價的。負指數(shù)分布是一種無記憶性的分布。記憶性的分布。對顧客的服務(wù)時間對顧客的服務(wù)時間 ：系統(tǒng)處于忙期時系統(tǒng)處于忙期時兩顧客相繼離兩顧客相繼離開系統(tǒng)的時間間隔開系統(tǒng)的時間間隔，一般地也服從負指數(shù)分布

32、。，一般地也服從負指數(shù)分布。 即即T服從負指數(shù)分布，它的期望及方差為：服從負指數(shù)分布，它的期望及方差為： 1TE21 TVar 接受服務(wù)，然后離開接受服務(wù)，然后離開服務(wù)時間的分布：服務(wù)時間的分布：即：即：P(Xt+s|Xt)=P(Xs)P(Xt+s|Xt)=P(Xs)38其中：其中：表示單位時間內(nèi)能被服務(wù)的顧客數(shù)，即平均表示單位時間內(nèi)能被服務(wù)的顧客數(shù)，即平均 服務(wù)率。服務(wù)率。 1/1/表示一個顧客的平均服務(wù)時間。表示一個顧客的平均服務(wù)時間。3 3、愛爾朗、愛爾朗(Erlang)(Erlang)分布分布 設(shè)設(shè)v v1 1, v, v2 2，, v, vk k是是k k個獨立的隨機變量，服從相同個

33、獨立的隨機變量，服從相同參數(shù)參數(shù) k k 的負指數(shù)分布，那么：的負指數(shù)分布，那么：tetF 1)(tetf )( ，則，則 令令 ，則，則稱為服務(wù)強度稱為服務(wù)強度。kT 21 令令39 串列串列k k個服務(wù)臺個服務(wù)臺，每臺服務(wù)時間相互獨立，服從，每臺服務(wù)時間相互獨立，服從相同負指數(shù)分布（參數(shù)相同負指數(shù)分布（參數(shù)k k ），那么一顧客走完），那么一顧客走完k k個服個服務(wù)臺總共所需要服務(wù)時間服從上述務(wù)臺總共所需要服務(wù)時間服從上述k k階階ErlangErlang分布。分布。011 te)!k()kt(k)t (ftkkk 則稱則稱T服從服從k階階愛爾朗分布。其特征值為：愛爾朗分布。其特征值為：

34、1TE21 kTVar ,其概率密度是其概率密度是1/ k1/ k表示一個顧客一個服務(wù)臺的平均服務(wù)時間。表示一個顧客一個服務(wù)臺的平均服務(wù)時間。 其他常用的分布參見教材其他常用的分布參見教材P122-123P122-123，也可參見概，也可參見概率論與數(shù)理統(tǒng)計相關(guān)教程。率論與數(shù)理統(tǒng)計相關(guān)教程。40生滅過程生滅過程1、生滅過程簡介、生滅過程簡介 一類非常重要且廣泛存在的排隊系統(tǒng)是生滅過程排隊系統(tǒng)。生滅過程是一類特殊的隨機過程，在生物學(xué)、物理學(xué)、運籌學(xué)中有廣泛的應(yīng)用。 2 2、生滅過程的定義、生滅過程的定義 設(shè)N(t),t0 為一個隨機過程。 如N(t)的概率分布具有以下性質(zhì)： (1)假設(shè)N(t)=

35、n，則從時刻t起到下一個顧客到達時刻止的時間服從參數(shù)為n的負指數(shù)分布，n=0，1，2，。間隔時間分布間隔時間分布 (2)假設(shè)N(t)=n，則從時刻t起到下一個顧客離去時刻止的時間服從參數(shù)為n的負指數(shù)分布，n=0，1，2，。服務(wù)時間分布服務(wù)時間分布 (3)同一時刻只有一個顧客到達或離去。 則稱設(shè)N(t),t0 為一個生滅過程。41 顧客到達“生”； 顧客離開“滅” n ， n ，生滅過程示意圖：顧客到達顧客到達顧客離去顧客離去42 一般說來，得到 是比較困難的或非理論作用不太大，因此通常是求當(dāng)系統(tǒng)達到平穩(wěn)狀態(tài)后的狀態(tài)分布，記為 , n=0,1,2, 為求平穩(wěn)分布 ，考慮系統(tǒng)在 t+t 時刻可能處

36、的任一狀態(tài)n的概率?？山o出狀態(tài)轉(zhuǎn)移圖如下：np( )( ) ( )nN tp tP N tn的分布np狀態(tài)轉(zhuǎn)移圖狀態(tài)轉(zhuǎn)移圖 說明：說明：n n狀態(tài)下，排隊系統(tǒng)中的人數(shù)穩(wěn)定為狀態(tài)下，排隊系統(tǒng)中的人數(shù)穩(wěn)定為n,n=0,1,2,.,n,n=0,1,2,.,即進了多少個就要出去多少個。即進了多少個就要出去多少個。43方式方式 t t時刻狀態(tài)時刻狀態(tài)t t狀態(tài)的狀態(tài)的概率概率（t,t+tt,t+t）內(nèi)發(fā)生）內(nèi)發(fā)生的事件的事件發(fā)生的概率發(fā)生的概率1n nP Pn n(t)(t)0 0人到達，人到達，0 0人離去人離去 （1-n nt） (1-n nt) 2n -1n -1P Pn-1n-1(t)(t)1

37、1人到達，人到達，0 0人離去人離去 n-1n-1t (1-n-1n-1t) 3n +1n +1P Pn+1n+1(t)(t)0 0人到達，人到達，1 1人離去人離去(1-n+1n+1t) n+1n+1t 4n nP Pn n(t)(t)1 1人到達，同時人到達，同時1 1人離人離去去(n nt) (n nt) 各種方式下發(fā)生概率表（保證各種方式下發(fā)生概率表（保證n狀態(tài)狀態(tài):t+tt時刻時刻穩(wěn)定有穩(wěn)定有n個人）個人） 說明：狀態(tài)說明：狀態(tài)n n下，下，1 1人到達的概率約為人到達的概率約為 n ntt，1 1人離去的概人離去的概率約為率約為 n ntt，0 0人到達的概率約為人到達的概率約為1

38、-1-n ntt，0 0人離去的概率約為人離去的概率約為1-1-n ntt。( (根據(jù)根據(jù)泊松流的特征得到泊松流的特征得到) )44又因為前述方式1，2，3，4是互不相容且完備互不相容且完備的，因此有：111111()( ) (1)(1)( ) ()(1)( ) (1)()( ) ()()nnnnnnnnnnnnnP ttP tttPtttPtttP ttt 0()( )limnntP ttP tt1111( )( )()( )nnnnnnnPtP tPt對上式展開并構(gòu)造如下極限式： ，則有：，則有： 這剛好就是這剛好就是P Pn n(t)(t)對對t t的導(dǎo)數(shù)。的導(dǎo)數(shù)。 事件事件(0,t+(

39、0,t+t)t)發(fā)生可發(fā)生可看作事件看作事件(0,t(0,t）和事件）和事件(t,t+(t,t+t)t)同時發(fā)生。因同時發(fā)生。因此：此：P(0,t+P(0,t+t)= t)= P(0,t)P(t,t+P(0,t)P(t,t+t)t)45當(dāng)n=0時，只有方式1和3，4發(fā)生，且方式1中無離去的概率為1，則:00011( )( )( )dP tP tP tdt 設(shè)系統(tǒng)是穩(wěn)態(tài)的，即與時刻t無關(guān)，于是可得：( )0ndPtdt0011111100()0,1,2,nnnnnnnPPnPPPn令P0已知，可用遞推方法求得：4600110PP0101()PP0011122()0PPP1111122()0PPP

40、012011122()PPP 120011.nnnnnPP記12011.nnnnnC則平穩(wěn)狀態(tài)的分布為：0nnPC P 下面求下面求P P0 0。47由概率分布的要求：01nnP0111nnCP有：0111nnPC即綜上述，得到各狀態(tài)平衡時的概率分布遞推計算式如下：12001101.11nnnnnnnPPPC 所以關(guān)鍵是得到各狀態(tài)下單位時間單位時間到達和離開的人數(shù)：,0 ,1,nnn48例：某小型超市有一個收款臺。付款顧客以每小時30人的負指數(shù)分布到達。當(dāng)收款臺前只有一名顧客時，有一名收款員單獨服務(wù)，收款時間為平均1.5min的負指數(shù)分布；當(dāng)有2名或以上顧客時，將增加一名助手共同為顧客服務(wù)，收

41、款時間將縮短至平均1min的負指數(shù)分布。求收款臺前有n名顧客的概率Pn01.30/nh人16040/1.5h人260.60/1nh人解：這里的單位時間是1小時，所以491011112.303 1( ).(40)(60)4 2nnnnnnC n=1,2.=011111231511.( )42nnnnPC則有由0nnPC P可知：131231()()42552nnnP50 一般地，對排隊模型，在給定輸入和服務(wù)條件下，一般地，對排隊模型，在給定輸入和服務(wù)條件下，主要研究系統(tǒng)的下述運行指標(biāo)：主要研究系統(tǒng)的下述運行指標(biāo)： (1)(1)系統(tǒng)的系統(tǒng)的平均隊長平均隊長L Ls s( (期望值期望值) )和和平

42、均隊列長平均隊列長L Lq q( (期望值期望值) )； (2)(2)系統(tǒng)中系統(tǒng)中顧客平均逗留時間顧客平均逗留時間W Ws s與隊列中與隊列中平均等待平均等待時間時間W Wq q；M/M/sM/M/s等待制排隊模型等待制排隊模型單服務(wù)臺模型：單服務(wù)臺模型： M/M/1/ M/M/1/ 是指：顧客的相繼到達時間服從參數(shù)為的負指數(shù)分布，服務(wù)臺數(shù)為1，服務(wù)時間服從參數(shù)為的負指數(shù)分布，系統(tǒng)空間無限，允許無限排隊。511、隊長的分布、隊長的分布(參數(shù)、就是單位時間進入或被服務(wù)的人數(shù))所以n =( n=0，1，2，)，n =( n=0，1，2，)記 = / ，并設(shè) 1 (否則隊列將排至無限遠)， 則()n

43、nC0nnppn= 1,2,.，n= 1,2,而1100111()()111nnnnpC 因此(1)nnP n=0,1,2是系統(tǒng)中至少有一個顧客的概率，也就是服務(wù)臺處于忙的狀態(tài)的概率，因而也稱為服務(wù)強度為服務(wù)強度，它反映了系統(tǒng)繁忙的程度。即為平衡條件下系統(tǒng)中顧客數(shù)為n的概率。522. 系統(tǒng)的運行指標(biāo)計算系統(tǒng)的運行指標(biāo)計算 (1) 系統(tǒng)中的隊長系統(tǒng)中的隊長Ls（平均隊長：排隊（平均隊長：排隊+被服務(wù)）被服務(wù)） nnnnsnPnL 001.)(n.)()()(n 11312132.nn.nn 1433223322 132.n (01) 1 期望期望53(2) 隊列中等待的平均顧客數(shù)隊列中等待的平均

44、顧客數(shù)Lq ：僅排隊：僅排隊 nnnnqnPnL 111) 1() 1( nnnn)(n 1111221sL (3) 顧客在顧客在系統(tǒng)中的平均逗留時間系統(tǒng)中的平均逗留時間Ws 顧客在系統(tǒng)中的逗留時間是隨機變量，可以證顧客在系統(tǒng)中的逗留時間是隨機變量，可以證明，它服從參數(shù)為明，它服從參數(shù)為-的負指數(shù)分布，分布函數(shù)的負指數(shù)分布，分布函數(shù) 11nn54 和密度函數(shù)為：和密度函數(shù)為：w)(e)w(F 1w)(e )()w( f （w00）()ssLW 1sWE w (4) (4)顧客在顧客在隊列中的平均逗留時間隊列中的平均逗留時間W Wq q 111qsWW ()qqLW 等待時等待時間間 顧客在隊列

45、中的平均逗留時間應(yīng)為顧客在隊列中的平均逗留時間應(yīng)為W Ws s減去平均服減去平均服務(wù)時間。務(wù)時間。 考慮考慮L LS S與與W WS S的關(guān)的關(guān)系系55 LsLsLLqs 12WsLs WqLq 四個指標(biāo)的關(guān)系為四個指標(biāo)的關(guān)系為(Little Little 公式公式)： 3. 系統(tǒng)的忙期與閑期系統(tǒng)的忙期與閑期 系統(tǒng)處于空閑狀態(tài)的概率：系統(tǒng)處于空閑狀態(tài)的概率： 10P 系統(tǒng)處于繁忙狀態(tài)的概率：系統(tǒng)處于繁忙狀態(tài)的概率： 010P)N(P服服務(wù)務(wù)強強度度56 在繁忙狀態(tài)下，隊列中的平均顧客數(shù)在繁忙狀態(tài)下，隊列中的平均顧客數(shù)L Lb b：(0)qbsLLLP N 顧客平均等待時間顧客平均等待時間:1(

46、0)qbsWWWP N 忙期的平均長度忙期的平均長度: 1B 1IB ( (由由 來來) ) 一個忙期平均服務(wù)顧客數(shù)為：一個忙期平均服務(wù)顧客數(shù)為： 111 L Lb bP P(N0)(N0)=L=Lq q57例：某修理店只有一個修理工，來修理的顧客到達過程為Poisson流，平均4人/h; 修理時間服從負指數(shù)分布，平均需要6min。試求：（1）修理店空閑的概率（2）店內(nèi)恰有3個顧客的概率（3）店內(nèi)至少有1個顧客的概率（4）在店內(nèi)的平均顧客數(shù)（5）每位顧客在店內(nèi)的平均逗留時間（6）等待服務(wù)的平均顧客數(shù)（7）每位顧客平均等待服務(wù)時間（8）顧客在店內(nèi)等待時間超過10min的概率58解 本例可看成一個

47、M/M/1/排隊問題，其中124100.15（1）修理店空閑的概率02110.65p（2）店內(nèi)恰有3個顧客的概率33322(1)() (1)0.03855p（3）店內(nèi)至少有1個顧客的概率02110.45P Np 59（4）在店內(nèi)的平均顧客數(shù)25250.6711L（5）每位顧客在店內(nèi)的平均逗留時間0.67( )10(min)4LWh（人）（6）等待服務(wù)的平均顧客數(shù)2 22()5250.26711qLL（人）60（7）每位顧客平均等待服務(wù)的時間0.267( ) 4(min)4qqLWh（8）顧客在店內(nèi)逗留時間超過10min的概率由于逗留時間服從參數(shù) 的負指數(shù)分布，即分布函數(shù)為()0tP Ttet

48、則10(1/6 1/15)1100.3679P Tee注：對于： 1小時 10 人 則 1分鐘 10/60=1/6(人)。同理61多服務(wù)臺模型：多服務(wù)臺模型： M/M/s/M/M/s/ M/M/s/ 是指：設(shè)顧客單個到達，相繼到達時間服從參數(shù)為的負指數(shù)分布，服務(wù)臺數(shù)為s，每個服務(wù)臺的服務(wù)時間相互獨立，且服從參數(shù)為的負指數(shù)分布，系統(tǒng)空間無限，允許無限排隊。當(dāng)考慮系統(tǒng)處于平穩(wěn)狀態(tài)后隊長N的概率分布,有(1,2. )(,1,2.)nnnnssss ss1、隊長的分布62記ssc且1s有( /)!( /)( /)()!nnsn sn snCsss s n=1,2,sns故00,1,2,!,!nnnn spnsnPpnss s其中1100)!(1nssnspns63上面兩個式子給出了平衡條件下系統(tǒng)中顧客數(shù)為n的概率，當(dāng)ns時，即系統(tǒng)中顧客數(shù)大于服務(wù)臺個數(shù)，這時再來的顧客必須等待，因此記：0( ,)!(1)snn ssc sPPsErlang等待公式它給出了顧客到達系統(tǒng)時需要等待的概率。由平穩(wěn)狀態(tài)下隊長N的概率分布，可得到平均排隊長Lq:021()!(1)ssqnnssPLns Ps 2、幾個主要數(shù)量指標(biāo)640( ,)!(