第運(yùn)籌學(xué)06章課件

1、1第六章 排隊(duì)論本章內(nèi)容重點(diǎn)排隊(duì)論的基本概念研究的基本問題與排隊(duì)問題求解思路泊松輸入指數(shù)服務(wù)排隊(duì)模型其他模型選介排隊(duì)系統(tǒng)的優(yōu)化目標(biāo)與最優(yōu)化問題3 排隊(duì)論(Queuing Theory) 又稱隨機(jī)服務(wù)系統(tǒng)理論(Random Service System Theory),是一門研究擁擠現(xiàn)象(排隊(duì)、等待)的科學(xué)。具體地說，它是在研究各種排隊(duì)系統(tǒng)概率規(guī)律性的基礎(chǔ)上，解決相應(yīng)排隊(duì)系統(tǒng)的最優(yōu)設(shè)計(jì)和最優(yōu)控制問題。前 言4 排隊(duì)論是1909年由丹麥工程師愛爾朗(A.KErlang)在研究電話系統(tǒng)時(shí)創(chuàng)立的，幾十年來排隊(duì)論的應(yīng)用領(lǐng)域越來越廣泛，理論也日漸完善。特別是自20世紀(jì)60年代以來，由于計(jì)算機(jī)的飛速發(fā)展，更

2、為排隊(duì)論的應(yīng)用開拓了廣闊的前景。前 言5第一節(jié) 排隊(duì)論的基本概念 排隊(duì)是我們在日常生活和生產(chǎn)中經(jīng)常遇到的現(xiàn)象: 人多時(shí)排隊(duì)乘車； 顧客到商店購買物品交款； 病人到醫(yī)院看??； 旅客到車站售票處購買車票； 食堂就餐等。 常常出現(xiàn)人們排隊(duì)和等待現(xiàn)象。排隊(duì)的不一定是人，也可以是物：通信衛(wèi)星與地面待傳遞的信息；生產(chǎn)線上的原料、半成品等待加工；因故障停止運(yùn)轉(zhuǎn)的機(jī)器等待工人修理；碼頭的船只等待裝卸貨物；要降落的飛機(jī)因跑道不空而在空中盤旋等。7一、 排隊(duì)系統(tǒng)特征與基本過程 1.排隊(duì)問題的共同特征 有要求某種服務(wù)的人或物。排隊(duì)論里把要求服務(wù)的對象統(tǒng)稱為“顧客”。 有提供服務(wù)的人或機(jī)構(gòu)。把提供服務(wù)。的人或機(jī)構(gòu)稱為

3、“服務(wù)臺(tái)”或“服務(wù)員”。 顧客的到達(dá)、服務(wù)的時(shí)間至少有一個(gè)是隨機(jī)的，服從某種分布。8 2. 基本排隊(duì)過程 任何一個(gè)排隊(duì)問題的基本排隊(duì)過程都可以用圖 6-1表示：每個(gè)顧客由顧客源按照一定方式到達(dá)服務(wù)系統(tǒng)，首先加入隊(duì)列排隊(duì)等待接受服務(wù)，然后服務(wù)臺(tái)按一定規(guī)則從隊(duì)列中選擇顧客進(jìn)行服務(wù)，獲得服務(wù)后的顧客立即離開。一般排隊(duì)系統(tǒng)都可由圖6-1描述圖6-1 隨機(jī)服務(wù)系統(tǒng)排隊(duì)系統(tǒng)示意圖10 面對擁擠現(xiàn)象，顧客排隊(duì)時(shí)間的長短與服務(wù)設(shè)施規(guī)模的大小，就構(gòu)成了設(shè)計(jì)隨機(jī)服務(wù)系統(tǒng)中的一對矛盾。 如何做到既保證一定的服務(wù)質(zhì)量指標(biāo)，又使服務(wù)設(shè)施費(fèi)用經(jīng)濟(jì)合理，恰當(dāng)?shù)亟鉀Q顧客排隊(duì)時(shí)間與服務(wù)設(shè)施費(fèi)用大小這對矛盾，這就是排隊(duì)論所要研究

