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

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

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

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

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

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

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

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

8、)。 2. 研究系統(tǒng)狀態(tài)的概率。系統(tǒng)狀態(tài)是指系統(tǒng)中顧客數。狀態(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)一般很快都能達到，但實際中達不到穩(wěn)態(tài)的現象也存在。值得注意的是求穩(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é) 隨機服務系統(tǒng)特征和基本排隊模型,共同特征： (1)請求服務的人或者物——顧客； (2)有為顧客服務的人或者物，即服務員或服務臺； (3)顧客到達系統(tǒng)的時刻是隨機的，為每一位顧客提供服務的時間是隨機的，因而整個排隊系統(tǒng)的狀態(tài)也

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

29、均服務率；1/μ——平均服務時間；N――穩(wěn)態(tài)系統(tǒng)任一時刻的狀態(tài)（即系統(tǒng)中所有顧客數）；U――任一顧客在穩(wěn)態(tài)系統(tǒng)中的逗留時間；Q――任一顧客在穩(wěn)態(tài)系統(tǒng)中的等待時間；,系統(tǒng)狀態(tài) =排隊系統(tǒng)顧客的數量。 N(t) =在時間 t 排隊系統(tǒng)中顧客的數量。隊列長度 =等待服務的顧客的數量。 Pn(t) =在時間t,排隊系統(tǒng)中恰好有n個顧客的概率。s =服務臺的數目。,,,,ρ——服務強度，即每個

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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