第九章 排隊論 (1)

1、第第9章章 排隊論排隊論南京航空航天大學南京航空航天大學排隊是我們在日常生活中經(jīng)常遇到的現(xiàn)象，例如排隊是我們在日常生活中經(jīng)常遇到的現(xiàn)象，例如病人到醫(yī)院看病、客戶到銀行匯款、城市擁堵病人到醫(yī)院看病、客戶到銀行匯款、城市擁堵路段的汽車排隊、電話占線等。排隊現(xiàn)象產(chǎn)生路段的汽車排隊、電話占線等。排隊現(xiàn)象產(chǎn)生的原因之一是要求服務的數(shù)量超過了服務機構(gòu)的原因之一是要求服務的數(shù)量超過了服務機構(gòu)的容量，也就是有部分的服務對象不能立即得的容量，也就是有部分的服務對象不能立即得到服務；原因之二是系統(tǒng)服務對象到達和服務到服務；原因之二是系統(tǒng)服務對象到達和服務時間均存在隨機性。前者可以通過增加服務機時間均存在隨機性。前

2、者可以通過增加服務機構(gòu)的容量來解決排隊現(xiàn)象，但無休止地增加服構(gòu)的容量來解決排隊現(xiàn)象，但無休止地增加服務機構(gòu)的容量會導致追加投資并可能發(fā)生系統(tǒng)務機構(gòu)的容量會導致追加投資并可能發(fā)生系統(tǒng)資源長時間閑置。后者，也就是系統(tǒng)服務對象資源長時間閑置。后者，也就是系統(tǒng)服務對象到達和服務時間均存在隨機性，致使無法準確到達和服務時間均存在隨機性，致使無法準確預測估算排隊擁堵的具體情況。所以，在服務預測估算排隊擁堵的具體情況。所以，在服務系統(tǒng)中的排隊現(xiàn)象幾乎不可避免。系統(tǒng)中的排隊現(xiàn)象幾乎不可避免。9.1排隊論的基本概念排隊論的基本概念排隊論是通過對服務對象到來及服務時排隊論是通過對服務對象到來及服務時間的統(tǒng)計研究，

3、得出這些數(shù)量指標（等間的統(tǒng)計研究，得出這些數(shù)量指標（等待時間、排隊長度、忙期長短等）的統(tǒng)待時間、排隊長度、忙期長短等）的統(tǒng)計規(guī)律，然后根據(jù)這些規(guī)律來改進服務計規(guī)律，然后根據(jù)這些規(guī)律來改進服務系統(tǒng)的結(jié)構(gòu)或重新組織被服務對象，使系統(tǒng)的結(jié)構(gòu)或重新組織被服務對象，使得服務系統(tǒng)既能滿足服務對象的需要，得服務系統(tǒng)既能滿足服務對象的需要，又能使服務機構(gòu)的費用最經(jīng)濟或某些指又能使服務機構(gòu)的費用最經(jīng)濟或某些指標最優(yōu)。標最優(yōu)。9.1.1排隊過程的一般表示排隊過程的一般表示排隊系統(tǒng)示意圖排隊系統(tǒng)示意圖一般的排隊系統(tǒng)有三個基本組成一般的排隊系統(tǒng)有三個基本組成部分部分： 輸入過程輸入過程 排隊及排隊規(guī)則排隊及排隊規(guī)則服

4、務機構(gòu)服務機構(gòu)輸入過程輸入過程主要包括：主要包括：l顧客相繼到達系統(tǒng)的時間間隔顧客相繼到達系統(tǒng)的時間間隔l顧客到達系統(tǒng)的方式（顧客可能單個顧客到達系統(tǒng)的方式（顧客可能單個到達，也可能成批到達）到達，也可能成批到達）l顧客源情況顧客源情況 輸入過程說明顧客按怎樣的規(guī)律到達服務系統(tǒng)輸入過程說明顧客按怎樣的規(guī)律到達服務系統(tǒng)的。它可用一定時間內(nèi)顧客到達的數(shù)量或前后兩的。它可用一定時間內(nèi)顧客到達的數(shù)量或前后兩個顧客相繼到達的間隔時間來描述。按照一定時個顧客相繼到達的間隔時間來描述。按照一定時間內(nèi)顧客到達數(shù)量或前后兩個顧客相繼到達的間間內(nèi)顧客到達數(shù)量或前后兩個顧客相繼到達的間隔時間類型的不同，輸入過程可以

