數(shù)學(xué)建模排隊論模型

1、.排排 隊隊 論論 模模 型型 .排隊論模型排隊論模型 一、排隊論的基本概念一、排隊論的基本概念 二、單通道等待制排隊問題二、單通道等待制排隊問題 （MM1排隊系統(tǒng)）排隊系統(tǒng)）三、多通道等待制排隊問題三、多通道等待制排隊問題 （MMc排隊系統(tǒng)）排隊系統(tǒng)） .一、排隊論的基本概念一、排隊論的基本概念（一）排隊過程（一）排隊過程 1.1.排隊系統(tǒng)排隊系統(tǒng) “排隊排隊”是指在服務(wù)機(jī)構(gòu)處要求服務(wù)對象的一個是指在服務(wù)機(jī)構(gòu)處要求服務(wù)對象的一個等待隊列，而等待隊列，而“排隊論排隊論”則是研究各種排隊現(xiàn)象的理則是研究各種排隊現(xiàn)象的理論。論。 到來 服服務(wù)務(wù)規(guī)規(guī)則則 服服 離離去去 顧顧客客源源 排排隊隊機(jī)機(jī)構(gòu)

2、構(gòu) 務(wù)務(wù) 機(jī)機(jī) 構(gòu)構(gòu) 排排隊隊系系統(tǒng)統(tǒng) . 在排隊論中，我們把要求服務(wù)的對象稱為在排隊論中，我們把要求服務(wù)的對象稱為“顧客顧客”，而將從事服務(wù)的機(jī)構(gòu)或人稱為，而將從事服務(wù)的機(jī)構(gòu)或人稱為“服務(wù)服務(wù)臺臺”。 在顧客到達(dá)服務(wù)臺時，可能立即得到服在顧客到達(dá)服務(wù)臺時，可能立即得到服務(wù)，也可能要等待到可以利用服務(wù)臺的時候為止。務(wù)，也可能要等待到可以利用服務(wù)臺的時候為止。. 排隊系統(tǒng)隊列除了有形的還有無形的排隊系統(tǒng)隊列除了有形的還有無形的。 排隊系統(tǒng)中的排隊系統(tǒng)中的“顧客顧客”與與“服務(wù)臺服務(wù)臺”這兩個名這兩個名詞可以從不同的角度去理解。詞可以從不同的角度去理解。排隊系統(tǒng)排隊系統(tǒng)顧客顧客服務(wù)臺服務(wù)臺上、下班

3、的工人乘公共汽車上、下班的工人乘公共汽車工人工人公共汽車公共汽車病人到醫(yī)院看病病人到醫(yī)院看病病人病人醫(yī)生醫(yī)生高炮擊退敵機(jī)高炮擊退敵機(jī)敵機(jī)敵機(jī)高炮高炮機(jī)器發(fā)生故障需要維修機(jī)器發(fā)生故障需要維修機(jī)器機(jī)器修理工修理工. 在上述顧客在上述顧客- -服務(wù)臺組成的排隊系統(tǒng)中，顧客到服務(wù)臺組成的排隊系統(tǒng)中，顧客到來的時刻與服務(wù)臺進(jìn)行服務(wù)的時間一般來說是隨不來的時刻與服務(wù)臺進(jìn)行服務(wù)的時間一般來說是隨不同的時機(jī)與條件而變化的，往往預(yù)先無法確定。因同的時機(jī)與條件而變化的，往往預(yù)先無法確定。因此，系統(tǒng)的狀態(tài)是隨機(jī)的，故而排隊論也稱此，系統(tǒng)的狀態(tài)是隨機(jī)的，故而排隊論也稱隨機(jī)服隨機(jī)服務(wù)系統(tǒng)務(wù)系統(tǒng)。. 各式各樣的排隊現(xiàn)象呈

