系統(tǒng)工程原理12-9夏昊翔

1、系統(tǒng)工程原理 (2060120023) 3-14周：周四 5-8節(jié)，研教樓-201室,榮莉莉 、 夏昊翔大連理工大學(xué) 管理與經(jīng)濟(jì)學(xué)部 管理科學(xué)與工程學(xué)院 系統(tǒng)工程研究所夏昊翔 hxxia@dlut.edu.cn84706689(o),第11章 隨機(jī)服務(wù)系統(tǒng),第1節(jié) 隨機(jī)服務(wù)系統(tǒng)概念隨機(jī)服務(wù)系統(tǒng)是一類研究得較多的離散事件動態(tài)系統(tǒng)?，F(xiàn)實(shí)中很多問題可以使用隨機(jī)服務(wù)系統(tǒng)加以描述和分析。 火車站買票，顧

2、客-售票員； 船靠碼頭卸貨，船-碼頭卸船機(jī)； 計算機(jī)任務(wù)處理，任務(wù)-計算機(jī)；等等。這類系統(tǒng)的特點(diǎn)：隨機(jī)性：顧客到來的時間與服務(wù)者提供服務(wù)的時間都是隨機(jī)的；排隊：顧客排隊等待服務(wù)；（因此，隨機(jī)服務(wù)系統(tǒng)理論也稱為排隊論）,排隊論（queuing),也稱隨機(jī)服務(wù)系統(tǒng)理論，是運(yùn)籌學(xué)的一個主要分支。 1909年，丹麥哥本哈根電子公司電話工程師A. K. Erlang的開創(chuàng)性論文“概率論和電話通訊理論”標(biāo)志此理論的誕生。 排隊論的

3、發(fā)展最早是與電話、通信中的問題相聯(lián)系的，并到現(xiàn)在是排隊論的傳統(tǒng)的應(yīng)用領(lǐng)域。 近年來在計算機(jī)通訊網(wǎng)絡(luò)系統(tǒng)、交通運(yùn)輸、醫(yī)療衛(wèi)生系統(tǒng)、庫存管理、作戰(zhàn)指揮等各領(lǐng)域中均得到應(yīng)用。,排隊是指在服務(wù)機(jī)構(gòu)處要求服務(wù)對象的一個等待隊列。排隊系統(tǒng)是指一個具有排隊等待現(xiàn)象的服務(wù)系統(tǒng)。排隊論是指定量的研究排隊問題，尋找系統(tǒng)內(nèi)在規(guī)律，尋找供求關(guān)系平衡的最優(yōu)方案。 現(xiàn)實(shí)世界中排隊的現(xiàn)象比比皆是，但有如下共同特征: (1)有請求服務(wù)的人或物，如候診

4、的病人，請求著陸的飛機(jī)等，我們將此稱為“顧客”。 (2)有為顧客提供服務(wù)的人或物，如醫(yī)生、飛機(jī)跑道等，我們稱為“服務(wù)員”。由顧客和服務(wù)員就組成服務(wù)系統(tǒng)。 (3)顧客隨機(jī)地一個一個(或者一批一批)來到服務(wù)系統(tǒng)，每位顧客需要服務(wù)的時間不一定確定的，服務(wù)過程的這種隨機(jī)性造成某個階段顧客排長隊，而某些時間服務(wù)員又空閑無事。,各種形式的排隊系統(tǒng),,,,各種形式的排隊系統(tǒng),,,,各種形式的排隊系統(tǒng),,,,各種形式的排隊系統(tǒng),,,,各

5、種形式的排隊系統(tǒng),,,,隨機(jī)服務(wù)系統(tǒng)研究目的與方法,面對擁擠現(xiàn)象，人們通常的做法是增加服務(wù)設(shè)施，但是增加的數(shù)量越多，人力、物力的支出就越大，甚至?xí)霈F(xiàn)空閑浪費(fèi)，如果服務(wù)設(shè)施太少，顧客排隊等待的時間就會很長，這樣對顧客會帶來不良影響。如何做到既保證一定的服務(wù)質(zhì)量指標(biāo)，又使服務(wù)設(shè)施費(fèi)用經(jīng)濟(jì)合理，恰當(dāng)?shù)亟鉀Q顧客排隊時間與服務(wù)設(shè)施費(fèi)用大小這對矛盾，就是隨機(jī)服務(wù)系統(tǒng)理論——排隊論所要研究解決的問題。因此，研究隨機(jī)服務(wù)系統(tǒng)的基本目的在于合理設(shè)計

