《Ch9排隊(duì)論》PPT課件

1、Queuing theory,第九章 排隊(duì)論,運(yùn)籌學(xué) Operations Research,9.1 排隊(duì)論的基本概念 9.2 排隊(duì)系統(tǒng)常用分布 9.3 單服務(wù)臺(tái)模型M/M/1 9.4 多服務(wù)臺(tái)模型M/M/s 9.5 其它服務(wù)時(shí)間分布模型 9.6 排隊(duì)系統(tǒng)的優(yōu)化,9.1 排隊(duì)論的基本概念,2020年7月24日星期五,9.1.1 排隊(duì)系統(tǒng)的描述,排隊(duì)系統(tǒng)的例子,9.1 排隊(duì)論的基本概念 Basic Concepts of Queuing theory,2020年7月24日星期五,排隊(duì)的過(guò)程可表示為：,9.1 排隊(duì)論的基本概念 Basic Concepts of Queuing theory,20

2、20年7月24日星期五,根據(jù)服務(wù)臺(tái)的數(shù)量及排隊(duì)方式，排隊(duì)系統(tǒng)可以分為 (1)單服務(wù)臺(tái)單隊(duì),(2)多服務(wù)臺(tái)單隊(duì),圖9-2單服務(wù)臺(tái)單隊(duì)系統(tǒng),顧客到達(dá),服務(wù)臺(tái),顧客離去,服務(wù)臺(tái),服務(wù)臺(tái),圖9-3 多服務(wù)臺(tái)單隊(duì)系統(tǒng),9.1 排隊(duì)論的基本概念 Basic Concepts of Queuing theory,2020年7月24日星期五,(3)多隊(duì)多服務(wù)臺(tái),(4)多服務(wù)臺(tái)串聯(lián)服務(wù),圖9-4 多服務(wù)臺(tái)多隊(duì)系統(tǒng),圖9-5 多服務(wù)臺(tái)串聯(lián)系統(tǒng),9.1 排隊(duì)論的基本概念 Basic Concepts of Queuing theory,顧客到達(dá),服務(wù)臺(tái),顧客離去,服務(wù)臺(tái),服務(wù)臺(tái),顧客到達(dá),顧客離去,2020年7月2

3、4日星期五,9.1.2排隊(duì)系統(tǒng)的基本組成,排隊(duì)系統(tǒng)由輸入過(guò)程、服務(wù)規(guī)則和服務(wù)臺(tái)三個(gè)部分組成,這是指要求服務(wù)的顧客按怎樣的規(guī)律到達(dá)排隊(duì)系統(tǒng)的過(guò)程，有時(shí)也稱之為顧客流。 （1）顧客總體數(shù)，又稱顧客源、輸入源。顧客源可以是有限的，也可以是無(wú)限的。 （2）顧客到達(dá)的形式。這是描述顧客是怎樣來(lái)到系統(tǒng)的，是單個(gè)到達(dá)，還是成批到達(dá)。 （3）顧客流的概率分布，或稱顧客相繼到達(dá)的時(shí)間間隔分布。這是首先需要確定的指標(biāo)。,9.1 排隊(duì)論的基本概念 Basic Concepts of Queuing theory,1.輸入過(guò)程,2020年7月24日星期五,(1)先到先服務(wù)（FCFS，F(xiàn)irst Come First

4、Serve）； (2)后到先服務(wù)（LCFS，Last Come First Serve）； (3)有優(yōu)先權(quán)的服務(wù)（PR，Priority） (4)隨機(jī)服務(wù)（SIRO，Service in Random Order）,9.1 排隊(duì)論的基本概念 Basic Concepts of Queuing theory,2.排隊(duì)規(guī)則,(1)等待制 指顧客到達(dá)系統(tǒng)后，所有服務(wù)臺(tái)都不空，顧客加入排隊(duì)行列等待服務(wù)，一直等到服務(wù)完畢以后才離去 ；,(2)損失制 指當(dāng)顧客到達(dá)系統(tǒng)時(shí)，所有服務(wù)臺(tái)都已被占用，顧客不愿等待而離開(kāi)系統(tǒng)。,2020年7月24日星期五,(3)混合制 這是等待制與損失制相結(jié)合的一種服務(wù)規(guī)則，一般是

5、指允許排隊(duì)，但又不允許隊(duì)列無(wú)限長(zhǎng)下去。大體有以下三種： 隊(duì)長(zhǎng)有限。當(dāng)?shù)却?wù)的顧客人數(shù)超過(guò)規(guī)定數(shù)量時(shí)，后來(lái)的顧客就自動(dòng)離去，另求服務(wù)，即系統(tǒng)的等待空間是有限的。 等待時(shí)間有限。即顧客在系統(tǒng)中的等待時(shí)間不超過(guò)某一給定的長(zhǎng)度T，當(dāng)?shù)却龝r(shí)間超過(guò)時(shí)間T時(shí)，顧客將自動(dòng)離去，并不再回來(lái)。 逗留時(shí)間（等待時(shí)間與服務(wù)時(shí)間之和）有限。,9.1 排隊(duì)論的基本概念 Basic Concepts of Queuing theory,2020年7月24日星期五,(1)服務(wù)臺(tái)數(shù)量及構(gòu)成形式 從數(shù)量上說(shuō)，服務(wù)臺(tái)有單臺(tái)和多臺(tái)之分。從構(gòu)成形式上看，有單隊(duì)單服務(wù)臺(tái)式、單隊(duì)多服務(wù)臺(tái)并聯(lián)式、多隊(duì)多服務(wù)臺(tái)并聯(lián)式、單隊(duì)多服務(wù)臺(tái)串聯(lián)式等等

