第08章 排隊(duì)論 運(yùn)籌學(xué)

1、1第第8 8章章 排隊(duì)論排隊(duì)論本章內(nèi)容重點(diǎn)本章內(nèi)容重點(diǎn) 排隊(duì)論基本概念排隊(duì)論基本概念 基本問題與求解思路基本問題與求解思路 泊松輸入泊松輸入指數(shù)服務(wù)排隊(duì)模型指數(shù)服務(wù)排隊(duì)模型 其他模型選介其他模型選介 排隊(duì)系統(tǒng)的優(yōu)化排隊(duì)系統(tǒng)的優(yōu)化3 排隊(duì)論排隊(duì)論(Queuing Theory)(Queuing Theory)，又，又稱 隨 機(jī) 服 務(wù) 系 統(tǒng) 理 論稱 隨 機(jī) 服 務(wù) 系 統(tǒng) 理 論 ( R a n d o m ( R a n d o m Service System Theory),Service System Theory),是一門研是一門研究擁擠現(xiàn)象究擁擠現(xiàn)象( (排隊(duì)、等待排隊(duì)、等待)

2、)的科學(xué)。具的科學(xué)。具體地說，它是在研究各種排隊(duì)系統(tǒng)概體地說，它是在研究各種排隊(duì)系統(tǒng)概率規(guī)律性的基礎(chǔ)上，解決相應(yīng)排隊(duì)系率規(guī)律性的基礎(chǔ)上，解決相應(yīng)排隊(duì)系統(tǒng)的最優(yōu)設(shè)計(jì)和最優(yōu)控制問題。統(tǒng)的最優(yōu)設(shè)計(jì)和最優(yōu)控制問題。前前 言言4 排隊(duì)論是排隊(duì)論是19091909年由丹麥工程師愛年由丹麥工程師愛爾朗爾朗(A.K(A.KErlangErlang) )在研究電活系統(tǒng)時(shí)在研究電活系統(tǒng)時(shí)創(chuàng)立的，幾十年來排隊(duì)論的應(yīng)用領(lǐng)域創(chuàng)立的，幾十年來排隊(duì)論的應(yīng)用領(lǐng)域越來越廣泛，理論也日漸完善。特別越來越廣泛，理論也日漸完善。特別是自二十世紀(jì)是自二十世紀(jì)6060年代以來，由于計(jì)算年代以來，由于計(jì)算機(jī)的飛速發(fā)展，更為排隊(duì)論的應(yīng)用開機(jī)

3、的飛速發(fā)展，更為排隊(duì)論的應(yīng)用開拓了寬闊的前景。拓了寬闊的前景。前前 言言51. 1. 排隊(duì)論基本概念排隊(duì)論基本概念 排隊(duì)是我們?cè)谌粘Ｉ詈蜕a(chǎn)中經(jīng)常排隊(duì)是我們?cè)谌粘Ｉ詈蜕a(chǎn)中經(jīng)常遇到的現(xiàn)象遇到的現(xiàn)象: :上、下班搭乘公共汽車；上、下班搭乘公共汽車；顧客到商店購買物品；顧客到商店購買物品；病員到醫(yī)院看病；病員到醫(yī)院看??；旅客到售票處購買車票；旅客到售票處購買車票；學(xué)生去食堂就餐等就常常出現(xiàn)排隊(duì)和等學(xué)生去食堂就餐等就常常出現(xiàn)排隊(duì)和等待現(xiàn)象。待現(xiàn)象。排隊(duì)的不一定是人，也可以是物：排隊(duì)的不一定是人，也可以是物： 通訊衛(wèi)星與地面待傳遞的信息；通訊衛(wèi)星與地面待傳遞的信息； 生產(chǎn)線上的原料、半成品等待加工

4、；生產(chǎn)線上的原料、半成品等待加工； 因故障停止運(yùn)轉(zhuǎn)的機(jī)器等待工人修理；因故障停止運(yùn)轉(zhuǎn)的機(jī)器等待工人修理； 碼頭的船只等待裝卸貨物；碼頭的船只等待裝卸貨物； 要降落的飛機(jī)因跑道不空而在空中盤要降落的飛機(jī)因跑道不空而在空中盤旋等等。旋等等。71.1 排隊(duì)系統(tǒng)特征與基本過程排隊(duì)系統(tǒng)特征與基本過程1) 排隊(duì)問題的共同特征排隊(duì)問題的共同特征 有要求某種服務(wù)的人或物。排隊(duì)論里有要求某種服務(wù)的人或物。排隊(duì)論里把要求服務(wù)的對(duì)象統(tǒng)稱為把要求服務(wù)的對(duì)象統(tǒng)稱為“顧客顧客” 有提供服務(wù)的人或機(jī)構(gòu)。把提供服務(wù)有提供服務(wù)的人或機(jī)構(gòu)。把提供服務(wù)的人或機(jī)構(gòu)稱為的人或機(jī)構(gòu)稱為“服務(wù)臺(tái)服務(wù)臺(tái)”或或“服務(wù)員服務(wù)員” 顧客的到達(dá)、服

5、務(wù)的時(shí)間至少有一個(gè)顧客的到達(dá)、服務(wù)的時(shí)間至少有一個(gè)是是隨機(jī)隨機(jī)的，服從某種分布。的，服從某種分布。82) 基本排隊(duì)過程基本排隊(duì)過程 任何一個(gè)排隊(duì)問題的基本排隊(duì)任何一個(gè)排隊(duì)問題的基本排隊(duì)過程都可以用圖過程都可以用圖 8-18-1表示：每個(gè)顧表示：每個(gè)顧客由顧客源按照一定方式到達(dá)服務(wù)客由顧客源按照一定方式到達(dá)服務(wù)系統(tǒng)，首先加入隊(duì)列排隊(duì)等待接受系統(tǒng)，首先加入隊(duì)列排隊(duì)等待接受服務(wù)，然后服務(wù)臺(tái)按一定規(guī)則從隊(duì)服務(wù)，然后服務(wù)臺(tái)按一定規(guī)則從隊(duì)列中選擇顧客進(jìn)行服務(wù)，獲得服務(wù)列中選擇顧客進(jìn)行服務(wù)，獲得服務(wù)后的顧客立即離開。后的顧客立即離開。一般排隊(duì)系統(tǒng)都可由下圖（一般排隊(duì)系統(tǒng)都可由下圖（圖圖8-1）描述）描述圖圖

6、8-1 8-1 隨機(jī)服務(wù)系統(tǒng)隨機(jī)服務(wù)系統(tǒng)排隊(duì)系統(tǒng)示意圖排隊(duì)系統(tǒng)示意圖10 面對(duì)擁擠現(xiàn)象，顧客排隊(duì)時(shí)間的長短面對(duì)擁擠現(xiàn)象，顧客排隊(duì)時(shí)間的長短與服務(wù)設(shè)施規(guī)模的大小，就構(gòu)成了設(shè)計(jì)與服務(wù)設(shè)施規(guī)模的大小，就構(gòu)成了設(shè)計(jì)隨機(jī)服務(wù)系統(tǒng)中的一對(duì)矛盾。隨機(jī)服務(wù)系統(tǒng)中的一對(duì)矛盾。 如何做到既保證一定的服務(wù)質(zhì)量指標(biāo)，如何做到既保證一定的服務(wù)質(zhì)量指標(biāo)，又使服務(wù)設(shè)施費(fèi)用經(jīng)濟(jì)合理，恰當(dāng)?shù)亟庥质狗?wù)設(shè)施費(fèi)用經(jīng)濟(jì)合理，恰當(dāng)?shù)亟鉀Q顧客排隊(duì)時(shí)間與服務(wù)設(shè)施費(fèi)用大小這決顧客排隊(duì)時(shí)間與服務(wù)設(shè)施費(fèi)用大小這對(duì)矛盾，這就是排隊(duì)論所要研究解決的對(duì)矛盾，這就是排隊(duì)論所要研究解決的問題之一。問題之一。11 通常，排隊(duì)系統(tǒng)都有通常，排隊(duì)系統(tǒng)都有輸入過