6、實(shí)際的隨機(jī)服務(wù)系統(tǒng)，在保證服務(wù)質(zhì)量的同時使服務(wù)系統(tǒng)的開支最小。由于隨機(jī)因素在服務(wù)系統(tǒng)中起著根本性的影響，所以研究隨機(jī)服務(wù)系統(tǒng)時，需要采用研究隨機(jī)現(xiàn)象規(guī)律性的概率論的方法。,隨機(jī)服務(wù)系統(tǒng)研究的基本問題 1.排隊系統(tǒng)的統(tǒng)計推斷:即通過對排隊系統(tǒng)主要參數(shù)的統(tǒng)計推斷和對排隊系統(tǒng)的結(jié)構(gòu)分析，判斷一個給定的排隊系統(tǒng)符合于哪種模型，以便根據(jù)排隊理論進(jìn)行研究。 2.系統(tǒng)性態(tài)問題:即研究各種排隊系統(tǒng)的概率規(guī)律性，主要研究隊長分布、等待

7、時間分布和忙期分布等統(tǒng)計指標(biāo),包括了瞬態(tài)和穩(wěn)態(tài)兩種情形。 3.最優(yōu)化問題：即包括最優(yōu)設(shè)計(靜態(tài)優(yōu)化)，最優(yōu)運(yùn)營（動態(tài)優(yōu)化）。,排隊問題求解(主要指性態(tài)問題),求解一般排隊系統(tǒng)問題的目的主要是通過研究排隊系統(tǒng)運(yùn)行的效率指標(biāo)，估計服務(wù)質(zhì)量，確定系統(tǒng)的合理結(jié)構(gòu)和系統(tǒng)參數(shù)的合理值，以便實(shí)現(xiàn)對現(xiàn)有系統(tǒng)合理改進(jìn)和對新建系統(tǒng)的最優(yōu)設(shè)計等。 排隊問題的一般步驟： 1. 確定或擬合排隊系統(tǒng)顧客到達(dá)的時間間隔分布和服務(wù)時間分布(可實(shí)測

8、)。 2. 研究系統(tǒng)狀態(tài)的概率。系統(tǒng)狀態(tài)是指系統(tǒng)中顧客數(shù)。狀態(tài)概率用Pn(t)表示,即在t時刻系統(tǒng)中有n個顧客的概率，也稱瞬態(tài)概率。,求解狀態(tài)概率Pn(t)方法是建立含Pn(t)的微分差分方程，通過求解微分差分方程得到系統(tǒng)瞬態(tài)解，由于瞬態(tài)解一般求出確定值比較困難，即便求得一般也很難使用。因此我們常常使用它的極限(如果存在的話)：,穩(wěn)態(tài)的物理意義見右圖，系統(tǒng)的穩(wěn)態(tài)一般很快都能達(dá)到，但實(shí)際中達(dá)不到穩(wěn)態(tài)的現(xiàn)象也存在。值得注意的是求穩(wěn)態(tài)

9、概率Pn并不一定求t→∞的極限,而只需求Pn’(t)=0 即可。,稱為穩(wěn)態(tài)(steady state)解，或稱統(tǒng)計平衡狀態(tài) (Statistical Equilibrium State)的解。,第2節(jié) 隨機(jī)服務(wù)系統(tǒng)特征和基本排隊模型,共同特征： (1)請求服務(wù)的人或者物——顧客； (2)有為顧客服務(wù)的人或者物，即服務(wù)員或服務(wù)臺； (3)顧客到達(dá)系統(tǒng)的時刻是隨機(jī)的，為每一位顧客提供服務(wù)的時間是隨機(jī)的，因而整個排隊系統(tǒng)的狀態(tài)也

10、是隨機(jī)的。,每個顧客由顧客源按一定方式到達(dá)服務(wù)系統(tǒng)，首先加入隊列排隊等待接受服務(wù)，然后服務(wù)臺按一定規(guī)則從隊列中選擇顧客進(jìn)行服務(wù)，獲得服務(wù)的顧客立即離開。,基本排隊過程,隨機(jī)服務(wù)系統(tǒng)的基本組成隨機(jī)服務(wù)系統(tǒng)一般有三個基本組成部分：1.輸入過程；2.排隊規(guī)則；3.服務(wù)機(jī)構(gòu)。輸入過程 (顧客按照怎樣的規(guī)律到達(dá));排隊規(guī)則 (顧客按照一定規(guī)則排隊等待服務(wù));服務(wù)機(jī)構(gòu) (服務(wù)機(jī)構(gòu)的設(shè)置,服務(wù)臺的數(shù)量,服務(wù)的方式,服務(wù)時間分布等),,,,,,

11、排隊長度,,,,服務(wù)者1,服務(wù)者2,服務(wù)者n,顧客到達(dá),幾個關(guān)鍵時間指標(biāo)：1）顧客到來的時間間隔 2）排隊時間 3）系統(tǒng)服務(wù)時間,隨機(jī)服務(wù)系統(tǒng)的性質(zhì)由三個部分決定：顧客到來的規(guī)律、排隊規(guī)律、服務(wù)機(jī)理。,1．輸入過程,這是指要求服務(wù)的顧客是按怎樣的規(guī)律到達(dá)排隊系統(tǒng)的過程，有時也把它稱為顧客流。一般可以從3個方

