排隊(duì)論簡(jiǎn)要知識(shí)

1、排隊(duì)論簡(jiǎn)要知識(shí)l排隊(duì)系統(tǒng)描述l根本概念 lM / M / 1 模型lM / M / S 模型l顧客要求效勞的對(duì)象統(tǒng)稱為“顧客l效勞臺(tái)把提供效勞的人或機(jī)構(gòu)稱為“效勞臺(tái)或“效勞員l l 面對(duì)擁擠現(xiàn)象，人們通常的做法是增加效勞設(shè)施，但是增加的數(shù)量越多，人力、物力的支出就越大，甚至?xí)霈F(xiàn)空閑浪費(fèi)，如果效勞設(shè)施太少，顧客排隊(duì)等待的時(shí)間就會(huì)很長(zhǎng)，這樣對(duì)顧客會(huì)帶來不良影響。如何做到既保證一定的效勞質(zhì)量指標(biāo)，又使效勞設(shè)施費(fèi)用經(jīng)濟(jì)合理，恰當(dāng)?shù)亟鉀Q顧客排隊(duì)時(shí)間與效勞設(shè)施費(fèi)用大小這對(duì)矛盾，就是隨機(jī)效勞系統(tǒng)理論排隊(duì)論所要研究解決的問題。 一、排隊(duì)系統(tǒng)的描述 二、排隊(duì)系統(tǒng)的主要數(shù)量指標(biāo)l (一)系統(tǒng)特征和根本排隊(duì)過程l

2、 (二)排隊(duì)系統(tǒng)的根本組成局部l三)排隊(duì)系統(tǒng)的描述符號(hào)l相似的特征及數(shù)學(xué)抽象：相似的特征及數(shù)學(xué)抽象： l (1)(1)請(qǐng)求效勞的人或者物請(qǐng)求效勞的人或者物顧客；顧客； l (2)(2)有為顧客效勞的人或者物，即效勞有為顧客效勞的人或者物，即效勞員或效勞臺(tái)；員或效勞臺(tái)；l (3)(3)顧客到達(dá)系統(tǒng)的時(shí)刻是隨機(jī)的，為顧客到達(dá)系統(tǒng)的時(shí)刻是隨機(jī)的，為每一位顧客提供效勞的時(shí)間是隨機(jī)的，每一位顧客提供效勞的時(shí)間是隨機(jī)的，因而整個(gè)排隊(duì)系統(tǒng)的狀態(tài)也是隨機(jī)的。因而整個(gè)排隊(duì)系統(tǒng)的狀態(tài)也是隨機(jī)的。l根本排隊(duì)過程根本排隊(duì)過程l 可以用圖可以用圖6666表示。從圖表示。從圖6666可知，每個(gè)顧客由顧客源按一定方可知，每

3、個(gè)顧客由顧客源按一定方式到達(dá)效勞系統(tǒng)，首先參加隊(duì)列排式到達(dá)效勞系統(tǒng)，首先參加隊(duì)列排隊(duì)等待承受效勞，然后效勞臺(tái)按一隊(duì)等待承受效勞，然后效勞臺(tái)按一定規(guī)那么從隊(duì)列中選擇顧客進(jìn)展效定規(guī)那么從隊(duì)列中選擇顧客進(jìn)展效勞，獲得效勞的顧客立即離開。勞，獲得效勞的顧客立即離開。 排隊(duì)系統(tǒng)由3個(gè)局部組成 1、輸入過程 2、效勞規(guī)那么 3、效勞臺(tái) 這是指要求效勞的顧客是按怎樣的規(guī)律到達(dá)排隊(duì)這是指要求效勞的顧客是按怎樣的規(guī)律到達(dá)排隊(duì)系統(tǒng)的過程，有時(shí)也把它稱為顧客流。一般可以從系統(tǒng)的過程，有時(shí)也把它稱為顧客流。一般可以從3 3個(gè)方面來描述個(gè)方面來描述個(gè)輸入過程。個(gè)輸入過程。 (1)(1)顧客總體數(shù)，又稱顧客源、輸入源。這

4、是指顧客的顧客總體數(shù)，又稱顧客源、輸入源。這是指顧客的來源。顧客源可以是有限的，也可以是無限的。來源。顧客源可以是有限的，也可以是無限的。 (2)(2)顧客到達(dá)方式。這是描述顧客是怎樣來到系統(tǒng)的，顧客到達(dá)方式。這是描述顧客是怎樣來到系統(tǒng)的，是單個(gè)到達(dá)，還是成批到達(dá)。是單個(gè)到達(dá)，還是成批到達(dá)。 (3)(3)顧客流的概率分布，或稱相繼顧客到達(dá)的時(shí)間間隔顧客流的概率分布，或稱相繼顧客到達(dá)的時(shí)間間隔的分布。這是求解排隊(duì)系統(tǒng)有關(guān)運(yùn)行指標(biāo)問題時(shí)，首的分布。這是求解排隊(duì)系統(tǒng)有關(guān)運(yùn)行指標(biāo)問題時(shí)，首先需要確定的指標(biāo)。顧客流的概率分布一般有定長(zhǎng)分先需要確定的指標(biāo)。顧客流的概率分布一般有定長(zhǎng)分布、二項(xiàng)分布、泊松流布

