隨機過程與排隊論13

隨機過程與排隊論計算機科學與工程學院顧小豐Email：guxf@02三月2024無限源的簡單排隊系統(tǒng)—M/M/1/

問題的引入隊長等待時間與逗留時間Little公式忙期輸出過程計算機科學與工程學院顧小豐2024/3/2上一講內(nèi)容回顧顧客到達為參數(shù)

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

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

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

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

(>0)的負指數(shù)分布G(t)＝1-e-t，t0；系統(tǒng)中只有一個服務臺；容量為無窮大，而且到達過程與服務過程彼此獨立。忙期長度的分布函數(shù)平均忙期長度在忙期內(nèi)相繼輸出的間隔時間是獨立、同參數(shù)

(>0)的隨機變量，即參數(shù)為的泊松流輸出過程與到達過程相同,參數(shù)為

的泊松流等待時間分布函數(shù)：Wq(t)=1-

e-(1-)t，t0,

<1平均等待時間：逗留時間分布函數(shù)：平均逗留時間：隊長分布：pj＝(1-)j，j=0,1,2,…

<1等待隊長分布：平均隊長：平均等待隊長：37－22024/3/2計算機科學與工程學院顧小豐本講主要內(nèi)容具有可變輸入率的M/M/1/

問題的引入隊長等待時間與逗留時間Little公式具有可變服務率的M/M/1/

問題的引入隊長等待時間與逗留時間37－32024/3/2計算機科學與工程學院顧小豐例2

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

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

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

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

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

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

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

*，

b

(b-c)

*y

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

b

(b-c)

*y

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

*，且*唯一存在、有限，37－122024/3/2計算機科學與工程學院顧小豐例4

設顧客到達為泊松流，平均每小時到達個顧客是已知的。一個顧客在系統(tǒng)內(nèi)逗留每小時損失c1元，服務機構(gòu)的費用正比于服務率，每小時每位顧客的費用為c2元。假定服務時間為參數(shù)的負指數(shù)分布，求最佳服務率

*，使得整個系統(tǒng)總費用最少。解平均對長每小時顧客的平均損失費為元37－132024/3/2計算機科學與工程學院顧小豐例4(續(xù))每小時服務機構(gòu)的平均費用為c2元，單位時間內(nèi)平均總費用為由得因為所以最佳服務率為*，此時37－142024/3/2計算機科學與工程學院顧小豐§5.2具有可變輸入率的M/M/1/

在實際中，盡管顧客源源不斷到達，但并不一定進入排隊系統(tǒng)接受服務。常見的一種現(xiàn)象就是到達的顧客看到系統(tǒng)空閑或者等待的顧客不多則進入系統(tǒng)接受服務，看到前面排著長對時則產(chǎn)生猶豫，考慮是否排隊接受服務，這樣，如果排隊人數(shù)少時進入系統(tǒng)接受服務的可能性就大，排隊人數(shù)多則進入系統(tǒng)接受服務的可能性就小。顧客進入系統(tǒng)接受服務的可能性大小可用一概率表示，一般情況下是隊長的函數(shù)。37－152024/3/2計算機科學與工程學院顧小豐1.問題的敘述顧客到達為參數(shù)

(>0)的泊松過程；顧客到達看到隊長為k時，進入系統(tǒng)的概率為ak(0＜ak＜1)，1＝a0＞a1＞…＞ak→0(k→

)，即排隊越長進入的可能性越小(令ak＝)；顧客所需的服務時間序列{

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

(>0)的負指數(shù)分布；系統(tǒng)中只有一個服務臺；容量為無窮大，而且到達過程與服務過程彼此獨立。37－162024/3/2計算機科學與工程學院顧小豐2.隊長我們?nèi)杂肗(t)表示在時刻t系統(tǒng)中的顧客數(shù)，令pij(t)＝P{N(t+t)＝j|N(t)＝i}，i,j＝0,1,2,…則類似§5.1中pij(t)的推導，有于是，{N(t)，t0}是E＝{0,1,2,…}上的生滅過程，其參數(shù)為37－172024/3/2計算機科學與工程學院顧小豐定理定理令pj＝，j=0,1,2,…，則對一切＝，{pj，j0}存在，與初始條件無關，且構(gòu)成參數(shù)為的泊松概率分布。證明對一切＝，顯然有所以{pj，j0}存在，與初始條件無關。再根據(jù)生滅過程的平穩(wěn)分布公式易得結(jié)果。37－182024/3/2計算機科學與工程學院顧小豐結(jié)論在統(tǒng)計平衡的條件下，有平均隊長平均等待隊長37－192024/3/2計算機科學與工程學院顧小豐3.等待時間與逗留時間

假定顧客是先到先服務。此處的等待時間是指到達且進入系統(tǒng)接受服務的顧客的等待時間。

定理在統(tǒng)計平衡下，進入系統(tǒng)接受服務的顧客的等待時間分布函數(shù)為：

Wq(t)＝P{Wq≤t} 平均等待時間為：37－202024/3/2計算機科學與工程學院顧小豐證明設pj-表示到達的顧客看到系統(tǒng)中有j個顧客的平穩(wěn)概率。對于M/M/1/