7、程輸入過程、服務(wù)規(guī)則服務(wù)規(guī)則和和服務(wù)臺(tái)服務(wù)臺(tái)等等3 3個(gè)組成部分：個(gè)組成部分： 1) 1) 輸入過程輸入過程這是指要求服務(wù)的顧這是指要求服務(wù)的顧客是按怎樣的規(guī)律到達(dá)排隊(duì)系統(tǒng)的過程，客是按怎樣的規(guī)律到達(dá)排隊(duì)系統(tǒng)的過程，有時(shí)也把它稱為顧客流一般可以從有時(shí)也把它稱為顧客流一般可以從3 3個(gè)方面來描述一個(gè)輸入過程。個(gè)方面來描述一個(gè)輸入過程。1.2 1.2 排隊(duì)系統(tǒng)的基本組成部分排隊(duì)系統(tǒng)的基本組成部分121) 1) 輸入過程輸入過程 顧客總體數(shù)顧客總體數(shù)( (又稱又稱顧客源顧客源、輸、輸入源入源) )。這是指顧客的來源。顧。這是指顧客的來源。顧客源可以是客源可以是有限有限的，也可以是的，也可以是無無限限

8、的。例如，到售票處購票的顧的。例如，到售票處購票的顧客總數(shù)可以認(rèn)為是無限的，而某客總數(shù)可以認(rèn)為是無限的，而某個(gè)工廠因故障待修的機(jī)床則是有個(gè)工廠因故障待修的機(jī)床則是有限的。限的。13 顧客到達(dá)方式顧客到達(dá)方式。描述顧客是怎描述顧客是怎樣來到系統(tǒng)的，他們是單個(gè)到達(dá)，還樣來到系統(tǒng)的，他們是單個(gè)到達(dá)，還是成批到達(dá)。病人到醫(yī)院看病是顧客是成批到達(dá)。病人到醫(yī)院看病是顧客單個(gè)到達(dá)的例子。在庫存問題中如將單個(gè)到達(dá)的例子。在庫存問題中如將生產(chǎn)器材進(jìn)貨或產(chǎn)品入庫看作是顧客，生產(chǎn)器材進(jìn)貨或產(chǎn)品入庫看作是顧客，那么這種顧客則是成批到達(dá)的。那么這種顧客則是成批到達(dá)的。1) 1) 輸入過程輸入過程141) 輸入過程輸入過

9、程 顧客流的概率分布顧客流的概率分布，或稱，或稱相繼顧相繼顧客到達(dá)的時(shí)間間隔的分布客到達(dá)的時(shí)間間隔的分布。這是求這是求解排隊(duì)系統(tǒng)有關(guān)運(yùn)行指標(biāo)問題時(shí)，首先解排隊(duì)系統(tǒng)有關(guān)運(yùn)行指標(biāo)問題時(shí)，首先需要確定的指標(biāo)。流可以理解為在一定需要確定的指標(biāo)。流可以理解為在一定的時(shí)間間隔內(nèi)到達(dá)的時(shí)間間隔內(nèi)到達(dá)k個(gè)顧客個(gè)顧客(k =1、2、)的概率是多大。的概率是多大。顧客流的概率分布一般顧客流的概率分布一般有定長分布、二項(xiàng)分布、泊松流有定長分布、二項(xiàng)分布、泊松流( (最簡(jiǎn)最簡(jiǎn)單流單流) )、愛爾朗分布等若干種。、愛爾朗分布等若干種。15 指服務(wù)臺(tái)從隊(duì)列中選取顧客進(jìn)指服務(wù)臺(tái)從隊(duì)列中選取顧客進(jìn)行服務(wù)的順序。一般可以分為行

10、服務(wù)的順序。一般可以分為損失損失制制、等待制等待制和和混合制混合制等等3 3大類。大類。 損失制損失制。如果顧客到達(dá)排隊(duì)系統(tǒng)如果顧客到達(dá)排隊(duì)系統(tǒng)時(shí)，所有服務(wù)臺(tái)都已被占用，那么他時(shí)，所有服務(wù)臺(tái)都已被占用，那么他們就自動(dòng)離開系統(tǒng)永不再來。們就自動(dòng)離開系統(tǒng)永不再來。2) 服務(wù)規(guī)則服務(wù)規(guī)則 等待制等待制。當(dāng)顧客來到系統(tǒng)時(shí)，所有服務(wù)當(dāng)顧客來到系統(tǒng)時(shí)，所有服務(wù)臺(tái)都不空，顧客加入排隊(duì)行列等待服務(wù)。等臺(tái)都不空，顧客加入排隊(duì)行列等待服務(wù)。等待制中，服務(wù)臺(tái)在選擇顧客進(jìn)行服務(wù)時(shí)，常待制中，服務(wù)臺(tái)在選擇顧客進(jìn)行服務(wù)時(shí)，常有如下四種規(guī)則：有如下四種規(guī)則： 先到先服務(wù)。先到先服務(wù)。按顧客到達(dá)的先后順序?qū)︻櫚搭櫩偷竭_(dá)的先后

11、順序?qū)︻櫩瓦M(jìn)行服務(wù)，這是最普遍的情形?？瓦M(jìn)行服務(wù)，這是最普遍的情形。 后到先服務(wù)。后到先服務(wù)。倉庫中迭放的鋼材，后迭放倉庫中迭放的鋼材，后迭放上去的都先被領(lǐng)走，就屬于這種情況。上去的都先被領(lǐng)走，就屬于這種情況。2) 服務(wù)規(guī)則服務(wù)規(guī)則17 隨機(jī)服務(wù)隨機(jī)服務(wù)。即當(dāng)服務(wù)臺(tái)空閑時(shí)，不按即當(dāng)服務(wù)臺(tái)空閑時(shí)，不按照排隊(duì)序列而隨意指定某個(gè)顧客去接受服照排隊(duì)序列而隨意指定某個(gè)顧客去接受服務(wù)，如電話交換臺(tái)接通呼叫電話就是一例。務(wù)，如電話交換臺(tái)接通呼叫電話就是一例。 優(yōu)先權(quán)服務(wù)優(yōu)先權(quán)服務(wù)。如老人、兒童先進(jìn)車站；如老人、兒童先進(jìn)車站；危重病員先就診；遇到重要數(shù)據(jù)需要處理危重病員先就診；遇到重要數(shù)據(jù)需要處理計(jì)算機(jī)立即中

12、斷其他數(shù)據(jù)的處理等，均屬計(jì)算機(jī)立即中斷其他數(shù)據(jù)的處理等，均屬于此種服務(wù)規(guī)則。于此種服務(wù)規(guī)則。2) 服務(wù)規(guī)則服務(wù)規(guī)則(等待制等待制-續(xù)續(xù))18 混合制混合制等待制與損失制相結(jié)合的等待制與損失制相結(jié)合的一種服務(wù)規(guī)則，一般是指允許排隊(duì)，但一種服務(wù)規(guī)則，一般是指允許排隊(duì)，但又不允許隊(duì)列無限長下去。具體說來，又不允許隊(duì)列無限長下去。具體說來，大致有三種：大致有三種： 隊(duì)長有限隊(duì)長有限。當(dāng)排隊(duì)系統(tǒng)中的顧客人數(shù)當(dāng)排隊(duì)系統(tǒng)中的顧客人數(shù)K超過規(guī)定數(shù)量時(shí)，后來的顧客就自動(dòng)超過規(guī)定數(shù)量時(shí)，后來的顧客就自動(dòng)離去，另求服務(wù)，即系統(tǒng)的容量是有限離去，另求服務(wù)，即系統(tǒng)的容量是有限的。的。2) 服務(wù)規(guī)則服務(wù)規(guī)則19 等待時(shí)間

13、有限等待時(shí)間有限。顧客在系統(tǒng)中的等待顧客在系統(tǒng)中的等待時(shí)間不超過某一給定的長度時(shí)間不超過某一給定的長度T，當(dāng)?shù)却龝r(shí)，當(dāng)?shù)却龝r(shí)間超過間超過T 時(shí)，顧客將自動(dòng)離去，并不再回時(shí)，顧客將自動(dòng)離去，并不再回來。如易損壞的電子元器件的庫存問題，來。如易損壞的電子元器件的庫存問題，超過一定存儲(chǔ)時(shí)間的元器件被自動(dòng)認(rèn)為失超過一定存儲(chǔ)時(shí)間的元器件被自動(dòng)認(rèn)為失效。又如顧客到飯館就餐，等了一定時(shí)間效。又如顧客到飯館就餐，等了一定時(shí)間后不愿再等而自動(dòng)離去另找飯店用餐。后不愿再等而自動(dòng)離去另找飯店用餐。2) 服務(wù)規(guī)則服務(wù)規(guī)則（混合制（混合制-續(xù)）續(xù)） 逗留時(shí)間有限逗留時(shí)間有限。例如用高射炮射擊敵機(jī)，例如用高射炮射擊敵機(jī)，

