第九章 排隊(duì)論 (1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

20、取值越小，說(shuō)明系統(tǒng)隊(duì)長(zhǎng)越短，顧客等候時(shí)間越少，因此系統(tǒng)的性能就越好。間越少，因此系統(tǒng)的性能就越好。我們?cè)诜€(wěn)態(tài)下，討論單服務(wù)臺(tái)排隊(duì)系統(tǒng)和多服務(wù)臺(tái)我們?cè)诜€(wěn)態(tài)下，討論單服務(wù)臺(tái)排隊(duì)系統(tǒng)和多服務(wù)臺(tái)排隊(duì)系統(tǒng)。排隊(duì)系統(tǒng)。 9.29.2單服務(wù)臺(tái)排隊(duì)系統(tǒng)分析單服務(wù)臺(tái)排隊(duì)系統(tǒng)分析本節(jié)討論輸入過(guò)程為泊松流，服務(wù)時(shí)間本節(jié)討論輸入過(guò)程為泊松流，服務(wù)時(shí)間服從負(fù)指數(shù)分布的單服務(wù)臺(tái)的排隊(duì)系統(tǒng)。服從負(fù)指數(shù)分布的單服務(wù)臺(tái)的排隊(duì)系統(tǒng)。其中有：其中有：標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的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 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的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。因此對(duì)狀態(tài)因此對(duì)狀態(tài)0 0而言，必須滿足以下平衡而言，必須滿足以下平衡方程：方程：對(duì)系統(tǒng)的任何狀態(tài)對(duì)系統(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的條件下，標(biāo)準(zhǔn)的條件下，標(biāo)準(zhǔn)M/M/lM/M/l系統(tǒng)的重要運(yùn)行指系統(tǒng)的重要運(yùn)行指 標(biāo)如下：標(biāo)如下：(1)(1)在平衡條件在平衡條件 下系統(tǒng)中顧客數(shù)為下系統(tǒng)中顧客數(shù)為n n 的概率的概率P Pn n 由于由于 ，所以所以 故故 (2)(2)系統(tǒng)在平穩(wěn)狀態(tài)下的平均隊(duì)長(zhǎng)系統(tǒng)在平穩(wěn)狀態(tài)下的平均隊(duì)長(zhǎng)( (包括等待包括等待和接受服務(wù)的顧客數(shù)和接受服務(wù)的顧客數(shù)) )L Ls s為為：或或(3)(3)系統(tǒng)在平穩(wěn)狀態(tài)下平均排隊(duì)長(zhǎng)系統(tǒng)在平穩(wěn)狀態(tài)下平均排隊(duì)長(zhǎng)( (系統(tǒng)排隊(duì)系統(tǒng)排隊(duì)等待的顧客數(shù)等待的顧客數(shù)) ) L

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

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

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

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

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

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

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

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

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

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