5、、二項(xiàng)分布、泊松流( (最簡(jiǎn)單流最簡(jiǎn)單流) )、愛爾朗分布等假、愛爾朗分布等假設(shè)干種。設(shè)干種。 這是指效勞臺(tái)從隊(duì)列中選取顧客進(jìn)展效勞的順序。一般可以分為損失制、等待制和混合制等3大類。 (1)損失制。這是指如果顧客到達(dá)排隊(duì)系統(tǒng)時(shí)，所有效勞臺(tái)都被先到的顧客占用，那么他們就自動(dòng)離開系統(tǒng)永不再來。 (2)等待制 這是指當(dāng)顧客來到系統(tǒng)時(shí)，所有效勞臺(tái)都不空，顧客參加排隊(duì)行列等待效勞。等待制中，效勞臺(tái)在選擇顧客進(jìn)展效勞時(shí)常有如下四種規(guī)那么： 1)先到先效勞。按顧客到達(dá)的先后順序?qū)︻櫩瓦M(jìn)展效勞。 2)后到先效勞。 3)隨機(jī)效勞。即當(dāng)效勞臺(tái)空閑時(shí)，不按照排隊(duì)序列而隨意指定某個(gè)顧客承受效勞。 4)優(yōu)先權(quán)效勞。

6、(3)混合制 這是等待制與損失制相結(jié)合的一種效勞規(guī)那么，一般是指允許排隊(duì)，但又不允許隊(duì)列無限長(zhǎng)下去。具體說來，大致有三種： 1)隊(duì)長(zhǎng)有限。當(dāng)排隊(duì)等待效勞的顧客人數(shù)超過規(guī)定數(shù)量時(shí)，后來的顧客就自動(dòng)離去，另求效勞，即系統(tǒng)的等待空間是有限的。 2)等待時(shí)間有限。即顧客在系統(tǒng)中的等待時(shí)間不超過某一給定的長(zhǎng)度T，當(dāng)?shù)却龝r(shí)間超過T時(shí)，顧客將自動(dòng)離去，并不再回來。 3)逗留時(shí)間(等待時(shí)間與效勞時(shí)間之和)有限。 l (1)效勞臺(tái)數(shù)量及構(gòu)成形式。從數(shù)量上說，效勞臺(tái)有單效勞臺(tái)和多效勞臺(tái)之分。從構(gòu)成形式上看，效勞臺(tái)有：?jiǎn)侮?duì)單效勞臺(tái)式；單隊(duì)-多效勞臺(tái)并聯(lián)式;多隊(duì)多效勞臺(tái)并聯(lián)式；單隊(duì)多效勞臺(tái)串聯(lián)式；單隊(duì)多效勞臺(tái)并串聯(lián)混

7、合式，以及多隊(duì)多效勞臺(tái)并串聯(lián)混合式等等。l (2)效勞方式。這是指在某一時(shí)刻承受效勞的顧客數(shù)，它有單個(gè)效勞和成批效勞兩種。l (3)效勞時(shí)間的分布。在多數(shù)情況下，對(duì)每一個(gè)顧客的效勞時(shí)間是一隨機(jī)變量。描述符號(hào)：描述符號(hào)：/ 各符號(hào)的意義：各符號(hào)的意義： 表示顧客相繼到達(dá)間隔時(shí)間分布，常用以表示顧客相繼到達(dá)間隔時(shí)間分布，常用以下符號(hào)：下符號(hào)： M表示到達(dá)的過程為泊松過程或負(fù)指數(shù)表示到達(dá)的過程為泊松過程或負(fù)指數(shù)分布；分布； D表示定長(zhǎng)輸入；表示定長(zhǎng)輸入； EK表示表示K階愛爾朗分布；階愛爾朗分布； G表示一般相互獨(dú)立的隨機(jī)分布。表示一般相互獨(dú)立的隨機(jī)分布。 表示效勞時(shí)間分布，所用符號(hào)與表示顧客到達(dá)間

