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

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

2、一、排隊系統(tǒng)的描述 二、排隊系統(tǒng)的主要數(shù)量指標l (一)系統(tǒng)特征和基本排隊過程l (二)排隊系統(tǒng)的基本組成部分l（三)排隊系統(tǒng)的描述符號l相似的特征及數(shù)學抽象相似的特征及數(shù)學抽象： (1)請求服務(wù)的人或者物顧客； (2)為顧客服務(wù)的人或者物，即服務(wù)員或服務(wù)臺； (3)顧客到達系統(tǒng)的時刻是隨機的，為每一位顧客提供服務(wù)的時間是隨機的，因而整個排隊系統(tǒng)的狀態(tài)也是隨機的。l基本排隊過程基本排隊過程 可以用圖 6表示。從圖 6可知，每個顧客由顧客源按一定方式到達服務(wù)系統(tǒng)，首先加入隊列排隊等待接受服務(wù)，然后服務(wù)臺按一定規(guī)則從隊列中選擇顧客進行服務(wù)，獲得服務(wù)的顧客立即離開。 排隊系統(tǒng)由排隊系統(tǒng)由3 3個部分

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

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

5、，那么他們就自動離開系統(tǒng)永不再來。 (2)(2)等待制等待制 這是指當顧客來到系統(tǒng)時，所有服務(wù)臺都不空，顧客加入排隊行列等待服務(wù)。等待制中，服務(wù)臺在選擇顧客進行服務(wù)時常有如下四種規(guī)則： 1)先到先服務(wù)。按顧客到達的先后順序?qū)︻櫩瓦M行服務(wù)。 2)后到先服務(wù)。 3)隨機服務(wù)。即當服務(wù)臺空閑時，不按照排隊序列而隨意指定某個顧客接受服務(wù)。 4)優(yōu)先權(quán)服務(wù)。 (3)(3)混合制混合制 這是等待制與損失制相結(jié)合的一種服務(wù)規(guī)則，一般是指允許排隊，但又不允許隊列無限長下去。具體說來，大致有三種： 1)隊長有限。當排隊等待服務(wù)的顧客人數(shù)超過規(guī)定數(shù)量時，后來的顧客就自動離去，另求服務(wù)，即系統(tǒng)的等待空間是有限的。

6、2)等待時間有限。即顧客在系統(tǒng)中的等待時間不超過某一給定的長度T，當?shù)却龝r間超過T時，顧客將自動離去，并不再回來。 3)逗留時間(等待時間與服務(wù)時間之和)有限。 l (1)(1)服務(wù)臺數(shù)量及構(gòu)成形式服務(wù)臺數(shù)量及構(gòu)成形式。從數(shù)量上說，服務(wù)臺有單服務(wù)臺和多服務(wù)臺之分。從構(gòu)成形式上看，服務(wù)臺有：單隊單服務(wù)臺式；單隊-多服務(wù)臺并聯(lián)式;多隊多服務(wù)臺并聯(lián)式；單隊多服務(wù)臺串聯(lián)式；單隊多服務(wù)臺并串聯(lián)混合式，以及多隊多服務(wù)臺并串聯(lián)混合式等等。l (2)(2)服務(wù)方式服務(wù)方式。這是指在某一時刻接受服務(wù)的顧客數(shù)，它有單個服務(wù)和成批服務(wù)兩種。l (3)(3)服務(wù)時間的分布服務(wù)時間的分布。在多數(shù)情況下，對每一個顧客的服

7、務(wù)時間是一隨機變量。描述符號描述符號：/ 各符號的意義各符號的意義： 表示顧客相繼到達間隔時間分布，常用下列符號： M表示到達的過程為泊松過程或負指數(shù)分布； D表示定長輸入； EK表示K階愛爾朗分布； G表示一般相互獨立的隨機分布。 表示服務(wù)時間分布，所用符號與表示顧客到達間隔時間分布相同。表示服務(wù)臺(員)個數(shù)：“1”表示單個服務(wù)臺，“s”(s1)表示多個服務(wù)臺。 表示系統(tǒng)中顧客容量限額，或稱等待空間容量。如系統(tǒng)有K個等待位子，則，0K1)個服務(wù)臺；系統(tǒng)等待空間容量無限(等待制)；顧客源無限，采用先到先服務(wù)規(guī)則。 某些情況下，排隊問題僅用上述表達形式中的前3個符號。例如，某排隊問題為MMS，

