隨機(jī)過程與排隊論12

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

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

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

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

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

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

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

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

假定N(t)表示在時刻t系統(tǒng)中的顧客數(shù)，包括正在被服務(wù)的顧客數(shù)，即N(t)表示時刻t系統(tǒ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á)一個而服務(wù)未完成}

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

＝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ī)科學(xué)與工程學(xué)院顧小豐隊長(續(xù)1)pi,i-1(t)＝P{在t內(nèi)未到達(dá)而服務(wù)完成一個}

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

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

2)=

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

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

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

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

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

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

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

＝p0-＋{0<Wqt｜顧客到達(dá)時看到的隊長為j}?pj-

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

排隊系統(tǒng)，有

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

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

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

顯然，M/M/1/

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

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

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

令Tn+表示第n個顧客服務(wù)完畢的離去時刻，則Tn+1+-Tn+表示離去的時間間隔，n1，于是，對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á)間隔時間，與n+1獨立，而Nn+表示第n個離去顧客服務(wù)完畢離開系統(tǒng)時的隊長。40－232024/3/2計算機(jī)科學(xué)與工程學(xué)院顧小豐輸出過程(續(xù))因此由于此式表示在統(tǒng)計平衡下，相繼輸出的間隔時間服從參數(shù)為（>0）的負(fù)指數(shù)分布。

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

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

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

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

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

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

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

系統(tǒng)，需求量表示隊長，pk表示生產(chǎn)廠有k個訂貨未交的概率。設(shè)庫存量為s，則缺貨時的平均缺貨數(shù)為平均庫存數(shù)為40－282024/3/2計算機(jī)科學(xué)與工程學(xué)院顧小豐例2(續(xù)2)單位時間的期望總費用為用邊際分析法解上式，使上式最小的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ī)科學(xué)與工程學(xué)院顧小豐例3

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

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

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

*，

b

(b-c)

*y

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

b

(b-c)

*y

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

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

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