演示文稿排隊論模型及實例

演示文稿排隊論模型及實例目前一頁\總數(shù)四十七頁\編于二點（優(yōu)選）排隊論模型及實例目前二頁\總數(shù)四十七頁\編于二點排隊現(xiàn)象是由兩個方面構成，一方要求得到服務，另一方設法給予服務。我們把要求得到服務的人或物（設備）統(tǒng)稱為顧客,給予服務的服務人員或服務機構統(tǒng)稱為服務員或服務臺。顧客與服務臺就構成一個排隊系統(tǒng)，或稱為隨機服務系統(tǒng)。顯然缺少顧客或服務臺任何一方都不會形成排隊系統(tǒng).對于任何一個排隊服務系統(tǒng)，每一名顧客通過排隊服務系統(tǒng)總要經(jīng)過如下過程：顧客到達、排隊等待、接受服務和離去，其過程如下圖所示:

顧客總體隊伍輸出輸入

服務臺服務系統(tǒng)目前三頁\總數(shù)四十七頁\編于二點輸入過程顧客源總體：顧客的來源可能是有限的，也可能是無限的2.

排隊服務系統(tǒng)的基本概念到達的類型：顧客是單個到達，或是成批到達相繼顧客到達的間隔時間：通常假定是相互獨立、同分布的，有的是等距間隔時間，有的是服從Poisson分布，有的是服從k階Erlang分布輸入過程是描述顧客來源及顧客是按怎樣的規(guī)律抵達排隊系統(tǒng)目前四頁\總數(shù)四十七頁\編于二點排隊規(guī)則損失制排隊系統(tǒng)：顧客到達時,若有服務臺均被占,服務機構又不允許顧客等待,此時該顧客就自動辭去2.

排隊服務系統(tǒng)的基本概念等待制排隊系統(tǒng)：顧客到達時．若所有服務臺均被占，他們

就排隊等待服務。在等待制系統(tǒng)中,服務

順序又分為：先到先服務,即顧客按到達

的先后順序接受服務；后到先服務

.混合制排隊系統(tǒng)：損失制與等待制的混合，分為隊長(容量)

有限的混合制系統(tǒng)，等待時間有限的混合制系統(tǒng)，以及逗留時間有限制的混合系統(tǒng).排隊規(guī)則是指服務允許不允許排隊，顧客是否愿意排隊目前五頁\總數(shù)四十七頁\編于二點服務機構服務臺的數(shù)目:在多個服務臺的情形下，是串聯(lián)或是并聯(lián)；2.

排隊服務系統(tǒng)的基本概念顧客所需的服務時間服從什么樣的概率分布，每個顧客所需的服務時間是否相互獨立，是成批服務或是單個服務等。常見顧客的服務時間分布有：定長分布、負指數(shù)分布、超指數(shù)分布、k階Erlang分布、幾何分布、一般分布等.目前六頁\總數(shù)四十七頁\編于二點3.符號表示排隊論模型的記號是20世紀50年代初由D.G.Kendall(肯達爾)引入的，通常由3～5個英文字母組成，其形式為其中A表示輸入過程，B表示服務時間，C表示服務臺數(shù)目，n表示系統(tǒng)空間數(shù)。例如:

M/M/S/∞

表示輸入過程是Poisson流,服務時間服從負指數(shù)分布,系統(tǒng)有S個服務臺平行服務,系統(tǒng)容量為無窮的等待制排隊系統(tǒng).(2)M/G/1/∞表示輸入過程是Poisson流，顧客所需的服務時間為獨立、服從一般概率分布，系統(tǒng)中只有一個服務臺，容量為無窮的等待制系統(tǒng).目前七頁\總數(shù)四十七頁\編于二點GI/M/1/∞表示輸入過程為顧客獨立到達且相繼到達的間隔時間服從一船概率分布，服務時間是相互獨立、服從負指數(shù)分布，系統(tǒng)中只有一個服務臺，容量為無窮的等待制系統(tǒng)3.符號表示(4)Ek/G/1/K表示相繼到達的間隔時間獨立、服從k階Erlang分布，服務時間為獨立、服從一般概率分布，系統(tǒng)中只有一個服務臺，容量為K的混合制系統(tǒng).(5)D/M/S/K表示相繼到達的間隔時間獨立、服從定長分布、服務時間相互獨立、服從負指數(shù)分布，系統(tǒng)中有S個服務臺平行服務，容量為K的混合制系統(tǒng).目前八頁\總數(shù)四十七頁\編于二點4.描述排隊系統(tǒng)的主要數(shù)量指標