5、劃分為隔時間類型的不同，輸入過程可以劃分為確定型確定型和隨機型兩種和隨機型兩種：如在自動裝配線上裝配的各部件：如在自動裝配線上裝配的各部件就必須是按確定時間間隔到達裝配點，定期的航就必須是按確定時間間隔到達裝配點，定期的航班、長途客車等都是確定型的；顧客到商店購買班、長途客車等都是確定型的；顧客到商店購買商品、到醫(yī)院就診的病人等都是隨機型的商品、到醫(yī)院就診的病人等都是隨機型的。在排。在排隊論中，討論的輸入過程主要是隨機型的。隊論中，討論的輸入過程主要是隨機型的。 隨機型的輸入是指在時間隨機型的輸入是指在時間t內(nèi)顧客到達數(shù)量內(nèi)顧客到達數(shù)量n(t)服從一定的概率分布。服從一定的概率分布。如服從泊松

6、分布，則在時間如服從泊松分布，則在時間t內(nèi)到達內(nèi)到達n個顧個顧客的概率為客的概率為： 或相繼到達的顧客的間隔時間或相繼到達的顧客的間隔時間T服從負指服從負指數(shù)分布，即數(shù)分布，即： 式中式中為單位時間顧客期望到達數(shù)量，稱為單位時間顧客期望到達數(shù)量，稱為平均到達率；為平均到達率；1/為平均間隔時間。為平均間隔時間。 排隊論的系統(tǒng)輸入還要關(guān)注顧客源是有限集還是無排隊論的系統(tǒng)輸入還要關(guān)注顧客源是有限集還是無限集。如工廠內(nèi)待修的機器數(shù)顯然是有限集，而到某限集。如工廠內(nèi)待修的機器數(shù)顯然是有限集，而到某航空售票處購票的顧客源則可以認為是無限的。航空售票處購票的顧客源則可以認為是無限的。 顧客的到達可以是相互

7、獨立的，也就是說，以前的顧客的到達可以是相互獨立的，也就是說，以前的到達情況對以后顧客的到達沒有影響，否則就是有關(guān)到達情況對以后顧客的到達沒有影響，否則就是有關(guān)聯(lián)的。如工廠內(nèi)的機器在一個短的時間區(qū)間內(nèi)出現(xiàn)故聯(lián)的。如工廠內(nèi)的機器在一個短的時間區(qū)間內(nèi)出現(xiàn)故障（顧客到達）的概率就受已經(jīng)待修或被修理機器數(shù)障（顧客到達）的概率就受已經(jīng)待修或被修理機器數(shù)目的影響。我們主要討論的是相互獨立的情形。目的影響。我們主要討論的是相互獨立的情形。 輸入過程可以是平穩(wěn)的，或稱為對時間是齊次的，輸入過程可以是平穩(wěn)的，或稱為對時間是齊次的，是指描述相繼到達的時間間隔分布和所含參數(shù)（如期是指描述相繼到達的時間間隔分布和所含

8、參數(shù)（如期望、方差）都是與時間無關(guān)的，否則成為非平穩(wěn)的。望、方差）都是與時間無關(guān)的，否則成為非平穩(wěn)的。我們主要討論的是平穩(wěn)的情形。我們主要討論的是平穩(wěn)的情形。排隊及排隊規(guī)則排隊及排隊規(guī)則（1 1）排隊）排隊排隊規(guī)則是指顧客來到排隊系統(tǒng)后如何排隊等候服務的規(guī)則，一般有即時制、等待制和混合制三大類。其中即時制(損失制)是指當顧客到達時，如果所有服務臺都已被占用，顧客可以隨即離開系統(tǒng)。等待制指顧客到達系統(tǒng)時，所有服務臺被占用，顧客就加入排隊隊列等待服務。而混合制是即時制和等待制相結(jié)合的一種排隊服務規(guī)則?；旌现浦饕譃閮煞N情況：一是隊長有限制的情況，即當顧客排隊等侯服務的人數(shù)超過規(guī)定數(shù)量（等待空間有限