14、當(dāng)敵機(jī)飛越高射炮射擊有效區(qū)域的時(shí)間為當(dāng)敵機(jī)飛越高射炮射擊有效區(qū)域的時(shí)間為 t 時(shí)，若在這個(gè)時(shí)間內(nèi)未被擊落，就不可能再時(shí)，若在這個(gè)時(shí)間內(nèi)未被擊落，就不可能再被擊落了。被擊落了。 注意注意：損失制和等待制可看成是混合損失制和等待制可看成是混合制的特殊情形，如記制的特殊情形，如記 s 為系統(tǒng)中服務(wù)臺(tái)的個(gè)為系統(tǒng)中服務(wù)臺(tái)的個(gè)數(shù)，則當(dāng)數(shù)，則當(dāng) N = s 時(shí)，混合制即成為損失制；時(shí)，混合制即成為損失制；當(dāng)當(dāng)N = 時(shí)，混合制即成為等待制。時(shí)，混合制即成為等待制。2) 服務(wù)規(guī)則服務(wù)規(guī)則（混合制（混合制-續(xù)）續(xù)）服務(wù)臺(tái)可從以下三方面來描述：服務(wù)臺(tái)可從以下三方面來描述：1.1. 服務(wù)臺(tái)數(shù)量及構(gòu)成形式；服務(wù)臺(tái)數(shù)量

15、及構(gòu)成形式；2.2. 服務(wù)方式；服務(wù)方式；3.3. 服務(wù)時(shí)間分布服務(wù)時(shí)間分布3) 服務(wù)臺(tái)情況服務(wù)臺(tái)情況 服務(wù)臺(tái)數(shù)量及構(gòu)成形式（圖服務(wù)臺(tái)數(shù)量及構(gòu)成形式（圖8-28-6）單隊(duì)單隊(duì)單服務(wù)臺(tái)式；單服務(wù)臺(tái)式；單隊(duì)單隊(duì)多服務(wù)臺(tái)并聯(lián)式；多服務(wù)臺(tái)并聯(lián)式；多隊(duì)多隊(duì)多服務(wù)臺(tái)并聯(lián)式；多服務(wù)臺(tái)并聯(lián)式；單隊(duì)單隊(duì)多服務(wù)臺(tái)串聯(lián)式；多服務(wù)臺(tái)串聯(lián)式；單隊(duì)單隊(duì)多服務(wù)臺(tái)并串聯(lián)混合式及多隊(duì)多服務(wù)臺(tái)并串聯(lián)混合式及多隊(duì)多服多服務(wù)臺(tái)并串聯(lián)混合式等等。務(wù)臺(tái)并串聯(lián)混合式等等。圖圖8-2 8-2 單服務(wù)臺(tái)排隊(duì)系統(tǒng)單服務(wù)臺(tái)排隊(duì)系統(tǒng)23圖圖8-3 8-3 單隊(duì)列單隊(duì)列-S-S個(gè)服務(wù)臺(tái)并聯(lián)的排隊(duì)系統(tǒng)個(gè)服務(wù)臺(tái)并聯(lián)的排隊(duì)系統(tǒng)圖圖8-4 S8-4 S個(gè)隊(duì)列

16、個(gè)隊(duì)列-S-S個(gè)服務(wù)臺(tái)的并聯(lián)排隊(duì)系統(tǒng)個(gè)服務(wù)臺(tái)的并聯(lián)排隊(duì)系統(tǒng)24圖圖8-5 8-5 單隊(duì)單隊(duì)- -多個(gè)服務(wù)臺(tái)的串聯(lián)排隊(duì)系統(tǒng)多個(gè)服務(wù)臺(tái)的串聯(lián)排隊(duì)系統(tǒng)圖圖8-6 8-6 多隊(duì)多隊(duì)- -多服務(wù)臺(tái)混聯(lián)、網(wǎng)絡(luò)系統(tǒng)多服務(wù)臺(tái)混聯(lián)、網(wǎng)絡(luò)系統(tǒng)25 服務(wù)方式服務(wù)方式。這是指在某一時(shí)刻接受這是指在某一時(shí)刻接受服務(wù)的顧客數(shù)，它有單個(gè)服務(wù)和成批服務(wù)服務(wù)的顧客數(shù)，它有單個(gè)服務(wù)和成批服務(wù)兩種。兩種。 服務(wù)時(shí)間的分布服務(wù)時(shí)間的分布。在多數(shù)情況下，在多數(shù)情況下，對(duì)每一個(gè)顧客的服務(wù)時(shí)間是一隨機(jī)變量，對(duì)每一個(gè)顧客的服務(wù)時(shí)間是一隨機(jī)變量，其概率分布有定長分布、負(fù)指數(shù)分布、其概率分布有定長分布、負(fù)指數(shù)分布、K級(jí)愛爾朗分布、一般分布級(jí)愛爾

17、朗分布、一般分布( (所有顧客的服務(wù)所有顧客的服務(wù)時(shí)間都是獨(dú)立同分布的時(shí)間都是獨(dú)立同分布的) )等等。等等。3) 服務(wù)臺(tái)情況服務(wù)臺(tái)情況26 為了區(qū)別各種排隊(duì)系統(tǒng)，根據(jù)輸為了區(qū)別各種排隊(duì)系統(tǒng)，根據(jù)輸入過程、排隊(duì)規(guī)則和服務(wù)機(jī)制的變化入過程、排隊(duì)規(guī)則和服務(wù)機(jī)制的變化對(duì)排隊(duì)模型進(jìn)行描述或分類，肯道爾對(duì)排隊(duì)模型進(jìn)行描述或分類，肯道爾（DGKendall）提出了一種目前提出了一種目前在排隊(duì)論中被廣泛采用的在排隊(duì)論中被廣泛采用的“Kendall記記號(hào)號(hào)”，完整的表達(dá)方式通常用到，完整的表達(dá)方式通常用到6個(gè)個(gè)符號(hào)并取如下固定格式：符號(hào)并取如下固定格式：A/B/C/D/E/F 各符號(hào)的意義為：各符號(hào)的意義為：1

18、.3 排隊(duì)系統(tǒng)的描述符號(hào)與分類排隊(duì)系統(tǒng)的描述符號(hào)與分類A表示顧客相繼到達(dá)間隔時(shí)間分布，表示顧客相繼到達(dá)間隔時(shí)間分布，常用下列符號(hào)：常用下列符號(hào)： M 表示到達(dá)過程為泊松過程或負(fù)表示到達(dá)過程為泊松過程或負(fù)指數(shù)分布；指數(shù)分布； D 表示定長輸入；表示定長輸入； Ek 表示表示k階愛爾朗分布；階愛爾朗分布； G 表示一般相互獨(dú)立的隨機(jī)分布。表示一般相互獨(dú)立的隨機(jī)分布。Kendall記號(hào)含義記號(hào)含義Kendall記號(hào)含義記號(hào)含義B 表示服務(wù)時(shí)間分布表示服務(wù)時(shí)間分布。所用符號(hào)與表所用符號(hào)與表示顧客到達(dá)間隔時(shí)間分布相同。示顧客到達(dá)間隔時(shí)間分布相同。 M 表示服務(wù)過程為泊松過程或負(fù)表示服務(wù)過程為泊松過程或負(fù)

19、指數(shù)分布；指數(shù)分布； D 表示定長分布；表示定長分布； Ek 表示表示k階愛爾朗分布；階愛爾朗分布； G 表示一般相互獨(dú)立的隨機(jī)分布。表示一般相互獨(dú)立的隨機(jī)分布。 C表示服務(wù)臺(tái)表示服務(wù)臺(tái)(員員)個(gè)數(shù)個(gè)數(shù)： “1”則表示單個(gè)服務(wù)臺(tái)，則表示單個(gè)服務(wù)臺(tái)，“s”(s1)表示多表示多個(gè)服務(wù)臺(tái)。個(gè)服務(wù)臺(tái)。D表示系統(tǒng)中顧客容量限額表示系統(tǒng)中顧客容量限額： 如系統(tǒng)有如系統(tǒng)有N個(gè)位子，則個(gè)位子，則 s N00為一常數(shù)，表示單位時(shí)為一常數(shù)，表示單位時(shí)間內(nèi)到達(dá)顧客的平均數(shù)，又稱為顧客的平間內(nèi)到達(dá)顧客的平均數(shù)，又稱為顧客的平均到達(dá)率。均到達(dá)率。 負(fù)指數(shù)分布。負(fù)指數(shù)分布。對(duì)于泊松流，可以證明其對(duì)于泊松流，可以證明其相繼