8、如不特別說明則均理解為系統(tǒng)等待空間容量無限；顧客源無限，先到先服務(wù)，單個服務(wù)的等待制系統(tǒng)。 描述一個排隊系統(tǒng)運行狀況的主要數(shù)量指標有： 1 1隊長和排隊長隊長和排隊長(隊列長) 隊長是指系統(tǒng)中的顧客數(shù)(排隊等待的顧客數(shù)與正在接受服務(wù)的顧客數(shù)之和)；排隊長是指系統(tǒng)中正在排隊等待服務(wù)的顧客數(shù)。隊長和排隊長一般都是隨機變量。 2 2等待時間和逗留時間等待時間和逗留時間 從顧客到達時刻起到他開始接受服務(wù)止這段時間稱為等待時間。等待時間是個隨機變量。從顧客到達時刻起到他接受服務(wù)完成止這段時間稱為逗留時間，也是隨機變量。 3.3. 忙期和閑期忙期和閑期 忙期是指從顧客到達空閑著的服務(wù)機構(gòu)起，到服務(wù)機構(gòu)再次

9、成為空閑止的這段時間，即服務(wù)機構(gòu)連續(xù)忙的時間。這是個隨機變量，是服務(wù)員最為關(guān)心的指標，因為它關(guān)系到服務(wù)員的服務(wù)強度。與忙期相對的是閑期,即服務(wù)機構(gòu)連續(xù)保持空閑的時間。在排隊系統(tǒng)中，忙期和閑期總是交替出現(xiàn)的。 4 4數(shù)量指標的常用記號數(shù)量指標的常用記號 (1)(1)主要數(shù)量指標主要數(shù)量指標L平均隊長，即穩(wěn)態(tài)系統(tǒng)任一時刻的所有顧客數(shù) 的期望值；Lq平均等待隊長，即穩(wěn)態(tài)系統(tǒng)任一時刻等待服務(wù)的顧客數(shù)的期望值；W平均逗留時間，即(在任意時刻)進入穩(wěn)態(tài)系統(tǒng)的顧客逗留時間的期望值；Wq平均等待時間，即(在任意時刻)進入穩(wěn)態(tài)系統(tǒng)的顧客等待時間的期望值。 (2)(2)其他常用數(shù)量指標其他常用數(shù)量指標 s系統(tǒng)中并

10、聯(lián)服務(wù)臺的數(shù)目； 平均到達率；1平均到達間隔； 平均服務(wù)率；1/平均服務(wù)時間；N穩(wěn)態(tài)系統(tǒng)任一時刻的狀態(tài)（即系統(tǒng)中所有顧客數(shù)）；U任一顧客在穩(wěn)態(tài)系統(tǒng)中的逗留時間；Q任一顧客在穩(wěn)態(tài)系統(tǒng)中的等待時間； 全部空閑的概率；即穩(wěn)態(tài)系統(tǒng)所有服務(wù)臺），時（系統(tǒng)中顧客數(shù)為特別當?shù)母怕?；為穩(wěn)態(tài)系統(tǒng)任一時刻狀態(tài)000nn:PnNPPn服務(wù)強度，即每個服務(wù)臺單位時間內(nèi)的平均服務(wù)時間，般有=(s)，這是衡量排隊系統(tǒng)繁忙程度的重要尺度，當趨近于0時，表明對期望服務(wù)的數(shù)量來說，服務(wù)能力相對地說是很大的。這時，等待時間一定很短，服務(wù)臺有大量的空閑時間；如服務(wù)強度趨近于1，那么服務(wù)臺空閑時間較少而顧客等待時間較多。我們一般都假