12、面來描述—個輸入過程。 (1)顧客總體數(shù)，又稱顧客源、輸入源。這是指顧客的來源。顧客源可以是有限的，也可以是無限的。 (2)顧客到達(dá)方式。這是描述顧客是怎樣來到系統(tǒng)的，是單個到達(dá)，還是成批到達(dá)。 (3)顧客流的概率分布，或稱相繼顧客到達(dá)的時間間隔的分布。這是求解排隊系統(tǒng)有關(guān)運(yùn)行指標(biāo)問題時，首先需要確定的指標(biāo)。顧客流的概率分布一般有定長分布、二項(xiàng)分布、泊松流(最簡單流)、愛爾朗分布等若干種。,輸入過程,隨機(jī)服務(wù)系統(tǒng)的輸入就是顧

13、客的到來，由于到來規(guī)律的不同，所以有各種類型的輸入過程。一般用兩個顧客到達(dá)的時間間隔τ來描述系統(tǒng)的輸入特點(diǎn)。主要輸入過程類型：（1）定長輸入顧客有規(guī)律地等間隔到達(dá)，假如每隔時間α到一個，這時候相繼兩個顧客到達(dá)的相隔時間τ的分布函數(shù)為：,,例如：生產(chǎn)線上的產(chǎn)品從傳送帶過來進(jìn)入包裝箱的情況,（2）泊松輸入,前面講到的定長輸入過程是一個確定性過程，更多情況下輸入過程是隨機(jī)的。τ是隨機(jī)變量。最常見的顧客到來規(guī)律按照泊松分布到來，稱這樣的輸

14、入過程為泊松輸入。泊松輸入滿足以下條件：1）平穩(wěn)性：在每個時間段[a, a+t]內(nèi)k個顧客到達(dá)的概率與a無關(guān)，只與t, k有關(guān)；2）無后效性：不相交的時間段到達(dá)的顧客數(shù)相互獨(dú)立；3）普通性——在把時間段分的足夠小的話，每個時間段最多到達(dá)一個顧客；4）有限性：任意有限區(qū)間到達(dá)有限個顧客的概率為1。,（k =0，1，2，…）,在泊松輸入下，在時間長度為t的時間段里面到達(dá)k個顧客的概率被定義為泊松分布：,其分布函數(shù)為負(fù)指數(shù)分布：,,,

15、這種輸入是應(yīng)用最廣泛的，而且是最容易處理的。,0-t這個時間段內(nèi)顧客到達(dá)的平均數(shù)：,因此，單位時間里面顧客到達(dá)的平均數(shù)為λ，稱為平均到達(dá)率。平均到達(dá)的時間間隔為：,,其它輸入,（3）愛爾朗（Erlang）輸入它的到達(dá)間隔相互獨(dú)立，具有相同的分布 a (t)=λ(λt)k-1e-λt/(k-1)!, t≥0（4）一般獨(dú)立輸入到達(dá)間隔相互獨(dú)立、相同分布，其分布函數(shù)A(t)可以是任意一個函數(shù)，

16、上面的幾種輸入都可看作是它的特例。（5）成批到達(dá)的輸入每次到來的不一定是一個顧客，而可能是一批顧客，數(shù)目n是一個隨機(jī)變量，分布為 p{n=k}=ak, k=0,1,2,……到達(dá)時間間隔則可能是上述幾類輸入中的一種。,2．排隊規(guī)則,這是指服務(wù)臺從隊列中選取顧客進(jìn)行服務(wù)的順序。一般可以分為損失制、等待制和混合制等3大類。 (1)損失制 這是指如果顧客到達(dá)排隊系統(tǒng)時，所有服務(wù)臺都被先到的顧客占用，那么他

17、們就自動離開系統(tǒng)永不再來。典型例子如電話服務(wù)。,(2)等待制 這是指當(dāng)顧客來到系統(tǒng)時，所有服務(wù)臺都不空，顧客加入排隊行列等待服務(wù)。等待制中，服務(wù)臺在選擇顧客進(jìn)行服務(wù)時常有如下四種規(guī)則： 1)先到先服務(wù)。按顧客到達(dá)的先后順序?qū)︻櫩瓦M(jìn)行服務(wù)。最通常的情況。 2)后到先服務(wù)。堆棧 3)隨機(jī)服務(wù)。即當(dāng)服務(wù)臺空閑時，不按照排隊序列而隨意指定某個顧客接受服務(wù)。每一顧客被接待的概率相同 4)優(yōu)先權(quán)服務(wù)。分輕重緩急，如加急電報

