第十二章排隊(duì)論(運(yùn)籌學(xué)上海電力學(xué)院)

第十二章排隊(duì)論引言排隊(duì)論是研討排隊(duì)系統(tǒng)〔又稱隨機(jī)效力系統(tǒng)〕的數(shù)學(xué)實(shí)際和方法，是運(yùn)籌學(xué)的一個(gè)重要分支。有形排隊(duì)景象：進(jìn)餐館就餐，到圖書館借書，車站等車，去醫(yī)院看病，售票處售票，到工具房領(lǐng)物品等景象。

無(wú)形排隊(duì)景象：如幾個(gè)旅客同時(shí)打訂車票；假設(shè)有一人正在通話，其他人只得在各自的機(jī)前等待，他們分散在不同的地方，構(gòu)成一個(gè)無(wú)形的隊(duì)列在等待通。排隊(duì)的不一定是人，也可以是物。如消費(fèi)線上的原資料，半廢品等待加工；因缺點(diǎn)而停頓運(yùn)轉(zhuǎn)的機(jī)器設(shè)備在等待修繕；碼頭上的船只等待裝貨或卸貨；要下降的飛機(jī)因跑道不空而在空中盤旋等。當(dāng)然，進(jìn)展效力的也不一定是人，可以是跑道，自動(dòng)售貨機(jī)，公共汽車等。顧客——要求效力的對(duì)象。效力員——提供效力的效力者〔也稱效力機(jī)構(gòu)〕。顧客、效力員的含義是廣義的。排隊(duì)系統(tǒng)類型：效力臺(tái)顧客到達(dá)效力完成后分開單效力臺(tái)排隊(duì)系統(tǒng)排隊(duì)系統(tǒng)類型：效力臺(tái)2顧客到達(dá)效力完成后分開S個(gè)效力臺(tái)，一個(gè)隊(duì)列的排隊(duì)系統(tǒng)效力臺(tái)s效力臺(tái)1排隊(duì)系統(tǒng)類型：效力臺(tái)2顧客到達(dá)效力完成后分開S個(gè)效力臺(tái)，S個(gè)隊(duì)列的排隊(duì)系統(tǒng)效力臺(tái)s效力臺(tái)1效力完成后分開效力完成后分開排隊(duì)系統(tǒng)類型：效力臺(tái)1顧客到達(dá)分開多效力臺(tái)串聯(lián)排隊(duì)系統(tǒng)效力臺(tái)s排隊(duì)系統(tǒng)類型：效力機(jī)構(gòu)聚散隨機(jī)聚散效力系統(tǒng)〔輸入〕〔輸出〕隨機(jī)性——顧客到達(dá)情況與顧客接受效力的時(shí)間是隨機(jī)的。普通來(lái)說(shuō)，排隊(duì)論所研討的排隊(duì)系統(tǒng)中，顧客相繼到達(dá)時(shí)間間隔和效力時(shí)間這兩個(gè)量中至少有一個(gè)是隨機(jī)的，因此，排隊(duì)論又稱隨機(jī)效力實(shí)際。排隊(duì)系統(tǒng)的描畫實(shí)踐中的排隊(duì)系統(tǒng)各不一樣，但概括起來(lái)都由三個(gè)根本部分組成：輸入過(guò)程，排隊(duì)及排隊(duì)規(guī)那么和效力機(jī)構(gòu)。輸入過(guò)程顧客總體〔顧客源〕數(shù)：能夠是有限，也能夠是無(wú)限。

