數(shù)學(xué)建模-排隊(duì)論及其應(yīng)用)

1、隨機(jī)服務(wù)系統(tǒng)理論 l排隊(duì)系統(tǒng)描述l基本概念基本概念 lM / M / 1 模型模型lM / M / S 模型l顧客要求服務(wù)的對(duì)象統(tǒng)稱為“顧客”l服務(wù)臺(tái)把提供服務(wù)的人或機(jī)構(gòu)稱 為“服務(wù)臺(tái)”或“服務(wù)員” l 面對(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ì)如何做到既保證一定的服務(wù)質(zhì)量指標(biāo)，又使服務(wù)設(shè)施費(fèi)用經(jīng)濟(jì)合理量指標(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)題。

2、一、排隊(duì)系統(tǒng)的描述 二、排隊(duì)系統(tǒng)的主要數(shù)量指標(biāo)l (一)系統(tǒng)特征和基本排隊(duì)過(guò)程l (二)排隊(duì)系統(tǒng)的基本組成部分l（三)排隊(duì)系統(tǒng)的描述符號(hào)l相似的特征及數(shù)學(xué)抽象相似的特征及數(shù)學(xué)抽象： (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)也是隨機(jī)的。l基本排隊(duì)過(guò)程基本排隊(duì)過(guò)程 可以用圖 6表示。從圖 6可知，每個(gè)顧客由顧客源按一定方式到達(dá)服務(wù)系統(tǒng)，首先加入隊(duì)列排隊(duì)等待接受服務(wù)，然后服務(wù)臺(tái)按一定規(guī)則從隊(duì)列中選擇顧客進(jìn)行服務(wù)，獲得服務(wù)的顧客立即離開(kāi)。 排隊(duì)系統(tǒng)由排隊(duì)系統(tǒng)由3 3個(gè)部分

3、組成個(gè)部分組成 1、輸入過(guò)程 2、服務(wù)規(guī)則 3、服務(wù)臺(tái) 這是指要求服務(wù)的顧客是按怎樣的規(guī)律到達(dá)排隊(duì)這是指要求服務(wù)的顧客是按怎樣的規(guī)律到達(dá)排隊(duì)系統(tǒng)的過(guò)程，有時(shí)也把它稱為系統(tǒng)的過(guò)程，有時(shí)也把它稱為顧客流顧客流。一般可以從。一般可以從3 3個(gè)方面來(lái)描述一個(gè)輸入過(guò)程。個(gè)方面來(lái)描述一個(gè)輸入過(guò)程。 (1)(1)顧客總體數(shù)顧客總體數(shù)，又稱顧客源、輸入源。這是指顧客的，又稱顧客源、輸入源。這是指顧客的來(lái)源。顧客源可以是有限的，也可以是無(wú)限的。來(lái)源。顧客源可以是有限的，也可以是無(wú)限的。 (2)(2)顧客到達(dá)方式顧客到達(dá)方式。這是描述顧客是怎樣來(lái)到系統(tǒng)的，。這是描述顧客是怎樣來(lái)到系統(tǒng)的，是單個(gè)到達(dá)，還是成批到達(dá)。

4、是單個(gè)到達(dá)，還是成批到達(dá)。 (3)(3)顧客流的概率分布顧客流的概率分布，或稱相繼顧客到達(dá)的時(shí)間間隔，或稱相繼顧客到達(dá)的時(shí)間間隔的分布。的分布。這是求解排隊(duì)系統(tǒng)有關(guān)運(yùn)行指標(biāo)問(wèn)題時(shí)，首這是求解排隊(duì)系統(tǒng)有關(guān)運(yùn)行指標(biāo)問(wèn)題時(shí)，首先需要確定的指標(biāo)先需要確定的指標(biāo)。顧客流的概率分布一般有定長(zhǎng)分。顧客流的概率分布一般有定長(zhǎng)分布、二項(xiàng)分布、泊松流布、二項(xiàng)分布、泊松流( (最簡(jiǎn)單流最簡(jiǎn)單流) )、愛(ài)爾朗分布等若、愛(ài)爾朗分布等若干種。干種。 這是指服務(wù)臺(tái)從隊(duì)列中選取顧客進(jìn)行服務(wù)的順序。一般可以分為損失制、等待制和混合制等3大類。 (1)(1)損失制損失制。這是指如果顧客到達(dá)排隊(duì)系統(tǒng)時(shí)，所有服務(wù)臺(tái)都被先到的顧客占用