4、解決的問題之一。11 通常，排隊(duì)系統(tǒng)都有輸入過程、服務(wù)規(guī)則和服務(wù)臺(tái)等3個(gè)組成部分： 1) 輸入過程。這是指要求服務(wù)的顧客是按怎樣的規(guī)律到達(dá)排隊(duì)系統(tǒng)的過程，有時(shí)也把它稱為顧客流。一般可以從3個(gè)方面來描述一個(gè)輸入過程。二、 排隊(duì)系統(tǒng)的基本組成部分121) 輸入過程 顧客總體數(shù)(又稱顧客源、輸入源)。這是指顧客的來源。顧客源可以是有限的，也可以是無限的。例如，到售票處購票的顧客總數(shù)可以認(rèn)為是無限的，而某個(gè)工廠因故障待修的機(jī)床則是有限的。13 顧客到達(dá)方式。描述顧客是怎樣來到系統(tǒng)的，他們是單個(gè)到達(dá)，還是成批到達(dá)。病人到醫(yī)院看病是顧客單個(gè)到達(dá)的例子。在庫存問題中如將生產(chǎn)器材進(jìn)貨或產(chǎn)品入庫看做是顧客，那么

5、這種顧客則是成批到達(dá)的（下面只討論單個(gè)情況）。1) 輸入過程141) 輸入過程 顧客流的概率分布，或稱相繼顧客到達(dá)的時(shí)間間隔的分布。這是求解排隊(duì)系統(tǒng)有關(guān)運(yùn)行指標(biāo)問題時(shí)，首先需要確定的指標(biāo)。流可以理解為在一定的時(shí)間間隔內(nèi)到達(dá)k個(gè)顧客(k =1，2，)的概率是多大。顧客流的概率分布一般有定長分布、二項(xiàng)分布、泊松流(最簡單流)、愛爾朗分布等若干種。15 這指服務(wù)臺(tái)從隊(duì)列中選取顧客進(jìn)行服務(wù)的順序。一般可以分為損失制、等待制和混合制等3大類。 損失制。如果顧客到達(dá)排隊(duì)系統(tǒng)時(shí)，所有服務(wù)臺(tái)都已被占用，那么他們就自動(dòng)離開系統(tǒng)永不再來。2) 服務(wù)規(guī)則 等待制。當(dāng)顧客來到系統(tǒng)時(shí)，所有服務(wù)臺(tái)都不空，顧客加入排隊(duì)行列

6、等待服務(wù)。等待制中，服務(wù)臺(tái)在選擇顧客進(jìn)行服務(wù)時(shí)，常有如下四種規(guī)則：先到先服務(wù)。按顧客到達(dá)的先后順序?qū)︻櫩瓦M(jìn)行服務(wù)，這是最普遍的情形。后到先服務(wù)。倉庫中疊放的鋼材，后疊放上去的都先被領(lǐng)走，就屬于這種情況。2) 服務(wù)規(guī)則17隨機(jī)服務(wù)。即當(dāng)服務(wù)臺(tái)空閑時(shí)，不按照排隊(duì)序列而隨意指定某個(gè)顧客去接受服務(wù)，如電話交換臺(tái)接通呼叫電話就是一例。優(yōu)先權(quán)服務(wù)。如老人、兒童先進(jìn)車站；危重病員先就診；遇到重要數(shù)據(jù)需要處理，計(jì)算機(jī)立即中斷其他數(shù)據(jù)的處理等，均屬于此種服務(wù)規(guī)則。2) 服務(wù)規(guī)則(等待制-續(xù))18 混合制。等待制與損失制相結(jié)合的一種服務(wù)規(guī)則，一般是指允許排隊(duì)，但又不允許隊(duì)列無限長下去。具體說來，大致有三種：隊(duì)長有

7、限。當(dāng)排隊(duì)系統(tǒng)中的顧客人數(shù)K超過規(guī)定數(shù)量時(shí)，后來的顧客就自動(dòng)離去，另求服務(wù)，即系統(tǒng)的容量是有限的。2) 服務(wù)規(guī)則19等待時(shí)間有限。顧客在系統(tǒng)中的等待時(shí)間不超過某一給定的長度T，當(dāng)?shù)却龝r(shí)間超過T 時(shí)，顧客將自動(dòng)離去，并不再回來。如易損壞的電子元器件的庫存問題，超過一定存儲(chǔ)時(shí)間的元器件被自動(dòng)認(rèn)為失效。又如顧客到飯館就餐，等了一定時(shí)間后不愿再等而自動(dòng)離去另找飯店用餐。2) 服務(wù)規(guī)則（混合制-續(xù)）逗留時(shí)間有限。例如用高射炮射擊敵機(jī)，當(dāng)敵機(jī)飛越高射炮射擊有效區(qū)域的時(shí)間為 t 時(shí)，若飛機(jī)在這個(gè)時(shí)間內(nèi)未被擊落，就不可能再被擊落了。 注意：損失制和等待制可看成是混合制的特殊情形，如記 s 為系統(tǒng)中服務(wù)臺(tái)的個(gè)數(shù)