隊長與等待隊長隊長(通常記為LS)是指在系統(tǒng)中的顧客的平均數(shù)(包括正在接受服務的顧客),而等待隊長(通常記為Lq)是指系統(tǒng)中排隊等待的顧客的平均數(shù)，它們是顧客和服務機構雙方都十分關心的數(shù)量指標。顯然隊長等于等待隊長加上正在被服務的顧客數(shù).

顧客的平均等待時間與平均逗留時間顧客的平均等待時間(通常記為Wq)是指從顧客進入系統(tǒng)的時刻起直到開始接受服務止的平均時間。平均逗留時間(通常記為Ws)是指顧客在系統(tǒng)中的平均等待時間與平均服務時間之和。平均等待時間與平均服務時間是顧客最關心的數(shù)量指標.目前九頁\總數(shù)四十七頁\編于二點4.描述排隊系統(tǒng)的主要數(shù)量指標

系統(tǒng)的忙期與閑期

從顧客到達空閑的系統(tǒng)，服務立即開始，直到系統(tǒng)再次變?yōu)榭臻e，這段時間是系統(tǒng)連續(xù)繁忙的時間，我們稱為系統(tǒng)的忙期，它反映了系統(tǒng)中服務機構的工作強度，是衡量服務機構利用效率的指標，即與忙期對應的是系統(tǒng)的閑期，即系統(tǒng)連續(xù)保持空閑的時間長度.服務機構工作強度用于服務顧客的時間服務設施總的服務時間用于服務顧客的時間服務設施總的服務時間目前十頁\總數(shù)四十七頁\編于二點5.Little（利特爾）公式用λ

表示單位時間內顧客到達的平均數(shù),μ表示單位時間內被服務完畢離去的平均顧客數(shù)，因此1/λ表示相鄰兩顧客到達的平均時間，1/μ表示對每個顧客的平均服務時間.J.D.C.Little給出了如下公式：目前十一頁\總數(shù)四十七頁\編于二點6.與排隊論模型有關的LINGO函數(shù)(1)@peb(load,S)該函數(shù)的返回值是當?shù)竭_負荷為load,服務系統(tǒng)中有S個服務器且允許排隊時系統(tǒng)繁忙的概率,也就是顧客等待的概率.(2)@pel(load,S)該函數(shù)的返回值是當?shù)竭_負荷為load,服務系統(tǒng)中有S個服務器且不允許排隊時系統(tǒng)損失概率,也就是顧客得不到服務離開的概率.(3)@pfs(load,S,K)該函數(shù)的返回值是當?shù)竭_負荷為load,顧客數(shù)為K,平行服務器數(shù)量為S時,有限源的Poisson服務系統(tǒng)等待或返修顧客數(shù)的期望值.目前十二頁\總數(shù)四十七頁\編于二點10.2等待制排隊模型等待制排隊模型中最常見的模型是即顧客到達系統(tǒng)的相繼到達時間間隔獨立，且服從參數(shù)為λ的負指數(shù)分布(即輸入過程為Poisson過程),服務臺的服務時間也獨立同分布,且服從參數(shù)為μ的負指數(shù)分布，而且系統(tǒng)空間無限，允許永遠排隊.目前十三頁\總數(shù)四十七頁\編于二點

1.

等待制排隊模型的基本參數(shù)(1)

顧客等待的概率Pwait其中S是服務臺或服務員的個數(shù)，load是系統(tǒng)到達負荷，即load=λ/μ=R*T,式中R表示λ,T表示1/μ,R表示λ,在下面的程序中，因此，R或λ是顧客的平均到達率，μ是顧客的平均被服務數(shù)，T就是平均服務時間.目前十四頁\總數(shù)四十七頁\編于二點

1.