6、，如圖9-2到9-5所示； (2)服務(wù)方式 指在某一時(shí)刻接受服務(wù)的顧客數(shù)，有單個(gè)服務(wù)和成批服務(wù)兩種； (3)服務(wù)時(shí)間的分布 在多數(shù)情況下，對(duì)某一個(gè)顧客的服務(wù)時(shí)間是一隨機(jī)變量，與顧客到達(dá)的時(shí)間間隔分布一樣，服務(wù)時(shí)間的分布有定長(zhǎng)分布、負(fù)指數(shù)分布、愛(ài)爾朗分布等等。,3.服務(wù)臺(tái),9.1 排隊(duì)論的基本概念 Basic Concepts of Queuing theory,服務(wù)臺(tái)可以從以下三個(gè)方面來(lái)描述：,2020年7月24日星期五,9.1.3 排隊(duì)系統(tǒng)的主要數(shù)量指標(biāo)、記號(hào)和符號(hào),9.1 排隊(duì)論的基本概念 Basic Concepts of Queuing theory,（1）隊(duì)長(zhǎng)和隊(duì)列長(zhǎng)(排隊(duì)長(zhǎng)) 隊(duì)長(zhǎng)

7、是指系統(tǒng)中的顧客數(shù)（排隊(duì)等待的顧客數(shù)與正在接受服務(wù)的顧客數(shù)之和） 隊(duì)列長(zhǎng)是指系統(tǒng)中正在排隊(duì)等待服務(wù)的顧客數(shù)。隊(duì)長(zhǎng)和隊(duì)列長(zhǎng)一般都是隨機(jī)變量 （2）等待時(shí)間和逗留時(shí)間 從顧客到達(dá)時(shí)刻起到他開(kāi)始接受服務(wù)止這段時(shí)間稱為等待時(shí)間。從顧客到達(dá)時(shí)刻起到他接受服務(wù)完止這段時(shí)間稱為逗留時(shí)間。兩種時(shí)間都是隨機(jī)變量 （3）忙期和閑期 忙期是指從顧客到達(dá)空閑著的服務(wù)機(jī)構(gòu)起，到服務(wù)再次成為空閑止的這段時(shí)間，服務(wù)機(jī)構(gòu)連續(xù)忙的時(shí)間。這是個(gè)隨機(jī)變量。與忙期相對(duì)的是閑期，即服務(wù)機(jī)構(gòu)連續(xù)保持空閑的時(shí)間。,1. 主要數(shù)量指標(biāo),2020年7月24日星期五,9.1 排隊(duì)論的基本概念 Basic Concepts of Queuing

8、theory,2. 記號(hào),時(shí)刻 t 系統(tǒng)中的顧客數(shù)（又稱為系統(tǒng)的狀態(tài)），即隊(duì)長(zhǎng)； 時(shí)刻 t 系統(tǒng)中排隊(duì)的顧客數(shù)，即列隊(duì)長(zhǎng)； 時(shí)刻 t 到達(dá)系統(tǒng)的顧客在系統(tǒng)中的逗留時(shí)間； 時(shí)刻 t 到達(dá)系統(tǒng)的顧客在系統(tǒng)中的等待時(shí)間,L：平均隊(duì)長(zhǎng)，即穩(wěn)態(tài)系統(tǒng)任一時(shí)刻顧客數(shù)的期望值； Lq：平均等待隊(duì)長(zhǎng)，即穩(wěn)態(tài)系統(tǒng)任一時(shí)刻等待服務(wù)的顧客數(shù)的期望值； W：平均逗留時(shí)間，即在任一時(shí)刻進(jìn)入穩(wěn)態(tài)系統(tǒng)的顧客逗留時(shí)間的期望值； Wq：平均等待時(shí)間，即在任一時(shí)刻進(jìn)入穩(wěn)態(tài)系統(tǒng)的顧客等待時(shí)間的期望值；,在平穩(wěn)狀態(tài)下:,2020年7月24日星期五,9.1 排隊(duì)論的基本概念 Basic Concepts of Queuing theor

9、y,：顧客到達(dá)的平均速率，即單位時(shí)間內(nèi)平均到達(dá)的顧客數(shù)； 1/：平均到達(dá)時(shí)間間隔； ：平均服務(wù)速率，即單位時(shí)間內(nèi)服務(wù)完畢離去的顧客數(shù)； 1/：平均服務(wù)時(shí)間； s ：系統(tǒng)中服務(wù)臺(tái)的個(gè)數(shù)； ：服務(wù)強(qiáng)度，即每個(gè)服務(wù)臺(tái)單位時(shí)間內(nèi)的平均服務(wù)時(shí)間，一般有/(s)； N：穩(wěn)態(tài)系統(tǒng)任一時(shí)刻的狀態(tài)（即系統(tǒng)中所有顧客數(shù)）； U：任一顧客在穩(wěn)態(tài)系統(tǒng)中的逗留時(shí)間； Q：任一顧客在穩(wěn)態(tài)系統(tǒng)中的等待時(shí)間； PnPN=n：穩(wěn)態(tài)系統(tǒng)任一時(shí)刻狀態(tài)為n的概率；特別當(dāng)n=0時(shí)，PnP0，即穩(wěn)態(tài)系統(tǒng)所有服務(wù)臺(tái)全部空閑的概率； e：有效平均到達(dá)率，即期望每單位時(shí)間內(nèi)來(lái)到系統(tǒng)（包括未進(jìn)入系統(tǒng)）的概率。,2020年7月24日星期五,3.排