18、 5）多個服務(wù)臺情況：可派成幾隊，或一隊。,,(3)混合制 這是等待制與損失制相結(jié)合的一種服務(wù)規(guī)則，一般是指允許排隊，但又不允許隊列無限長下去。具體說來，大致有三種： 1)隊長有限。當(dāng)排隊等待服務(wù)的顧客人數(shù)超過規(guī)定數(shù)量時，后來的顧客就自動離去，另求服務(wù)，即系統(tǒng)的等待空間是有限的。 2)等待時間有限。即顧客在系統(tǒng)中的等待時間不超過某一給定的長度T，當(dāng)?shù)却龝r間超過T時，顧客將自動離去，并不再回來。 3)逗留時間(等待時間

19、與服務(wù)時間之和)有限。,3．服務(wù)機(jī)理,服務(wù)機(jī)理是隨機(jī)服務(wù)系統(tǒng)的第三個要素，包括：服務(wù)者的個數(shù)、單個服務(wù)還是成批服務(wù)、以及服務(wù)的時間分布(1)服務(wù)臺數(shù)量及構(gòu)成形式。從數(shù)量上說，服務(wù)臺有單服務(wù)臺和多服務(wù)臺之分。從構(gòu)成形式上看，服務(wù)臺有：①單隊—－單服務(wù)臺式；②單隊-－多服務(wù)臺并聯(lián)式；③多隊—－多服務(wù)臺并聯(lián)式；④單隊—－多服務(wù)臺串聯(lián)式；⑤單隊—－多服務(wù)臺并串聯(lián)混合式，以及多隊多服務(wù)臺并串聯(lián)混合式等等。,,,(2)服務(wù)方式。這

20、是指在某一時刻接受服務(wù)的顧客數(shù)，它有單個服務(wù)和成批服務(wù)兩種。(3)服務(wù)時間的分布。服務(wù)時間分為確定型和隨機(jī)型。在多數(shù)情況下，對每一個顧客的服務(wù)時間是一隨機(jī)變量。1 定長分布：每一個顧客服務(wù)時間都是常數(shù)。類似于輸入過程的定長分布情況。2 負(fù)指數(shù)分布：各顧客的服務(wù)時間相互獨(dú)立，具有相同分布。,同樣類似于泊松輸入的分析，平均服務(wù)時間為1/μ。,3 愛爾朗分布：,,平均服務(wù)時間為1/μ。當(dāng)k=1時就轉(zhuǎn)化為負(fù)指數(shù)分布， k→∞

21、時就得到長度為1/μ的定長分布。,4 一般服務(wù)分布：服務(wù)時間相互獨(dú)立，分布相同，分布函數(shù)可能是任意函數(shù)。5 多服務(wù)臺情況。6 服務(wù)時間依賴于隊長的情況。,第3節(jié) 隨機(jī)服務(wù)系統(tǒng)的一般描述,從一般意義上講，隨機(jī)服務(wù)系統(tǒng)可以采用如下符號表示： ①/②/③/④/⑤/⑥ （A/B/C/K/m/Z) ①代表輸入過程（時間分布）、 ②代表服務(wù)時間分布、 ③是服務(wù)者數(shù)目、 ④是系統(tǒng)中允許的最大顧客數(shù)、 ⑤是能夠到來的顧客數(shù)、 ⑥是排隊規(guī)

22、則。 各符號的具體內(nèi)涵： ①——表示顧客相繼到達(dá)間隔時間分布，常用下列符號： M——表示到達(dá)的過程為泊松過程或負(fù)指數(shù)分布； D——表示定長輸入； EK——表示K階愛爾朗分布； G——表示一般相互獨(dú)立的隨機(jī)分布。,②——表示服務(wù)時間分布，所用符號與表示顧客到達(dá)間隔時間分布相同。③——表示服務(wù)臺(員)個數(shù)：“1”表示單個服務(wù)臺，“s”(s>1)表示多個服務(wù)臺。

23、 ④——表示系統(tǒng)中顧客容量限額，或稱等待空間容量。如系統(tǒng)有K個等待位子，則，0<K<∞，當(dāng)K=0時，說明系統(tǒng)不允許等待，即為損失制。K=∞時為等待制系統(tǒng)，此時一般∞省略不寫。K為有限整數(shù)時，表示為混合制系統(tǒng)。⑤——表示顧客源限額，分有限與無限兩種，∞表示顧客源無限，一般∞也可省略不寫。⑥——表示服務(wù)規(guī)則，常用下列符號FCFS：表示先到先服務(wù)的排隊規(guī)則；LCFS：表示后到先服務(wù)的排隊規(guī)則；PR：表示優(yōu)先權(quán)服務(wù)的排

24、隊規(guī)則。,舉例：,某排隊問題為M／M／S／∞／∞/FCFS，則表示顧客到達(dá)間隔時間為負(fù)指數(shù)分布(泊松流)；服務(wù)時間為負(fù)指數(shù)分布；有s(s>1)個服務(wù)臺；系統(tǒng)等待空間容量無限(等待制)；顧客源無限；采用先到先服務(wù)規(guī)則。一般情況下不限制顧客數(shù)，采用先到先服務(wù)排隊規(guī)則，這樣系統(tǒng)可簡寫為前三項(xiàng)①/②/③ （A/B/C）。M/M/s即Poisson輸入、負(fù)指數(shù)服務(wù)時間分布、S個服務(wù)臺的等待制排隊模型。 M/M/1表示指數(shù)輸入和指數(shù)服務(wù)