8、，則當(dāng) K = s 時(shí)，混合制即成為損失制；當(dāng)K = 時(shí)，混合制即成為等待制。2) 服務(wù)規(guī)則（混合制-續(xù)） 服務(wù)臺(tái)可從以下三方面來描述： 服務(wù)臺(tái)數(shù)量及構(gòu)成形式（圖6-26-6）單隊(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)混合式，等等。3.服務(wù)臺(tái)情況 不同的顧客與服務(wù)臺(tái)組成了各式各樣的服務(wù)系統(tǒng)。顧客為了得到某種服務(wù)而到達(dá)系統(tǒng)、若不能立即獲得服務(wù)而又允許排隊(duì)等待，則加入等待隊(duì)伍，待獲得服務(wù)后離開系統(tǒng)，見圖6-2至圖6-6。圖6-2 單服務(wù)臺(tái)排隊(duì)系統(tǒng)圖6-3 單隊(duì)列-S個(gè)服務(wù)臺(tái)并聯(lián)的排隊(duì)系統(tǒng)圖6-4 S個(gè)隊(duì)列-S個(gè)服務(wù)臺(tái)的并

9、聯(lián)排隊(duì)系統(tǒng)圖6-5 單隊(duì)-多個(gè)服務(wù)臺(tái)的串聯(lián)排隊(duì)系統(tǒng)圖6-6 多隊(duì)-多服務(wù)臺(tái)混聯(lián)、網(wǎng)絡(luò)系統(tǒng)25 服務(wù)方式。這是指在某一時(shí)刻接受服務(wù)的顧客數(shù)，它有單個(gè)服務(wù)和成批服務(wù)兩種（下面只討論單個(gè)情況）。 服務(wù)時(shí)間的分布。在多數(shù)情況下，對每一個(gè)顧客的服務(wù)時(shí)間是一隨機(jī)變量，其概率分布有定長分布、負(fù)指數(shù)分布、K級(jí)愛爾朗分布、一般分布(所有顧客的服務(wù)時(shí)間都是獨(dú)立同分布的)等等。3.服務(wù)臺(tái)情況26 為了區(qū)別各種排隊(duì)系統(tǒng)，根據(jù)輸入過程、排隊(duì)規(guī)則和服務(wù)機(jī)制的變化對排隊(duì)模型進(jìn)行描述或分類，DGKendall提出了一種目前在排隊(duì)論中被廣泛采用的“Kendall記號(hào)”，完整的表達(dá)方式通常用到6個(gè)符號(hào)并取如下固定格式：A/B/C

10、/D/E/F 各符號(hào)的位置含義如下：三、 排隊(duì)系統(tǒng)的描述符號(hào)與分類A 表示顧客相繼到達(dá)間隔時(shí)間 分布，常用下列符號(hào)：M 表示到達(dá)過程為泊松過程或負(fù)指 數(shù)分布；D 表示定長輸入；Ek 表示k階愛爾朗分布；G 表示一般相互獨(dú)立的隨機(jī)分布。Kendall記號(hào)含義Kendall記號(hào)含義B 表示服務(wù)時(shí)間分布。所用符號(hào) 與表示顧客到達(dá)間隔時(shí)間分布相同。M 表示服務(wù)過程為泊松過程或負(fù) 指數(shù)分布；D 表示定長分布；Ek 表示k階愛爾朗分布；G 表示一般相互獨(dú)立的隨機(jī)分布。C 表示服務(wù)臺(tái)(員)個(gè)數(shù)： “1”則表示單個(gè)服務(wù)臺(tái)，“s”(s1)表示多個(gè)服務(wù)臺(tái)。D 表示系統(tǒng)中顧客容量限額： 如系統(tǒng)有K個(gè)位子，則 sK0