9、）時，后來的顧客就自動離開，另求服務；二是排隊等侯時間有限制的情況，即當顧客排隊等候超過一定時間就會自動離開，不能再等。（2 2）排隊規(guī)則）排隊規(guī)則最常見的等待制排隊規(guī)則是：最常見的等待制排隊規(guī)則是：先到先服務先到先服務FCFS：即按到達次序接受服務，這是：即按到達次序接受服務，這是最常見的情形。最常見的情形。后到先服務后到先服務LCFS：如倉庫中存放的貨物常常是后：如倉庫中存放的貨物常常是后放入的先被出庫使用。放入的先被出庫使用。具有優(yōu)先權(quán)的服務具有優(yōu)先權(quán)的服務PS：如醫(yī)院對病情嚴重的病人予：如醫(yī)院對病情嚴重的病人予以優(yōu)先治療，公交車上對老年人予以優(yōu)先上車就坐以優(yōu)先治療，公交車上對老年人予以

10、優(yōu)先上車就坐等。等。隨機服務隨機服務SIRO：指服務員從等待的顧客中隨機地選：指服務員從等待的顧客中隨機地選取其中一個進行服務而不管到達的先后。如電話交取其中一個進行服務而不管到達的先后。如電話交換臺接通呼喚的電話。換臺接通呼喚的電話。服務機構(gòu)服務機構(gòu)排隊系統(tǒng)的服務機構(gòu)主要包含排隊系統(tǒng)的服務機構(gòu)主要包含：l服務員（服務設(shè)施）數(shù)量及其連接服務員（服務設(shè)施）數(shù)量及其連接形式（并聯(lián)或串聯(lián)）形式（并聯(lián)或串聯(lián)）l顧客是單個接受服務還是成批接受顧客是單個接受服務還是成批接受服務服務l服務時間的分布服務時間的分布各類型排隊系統(tǒng)各類型排隊系統(tǒng) 服務臺的服務時間一般也分成確定型和隨機型服務臺的服務時間一般也分成

11、確定型和隨機型兩種。例如，自動沖洗汽車的裝置對每輛汽車兩種。例如，自動沖洗汽車的裝置對每輛汽車沖洗（服務）時間是相同的，因而是確定型的。沖洗（服務）時間是相同的，因而是確定型的。但大多數(shù)情況下服務時間是隨機型的，對于隨但大多數(shù)情況下服務時間是隨機型的，對于隨機型的服務時間，我們需要知道服務時間機型的服務時間，我們需要知道服務時間V的概的概率分布。如果服務時間率分布。如果服務時間V服從負指數(shù)分布，則其服從負指數(shù)分布，則其分布函數(shù)是分布函數(shù)是式中式中為平均服務率，為平均服務率，1/1/為平均服務時間。為平均服務時間。9.1.2排隊系統(tǒng)的分類排隊系統(tǒng)的分類KendallKendall符號的形式符號的

12、形式X/Y/ZX/Y/Z。各符號的含。各符號的含義如下：義如下：lX X指顧客相繼到達間隔時間的分布指顧客相繼到達間隔時間的分布lY Y為服務時間的分布為服務時間的分布lZ Z為并列的服務臺數(shù)目為并列的服務臺數(shù)目表示相繼到達的間隔時間和服務時間分布符號常用表示相繼到達的間隔時間和服務時間分布符號常用以下符號表示以下符號表示lM M：負指數(shù)分布，表示每個顧客接受服務的時間相：負指數(shù)分布，表示每個顧客接受服務的時間相互獨立，具有相同的負指數(shù)分布；互獨立，具有相同的負指數(shù)分布；l負指數(shù)分布描述的隨機現(xiàn)象對于過去的事件具有負指數(shù)分布描述的隨機現(xiàn)象對于過去的事件具有無記憶性，即無記憶性，即MarkovM

13、arkov性，因此用性，因此用MarkovMarkov開頭字母開頭字母M M表示；表示；lD D：定長分布，表示每個顧客接受服務的時間是一：定長分布，表示每個顧客接受服務的時間是一個確定的常數(shù)；個確定的常數(shù)；0 t 00 t)(tetblE Ek k：k k階愛爾朗分布階愛爾朗分布Erlang)Erlang)，表示每個，表示每個顧客接受服務的時間服從顧客接受服務的時間服從k k階愛爾朗分布，階愛爾朗分布，其密度函數(shù)為其密度函數(shù)為l當當k=1k=1時愛爾朗分布就是負指數(shù)分布；當時愛爾朗分布就是負指數(shù)分布；當k k增加時，愛爾朗分布逐漸變?yōu)閷ΨQ的。增加時，愛爾朗分布逐漸變?yōu)閷ΨQ的。當當k30k30