10、隊(duì)系統(tǒng)的符號(hào),一個(gè)排隊(duì)系統(tǒng)的特征可以用六個(gè)參數(shù)表示，形式為： XYZ：ABC 或 X/Y/Z/A/B/C 其中 X 顧客到達(dá)的概率分布，可取M、D、Ek、G等； Y 服務(wù)時(shí)間的概率分布，可取M、D、Ek 、G等； Z 服務(wù)臺(tái)個(gè)數(shù)，取正整數(shù)； A 排隊(duì)系統(tǒng)的最大容量，可取正整數(shù)或； B 顧客源的最大容量，可取正整數(shù)或； C 排隊(duì)規(guī)則，可取FCFS、LCFS等。 例如 M/M/1：/FCFS 表示顧客到達(dá)的時(shí)間間隔是負(fù)指數(shù)分布，服務(wù)時(shí)間是負(fù)指數(shù)分布，一個(gè)服務(wù)臺(tái)，排隊(duì)系統(tǒng)和顧客源的容量都是無(wú)限，實(shí)行先到先服務(wù)的一個(gè)服務(wù)系統(tǒng)。,9.1 排隊(duì)論的基本概念 Basic Concepts of Queuin

11、g theory,2020年7月24日星期五,下一節(jié)：排隊(duì)系統(tǒng)常用分布,9.1 排隊(duì)論的基本概念 Basic Concepts of Queuing theory,9.2 排隊(duì)系統(tǒng)常用分布,2020年7月24日星期五,9.2.1 負(fù)指數(shù)分布,隨機(jī)變量T服從負(fù)指數(shù)分布，其分布函數(shù)為,密度函數(shù)為,T的期望值為,T的方差為,9.2 排隊(duì)系統(tǒng)常用分布,2020年7月24日星期五,負(fù)指數(shù)分布具有性質(zhì),(1)密度函數(shù),對(duì)時(shí)間t嚴(yán)格遞減,(2)無(wú)記憶性或馬爾柯夫性，即,(3)當(dāng)顧客到達(dá)過(guò)程是泊松流時(shí)，顧客相繼到達(dá)的間隔時(shí)間T 必服從負(fù)指數(shù)分布，這個(gè)性質(zhì)將在定理9.1中予以證明。,若隨機(jī)變量X的概率密度為,9

12、.2.2泊松分布,則稱X服從參數(shù)為的泊松(Poisson)分布，記為XP()。其均值和方差分別為,9.2 排隊(duì)系統(tǒng)常用分布,2020年7月24日星期五,【定義9.1】對(duì)于隨機(jī)過(guò)程 ,若滿足,1.Poisson流的定義,9.2 顧客到達(dá)和服務(wù)的時(shí)間分布,(1)獨(dú)立增量性(無(wú)后效性) 即對(duì)任意n個(gè)參數(shù) 增量 相互獨(dú)立 或者說(shuō)不相交的時(shí)間區(qū)間內(nèi)到達(dá)的顧客數(shù)互相獨(dú)立。,(2)增量平穩(wěn)性 即在長(zhǎng)度為 t 的時(shí)間區(qū)間內(nèi)恰好到達(dá)k個(gè)顧客的概率僅與區(qū)間長(zhǎng)度t有關(guān)，而與區(qū)間起始點(diǎn)無(wú)關(guān),(3)普遍性 即當(dāng)t充分小時(shí)，有,稱 為Poisson過(guò)程，N(t)服從泊松分布,2020年7月24日星期五,2排隊(duì)系統(tǒng)與泊松過(guò)

13、程,9.2 顧客到達(dá)和服務(wù)的時(shí)間分布,若N(t)為時(shí)間區(qū)間0,t）(t0)內(nèi)到達(dá)系統(tǒng)的顧客數(shù)，則N(t)是一個(gè)隨機(jī)變量，且 N(t)|t(0,T)為一個(gè)隨機(jī)過(guò)程。若該隨機(jī)過(guò)程滿足,（1）在不相重疊的區(qū)間內(nèi)，顧客的到達(dá)數(shù)是相互獨(dú)立的； （2）在時(shí)間區(qū)間t,t+t）內(nèi)有顧客的到達(dá)數(shù)只與區(qū)間長(zhǎng)度t有關(guān)，而與區(qū)間起始點(diǎn)t無(wú)關(guān)； （3）對(duì)于充分小的t，在時(shí)間區(qū)間t,t+t）內(nèi)有2個(gè)或2個(gè)以上的顧客到達(dá)的概率極小，以致于可以忽略,則認(rèn)為顧客到達(dá)系統(tǒng)的過(guò)程是泊松過(guò)程，且,2020年7月24日星期五,9.2 顧客到達(dá)和服務(wù)的時(shí)間分布,如果一個(gè)隨機(jī)變量，概率分布與時(shí)間t有關(guān)，則稱這個(gè)隨機(jī)變量為一隨機(jī)過(guò)程，排隊(duì)系