11、 和 n0，n = 1,2,N 當(dāng) t (t 0) 時(shí)刻，記狀態(tài)隨機(jī)變量為K(t)，系統(tǒng)內(nèi)有n個(gè)顧客的概率為Pn(t)，經(jīng)過t 時(shí)間，如果滿足59 則稱這個(gè)隨機(jī)過程 K(t) ：t 0 為有限狀態(tài)S上的生滅過程。當(dāng)系統(tǒng)具有可列無限狀態(tài)集S = 0, 1, 2, 時(shí),則稱為無限狀態(tài)的生滅過程。生滅過程與狀態(tài)轉(zhuǎn)移速度圖 狀態(tài)轉(zhuǎn)移速度圖。我們把充分小的t 固定，直接用參數(shù) n 和 n 表示 nt 和nt，生滅過程可利用狀態(tài)轉(zhuǎn)移速度圖來描述“生”、“滅”導(dǎo)致狀態(tài)轉(zhuǎn)移的過程。注意，實(shí)際上，n和n的取值不需要考慮t的大小，只要保證二者的基礎(chǔ)時(shí)段一致即可（計(jì)算中考慮的是二者的比率）。生滅過程與狀態(tài)轉(zhuǎn)移速度圖

12、無限狀態(tài)生滅過程的狀態(tài)轉(zhuǎn)移速度圖如下圖：狀態(tài)轉(zhuǎn)移速度圖0n123021n-1n1n32n+1狀態(tài)轉(zhuǎn)移速度圖 根據(jù)泊松流的普通性，當(dāng)t充分小時(shí)，在 (t,t+t) 時(shí)間段內(nèi)有一個(gè)顧客到達(dá)的概率為 nt + o (t ) ，而無顧客到達(dá)的概率為1-nt + o(t )，故泊松輸入指數(shù)服務(wù)排隊(duì)系統(tǒng)的狀態(tài)轉(zhuǎn)移過程是生滅過程。因此，可以通過狀態(tài)轉(zhuǎn)移速度圖研究狀態(tài)概率之間的關(guān)系。三、 泊松輸入-指數(shù)服務(wù)排隊(duì)系統(tǒng)的求解 1) 狀態(tài)概率之間的關(guān)系: 可以通過兩種方式推導(dǎo)這種關(guān)系： 直接通過概率發(fā)生情況討論系統(tǒng)狀態(tài)概率之間的關(guān)系。 利用狀態(tài)轉(zhuǎn)移速度圖導(dǎo)出各狀態(tài)概率之間的關(guān)系。 直接通過概率發(fā)生情況討論系統(tǒng)狀態(tài)概

13、率之間的關(guān)系： n：系統(tǒng)狀態(tài)為n時(shí)，顧客進(jìn)入系統(tǒng)的平均速度 n：系統(tǒng)狀態(tài)為n時(shí)，顧客離開系統(tǒng)的平均速度 Pn(t)：t 時(shí)刻，系統(tǒng)內(nèi)有n個(gè)顧客的概率。 那么，在 (t, t+t) 有一個(gè)顧客到達(dá)概率為nt，無顧客到達(dá)的概率為 1-nt（根據(jù)普通性）。 各種方式發(fā)生概率表 Pn(t+t) = Pn(t)(1-nt)(1-nt) +Pn-1(t) n-1t(1-n-1t) +Pn+1(t)(1-n+1t) n+1t +Pn(t) ntntdPn(t)/dt = limt-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)?/p>

14、零)方式1, 2, 3, 4互不相容且完備,于是67 當(dāng)n=0時(shí)，只有方式1和3，4發(fā)生，且方式1中無離去的概率為1，則 dP0(t)/dt = -P0(t)0+P1(t) 1 我們假設(shè)系統(tǒng)是穩(wěn)態(tài)的，即與時(shí)刻無關(guān)，于是可得 d Pn(t) / d t = 0；公式推導(dǎo)如下： 根據(jù)此各事件兩兩不相容，且完備，有 pn=1，于是 可求出 pn, n=0, 1, 2, 利用狀態(tài)轉(zhuǎn)移速度圖得到概率公式由此圖易得轉(zhuǎn)入率=轉(zhuǎn)出率n=0 ，0P0=1P1n0 ，n-1Pn-1+n+1Pn+1=(n+n)Pn0n123021n-1n1n32n+171公式推導(dǎo)如下：72 根據(jù)此各事件兩兩不相容，且完備，有 pn