14、時，愛爾朗分布近似于正態(tài)分布。時，愛爾朗分布近似于正態(tài)分布。G：一般隨機分布。：一般隨機分布。 例如例如M/M/l表示到達的間隔時間服從負指數(shù)表示到達的間隔時間服從負指數(shù)分布，服務時間也服從負指數(shù)分布的單服務分布，服務時間也服從負指數(shù)分布的單服務臺排隊系統(tǒng)模型。臺排隊系統(tǒng)模型。M/D/2表示到達間隔時間表示到達間隔時間服從負指數(shù)分布，而服務時間為定長分布的服從負指數(shù)分布，而服務時間為定長分布的雙服務臺排隊系統(tǒng)模型。雙服務臺排隊系統(tǒng)模型。 1971年有關(guān)排隊論符號的標準化會議將年有關(guān)排隊論符號的標準化會議將Kendall符號擴展為符號擴展為X/Y/Z/A/B/C，其中，其中A指排指排隊系統(tǒng)的容量

15、，取非負整數(shù)或隊系統(tǒng)的容量，取非負整數(shù)或；B表示顧客源表示顧客源的數(shù)目，取非負整數(shù)或的數(shù)目，取非負整數(shù)或；C表示服務規(guī)則（先表示服務規(guī)則（先來先服務來先服務FCFS、后來先服務、后來先服務LCFS，具有優(yōu)先，具有優(yōu)先權(quán)的服務權(quán)的服務PS，隨機服務，隨機服務SIRO等）。等）。如如M/M/1/ / / FCFS:表示顧客到達的時間間表示顧客到達的時間間隔服從負指數(shù)分布、服務時間服從負指數(shù)分布隔服從負指數(shù)分布、服務時間服從負指數(shù)分布、單服務臺、系統(tǒng)容量為無限、顧客源為無限、單服務臺、系統(tǒng)容量為無限、顧客源為無限、排隊規(guī)則為先來先服務的排隊模型。我們這、排隊規(guī)則為先來先服務的排隊模型。我們這一章的模

16、型只討論先到先服務的情形，因此后一章的模型只討論先到先服務的情形，因此后面都略去第六項。面都略去第六項。9.1.3排隊系統(tǒng)的衡量指標排隊系統(tǒng)的衡量指標 構(gòu)建了排隊系統(tǒng)的模型后，需要對排隊系統(tǒng)構(gòu)建了排隊系統(tǒng)的模型后，需要對排隊系統(tǒng)的運行效率和服務質(zhì)量進行研究和評估，以確定的運行效率和服務質(zhì)量進行研究和評估，以確定系統(tǒng)的結(jié)構(gòu)是否合理。任何排隊系統(tǒng)開始運行時，系統(tǒng)的結(jié)構(gòu)是否合理。任何排隊系統(tǒng)開始運行時，其狀態(tài)在很大程度上取決于系統(tǒng)的初始狀態(tài)和運其狀態(tài)在很大程度上取決于系統(tǒng)的初始狀態(tài)和運轉(zhuǎn)的時間。但系統(tǒng)運行了一段時間后，系統(tǒng)將進轉(zhuǎn)的時間。但系統(tǒng)運行了一段時間后，系統(tǒng)將進入穩(wěn)定狀態(tài)（即穩(wěn)態(tài)，系統(tǒng)運行充分

17、長時間后，入穩(wěn)定狀態(tài)（即穩(wěn)態(tài)，系統(tǒng)運行充分長時間后，初始狀態(tài)的影響基本消失，系統(tǒng)狀態(tài)不再隨時間初始狀態(tài)的影響基本消失，系統(tǒng)狀態(tài)不再隨時間變化）。對排隊系統(tǒng)進行分析主要是指對其穩(wěn)定變化）。對排隊系統(tǒng)進行分析主要是指對其穩(wěn)定狀態(tài)的運行效率指標進行分析。狀態(tài)的運行效率指標進行分析。 常用于分析排隊系統(tǒng)效率的常用于分析排隊系統(tǒng)效率的有以下有以下指標：指標：l平均隊長平均隊長L Ls s和平均排隊長和平均排隊長L Lq ql平均逗留時間平均逗留時間w ws s和平均等待時間和平均等待時間w wq ql忙期和閑期忙期和閑期l服務強度服務強度（1）平均隊長）平均隊長Ls和平均排隊長和平均排隊長Lq。平均隊。