14、統(tǒng)中顧客到達(dá)的個(gè)數(shù)就是一個(gè)隨機(jī)過(guò)程。,【定理9.1】在排隊(duì)系統(tǒng)中，如果到達(dá)的顧客數(shù)服從以t為參數(shù)的泊松分布，則顧客相繼到達(dá)的時(shí)間間隔服從以為參數(shù)的負(fù)指數(shù)分布.,證明參看教材。,由定理9.1可以看出，“到達(dá)的顧客數(shù)是一個(gè)以為參數(shù)的泊松流”與“顧客相繼到達(dá)的時(shí)間間隔服從以為參數(shù)的負(fù)指數(shù)分布”兩個(gè)事實(shí)是等價(jià)的,2020年7月24日星期五,【定理9.2】設(shè)X1,X2,，Xk ,是k個(gè)互相獨(dú)立的，具有相同參數(shù)的負(fù)指數(shù)分布隨機(jī)變量，則隨機(jī)變量,服從k階愛(ài)爾朗(Erlang)分布，X的密度函數(shù)為,記為,或簡(jiǎn)記為,隨機(jī)變量X的均值和方差分別為：,9.2 排隊(duì)系統(tǒng)常用分布,2020年7月24日星期五,為單位時(shí)間

15、平均到達(dá)顧客數(shù)目，亦稱平均到達(dá)率。顧客到達(dá)服從泊松分布，亦稱顧客到達(dá)形成泊松流（最簡(jiǎn)單流）。,例1：一臺(tái)儀表由1000個(gè)元件組成，每個(gè)元件在一年工作時(shí)間內(nèi)發(fā)生故障的概率為0.001，并且與其它元件的狀況無(wú)關(guān)，求在一年內(nèi)不少于2個(gè)元件發(fā)生故障的概率。 解： 設(shè)X=元件發(fā)生故障個(gè)數(shù)，由于n=1000 P=0.001很小，可視發(fā)生故障服從泊松分布，其中=nP=1 因此,9.2 顧客到達(dá)和服務(wù)的時(shí)間分布,2020年7月24日星期五,下一節(jié)： 單服務(wù)臺(tái)模型,9.2 顧客到達(dá)和服務(wù)的時(shí)間分布,9.3單服務(wù)臺(tái)模型M/M/1,2020年7月24日星期五,9.3 單服務(wù)臺(tái)模型,9.3.1基本模型,設(shè)單位時(shí)間到達(dá)

16、系統(tǒng)的顧客數(shù)為 ，單位時(shí)間被服務(wù)完的顧客數(shù)為。由于是單服務(wù)臺(tái)，且顧客源無(wú)限，因此，在各種狀態(tài)的情況下，系統(tǒng)的“出生率”為，系統(tǒng)的“死亡率”為。系統(tǒng)在穩(wěn)態(tài)情況下的狀態(tài)轉(zhuǎn)移如圖9-6所示,圖9-6,根據(jù)以上狀態(tài)轉(zhuǎn)移圖，可以得出如下平衡方程,(91),(92),1 系統(tǒng)狀態(tài)概率Pn(t)的計(jì)算,2020年7月24日星期五,9.3 單服務(wù)臺(tái)模型,由(91)和(92)可以遞推求解P1，P2，Pn，得到,(93),(94),表示平均到達(dá)率與平均服務(wù)率之比，稱為服務(wù)強(qiáng)度,2020年7月24日星期五,9.3 單服務(wù)臺(tái)模型,【例9.1】高速公路收費(fèi)處設(shè)有一個(gè)收費(fèi)通道，汽車到達(dá)服從泊松分布，平均到達(dá)速率為150輛

17、小時(shí)，收費(fèi)時(shí)間服從負(fù)指數(shù)分布，平均收費(fèi)時(shí)間為15秒輛。求 (1)收費(fèi)處空閑的概率； (2)收費(fèi)處忙的概率； (3)系統(tǒng)中分別有1，2，3輛車的概率。,【解】根據(jù)題意, =150輛/小時(shí), 1/=15秒=1/240（小時(shí)/輛）,即240（輛/小時(shí)）。/=150/240=5/8，則有 (1)系統(tǒng)空閑的概率為：P0=1=1(5/8)=3/8=0.375 (2)系統(tǒng)忙的概率為：1-P0=5/8=0.625 (3)系統(tǒng)中有1輛車的概率為：P1=(1)=0.6250.375=0.234 系統(tǒng)中有2輛車的概率為：P2= 2(1)= 0.2340.625=0.146 系統(tǒng)中有3輛車的概率為：P3=3(1)=0

18、.1460.625=0.091,2020年7月24日星期五,2. 系統(tǒng)的運(yùn)行指標(biāo),(1)系統(tǒng)中的平均顧客數(shù)（系統(tǒng)中顧客數(shù)的期望值）L,即隊(duì)長(zhǎng)為系統(tǒng)中顧客數(shù)的期望值（系統(tǒng)中各種狀態(tài)的加權(quán)平均值）,(2)隊(duì)列中的平均顧客數(shù),9.3 單服務(wù)臺(tái)模型,2020年7月24日星期五,9.3 單服務(wù)臺(tái)模型,(3)顧客在系統(tǒng)中的平均逗留時(shí)間W,(98),(4)顧客在隊(duì)列中的平均逗留時(shí)間 Wq,(99),(910),Little公式:,2020年7月24日星期五,9.3 單服務(wù)臺(tái)模型,【例9.2】輕軌進(jìn)站口售票處設(shè)有一個(gè)售票窗口，乘客到達(dá)服從泊松分布，平均到達(dá)速率為200人/小時(shí)，售票時(shí)間服從負(fù)指數(shù)分布，平均售票

