建模算法及部分源代碼-排隊(duì)論

第十章排隊(duì)排隊(duì)論（queuingtheory）是一門(mén)應(yīng)用十分廣泛的運(yùn)籌學(xué)分支，它在各種存在等短，但在許多商務(wù)活動(dòng)中須給顧客的等待時(shí)間以充分的重視。絕大多數(shù)大型在。零售商不敢讓顧客在隊(duì)伍中等待太長(zhǎng)的時(shí)間，因?yàn)闀r(shí)間對(duì)顧客來(lái)說(shuō)可能是（queue（A.K.Erlang,aDanishephoneengineer）的一篇，從那時(shí)起的名字就與概率排隊(duì)模型緊密聯(lián)系了在一起，該的為后來(lái)排隊(duì)論的發(fā)展奠定了排隊(duì)模型的目的就是要規(guī)劃一種為顧客提供服務(wù)的方式以實(shí)現(xiàn)一定的運(yùn)營(yíng)效率，它并不象前面已經(jīng)遇到的一些模型（如線性規(guī)劃模型、存貯模型）務(wù)水平。這些平均值是系統(tǒng)對(duì)顧務(wù)水平的標(biāo)志，在后續(xù)的成本分析中將發(fā)揮重要的作用?！?排隊(duì)系統(tǒng)綜統(tǒng)、超市的收銀系統(tǒng)、通訊系統(tǒng)等。一些排隊(duì)系統(tǒng)的構(gòu)成十分明顯，而另一排隊(duì)系統(tǒng)的構(gòu)成可能很模糊。如從廣州往打，由于受廣州與之間信道限制時(shí)，就不得不等待，雖然打的人分散在全市的各個(gè)角落，彼此互不見(jiàn)面實(shí)這種無(wú)形的隊(duì)伍與超市收銀系統(tǒng)中的有形隊(duì)伍都可以構(gòu)成排隊(duì)系統(tǒng)中的隊(duì)列。facility設(shè)施空閑，則到達(dá)的顧客即刻得到服務(wù)，否則顧客將排隊(duì)等待或離去。通常會(huì)排隊(duì)系統(tǒng)的基本構(gòu)10-1輸隊(duì)普通的呼叫屬于損失制。系統(tǒng)如果有多個(gè)服務(wù)臺(tái)，各服務(wù)臺(tái)可以有各自獨(dú)立的服務(wù)outoutorder輸排隊(duì)系統(tǒng)的分類(lèi)描根據(jù)排隊(duì)系統(tǒng)的基本構(gòu)成，肯（Kendall）于1953年提出了排隊(duì)系統(tǒng)的分6項(xiàng)代碼來(lái)表示一個(gè)特定排隊(duì)模型的。M代表泊松輸入（相繼到達(dá)間隔時(shí)間服從負(fù)指數(shù)分布）或服務(wù)時(shí)間服從負(fù)指數(shù)分布；D代表確定的相繼到達(dá)間隔時(shí)間或服務(wù)時(shí)間；EK代表k階（Erlang）分布的相繼到達(dá)間按照肯排隊(duì)模型的記法，M/M/n代表顧客輸入為泊松分布，服務(wù)時(shí)間為負(fù)n個(gè)并聯(lián)服務(wù)臺(tái)的排隊(duì)系統(tǒng)；M/D/2/N代表泊松分布的顧客到達(dá)，確2N的排隊(duì)系統(tǒng)；D/G/1代表定長(zhǎng)輸繼到達(dá)間隔時(shí)間，三階分布的服務(wù)時(shí)間，c個(gè)并聯(lián)服務(wù)臺(tái)，系統(tǒng)容量為10，10，后到先服務(wù)的排隊(duì)系統(tǒng)。排隊(duì)系統(tǒng)的數(shù)量指一個(gè)特定的模型可能會(huì)有多種假設(shè)，同時(shí)也需要通過(guò)多種數(shù)量指標(biāo)來(lái)加以描述。由于受所處環(huán)境的影響，只需要選擇那些起關(guān)鍵作用的指標(biāo)作為模型求的對(duì)象。環(huán)境不同，選擇的指標(biāo)也會(huì)不同；例如，有時(shí)關(guān)心的是顧客平均等的時(shí)間，有時(shí)關(guān)心的是服務(wù)臺(tái)的利用率。Pnnn0N

pc1pc2 關(guān)的隨量，當(dāng)nc時(shí)有n個(gè)服務(wù)臺(tái)被占用，當(dāng)nc時(shí)有c個(gè)服務(wù)臺(tái)被占用。這也就是說(shuō)，在全部的服務(wù)臺(tái)被占滿之前，n個(gè)服務(wù)臺(tái)被占用同系統(tǒng)中有n個(gè)顧客qi代表有iq0p0pqi