11、定平均服務(wù)率大于平均到達率，即/1,否則排隊的人數(shù)會越來越多，以后總是保持這個假設(shè)而不再聲明。l 在系統(tǒng)達到穩(wěn)態(tài)時，假定平均到達率為常數(shù)，平均服務(wù)時間為常數(shù)1/，則有下面的李特爾公式：l L= W l Lq= Wq l W= Wq +1/l L= Lq +/ 排隊系統(tǒng)運行情況的分析，就是在給定輸入與服務(wù)條件下，通過求解系統(tǒng)狀態(tài)為n(有n個顧客)的概率Pn，再進行計算其主要的運行指標： 系統(tǒng)中顧客數(shù)(隊長)的期望值L； 排隊等待的顧客數(shù)(排隊長)的期望值Lq； 顧客在系統(tǒng)中全部時間(逗留時間)的期望值W； 顧客排隊等待時間的期望值Wq。模型的條件是：1、輸入過程顧客源是無限的，顧客到達完全是隨機

12、的，單個到來，到達過程服從普阿松分布，且是平穩(wěn)的；2、排隊規(guī)則單隊，且隊長沒有限制，先到先服務(wù)；3、服務(wù)機構(gòu)單服務(wù)臺，服務(wù)時間的長短是隨機的，服從相同的指數(shù)分布 。 10P)1 (nnP1LLLq1)(221WWWq)(1)(kkNP 某醫(yī)院急診室同時只能診治一個病人，診某醫(yī)院急診室同時只能診治一個病人，診治時間服從指數(shù)分布，每個病人平均需要治時間服從指數(shù)分布，每個病人平均需要1515分鐘。分鐘。病人按泊松分布到達，平均每小時到達病人按泊松分布到達，平均每小時到達3 3人。試人。試對此排隊隊系統(tǒng)進行分析。對此排隊隊系統(tǒng)進行分析。解解 對此排隊隊系統(tǒng)分析如下：對此排隊隊系統(tǒng)分析如下：（1 1）先

13、確定參數(shù)值先確定參數(shù)值：這是單服務(wù)臺系統(tǒng)，有：這是單服務(wù)臺系統(tǒng)，有： 故服務(wù)強度為：故服務(wù)強度為：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個服務(wù)臺，各服務(wù)臺的工作相互獨立，服務(wù)率相等，如果顧客到達時，S個服務(wù)臺都忙著

14、，則排成一隊等待，先到先服務(wù)的單隊模型。l整個系統(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！整個掛號間空閑的概率P 人稱隊列長等待掛號的平均人數(shù)或7 . 10748. 0!34/32.2523qL 人稱隊長掛號間平均逗留人數(shù)或

15、95. 325. 27 . 13qLL 分鐘在掛號間平均逗留時間分鐘等候掛號的平均時間4.390.411.89589.19 .07 .14WWq 57. 00748. 04/132.253363！閑）的概率人或各掛號員都沒有空者不少于（即系統(tǒng)中就診就診者到達后必須等待NP 表表2 2 兩個模型的比較兩個模型的比較指標指標（1 1）M/M/3M/M/3型型（2 2）M/M/1M/M/1型型掛號間空閑掛號間空閑的概率的概率0.07480.07480.250.25（各子系統(tǒng)）（各子系統(tǒng)）就診者必須等待就診者必須等待的概率的概率P(N3)= 0.57P(N3)= 0.570.750.75平均隊列長平均

16、隊列長1.71.7（人）（人）2.252.25（人）（人）（各子系統(tǒng)）（各子系統(tǒng)）平均隊長平均隊長3.953.95（人）（人）9 9（人）（人）（整個系統(tǒng)）（整個系統(tǒng)）平均逗留時間平均逗留時間4.394.39（分鐘）（分鐘）1010（分鐘）（分鐘）平均等待時間平均等待時間1.891.89（分鐘）（分鐘）7.57.5（分鐘）（分鐘）1思考題（1）排隊論主要研究的問題是什么？（2）試述排隊系統(tǒng)的基本組成部分。（3）理解平均到達率、平均服務(wù)率、平均服務(wù)時間和顧客到達間隔時間等概念。（4）試述隊長和排隊長、等待時間和逗留時間、忙期和閑期等概念。2設(shè)有一個醫(yī)院門診，只有一個值班醫(yī)生。病人的到達過程為泊松流，平均到達時間間隔為20min，診斷時間服從負指數(shù)分布，平均需12min，求