25、分布、一個服務(wù)者。M/G/n表示指數(shù)輸入、一般服務(wù)分布、n個服務(wù)者。M/G/1即Poisson輸入，一般服務(wù)時間分布，單個服務(wù)臺的等待制排隊模型。,其他模型,M/M/c/K/K顧客來源是有限的服務(wù)系統(tǒng). 例如： 一個飯店有 X 張桌子和 Y個服務(wù)生服務(wù)來源有限的顧客.M/D/1服務(wù)時間不變的服務(wù)系統(tǒng).D/M/1確定性到達(dá)模式, 及指數(shù)分布服務(wù)時間. 例如：醫(yī)生赴約治病的時間表.M/E k/1服務(wù)服從 Erlang 分布

26、. 例如：用相同平均時間去完成一些程序。,隨機(jī)服務(wù)系統(tǒng)的主要數(shù)量指標(biāo),描述一個排隊系統(tǒng)運(yùn)行狀況的主要數(shù)量指標(biāo)有：1．隊長和排隊長(隊列長)隊長是指系統(tǒng)中的顧客數(shù)(排隊等待的顧客數(shù)與正在接受服務(wù)的顧客數(shù)之和)。排隊長是指系統(tǒng)中正在排隊等待服務(wù)的顧客數(shù)。隊長和排隊長一般都是隨機(jī)變量。這是雙方都關(guān)心的，也是系統(tǒng)設(shè)計者關(guān)心的。,2．等待時間和逗留時間從顧客到達(dá)時刻起到他開始接受服務(wù)止這段時間稱為等待時間。等待時間是個隨機(jī)變量。從顧客

27、到達(dá)時刻起到他接受服務(wù)完成止這段時間稱為逗留時間，也是隨機(jī)變量。這是顧客最關(guān)心的，希望越短越好。3. 忙期和閑期 忙期是指從顧客到達(dá)空閑著的服務(wù)機(jī)構(gòu)起，到服務(wù)機(jī)構(gòu)再次成為空閑止的這段時間，即服務(wù)機(jī)構(gòu)連續(xù)忙的時間。這是個隨機(jī)變量，是服務(wù)員最為關(guān)心的指標(biāo)，因?yàn)樗P(guān)系到服務(wù)員的服務(wù)強(qiáng)度。與忙期相對的是閑期,即服務(wù)機(jī)構(gòu)連續(xù)保持空閑的時間。在排隊系統(tǒng)中，忙期和閑期總是交替出現(xiàn)的。這些量都是隨機(jī)變量，常常要求取它們的分布及平均值。,4

28、．?dāng)?shù)量指標(biāo)的常用記號 (1)主要數(shù)量指標(biāo)L——平均隊長，即穩(wěn)態(tài)系統(tǒng)任一時刻的所有顧客數(shù) 的期望值；Lq——平均等待隊長，即穩(wěn)態(tài)系統(tǒng)任一時刻等待服務(wù)的顧客數(shù)的期望值；W——平均逗留時間，即(在任意時刻)進(jìn)入穩(wěn)態(tài)系統(tǒng)的顧客逗留時間的期望值；Wq——平均等待時間，即(在任意時刻)進(jìn)入穩(wěn)態(tài)系統(tǒng)的顧客等待時間的期望值。,(2)其他常用數(shù)量指標(biāo)s——系統(tǒng)中并聯(lián)服務(wù)臺的數(shù)目；λ——平均到達(dá)率；1／λ——平均到達(dá)間隔；μ——平

29、均服務(wù)率；1/μ——平均服務(wù)時間；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)中的等待時間；,系統(tǒng)狀態(tài) =排隊系統(tǒng)顧客的數(shù)量。 N(t) =在時間 t 排隊系統(tǒng)中顧客的數(shù)量。隊列長度 =等待服務(wù)的顧客的數(shù)量。 Pn(t) =在時間t,排隊系統(tǒng)中恰好有n個顧客的概率。s =服務(wù)臺的數(shù)目。,,,,ρ——服務(wù)強(qiáng)度，即每個

30、服務(wù)臺單位時間內(nèi)的平均服務(wù)時間，—般有ρ=λ／(sμ)。這是衡量排隊系統(tǒng)繁忙程度的重要尺度。當(dāng)ρ趨近于0時，表明對期望服務(wù)的數(shù)量來說，服務(wù)能力相對地說是很大的，這時，等待時間一定很短，服務(wù)臺有大量的空閑時間。如服務(wù)強(qiáng)度ρ趨近于1，那么服務(wù)臺空閑時間較少而顧客等待時間較多。一般都假定平均服務(wù)率μ大于平均到達(dá)率λ，即λ/μ<1,否則排隊的人數(shù)會越來越多。,排隊系統(tǒng)運(yùn)行情況的分析,排隊系統(tǒng)運(yùn)行情況的分析，就是在給定輸入與服務(wù)條件下