（i0LPn具有LiiB

Bipic

Lq是對(duì)長(zhǎng)，代表隊(duì)列中顧客數(shù)量的期望值，則Lqii

LLq

1代表服務(wù)時(shí)間期望值，與式（10-4）1WWq 1用U代表服務(wù)臺(tái)利用率期望值，由于各服務(wù)臺(tái)的利用率不盡相同，所以U是所UB

如果c1，式（10-6）可簡(jiǎn)化為UB1p0§2最簡(jiǎn)單）在排隊(duì)論中經(jīng)常用到最簡(jiǎn)單流這一概念。所謂最簡(jiǎn)單流就是指在t這一時(shí)間段k個(gè)顧客到達(dá)服務(wù)系統(tǒng)的概率vk(t)服從泊松分布，即：） kv(t)et(t k

什么樣的排隊(duì)系統(tǒng)才能具有最簡(jiǎn)單流呢？可以通過(guò)如下三個(gè)標(biāo)準(zhǔn)來(lái)加以式（10-7）中的參數(shù)代表單位時(shí)間里到達(dá)顧客的平均數(shù)，即平均到達(dá)率。我們可以通過(guò)令t1求vk(t)的數(shù)學(xué)期望來(lái)加以證明： kv(1)kek

k1ek

k (kk k1既然1

負(fù)指數(shù)分布的服務(wù)時(shí)f(x)ex，F(xiàn)(x)1假設(shè)服務(wù)臺(tái)對(duì)顧客的服務(wù)時(shí)間tf(tet；則對(duì)于每一1

E(t)tf(t)dttetdttd(et

etd(t)1生死過(guò)一個(gè)顧客的到達(dá)將使系統(tǒng)狀態(tài)從n到n1，這一過(guò)程成為生；一個(gè)顧客的離開(kāi)將使系統(tǒng)狀態(tài)從n到n1，這一過(guò)程成為死系統(tǒng)狀態(tài)的轉(zhuǎn)移可以用狀態(tài)轉(zhuǎn)移（圖 01012n

10-2ij轉(zhuǎn)移弧上的轉(zhuǎn)移率為rij，那么這條轉(zhuǎn)移弧所發(fā)生的流量就是rijpi。流的平衡原理具有鮮明的ipip0p2p2p1 1p0p1p0p1p0表示p1總是可以實(shí)現(xiàn)的。第二個(gè)方程是根據(jù)狀態(tài)“1”的流平衡條件建立的，它涉及p0、p1p2p0p1p0p2兩個(gè)，進(jìn)p0p2p0的p0表示出來(lái)。pip0的函數(shù)，所以正規(guī)方程pi1i個(gè)狀態(tài)，正規(guī)方程pi1p0ip1()p()2 p()i 引入正規(guī)方程pi1i()n]p[1(()n]

1(

p01

ip()i(1 i起，所以可以用一個(gè)小寫(xiě)的希臘字母來(lái)代替，即。將代入上述 ipi(1i是到達(dá)率與服務(wù)率之比，被稱為繁忙率

的含義是平均服務(wù)時(shí)間與相繼到達(dá)平均間隔時(shí)間之比；11基本模希望在W和L之間建立起某種關(guān)系。（Little）公式給出了L、W和三者之LW，即系統(tǒng)中平均顧客數(shù)等于顧客平均到達(dá)率與平均逗留時(shí)間積。根據(jù)公式，自然可以得到關(guān)系 有了公式，即可得到如下排隊(duì)系統(tǒng)的基本模型L i

(1)[2233WL

] 1

Lq0p0 (n1)pn npn

L(1p0)L

(

W

(MM/1排隊(duì)系統(tǒng)構(gòu)建的，對(duì)LLqBL9，那9人，必須服務(wù)臺(tái)有10%的空閑時(shí)間§3排隊(duì)模型的應(yīng)[例10-1]某醫(yī)院的一個(gè)診室根據(jù)來(lái)診和診治的時(shí)間記錄，任意100個(gè)工作小時(shí)，每小時(shí)來(lái)就診的數(shù)n的出現(xiàn)次數(shù)，以及任意100個(gè)完成診治v10-1所示，試分析該排隊(duì)系統(tǒng)。10-100.0~10.2~20.4~30.6~940.8~6561.0~5611.2~0合合解MM/1計(jì)算每小時(shí)的平均到達(dá)數(shù)，即到達(dá)率

2.1（人/小時(shí)計(jì)算每次診治的平均時(shí)間（v值取區(qū)間中值每次診治的平均時(shí)間

0.4（小時(shí)/人012.50通過(guò)統(tǒng)計(jì)檢驗(yàn)的方法，認(rèn)定在一定顯著水平下，的到達(dá)服從參數(shù)21 2

L2.52.15.25（人LqL0.845.254.41（人 W2.52.12.5（小時(shí) Wq2.52.12.1（小時(shí)[10-2]2090%的顧客都能有座位，則應(yīng)設(shè)置多少個(gè)等待席位。解：MM/190%N+1的概率不小0.9，即：N

N(1) i1N23 N2lg0.1

lg0.18lg0.75N[例10-3]某一大型客運(yùn)公車(chē)大修率服從泊松分布，平均每天2臺(tái)。機(jī)修廠對(duì)每臺(tái)大修機(jī)車(chē)的修理時(shí)間服從負(fù)指數(shù)分布，平均每臺(tái)1廠年度運(yùn)行費(fèi)用K(K)0.1105K（K1.9105元又已知機(jī)車(chē)大修平均每天損失1000元試決定該客運(yùn)公修廠最佳的年度運(yùn)行費(fèi)解MM/1S1=（系統(tǒng)中的機(jī)車(chē)數(shù)）（每輛每天損失）（月工作日數(shù)L100021.521500( )0.1105KS

105KSS1S2

105K dS

43000105

1K41.8（萬(wàn)元(K)0.110541.81044.28（輛/天[10-4]315解：MM/1410- 0101234 10-利用流平衡方程組MM/1 )

i

（i0,1,2,3,4 再利用正規(guī)方程p0p11 1

151 1440.75，p0151(3)5444Lipip12p23p340p(123243)00.750.33(120.7530.7524有效的到達(dá)率顧客以客輸入率應(yīng)該是比小的e因?yàn)榉?wù)系統(tǒng)的利用率可以從兩個(gè)不同的角度表達(dá)1pe，即1pe，所以應(yīng)有(1p W

0.54（小時(shí)）32 qWqe

0.29（小時(shí)）17（分鐘 p4p0.7540.330.1044 ，[10-5]5個(gè)停車(chē)位，在車(chē)當(dāng)?？空緹o(wú)車(chē)時(shí)就向出租公司要車(chē)設(shè)出租車(chē)以平均每小時(shí)8（8），（2）（3）解：將?？空九c到達(dá)的出租車(chē)作為一個(gè)排隊(duì)系統(tǒng)，1號(hào)車(chē)位相當(dāng)于正在接受服務(wù)的位置，2、3、4、5MM/15排隊(duì)模e10(1p01p01

10(1p0

0.8(16ipi i00ipi i0012345合44ppi1p555LipiW

2.4100.356（小時(shí)）21（分鐘p1p010.18[例10-6]設(shè)一名工人負(fù)責(zé)照管6臺(tái)自床，當(dāng)機(jī)床需要加料或發(fā)生故障時(shí)就1，0.1小時(shí)（10解：MM/16610-4加有限的有限的圖10-4極限狀態(tài)，顧客的到達(dá)率自然減少到“0令望的負(fù)指數(shù)分布，那么將是平均逗留時(shí)間的倒數(shù)。需要注意的是，此時(shí)的不能0123456 0123456 10-率就是2，這樣依次10-5所示的系統(tǒng)狀態(tài)轉(zhuǎn)移圖。根據(jù)圖10-5可得穩(wěn)定狀態(tài)流平衡方程06P0

(i

(iP

(6i)!() 100.1P6!(0.1)P0.6P P6!(0.1)2P P6!(0.1)3P0.12P P6!(0.1)4P P6!(0.1)5

0.0072P

P6!(0.1)6

66又由于Pi1P00.48451P010.484566LiPiW

0.84540.164（小時(shí)）9.84（分鐘 WqW0.164100.064（小時(shí)）3.84（分鐘 L0.84540.141 [例10-7]如果將上例改為三名工人聯(lián)合負(fù)責(zé)看管20臺(tái)自床，其他各項(xiàng)數(shù)解：MM32020S3N200.110-601234i10-3中，由于當(dāng)i12P0.5105，故忽略不計(jì)。i1 (3i)Pi L Lq L2.126770.106 e W

2.126770.119（小時(shí)）7.14（分鐘Wqe

0.019（小時(shí)）1.14（分鐘Pi(i-3)0003----1102--2201--3300--431053206330734083509360370380390率0.6人/0.4人/解MMS，S310-7所示。 001S (SSSSS10-根據(jù)圖10-7可得穩(wěn)定狀態(tài)流平衡方程(i1)Pi1Pi1(i)Pi

（1iS（iS這里P1

1i

SS11

SP0[ ) )i0i! S!1P1 i!()

（iSP S!SiS()

（iSLLqiS (SiSLq

(iS)PiS!(1)2

WL

WLq 0.41.5S30.40.5

P0[0!1!

3!1

1.53Lq3!(10.5)20.210.236（人L

0.2361.51.736（人Wq

0.393（分鐘顧客在系統(tǒng)中的平均逗留時(shí)間（不包括就餐的時(shí)間WL1.7362.893（分鐘 M/M/1模型的標(biāo)準(zhǔn)公式就能計(jì)算出每輛卡車(chē)在糧庫(kù)的平均逗留時(shí)3萬(wàn)元。40萬(wàn)元。100萬(wàn)元。來(lái)進(jìn)行，而方案三需要分解為兩個(gè)獨(dú)立的M/M/1系統(tǒng)。由于這兩個(gè)獨(dú)立的M/M/1系統(tǒng)具有相同的系統(tǒng)參數(shù)；因此，在分析個(gè)別車(chē)輛時(shí)，只研究其中一個(gè)系10-4給出了各方案車(chē)輛在系統(tǒng)中的平均逗留時(shí)間，這一結(jié)果足以使 M/M9（人/小時(shí)10（人/小時(shí)60（分鐘1M/M62M/M/93M/M§4非排隊(duì)模假設(shè)的排隊(duì)模型。鑒于此，本節(jié)將對(duì)幾種典型的非排隊(duì)模型進(jìn)行LLqL

WWqE(TLqLcE(TMG/1模MG/1模型，服務(wù)時(shí)間T是一般分布（但要求期望值E(T)和方差Var(T都存在MM/11還是必要的，這里 E(T)。在上述條件下有E(TL

22Var(T)2(1)Pollaczek-Khintchine（P-K）公式，只要知道、E(T和Var(T，不W、WqLq。[10-10]2302（1）（2）f(T)e1T，Tf(T)0 T解（1）10.410.50.4W

10（分鐘

W

0.50.5

8（分鐘（2）令T為服務(wù)時(shí)間，那么T1xx1的負(fù)指數(shù)分布；于是E(T2，Var(TVar(1xVar(x1E(T0.420.8P-K公式L0.8

0.820.422(1

WL2.87（分鐘，W

5 MD/1模對(duì)于服務(wù)時(shí)間是確定常數(shù)的情形，由于有T1和Var(T)0P-K式將簡(jiǎn)化為

L

2(1[例10-11]一自動(dòng)汽車(chē)機(jī)，每輛汽車(chē)的時(shí)間均為6分鐘，汽車(chē)按泊松15LLq、W和Wq。解：MD/14，E(T)10，0.4，Var(T)2L0.4 0.533（輛）2(10.4)Lq0.5330.40.133（輛W0.5330.133（小時(shí)）8（分鐘4W0.1330.033（小時(shí)）2（分鐘 P-K公式LLqW和Wq最小。這完全符合人們通常的理解，即服務(wù)時(shí)間越有規(guī)律，等候的時(shí)間也[10-12]一裝卸隊(duì)專為來(lái)到碼頭倉(cāng)庫(kù)的貨車(chē)裝卸貨物，設(shè)貨車(chē)的到達(dá)服從泊每班（8小時(shí)）的生產(chǎn)費(fèi)用為(204x（2）解：計(jì)算一小時(shí)的費(fèi)用，該費(fèi)用包括裝卸隊(duì)費(fèi)用和汽車(chē)在系統(tǒng)中逗留的損失c(204x)862x3Lx2L 32(1)2

2x3(3(3

c2.5dc

(2x 0.5d

2[x(x3)x2(x

02135x202.51112之間有一個(gè)根，分別比較二者所對(duì)應(yīng)的費(fèi)用值，因有c(11)12.858、c(12)13.42211名裝卸工人。c204x15(

)2.50.5x

2x令dc0.590

0 (x(x3)290x比較c(12和c(13，由于c(12c(1313.51213MEk/1模當(dāng)服務(wù)時(shí)間為定長(zhǎng)時(shí)，均方差01；而均方差介于這二者之間的一種理論分布稱 （Erlang）分布。1 f(t) （t0 kk如果服務(wù)臺(tái)對(duì)顧客的服務(wù)不是一項(xiàng)，而是按順序進(jìn)行的k項(xiàng)，又假設(shè)其中每一項(xiàng)服務(wù)的服務(wù)時(shí)間都具有相同的負(fù)指數(shù)分布則總的服務(wù)時(shí)間服從k階分布。實(shí)際上分布是Gamma分布的一個(gè)特例，分布的數(shù)學(xué)期望和方差分別 為E(t) 、Var(t) 。這里有兩個(gè)參數(shù)和k，有于k值的不同，可以 k到不同的分布，見(jiàn)圖10-8。當(dāng)k1時(shí)是負(fù)指數(shù)分布，當(dāng)k時(shí)是定長(zhǎng)分kkkkkkt將Var(t)

1k

10-P-K(k1)L 2k(1)

(k1)Lq2k(1)WL

WLq [10-13]4道工序，每一工序的工序時(shí)間均服從期望2（小時(shí)）的負(fù)指數(shù)分布。該產(chǎn)品的毛坯按泊松分布到達(dá)，平均到達(dá)率為每小0.14道工序的期望時(shí)間。

1均每道工序所需要的時(shí)間。依題意可知：0.11

2（0.125

0.8，E(t)18，Var(t)

k

16(41)L0.8 2.8（件24(1WL2.828（小時(shí) 428§5具有優(yōu)先級(jí)的排隊(duì)模NN級(jí)享有最低的中每一級(jí)別顧客的輸入均服從泊松分布，用i（i1, ,N）代表具有第i優(yōu)1（表示每名顧客的服務(wù)時(shí)間1服務(wù)。因此，對(duì)于具有別優(yōu)先級(jí)的顧客在排隊(duì)系統(tǒng)中得到服務(wù)的情況就如 別優(yōu)先級(jí)的顧客只要將輸入率換以1，有所改變。因此，對(duì)W12其中W1和W2

W12 1

即

1W2 N

WN W1Ni1 N N其中 1。[例10-14]某醫(yī)院門(mén)診部的患者按泊松分布到達(dá)，平均到達(dá)率2人/3人/解：3、10.2、20.6、3

3

( 3(0.2W0.20.60.4540.20.357 W0.20.61.210.20.3570.60.454 WW10.3570.3330.024（小時(shí)）1.44（分鐘

10.4860.3330.153（小時(shí)）9.18（分鐘11.3790.3331.046（小時(shí)）62.76（分鐘MM2PL公式，可推得WLq1 ()2( 1( W [1( )2 2(1 {(2

(2

]} W1{3(60.2)2

]} 3(6 W12{3(60.8)2

W123{3(62)2[133(62)]}3

W0.60.20.33910.20.3337 W1.20.60.20.3750.20.33370.60.3410 W1q0.0004（小時(shí)）0.024（分鐘）W2q0.0077（小時(shí)）0.462（分鐘）W3q0.0656（小時(shí)）3.936（分鐘§6排隊(duì)系統(tǒng)的最優(yōu)排隊(duì)系統(tǒng)的最優(yōu)化問(wèn)題可分為兩類(lèi)，即系統(tǒng)設(shè)計(jì)的最優(yōu)化和系統(tǒng)控制的最優(yōu)化0成為了排隊(duì)論研究的重點(diǎn)之一。動(dòng)態(tài)分析是建立在靜態(tài)分析的基礎(chǔ)之上的，本只靜態(tài)最優(yōu)化問(wèn)題MM/1模型中最設(shè)系統(tǒng)單位時(shí)間的服務(wù)費(fèi)用與值成正比，比例系數(shù)為c1；每一個(gè)顧客在系統(tǒng)中逗留（包括接受服務(wù)的時(shí)間）的等待費(fèi)用與等待時(shí)間成正比，比例系數(shù)為c2，如果用TC()值時(shí)的系統(tǒng)總費(fèi)用，則：TC()c1c2Lc1

當(dāng)c、c只與顧客的到達(dá)率有關(guān)，根號(hào)前取“+ 1對(duì)于M/M/1/N排隊(duì)系統(tǒng)，PN為顧客被 的概率，1PN就是顧客被接受的概率，所以(1PN)就是單位時(shí)間實(shí)際進(jìn)入系統(tǒng)的平均顧客數(shù)。在穩(wěn)定狀態(tài)下(1PN)r(1PN)rc1Z代表純利1 NZ(1PN)rc1r1N1c1rN1N1令dz0，可得N 1d (1N1 NNNr21 10-應(yīng)滿足此式，雖然此式中的cr、（）N ，rc已知數(shù)，但要通過(guò)此式求解出卻不是一件容易的事。對(duì)該問(wèn)題的處理經(jīng)常，rc1

對(duì)于M/M/1/N/N排隊(duì)系統(tǒng)，仍然按照設(shè)備故障問(wèn)題來(lái)加以考慮。設(shè)障的時(shí)間服從負(fù)指數(shù)分布。c1的含義同上，r