18、平均隊長長Ls指一個排隊系統(tǒng)的顧客平均數(shù)（其中包指一個排隊系統(tǒng)的顧客平均數(shù)（其中包括正在接受服務的顧客）。而平均排隊長括正在接受服務的顧客）。而平均排隊長Lq則是指系統(tǒng)中等待服務的顧客平均數(shù)；則是指系統(tǒng)中等待服務的顧客平均數(shù)；（2）平均逗留時間）平均逗留時間ws和平均等待時間和平均等待時間wq。平均逗留時間平均逗留時間ws指進入系統(tǒng)的顧客逗留時指進入系統(tǒng)的顧客逗留時間的平均值（包括接受服務的時間），而平間的平均值（包括接受服務的時間），而平均等待時間均等待時間wq則是指進入系統(tǒng)的顧客等待則是指進入系統(tǒng)的顧客等待時間的平均值；時間的平均值； （3）忙期和閑期。忙期是指服務機構(gòu)兩次空閑的）忙期和閑

19、期。忙期是指服務機構(gòu)兩次空閑的時間間隔，這是一個隨機變量，是服務員最關(guān)心的時間間隔，這是一個隨機變量，是服務員最關(guān)心的指標，因為它關(guān)系到服務員的服務強度；與忙期相指標，因為它關(guān)系到服務員的服務強度；與忙期相對的是閑期，它是服務機構(gòu)連續(xù)保持空閑的時間。對的是閑期，它是服務機構(gòu)連續(xù)保持空閑的時間。在排隊系統(tǒng)中，忙期和閑期總是交替出現(xiàn)的。在排隊系統(tǒng)中，忙期和閑期總是交替出現(xiàn)的。（4）服務強度）服務強度。每個服務臺單位時間內(nèi)平均服務。每個服務臺單位時間內(nèi)平均服務時間。時間。其中其中Ls、Lq、ws和和wq通常稱之為重要的運行指標通常稱之為重要的運行指標。它們?nèi)≈翟叫?，說明系統(tǒng)隊長越短，顧客等候時。它們

20、取值越小，說明系統(tǒng)隊長越短，顧客等候時間越少，因此系統(tǒng)的性能就越好。間越少，因此系統(tǒng)的性能就越好。我們在穩(wěn)態(tài)下，討論單服務臺排隊系統(tǒng)和多服務臺我們在穩(wěn)態(tài)下，討論單服務臺排隊系統(tǒng)和多服務臺排隊系統(tǒng)。排隊系統(tǒng)。 9.29.2單服務臺排隊系統(tǒng)分析單服務臺排隊系統(tǒng)分析本節(jié)討論輸入過程為泊松流，服務時間本節(jié)討論輸入過程為泊松流，服務時間服從負指數(shù)分布的單服務臺的排隊系統(tǒng)。服從負指數(shù)分布的單服務臺的排隊系統(tǒng)。其中有：其中有：標準的標準的M/M/M/M/1/1/系統(tǒng)；系統(tǒng)；有限等待空間系統(tǒng)有限等待空間系統(tǒng)M/M/M/M/1/N/1/N/；顧客為有限源系統(tǒng)顧客為有限源系統(tǒng)M/MM/M/1/m/1/m。9.2.

21、1 標準的標準的M/M/1/系統(tǒng)系統(tǒng)M/M/1M/M/1系統(tǒng)狀態(tài)轉(zhuǎn)移圖系統(tǒng)狀態(tài)轉(zhuǎn)移圖: :系統(tǒng)狀態(tài)從系統(tǒng)狀態(tài)從0 0轉(zhuǎn)移到轉(zhuǎn)移到l l的轉(zhuǎn)移率為的轉(zhuǎn)移率為P P0 0，而系統(tǒng)狀態(tài)從而系統(tǒng)狀態(tài)從1 1轉(zhuǎn)移到轉(zhuǎn)移到0 0的轉(zhuǎn)移率為的轉(zhuǎn)移率為P P1 1。因此對狀態(tài)因此對狀態(tài)0 0而言，必須滿足以下平衡而言，必須滿足以下平衡方程：方程：對系統(tǒng)的任何狀態(tài)對系統(tǒng)的任何狀態(tài)n n 1 1，系統(tǒng)狀態(tài)從，系統(tǒng)狀態(tài)從n n轉(zhuǎn)移到轉(zhuǎn)移到n n+1+1和和n n-1-1的轉(zhuǎn)移率為的轉(zhuǎn)移率為P Pn n+P Pn n，而系統(tǒng)狀態(tài)從，而系統(tǒng)狀態(tài)從n n+1+1和和n n-1-1轉(zhuǎn)移到轉(zhuǎn)移到n n的轉(zhuǎn)移率為的轉(zhuǎn)移率為P