20、顧客到達(dá)時(shí)間間隔相繼顧客到達(dá)時(shí)間間隔 i，i = 1,2,是相互是相互獨(dú)立同分布的，其分布函數(shù)為負(fù)指數(shù)分布：獨(dú)立同分布的，其分布函數(shù)為負(fù)指數(shù)分布：0, 00,1)(ttetFti ), 2 , 1(i1) 重要的概率分布重要的概率分布 poisson流流 k階階愛爾朗分布愛爾朗分布. . 這是指相繼顧客到達(dá)這是指相繼顧客到達(dá)時(shí)間間隔時(shí)間間隔 相互獨(dú)立，具有相同的分布，其分相互獨(dú)立，具有相同的分布，其分布密度為布密度為其中其中k為非負(fù)整數(shù)。為非負(fù)整數(shù)。 可以證明，在參數(shù)為可以證明，在參數(shù)為 的泊松輸人中，對(duì)任的泊松輸人中，對(duì)任意的意的j與與k,設(shè)第設(shè)第j與第與第j+k個(gè)顧客之間的到達(dá)間隔個(gè)顧客之

21、間的到達(dá)間隔為為則隨機(jī)變量則隨機(jī)變量Tk的分布必遵從參數(shù)為的分布必遵從參數(shù)為 的愛爾朗的愛爾朗分布。分布。1()( )0(1)!Kttf tetK )(21kkkTT 例：某排隊(duì)系統(tǒng)有并聯(lián)的例：某排隊(duì)系統(tǒng)有并聯(lián)的k個(gè)服務(wù)臺(tái)，顧個(gè)服務(wù)臺(tái)，顧客流為泊松流，規(guī)定第客流為泊松流，規(guī)定第i, k+i, 2k+i 個(gè)顧個(gè)顧客排入第客排入第i號(hào)臺(tái)號(hào)臺(tái) ( i = 1,2,k )，則第，則第k臺(tái)所臺(tái)所獲得的顧客流，即為獲得的顧客流，即為k階愛爾朗輸入流，階愛爾朗輸入流，其他各臺(tái)，從它的第一個(gè)顧客到達(dá)以后開其他各臺(tái)，從它的第一個(gè)顧客到達(dá)以后開始所獲得的流也為愛爾朗輸入流。始所獲得的流也為愛爾朗輸入流。 此外，愛

22、爾朗分布中，當(dāng)此外，愛爾朗分布中，當(dāng)k1時(shí)將化時(shí)將化為負(fù)指數(shù)分布。為負(fù)指數(shù)分布。1) 重要的概率分布重要的概率分布 愛爾朗分布愛爾朗分布592) 生滅過程與狀態(tài)轉(zhuǎn)移速度圖生滅過程與狀態(tài)轉(zhuǎn)移速度圖 生滅過程。生滅過程。 假定一個(gè)系統(tǒng)具有狀態(tài)集假定一個(gè)系統(tǒng)具有狀態(tài)集 S = 0, 1, 2, , N , 并存在常數(shù)并存在常數(shù) n0 和和 n0，n = 1,2,N 當(dāng)當(dāng) t (t 0) 時(shí)刻，記狀態(tài)隨機(jī)變量時(shí)刻，記狀態(tài)隨機(jī)變量為為K(t)，系統(tǒng)內(nèi)有，系統(tǒng)內(nèi)有n個(gè)顧客的概率為個(gè)顧客的概率為Pn(t)，經(jīng)過，經(jīng)過t 時(shí)間，如果滿足時(shí)間，如果滿足60 則稱這個(gè)隨機(jī)過程則稱這個(gè)隨機(jī)過程 K(t) ：t 0

23、為為有限狀態(tài)有限狀態(tài)S上的上的生滅過程生滅過程。當(dāng)系統(tǒng)具有。當(dāng)系統(tǒng)具有可列無限狀態(tài)集可列無限狀態(tài)集S = 0, 1, 2, 時(shí)時(shí),則則稱為無限狀態(tài)的生滅過程。稱為無限狀態(tài)的生滅過程。2) 生滅過程與狀態(tài)轉(zhuǎn)移速度圖生滅過程與狀態(tài)轉(zhuǎn)移速度圖1, 1,),()()()()()(11nnnkSktottPtotttPtotttPknnnn 狀態(tài)轉(zhuǎn)移速度圖。狀態(tài)轉(zhuǎn)移速度圖。我們把充分小的我們把充分小的t 固定，直接用參數(shù)固定，直接用參數(shù) n 和和 n 表示表示 n t 和和 n t，生滅過程可利用狀態(tài)轉(zhuǎn)移速度圖來描，生滅過程可利用狀態(tài)轉(zhuǎn)移速度圖來描述述“生生”、“滅滅”導(dǎo)致狀態(tài)轉(zhuǎn)移的過程。注導(dǎo)致狀態(tài)轉(zhuǎn)移

24、的過程。注意，在實(shí)際上，意，在實(shí)際上， n和和 n的取值不需要考慮的取值不需要考慮t的大小，只要保證二者的基礎(chǔ)時(shí)段一致即可的大小，只要保證二者的基礎(chǔ)時(shí)段一致即可（計(jì)算中考慮的是二者的比率）。（計(jì)算中考慮的是二者的比率）。2) 生滅過程與狀態(tài)轉(zhuǎn)移速度圖生滅過程與狀態(tài)轉(zhuǎn)移速度圖無限狀態(tài)生滅過程的狀態(tài)轉(zhuǎn)移速度無限狀態(tài)生滅過程的狀態(tài)轉(zhuǎn)移速度圖如圖圖如圖：狀態(tài)轉(zhuǎn)移速度圖狀態(tài)轉(zhuǎn)移速度圖0n123021n-1n1n32n+1狀態(tài)轉(zhuǎn)移速度圖狀態(tài)轉(zhuǎn)移速度圖 根據(jù)泊松流的普通性，當(dāng)根據(jù)泊松流的普通性，當(dāng)t充分小充分小時(shí)，在時(shí)，在 (t,t+t) 時(shí)間段內(nèi)有一個(gè)顧客到時(shí)間段內(nèi)有一個(gè)顧客到達(dá)的概率為達(dá)的概率為 nt

25、+ o (t ) ，而無顧客，而無顧客到達(dá)的概率為到達(dá)的概率為1- nt + o(t )，故泊松，故泊松輸入輸入指數(shù)服務(wù)排隊(duì)系統(tǒng)的狀態(tài)轉(zhuǎn)指數(shù)服務(wù)排隊(duì)系統(tǒng)的狀態(tài)轉(zhuǎn)移過程是生滅過程。因此，可以通過移過程是生滅過程。因此，可以通過狀態(tài)轉(zhuǎn)移速度圖研究狀態(tài)概率之間的狀態(tài)轉(zhuǎn)移速度圖研究狀態(tài)概率之間的關(guān)系。關(guān)系。2.2 泊松輸入泊松輸入-指數(shù)服務(wù)排隊(duì)系統(tǒng)的求解指數(shù)服務(wù)排隊(duì)系統(tǒng)的求解 1) 狀態(tài)概率之間的關(guān)系狀態(tài)概率之間的關(guān)系: 可以通過兩種方式推導(dǎo)這種關(guān)系：可以通過兩種方式推導(dǎo)這種關(guān)系： 直接通過概率發(fā)生情況討論系統(tǒng)直接通過概率發(fā)生情況討論系統(tǒng)狀態(tài)概率之間的關(guān)系。狀態(tài)概率之間的關(guān)系。 利用狀態(tài)轉(zhuǎn)移速度圖導(dǎo)出

26、各狀態(tài)利用狀態(tài)轉(zhuǎn)移速度圖導(dǎo)出各狀態(tài)概率之間的關(guān)系。概率之間的關(guān)系。 直接通過概率發(fā)生情況討論系統(tǒng)狀態(tài)直接通過概率發(fā)生情況討論系統(tǒng)狀態(tài)概率之間的關(guān)系：概率之間的關(guān)系： n：系統(tǒng)狀態(tài)為系統(tǒng)狀態(tài)為n時(shí)，顧客進(jìn)入系統(tǒng)的平均速度時(shí)，顧客進(jìn)入系統(tǒng)的平均速度 n：系統(tǒng)狀態(tài)系統(tǒng)狀態(tài)為為n時(shí)，顧客離開系統(tǒng)的平均速度時(shí)，顧客離開系統(tǒng)的平均速度 Pn(t)：t 時(shí)刻，系統(tǒng)內(nèi)有時(shí)刻，系統(tǒng)內(nèi)有n個(gè)顧客的概率。個(gè)顧客的概率。 那么，在那么，在 (t, t+ t) 有一個(gè)顧客到達(dá)概率為有一個(gè)顧客到達(dá)概率為 n t，無顧客到達(dá)的概率為，無顧客到達(dá)的概率為 1- n t（根據(jù)普（根據(jù)普通性）。通性）。 各種方式發(fā)生概率表各種方