5、，那么他們就自動(dòng)離開(kāi)系統(tǒng)永不再來(lái)。 (2)(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ù)。 (3)(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)的等待空間是有限的。

6、2)等待時(shí)間有限。即顧客在系統(tǒng)中的等待時(shí)間不超過(guò)某一給定的長(zhǎng)度T，當(dāng)?shù)却龝r(shí)間超過(guò)T時(shí)，顧客將自動(dòng)離去，并不再回來(lái)。 3)逗留時(shí)間(等待時(shí)間與服務(wù)時(shí)間之和)有限。 l (1)(1)服務(wù)臺(tái)數(shù)量及構(gòu)成形式服務(wù)臺(tái)數(shù)量及構(gòu)成形式。從數(shù)量上說(shuō)，服務(wù)臺(tái)有單服務(wù)臺(tái)和多服務(wù)臺(tái)之分。從構(gòu)成形式上看，服務(wù)臺(tái)有：?jiǎn)侮?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)混合式等等。l (2)(2)服務(wù)方式服務(wù)方式。這是指在某一時(shí)刻接受服務(wù)的顧客數(shù)，它有單個(gè)服務(wù)和成批服務(wù)兩種。l (3)(3)服務(wù)時(shí)間的分布服務(wù)時(shí)間的分布。在多數(shù)情況下，對(duì)每一個(gè)顧客的服

7、務(wù)時(shí)間是一隨機(jī)變量。描述符號(hào)描述符號(hào)：/ 各符號(hào)的意義各符號(hào)的意義： 表示顧客相繼到達(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”(s1)表示多個(gè)服務(wù)臺(tái)。 表示系統(tǒng)中顧客容量限額，或稱等待空間容量。如系統(tǒng)有K個(gè)等待位子，則，0K1)個(gè)服務(wù)臺(tái)；系統(tǒng)等待空間容量無(wú)限(等待制)；顧客源無(wú)限，采用先到先服務(wù)規(guī)則。 某些情況下，排隊(duì)問(wèn)題僅用上述表達(dá)形式中的前3個(gè)符號(hào)。例如，某排隊(duì)問(wèn)題為MMS，

8、如不特別說(shuō)明則均理解為系統(tǒng)等待空間容量無(wú)限；顧客源無(wú)限，先到先服務(wù)，單個(gè)服務(wù)的等待制系統(tǒng)。 描述一個(gè)排隊(duì)系統(tǒng)運(yùn)行狀況的主要數(shù)量指標(biāo)有： 1 1隊(duì)長(zhǎng)和排隊(duì)長(zhǎng)隊(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ī)變量。 2 2等待時(shí)間和逗留時(shí)間等待時(shí)間和逗留時(shí)間 從顧客到達(dá)時(shí)刻起到他開(kāi)始接受服務(wù)止這段時(shí)間稱為等待時(shí)間。等待時(shí)間是個(gè)隨機(jī)變量。從顧客到達(dá)時(shí)刻起到他接受服務(wù)完成止這段時(shí)間稱為逗留時(shí)間，也是隨機(jī)變量。 3.3. 忙期和閑期忙期和閑期 忙期是指從顧客到達(dá)空閑著的服務(wù)機(jī)構(gòu)起，到服務(wù)機(jī)構(gòu)再次

9、成為空閑止的這段時(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)的。 4 4數(shù)量指標(biāo)的常用記號(hào)數(shù)量指標(biāo)的常用記號(hào) (1)(1)主要數(shù)量指標(biāo)主要數(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)(2)其他常用數(shù)量指標(biāo)其他常用數(shù)量指標(biāo) s系統(tǒng)中并