8、隔時(shí)間分布一樣。表示效勞臺(tái)(員)個(gè)數(shù)：“1表示單個(gè)效勞臺(tái)，“s(s1)表示多個(gè)效勞臺(tái)。 表示系統(tǒng)中顧客容量限額，或稱等待空間容量。如系統(tǒng)有K個(gè)等待位子，那么，0K1)個(gè)效勞臺(tái)；系統(tǒng)等待空間容量無限(等待制)；顧客源無限，采用先到先效勞規(guī)那么。 某些情況下，排隊(duì)問題僅用上述表達(dá)形式中的前3個(gè)符號(hào)。例如，某排隊(duì)問題為MMS， 如不特別說明那么均理解為系統(tǒng)等待空間容量無限；顧客源無限，先到先效勞，單個(gè)效勞的等待制系統(tǒng)。 描述一個(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ù)與正在承受效勞的顧客數(shù)之和)；排隊(duì)長(zhǎng)是指系統(tǒng)中正在排隊(duì)等待效勞的顧客數(shù)。

9、隊(duì)長(zhǎng)和排隊(duì)長(zhǎng)一般都是隨機(jī)變量。 2等待時(shí)間和逗留時(shí)間 從顧客到達(dá)時(shí)刻起到他開場(chǎng)承受效勞止這段時(shí)間稱為等待時(shí)間。等待時(shí)間是個(gè)隨機(jī)變量。從顧客到達(dá)時(shí)刻起到他承受效勞完成止這段時(shí)間稱為逗留時(shí)間，也是隨機(jī)變量。 3. 忙期和閑期 忙期是指從顧客到達(dá)空閑著的效勞機(jī)構(gòu)起，到效勞機(jī)構(gòu)再次成為空閑止的這段時(shí)間，即效勞機(jī)構(gòu)連續(xù)忙的時(shí)間。這是個(gè)隨機(jī)變量，是效勞員最為關(guān)心的指標(biāo)，因?yàn)樗P(guān)系到效勞員的效勞強(qiáng)度。與忙期相對(duì)的是閑期,即效勞機(jī)構(gòu)連續(xù)保持空閑的時(shí)間。在排隊(duì)系統(tǒng)中，忙期和閑期總是交替出現(xiàn)的。 4數(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)

10、系統(tǒng)任一時(shí)刻等待效勞的顧客數(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)效勞臺(tái)的數(shù)目； 平均到達(dá)率；1平均到達(dá)間隔； 平均效勞率；1/平均效勞時(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í)間； 全部空閑的概率；即穩(wěn)態(tài)系統(tǒng)所有服務(wù)臺(tái)），時(shí)（系統(tǒng)中顧客數(shù)為特別當(dāng)?shù)母怕?；為穩(wěn)態(tài)系統(tǒng)任一時(shí)刻狀態(tài)000nn:PnNPPn效勞強(qiáng)度，即每個(gè)效勞臺(tái)單位時(shí)間內(nèi)的平均效勞時(shí)間，般有=(s)，這是衡量排隊(duì)系統(tǒng)

11、繁忙程度的重要尺度，當(dāng)趨近于0時(shí)，說明對(duì)期望效勞的數(shù)量來說，效勞能力相對(duì)地說是很大的。這時(shí)，等待時(shí)間一定很短，效勞臺(tái)有大量的空閑時(shí)間；如效勞強(qiáng)度趨近于1，那么效勞臺(tái)空閑時(shí)間較少而顧客等待時(shí)間較多。我們一般都假定平均效勞率大于平均到達(dá)率，即/1,否那么排隊(duì)的人數(shù)會(huì)越來越多，以后總是保持這個(gè)假設(shè)而不再聲明。l 在系統(tǒng)到達(dá)穩(wěn)態(tài)時(shí)，假定平均到達(dá)率為常數(shù)，平均效勞時(shí)間為常數(shù)1/，那么有下面的李特爾公式：l L= W l Lq= Wq l W= Wq +1/l L= Lq +/ 排隊(duì)系統(tǒng)運(yùn)行情況的分析，就是在給定輸人與效勞條件下，通過求解系統(tǒng)狀態(tài)為n(有n個(gè)顧客)的概率Pn，再進(jìn)展計(jì)算其主要的運(yùn)行指標(biāo)：