15、=1，于是 可求出 pn, n=0, 1, 2, 對排隊(duì)系統(tǒng)運(yùn)行情況的分析，通常是在給定輸入與服務(wù)條件下，通過求解系統(tǒng)狀態(tài)為n的概率Pn(t)，再計(jì)算其主要的運(yùn)行指標(biāo):74泊松輸入-指數(shù)服務(wù)穩(wěn)態(tài)排隊(duì)系統(tǒng)系統(tǒng)的運(yùn)行指標(biāo) 系統(tǒng)中顧客數(shù)(隊(duì)長)的期望值 排隊(duì)等待的顧客數(shù)(排隊(duì)長)的期望值為75 求出平均有效到達(dá)率e，再利用Little公式計(jì)算： 顧客在系統(tǒng)中全部時(shí)間(逗留時(shí)間)的期望值W； 顧客在系統(tǒng)中排隊(duì)等待時(shí)間的期望值Wq。76 根據(jù)已知條件繪制狀態(tài)轉(zhuǎn)移速度圖； 依據(jù)狀態(tài)轉(zhuǎn)移速度圖寫出各穩(wěn)態(tài)概率之間的關(guān)系； 求出 P0 及 Pn ；2)泊松輸入負(fù)指數(shù)分布服務(wù)的排隊(duì)系統(tǒng)的一般決策過程：772)泊松

16、輸入負(fù)指數(shù)分布服務(wù)的排隊(duì)系統(tǒng)的一般決策過程（續(xù)） 計(jì)算各項(xiàng)數(shù)量運(yùn)行指標(biāo)； 用系統(tǒng)運(yùn)行指標(biāo)構(gòu)造目標(biāo)函數(shù)，對系統(tǒng)進(jìn)行優(yōu)化。78 例6-2 某汽車加油站有兩臺(tái)加油泵為汽車加油，加油站內(nèi)最多能容納6輛汽車。已知顧客到達(dá)的時(shí)間間隔服從負(fù)指數(shù)分布，平均每小時(shí)到達(dá)18輛汽車。若加油站中已有K輛車，當(dāng)K2時(shí)，有K/6的顧客將自動(dòng)離去。加油時(shí)間服從負(fù)指數(shù)分布，平均每輛車需要5min。試求：非標(biāo)準(zhǔn)的M/M/2/N模型79 1）系統(tǒng)空閑的概率P0為多少？ 2）求系統(tǒng)滿的概率P6是多少？ 3）求系統(tǒng)服務(wù)臺(tái)不空的概率 P2+P3+P4+P5+P6=1- P0-P1 4）若服務(wù)一個(gè)顧客,加油站可以獲得利潤10元,問平均每

17、小時(shí)可獲得利潤為多少元？ 10e 5）求每小時(shí)損失掉的顧客數(shù)？ 損=-e 80 6）加油站平均有多少輛車在等待加油Lq ？ 平均有多少個(gè)車位被占L？ 7）進(jìn)入加油站的顧客需要等多長的時(shí)間才能開始加油Wq ？ 進(jìn)入加油站的顧客需要多長時(shí)間才能離去W？81穩(wěn)態(tài)概率關(guān)系：P1=/ P0=1.5P0 =(3/2)P0P2=/(2 )P1=0.751.5P0 =(9/8)P0 解：狀態(tài)轉(zhuǎn)移速度圖 以小時(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=(

18、3/6)/(2)P3=(3/8)(9/16)P0 = (27/128)P0P5=(2/6)/(2)P4=(1/4)(27/128)P0 = (27/512)P0P6=(1/6)/(2)P5=(1/8)(27/512)P0 = (27/4096)P083由 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。841) P0=0.224332) P6=0.001483) P忙=1-P0-P1=0.439184) e= 0P0+P1