10、聯(lián)服務(wù)臺(tái)的數(shù)目； 平均到達(dá)率；1平均到達(dá)間隔； 平均服務(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í)間； 全部空閑的概率；即穩(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服務(wù)強(qiáng)度，即每個(gè)服務(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í)間較多。我們一般都假

11、定平均服務(wù)率大于平均到達(dá)率，即/1,否則排隊(duì)的人數(shù)會(huì)越來(lái)越多，以后總是保持這個(gè)假設(shè)而不再聲明。l 在系統(tǒng)達(dá)到穩(wěn)態(tài)時(shí)，假定平均到達(dá)率為常數(shù)，平均服務(wù)時(shí)間為常數(shù)1/，則有下面的李特爾公式：l L= W l Lq= Wq l W= Wq +1/l L= Lq +/ 排隊(duì)系統(tǒng)運(yùn)行情況的分析，就是在給定輸入與服務(wù)條件下，通過(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。模型的條件是：1、輸入過(guò)程顧客源是無(wú)限的，顧客到達(dá)完全是隨機(jī)

12、的，單個(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)，服務(wù)時(shí)間的長(zhǎng)短是隨機(jī)的，服從相同的指數(shù)分布 。 10P)1 (nnP1LLLq1)(221WWWq)(1)(kkNP 某醫(yī)院急診室同時(shí)只能診治一個(gè)病人，診某醫(yī)院急診室同時(shí)只能診治一個(gè)病人，診治時(shí)間服從指數(shù)分布，每個(gè)病人平均需要治時(shí)間服從指數(shù)分布，每個(gè)病人平均需要1515分鐘。分鐘。病人按泊松分布到達(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）先

13、確定參數(shù)值先確定參數(shù)值：這是單服務(wù)臺(tái)系統(tǒng)，有：這是單服務(wù)臺(tái)系統(tǒng)，有： 故服務(wù)強(qiáng)度為：故服務(wù)強(qiáng)度為：hhh/4/1560,/3人人人75. 04375. 010P25. 075. 0110P人人3343L人人25. 275. 03LLqmin6013411hhWmin4575. 075. 01hhWWq211Wmin12511h9 . 0) 1(1) 1(xNPxNP1 . 0) 1( xNP1 . 021)1(xx1 . 021)1(xx875. 0lg1lg1 . 0lg2xl此模型與M/M/1模型不同之處在于有S個(gè)服務(wù)臺(tái)，各服務(wù)臺(tái)的工作相互獨(dú)立，服務(wù)率相等，如果顧客到達(dá)時(shí)，S個(gè)服務(wù)臺(tái)都忙著

14、，則排成一隊(duì)等待，先到先服務(wù)的單隊(duì)模型。l整個(gè)系統(tǒng)的平均服務(wù)率為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. 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ù)或

15、95. 325. 27 . 13qLL 分鐘在掛號(hào)間平均逗留時(shí)間分鐘等候掛號(hào)的平均時(shí)間4.390.411.89589.19 .07 .14WWq 57. 00748. 04/132.253363！閑）的概率人或各掛號(hào)員都沒(méi)有空者不少于（即系統(tǒng)中就診就診者到達(dá)后必須等待NP 表表2 2 兩個(gè)模型的比較兩個(gè)模型的比較指標(biāo)指標(biāo)（1 1）M/M/3M/M/3型型（2 2）M/M/1M/M/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)平均

16、隊(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ì)論主要研究的問(wèn)題是什么？（2）試述排隊(duì)系統(tǒng)的基本組成部分。（3）理解平均到達(dá)率、平均服務(wù)率、平均服務(wù)時(shí)間和顧客到達(dá)間隔時(shí)間等概念。（4）試述隊(duì)長(zhǎng)和排隊(duì)長(zhǎng)、等待時(shí)間和逗留時(shí)間、忙期和閑期等概念。2設(shè)有一個(gè)醫(yī)院門診，只有一個(gè)值班醫(yī)生。病人的到達(dá)過(guò)程為泊松流，平均到達(dá)時(shí)間間隔為20min，診斷時(shí)間服從負(fù)指數(shù)分布，平均需12min，求