31、，通過求解系統(tǒng)狀態(tài)為n(有n個顧客)的概率Pn，再進(jìn)行計算其主要的運(yùn)行指標(biāo)： ①系統(tǒng)中顧客數(shù)(隊長)的期望值L； ②排隊等待的顧客數(shù)(排隊長)的期望值Lq； ③顧客在系統(tǒng)中全部時間(逗留時間)的期望值W； ④顧客排隊等待時間的期望值Wq。,第4節(jié) 分析隨機(jī)服務(wù)系統(tǒng)的數(shù)學(xué)工具——隨機(jī)過程理論,一般的隨機(jī)過程在數(shù)學(xué)上采用隨機(jī)過程理論進(jìn)行研究；這里討論的隨機(jī)服務(wù)系統(tǒng)通常表現(xiàn)為有限記憶的隨機(jī)過程，可以采用隨機(jī)過程理論中的馬爾科夫過程進(jìn)行

32、分析。,隨機(jī)過程,假設(shè)一個系統(tǒng)的狀態(tài)變量是一個隨機(jī)變量。該隨機(jī)變量隨時間演化的過程是一個隨機(jī)過程。,對,稱隨機(jī)變量族｛X(t)}為隨機(jī)過程,若T 是連續(xù)區(qū)間，為連續(xù)過程；若T 是離散區(qū)間，則為離散過程。在離散情況下，隨機(jī)過程表現(xiàn)為一個隨機(jī)序列：｛x(t1),x(t2),x(t3),…},隨機(jī)過程,考慮離散隨機(jī)過程｛x(t1),x(t2),x(t3),…}一個重要研究課題是在一系列相鄰時間點(diǎn)之間狀態(tài)的變化過程和規(guī)律。x(t1)?x

33、(t2)?x (t3)?x(t4)?…,需要用多個時間聯(lián)合分布函數(shù)加以描述f(x1,t1;x2,t2;x3,t3…)獨(dú)立隨機(jī)過程：當(dāng)后一個時間點(diǎn)發(fā)生的隨機(jī)事件與之前的所有時間點(diǎn)的事件都無關(guān)的情況下，這個隨機(jī)過程為獨(dú)立事件隨機(jī)過程，或“白噪聲過程”（White Noise Process）。在這種情況下，n時間聯(lián)合分布可以分解為單時間分布函數(shù)的乘積。,馬爾科夫過程,稱可以用雙時間聯(lián)合分布完全表示的隨機(jī)過程為馬爾科夫過程（Markov

34、Process) ，即：,馬爾可夫過程是一種有限記憶隨機(jī)系統(tǒng)：只對最近的歷史數(shù)據(jù)有記憶,稱之為躍遷概率,隨機(jī)服務(wù)系統(tǒng)相關(guān)的隨機(jī)過程通?？梢允褂民R爾科夫過程進(jìn)行描述。,一類特殊的馬爾可夫過程。當(dāng)顧客到達(dá)時間間隔為負(fù)指數(shù)分布(即輸入過程具有Poisson特征，N(t)服從Poisson分布)，服務(wù)時間為負(fù)指數(shù)分布，則系統(tǒng)的排隊過程是Markov過程，而且它具有一類特殊Markov過程的特征，通常稱這類隨機(jī)過程為生滅過程。生滅過程的直觀

35、描述：,生滅過程,1.生滅過程的定義 設(shè)有一個系統(tǒng)，具有有限個狀態(tài)，其狀態(tài)集s={0，1，2…k}或有可數(shù)個狀態(tài)，狀態(tài)集s={0，1，2…}，令X(t)為系統(tǒng)在時刻t所處的狀態(tài)，若在某一時刻t系統(tǒng)的狀態(tài)數(shù)為n，如果對△t>0有： (1)到達(dá)(生)：在(t，t+△t)內(nèi)系統(tǒng)出現(xiàn)一個新的到達(dá)的概率為,的常數(shù)；沒有發(fā)生新的到達(dá)的概率為,；出現(xiàn)多于一個以上的新的到達(dá)概率為0(△t) 。,的常數(shù)，沒有消失的概率為,消失多

