隨機(jī)過(guò)程與排隊(duì)論12

隨機(jī)過(guò)程與排隊(duì)論計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐Email：guxf@02三月20242024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐上一講內(nèi)容回顧生滅過(guò)程排隊(duì)論簡(jiǎn)介排隊(duì)的概念基本的排隊(duì)系統(tǒng)排隊(duì)系統(tǒng)的基本組成經(jīng)典排隊(duì)系統(tǒng)的符號(hào)表示方法40－22024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐本講主要內(nèi)容無(wú)限源的簡(jiǎn)單排隊(duì)系統(tǒng)—M/M/1/

問(wèn)題的引入隊(duì)長(zhǎng)等待時(shí)間與逗留時(shí)間Little公式忙期輸出過(guò)程40－32024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐§5.1M/M/1/

問(wèn)題的敘述顧客到達(dá)為參數(shù)

(>0)的泊松過(guò)程，即相繼到達(dá)的間隔時(shí)間序列{

n，n1}獨(dú)立、服從參數(shù)為

(>0)的負(fù)指數(shù)分布F(t)＝1-e-t，t0；顧客所需的服務(wù)時(shí)間序列{

n,n1}獨(dú)立、服從參數(shù)為

(>0)的負(fù)指數(shù)分布G(t)＝1-e-t，t0；系統(tǒng)中只有一個(gè)服務(wù)臺(tái)；容量為無(wú)窮大，而且到達(dá)過(guò)程與服務(wù)過(guò)程彼此獨(dú)立。40－42024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐2.隊(duì)長(zhǎng)

假定N(t)表示在時(shí)刻t系統(tǒng)中的顧客數(shù)，包括正在被服務(wù)的顧客數(shù)，即N(t)表示時(shí)刻t系統(tǒng)的隊(duì)長(zhǎng)，t0，且令pij(t)＝P{N(t+t)＝j(luò)|N(t)＝i}，i,j＝0,1,2,…則1)pi,i+1(t)＝P{在t內(nèi)到達(dá)一個(gè)而服務(wù)未完成}

＋{在t內(nèi)到達(dá)j個(gè)而服務(wù)完j-1個(gè)}

＝P{1t，1>t}

＋{1+…+jt<1+…+j+1，

1+…+j-1t<1+…+j}＝(1-e-t)e-t＋o(t)＝t＋o(t) i＝0,1,2,…40－52024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐隊(duì)長(zhǎng)(續(xù)1)pi,i-1(t)＝P{在t內(nèi)未到達(dá)而服務(wù)完成一個(gè)}

＋{在t內(nèi)到達(dá)j個(gè)而服務(wù)完j+1個(gè)}

＝P{1>t，1t}

＋{1+…+jt<1+…+j+1，

1+…+j+1t<1+…+j+2}＝(1-e-t)e-t＋o(t)＝t＋o(t) i＝1,2,3,…類似分析可得pij(t)＝o(t)， |i-j|240－62024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐隊(duì)長(zhǎng)(續(xù)2)綜合上述1)2)3)得{N(t)，t0}是可列無(wú)限狀態(tài)E＝{0,1,2,…}上的生滅過(guò)程，其參數(shù)為此生滅過(guò)程的絕對(duì)分布pj(t)＝P{N(t)=j}，j=0,1,2,…的?？耍绽士朔匠探M為40－72024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐隊(duì)長(zhǎng)(續(xù)3)令＝，則稱為系統(tǒng)的交通強(qiáng)度(Trafficindensity)。有如下結(jié)論：令pj＝，j=0,1,2,…，則1)當(dāng)1時(shí)，pj＝0，j=0,1,2,…不構(gòu)成概率分布；2)當(dāng)<1時(shí)，{pj，j=0,1,2,…}存在，與初始條件無(wú)關(guān)，且pj＝(1-)j，j=0,1,2,…構(gòu)成一個(gè)幾何概率分布。40－82024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐結(jié)論在統(tǒng)計(jì)平衡的條件下(<1)：平均隊(duì)長(zhǎng)40－92024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐結(jié)論(續(xù)1)等待隊(duì)長(zhǎng)的分布平均等待隊(duì)長(zhǎng)40－102024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐結(jié)論(續(xù)2)隊(duì)長(zhǎng)的方差40－112024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐結(jié)論(續(xù)3)等待隊(duì)長(zhǎng)的方差40－121-P{Nq=0}=1-(1-

2)=