排隊系統(tǒng)，有pj-＝pj，j=0,1,2,…但是，此處到達的顧客不一定進入系統(tǒng)，因此，若令qj表示到達且進入系統(tǒng)的顧客看到有j個顧客的平穩(wěn)概率，則37－212024/3/2計算機科學與工程學院顧小豐證明(續(xù)1)于是，當t=0時，有當t＞0時，有其中，表示正在接受服務的顧客的剩余服務時間，i為排隊中第i個顧客的服務時間(1ij-1)。顯然，,1,2,…,j-1相互獨立、服從參數(shù)為的負指數(shù)分布，即+1+2+…+j-1服從參數(shù)為的j階愛爾朗分布，于是^^^37－222024/3/2計算機科學與工程學院顧小豐證明(續(xù)2)而平均等待時間為參數(shù)為的j階愛爾朗分布的數(shù)學期望為j/該顧客的平均等待時間等于對中的j個顧客的平均服務時間，服從參數(shù)為的j階愛爾朗分布37－232024/3/2計算機科學與工程學院顧小豐逗留時間類似地，顧客的逗留時間的分布函數(shù)為平均逗留時間為37－242024/3/2計算機科學與工程學院顧小豐Little公式對于可變輸入率的排隊系統(tǒng)，由于一部分到達的顧客沒有進入系統(tǒng)而造成流失，流失的大小可用概率表示。顯然，顧客到達時，發(fā)現(xiàn)系統(tǒng)有k個顧客而離去的概率為1-ak，因此顧客到達沒有進入系統(tǒng)而流失的概率為相反地，一個顧客到達而進入系統(tǒng)的概率為單位時間內(nèi)到達且進入系統(tǒng)的平均顧客數(shù)為可以驗證，在該系統(tǒng)中，Little公式成立，即37－252024/3/2計算機科學與工程學院顧小豐§5.3具有可變服務率的M/M/1/

在實際中，當服務臺前出現(xiàn)排隊時，排隊的長短往往直接影響服務員的工作效率。一般講，當排隊過長時服務員會提高服務速度，另一方面，對一個不熟練的服務員，當看到對長太長時可能慌張而降低了服務率。37－262024/3/2計算機科學與工程學院顧小豐1.問題的敘述顧客到達為參數(shù)

(＞0)的泊松過程；顧客所需的服務時間序列{

n,n≥1}獨立、服從負指數(shù)分布，具有兩個服務率

1、2(0＜

1＜

2)，當對長＜m（m是一個固定的正整數(shù)）時，服務員用速率1工作，當對長≥m時，服務員用速率2工作；系統(tǒng)中只有一個服務臺；容量為無窮大，而且到達過程與服務過程彼此獨立。37－272024/3/2計算機科學與工程學院顧小豐2.隊長用N(t)表示在時刻t系統(tǒng)中的顧客數(shù)，令pij(t)＝P{N(t+t)＝j|N(t)＝i},i,j＝0,1,2,…則類似§5.1中pij(t)的推導，有于是，{N(t)，t0}是E＝{0,1,2,…}上的生滅過程，其參數(shù)為37－282024/3/2計算機科學與工程學院顧小豐定理令當2≥1時，pj＝0，j=01,2,…當2＜1時，{pj，j≥0}存在，與初始條件無關，且，則37－292024/3/2計算機科學與工程學院顧小豐證明因為37－302024/3/2計算機科學與工程學院顧小豐證明(續(xù))所以，當2≥1時，pj＝0，j=01,2,…當2＜1時，{pj，j≥0}存在，與初始條件無關，且37－312024/3/2計算機科學與工程學院顧小豐結(jié)論在統(tǒng)計平衡的條件下，有平均隊長為平均等待隊長為37－322024/3/2計算機科學與工程學院顧小豐3.等待時間與逗留時間假定顧客是先到先服務。由于服務率是可變的，因此顧客的服務時間與該顧客接受服務時系統(tǒng)的隊長有關，這樣就不能使用前面的方式來討論等待時間的分布函數(shù)。但是，在統(tǒng)計平衡下，顧客服務完畢離開系統(tǒng)時留在系統(tǒng)中的顧客數(shù)（不包括該離去的顧客）等于在該顧客的逗留時間內(nèi)到達的顧客數(shù)，即pj+＝P{N+=j}＝P{在逗留時間W內(nèi)到達j個顧客}

由于當隊長＜m時，接受服務的顧客的服務時間服從參數(shù)為1的負指數(shù)分布，當對長≥m時，其服務時間服從參數(shù)為2的負指數(shù)分布，因此在統(tǒng)計平衡下，某個顧客的服務時間分布依賴于當時的隊長。37－332024/3/2計算機科學與工程學院顧小豐結(jié)論在統(tǒng)計平衡下，有 pj+＝pj，j=0,1,2,…顧客在系統(tǒng)中的平均逗留時間為顧客在系統(tǒng)中的平均等待時間為（由Little公式）顧客在系統(tǒng)中接受的平均