27、式發(fā)生概率表 Pn(t+ t) = Pn(t)(1- n t)(1- n t) +Pn-1(t) n-1 t(1- n-1 t) +Pn+1(t)(1- n+1 t) n+1 t +Pn(t) n t n tdPn(t)/dt = lim t-0(Pn(t+ t)-Pn(t)/ t) =Pn-1(t) n-1-Pn(t)( n+ n)+Pn+1(t) n+1 (其中其中 t2項(xiàng)都變?yōu)榱沩?xiàng)都變?yōu)榱?方式方式1, 2, 3, 4互不相容且完備互不相容且完備,于是于是68 當(dāng)當(dāng)n=0時(shí)，只有方式時(shí)，只有方式1和和3，4發(fā)生，且方式發(fā)生，且方式1中無離去的概率為中無離去的概率為1，則，則 dP0(t)

28、/dt = -P0(t) 0+P1(t) 1 我們假設(shè)系統(tǒng)是穩(wěn)態(tài)的，即我們假設(shè)系統(tǒng)是穩(wěn)態(tài)的，即與時(shí)刻無關(guān)，于是可得：與時(shí)刻無關(guān)，于是可得： d Pn(t) / d t = 0；公式推導(dǎo)如下：公式推導(dǎo)如下：2323332221112122211100010111000)(0)(0pppppppppppppp 根據(jù)此根據(jù)此各事件兩兩不相容，且完各事件兩兩不相容，且完備，有備，有 pn=1，于是于是 可求出可求出 pn, n=0, 1, 2, 01101111110)(ppppppinijnjnnnnnnnnnnn 利用狀態(tài)轉(zhuǎn)移速度圖得到概率公式利用狀態(tài)轉(zhuǎn)移速度圖得到概率公式由此圖易得：轉(zhuǎn)入率由此圖

29、易得：轉(zhuǎn)入率=轉(zhuǎn)出率轉(zhuǎn)出率n=0 ， 0P0= 1P1n0 ， n-1Pn-1+ n+1Pn+1=( n+ n)Pn0n123021n-1n1n32n+172公式推導(dǎo)如下：公式推導(dǎo)如下：2323332221112122211100010111000)(0)(0pppppppppppppp 73 根據(jù)此根據(jù)此各事件兩兩不相容，且完各事件兩兩不相容，且完備，有備，有 pn=1，于是于是 可求出可求出 pn, n=0, 1, 2, 01101111110)(ppppppinijnjnnnnnnnnnnn 對(duì)排隊(duì)系統(tǒng)運(yùn)行情況的分析，對(duì)排隊(duì)系統(tǒng)運(yùn)行情況的分析，通常是在給定輸入與服務(wù)條件下，通常是在給定輸

30、入與服務(wù)條件下，通過求解系統(tǒng)狀態(tài)為通過求解系統(tǒng)狀態(tài)為n的概率的概率Pn(t)，再計(jì)算其主要的運(yùn)行指標(biāo)，再計(jì)算其主要的運(yùn)行指標(biāo):75 根據(jù)已知條件繪制狀態(tài)轉(zhuǎn)移速根據(jù)已知條件繪制狀態(tài)轉(zhuǎn)移速度圖。度圖。 依據(jù)狀態(tài)轉(zhuǎn)移速度圖寫出各穩(wěn)依據(jù)狀態(tài)轉(zhuǎn)移速度圖寫出各穩(wěn)態(tài)概率之間的關(guān)系。態(tài)概率之間的關(guān)系。 求出求出 P0 及及 Pn 。2)泊松輸入泊松輸入負(fù)指數(shù)分布服務(wù)的排隊(duì)負(fù)指數(shù)分布服務(wù)的排隊(duì)系統(tǒng)的一般決策過程：系統(tǒng)的一般決策過程：762)泊松輸入泊松輸入負(fù)指數(shù)分布服務(wù)的負(fù)指數(shù)分布服務(wù)的排隊(duì)系統(tǒng)的一般決策過程（續(xù)）排隊(duì)系統(tǒng)的一般決策過程（續(xù)） 計(jì)算各項(xiàng)數(shù)量運(yùn)行指標(biāo)計(jì)算各項(xiàng)數(shù)量運(yùn)行指標(biāo)。 用系統(tǒng)運(yùn)行指標(biāo)構(gòu)造目標(biāo)函

31、數(shù)，用系統(tǒng)運(yùn)行指標(biāo)構(gòu)造目標(biāo)函數(shù)，對(duì)系統(tǒng)進(jìn)行優(yōu)化。對(duì)系統(tǒng)進(jìn)行優(yōu)化。77泊松輸入泊松輸入-指數(shù)服務(wù)指數(shù)服務(wù)穩(wěn)態(tài)穩(wěn)態(tài)排隊(duì)系統(tǒng)排隊(duì)系統(tǒng)的運(yùn)行指標(biāo)的運(yùn)行指標(biāo) 系統(tǒng)中顧客數(shù)系統(tǒng)中顧客數(shù)( (隊(duì)長隊(duì)長) )的期望值的期望值 排隊(duì)等待的顧客數(shù)排隊(duì)等待的顧客數(shù)( (排隊(duì)長排隊(duì)長) )的期望值的期望值0nnnpL1)(snnqpsnL78 求出平均有效到達(dá)率求出平均有效到達(dá)率 e，再再利用利用Little公式計(jì)算：公式計(jì)算： 顧客在系統(tǒng)中全部時(shí)間顧客在系統(tǒng)中全部時(shí)間(逗留逗留時(shí)間時(shí)間)的期望值的期望值W； 顧客在系統(tǒng)中排隊(duì)等待時(shí)間顧客在系統(tǒng)中排隊(duì)等待時(shí)間的期望值的期望值Wq。79例例某汽車加油站有兩臺(tái)加油泵為汽車

32、加某汽車加油站有兩臺(tái)加油泵為汽車加油，加油站內(nèi)最多能容納油，加油站內(nèi)最多能容納6輛汽車。已輛汽車。已知顧客到達(dá)的時(shí)間間隔服從負(fù)指數(shù)分知顧客到達(dá)的時(shí)間間隔服從負(fù)指數(shù)分布，平均每小時(shí)到達(dá)布，平均每小時(shí)到達(dá)18輛汽車。若輛汽車。若加加油站中已油站中已有有K輛車，當(dāng)輛車，當(dāng)K 2時(shí)，有時(shí)，有K/6的顧客將自動(dòng)離去的顧客將自動(dòng)離去。加油時(shí)間服從負(fù)。加油時(shí)間服從負(fù)指數(shù)分布，平均每輛車需要指數(shù)分布，平均每輛車需要5分鐘。試分鐘。試求：求：非標(biāo)準(zhǔn)的非標(biāo)準(zhǔn)的M/M/2/NM/M/2/N模型模型801）系統(tǒng)空閑的概率為多少？）系統(tǒng)空閑的概率為多少？ P02）求系統(tǒng)滿的概率是多少？）求系統(tǒng)滿的概率是多少？ P63）

33、求系統(tǒng)服務(wù)臺(tái)不空的概率）求系統(tǒng)服務(wù)臺(tái)不空的概率 P2+P3+P4+P5+P6=1- P0-P1 4）若服務(wù)一個(gè)顧客）若服務(wù)一個(gè)顧客,加油站可以獲加油站可以獲得利潤得利潤10元元,問平均每小時(shí)可獲得利問平均每小時(shí)可獲得利潤為多少元？潤為多少元？ 10 e5）求每小時(shí)損失掉的顧客數(shù)？）求每小時(shí)損失掉的顧客數(shù)？ 損損= - e 816）加油站平均有多少輛車在等待）加油站平均有多少輛車在等待加油？加油？ Lq 平均有多少個(gè)車位被占？平均有多少個(gè)車位被占？ L7）進(jìn)入加油站的顧客需要等多長）進(jìn)入加油站的顧客需要等多長的時(shí)間才能開始加油？的時(shí)間才能開始加油？ Wq 進(jìn)入加進(jìn)入加油站的顧客需要多長時(shí)間才能離

34、去？油站的顧客需要多長時(shí)間才能離去？ W82穩(wěn)態(tài)概率關(guān)系：穩(wěn)態(tài)概率關(guān)系：P1= / P0=1.5P0 =(3/2)P0P2= /(2 )P1=0.75*1.5P0 =(9/8)P0解：狀態(tài)轉(zhuǎn)移速度圖解：狀態(tài)轉(zhuǎn)移速度圖 以小時(shí)為單位以小時(shí)為單位 =18 =60/5=1222 2205124632(1-2/6)(1-3/6) (1-4/6) (1-5/6) P3=(4/6)/(2)P2=(1/2)(9/8)P0 = (9/16)P0 P4=(3/6)/(2)P3=(3/8)(9/16)P0 = (27/128)P0P5=(2/6)/(2)P4=(1/4)(27/128)P0 = (27/512)P

35、0P6=(1/6)/(2)P5=(1/8)(27/512)P0 = (27/4096)P084由由 P0+P1+P2+P3+P4+P5+P6=1解得：解得：P0=0.22433P1= 0.33649 ，P2= 0.25237 ，P3= 0.12618 ，P4= 0.04732 ，P5= 0.01183 ，P6=0.00148。851) P0=0.224332) P6=0.001483) P忙忙=1-P0-P1=0.439184) e= 0P0+ P1+2 (P2+P3+P4+P5+P6) = 14.578（輛（輛/h） 10 e= 145.78(元元/小時(shí)）小時(shí)）運(yùn)行指標(biāo)：運(yùn)行指標(biāo)：865)