19、+2(P2+P3+P4+P5+P6) = 14.578輛/h 10e= 145.78元/h運(yùn)行指標(biāo)：855)損=-e=(18-14.5782)輛/h =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.477087)Wq=Lq/e = 0.018h = 1.08min W=Wq+1/ = 0.101h = 6.08min運(yùn)行指標(biāo)（續(xù)）86 例6-3 車站候車室在某段時(shí)間旅客到達(dá)服從泊松分布，平均速度為50人/h，每位旅客在候車室內(nèi)停留的時(shí)間服從負(fù)指數(shù)分布，平均停留時(shí)間為0.5

20、h，問候車室內(nèi)平均人數(shù)為多少？ 解：把旅客停留在候車室看做服務(wù)，于是系統(tǒng)為M/M/ = 50 =1/0.5 = 287穩(wěn)態(tài)概率關(guān)系：Pn=/(n )Pn-1=1/n!(/ )nP0 記 = / = 50/2 = 25 狀態(tài)轉(zhuǎn)移速度圖:0n12n-1n2(n+1)n+13(n-1)(n+2)88因此，候車室平均人數(shù)為25人。 在排隊(duì)系統(tǒng)中，由于顧客到達(dá)分布和服務(wù)時(shí)間分布不同、服務(wù)臺(tái)數(shù)不同、隊(duì)長有限無限、顧客源有限無限等的不同組合，就會(huì)有不勝枚舉的不同排隊(duì)模型。下面分析泊松輸入-指數(shù)服務(wù)排隊(duì)系統(tǒng)模型。第三節(jié) 泊松輸入指數(shù)服務(wù)排隊(duì)模型 90 1) M/M/1/: 參數(shù) ， 穩(wěn)態(tài)概率方程： Pn=(/

21、)Pn-1=(/)nP0 令=/ 當(dāng) 1時(shí), n不收斂，故應(yīng)1, n=0即 k ) = k+1顧客逗留時(shí)間超過t的概率 P( U t ) = e-()t M/M/1/ 系統(tǒng)94 損=-e=pN , 損失率損 /。 設(shè)忙期、閑期和忙的概率、閑的概率分別為 T忙、T閑、 p忙、 p閑 ，那么可以證明 ，于是 M/M/1/ 系統(tǒng) 其他指標(biāo)95單服務(wù)臺(tái)無限源系統(tǒng) 2) M/M/1/N/ 參數(shù)、 系統(tǒng)狀態(tài)轉(zhuǎn)移速度： 穩(wěn)態(tài)概率方程：Pn=(/)Pn-1= (/)nP0 , 1n N0N-112N-2N96 由M/M/1/N/系統(tǒng)97e=npn=(1-pN)+0pN= (1-pN)(只有pN不再進(jìn)入，故N=

22、0，其余均為) e =npn=0p0+ (1-p0)（同理）W =L/e , Wq=W -(1/ ), Lq=Wqe M/M/1/N/ 系統(tǒng)98 3) 損失制M/M/1/1: 顧客到達(dá)若服務(wù)臺(tái)被占用立即離開。直接可得：P0= (1-) / (1-)2 = 1 / (1+) = /( +) P0+P1=1 P閑=P0= /( +)P損=P忙=P1= /( +)單服務(wù)臺(tái)無限源系統(tǒng) 1) M/M/c/ 系統(tǒng) 參數(shù) 、 穩(wěn)態(tài)概率應(yīng)滿足的關(guān)系： 當(dāng)nc時(shí)， pn=/(n) pn-1 當(dāng)nc時(shí)， Pn =/(c) pn-1 令=/(c) 系統(tǒng)負(fù)荷強(qiáng)度系數(shù)二、 多服務(wù)臺(tái)無限源系統(tǒng)012nc2cc-1ccc+

23、13(c-1)cc100 此系統(tǒng)中，當(dāng)=/(c)1時(shí)，不收斂，設(shè)1, M/M/c/ 系統(tǒng)101 根據(jù) ，可得到 Lq = ccc+1p0 / c! (1-)2利用 Little 公式得到 Wq = Lq / , W = Wq+ 1/ , L=W = Lq+/ M/M/c/ 系統(tǒng)102 例6-4 某火車站售票處有三個(gè)窗口，同時(shí)售各車次的車票。顧客到達(dá)服從泊松分布，平均每分鐘到達(dá) =0.9人，服務(wù)時(shí)間服從負(fù)指數(shù)分布，平均服務(wù)率每小時(shí) =24人，分兩種情況討論：1. 顧客排成一隊(duì)，依次購票；2.顧客在每個(gè)窗口排一隊(duì)，不準(zhǔn)串隊(duì)。 求: 1）售票處空閑的概率。 2）平均等待時(shí)間和逗留時(shí)間。 3）隊(duì)長和隊(duì)