22、Pn n+1+1+P Pn n-1-1。由平衡條件可得：由平衡條件可得：令令 可解得可解得 在在 11的條件下，標準的條件下，標準M/M/lM/M/l系統(tǒng)的重要運行指系統(tǒng)的重要運行指 標如下：標如下：(1)(1)在平衡條件在平衡條件 下系統(tǒng)中顧客數(shù)為下系統(tǒng)中顧客數(shù)為n n 的概率的概率P Pn n 由于由于 ，所以所以 故故 (2)(2)系統(tǒng)在平穩(wěn)狀態(tài)下的平均隊長系統(tǒng)在平穩(wěn)狀態(tài)下的平均隊長( (包括等待包括等待和接受服務的顧客數(shù)和接受服務的顧客數(shù)) )L Ls s為為：或或(3)(3)系統(tǒng)在平穩(wěn)狀態(tài)下平均排隊長系統(tǒng)在平穩(wěn)狀態(tài)下平均排隊長( (系統(tǒng)排隊系統(tǒng)排隊等待的顧客數(shù)等待的顧客數(shù)) ) L

23、Lq q為為平均排隊人數(shù)等于系統(tǒng)的平均人數(shù)減去平均平均排隊人數(shù)等于系統(tǒng)的平均人數(shù)減去平均的正在接受服務的人數(shù)：的正在接受服務的人數(shù)：或或設(shè)每個顧客在系統(tǒng)中平均逗留時間為設(shè)每個顧客在系統(tǒng)中平均逗留時間為W Ws s。顧。顧客在系統(tǒng)中逗留的時間客在系統(tǒng)中逗留的時間T T服從參數(shù)為服從參數(shù)為-的負的負指數(shù)分布，即顧客在系統(tǒng)中逗留時間超過指數(shù)分布，即顧客在系統(tǒng)中逗留時間超過t t的概率為的概率為: :因此顧客在系統(tǒng)中平均逗留時間為：因此顧客在系統(tǒng)中平均逗留時間為：或或每個顧客在系統(tǒng)中平均等待時間為每個顧客在系統(tǒng)中平均等待時間為W Wq q，平均，平均等待時間為顧客在系統(tǒng)中平均逗留時間減去等待時間為顧客

24、在系統(tǒng)中平均逗留時間減去平均服務時間：平均服務時間：或或例例. .假設(shè)某高鐵售票處僅一臺自助售票機，假設(shè)某高鐵售票處僅一臺自助售票機，買票的人隨機到來，且服從泊松分布，平買票的人隨機到來，且服從泊松分布，平均為每小時均為每小時2020人。如果售票的服務時間平人。如果售票的服務時間平均每人需均每人需0.50.5分鐘，售票機前會排多長的隊分鐘，售票機前會排多長的隊？如果平均服務時間為？如果平均服務時間為1.01.0分鐘或者分鐘或者2.02.0分分鐘，情況會怎樣？顧客平均在系統(tǒng)中花費鐘，情況會怎樣？顧客平均在系統(tǒng)中花費多少時間？多少時間？9.2.29.2.2有限等待空間系統(tǒng)有限等待空間系統(tǒng)M/MM/

25、M/1/1/N N/對對M/MM/M/1/1/N N/來說，系統(tǒng)狀態(tài)是有限來說，系統(tǒng)狀態(tài)是有限集合，即集合，即 : :M M/ /M M/1/1/N N/排隊系統(tǒng)的狀態(tài)轉(zhuǎn)移圖排隊系統(tǒng)的狀態(tài)轉(zhuǎn)移圖如如下：下：在穩(wěn)態(tài)條件下，可得如下狀態(tài)平衡方在穩(wěn)態(tài)條件下，可得如下狀態(tài)平衡方程：程：得得由于由于 所以所以由此可以計算系統(tǒng)的有關(guān)運行指標由此可以計算系統(tǒng)的有關(guān)運行指標：(1)(1)平均隊長平均隊長L Ls s當當 時時當?shù)群蚩臻g有限、且當?shù)群蚩臻g有限、且11時，真正進入服務時，真正進入服務系統(tǒng)的顧客平均輸入率小于顧客平均到達系統(tǒng)的顧客平均輸入率小于顧客平均到達率率的有效到達率為的有效到達率為 。由于系統(tǒng)