36、于一個以上的概率為0(△t)。則稱系統(tǒng)狀態(tài)隨時間而變化的過程X(t)為一個生滅過程。,(2)消失(滅)：在(t，t+△t)內(nèi)，系統(tǒng)消失一個的概率為,2.生滅過程微分差分方程組 設(shè),表示系統(tǒng)在時刻t的狀態(tài)X(t)=n的概率即,,，,狀態(tài)為n的概率近似于以下四個概率之和： (1)P{系統(tǒng)在時刻t時為n，而在△t內(nèi)沒有到達(dá)也沒有消失} =,(2)P{系統(tǒng)在t時為n-1而在△t內(nèi)有一個到達(dá)并且沒有一個消失

37、}=,(3)P{系統(tǒng)在t時為n+1，而在△t內(nèi)沒有到達(dá)而有一個消失}=,則系統(tǒng)在時刻t+△t的,(4)P{系統(tǒng)在△t內(nèi)發(fā)生多于一個的到達(dá)或消失}=0(△t)應(yīng)用全概率公式有,當(dāng) 時 類似地，當(dāng)S為有限集時，對 有 令△t→0得 當(dāng)系統(tǒng)狀態(tài)S為有限集時，生滅過程的微分差分方 程組為,,,,,,當(dāng)系統(tǒng)狀態(tài)S為可數(shù)集時，生滅過程微分差分方程組

38、為 若能求解這組方程，則可得到在時刻t系統(tǒng)狀態(tài)概率分布 稱為生滅過程的瞬時解，一般這種瞬時解是難以求得的。,,可以證明，前述

39、的生滅過程存在統(tǒng)計平衡態(tài)，即系統(tǒng)各個狀態(tài)（K＋1個）的概率分布:pi=常數(shù)（i=0,1,…,K)即：,3.統(tǒng)計平衡下的極限解 實(shí)際應(yīng)用中，關(guān)心的是 時方程的解，稱為生滅過程微分差分方程組的極限解。,令 得當(dāng)S為有限狀態(tài)集時：當(dāng)S為可數(shù)狀態(tài)集時： 從而可以

40、求得概率分布列,,,,,,第5節(jié) 典型隨機(jī)服務(wù)系統(tǒng)模型和理論結(jié)果,1、M/M/1系統(tǒng)分析,通過分析排隊隊長無限、泊松輸入、指數(shù)服務(wù)分布的隨機(jī)服務(wù)系統(tǒng)來了解隨機(jī)服務(wù)系統(tǒng)分析的基本方法。下面介紹滿足生滅過程典型排隊M/M/1與M/M/S的結(jié)果1）在時間區(qū)段(t,t+Δt)內(nèi)，當(dāng)系統(tǒng)在t時刻的狀態(tài)為i（已經(jīng)有i人在系統(tǒng)中，包括排隊的和接受服務(wù)的）又有一個新的顧客到來的概率為λiΔt；2）在時間區(qū)段(t,t+Δt)內(nèi)，當(dāng)系統(tǒng)在t時刻的狀

41、態(tài)為i而有一個顧客離去的概率為μiΔt；3)兩個以上顧客同時到來或者離去的概率為高階無窮小可忽略,這一情況與生滅過程一致，可以用生滅過程進(jìn)行分析。,M／M／1模型,一個基本的排列模型。一個服務(wù)臺, 到達(dá)率 ? 和服務(wù)率 ? 都服從指數(shù)分布。模型的條件是：1、輸入過程――顧客源是無限的，顧客到達(dá)完全是隨機(jī)的，單個到來，到達(dá)過程服從普阿松分布，且是平穩(wěn)的；2、排隊規(guī)則――單隊，且隊長沒有限制，先到先服務(wù)；3、服務(wù)機(jī)構(gòu)――單服務(wù)臺

42、，服務(wù)時間的長短是隨機(jī)的，服從相同的指數(shù)分布 。,M/M/1系統(tǒng)分析,假定：對于所有狀態(tài)i而言，到達(dá)率為常數(shù)，即?i= ?對所有狀態(tài)i而言，服務(wù)率為常數(shù)，即?i = ? (3) ?< ?,保證隊列不會越排越長。單位時間內(nèi)平均到達(dá)顧客數(shù) ?（即到達(dá)率），即顧客平均到達(dá)時間1/ ?服務(wù)率 ? ：單位時間平均服務(wù)完的顧客數(shù)?，每個顧客平均服務(wù)時間1/ ?。定義 為服務(wù)強(qiáng)度。,,,,,,,對

43、于M/M/1系統(tǒng)，其平衡點(diǎn)的主要指標(biāo)有：,系統(tǒng)中有n個顧客的概率：,平均隊長（系統(tǒng)中平均顧客數(shù)）：,平均排隊長度：,每個顧客在系統(tǒng)中平均所花時間：,每個顧客排隊所花費(fèi)的平均時間:,M/M/1 舉例,例1,某醫(yī)院急診室同時只能診治一個病人，診治時間服從指數(shù)分布，每個病人平均需要15分鐘。病人按泊松分布到達(dá)，平均每小時到達(dá)3人。試對此排隊隊系統(tǒng)進(jìn)行分析。 解: 對此排隊隊系統(tǒng)分析如下：（1）先確定參數(shù)值：這是單服務(wù)臺系統(tǒng)，有：