36、損損= - e =18-14.5782 =3.4218（輛（輛/h）6)Lq=(3-2)P3+(4-2)P4+(5-2)P5+(6-2)P6 = 0.26223 L=Lq+ e/ =0.26223+1.21485 =1.47708運(yùn)行指標(biāo)（續(xù)）運(yùn)行指標(biāo)（續(xù)）87運(yùn)行指標(biāo)（續(xù)）運(yùn)行指標(biāo)（續(xù)）7)7)W Wq q= =L Lq q/ / e e = 0.018h = 1.08= 0.018h = 1.08分鐘分鐘 W W= =W Wq q+1/+1/ = 0.101h = 6.08= 0.101h = 6.08分鐘分鐘88 車站候車室在某段時(shí)間旅客到達(dá)車站候車室在某段時(shí)間旅客到達(dá)服從泊松分布，平均

37、速度為服從泊松分布，平均速度為50人人/h，每位旅客在候車室內(nèi)停留的時(shí)間服從每位旅客在候車室內(nèi)停留的時(shí)間服從負(fù)指數(shù)分布，平均停留時(shí)間為負(fù)指數(shù)分布，平均停留時(shí)間為0.5h，問候車室內(nèi)平均人數(shù)為多少？問候車室內(nèi)平均人數(shù)為多少？解：把旅客停留在候車室看做服務(wù)，解：把旅客停留在候車室看做服務(wù)，于是系統(tǒng)為于是系統(tǒng)為M/M/ = 50 =1/0.5 = 2例例89穩(wěn)態(tài)概率關(guān)系：穩(wěn)態(tài)概率關(guān)系：Pn= /(n )Pn-1=1/n!( / )nP0 記記 = / = 50/2 = 25 狀態(tài)轉(zhuǎn)移速度圖狀態(tài)轉(zhuǎn)移速度圖: :0n12n-1n2(n+1)n+13 (n-1)(n+2)90010100025!1)!1(

38、1!1,1nnnnnnnnnnnenenpLenpp 代入代入因此，候車室平均人數(shù)為因此，候車室平均人數(shù)為25人。人。 在排隊(duì)系統(tǒng)中，由于顧客到達(dá)在排隊(duì)系統(tǒng)中，由于顧客到達(dá)分布和服務(wù)時(shí)間分布不同、服務(wù)臺(tái)分布和服務(wù)時(shí)間分布不同、服務(wù)臺(tái)數(shù)不同、隊(duì)長有限無限、顧客源有數(shù)不同、隊(duì)長有限無限、顧客源有限無限等的不同組合，就會(huì)有不勝限無限等的不同組合，就會(huì)有不勝枚舉的不同排隊(duì)模型。枚舉的不同排隊(duì)模型。下面分析下面分析泊泊松輸入松輸入-指數(shù)服務(wù)指數(shù)服務(wù)排隊(duì)系統(tǒng)模型。排隊(duì)系統(tǒng)模型。3 3 泊松輸入泊松輸入-指數(shù)服務(wù)排隊(duì)模型指數(shù)服務(wù)排隊(duì)模型 921) M/M/1/: 參數(shù)參數(shù) ， 穩(wěn)態(tài)概率方程：穩(wěn)態(tài)概率方程：

39、Pn=( / )Pn-1=( / )nP0 令令= / 當(dāng)當(dāng) 1時(shí)時(shí), n不收斂，故應(yīng)不收斂，故應(yīng)1, n=0即即 k ) = k+1顧客逗留時(shí)間超過顧客逗留時(shí)間超過t的概率的概率 P( U t ) = e-()t 96 設(shè)忙期、閑期和忙的概率、閑的概設(shè)忙期、閑期和忙的概率、閑的概率分別為率分別為 T忙忙、T閑閑、 p忙忙、 p閑閑 ，那么可，那么可以計(jì)算忙期和閑期。注意，以計(jì)算忙期和閑期。注意， M/M/1/ / 系統(tǒng)系統(tǒng) 其他指標(biāo)其他指標(biāo) 11,1,0000ppppTTpppp忙忙閑閑忙忙閑閑忙忙閑閑又又 1閑閑T 11閑閑忙忙TT97例例82 P216 某醫(yī)院急診室同時(shí)只能診治1個(gè)病人，

40、診治時(shí)間服從指數(shù)分布，每個(gè)病人平均需要15分鐘。病人按泊松分布到達(dá)，平均每小時(shí)到達(dá)3人。983.1 單服務(wù)臺(tái)無限源系統(tǒng)單服務(wù)臺(tái)無限源系統(tǒng)2) M/M/1/N/ 參數(shù)參數(shù) , 系統(tǒng)狀態(tài)轉(zhuǎn)移速度：系統(tǒng)狀態(tài)轉(zhuǎn)移速度：穩(wěn)態(tài)概率方程：穩(wěn)態(tài)概率方程：Pn=( / )Pn-1= ( / )nP0 , 1n N0N-112N-2N99 由由M/M/1/N/ 系統(tǒng)系統(tǒng)10 Nnnp Nnnp001 10011111NNnnNp100 e= npn= (1-pN)+0pN= (1-pN)(只有只有pN不再進(jìn)人，故不再進(jìn)人，故 N=0，其余均為，其余均為 ) e = npn=0p0+ (1-p0)（同理）（同理）W

41、 =L/ e , Wq=W -(1/ ), Lq=Wq e M/M/1/N/ 系統(tǒng)系統(tǒng)1,21,1)1(1110 NNnpLNNNnn1013) 損失制損失制M/M/1/1: 顧客到達(dá)若服顧客到達(dá)若服務(wù)臺(tái)被占用立即離開。直接可得：務(wù)臺(tái)被占用立即離開。直接可得：P1 = P0 ; P0+P1=1 P0 = 1 / (1+) = /( + ) P閑閑=P0= /( + )P損損=P忙忙=P1= /( + )3.1 單服務(wù)臺(tái)無限源系統(tǒng)單服務(wù)臺(tái)無限源系統(tǒng)102例例83 P2181) M/M/s/ / 系統(tǒng)系統(tǒng) 參數(shù)參數(shù) ， 穩(wěn)態(tài)概率應(yīng)滿足的關(guān)系：穩(wěn)態(tài)概率應(yīng)滿足的關(guān)系：當(dāng)當(dāng)ns時(shí)，時(shí)， pn= /(n

42、) pn-1當(dāng)當(dāng)ns時(shí)，時(shí)， Pn = /(s ) pn-1 令令= /(s ) 系統(tǒng)負(fù)荷強(qiáng)度系數(shù)系統(tǒng)負(fù)荷強(qiáng)度系數(shù)3.2 多服務(wù)臺(tái)無限源系統(tǒng)多服務(wù)臺(tái)無限源系統(tǒng)012ns2cc-1ssc+13(s-1)ss104 此系統(tǒng)中，當(dāng)此系統(tǒng)中，當(dāng)= /(s )1時(shí)，不時(shí)，不收斂，設(shè)收斂，設(shè)1, M/M/s/ 系統(tǒng)系統(tǒng)1010,1!,!nnnsnssppnsnnpsppnss 105 根據(jù)根據(jù) ，可得到，可得到 Lq = sss+1p0 / s! (1-)2利用利用 Little 公式得到公式得到 Wq = Lq / , W = Wq+ 1/ , L= W = Lq+ / M/M/s/ 系統(tǒng)系統(tǒng)10nnp