26、容量為由于系統(tǒng)容量為N N，所以，所以故故 1- 1-P P0 0 = = （2 2）平均排隊長）平均排隊長 （3 3）平均逗留時間）平均逗留時間 （4 4）平均等候時間）平均等候時間 例例. .單人理發(fā)館有單人理發(fā)館有4 4個椅子供人們排隊等個椅子供人們排隊等待理發(fā)。當待理發(fā)。當4 4個椅子都坐滿時，后來的個椅子都坐滿時，后來的顧客就自動離開。若顧客按泊松流到達顧客就自動離開。若顧客按泊松流到達，平均間隔時間，平均間隔時間2020分鐘，顧客理發(fā)時間分鐘，顧客理發(fā)時間服從負指數(shù)分布，平均理發(fā)時間為服從負指數(shù)分布，平均理發(fā)時間為1515分分鐘。試求任一顧客的平均等待時間等相鐘。試求任一顧客的平均

27、等待時間等相關(guān)參數(shù)。關(guān)參數(shù)。9.2.39.2.3顧客為有限源系顧客為有限源系M M/ /M M/1/1/m m該排隊系統(tǒng)平均到達率隨系統(tǒng)狀態(tài)的變該排隊系統(tǒng)平均到達率隨系統(tǒng)狀態(tài)的變化而變化。該排隊系統(tǒng)的化而變化。該排隊系統(tǒng)的狀狀態(tài)轉(zhuǎn)移圖如態(tài)轉(zhuǎn)移圖如下：下：系統(tǒng)的狀態(tài)平衡方程為：系統(tǒng)的狀態(tài)平衡方程為：得得因為因為 ，所以并不要求所以并不要求 所以所以由此可推導出系統(tǒng)的各項運行指標由此可推導出系統(tǒng)的各項運行指標: :（1 1）平均顧客數(shù)）平均顧客數(shù)L Ls s（2 2）平均排隊長）平均排隊長L Lq q （3 3）平均逗留時間）平均逗留時間 （4 4）平均等待時間）平均等待時間 例例. .某車間共有

28、某車間共有6 6臺車床，每臺車床的連續(xù)運轉(zhuǎn)臺車床，每臺車床的連續(xù)運轉(zhuǎn)時間服從負指數(shù)分布，平均連續(xù)運轉(zhuǎn)時間時間服從負指數(shù)分布，平均連續(xù)運轉(zhuǎn)時間6060分分鐘。車間有一名負責維修人員，該工人每次修鐘。車間有一名負責維修人員，該工人每次修理時間服從負指數(shù)分布，平均每次維修時間為理時間服從負指數(shù)分布，平均每次維修時間為6 6分鐘。試計算以下問題分鐘。試計算以下問題: :（1 1）工人空閑的概率；）工人空閑的概率；（2 2）6 6臺機床都出故障的概率；臺機床都出故障的概率；（3 3）出故障的平均機床數(shù)；）出故障的平均機床數(shù)；（4 4）等待修理的平均機床數(shù)，）等待修理的平均機床數(shù)，5 5平均停工的時間；平

29、均停工的時間；（6 6）平均等待修理的時間；）平均等待修理的時間；（7 7）機床設(shè)備利用率。）機床設(shè)備利用率。9.39.3多服務臺排隊系統(tǒng)分析多服務臺排隊系統(tǒng)分析對于多服務臺排隊系統(tǒng)，本節(jié)假定：對于多服務臺排隊系統(tǒng)，本節(jié)假定：（1 1）N N個完全相同的服務臺并聯(lián)工作；個完全相同的服務臺并聯(lián)工作；（2 2）只有一隊顧客；）只有一隊顧客；（3 3）顧客隨機到達；）顧客隨機到達；（4 4）隨機的服務時間長度；）隨機的服務時間長度；（5 5）服務規(guī)則為）服務規(guī)則為“先到先服務先到先服務”；（6 6）系統(tǒng)可以達到穩(wěn)定狀態(tài)；）系統(tǒng)可以達到穩(wěn)定狀態(tài)；（7 7）對于隊列中的顧客數(shù)量沒有限制；）對于隊列中的顧