44、 故服務(wù)強(qiáng)度為：,,,（2）計算穩(wěn)態(tài)概率：這就是急診室空閑的概率，也是病人不必等待立即就能就診的概率。而病人需要等待的概率則為：這也是急診室繁忙的概率。,,,（3）計算系統(tǒng)主要工作指標(biāo)。急診室內(nèi)外的病人平均數(shù)：急診室外排隊等待的病人平均數(shù)：病人在急診室內(nèi)外平均逗留時間：病人平均等候時間：,,,,（4）為使病人平均逗留時間不超過半小時，那么平均服務(wù)時間應(yīng)減少多少？由于代入λ=3

45、，解得μ≥5，平均服務(wù)時間為：15－12＝3min即平均服務(wù)時間至少應(yīng)減少3min,,,(5)若醫(yī)院希望候診的病人90% 以上都能有座位,則候診室至少應(yīng)安置多少座位? 設(shè)應(yīng)該安置χ個座位,加上急診室的一個座位,共有χ+1個。要使90% 以上的候診病人有座位，相當(dāng)于使“來診的病人數(shù)不多于χ+1個”的概率不少于90%，即,,,,,兩邊取對數(shù)（x＋2）lgρ ≤ lg0.1因 ρ < 1，故所以

46、 ⅹ≥6即候診室至少應(yīng)安置6個座位。,,,2、M / M / S 模型,此模型與M/M/1模型不同之處在于有S個服務(wù)臺，各服務(wù)臺的工作相互獨(dú)立，服務(wù)率相等，如果顧客到達(dá)時，S個服務(wù)臺都忙著，則排成一隊等待，先到先服務(wù)的單隊模型。整個系統(tǒng)的平均服務(wù)率為sμ，ρ*＝λ/sμ，（ρ*<1）為該系統(tǒng)的服務(wù)強(qiáng)度。,1、狀態(tài)概率,2、主要運(yùn)行指標(biāo)3、系統(tǒng)狀態(tài)N ≥S的概率,M/M/s 舉例,例2 承接例1，假設(shè)醫(yī)院增強(qiáng)

47、急診室的服務(wù)能力，使其同時能診治兩個病人，且平均服務(wù)率相同，試分析該系統(tǒng)工作情況，并且，例1、例2的結(jié)果進(jìn)行比較。,解：這相當(dāng)于增加了一個服務(wù)臺，故有： S=2,λ=3人/h，μ=4人/h,,,,,,,病人必須等候的概率,即系統(tǒng)狀態(tài)N≥2的概率：,表1 兩個系統(tǒng)的比較,p0,例3 某醫(yī)院掛號室有三個窗口，就診者的到達(dá)服從泊松分布，平均到達(dá)率為每分鐘0.9人，掛號員服務(wù)時間服從指數(shù)分布，平均服務(wù)率每分鐘0

48、.4人，現(xiàn)假設(shè)就診者到達(dá)后排成一隊，依次向空閑的窗口掛號，顯然系統(tǒng)的容量和顧客源是不限的，屬于M/M/3型的排隊服務(wù)模型。求：該系統(tǒng)的運(yùn)行指標(biāo) 解:,如果在例3中，就診者到達(dá)后在每個掛號窗口各自排成一隊，即排成3隊，且進(jìn)入隊列后不離開，各列間也互不串換，這就形成3個隊列，而例3中的其它條件不變。假設(shè)每個隊列平均到達(dá)率相等且為：λ1＝λ2＝λ3＝0.9/3＝0.3（人/分鐘）這樣，原來的M/M/3系統(tǒng)就變成了3個M/M/1型

49、的子系統(tǒng)。 現(xiàn)按M/M/1型計算主要運(yùn)行指標(biāo)，并與上面的例子進(jìn)行對比分析，結(jié)果見表2。,表2 兩個模型的比較,3、M/M/S/N/? 系統(tǒng)容量有限,固定長度排隊意味著若到了最大系統(tǒng)容量顧客將不能進(jìn)入系統(tǒng)。當(dāng)N=S 時為損失制系統(tǒng)當(dāng)N﹥S時為混合制系統(tǒng),M/M/1/N/? 舉例,作業(yè),一、顧客按泊松分布到達(dá)某私人按摩診所，平均間隔20分鐘。按摩時間為指數(shù)分布，平均每人15分鐘。試求：1）顧客不必等待的概率；2）4

50、項(xiàng)主要工作指標(biāo)；3）若顧客在所內(nèi)耗時超過1.25小時，則按摩師的配偶也參與按摩。問平均到達(dá)率提高多少，配偶才會參與？4）若希望95%以上的顧客都有座位，則至少應(yīng)該準(zhǔn)備多少把椅子？,,二、前來某體育館買票觀賽者為泊松流，平均每分鐘到達(dá)1人。售票處只有一個窗口，售票時間為指數(shù)分布，平均每人20秒。1）若一個觀眾于賽前2分鐘到達(dá)售票窗口，買完票后恰好用一分半鐘來到其座位，試問他能期望于開賽前坐好嗎？2）試求他在開賽前坐好的概率；3）