等待制排隊模型的基本參數(shù)(2)顧客的平均等待時間Wq其中T/(S-load)是一個重要指標，可以看成一個“合理的長度間隔”。注意，當load→S時，此值趨于無窮。也就是說，系統(tǒng)負荷接近服從器的個數(shù)時，顧客平均等待時間將趨于無窮.當load>S時,上式Wq無意義。其直觀的解釋是：當系統(tǒng)負荷超過服從器的個數(shù)時,排隊系統(tǒng)達不到穩(wěn)定的狀態(tài),其隊將越排越長.目前十五頁\總數(shù)四十七頁\編于二點

1.

等待制排隊模型的基本參數(shù)顧客的平均逗留時間Ws、隊長Ls和等待隊長Lq這三個值可由Little公式直接得到目前十六頁\總數(shù)四十七頁\編于二點2.等待制排隊模型的計算實例S=1的情況(M/M/1/∞)

即只有一個服務臺或一名服務員服務的情況.例10.2

某維修中心在周末現(xiàn)只安排一名員工為顧客提供服

務。新來維修的顧客到達后，若已有顧客正在接受服務，

則需要排隊等待。假設來維修的顧客到達過程為Poisson

流，平均4人/小時，維修時間服從負指數(shù)分布，平均需要

6分鐘。試求該系統(tǒng)的主要數(shù)量指標。解按照式上面分析,編寫LINGO程序，其中R=4,

T=6/60,load=R.T,S=1.程序名:exam1002.lg4.目前十七頁\總數(shù)四十七頁\編于二點2.等待制排隊模型的計算實例由此得到：(1)系統(tǒng)平均隊長Ls=0.6666667,(2)系統(tǒng)平均等待隊長Lq=0.2666667,(3)顧客平均逗留時間Ws=0.1666667(小時)=10(分鐘)(4)顧客平均等待時間Wq=0.06666667(小時)=4(分鐘)(5)系統(tǒng)繁忙概率Pwait=0.4目前十八頁\總數(shù)四十七頁\編于二點在商業(yè)中心處設置一臺ATM機，假設來取錢的顧客平均每

分鐘0.6個，而每個顧客的平均取錢的時間為1.25分鐘，試

求該ATM機的主要數(shù)量指標.解只需將上例LINGO程序作如下改動：R=0.6,T=1.25

即

可得到結果.程序名:exam1003.lg4.計算結果見運行．

例10.3即平均隊長為3人，平均等待隊長為2.25人，顧客平均逗留

時間5分鐘，顧客平均等待時間為3.75分鐘，系統(tǒng)繁忙概率

為0.75.目前十九頁\總數(shù)四十七頁\編于二點S>1的情況(M/M/S/∞)

表示有多個服務臺或多名服務員服務的情況例10.４設打印室有3名打字員,平均每個文件的打印時間為10分鐘，而文件的到達率為每小時15件，試求該打印

室的主要數(shù)量指標.解按照上面分析,編寫LINGO程序,程名:exam1004.lg4.計算結果分析：即在打字室內現(xiàn)有的平均文件數(shù)為6.011

件，等待打印平均文件數(shù)3.511件，每份文件在打字室平

均停留時間為0.400小時（24分鐘），排隊等待打印的平

均時間0.234小時(14分鐘),打印室不空閑的概率0.702.目前二十頁\總數(shù)四十七頁\編于二點某售票點有兩個售票窗口，顧客按參數(shù)λ=8人/分鐘的

Poisson流到達，每個窗口的售票時間均服從參數(shù)μ=5人/分

鐘的負指數(shù)分布，試比較以下兩種排隊方案的運行指標.(1)

顧客到達后,以1/2的概率站成兩個隊列，如右圖所示：

例10.5(2)顧客到達后排成一個隊列,顧客發(fā)現(xiàn)哪個窗口空時,他就

接受該窗口的服務，如下圖所示:目前二十一頁\總數(shù)四十七頁\編于二點解(1)實質上是兩個獨立的M/M/1/∞系統(tǒng),其參數(shù)S=1,

R=λ1=λ2=4,T=1/μ=1/5=0.2,編寫其LINGO程序，程序

