《Ch9排隊論》PPT課件

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

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

3、4日星期五,9.1.2排隊系統(tǒng)的基本組成,排隊系統(tǒng)由輸入過程、服務(wù)規(guī)則和服務(wù)臺三個部分組成,這是指要求服務(wù)的顧客按怎樣的規(guī)律到達排隊系統(tǒng)的過程，有時也稱之為顧客流。 （1）顧客總體數(shù)，又稱顧客源、輸入源。顧客源可以是有限的，也可以是無限的。 （2）顧客到達的形式。這是描述顧客是怎樣來到系統(tǒng)的，是單個到達，還是成批到達。 （3）顧客流的概率分布，或稱顧客相繼到達的時間間隔分布。這是首先需要確定的指標。,9.1 排隊論的基本概念 Basic Concepts of Queuing theory,1.輸入過程,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)隨機服務(wù)（SIRO，Service in Random Order）,9.1 排隊論的基本概念 Basic Concepts of Queuing theory,2.排隊規(guī)則,(1)等待制 指顧客到達系統(tǒng)后，所有服務(wù)臺都不空，顧客加入排隊行列等待服務(wù)，一直等到服務(wù)完畢以后才離去 ；,(2)損失制 指當(dāng)顧客到達系統(tǒng)時，所有服務(wù)臺都已被占用，顧客不愿等待而離開系統(tǒng)。,2020年7月24日星期五,(3)混合制 這是等待制與損失制相結(jié)合的一種服務(wù)規(guī)則，一般是

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

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

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

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

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

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

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

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

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

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

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

16、系統(tǒng)的顧客數(shù)為 ，單位時間被服務(wù)完的顧客數(shù)為。由于是單服務(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)的計算,2020年7月24日星期五,9.3 單服務(wù)臺模型,由(91)和(92)可以遞推求解P1，P2，Pn，得到,(93),(94),表示平均到達率與平均服務(wù)率之比，稱為服務(wù)強度,2020年7月24日星期五,9.3 單服務(wù)臺模型,【例9.1】高速公路收費處設(shè)有一個收費通道，汽車到達服從泊松分布，平均到達速率為150輛

17、小時，收費時間服從負指數(shù)分布，平均收費時間為15秒輛。求 (1)收費處空閑的概率； (2)收費處忙的概率； (3)系統(tǒng)中分別有1，2，3輛車的概率。,【解】根據(jù)題意, =150輛/小時, 1/=15秒=1/240（小時/輛）,即240（輛/小時）。/=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)的運行指標,(1)系統(tǒng)中的平均顧客數(shù)（系統(tǒng)中顧客數(shù)的期望值）L,即隊長為系統(tǒng)中顧客數(shù)的期望值（系統(tǒng)中各種狀態(tài)的加權(quán)平均值）,(2)隊列中的平均顧客數(shù),9.3 單服務(wù)臺模型,2020年7月24日星期五,9.3 單服務(wù)臺模型,(3)顧客在系統(tǒng)中的平均逗留時間W,(98),(4)顧客在隊列中的平均逗留時間 Wq,(99),(910),Little公式:,2020年7月24日星期五,9.3 單服務(wù)臺模型,【例9.2】輕軌進站口售票處設(shè)有一個售票窗口，乘客到達服從泊松分布，平均到達速率為200人/小時，售票時間服從負指數(shù)分布，平均售票

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

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

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

22、時,2020年7月24日星期五,9.3 單服務(wù)臺模型,即增加一個咨詢工作人員可以減少顧客損失率1.6%,9.3.3 有限顧客源模型,設(shè)顧客總數(shù)為m。當(dāng)顧客需要服務(wù)時，就進入隊列等待；服務(wù)完畢后，重新回到顧客源中，如此循環(huán)往復(fù)。由于顧客源的數(shù)量有限，因此隊列的長度也是有限的，并且隊列的長度必定小于顧客源總數(shù) 。,有限源系統(tǒng)顧客的平均到達速率：,2020年7月24日星期五,9.3 單服務(wù)臺模型,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)概率的計算,(921),2020年7月24日星期五,9.

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

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

25、星期五,9.4多服務(wù)臺模型,9.4.1基本模型,規(guī)定各服務(wù)臺工作相互獨立且服務(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ù)臺模型,穩(wěn)態(tài)概率方程,(928),(929),(930),(931),(932),(933),2020年7月24日星期五,9.4多服務(wù)臺模型,顧客需要等待 (系統(tǒng)已有s個顧客)的概率,與單服務(wù)臺系統(tǒng)的方法類似，有,2020年7月24日星期五,9.4多服務(wù)臺模型,【例9.5】銀行辦理個人儲蓄業(yè)務(wù)有三個窗口，顧客到達服從泊松流，到達速率為0.9

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

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

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

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

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

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

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

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

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

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

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