19、時(shí)間為15秒/人。求L、Lq、W和Wq。 【解】根據(jù)題意，=200人/小時(shí)，=240人/小時(shí)，=5/6。,2020年7月24日星期五,9.3 單服務(wù)臺(tái)模型,9.3.2有限隊(duì)列模型,如果系統(tǒng)的最大容量為N，對(duì)于單服務(wù)臺(tái)的情形，排隊(duì)等待的顧客最多為N-1，在某一時(shí)刻一顧客到達(dá)時(shí)，如系統(tǒng)中已有N個(gè)顧客，那么這個(gè)顧客就被拒絕進(jìn)入系統(tǒng)。系統(tǒng)狀態(tài)轉(zhuǎn)移如圖9-7,圖97,1.系統(tǒng)狀態(tài)概率的計(jì)算,2020年7月24日星期五,9.3 單服務(wù)臺(tái)模型,由狀態(tài)轉(zhuǎn)移圖9-7，建立系統(tǒng)概率平衡方程如下,(911),(912),(913),2020年7月24日星期五,93 單服務(wù)臺(tái)模型,(914),(915),2020年7

20、月24日星期五,9.3 單服務(wù)臺(tái)模型,根據(jù)式912和913可以導(dǎo)出系統(tǒng)的各個(gè)指標(biāo)，對(duì)于1，有,(9-16),(1)系統(tǒng)中的平均顧客數(shù)L,2020年7月24日星期五,9.3 單服務(wù)臺(tái)模型,(917),(2)隊(duì)列中的平均顧客數(shù)Lq,(918),e 稱為有效到達(dá)率，即單位時(shí)間內(nèi)到達(dá)并能進(jìn)入隊(duì)列的平均顧客數(shù)。e 稱為有效服務(wù)強(qiáng)度,2020年7月24日星期五,9.3 單服務(wù)臺(tái)模型,(3)顧客在系統(tǒng)中的平均逗留時(shí)間W,(9-19),(4)顧客在隊(duì)列中的平均逗留時(shí)間,(9-20),2020年7月24日星期五,9.3 單服務(wù)臺(tái)模型,【例9.3】咨詢中心有一位咨詢工作人員，每次只能咨詢一人，另外有4個(gè)座位供前來(lái)

21、咨詢的人等候。某人到來(lái)發(fā)現(xiàn)沒(méi)有座位，就不再等待而離去。前來(lái)咨詢者到達(dá)服從泊松流，到達(dá)的平均速率為4人/小時(shí)，咨詢?nèi)藛T的平均咨詢時(shí)間為10分鐘/人。咨詢時(shí)間服從負(fù)指數(shù)分布。求： (1)咨詢者到達(dá)不用等待就可咨詢的概率 (2)咨詢中心的平均人數(shù)以及等待咨詢的平均人數(shù) (3)咨詢者來(lái)咨詢中心一次平均花費(fèi)的時(shí)間以及平均等待的時(shí)間 (4)咨詢者到達(dá)后因客滿而離去的概率 (5)增加一個(gè)咨詢工作人員可以減少的顧客損失率,【解】N=4+1=5，=4人/小時(shí)，=6人/小時(shí)，=2/3,(1),2020年7月24日星期五,9.3 單服務(wù)臺(tái)模型,(2),(3),(4),因客滿而離去的概率為0.048,(5) 當(dāng)N=6

22、時(shí),2020年7月24日星期五,9.3 單服務(wù)臺(tái)模型,即增加一個(gè)咨詢工作人員可以減少顧客損失率1.6%,9.3.3 有限顧客源模型,設(shè)顧客總數(shù)為m。當(dāng)顧客需要服務(wù)時(shí)，就進(jìn)入隊(duì)列等待；服務(wù)完畢后，重新回到顧客源中，如此循環(huán)往復(fù)。由于顧客源的數(shù)量有限，因此隊(duì)列的長(zhǎng)度也是有限的，并且隊(duì)列的長(zhǎng)度必定小于顧客源總數(shù) 。,有限源系統(tǒng)顧客的平均到達(dá)速率：,2020年7月24日星期五,9.3 單服務(wù)臺(tái)模型,0,1,2,n-1,n,n+1,m-1,m,圖9-8 有限顧客源模型狀態(tài)轉(zhuǎn)移圖,狀態(tài)轉(zhuǎn)移圖如圖9-8,由圖9-8得到系統(tǒng)穩(wěn)態(tài)概率平衡方程組,1系統(tǒng)狀態(tài)概率的計(jì)算,(921),2020年7月24日星期五,9.