43、 essnsnnssnsp,1!1100106 某火車站售票處有三個(gè)窗口，同時(shí)售各某火車站售票處有三個(gè)窗口，同時(shí)售各車次的車票。顧客到達(dá)服從泊松分布，平車次的車票。顧客到達(dá)服從泊松分布，平均每分鐘到達(dá)均每分鐘到達(dá) =0.9(人人)，服務(wù)時(shí)間服從負(fù)，服務(wù)時(shí)間服從負(fù)指數(shù)分布，平均服務(wù)率每小時(shí)指數(shù)分布，平均服務(wù)率每小時(shí) =24(人人)，分兩種情況討論：分兩種情況討論：1. 顧客排成一隊(duì)，依次購票；顧客排成一隊(duì)，依次購票；2.顧客在每個(gè)窗口排一隊(duì)，不準(zhǔn)串隊(duì)。顧客在每個(gè)窗口排一隊(duì)，不準(zhǔn)串隊(duì)。 求求: 1）售票處空閑的概率。）售票處空閑的概率。 2）平均等待時(shí)間和逗留時(shí)間。）平均等待時(shí)間和逗留時(shí)間。 3）

44、隊(duì)長和隊(duì)列長。）隊(duì)長和隊(duì)列長。例例單位一致單位一致： =0.4(人人/分鐘分鐘)= /(3 )=0.75穩(wěn)態(tài)概率：穩(wěn)態(tài)概率：031232343解：情況解：情況1. M/M/3/)3(5 . 4! 33,53125. 22,25. 2003012001npppppppppnnn 108解：情況解：情況1. M/M/3/ 續(xù)續(xù)由由得得15 . 453125. 225. 2,130000nnnnpppp 1893. 0,1683. 0,0748. 015 . 453125. 225. 21 21130ppp ,)3(5 . 4)3(44044nnnnqnppnL 109解：情況解：情況1. M/M/

45、3/ 續(xù)續(xù)44)3(nnnS 1) 3(4434nnnndndSF,704. 1)1(5 . 4,)1(12042 pLddFSq記記 先求積分，再求微分先求積分，再求微分954. 3,393. 41,893. 1WLWWLWqqq 110解：情況解：情況1. M/M/3/ 續(xù)續(xù)售票處的空閑的概率為售票處的空閑的概率為0.0748平均等待時(shí)間平均等待時(shí)間 Wq=1.893分鐘，分鐘， 平均逗留時(shí)間平均逗留時(shí)間 W=4.393分鐘分鐘隊(duì)長隊(duì)長 L =3.954(人人) Lq=1.704(人人)111參數(shù)參數(shù) =0.3 =0.4 = / = 0.75利用公式，利用公式，1個(gè)服務(wù)臺(tái)有空個(gè)服務(wù)臺(tái)有空

46、p0 = 1- = 0.25 2個(gè)、個(gè)、3個(gè)服務(wù)臺(tái)有空個(gè)服務(wù)臺(tái)有空: p02=0.0625 和和 p03=0.0156L =/(1-)=3 e= = 0.3用用Little公式：公式： Lq= L- / = 2.25, W =L / =10 , Wq=W-1/ =7.5情況情況2 M/M/1/ 3個(gè)系統(tǒng)并聯(lián)個(gè)系統(tǒng)并聯(lián)112故售票處空閑的概率為故售票處空閑的概率為 0.0156平均等待時(shí)間平均等待時(shí)間 Wq=7.5分鐘分鐘 平均逗留時(shí)間平均逗留時(shí)間 W=10分鐘分鐘隊(duì)長隊(duì)長 L=3 三個(gè)隊(duì)三個(gè)隊(duì) 共共3+3+3=9隊(duì)列長隊(duì)列長 Lq=2.25 共共6.75（人）（人） 顯然，排一隊(duì)共享顯然，排一

47、隊(duì)共享3個(gè)服務(wù)臺(tái)效率高。個(gè)服務(wù)臺(tái)效率高。解：情況解：情況2. M/M/1/ 續(xù)續(xù)1132) M/M/c/N/ 穩(wěn)態(tài)概率應(yīng)滿足的關(guān)系：穩(wěn)態(tài)概率應(yīng)滿足的關(guān)系：當(dāng)當(dāng)nc時(shí)，時(shí)，當(dāng)當(dāng)nc時(shí)，時(shí)，3.2 多服務(wù)臺(tái)無限源系統(tǒng)多服務(wù)臺(tái)無限源系統(tǒng)0N-112N-2c2cNcc-1ccc+1(c-1)cc111 nnnnnpnpp 111nnnnnpcpp 114令令= /(c )，根據(jù)，根據(jù) pn=1，可得，可得M/M/c/N/ 系統(tǒng)系統(tǒng)Nncpccpcnpncpncpcnnnn,!1,!0101 1,!)1(!1,1!11011100 sssNnsssnsPsnsnNssnnsn115運(yùn)行指標(biāo)：運(yùn)行指標(biāo)：M

48、/M/c/N/ 系統(tǒng)系統(tǒng)1,!2) 1)(1,)1)(1(1)1 ( !0021 pcccNcNpcNccLccNccq116同單服務(wù)臺(tái)情況的分析，同單服務(wù)臺(tái)情況的分析， e= (1- pN)利用利用 Little 公式，可求得公式，可求得 Wq=Lq / e W=Wq+1/ L=We=Lq+e/M/M/c/N/ 系統(tǒng)系統(tǒng)117此即此即M/M/c/N中中 N=c 的情形的情形 損損= - e= pc ，損失率，損失率= 損損/ = pc 3) M/M/c/c/損失制系統(tǒng)損失制系統(tǒng) cpncppnnnnnn,!0110,0,)1(,!100qqcecnnnWLpncp )1(,1cpLW 118

49、3.3 有限源排隊(duì)系統(tǒng)有限源排隊(duì)系統(tǒng)1) M/M/1/m/m系統(tǒng)系統(tǒng)顧客源是顧客源是m個(gè)，那么系統(tǒng)容量實(shí)質(zhì)上最多有個(gè)，那么系統(tǒng)容量實(shí)質(zhì)上最多有m個(gè)足夠。個(gè)足夠。0m-112m-2m(m-1)2m(m-2)3顧客源中剩余的顧客數(shù)顧客源中剩余的顧客數(shù)乘以每個(gè)顧客到達(dá)的概率乘以每個(gè)顧客到達(dá)的概率1191) M/M/1/m/m系統(tǒng)系統(tǒng)穩(wěn)態(tài)概率方程：穩(wěn)態(tài)概率方程：由概率性質(zhì)，得由概率性質(zhì)，得mnpnmmpnmpnnn, 2 , 1)()!(!)1(01 mnnnmmp010)!(!( )()()(0000Lmnppmpnmpmnnmnnmnmnnnne 1) M/M/1/m/m系統(tǒng)系統(tǒng)根據(jù)根據(jù) e= (

50、m-L)= e= (1-p0), 得得 L=m- / (1-p0)再利用再利用Little公式，可求得公式，可求得 W=L/ e Wq=W-1/ Lq=Wq e1212) M/M/c/m/m系統(tǒng)系統(tǒng)0m-112m-2m(m-1)2c2cmcc-1(m(c-1)c穩(wěn)態(tài)概率方程穩(wěn)態(tài)概率方程1, 2 , 1!)!(!)1(01cnpnnmmpnnmpnnn mccnpccnmmpcnmpncnnn, 1,!)!(!)1(01 122代入代入 pn=1 得得,同前，同前，M/M/c/m/m系統(tǒng)系統(tǒng)mcnncncnnccnmmnnmmp1100!)!(!)!(! )()()(0000Lmnppmpnmp

51、mnnmnnmnmnnnne 123進(jìn)一步可得進(jìn)一步可得 ：可求出可求出L和和 e，再利用，再利用Little公式，得公式，得 M/M/c/m/m系統(tǒng)系統(tǒng)msnnsnneepspn11 qeqqeWLWWLW ,1,1244其他模型選介1) M/G/1排隊(duì)系統(tǒng)排隊(duì)系統(tǒng) 設(shè)顧客平均到達(dá)率為設(shè)顧客平均到達(dá)率為 ，服務(wù)時(shí)間為隨機(jī)，服務(wù)時(shí)間為隨機(jī)變量變量V，且，且E(V) = 1/ ，D(V) = 2 那么，服務(wù)強(qiáng)度那么，服務(wù)強(qiáng)度 ，當(dāng)，當(dāng) 1時(shí)時(shí) p0 = 1 - 根據(jù)波拉切克根據(jù)波拉切克- -欣欽欣欽（Pollaczek-Khinchine）公式公式可導(dǎo)出可導(dǎo)出 Lq = ( 2+ ) / 2(1

52、- )其它量的計(jì)算同前。其它量的計(jì)算同前。1254 4 其他模型選介其他模型選介2) M/D/1排隊(duì)系統(tǒng)排隊(duì)系統(tǒng) 設(shè)顧客平均到達(dá)率為設(shè)顧客平均到達(dá)率為 ，服務(wù)時(shí)間為常數(shù)，服務(wù)時(shí)間為常數(shù)v，則，則 E( v ) = v = 1/ , D( v ) = 0那么，服務(wù)強(qiáng)度那么，服務(wù)強(qiáng)度 ，當(dāng)，當(dāng) 1時(shí)時(shí) p0 = 1 - 根據(jù)上一模型的公式可直接得到根據(jù)上一模型的公式可直接得到 Lq = 2 / 2(1- )其它量的計(jì)算同前。其它量的計(jì)算同前。126 5 5 排隊(duì)系統(tǒng)的優(yōu)化目標(biāo)排隊(duì)系統(tǒng)的優(yōu)化目標(biāo)與最優(yōu)化問題與最優(yōu)化問題 從經(jīng)濟(jì)角度考慮，排隊(duì)系統(tǒng)的從經(jīng)濟(jì)角度考慮，排隊(duì)系統(tǒng)的費(fèi)用應(yīng)該包含以下兩個(gè)方面：一