24、列長。單位一致： =0.4人/min，= /(3)=0.75穩(wěn)態(tài)概率：031232343 解：情況1. M/M/3/104解：情況1. M/M/3/ 續(xù)由得105解：情況1. M/M/3/ 續(xù)記 , 先求積分，再求微分106解：情況1. M/M/3/ 續(xù)售票處的空閑的概率為0.0748平均等待時(shí)間 Wq=1.893min， 平均逗留時(shí)間 W=4.393min隊(duì)長 L =3.954人) Lq=1.704人有1個(gè)窗口空閑 0.18934有2個(gè)窗口空閑 0.1683107參數(shù) =0.3 =0.4 =/ = 0.75利用公式，1個(gè)服務(wù)臺(tái)有空 p0 = 1- = 0.25 2個(gè)、3個(gè)服務(wù)臺(tái)有空: p02

25、=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)108故售票處空閑的概率為 0.0156平均等待時(shí)間 Wq=7.5min 平均逗留時(shí)間 W=10min隊(duì)長 L=3 三個(gè)隊(duì) 共3+3+3=9隊(duì)列長 Lq=2.25 共6.75人顯然，排一隊(duì)共享3個(gè)服務(wù)臺(tái)效率高。解：情況2. M/M/1/ 續(xù)有1個(gè)窗口空閑 0.25有2個(gè)窗口空閑 0.06251092) M/M/c/N/穩(wěn)態(tài)概率應(yīng)滿足的關(guān)系：當(dāng)nc時(shí)，當(dāng)nc時(shí)，多服務(wù)臺(tái)無限源系統(tǒng)0

26、N-112N-2c2cNcc-1ccc+1(c-1)cc110令=/(c)，根據(jù) pn=1，可得M/M/c/N/ 系統(tǒng)111運(yùn)行指標(biāo)：M/M/c/N/ 系統(tǒng)112同單服務(wù)臺(tái)情況的分析，e=(1- pN)利用 Little 公式，可求得 Wq=Lq /e W=Wq+1/ L=We=Lq+e/M/M/c/N/ 系統(tǒng)113此即M/M/c/N中 N=c 的情形 損=-e=pc ，損失率=損/= pc 3) M/M/c/c/損失制系統(tǒng)114三、 有限源排隊(duì)系統(tǒng) 1) M/M/1/m/m系統(tǒng) 顧客源是m個(gè)，那么系統(tǒng)容量實(shí)質(zhì)上最多有m個(gè)足夠。0m-112m-2m(m-1)2m(m-2)3顧客源中剩余的顧客數(shù)