4、現(xiàn)的基本特征：排隊系統(tǒng)各式各樣的排隊現(xiàn)象呈現(xiàn)的基本特征：排隊系統(tǒng)由輸入過程、排隊規(guī)則及服務(wù)機(jī)構(gòu)三部分組成。由輸入過程、排隊規(guī)則及服務(wù)機(jī)構(gòu)三部分組成。(1)(1)輸入過程輸入過程 輸入過程就是顧客按怎樣的規(guī)律到達(dá)輸入過程就是顧客按怎樣的規(guī)律到達(dá)包括顧客總體數(shù)，是有限的還是無限的；包括顧客總體數(shù)，是有限的還是無限的；顧客到達(dá)的方式，是成批到達(dá)顧客到達(dá)的方式，是成批到達(dá)( (每批數(shù)量是隨機(jī)的每批數(shù)量是隨機(jī)的還是確定性的還是確定性的) )還是單個到達(dá)；還是單個到達(dá)；相繼到達(dá)的顧客相繼到達(dá)的顧客( (或批或單個或批或單個) )之間的時間間隔的分之間的時間間隔的分布是什么。布是什么。 2.2.排隊系統(tǒng)的組

5、成和特征排隊系統(tǒng)的組成和特征. 排隊規(guī)則是指到達(dá)的顧客以怎樣的規(guī)則接受服務(wù)。排隊規(guī)則是指到達(dá)的顧客以怎樣的規(guī)則接受服務(wù)。 1 1）損失制：）損失制：顧客到達(dá)，服務(wù)臺不空立即離去，顧客到達(dá)，服務(wù)臺不空立即離去，另求服務(wù)。另求服務(wù)。 2 2）等待制：）等待制：顧客到達(dá)，排隊等待。對等待制服顧客到達(dá)，排隊等待。對等待制服務(wù)可分為：先到先服務(wù)，后到先服務(wù)，優(yōu)先服務(wù)，隨務(wù)可分為：先到先服務(wù)，后到先服務(wù)，優(yōu)先服務(wù)，隨機(jī)服務(wù)，成批服務(wù)等。機(jī)服務(wù)，成批服務(wù)等。 3 3）混合制：）混合制：在現(xiàn)實生活中，很多服務(wù)系統(tǒng)介于在現(xiàn)實生活中，很多服務(wù)系統(tǒng)介于損失制和等待制之間，當(dāng)顧客到達(dá)時，服務(wù)臺不空就損失制和等待制之間

6、，當(dāng)顧客到達(dá)時，服務(wù)臺不空就排隊，若排隊的位置已滿就離去。排隊，若排隊的位置已滿就離去。 (2)(2)排隊規(guī)則排隊規(guī)則.服務(wù)機(jī)構(gòu)主要指服務(wù)臺的數(shù)目，服務(wù)機(jī)構(gòu)主要指服務(wù)臺的數(shù)目，多個服務(wù)臺進(jìn)行服務(wù)時，服務(wù)方式是并聯(lián)還多個服務(wù)臺進(jìn)行服務(wù)時，服務(wù)方式是并聯(lián)還是串聯(lián)；是串聯(lián)；服務(wù)時間服從什么分布等。服務(wù)時間服從什么分布等。 (3)(3)服務(wù)機(jī)構(gòu)服務(wù)機(jī)構(gòu). 1.1.排隊模型的分類排隊模型的分類這里僅針對并列的服務(wù)臺。這里僅針對并列的服務(wù)臺。 記記X X：顧客到達(dá)的時間間隔分布；顧客到達(dá)的時間間隔分布；Y Y：服務(wù)時間的服務(wù)時間的分布；分布；Z Z：服務(wù)臺數(shù)。則排隊模型：服務(wù)臺數(shù)。則排隊模型：X XY Y