22024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐結(jié)論(續(xù)4)在等待條件下的等待隊(duì)長(zhǎng)分布在等待條件下的平均等待隊(duì)長(zhǎng)根據(jù)隊(duì)長(zhǎng)分布意知：

p0=1－也是系統(tǒng)空閑的概率，而

正是系統(tǒng)繁忙的概率。顯然，越大，系統(tǒng)就越繁忙。=pj-140－132024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐3.等待時(shí)間與逗留時(shí)間假定顧客是先到先服務(wù)。

定理在統(tǒng)計(jì)平衡(<1)下，顧客的等待時(shí)間分布函數(shù)Wq(t)＝P{Wqt}為Wq(t)＝1－

e-(1-)t，t0平均等待時(shí)間為等待時(shí)間的方差為40－142024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐證明1)當(dāng)t=0時(shí)，有

Wq(0)＝P{Wq=0}＝P{顧客到達(dá)時(shí)看到的隊(duì)長(zhǎng)為0}＝p0-2)當(dāng)t>0時(shí)，有

Wq(t)＝P{Wq=0}＋P{0<Wqt}

＝p0-＋{0<Wqt｜顧客到達(dá)時(shí)看到的隊(duì)長(zhǎng)為j}?pj-

其中，pj-表示顧客到達(dá)時(shí)看到有j個(gè)顧客的平穩(wěn)概率。對(duì)于M/M/1/

排隊(duì)系統(tǒng)，有

pj-＝pj，j=0,1,2,…40－152024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐證明于是Wq(t)＝p0-+40－162024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐證明(續(xù))平均等待時(shí)間等待時(shí)間的方差40－172024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐逗留時(shí)間由于顧客的逗留時(shí)間等于等待時(shí)間加上服務(wù)時(shí)間，即W＝Wq＋

且Wq與相互獨(dú)立，于是平均逗留時(shí)間逗留時(shí)間的方差40－182024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐Little公式對(duì)于一個(gè)排隊(duì)系統(tǒng)，如果在它達(dá)到統(tǒng)計(jì)平衡狀態(tài)后，系統(tǒng)中任一時(shí)刻的平均隊(duì)長(zhǎng)、平均等待隊(duì)長(zhǎng)，與每一顧客在系統(tǒng)中的平均逗留時(shí)間、平均等待時(shí)間之間有關(guān)系式：成立，則稱該排隊(duì)系統(tǒng)滿足Little公式。其中

e表示單位時(shí)間內(nèi)實(shí)際進(jìn)入系統(tǒng)的平均顧客數(shù)。40－192024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐服務(wù)的顧客，在他后面排隊(duì)等待服務(wù)的平均顧客數(shù)等于在他的平均等待時(shí)間內(nèi)實(shí)際進(jìn)入系統(tǒng)的平均顧客數(shù)，即；又考慮一個(gè)剛服務(wù)結(jié)束的顧客，在他離開(kāi)系統(tǒng)時(shí)留在系統(tǒng)中的平均顧客數(shù)等于在他的平均逗留時(shí)間內(nèi)實(shí)際進(jìn)入系統(tǒng)的平均顧客數(shù)，即。Little公式的直觀解釋在系統(tǒng)達(dá)到統(tǒng)計(jì)平衡下，可慮一個(gè)剛開(kāi)始接受

顯然，M/M/1/

排隊(duì)系統(tǒng)中，Little公式是成立的，且