30、客數(shù)量沒有限制；（8 8）對于接受服務的顧客數(shù)量沒有限制；）對于接受服務的顧客數(shù)量沒有限制；（9 9）所有到來的顧客都等待服務）所有到來的顧客都等待服務。9.3.19.3.1標準標準M/M/cM/M/c/系統(tǒng)系統(tǒng)顧客的平均到達率為常數(shù)顧客的平均到達率為常數(shù)，每個服務臺的，每個服務臺的平均服務率均為平均服務率均為，同時規(guī)定各服務臺的工，同時規(guī)定各服務臺的工作是相互獨立的。就整個服務機構(gòu)而言，平作是相互獨立的。就整個服務機構(gòu)而言，平均服務率與系統(tǒng)狀態(tài)有關(guān)，即：均服務率與系統(tǒng)狀態(tài)有關(guān)，即：同時要求系統(tǒng)的服務強度（服務機構(gòu)的平均同時要求系統(tǒng)的服務強度（服務機構(gòu)的平均利用率）利用率） , ,這樣系統(tǒng)不會

31、排成無限這樣系統(tǒng)不會排成無限隊列。隊列。M M/ /M M/ /c c系統(tǒng)的狀態(tài)轉(zhuǎn)移如圖系統(tǒng)的狀態(tài)轉(zhuǎn)移如圖：由圖可得：由圖可得：用遞推法求解上述差分方程，可得狀態(tài)概率用遞推法求解上述差分方程，可得狀態(tài)概率：系統(tǒng)的其它運行指標計算如下：系統(tǒng)的其它運行指標計算如下：（1 1）平均排隊長和平均隊長）平均排隊長和平均隊長：（2 2）平均等待和逗留時間）平均等待和逗留時間例例. .某郵局有某郵局有3 3個窗口，來辦理業(yè)務的個窗口，來辦理業(yè)務的人員是隨機到達，平均每小時人員是隨機到達，平均每小時2525人到人到達。每個顧客辦理業(yè)務的平均時間為達。每個顧客辦理業(yè)務的平均時間為6 6分鐘，也就是每個窗口每小時

32、可以為分鐘，也就是每個窗口每小時可以為1010個顧客提供服務。試求解這一排隊個顧客提供服務。試求解這一排隊系統(tǒng)的相關(guān)參數(shù)。系統(tǒng)的相關(guān)參數(shù)。9.3.2 M/M/c/N/9.3.2 M/M/c/N/系統(tǒng)系統(tǒng)該排隊系統(tǒng)的狀態(tài)轉(zhuǎn)移如圖該排隊系統(tǒng)的狀態(tài)轉(zhuǎn)移如圖: :由圖可得：由圖可得：可得系統(tǒng)有關(guān)狀態(tài)運行指標如下：可得系統(tǒng)有關(guān)狀態(tài)運行指標如下：其中其中 ，這里不必對系統(tǒng)強度，這里不必對系統(tǒng)強度作限制。系統(tǒng)的其他運行指標如下：作限制。系統(tǒng)的其他運行指標如下：(1) 1eNsqqqNPLLLLcP021c)1 ()(1 )1 ()()(PcNccPcnLcNcNcNnnq！(1)qqqeNLLWP1 sqWW有些服務機構(gòu)不允許排隊（例如停車場一般有些服務機構(gòu)不允許排隊（例如停車場一般不允許排隊等待空位），這時不允許排隊等待空位），這時N N = =c c，即系統(tǒng)，即系統(tǒng)最大容量最大容量N N 和服務臺數(shù)和服務臺數(shù)c c 相等時系統(tǒng)由混合相等時系統(tǒng)由混合制變成即時制。此時有：制變成即時制。此時有：并且并且10001, ,1!ncnnncPcPPnNnn9.3.39.3.3 M/M/c/m系統(tǒng)假設(shè)排隊系統(tǒng)有假設(shè)排隊系統(tǒng)有c c個服務臺，顧客總數(shù)為個服務臺，顧客總數(shù)為m m個，同時假設(shè)個，同時假設(shè)c c m m，系統(tǒng)的狀態(tài)轉(zhuǎn)移如圖，系統(tǒng)的狀態(tài)轉(zhuǎn)移如圖: :n1n1n01就整個服務