53、個(gè)費(fèi)用應(yīng)該包含以下兩個(gè)方面：一個(gè)是服務(wù)費(fèi)用，它是服務(wù)水平的遞增是服務(wù)費(fèi)用，它是服務(wù)水平的遞增函數(shù)；另一個(gè)是顧客等待的機(jī)會(huì)損函數(shù)；另一個(gè)是顧客等待的機(jī)會(huì)損失失( (費(fèi)用費(fèi)用) )，它是服務(wù)水平的遞減函，它是服務(wù)水平的遞減函數(shù)。兩者的總和呈一條數(shù)。兩者的總和呈一條U U形曲線。形曲線。127排隊(duì)系統(tǒng)優(yōu)化問題排隊(duì)系統(tǒng)優(yōu)化問題 系統(tǒng)最優(yōu)化的目標(biāo)就是尋求上述系統(tǒng)最優(yōu)化的目標(biāo)就是尋求上述合成費(fèi)用曲線的最小點(diǎn)。合成費(fèi)用曲線的最小點(diǎn)。 排隊(duì)系統(tǒng)的最優(yōu)化問題通常分為排隊(duì)系統(tǒng)的最優(yōu)化問題通常分為兩類：系統(tǒng)的靜態(tài)最優(yōu)設(shè)計(jì)，目的在兩類：系統(tǒng)的靜態(tài)最優(yōu)設(shè)計(jì)，目的在于使設(shè)備達(dá)到最大效益；系統(tǒng)動(dòng)態(tài)最于使設(shè)備達(dá)到最大效益；系

54、統(tǒng)動(dòng)態(tài)最優(yōu)運(yùn)營，是指一個(gè)給定排隊(duì)系統(tǒng)，如優(yōu)運(yùn)營，是指一個(gè)給定排隊(duì)系統(tǒng)，如何運(yùn)營可使某個(gè)目標(biāo)函數(shù)得到最優(yōu)。何運(yùn)營可使某個(gè)目標(biāo)函數(shù)得到最優(yōu)。128排隊(duì)系統(tǒng)常見的優(yōu)化問題排隊(duì)系統(tǒng)常見的優(yōu)化問題1)1)確定最優(yōu)服務(wù)率確定最優(yōu)服務(wù)率 * *；2)2)確定最佳服務(wù)臺(tái)數(shù)量確定最佳服務(wù)臺(tái)數(shù)量s s* *；3)3)選擇最為合適的服務(wù)規(guī)則；選擇最為合適的服務(wù)規(guī)則；4)4)或是確定上述幾個(gè)量的最優(yōu)組合。或是確定上述幾個(gè)量的最優(yōu)組合。 研究排隊(duì)系統(tǒng)的根本目的在于以研究排隊(duì)系統(tǒng)的根本目的在于以最少的設(shè)備得到最大的效益。最少的設(shè)備得到最大的效益。129本節(jié)討論的排隊(duì)系統(tǒng)優(yōu)化問題本節(jié)討論的排隊(duì)系統(tǒng)優(yōu)化問題 本章只討論系統(tǒng)靜

55、態(tài)的最優(yōu)設(shè)計(jì)問題。本章只討論系統(tǒng)靜態(tài)的最優(yōu)設(shè)計(jì)問題。這類問題一般可以借助于前面所得到的一這類問題一般可以借助于前面所得到的一些表達(dá)式來解決。些表達(dá)式來解決。 本節(jié)就本節(jié)就 ，s s 這兩個(gè)決策變量這兩個(gè)決策變量的分別單獨(dú)優(yōu)化，介紹兩個(gè)較簡(jiǎn)單的的分別單獨(dú)優(yōu)化，介紹兩個(gè)較簡(jiǎn)單的模型。模型。5.1 M/M/1/系統(tǒng)的最優(yōu)平均服系統(tǒng)的最優(yōu)平均服務(wù)率務(wù)率 * 設(shè)：設(shè)：c1 當(dāng)當(dāng) =1時(shí)服務(wù)系統(tǒng)單位時(shí)間的時(shí)服務(wù)系統(tǒng)單位時(shí)間的平均費(fèi)平均費(fèi) cw 平均每個(gè)顧客在系統(tǒng)逗留單位平均每個(gè)顧客在系統(tǒng)逗留單位時(shí)間的損失；時(shí)間的損失； y 系統(tǒng)單位時(shí)間的平均總費(fèi)用。系統(tǒng)單位時(shí)間的平均總費(fèi)用。其中其中 c1，cw 均為可知

56、。則目標(biāo)函數(shù)為均為可知。則目標(biāo)函數(shù)為Lccyw1求解過程求解過程將將L= ( -)，代入上式，得，代入上式，得 y 是關(guān)于決策變量是關(guān)于決策變量 的一元非線性函的一元非線性函數(shù)數(shù),由一階條件由一階條件解得駐點(diǎn)解得駐點(diǎn) 11wccy1210()wdyccd1*/ ccw 132求解過程（續(xù)）求解過程（續(xù)） 根號(hào)前取正號(hào)是為了保證根號(hào)前取正號(hào)是為了保證 1 ，這樣，系統(tǒng)才能達(dá)到穩(wěn)態(tài)。又由，這樣，系統(tǒng)才能達(dá)到穩(wěn)態(tài)。又由二階條件二階條件 ( ( ) )可知求出的可知求出的 * *為為( (,),)上的全局唯一最上的全局唯一最小點(diǎn)。將小點(diǎn)。將 * *代入代入y中，可得最小總平均費(fèi)中，可得最小總平均費(fèi)用用

57、0)(2322 wcdyd wcccy11*2133求解過程（續(xù)）求解過程（續(xù)） 另外，若設(shè)另外，若設(shè)cw為平均每個(gè)顧客在為平均每個(gè)顧客在隊(duì)列中等待單位時(shí)間的損失，則需用隊(duì)列中等待單位時(shí)間的損失，則需用 取代前式中的取代前式中的L，這時(shí)，這時(shí)類似可得一階條件：類似可得一階條件： 這一般采用數(shù)值法這一般采用數(shù)值法(如牛頓法如牛頓法)確定其確定其根根 *。)(2 qL022322213141 wwccccc134 興建一座港口碼頭，只有一個(gè)裝卸興建一座港口碼頭，只有一個(gè)裝卸船只的泊位。要求設(shè)計(jì)裝卸能力船只的泊位。要求設(shè)計(jì)裝卸能力 ，單，單位為（只位為（只/日）船數(shù)。已知：?jiǎn)挝谎b卸日）船數(shù)。已知：?jiǎn)挝谎b卸能力的平均生產(chǎn)費(fèi)用能力的平均生產(chǎn)費(fèi)用a=2千元，船只逗千元，船只逗留每日損失留每日損失b=1.5千元。船只到達(dá)服從千元。船只到達(dá)服從泊松分布，平均速率泊松分布，平均速率 =3只只/日。船只裝日。船只裝卸時(shí)間服從負(fù)指數(shù)分布。目標(biāo)是每日總卸時(shí)間服從負(fù)指數(shù)分布。目標(biāo)是每日總支出最少。支出最少。例例 =3 待定待定 模型模型 M/M/1/ 隊(duì)長隊(duì)長 Ls = /( - )總費(fèi)用總費(fèi)用 c =a +bL=a +b /( - ) 求導(dǎo)求導(dǎo) dc/d =a+(-b )/( - )2 = 0得得: - = (b /a