名:exam1005a.lg4.計算結果見運行．

例10.5(2)

是兩個并聯(lián)系統(tǒng),其參數(shù)S=2,R=λ=8,T=1/μ=1/5=0.2,

編寫其LINGO程序,程序名:exam1005b.lg4.計算結果見

運行．兩種系統(tǒng)的計算結果目前二十二頁\總數(shù)四十七頁\編于二點從上表中所列的計算結果可以看出,在服務臺的各種性能指標不變的情況下,采用不同的排隊方式,其結果是不同的.從表得到,采用多隊列排隊系統(tǒng)的隊長為4,而采用單排隊系統(tǒng)總隊長為4.444,也就是說每一個子隊的隊長為2.222,幾乎是多列隊排隊系統(tǒng)的1/2,效率幾乎提高了一倍.

例10.5比較分析目前二十三頁\總數(shù)四十七頁\編于二點10.3損失制排隊模型損失制排隊模型通常記為當S個服務器被占用后，顧客自動離去。其模型的基本參數(shù)與等待制排隊模型有些不同,我們關心如下指標：(1)

系統(tǒng)損失的概率其中l(wèi)oad是系統(tǒng)到達負荷,S是服務臺或服務員的個數(shù).

1.損失制排隊模型的基本參數(shù)目前二十四頁\總數(shù)四十七頁\編于二點(2)單位時間內平均進入系統(tǒng)的顧客數(shù)(λe或Re)(3)系統(tǒng)的相對通過能力Q與絕對通過能力A(4)系統(tǒng)在單位時間內占用服務臺(或服務員)的均值Ls注意:在損失制排隊系統(tǒng)中,Lq=0,即等待隊長為0.目前二十五頁\總數(shù)四十七頁\編于二點(5)系統(tǒng)服務臺（或服務員）的效率(6)顧客在系統(tǒng)內平均逗留時間(由于Wq=0,即為Ws）注意:在損失制排隊系統(tǒng)中,Wq=0,即等待時間為0.在上述公式中,引入λe(或Re)是十分重要的,因為盡管顧客的以平均λ(或R)的速率到達服務系統(tǒng),但當系統(tǒng)被占滿后,有一部分顧客會自動離去,因此,真正進入系統(tǒng)的顧客輸入率是λe,它小于λ.目前二十六頁\總數(shù)四十七頁\編于二點2.損失制排隊模型的計算實例S=1的情況(M/M/1/1)例10.6設某條電話線，平均每分鐘有0.6次呼喚，若每次

通話時間平均為1.25分鐘，求系統(tǒng)相應的參數(shù)指標。解按照上面分析,編寫LINGO程序，其中S=1,R=λ=0.6,

T=1/μ=1.25,程序名:exam1006.lg4，結果見運行．系統(tǒng)的顧客損失率為43%,即43%的電話沒有接通,有57%的電話得到了服務,通話率為平均每分鐘有0.195次,系統(tǒng)的服務效率為43%.對于一個服務臺的損失制系統(tǒng),系統(tǒng)的服務效率等于系統(tǒng)的顧客損失率,這一點在理論上也是正確的.目前二十七頁\總數(shù)四十七頁\編于二點S>1的情況(M/M/S/S)例10.7某單位電話交換臺有一臺200門內線的總機，已知在

上班8小時的時間內，有20%的內線分機平均每40分鐘要一

次外線電話，80%的分機平均隔120分鐘要一次外線。又知

外線打入內線的電話平均每分鐘1次.假設與外線通話的時

間為平均3分鐘,并且上述時間均服從負指數(shù)分布,如果要求

電話的通話率為95%,問該交換臺應設置多少條外線？解(1)電話交換臺的服務分成兩類,第一類內線打外線,其強

度為:第二類是外線打內線，其強度為λ2=1*60=60.

因此，總強度為λ=λ1+λ2=140+60=200.目前二十八頁\總數(shù)四十七頁\編于二點(2)這是損失制服務系統(tǒng),按題目要求,系統(tǒng)損失的概率不能超過5%,即(3)外線是整數(shù)，在滿足條件下，條數(shù)越少越好。

由上述三條，寫出相應的LINGO程序，

程序名：exam1007a.lg4.

例10.7經(jīng)計算得到,即需要15條外線,在此條件下,交換臺的顧客

損失率為3.65%,有96.35%的電話得到了服務,通話率為平

均每小時185.67次,交換臺每條外線的服務效率為64.23%.目前二十九頁\總數(shù)四十七頁\編于二點在前面談過，盡量選用簡單的模型讓LINGO軟件求解，而

上述程序是解非線性整數(shù)規(guī)劃(盡管是一維的),但計算時間

可能會較長,因此,我們選用下面的處理法,分兩步處理.第一步,求出概率為5%的服務臺的個數(shù),盡管要求服務臺

是整數(shù),但@pel()可以給出實數(shù)解.

寫出LINGO程序,程序名：exam1007b1.lg4.

例10.7第二步,注意到@pel(load,S)是S的單調遞減函數(shù),因此,對

S取整(采用只入不舍原則)就是滿足條件的最小服務臺數(shù),

然后再計算出其他的參數(shù)指標。

寫出LINGO程序,程序名：exam1007b2.lg4.比較兩種方法的計算結果，其答案是相同的，但第二種方法比第一種方法在計算時間上要少許多.目前三十頁\總數(shù)四十七頁\編于二點10.4混合制排隊模型混合制排隊模型通常記為即有S個服務臺或服務員,系統(tǒng)空間容量為K,當K個位置已被顧客占用時,新到的顧客自動離去,當系統(tǒng)中有空位置時,新到的顧客進入系統(tǒng)排隊等待。對于混合制排隊模型,LINGO軟件并沒有提供特殊的計算函數(shù),因此需要混合制排隊模型的基本公式進行算,為此,先給出其基本公式.目前三十一頁\總數(shù)四十七頁\編于二點設pi(i=1,2,…,K)是系統(tǒng)有i個顧客的概率,p0表示系統(tǒng)空閑時的概率,因此有:設λi(i=1,2,…,K)為系統(tǒng)在i時刻的輸入強度,μi

(i=1,2,…,K)

為系統(tǒng)在i時刻的服務強度,在平衡過下,可得到平衡方程1.混合制排隊模型的基本公式目前三十二頁\總數(shù)四十七頁\編于二點對于混合制排隊模型M/M/S/K,有1.混合制排隊模型的基本公式目前三十三頁\總數(shù)四十七頁\編于二點對于混合制排隊模型，人們關心如下參數(shù)：(1)系統(tǒng)的損失概率2.

混合制排隊模型的基本參數(shù)(2)系統(tǒng)的相對通過能力Q和單位時間平均進入系統(tǒng)的顧客數(shù)λe(3)平均隊長Ls和平均等待隊長Lq目前三十四頁\總數(shù)四十七頁\編于二點(4)顧客在系統(tǒng)內平均逗留時間Ws

和平均排隊等待時間Wq

,

這兩個時間可由Little公式得到注意:上面兩公式中，是除λe而不是λ,其理由與損失制系統(tǒng)相同.2.

混合制排隊模型的基本參數(shù)目前三十五頁\總數(shù)四十七頁\編于二點S=1的情況(M/M/1/K)例10.8某理發(fā)店只有1名理發(fā)員,因場所有限,店里最多可

容納4名顧客,假設來理發(fā)的顧客按Poisson過程到達,平均

到達率為每小時6人,理發(fā)時間服從負指數(shù)分布,平均12分

鐘可為1名顧客理發(fā),求該系統(tǒng)的各項參數(shù)指標.解按照上面分析,其參數(shù)S=1,K=4,R=λ=6,T=1/μ=12/60,

再計算相應的損失概率pK及各項參數(shù)指標,編寫出LINGO程序，程序名:exam1008.lg4，結果見運行．即理發(fā)店的空閑率為13.4%,顧客的損失率為27.9%,每小時進入理發(fā)店的平均顧客數(shù)為4.328人,理發(fā)店內的平均顧客數(shù)(隊長)為2.359人,顧客在理發(fā)店的平均逗留時間是0.545小時(32.7分鐘),理發(fā)店里等待理發(fā)的平均顧客數(shù)(等待隊長)為1.494人,顧客在理發(fā)店的平均等待時間為0.345小時(20.7分)3.

混合制排隊模型的計算實例目前三十六頁\總數(shù)四十七頁\編于二點S>1的情況(M/M/S/K)例10.9某工廠的機器維修中心有9名維修工,因為場地限制,

中心內最多可以容納12臺需要維修的設備,假設待修的設備

按Poisson過程到達,平均每天4臺,維修設備服從負指數(shù)分布,

每臺設備平均需要2天時間,求該系統(tǒng)的各項參數(shù)指標.解其參數(shù)S=9,K=12,R=λ=4,T=1/μ=2,再計算相應的損失

概率pK及各項參數(shù)指標,編寫出LINGO程序，

程序名:exam1009.lg4，結果見運行．經(jīng)計算得到：維修中心的空閑率p0=0.033%$,設備的損失率

Plost=8.61%,每天進入維修中心需要維修的設備λe=3.66臺,

維修中心內的平均維修的設備(隊長)Ls=7.87臺,待修設備在

維修中心的平均逗留時間Ws=2.15天,維修中心內等平均待

維修的設備(等待隊長)Lq=0.561天,待修設備在維修中心的

平均等待時間Wq=0.153天.目前三十七頁\總數(shù)四十七頁\編于二點10.5閉合式排隊模型設系統(tǒng)內有M個服務臺(或服務員),顧客到達系統(tǒng)的間隔時間和服務臺的服務時間均為負指數(shù)分布,而系統(tǒng)的容量和潛在的顧客數(shù)都為K,又顧客到達率為λ,服務臺的平均服務率為μ,這樣的系統(tǒng)稱為閉合式排隊模型,記為目前三十八頁\總數(shù)四十七頁\編于二點對于閉合式排隊模型，我們關心的參數(shù)：(1)平均隊長1.

閉合式排隊模型的基本參數(shù)其中l(wèi)oad是系統(tǒng)的負荷,其計算公式為即系統(tǒng)的負荷=系統(tǒng)的顧客數(shù)

X顧客的到達率

X顧客的服務時間(2)單位時間平均進入系統(tǒng)的顧客數(shù)λe或Re.目前三十九頁\總數(shù)四十七頁\編于二點(3)顧客處于正常情況的概率(5)每個服務臺(服務員)的工作強度(4)平均逗留時間Ws、平均等待隊長Lq和平均排隊等待時間Wq

,這三個值可由Little公式得到目前四十頁\總數(shù)四十七頁\編于二點S=1的情況(M/M/1/K/K)例10.10設有1名工人負責照管6臺自動機床.當機床需要加

料、發(fā)生故障或刀具磨損時就自動停車,等待工人照管.設

平均每臺機床兩次停車的時間間隔為1小時,停車時需要工

人照管的平均時間是6分鐘,并均服從負指數(shù)分布,求該系

統(tǒng)的各項指標.解這是一個閉合式排隊模型M/M/1/6/6,

其參數(shù)為S=1,K=6,

R=λ=1,T=1/μ=6/60,計算出平均隊長,再計算出其他各項

指標,寫出LINGO程序,程序名:exam1010.lg4,結果見運行.機床的平均隊長為0.845臺,平均等待隊長為0.330臺,機床的平均逗留時間為0.164小時(9.84分鐘),平均等待時間為0.064小時(3.84分鐘),機床的正常工作概率為85.91%,工人的勞動強度為0.515.目前四十一頁\總數(shù)四十七頁\編于二點S>1的情況例10.11(繼例10.10)將例中的條件改為由3名工人聯(lián)合看

管20臺自動機床,其他條件不變,求該系統(tǒng)的各項指標。解這是M/M/3/20/20閉合式排隊模型,

其參數(shù)為S=3,K=20,

其余不變,寫出LINGO程序,程序名:exam1011.lg4,

結果見運行.2.

閉合式排隊模型的計算實例目前四十二頁\總數(shù)四十七頁\編于二點從上表可以看出,在第二種情況下,盡管每個工人看管的機器

數(shù)增加了,但機器逗留時間和等待維修時間卻縮短了