系統(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)是一類研究得較多的離散事件動(dòng)態(tài)系統(tǒng)?，F(xiàn)實(shí)中很多問(wèn)題可以使用隨機(jī)服務(wù)系統(tǒng)加以描述和分析。 火車站買票，顧

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

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

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

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

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

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

8、)。 2. 研究系統(tǒng)狀態(tài)的概率。系統(tǒng)狀態(tài)是指系統(tǒng)中顧客數(shù)。狀態(tài)概率用Pn(t)表示,即在t時(shí)刻系統(tǒng)中有n個(gè)顧客的概率，也稱瞬態(tài)概率。,求解狀態(tài)概率Pn(t)方法是建立含Pn(t)的微分差分方程，通過(guò)求解微分差分方程得到系統(tǒng)瞬態(tài)解，由于瞬態(tài)解一般求出確定值比較困難，即便求得一般也很難使用。因此我們常常使用它的極限(如果存在的話)：,穩(wěn)態(tài)的物理意義見(jiàn)右圖，系統(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)計(jì)平衡狀態(tài) (Statistical Equilibrium State)的解。,第2節(jié) 隨機(jī)服務(wù)系統(tǒng)特征和基本排隊(duì)模型,共同特征： (1)請(qǐng)求服務(wù)的人或者物——顧客； (2)有為顧客服務(wù)的人或者物，即服務(wù)員或服務(wù)臺(tái)； (3)顧客到達(dá)系統(tǒng)的時(shí)刻是隨機(jī)的，為每一位顧客提供服務(wù)的時(shí)間是隨機(jī)的，因而整個(gè)排隊(duì)系統(tǒng)的狀態(tài)也

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

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

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

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

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

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

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

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

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

19、與服務(wù)時(shí)間之和)有限。,3．服務(wù)機(jī)理,服務(wù)機(jī)理是隨機(jī)服務(wù)系統(tǒng)的第三個(gè)要素，包括：服務(wù)者的個(gè)數(shù)、單個(gè)服務(wù)還是成批服務(wù)、以及服務(wù)的時(shí)間分布(1)服務(wù)臺(tái)數(shù)量及構(gòu)成形式。從數(shù)量上說(shuō)，服務(wù)臺(tái)有單服務(wù)臺(tái)和多服務(wù)臺(tái)之分。從構(gòu)成形式上看，服務(wù)臺(tái)有：①單隊(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)混合式等等。,,,(2)服務(wù)方式。這

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

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

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

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

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

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

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

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

28、．?dāng)?shù)量指標(biāo)的常用記號(hào) (1)主要數(shù)量指標(biāo)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í)間的期望值。,(2)其他常用數(shù)量指標(biāo)s——系統(tǒng)中并聯(lián)服務(wù)臺(tái)的數(shù)目；λ——平均到達(dá)率；1／λ——平均到達(dá)間隔；μ——平

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

46、 ⅹ≥6即候診室至少應(yīng)安置6個(gè)座位。,,,2、M / M / S 模型,此模型與M/M/1模型不同之處在于有S個(gè)服務(wù)臺(tái)，各服務(wù)臺(tái)的工作相互獨(dú)立，服務(wù)率相等，如果顧客到達(dá)時(shí)，S個(gè)服務(wù)臺(tái)都忙著，則排成一隊(duì)等待，先到先服務(wù)的單隊(duì)模型。整個(gè)系統(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ù)能力，使其同時(shí)能診治兩個(gè)病人，且平均服務(wù)率相同，試分析該系統(tǒng)工作情況，并且，例1、例2的結(jié)果進(jìn)行比較。,解：這相當(dāng)于增加了一個(gè)服務(wù)臺(tái)，故有： S=2,λ=3人/h，μ=4人/h,,,,,,,病人必須等候的概率,即系統(tǒng)狀態(tài)N≥2的概率：,表1 兩個(gè)系統(tǒng)的比較,p0,例3 某醫(yī)院掛號(hào)室有三個(gè)窗口，就診者的到達(dá)服從泊松分布，平均到達(dá)率為每分鐘0.9人，掛號(hào)員服務(wù)時(shí)間服從指數(shù)分布，平均服務(wù)率每分鐘0

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

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

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