12、系統(tǒng)中顧客數(shù)(隊(duì)長(zhǎng))的期望值L； 排隊(duì)等待的顧客數(shù)(排隊(duì)長(zhǎng))的期望值Lq； 顧客在系統(tǒng)中全部時(shí)間(逗留時(shí)間)的期望值W； 顧客排隊(duì)等待時(shí)間的期望值Wq。模型的條件是：1、輸入過程顧客源是無限的，顧客到達(dá)完全是隨機(jī)的，單個(gè)到來，到達(dá)過程服從普阿松分布，且是平穩(wěn)的；2、排隊(duì)規(guī)那么單隊(duì)，且隊(duì)長(zhǎng)沒有限制，先到先效勞；3、效勞機(jī)構(gòu)單效勞臺(tái)，效勞時(shí)間的長(zhǎng)短是隨機(jī)的，服從一樣的指數(shù)分布 。 10P)1 (nnP1LLLq1)(221WWWq)(1)(kkNP 某醫(yī)院急診室同時(shí)只能診治一個(gè)病人，診某醫(yī)院急診室同時(shí)只能診治一個(gè)病人，診治時(shí)間服從指數(shù)分布，每個(gè)病人平均需要治時(shí)間服從指數(shù)分布，每個(gè)病人平均需要151

13、5分鐘。分鐘。病人按泊松分布到達(dá)，平均每小時(shí)到達(dá)病人按泊松分布到達(dá)，平均每小時(shí)到達(dá)3 3人。試人。試對(duì)此排隊(duì)隊(duì)系統(tǒng)進(jìn)展分析。對(duì)此排隊(duì)隊(duì)系統(tǒng)進(jìn)展分析。解解 對(duì)此排隊(duì)隊(duì)系統(tǒng)分析如下：對(duì)此排隊(duì)隊(duì)系統(tǒng)分析如下：1 1先確定參數(shù)值：這是單效勞臺(tái)系統(tǒng)，有：先確定參數(shù)值：這是單效勞臺(tái)系統(tǒng)，有： 故效勞強(qiáng)度為：故效勞強(qiáng)度為：hhh/4/1560,/3人人人75. 04375. 010P25. 075. 0110P人人3343L人人25. 275. 03LLqmin6013411hhWmin4575. 075. 01hhWWq211Wmin12511h9 . 0) 1(1) 1(xNPxNP1 . 0) 1(

14、xNP1 . 021)1(xx1 . 021)1(xx875. 0lg1lg1 . 0lg2xl此模型與M/M/1模型不同之處在于有S個(gè)效勞臺(tái)，各效勞臺(tái)的工作相互獨(dú)立，效勞率相等，如果顧客到達(dá)時(shí)，S個(gè)效勞臺(tái)都忙著，那么排成一隊(duì)等待，先到先效勞的單隊(duì)模型。l整個(gè)系統(tǒng)的平均效勞率為s，*/s，*0Q0）0.750.750 02020L Lq q2.252.25人人0 01212人人L L3 3人人0 08787人人W W60min60min17174min4minW Wq q45min45min2 24min4min.3,qq0NPWWLLP，1430.93，SS 0748

15、. 03/2.251132.2522.2512.2502.251132100！整個(gè)掛號(hào)間空閑的概率P 人稱隊(duì)列長(zhǎng)等待掛號(hào)的平均人數(shù)或7 . 10748. 0!34/32.2523qL 人稱隊(duì)長(zhǎng)掛號(hào)間平均逗留人數(shù)或95. 325. 27 . 13qLL 分鐘在掛號(hào)間平均逗留時(shí)間分鐘等候掛號(hào)的平均時(shí)間4.390.411.89589.19 .07 .14WWq 57. 00748. 04/132.253363！閑）的概率人或各掛號(hào)員都沒有空者不少于（即系統(tǒng)中就診就診者到達(dá)后必須等待NP 表表6 62 2 兩個(gè)模型的比較兩個(gè)模型的比較指標(biāo)指標(biāo)（1 1）M/M/3M/M/3型型（2 2）M/M/1M/M

16、/1型型掛號(hào)間空閑掛號(hào)間空閑的概率的概率0.07480.07480.250.25（各子系統(tǒng)）（各子系統(tǒng)）就診者必須等待就診者必須等待的概率的概率P(N3)= 0.57P(N3)= 0.570.750.75平均隊(duì)列長(zhǎng)平均隊(duì)列長(zhǎng)1.71.7（人）（人）2.252.25（人）（人）（各子系統(tǒng)）（各子系統(tǒng)）平均隊(duì)長(zhǎng)平均隊(duì)長(zhǎng)3.953.95（人）（人）9 9（人）（人）（整個(gè)系統(tǒng)）（整個(gè)系統(tǒng)）平均逗留時(shí)間平均逗留時(shí)間4.394.39（分鐘）（分鐘）1010（分鐘）（分鐘）平均等待時(shí)間平均等待時(shí)間1.891.89（分鐘）（分鐘）7.57.5（分鐘）（分鐘）1思考題1排隊(duì)論主要研究的問題是什么？2試述排隊(duì)系統(tǒng)的根本組成局部。3理解平均到達(dá)率、平均效勞率、平均效勞時(shí)間和顧客到達(dá)間隔時(shí)間等概念。4試述隊(duì)長(zhǎng)和排隊(duì)長(zhǎng)、等待時(shí)間和逗留時(shí)間、忙期和閑期等概念。2設(shè)有一個(gè)醫(yī)院門診，只有一個(gè)值班醫(yī)生。病人的到達(dá)過程為泊松流，平均到達(dá)時(shí)間間隔為20min，診斷時(shí)間服從負(fù)指數(shù)分布，平均需12min，求：