23、3 單服務(wù)臺(tái)模型,用遞推方法解該方程組，得到,(922),(923),2 有限源系統(tǒng)的運(yùn)行指標(biāo),在求得系統(tǒng)中出現(xiàn)顧客數(shù)的概率后，即可求得系統(tǒng)的運(yùn)行指標(biāo)(推導(dǎo)過(guò)程略),2020年7月24日星期五,9.3 單服務(wù)臺(tái)模型,(924),(925),(926),(927),在機(jī)器維修問(wèn)題中，L是待檢修及正在檢修的平均機(jī)器數(shù)，而,表示正常運(yùn)行的平均機(jī)器數(shù)。,2020年7月24日星期五,9.3 單服務(wù)臺(tái)模型,【例9.4】某車間有5臺(tái)機(jī)器，每臺(tái)機(jī)器的連續(xù)運(yùn)轉(zhuǎn)時(shí)間服從負(fù)指數(shù)分布，一天（8小時(shí)）平均連續(xù)運(yùn)行時(shí)間120分鐘。有一個(gè)修理工，每次修理時(shí)間服從負(fù)指數(shù)分布，平均每次96分鐘。求： (1)修理工忙的概率(記為

24、Pb)； (2)五臺(tái)機(jī)器都出故障的概率； (3)出故障的平均臺(tái)數(shù)； (4)平均停工時(shí)間； (5)平均等待修理時(shí)間； (6)評(píng)價(jià)這個(gè)系統(tǒng)的運(yùn)行情況,【解】一天為一個(gè)單位時(shí)間。認(rèn)為一天內(nèi)來(lái)修理的機(jī)器數(shù)平均為4臺(tái)，修理工一天平均修理機(jī)器數(shù)為5臺(tái)。m=5，=4，=5，=0.8,2020年7月24日星期五,9.3 單服務(wù)臺(tái)模型,由計(jì)算結(jié)果看出，系統(tǒng)的修理工幾乎沒(méi)有空閑時(shí)間，機(jī)器的停工時(shí)間是平均運(yùn)行時(shí)間的三倍，系統(tǒng)的服務(wù)效率很低,2020年7月24日星期五,9.3 單服務(wù)臺(tái)模型,作業(yè)：教材P216 T 1，2，3，4，5，6,下一節(jié)： 9.4多服務(wù)臺(tái)模型,9.4多服務(wù)臺(tái)模型M/M/s,2020年7月24日

25、星期五,9.4多服務(wù)臺(tái)模型,9.4.1基本模型,規(guī)定各服務(wù)臺(tái)工作相互獨(dú)立且服務(wù)速率相同,系統(tǒng)的平均服務(wù)速率為 s,令,0,1,2,s-1,s,s+1,n-1,n,圖9-9 基本模型狀態(tài)轉(zhuǎn)移圖,系統(tǒng)的狀態(tài)轉(zhuǎn)移圖9-9。,2020年7月24日星期五,9.4多服務(wù)臺(tái)模型,穩(wěn)態(tài)概率方程,(928),(929),(930),(931),(932),(933),2020年7月24日星期五,9.4多服務(wù)臺(tái)模型,顧客需要等待 (系統(tǒng)已有s個(gè)顧客)的概率,與單服務(wù)臺(tái)系統(tǒng)的方法類似，有,2020年7月24日星期五,9.4多服務(wù)臺(tái)模型,【例9.5】銀行辦理個(gè)人儲(chǔ)蓄業(yè)務(wù)有三個(gè)窗口，顧客到達(dá)服從泊松流，到達(dá)速率為0.9

26、人分，辦理業(yè)務(wù)時(shí)間服從負(fù)指數(shù)分布，每個(gè)窗口的平均服務(wù)速率為0.4人分。顧客到達(dá)后取得一個(gè)排隊(duì)號(hào)，依次由空閑窗口按號(hào)碼順序辦理儲(chǔ)蓄業(yè)務(wù)。求： (1)所有窗口都空閑的概率； (2)平均隊(duì)長(zhǎng)； (3)平均等待時(shí)間及逗留時(shí)間； (4)顧客到達(dá)后必須等待的概率。,(1)所有窗口都空閑的概率，即求P0,2020年7月24日星期五,(2)平均隊(duì)長(zhǎng)，先求Lq ,再求L,(3)平均等待時(shí)間和平均逗留時(shí)間，即求Wq和W的值,(4)顧客到達(dá)后必須等待，即n3,9.4多服務(wù)臺(tái)模型,2020年7月24日星期五,9.4多服務(wù)臺(tái)模型,9.4.2有限隊(duì)列模型,0,1,2,s-1,s,s+1,N-1,N,圖9-10 有限隊(duì)列模

27、型狀態(tài)轉(zhuǎn)移圖,設(shè)系統(tǒng)容量為N(Ns)，當(dāng)系統(tǒng)中的顧客數(shù)nN時(shí)，到達(dá)的顧客進(jìn)入系統(tǒng)；當(dāng)nN時(shí)，到達(dá)的顧客就被拒絕。設(shè)顧客到達(dá)的速率為，每個(gè)服務(wù)臺(tái)服務(wù)的速率為，,系統(tǒng)的狀態(tài)轉(zhuǎn)移圖見(jiàn)圖9-10,2020年7月24日星期五,9.4多服務(wù)臺(tái)模型,穩(wěn)定狀態(tài)的狀態(tài)概率轉(zhuǎn)移方程為：,(938),(939),(940),(941),(942),(943),(944),2020年7月24日星期五,9.4多服務(wù)臺(tái)模型,(945),系統(tǒng)的運(yùn)行指標(biāo):,(946),(947),(948),(949),2020年7月24日星期五,9.4多服務(wù)臺(tái)模型,【例9.6】某旅館有10個(gè)床位，旅客到達(dá)服從泊松流，平均速率為6人天，旅客