7、Z Z。 常用的記號：常用的記號：M M負(fù)指數(shù)分布；負(fù)指數(shù)分布；D D確定型；確定型；EkEkk k階愛爾朗（階愛爾朗（ErlangErlang）分布；分布；GIGI一般相互獨立的隨一般相互獨立的隨機(jī)分布，機(jī)分布，G G一般隨機(jī)分布。這里主要討論一般隨機(jī)分布。這里主要討論M MM M1 1，M MM MC C。（二）排隊模型的分類及數(shù)量指標(biāo)（二）排隊模型的分類及數(shù)量指標(biāo). (1)(1)隊長隊長隊長是指系統(tǒng)中的顧客數(shù)隊長是指系統(tǒng)中的顧客數(shù)( (包括排隊等候和正在包括排隊等候和正在接受服務(wù)的顧客數(shù)接受服務(wù)的顧客數(shù)) )；等待隊長是指系統(tǒng)中等待服務(wù)的顧客數(shù)。等待隊長是指系統(tǒng)中等待服務(wù)的顧客數(shù)。 2.

8、2.排隊模型的數(shù)量指標(biāo)排隊模型的數(shù)量指標(biāo).逗留時間是指一顧客從進(jìn)入系統(tǒng)起一直到接受服逗留時間是指一顧客從進(jìn)入系統(tǒng)起一直到接受服務(wù)后離開系統(tǒng)為止所花費的時間；務(wù)后離開系統(tǒng)為止所花費的時間；等待時間是指一顧客從進(jìn)入系統(tǒng)起到接受服務(wù)時等待時間是指一顧客從進(jìn)入系統(tǒng)起到接受服務(wù)時所花費的時間。所花費的時間。 (2)(2)逗留時間逗留時間. 忙期是指從顧客到達(dá)空閑服務(wù)機(jī)構(gòu)起到服務(wù)機(jī)構(gòu)忙期是指從顧客到達(dá)空閑服務(wù)機(jī)構(gòu)起到服務(wù)機(jī)構(gòu)再次為空閑為止的這段時間，即服務(wù)機(jī)構(gòu)連續(xù)繁忙的再次為空閑為止的這段時間，即服務(wù)機(jī)構(gòu)連續(xù)繁忙的時間長度。時間長度。這是服務(wù)機(jī)構(gòu)最關(guān)心的數(shù)量指標(biāo)，因為它直接關(guān)系到這是服務(wù)機(jī)構(gòu)最關(guān)心的數(shù)量指

9、標(biāo)，因為它直接關(guān)系到服務(wù)員的工作強(qiáng)度，與忙期相對應(yīng)的是閑期，即為服服務(wù)員的工作強(qiáng)度，與忙期相對應(yīng)的是閑期，即為服務(wù)機(jī)構(gòu)連續(xù)保持空閑的時間長度。顯然，在排隊系統(tǒng)務(wù)機(jī)構(gòu)連續(xù)保持空閑的時間長度。顯然，在排隊系統(tǒng)中，忙期與閑期是交錯出現(xiàn)的。中，忙期與閑期是交錯出現(xiàn)的。 (3)(3)忙期忙期.1.1.最簡單流與最簡單流與PoissonPoisson過程過程 記隨機(jī)過程記隨機(jī)過程x x（t t）：）：t0t0為時間為時間0 0，t t內(nèi)內(nèi)流流( (事件事件) )發(fā)生的次數(shù)，例如對于隨機(jī)到來某電話交換發(fā)生的次數(shù)，例如對于隨機(jī)到來某電話交換臺的呼叫，以臺的呼叫，以x x（t t）表示該交換臺在表示該交換臺在0