河流上游流入水庫(kù)的水量可以為是無(wú)限的；車間內(nèi)停機(jī)待修的機(jī)器顯然是有限的。到達(dá)方式：是單個(gè)到達(dá)還是成批到達(dá)。庫(kù)存問(wèn)題中，假設(shè)把進(jìn)來(lái)的貨看成顧客，那么為成批到達(dá)的例子。顧客〔單個(gè)或成批〕相繼到達(dá)的時(shí)間間隔分布：這是刻劃輸入過(guò)程的最重要內(nèi)容。令T0=0，Tn表示第n顧客到達(dá)的時(shí)辰，那么有T0T1T2…..Tn……記Xn=Tn–Tn-1n=1,2,…,那么Xn是第n顧客與第n-1顧客到達(dá)的時(shí)間間隔。普通假定{Xn}是獨(dú)立同分布，并記分布函數(shù)為A(t)。{Xn}的分布A(t)常見(jiàn)的有：定常分布〔D〕：顧客相繼到達(dá)的時(shí)間間隔為確定的。如產(chǎn)品經(jīng)過(guò)傳送帶進(jìn)入包裝箱就是定常分布。最簡(jiǎn)流〔或稱Poisson)〔M〕：顧客相繼到達(dá)的時(shí)間間隔{Xn}為獨(dú)立的，同為負(fù)指數(shù)分布，其密度函數(shù)為：a(t)=e-tt00t<0排隊(duì)及排隊(duì)規(guī)那么排隊(duì)有限排隊(duì)——排隊(duì)系統(tǒng)中顧客數(shù)是有限的。無(wú)限排隊(duì)——顧客數(shù)是無(wú)限，隊(duì)列可以排到無(wú)限長(zhǎng)〔等待制排隊(duì)系統(tǒng)〕。有限排隊(duì)還可以分成：損失制排隊(duì)系統(tǒng)：排隊(duì)空間為零的系統(tǒng)，即不允許排隊(duì)?！差櫩偷竭_(dá)時(shí)，效力臺(tái)占滿，顧客自動(dòng)分開，不再回來(lái)〕〔系統(tǒng)〕混合制排隊(duì)系統(tǒng)：是等待制與損失制結(jié)合，即允許排隊(duì)，但不允許隊(duì)列無(wú)限長(zhǎng)?；旌现婆抨?duì)系統(tǒng)：隊(duì)長(zhǎng)有限。即系統(tǒng)等待空間是有限的。例：最多只能包容K個(gè)顧客在系統(tǒng)中，當(dāng)新顧客到達(dá)時(shí)，假設(shè)系統(tǒng)中的顧客數(shù)〔又稱為隊(duì)長(zhǎng)〕小于K，那么可進(jìn)入系統(tǒng)排隊(duì)或接受效力；否那么，便分開系統(tǒng)，并不再回來(lái)。如水庫(kù)的庫(kù)容是有限的，旅館的床位是有限的?；旌现婆抨?duì)系統(tǒng)：等待時(shí)間有限。即顧客在系統(tǒng)中等待時(shí)間不超越某一給定的長(zhǎng)度T，當(dāng)?shù)却龝r(shí)間超越T時(shí)，顧客將自動(dòng)分開，不再回來(lái)。如易損失的電子元件的庫(kù)存問(wèn)題，超越一定存儲(chǔ)時(shí)間的元器件被自動(dòng)以為失效?；旌现婆抨?duì)系統(tǒng)：逗留時(shí)間〔等待時(shí)間與效力時(shí)間之和〕有限。例：用高射炮射擊飛機(jī)，當(dāng)敵機(jī)飛越射擊有效區(qū)域的時(shí)間為t時(shí)，假設(shè)這個(gè)時(shí)間內(nèi)未被擊落，也就不能夠再被擊落了。損失制和等待制可看成是混合制的特殊情形，如記s為系統(tǒng)中效力臺(tái)個(gè)數(shù)，那么當(dāng)k=s時(shí)，混合制即為損失制；當(dāng)k=時(shí)，即成為等待制。排隊(duì)規(guī)那么當(dāng)顧客到達(dá)時(shí)，假設(shè)一切效力臺(tái)都被占有且又允許排隊(duì)，那么該顧客將進(jìn)入隊(duì)列等待。效力臺(tái)對(duì)顧客進(jìn)展效力所遵照的規(guī)那么通常有：先來(lái)先效力〔FCFS〕后來(lái)先效力〔LCFS〕。在許多庫(kù)存系統(tǒng)中就會(huì)出現(xiàn)這種情況，如鋼板存入倉(cāng)庫(kù)后，需求時(shí)總是從最上面取出；又如在情報(bào)系統(tǒng)中，后來(lái)到達(dá)的信息往往更重要，首先要加以分析和利用。具有優(yōu)先權(quán)的效力〔PS〕。效力臺(tái)根據(jù)顧客的優(yōu)先權(quán)的不同進(jìn)展效力。如病危的病人應(yīng)優(yōu)先治療；重要的信息應(yīng)優(yōu)先處置；出價(jià)高的顧客應(yīng)優(yōu)先思索。效力機(jī)制包括：效力員的數(shù)量及其銜接方式〔串聯(lián)還是并聯(lián)〕；顧客是單個(gè)還是成批接受效力；效力時(shí)間的分布。記某效力臺(tái)的效力時(shí)間為V，其分布函數(shù)為B(t),密度函數(shù)為b(t),那么常見(jiàn)的分布有：定長(zhǎng)分布〔D〕：每個(gè)顧客接受的效力時(shí)間是一個(gè)確定的常數(shù)。負(fù)指數(shù)分布〔M〕：每個(gè)顧客接受的效力時(shí)間相互獨(dú)立，具有一樣的負(fù)指數(shù)分布：b(t)=e-tt00t<0其中>0為一常數(shù)。K階愛(ài)爾朗分布〔En〕：b(t)=k(kt)k-1(K-1)!=e-kt當(dāng)k=1時(shí)即為負(fù)指數(shù)分布；k30,近似于正態(tài)分布。當(dāng)k時(shí)，方差0即為完全非隨機(jī)的。排隊(duì)系統(tǒng)的符號(hào)表示：“Kendall〞記號(hào)：X/Y/Z/W其中：X表示顧客相繼到達(dá)的時(shí)間間隔分布；Y表示效力時(shí)間的分布；Z表示效力臺(tái)個(gè)數(shù)；W表示系統(tǒng)的容量，即可包容的最多顧客數(shù)。例12-1M/M/1/M表示顧客相繼到達(dá)的時(shí)間間隔服從負(fù)指數(shù)分布；M表示效力時(shí)間為負(fù)指數(shù)分布；單個(gè)效力臺(tái)；系統(tǒng)容量為無(wú)限〔等待制〕的排隊(duì)模型。例12-2M/M/S/K表示顧客到達(dá)的時(shí)間間隔服從負(fù)指數(shù)分布；效力時(shí)間為負(fù)指數(shù)分布；S個(gè)效力臺(tái)；系統(tǒng)容量為K的排隊(duì)模型。當(dāng)K=S時(shí)為損失制排隊(duì)模型；當(dāng)K=時(shí)為等待制排隊(duì)模型。排隊(duì)系統(tǒng)的主要數(shù)量目的：系統(tǒng)形狀：也稱為隊(duì)長(zhǎng)，指排隊(duì)系統(tǒng)中的顧客數(shù)〔排隊(duì)等待的顧客數(shù)與正在接受效力的顧客數(shù)之和〕。排隊(duì)長(zhǎng)：系統(tǒng)中正在排隊(duì)等待效力的顧客數(shù)。記N(t)：時(shí)辰t(t0)的系統(tǒng)形狀；pn(t)：時(shí)辰t系統(tǒng)處于形狀n的概率；S：排隊(duì)系統(tǒng)中并行的效力臺(tái)數(shù)；n：當(dāng)系統(tǒng)處于形狀n時(shí)，新來(lái)的顧客的平均到達(dá)率〔單位時(shí)間內(nèi)到達(dá)的平均顧客數(shù)〕；n：當(dāng)系統(tǒng)處于形狀n時(shí)，整個(gè)系統(tǒng)的平均效力率〔單位時(shí)間內(nèi)可以效力完的平均顧客數(shù)〕；當(dāng)n為常數(shù)時(shí)記為；當(dāng)每個(gè)效力臺(tái)的平均效力率為常數(shù)時(shí)，記每個(gè)效力臺(tái)的效力率為，那么當(dāng)ns時(shí)，有n=s。因此，顧客相繼到達(dá)的平均時(shí)間間隔為1/，平均效力時(shí)間為1/，令=/s，那么為系統(tǒng)的效力強(qiáng)度。pn(t)稱為系統(tǒng)在時(shí)辰t的瞬間分布，普通不容易求得，同時(shí)，由于排隊(duì)系統(tǒng)運(yùn)轉(zhuǎn)一段時(shí)間后，其形狀和分布都呈現(xiàn)出與初始形狀或分布無(wú)關(guān)的性質(zhì)，稱具有這種性質(zhì)的形狀或分布為平穩(wěn)形狀或平穩(wěn)分布，排隊(duì)論普通更留意研討系統(tǒng)在平穩(wěn)形狀下的性質(zhì)。排隊(duì)系統(tǒng)在平穩(wěn)形狀時(shí)一些根本目的有：Pn:系統(tǒng)中恰有n個(gè)顧客的概率；L：系統(tǒng)中顧客數(shù)的平均值，又稱為平均隊(duì)長(zhǎng)；Lq：系統(tǒng)中正在排隊(duì)的顧客數(shù)的平均值，又稱為平均排隊(duì)長(zhǎng)；T：顧客在系統(tǒng)中的逗留時(shí)間；W=E(T)：顧客在系統(tǒng)中的平均逗留時(shí)間；Tq：顧客在系統(tǒng)中的排隊(duì)等待時(shí)間；Wq=E(Tq)：顧客在系統(tǒng)中的平均排隊(duì)等待時(shí)間。排隊(duì)論研討的根本問(wèn)題：經(jīng)過(guò)研討主要數(shù)量目的在瞬時(shí)或平穩(wěn)形狀下的概率分布及數(shù)字特征，了解系統(tǒng)運(yùn)轉(zhuǎn)的根本特征。統(tǒng)計(jì)推斷問(wèn)題：建立適當(dāng)?shù)呐抨?duì)模型是排隊(duì)論研討的第一步，建立模型過(guò)程中，系統(tǒng)能否到達(dá)平穩(wěn)形狀的檢驗(yàn)；顧客相繼到達(dá)時(shí)間間隔相互獨(dú)立性的檢驗(yàn)，效力時(shí)間的分布及有關(guān)參數(shù)確實(shí)定等。排隊(duì)研討的根本問(wèn)題：系統(tǒng)優(yōu)化問(wèn)題：又稱為系統(tǒng)控制問(wèn)題或系統(tǒng)運(yùn)營(yíng)問(wèn)題，其根本目的是使系統(tǒng)處于最優(yōu)的或最合理的形狀。包括：最優(yōu)設(shè)計(jì)問(wèn)題和最優(yōu)運(yùn)營(yíng)問(wèn)題。M/M/S等待制排隊(duì)模型單效力臺(tái)問(wèn)題，又表示為M/M/1/：顧客相繼到達(dá)時(shí)間服從參數(shù)為的負(fù)指數(shù)分布；效力臺(tái)數(shù)為1；效力時(shí)間服從參數(shù)為的負(fù)指數(shù)分布；系統(tǒng)的空間為無(wú)限，允許永遠(yuǎn)排隊(duì)。隊(duì)長(zhǎng)的分布記Pn=p{N=n},n=0,1,2….為系統(tǒng)到達(dá)平衡形狀后隊(duì)長(zhǎng)的概率分布，那么n=；n=，=/<1，有Pn=(1-)nn=0,1,2….幾個(gè)數(shù)量目的平均隊(duì)長(zhǎng)：L=nPn=n(1-)n=/(1-)=/(-)平均排隊(duì)長(zhǎng)：Lq=(n-1)Pn=2/(1-)=2/(-)幾個(gè)數(shù)量目的平均逗留時(shí)間：W=E(T)=1/(-)平均等待時(shí)間：Wq=/(-)它們之間有關(guān)系：L=WLq=WqLittle公式。例12-3：思索一個(gè)鐵路列車編組站。設(shè)待編列車到達(dá)時(shí)間間隔服從負(fù)指數(shù)分布，平均每小時(shí)到達(dá)2列；效力臺(tái)是編組站，編組時(shí)間服從負(fù)指數(shù)分布，平均每20分鐘可編一組。知編組站上共有2股道，當(dāng)均被占用時(shí)，不能接車，再來(lái)的列車只能停在站外或前方站。求在平衡形狀下系統(tǒng)中列車的平均數(shù)；每一列車的平均逗留時(shí)間；等待編組的列車平均數(shù)。假設(shè)列車因站中2股道均被占用而停在站外或前方站時(shí)，每列車每小時(shí)費(fèi)用為a元，求每天由于列車在站外等待而呵斥的損失。解：本例可看成一個(gè)M/M/1/排隊(duì)問(wèn)題，其中=2，=3，=/=2/3<1系統(tǒng)中列車的平均數(shù)L=/(1-)=(2/3)/(1-2/3)=2〔列〕列車在系統(tǒng)中的平均停留時(shí)間W=L/=2/2=1〔小時(shí)〕系統(tǒng)中等待編組的列車平均數(shù)Lq=L-=2-2/3=4/3〔列〕列車在系統(tǒng)中的平均等待編組時(shí)間Wq=Lq/=(4/3)/(1/2)=2/3〔小時(shí)〕記列車平均延誤〔由于站內(nèi)2股道均被占用而不能進(jìn)站〕時(shí)間為W0那么W0=WP{N>2}=W{1-P0-P1-P2}=W{1-(l-)-(l-)1-(l-)2}=1*3=3=(2/3)3=0.296〔小時(shí)〕故每天列車由于等待而支出的平均費(fèi)用E=24W0a=24*2*0.296*a=14.2a元例12-4：某修繕店只需一位修繕工，來(lái)修繕的顧客到達(dá)過(guò)程為Poisson流，平均每小時(shí)4人；修繕時(shí)間服從負(fù)指數(shù)分布，平均需求6分鐘。試求：修繕店空閑的概率；店內(nèi)恰有3位顧客的概率；店內(nèi)至少有一位顧客的概率；在店內(nèi)平均顧客數(shù)；每位在店內(nèi)平均逗留時(shí)間；等待效力的平均顧客數(shù)；每位顧客平均等待效力時(shí)間；顧客在店內(nèi)等待時(shí)間超越10分鐘的概率。解：本例可看成一個(gè)M/M/1/排隊(duì)問(wèn)題，其中=4，=1/0.1=10(人/小時(shí)〕，=/=2/5<1修繕店內(nèi)空閑的概率P0=1-=(1-2/5)=0.6店內(nèi)恰有3個(gè)顧客的概率P3=3(1-)=(2/5)3(1-2/5)=0.038店內(nèi)至少有1位顧客的概率P{N1}=1-P0=1-(1-)==2/5=0.4在店內(nèi)平均顧客數(shù)L=/(1-)=(2/5)/(1-2/5)=0.67(人〕每位顧客在店內(nèi)平均逗留時(shí)間W=L/=0.67/4=10分鐘等待效力的平均顧客數(shù)Lq=L-=0.67-2/5=0.27(人)每個(gè)顧客平均等待效力時(shí)間Wq=Lq/=0.27/4=0.0675小時(shí)=4分鐘顧客在店內(nèi)等待時(shí)間超越10分鐘的概率P{T>10}=e-10(1/6-1/15)=e-1=0.3677P{T>t}=e-(-)tt=10分鐘,=10人/小時(shí)=10/60=1/6=4人/小時(shí)=4/60=1/15M/M/S等待制排隊(duì)模型多效力臺(tái)問(wèn)題，又表示為M/M/S/：顧客相繼到達(dá)時(shí)間服從參數(shù)為的負(fù)指數(shù)分布；效力臺(tái)數(shù)為S；每個(gè)效力臺(tái)的效力時(shí)間相互獨(dú)立，且服從參數(shù)為的負(fù)指數(shù)分布。當(dāng)顧客到達(dá)時(shí)，假設(shè)有空閑效力臺(tái)馬上被進(jìn)展效力，否那么便排成一隊(duì)列等待，等待空間為無(wú)限。隊(duì)長(zhǎng)的分布記Pn=p{N=n},n=0,1,2….為系統(tǒng)到達(dá)平衡形狀后隊(duì)長(zhǎng)N的概率分布，對(duì)多效力臺(tái)有n=；n=0,1,2….n=nn=0,1,2….sn=sn=s,s+1,s+2….s=/s=/s,當(dāng)s<1時(shí)，有Cn=(/)nn!(/)ss!(/s)n-s=(/)ns!sn-sn=1,2,…..snspn=(p)nn!n=1,2,…..sns!sn-snsp0p0其中：p0=[0s-1pn/n!+s/s!(1-s)]-1當(dāng)ns時(shí)，顧客必需等待，記C(s,)=spn=s/s!(1-s)p0稱為Erlang等待公式，它給出了顧客到達(dá)系統(tǒng)時(shí)，需求等待的概率。平均排隊(duì)長(zhǎng)：Lq=s(n-s)pn=p0ss/s!(1-s)2或