28、平均逗留時(shí)間為2天，求： (1)旅館客滿的概率； (2) 每天客房平均占用數(shù).,旅館10個(gè)床位全滿的概率為0.3019,平均占用8.377個(gè)床位?？头空加寐蕿?3.77%。,2020年7月24日星期五,9.4多服務(wù)臺(tái)模型,9.4.3有限顧客源模型,設(shè)顧客源為有限數(shù)m，服務(wù)臺(tái)個(gè)數(shù)為s，且ms。這個(gè)模型的典型例子是機(jī)器維修問(wèn)題，機(jī)器數(shù)量為m臺(tái)，修理工數(shù)量為s人,狀態(tài)概率：,式中：,(951),(950),2020年7月24日星期五,9.4多服務(wù)臺(tái)模型,運(yùn)行指標(biāo),2020年7月24日星期五,9.4多服務(wù)臺(tái)模型,【例9.7】車間有5臺(tái)機(jī)器，每臺(tái)機(jī)器的故障率為1次小時(shí)，有2個(gè)修理工負(fù)責(zé)修理這5臺(tái)機(jī)器，工

29、作效率相同，為4臺(tái)小時(shí)。求： (1)等待修理的平均機(jī)器數(shù)； (2)等待修理及正在修理的平均機(jī)器數(shù)； (3)每小時(shí)發(fā)生故障的平均機(jī)器數(shù)； (4)平均等待修理的時(shí)間； (5)平均停工時(shí)間。,【解】這是一個(gè) 模型,2020年7月24日星期五,9.4多服務(wù)臺(tái)模型,P1=0.394， P2=0.197 ,P3=0.074， P4=0.018， P5=0.002,由式(951)可以計(jì)算得到,2020年7月24日星期五,作業(yè)：教材P216 T 7，8,下一節(jié)：其它服務(wù)時(shí)間分布模型,9.4多服務(wù)臺(tái)模型,9.5其它服務(wù)時(shí)間分布模型,2020年7月24日星期五,9.5 其它服務(wù)時(shí)間分布模型,9.5.1一般分布模型

30、,G表示服務(wù)時(shí)間T的分布為任意的概率分布，但已知期望值E(T)和方差Var(T)。 該模型被稱為“單服務(wù)臺(tái)泊松到達(dá)、任意服務(wù)時(shí)間的排隊(duì)模型”,在穩(wěn)態(tài)情況下，當(dāng) 時(shí)，可以證明下列PK (PollaczekKhint chine)公式成立：,其他指標(biāo)為（推導(dǎo)過(guò)程略）：,(957),(958),2020年7月24日星期五,9.5 其它服務(wù)時(shí)間分布模型,【例9.8】某維修站有一技工修理出故障機(jī)器?，F(xiàn)已知機(jī)器按泊松流發(fā)生故障，平均故障率為每小時(shí)5臺(tái)，機(jī)器排隊(duì)有兩種類型，一種修理時(shí)間為9分鐘，另一種是12分鐘，資料統(tǒng)計(jì)知，1/3故障需要修理12分鐘。試求此維修站的運(yùn)行指標(biāo)。 【解】服務(wù)時(shí)間可以看成是二項(xiàng)分

31、布,利用PK公式求得,2020年7月24日星期五,9.5 其它服務(wù)時(shí)間分布模型,9.5.2定長(zhǎng)分布模型,模型符號(hào)中的D表示服務(wù)時(shí)間為固定長(zhǎng)度，即為常數(shù).該模型被稱為單服務(wù)臺(tái)泊松到達(dá)、定長(zhǎng)服務(wù)時(shí)間的排隊(duì)模型.,因此，只需將模型中 的方差改為0，即可得到定長(zhǎng)排隊(duì)模型的各個(gè)指標(biāo)。,2020年7月24日星期五,9.5 其它服務(wù)時(shí)間分布模型,【解】服務(wù)時(shí)間定長(zhǎng)，該服務(wù)系統(tǒng)是一個(gè),排隊(duì)系統(tǒng)，其中：,代入式(958)計(jì)算得,【例9.9】某汽車沖洗站有一套自動(dòng)沖洗設(shè)備，沖洗每輛汽車所需時(shí)間為6分鐘，到此沖洗站來(lái)沖洗汽車的到達(dá)過(guò)程服從泊松分布，每小時(shí)平均到達(dá)6輛，求該排隊(duì)系統(tǒng)的有關(guān)運(yùn)行指標(biāo)。,2020年7月24

32、日星期五,9.5 其它服務(wù)時(shí)間分布模型,9.5.3愛(ài)爾朗分布模型,在此模型中，每一個(gè)顧客必須依次經(jīng)過(guò)k個(gè)服務(wù)站，接受k次服務(wù)后才構(gòu)成一個(gè)完整的服務(wù)過(guò)程。該模型假設(shè)每個(gè)服務(wù)站的服務(wù)時(shí)間Ti服務(wù)相同的負(fù)指數(shù)分布（參數(shù)為k）。則總的服務(wù)時(shí)間,服從k階愛(ài)爾朗（Erlang）分布。其他條件與標(biāo)準(zhǔn)的M/M/1模型相同。,此模型的如下數(shù)量指標(biāo),(959),(960),(961),2020年7月24日星期五,9.5 其它服務(wù)時(shí)間分布模型,(962),(963),在M/EK/1/FCFS排隊(duì)系統(tǒng)中 ,而當(dāng)K時(shí)，m/EK/1/排隊(duì)系統(tǒng)可認(rèn)為為m/D/1排隊(duì)系統(tǒng)。在m/D/1排隊(duì)系統(tǒng)中,2020年7月24日星期五,