e等于泊松過(guò)程的參數(shù)。40－202024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐4.忙期從N(t)由0變到1的時(shí)刻開(kāi)始到N(t)第一次又變回0時(shí)結(jié)束忙期的長(zhǎng)度與忙期的起點(diǎn)無(wú)關(guān)忙期長(zhǎng)度的概率密度其中，為修正貝塞爾(Bessel)函數(shù)。忙期長(zhǎng)度的分布函數(shù)40－212024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐忙期(續(xù))平均忙期長(zhǎng)度一個(gè)忙期中所服務(wù)的平均顧客數(shù)40－222024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐5.輸出過(guò)程在忙期內(nèi)相繼輸出的間隔時(shí)間是獨(dú)立、同參數(shù)

(>0)的隨機(jī)變量，即參數(shù)為的泊松流。當(dāng)系統(tǒng)空閑后，從開(kāi)始空閑時(shí)刻起，到下一個(gè)顧客服務(wù)完畢離去時(shí)之間的間隔時(shí)間不與服務(wù)時(shí)間同分布。

令Tn+表示第n個(gè)顧客服務(wù)完畢的離去時(shí)刻，則Tn+1+-Tn+表示離去的時(shí)間間隔，n1，于是，對(duì)t0有

P{Tn+1+－Tn+>t}

＝P{Nn+=0}·P{Tn+1+－Tn+>t|Nn+=0}

＋P{Nn+1}·P{Tn+1+－Tn+>t|Nn+1}

＝P{Nn+=0}·P{n+1＋

n+1>t}＋P{Nn+1}·P{n+1>t}其中n+1表示剩余到達(dá)間隔時(shí)間，與n+1獨(dú)立，而Nn+表示第n個(gè)離去顧客服務(wù)完畢離開(kāi)系統(tǒng)時(shí)的隊(duì)長(zhǎng)。40－232024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐輸出過(guò)程(續(xù))因此由于此式表示在統(tǒng)計(jì)平衡下，相繼輸出的間隔時(shí)間服從參數(shù)為（>0）的負(fù)指數(shù)分布。

另外，在統(tǒng)計(jì)平衡下，輸出的間隔時(shí)間相互獨(dú)立，因此對(duì)M/M/1/

系統(tǒng)，其統(tǒng)計(jì)平衡下的輸出過(guò)程與到達(dá)過(guò)程相同。40－242024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐例1

某火車站一個(gè)售票窗口，若到達(dá)該窗口購(gòu)票的顧客按泊松流到達(dá)，平均每分鐘到達(dá)1人，假定售票時(shí)間服從負(fù)指數(shù)分布，平均每分鐘可售2人，試研究該售票窗口前的排隊(duì)情況。解由題設(shè)知，＝1(人/分)，＝2(人/分)，＝，該系統(tǒng)按M/M/1/

型處理，于是在統(tǒng)計(jì)平衡下，有平均隊(duì)長(zhǎng)為(人)平均等待隊(duì)長(zhǎng)為(人)40－252024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐例1(續(xù))平均等待時(shí)間為(分鐘)平均逗留時(shí)間為(分鐘)顧客到達(dá)不需要等待的概率為等待隊(duì)長(zhǎng)超過(guò)5人的概率為40－262024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐例2

考慮某種產(chǎn)品的庫(kù)存問(wèn)題。如果進(jìn)貨過(guò)多，則會(huì)帶來(lái)過(guò)多的保管費(fèi)，如果存貨不足，則缺貨時(shí)影響生產(chǎn)，造成經(jīng)濟(jì)損失。最好的辦法是能及時(shí)供應(yīng)，但由于生產(chǎn)和運(yùn)輸?shù)确矫娴囊蛩?，一般講這是難以滿足的，因此希望找到一種合理的庫(kù)存s，使得庫(kù)存費(fèi)與缺貨損失費(fèi)的總和達(dá)到最小。假定需求是參數(shù)