10、 0，t t這段時這段時間內(nèi)收到呼叫的次數(shù)；若是服務(wù)機(jī)構(gòu)，可以用間內(nèi)收到呼叫的次數(shù)；若是服務(wù)機(jī)構(gòu)，可以用x x（t t）表示該機(jī)構(gòu)在表示該機(jī)構(gòu)在0 0，t t時間內(nèi)來到的顧客數(shù)時間內(nèi)來到的顧客數(shù)。（三）（三）PoissonPoisson流與指數(shù)分布流與指數(shù)分布.最簡單流應(yīng)最簡單流應(yīng) 具有以下特征稱具有以下特征稱0: )(ttx(1)(1)流具有平衡性流具有平衡性 對任何對任何 和和 , , 的分布只取決于的分布只取決于 而與而與 無關(guān)。無關(guān)。(2)(2)流具有無后效性流具有無后效性對互不交接的時間區(qū)間序列對互不交接的時間區(qū)間序列 ， 是一組相互獨立的隨機(jī)變量。是一組相互獨立的隨機(jī)變量。(3)(

11、3)流具有普通性流具有普通性即在即在 時間內(nèi)，事件發(fā)生多于時間內(nèi)，事件發(fā)生多于1 1次的概率為次的概率為 。 0anttt210)1 ()()(niaxtaxinttt,21a)1 (,nibaii)()(iiaxbx01)()(Prlimtaxtaxtt)( to .定理定理1 1設(shè)設(shè) 是最簡單流，則對任何是最簡單流，則對任何 和和都有都有 我們把滿足這一分布規(guī)律的隨機(jī)過程我們把滿足這一分布規(guī)律的隨機(jī)過程稱為稱為PoissonPoisson過程，最簡單流亦稱過程，最簡單流亦稱PoissonPoisson流，特別取流，特別取 得得故參數(shù)故參數(shù)表示單位時間內(nèi)事件發(fā)生次數(shù)的平均數(shù)表示單位時間內(nèi)事件

12、發(fā)生次數(shù)的平均數(shù)。0: )(ttx0a0t( t)P()( )(0,1,2,)!ktx atx akekk0: )(ttx( t)Pr( )(0,1,2,)!ktx tkekk0attxE)(.2.2.PoissonPoisson流的發(fā)生時間間隔分布流的發(fā)生時間間隔分布 當(dāng)流當(dāng)流( (過程過程) ) 構(gòu)成構(gòu)成PoissonPoisson過程時，就稱過程時，就稱為為PoissonPoisson流。設(shè)流發(fā)生的時刻依次為流。設(shè)流發(fā)生的時刻依次為 , ,，發(fā)生的時間間隔記為發(fā)生的時間間隔記為 ，其中其中 。定理定理2 2 事件流事件流 為為PoissonPoisson流的充要條件是流的充要條件是 的流

13、發(fā)生時間間隔的流發(fā)生時間間隔 相互獨立，且服從相互獨立，且服從相同的負(fù)指數(shù)分布，即相同的負(fù)指數(shù)分布，即0: )(ttxnttt,21), 2 , 1(1nttnnn00t0: )(ttx0: )(ttx n0001Prttettn. 對于單通道等待制排隊問題主要討論輸入過對于單通道等待制排隊問題主要討論輸入過程為程為PoissonPoisson流，服務(wù)時間服從負(fù)指數(shù)分布，單服流，服務(wù)時間服從負(fù)指數(shù)分布，單服務(wù)臺的情形，即務(wù)臺的情形，即M MM M1 1排隊系統(tǒng)。排隊系統(tǒng)。（一）標(biāo)準(zhǔn)模型（一）標(biāo)準(zhǔn)模型 即為即為M MM M1 1排隊系統(tǒng)。所謂標(biāo)準(zhǔn)模型，排隊系統(tǒng)。所謂標(biāo)準(zhǔn)模型，就是顧客的輸入流是參

14、數(shù)為就是顧客的輸入流是參數(shù)為的的PoissonPoisson流，每個流，每個顧客的服務(wù)時間是相互獨立的且服從參數(shù)為顧客的服務(wù)時間是相互獨立的且服從參數(shù)為的的負(fù)指數(shù)分布，單個服務(wù)臺且系統(tǒng)的容量無限負(fù)指數(shù)分布，單個服務(wù)臺且系統(tǒng)的容量無限( (排隊排隊模型分類第四個表示系統(tǒng)中允許的最大顧客數(shù)模型分類第四個表示系統(tǒng)中允許的最大顧客數(shù)) )。二、單通道等待制排隊問題二、單通道等待制排隊問題 （MMMM1 1排隊系統(tǒng)）排隊系統(tǒng)）.1.1.系統(tǒng)的系統(tǒng)的MarkovMarkov特性特性 考慮隨機(jī)過程考慮隨機(jī)過程 ，其中其中 為時刻為時刻 時時排隊系統(tǒng)中的顧客數(shù)。排隊系統(tǒng)中的顧客數(shù)。 對于任何對于任何 條件概率

15、條件概率由于輸入為由于輸入為PoissonPoisson流，服務(wù)時間服從負(fù)指數(shù)分布，流，服務(wù)時間服從負(fù)指數(shù)分布，則無論則無論 在在 處取何值，上式條件概率僅依處取何值，上式條件概率僅依賴于賴于 的值和區(qū)間的值和區(qū)間 的長度的長度 ，即即0: )(ttx)(txtnttt210112211)(,)(,)()(Prnnnnitxitxitxitx)(txnttt,21)(1ntx),(1nntt1nntt11112211)()(Pr)(,)(,)()(Prnnnnnnnnitxitxitxitxitxitx. 記時刻記時刻t t系統(tǒng)處于狀態(tài)系統(tǒng)處于狀態(tài)n n的概率的概率利用利用M MM M1 1對

16、輸入與服務(wù)時間分布的假設(shè)，在時間對輸入與服務(wù)時間分布的假設(shè)，在時間區(qū)間區(qū)間 內(nèi)，新進(jìn)入或離開顧客個數(shù)有以下結(jié)果：內(nèi)，新進(jìn)入或離開顧客個數(shù)有以下結(jié)果： 內(nèi)沒有顧客進(jìn)入內(nèi)沒有顧客進(jìn)入 內(nèi)新進(jìn)入一名顧客內(nèi)新進(jìn)入一名顧客 內(nèi)多于一名顧客進(jìn)入內(nèi)多于一名顧客進(jìn)入 內(nèi)沒有顧客離開內(nèi)沒有顧客離開 內(nèi)有一名顧客離開內(nèi)有一名顧客離開 內(nèi)多于一名顧客離開內(nèi)多于一名顧客離開2.2.排隊系統(tǒng)的穩(wěn)態(tài)解排隊系統(tǒng)的穩(wěn)態(tài)解ntxtPn)(Pr)(),(ttt)(1),(Prtotetttt)(),(Prtottetttt)(),(Prtottt)(1),(Prtotetttt)(),(Prtottetttt)(),(Prtot

17、tt. 當(dāng)當(dāng) 時有時有導(dǎo)出導(dǎo)出 滿足的微分方程組滿足的微分方程組)(tpn)()1 ()()1)()(100totttpttpttp)()()()()(1000tottpttptpttp0t)()()(100tptptp.故故 滿足的微分方程組滿足的微分方程組)()()1)(1)()()(11tottptttpttpttpnnnn)()()()()(11tptptptpnnnn對對1n)()()(, 2 , 1)()()()()(10011tptptpntptptptpnnnn)(tpn. 對于系統(tǒng)的穩(wěn)定狀態(tài)情形，對于系統(tǒng)的穩(wěn)定狀態(tài)情形， 與與t t無關(guān)，無關(guān)，故故 ，記記 ，從而有從而有對于

18、上述差分方程，利用歸納法不難求得對于上述差分方程，利用歸納法不難求得)(tpn0)( tpn)(tppnn0, 2 , 10)(1011ppnpppnnn0)(ppnn. 記記 為排隊系統(tǒng)的來往強(qiáng)度，當(dāng)為排隊系統(tǒng)的來往強(qiáng)度，當(dāng) 時，由時，由 可得可得 由于由于 構(gòu)成概率分布，則構(gòu)成概率分布，則 ，從而級數(shù)從而級數(shù) 必須收斂，故有必須收斂，故有 。 np01nnp0)(nn1101nnp, 2 , 1 , 0)1 (npnn.MMMM1 1系統(tǒng)的數(shù)量指標(biāo)系統(tǒng)的數(shù)量指標(biāo) (1)(1)穩(wěn)定狀態(tài)下系統(tǒng)中顧客數(shù)的數(shù)學(xué)期望的定義為穩(wěn)定狀態(tài)下系統(tǒng)中顧客數(shù)的數(shù)學(xué)期望的定義為被稱為系統(tǒng)中顧客的平均數(shù)，簡稱被稱為

19、系統(tǒng)中顧客的平均數(shù)，簡稱平均隊長平均隊長。 0nnnpL1)(1(1000nnnnnnnnpL1)1(2000nnnnnnqpnppnL 穩(wěn)定狀態(tài)下系統(tǒng)中等待服務(wù)顧客數(shù)的數(shù)學(xué)期望，穩(wěn)定狀態(tài)下系統(tǒng)中等待服務(wù)顧客數(shù)的數(shù)學(xué)期望，簡稱平均簡稱平均等待隊長等待隊長。. (2)(2)顧客在系統(tǒng)中的顧客在系統(tǒng)中的平均逗留時間平均逗留時間 則顧客在系統(tǒng)中的則顧客在系統(tǒng)中的平均等待時間平均等待時間 可以證明，顧客在系統(tǒng)中逗留時間服從參數(shù)為可以證明，顧客在系統(tǒng)中逗留時間服從參數(shù)為-的負(fù)指數(shù)分布。的負(fù)指數(shù)分布。1)(11q. 與與 是衡量排隊系統(tǒng)質(zhì)量的很重要的效是衡量排隊系統(tǒng)質(zhì)量的很重要的效率度量率度量上式稱為上式

20、稱為LittleLittle公式。公式。 表明系統(tǒng)中的顧客數(shù)，等于一個顧客在表明系統(tǒng)中的顧客數(shù)，等于一個顧客在系統(tǒng)時間內(nèi)來到的新的顧客數(shù)；系統(tǒng)時間內(nèi)來到的新的顧客數(shù)； 表明系統(tǒng)中處于等待狀態(tài)的顧客數(shù)，表明系統(tǒng)中處于等待狀態(tài)的顧客數(shù)，等于一個顧客的等待時間內(nèi)來到的新顧客數(shù)。等于一個顧客的等待時間內(nèi)來到的新顧客數(shù)。 LittleLittle公式公式qqLLLqqLqLL,q,.(3)(3)穩(wěn)定狀態(tài)下穩(wěn)定狀態(tài)下忙期忙期的數(shù)學(xué)期望的數(shù)學(xué)期望由此可見，一個忙期中所服務(wù)顧客的平均數(shù)為由此可見，一個忙期中所服務(wù)顧客的平均數(shù)為1)(TE忙忙11)(TE.（二）系統(tǒng)容量有限的模型（二）系統(tǒng)容量有限的模型 即為即

21、為M MM M1 1N N排隊系統(tǒng)。考慮排隊系統(tǒng)的容排隊系統(tǒng)。考慮排隊系統(tǒng)的容量為量為N N，即若系統(tǒng)已有即若系統(tǒng)已有N N個顧客，則再來新顧客即被個顧客，則再來新顧客即被拒絕進(jìn)入系統(tǒng)。對于拒絕進(jìn)入系統(tǒng)。對于n nN N，與與M MM M1 1相類似，相類似， ，有有ntxtPn)(Pr)()()()(1, 2 , 1)()()()()(10011tptptpNntptptptpnnnn對于對于n nN N，)()1)()()(1tottpttpttpNNN)()()(1tptptpNNN. 即即 滿足微分方程滿足微分方程 在穩(wěn)態(tài)情況下，在穩(wěn)態(tài)情況下， ， ，則則)(tPn)()()()()()(1, 2 , 1)()()()()(110011tptptptptptpNntptptptpNNNnnnn