33、9.8.2 M/D/1: / /FCFS,在m/D/1排隊(duì)系統(tǒng)中,2020年7月24日星期五,9.5 其它服務(wù)時(shí)間分布模型,【例9.10】一個(gè)質(zhì)量檢查員平均每小時(shí)收到2件送來(lái)檢驗(yàn)的樣品，每件樣品要依次完成5項(xiàng)檢驗(yàn)才能判定是否合格。據(jù)統(tǒng)計(jì)，每項(xiàng)檢驗(yàn)所需時(shí)間的期望值都是4分鐘，每項(xiàng)檢驗(yàn)的時(shí)間和送檢產(chǎn)品的到達(dá)時(shí)間間隔都為負(fù)指數(shù)分布。求檢驗(yàn)過(guò)程的各項(xiàng)指標(biāo)。,【解】該檢驗(yàn)系統(tǒng)是一個(gè) 排隊(duì)系統(tǒng)，且,2020年7月24日星期五,作業(yè)：教材P216 T9，10，11,下一節(jié)：排隊(duì)系統(tǒng)的優(yōu)化,9.5 其它服務(wù)時(shí)間分布模型,9.6排隊(duì)系統(tǒng)的優(yōu)化,2020年7月24日星期五,9.6排隊(duì)系統(tǒng)的優(yōu)化,排隊(duì)系統(tǒng)的費(fèi)用包含

34、以下兩個(gè)方面：一個(gè)是服務(wù)費(fèi)用，它是服務(wù)水平的遞增函數(shù)；另一個(gè)是顧客等待的機(jī)會(huì)損失（費(fèi)用），它是服務(wù)水平的遞減函數(shù)。兩者的總和呈一條U形曲線，如圖9-11。,服務(wù)水平,費(fèi)用,等待費(fèi)用,服務(wù)費(fèi)用,總費(fèi)用,如圖9-11,9.6.1排隊(duì)系統(tǒng)經(jīng)濟(jì)分析,2020年7月24日星期五,9.6排隊(duì)系統(tǒng)的優(yōu)化,排隊(duì)系統(tǒng)的優(yōu)化問(wèn)題常常分為兩類：一類稱之為系統(tǒng)的靜態(tài)最優(yōu)設(shè)計(jì)，目的在于使設(shè)備達(dá)到最大效益，或者說(shuō)，在保證一定服務(wù)質(zhì)量指標(biāo)的前提下，要求機(jī)構(gòu)最為經(jīng)濟(jì)；另一類叫做系統(tǒng)動(dòng)態(tài)最優(yōu)運(yùn)營(yíng)，是指一個(gè)給定排隊(duì)系統(tǒng)，如何運(yùn)營(yíng)可使某個(gè)目標(biāo)函數(shù)得到最優(yōu)。歸納起來(lái)，排隊(duì)系統(tǒng)常見(jiàn)的優(yōu)化問(wèn)題有：,（1）確定最優(yōu)服務(wù)率 （2）確定最佳服

35、務(wù)臺(tái)數(shù)量 （3）選擇最為合適的服務(wù)規(guī)則 （4）或是確定上述幾個(gè)量的最佳組合,2020年7月24日星期五,式中：Cs 為 =1 時(shí)單位時(shí)間內(nèi)的服務(wù)費(fèi)用；,Cw為每個(gè)顧客在系統(tǒng)中逗留單位時(shí)間的費(fèi)用,穩(wěn)態(tài)下取目標(biāo)函數(shù)z為單位時(shí)間服務(wù)成本與顧客在系統(tǒng)逗留費(fèi)用之和的期望值最小：,M/M/1/:/FCFS,9.6排隊(duì)系統(tǒng)的優(yōu)化,9.6.2最優(yōu)服務(wù)水平,的確定,1.基本模型,（965）,(966),2020年7月24日星期五,9.6排隊(duì)系統(tǒng)的優(yōu)化,【例9.11】某地欲興建一座港口碼頭，但只有一個(gè)裝卸船只的位置，現(xiàn)要求設(shè)計(jì)裝卸能力，裝卸能力用每天裝卸的船只數(shù)表示。已知單位裝卸能力每天平均生產(chǎn)成本為2000元，

36、船只到港后若不能及時(shí)裝卸，停留一天損失運(yùn)輸費(fèi)1500元。預(yù)計(jì)船只的平均到達(dá)率為3只/天。設(shè)船只到達(dá)的時(shí)間間隔和裝卸時(shí)間都服從負(fù)指數(shù)分布。問(wèn)港口裝卸能力為多大時(shí)，每天的總支出最少？,【解】 Cs=2000元/天；Cw=1500元/天； =3只/天。由式(9.66)有,即最優(yōu)裝卸能力為4.5只/天。,2020年7月24日星期五,2.有限隊(duì)列模型的最優(yōu)服務(wù)率M/M/1/:N/FCFS,單位時(shí)間內(nèi)達(dá)到系統(tǒng)的平均顧客數(shù)：,設(shè)服務(wù)一個(gè)顧客服務(wù)機(jī)構(gòu)的收入為G，單位時(shí)間收入的期望值是,給定N及Cs/G 求出* ,或給定Cs/G 及求N* 。,PN為被拒絕的概率，1-PN為能接受服務(wù)的概率.,取純利潤(rùn)最大:,9