的泊松流，生產(chǎn)是一個(gè)一個(gè)產(chǎn)品生產(chǎn)的，每生產(chǎn)一個(gè)產(chǎn)品所需時(shí)間為參數(shù)

的負(fù)指數(shù)分布。庫(kù)存一個(gè)產(chǎn)品的單位時(shí)間費(fèi)用為c元，缺一個(gè)產(chǎn)品造成的損失費(fèi)為h元，尋找一個(gè)最優(yōu)庫(kù)存量s，使得庫(kù)存費(fèi)與損失費(fèi)之和達(dá)到最?。ú豢紤]產(chǎn)品的運(yùn)輸時(shí)間）。40－272024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐例2(續(xù)1)解把生產(chǎn)產(chǎn)品的工廠看成是服務(wù)機(jī)構(gòu)，需求看作是輸入流，于是把問(wèn)題化成M/M/1/

系統(tǒng)，需求量表示隊(duì)長(zhǎng)，pk表示生產(chǎn)廠有k個(gè)訂貨未交的概率。設(shè)庫(kù)存量為s，則缺貨時(shí)的平均缺貨數(shù)為平均庫(kù)存數(shù)為40－282024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐例2(續(xù)2)單位時(shí)間的期望總費(fèi)用為用邊際分析法解上式，使上式最小的s應(yīng)滿足f(s-1)f(s)，f(s+1)f(s)，于是由f(s+1)f(s)得，于是由f(s-1)f(s)得因此取最佳s*為最靠近的正整數(shù)即可。40－292024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐例3

設(shè)船按泊松流進(jìn)港口，平均每天到達(dá)2條，裝卸時(shí)間服從負(fù)指數(shù)分布，平均每天裝卸3條船，求：平均等待對(duì)長(zhǎng)與平均等待時(shí)間；如果船在港口的停留時(shí)間超過(guò)一個(gè)值t0就要罰款，求遭罰款的概率；若每超過(guò)一天罰款c元，提前一天獎(jiǎng)勵(lì)b元。假定服務(wù)費(fèi)與服務(wù)率成正比，每天

h元，裝卸一條船收入a元，求使港口每天收入最大的服務(wù)率*的值。40－302024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐例3(續(xù)1)解由題設(shè)知，＝2(條/天)，＝3(條/天)，＝，該系統(tǒng)按M/M/1/

型處理。平均等待對(duì)長(zhǎng)為(條船)平均等待時(shí)間為(天)由于遭到罰款當(dāng)且僅當(dāng)船在港口的逗留時(shí)間超過(guò)t0，所以遭到罰款的概率為從費(fèi)用方面考慮，每天裝卸完條船收入a元，每天服務(wù)費(fèi)為h元。40－312024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐例3(續(xù)2)平均提前完成時(shí)間為平均延后時(shí)間為所以，港口一天的總收入為40－322024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐例3(續(xù)3)對(duì)f求導(dǎo)得討論：b＝c時(shí)，b＞c時(shí)，由于的符號(hào)在＞時(shí)完全由括號(hào)內(nèi)的兩項(xiàng)決定。令40－332024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐例3(續(xù)4)由上圖看出，y1與y2兩曲線有唯一交點(diǎn)，其橫坐標(biāo)為

*，

b

(b-c)

*y

y2y1且*唯一存在、有限，40－342024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐例3(續(xù)5)

b

(b-c)

*y

y2y1b＜c時(shí)，由下圖看出，y1與y2兩曲線仍有唯一交點(diǎn)，其橫坐標(biāo)為

*，且*唯一存在、有限，40－352024/3/2計(jì)算機(jī)科學(xué)與工程學(xué)院顧小豐例4

設(shè)顧客到達(dá)為泊松流，平均每小時(shí)到達(dá)個(gè)顧客是已知的。一個(gè)顧客在系統(tǒng)內(nèi)逗留每小時(shí)損失c1元，服務(wù)機(jī)