27、乘以每個(gè)顧客到達(dá)的概率115M/M/1/m/m系統(tǒng)穩(wěn)態(tài)概率方程：由概率性質(zhì)，得M/M/1/m/m系統(tǒng)根據(jù)e=(m-L)=e=(1-p0), 得 L=m- /(1-p0)再利用Little公式，可求得 W=L/e Wq=W-1/ Lq=Wqe1172) M/M/c/m/m系統(tǒng)0m-112m-2m(m-1)2c2cmcc-1(m(c-1)c穩(wěn)態(tài)概率方程118代入 pn=1 得同前，M/M/c/m/m系統(tǒng)119進(jìn)一步可得 可求出L和e，再利用Little公式，得 M/M/c/m/m系統(tǒng)120第四節(jié) 其他模型選介一、 M/G/1排隊(duì)系統(tǒng) 設(shè)顧客平均到達(dá)率為，服務(wù)時(shí)間為隨機(jī)變量V，且E(V) = 1/

28、，D(V) = 2 。那么，服務(wù)強(qiáng)度 ，當(dāng) 1時(shí)， p0 = 1 - 根據(jù)波拉切克-欣欽（Pollaczek-Khinchine）公式可導(dǎo)出 其他量的計(jì)算同前。121其他模型選介二、 M/D/1排隊(duì)系統(tǒng) 設(shè)顧客平均到達(dá)率為，服務(wù)時(shí)間為常數(shù)v，則 E( v ) = v = 1/ , D( v ) = 0那么，服務(wù)強(qiáng)度 ，當(dāng) 1時(shí) p0 = 1 - 根據(jù)上一模型的公式可直接得到 其他量的計(jì)算同前。122第五節(jié) 排隊(duì)系統(tǒng)的優(yōu)化目標(biāo)與最優(yōu)化問題 從經(jīng)濟(jì)角度考慮，排隊(duì)系統(tǒng)的費(fèi)用應(yīng)該包含以下兩個(gè)方面：一個(gè)是服務(wù)費(fèi)用，它是服務(wù)水平的遞增函數(shù)；另一個(gè)是顧客等待的機(jī)會(huì)損失(費(fèi)用)，它是服務(wù)水平的遞減函數(shù)。兩者的

29、總和呈一條U形曲線。123排隊(duì)系統(tǒng)優(yōu)化問題 系統(tǒng)最優(yōu)化的目標(biāo)就是尋求上述合成費(fèi)用曲線的最小點(diǎn)。 排隊(duì)系統(tǒng)的最優(yōu)化問題通常分為兩類：系統(tǒng)的靜態(tài)最優(yōu)設(shè)計(jì)，目的在于使設(shè)備達(dá)到最大效益；系統(tǒng)動(dòng)態(tài)最優(yōu)運(yùn)營，是指一個(gè)給定排隊(duì)系統(tǒng)，如何運(yùn)營可使某個(gè)目標(biāo)函數(shù)得到最優(yōu)。124排隊(duì)系統(tǒng)常見的優(yōu)化問題 1)確定最優(yōu)服務(wù)率*； 2)確定最佳服務(wù)臺(tái)數(shù)量c*； 3)選擇最為合適的服務(wù)規(guī)則； 4)或是確定上述幾個(gè)量的最優(yōu)組合。 研究排隊(duì)系統(tǒng)的根本目的在于以最少的設(shè)備得到最大的效益。125本節(jié)討論的排隊(duì)系統(tǒng)優(yōu)化問題 本章只討論系統(tǒng)靜態(tài)的最優(yōu)設(shè)計(jì)問題。這類問題一般可以借助于前面所得到的一些表達(dá)式來解決。 本節(jié)就 、c 這兩個(gè)決

30、策變量的分別單獨(dú)優(yōu)化，介紹兩個(gè)較簡單的模型。一、 M/M/1/系統(tǒng)的最優(yōu)平均服務(wù)率* 設(shè)：c1 當(dāng) =1時(shí)服務(wù)系統(tǒng)單位時(shí)間的平均費(fèi)cw每個(gè)顧客在系統(tǒng)逗留單位時(shí)間的平均機(jī)會(huì)損失； y 系統(tǒng)單位時(shí)間的平均總費(fèi)用。其中 c1、cw 均為可知，則目標(biāo)函數(shù)為 求解過程將L= ( -)，代入上式，得 y 是關(guān)于決策變量 的一元非線性函數(shù),由一階條件解得駐點(diǎn)128求解過程（續(xù)） 根號(hào)前取正號(hào)是為了保證 ，這樣，系統(tǒng)才能達(dá)到穩(wěn)態(tài)。又由二階條件 ()可知求出的*為(,)上的全局唯一最小點(diǎn)。將*代入y中，可得最小總平均費(fèi)用129求解過程（續(xù)） 另外，若設(shè)cw為平均每個(gè)顧客在隊(duì)列中等待單位時(shí)間的損失，則需用 取代前式中的L，這時(shí)類似可得一階條件： 這一般采用數(shù)值法(如牛頓法)確定其根*。130 例6-5 興建一座港口碼頭，只有一個(gè)裝卸船只的泊位。要求設(shè)計(jì)裝卸能力，單位為（只/日）船數(shù)。已知：單位裝卸能力的平均生產(chǎn)費(fèi)用a=2千元，船只逗留每日損失b=1.5千元。船只到達(dá)服從泊松分布，平均速率=3只/日。船只裝卸時(shí)間服從負(fù)指數(shù)分布。目標(biāo)是每日總支出最少。 解 =3 ， 待定 模型 M/M/1/ 隊(duì)長 Ls =/(-)總費(fèi)用 c =a +bL=a +b/(-) 求導(dǎo) dc/d =a+(-b)