排隊論模型24067

1、排隊論模型排隊論也稱隨機服務系統(tǒng)理論。它涉及的是建立一些數(shù)學模型，藉以對隨機發(fā)生的需求提供服務的系統(tǒng)預測其行為?，F(xiàn)實世界中排隊的現(xiàn)象比比皆是，如到商店購貨、輪船進港、病人就診、機器等待修理等等。排隊的內(nèi)容雖然不同，但有如下共同特征： 有請求服務的人或物，如候診的病人、請求著陸的飛機等，我們將此稱為“顧客”。 有為顧客提供服務的人或物，如醫(yī)生、飛機跑道等，我們稱此為“服務員”。由顧客和服務員就組成服務系統(tǒng)。 顧客隨機地一個一個（或者一批一批）來到服務系統(tǒng)，每位顧客需要服務的時間不一定是確定的，服務過程的這種隨機性造成某個階段顧客排長隊，而某些時候服務員又空閑無事。排隊論主要是對服務系統(tǒng)建立數(shù)學模

2、型，研究諸如單位時間內(nèi)服務系統(tǒng)能夠服務的顧客的平均數(shù)、顧客平均的排隊時間、排隊顧客的平均數(shù)等數(shù)量規(guī)律。一、 排隊論的一些基本概念為了敘述一個給定的排隊系統(tǒng)，必須規(guī)定系統(tǒng)的下列組成部分： 輸入過程 即顧客來到服務臺的概率分布。排隊問題首先要根據(jù)原始資料，由顧客到達的規(guī)律、作出經(jīng)驗分布，然后按照統(tǒng)計學的方法（如卡方檢驗法）確定服從哪種理論分布，并估計它的參數(shù)值。我們主要討論顧客來到服務臺的概率分布服從泊松分布，且顧客的達到是相互獨立的、平穩(wěn)的輸入過程。所謂“平穩(wěn)”是指分布的期望值和方差參數(shù)都不受時間的影響。 排隊規(guī)則 即顧客排隊和等待的規(guī)則，排隊規(guī)則一般有即時制和等待制兩種。所謂即時制就是服務臺被

3、占用時顧客便隨即離去；等待制就是服務臺被占用時，顧客便排隊等候服務。等待制服務的次序規(guī)則有先到先服務、隨機服務、有優(yōu)先權(quán)的先服務等，我們主要討論先到先服務的系統(tǒng)。 服務機構(gòu) 服務機構(gòu)可以是沒有服務員的，也可以是一個或多個服務員的；可以對單獨顧客進行服務，也可以對成批顧客進行服務。和輸入過程一樣，多數(shù)的服務時間都是隨機的，且我們總是假定服務時間的分布是平穩(wěn)的。若以n表示服務員為第n個顧客提供服務所需的時間，則服務時間所構(gòu)成的序列n，n=1，2，所服從的概率分布表達了排隊系統(tǒng)的服務機制，一般假定，相繼的服務時間1，2，是獨立同分布的，并且任意兩個顧客到來的時間間隔序列Tn也是獨立的。如果按服務系統(tǒng)

4、的以上三個特征的各種可能情形來對服務系統(tǒng)進行分類，那么分類就太多了。因此，現(xiàn)在已被廣泛采用的是按顧客相繼到達時間間隔的分布、服務時間的分布和服務臺的個數(shù)進行分類。研究排隊問題的目的，是研究排隊系統(tǒng)的運行效率，估計服務質(zhì)量，確定系統(tǒng)參數(shù)的最優(yōu)值，以決定系統(tǒng)的結(jié)構(gòu)是否合理，設計改進措施等。所以，必須確定用來判斷系統(tǒng)運行優(yōu)劣的基本數(shù)量指標，這些數(shù)量指標通常是： 隊長 指排隊系統(tǒng)中的顧客數(shù)，它的期望值記為L系；排隊長，指在排隊系統(tǒng)中排隊等待服務的顧客數(shù)，其期望值記為L隊。系統(tǒng)中的顧客數(shù) = 等待服務的顧客數(shù) + 正被服務的顧客數(shù)所以L隊（或L系）越大，說明服務效率越低。 逗留時間 指一個顧客在排隊系統(tǒng)

5、中的停留時間，即顧客從進入服務系統(tǒng)到服務完畢的整個時間。其期望值記為W系。等待時間，指一個顧客在排隊系統(tǒng)中等待服務的時間，其期望值記為W隊。 逗留時間 = 等待時間 + 服務時間 忙期 指從顧客到達空閑服務機構(gòu)起到服務機構(gòu)再次為空閑這段時間長度，即服務機構(gòu)連續(xù)工作的時間長度。它關(guān)系到服務員的工作長度，即服務機構(gòu)連續(xù)工作的時間長度。它關(guān)系到服務員的工作強度、忙期的長度和一個忙期中平均完成服務的顧客數(shù)，這些都是衡量服務效率的指標。要計算以上這些指標必須知道系統(tǒng)狀態(tài)的概率，所謂系統(tǒng)狀態(tài)即時刻t時排隊系統(tǒng)中的顧客數(shù)。如果時刻t時排隊系統(tǒng)中有n個顧客，就說系統(tǒng)的狀態(tài)是n，其概率一般用Pn(t)表示。求P

6、n(t)的方法，首先要建立含Pn(t)關(guān)系式，因t為連續(xù)變量而n只取非負整數(shù)，所以建立的Pn(t)的關(guān)系式一般是微分差分方程，這時要求方程的解是不容易的，有時即使求出也很難利用。因此，往往只求穩(wěn)態(tài)解Pn，求Pn并不一定求t時的Pn(t)極限，而只需由=0，用Pn代替Pn(t)即可。下面分析幾個排隊系統(tǒng)。二、 單通道等待制排隊問題對于單通道等待制排隊問題主要討論輸入過程服從泊松分布，服務時間服從負指數(shù)分布，單服務臺的情形。分兩種模型來分析： 標準模型所謂標準模型是指顧客源為無限，顧客單個到來，相互獨立，一定時間的到達數(shù)服從泊松分布，到達過程是平穩(wěn)的，排隊為單隊，隊長沒有限制，先到先服務，各顧客的

7、服務時間服從負指數(shù)分布，且相互獨立。同時還假定顧客到達的時間間隔和服務時間是相互對立的。可以證明，顧客相繼到達的時間間隔獨立且為負指數(shù)分布的充要條件是輸入過程服從泊松分布。首先求出排隊系統(tǒng)在任意時刻t的、狀態(tài)為n的概率Pn(t)，不妨假設顧客到達規(guī)律服從參數(shù)為的泊松分布，服務時間服從參數(shù)為的負指數(shù)，由此決定了t，t+t時間間隔內(nèi)：1、 有1個顧客到達的概率為t+o(t)，沒有顧客到達的概率是1-t+o(t)。2、 當有顧客在接受服務時，1個顧客被服務完了的概率是t+o(t)，沒有服務完的概率是1-t+o(t)。3、 多于一個顧客到達或服務完的概率為o(t)，均可忽略。注1：因為單位時間內(nèi)顧客到

8、達數(shù)XP（），所以t時間間隔內(nèi)顧客到達數(shù)Y P（t），因而在t時間間隔內(nèi)有一個顧客到達的概率為：P Y=1 =te-t=t + o(t)，沒有顧客到達的概率為PY=0= e-t=1-t + o(t)。注2：由于服務時間TE（），故在有顧客接受服務時，一個顧客被服務完的概率為PTt =1 - e-t=t + o(t)，沒有被服務完的概率為1 -t + o(t)。在t+t時刻，系統(tǒng)中有n個顧客的狀態(tài)由t時刻的以下狀態(tài)轉(zhuǎn)化而來：t時刻系統(tǒng)中有n個顧客，沒有顧客到達且沒有顧客服務完畢，其概率為：1-t+o(t) 1-t+o(t)= (1-t-t)+o(t)；t時刻系統(tǒng)中有n+1個顧客，沒有顧客到達且有

9、一個顧客服務完畢，其概率為：1-t+o(t)t+o(t)= t+o(t)；t時刻系統(tǒng)中有n-1個顧客，有一個顧客到達且沒有顧客服務完畢，其概率為：t+o(t)1-t+o(t)= t+o(t)；其他狀態(tài)的概率為o(t)。因此，在t+t時刻，系統(tǒng)中有n個顧客的概率Pn(t+t)滿足：Pn(t+t)= Pn(t)(1-t-t)+ Pn+1(t)t + Pn-1(t)t+o(t)Pn(t+t)- Pn(t)/t=Pn-1(t)+Pn+1(t)-(+)Pn(t)+o(t)/t 令t0，得到 n=0時，因為 P0(t+t)= P0(t)(1-t)+ P1(t)(1-t) t+o(t)所以，有 對于穩(wěn)態(tài)情形

10、，與t無關(guān)，其導數(shù)為零。因此，得到差分方程 求解此差分方程 Pn=(/)nP0由概率的性質(zhì)知，將上式代入/1時可得到 P0=1-/ Pn=(1-/)( /)n因為顧客到達規(guī)律服從參數(shù)為的泊松分布，服務時間服從參數(shù)為的負指數(shù)分布，其期望值就分別為，1/。所以表示單位時間內(nèi)平均到達的顧客數(shù)，表示單位時間內(nèi)能服務完的顧客數(shù)。如果令=/，這時就表示相同區(qū)間內(nèi)顧客到達的平均數(shù)與能被服務的平均數(shù)之比，它是刻畫服務效率和服務機構(gòu)利用程度的重要標志，稱為服務強度。上面在1，可以證明排隊長度將是無限增加的，即使=1的情況下，P0(t)也是隨時間而變化的，系統(tǒng)達不到穩(wěn)定狀態(tài)。因此，這里只討論1時情況，從上面的推導

11、知 Pn=(1-) n n=0,1,2,下面計算出系統(tǒng)的運行指標 可以證明，顧客在系統(tǒng)中逗留時間服從參數(shù)為的負指數(shù)分布。因此，有 W系=1/(-) W隊=W系-由以上結(jié)論可以看出，各指標之間有如下關(guān)系： L系=W系； L隊=W隊 W系=W隊+1/, L系=L隊+/在指標的計算過程中，一般只要計算其中一個，其它的指標便可隨之導出。例1 病人候診問題 某單位醫(yī)院的一個科室有一位醫(yī)生值班，經(jīng)長期觀察，每小時平均有4個病人，醫(yī)生每小時平均可診5個病人，病人的到來服從泊松分布，醫(yī)生的診病時間服從負指數(shù)分布。試分析該科室的工作狀況。如果滿足99%以上的病人有座，此科室至少應設多少個座位？如果該單位每天24

12、h上班，病人看病1h因耽誤工作單位要損失30元，這樣單位平均每天損失多少元？如果該科室提高看病速度，每小時平均可診6個病人，單位每天可減少損失多多少？可減少多少個座位？解 由題意知=4，=5，=4/5，=4/5=0.81，從而排隊系統(tǒng)的穩(wěn)態(tài)概率為： Pn=0.20.8n n=0，1，2該科室平均有病人數(shù)為： L系=/（1-）=0.8/（1-0.8）=4（人）該科室內(nèi)排隊候診病人的平均數(shù)為： L隊=L系-/=4-0.8=3.2（人）看一次病平均所需的時間為： W系=L系/=4/4=1h排隊等候看病的平均時間為： W隊=W系-1/=1-1/5=0.8h為滿足99%以上的病人有座，設科室應設m個座位

13、，則m應滿足： P醫(yī)務室病人數(shù)m0.99 所以該科室至少應設20個座位。如果該單位24h上班，則每天平均有病人244=96人，病人看病所花去的總時間為961=96 h。因看病平均每天損失3096=2880元。如果醫(yī)生每小時可診6個病人，=2/3，則 L系=2（人），L隊=4/3（人） W系=0.5h，W隊=1/3h這樣單位每天的損失費為960.530=1440元，因而單位每天平均可減少損失2880-1440=1440元，這時為保證99%以上的病人有座，應設座位數(shù)mln0.01/ln(2/3)-1=11個，比原來減少了9個。下面舉一個與決策有關(guān)的排隊問題。例2 修理工錄用問題 某工廠平均每天有一

14、臺機器發(fā)生故障而需要修理，機器的故障數(shù)服從泊松分布。修理一臺機器平均花費20元。現(xiàn)有技術(shù)水平不同的修理工人A和B，A種修理工平均每天能修理1.2臺機器，每天工資3元；B種修理工平均每天能修理1.5臺機器，每天工資5元，兩種修理工修理機器的時間為負指數(shù)分布。問工廠錄用哪種工人較合算？解 用N 表示每天發(fā)生故障機器的平均數(shù)，包括正在修理和等待修理的機器數(shù)，即等于排隊L系，C1和C2分別表示修理一臺機器的費用和工人的工資，則工廠每天平均損失費用為： R=NC1+NC2若錄用A種修理工，據(jù)題意知=1，A=0.2，A=/A=5/6，L系A(chǔ)=A/(1-A)=5臺，則若錄用A種修理工，工廠每天平均損失費用為

15、： RA=520+3=103元若錄用B種修理工，據(jù)題意知=1，B=1.5，b=2/3，L系B=2臺，則若錄用B種修理工，工廠每天平均損失費用為： RB=220+3=43元比較可知，工廠錄用B種修理工較為合算。如果計入機器停工損失費用，這一選擇更為上算。 系統(tǒng)容量有限的模型因為是單服務臺，設排隊系統(tǒng)的容量為N，即是排隊等待的顧客最多為N-1，在某時刻一顧客到達時，如系統(tǒng)中已有N個顧客，那么這個顧客就被拒絕進入系統(tǒng)。在研究系統(tǒng)中有n個顧客的概率Pn(t)時，和標準模型研究方法相同，當n=N時有 在穩(wěn)態(tài)情形下，并令，得 在條件下解上式得到 這里，不假設1，下面給出系統(tǒng)的各種指標的計算結(jié)果：（1） L

16、系= （2） L隊= L系-(1-P0)=（3） W系= L系/(1-P0)（4） W隊= W系 -應該指出，W系，W隊的導出過程中不是采用平均達到率，而是采用有效到達率效。這主要是由于當系統(tǒng)已滿時，顧客的實際到達率為零，因為正在被服務的顧客的平均數(shù)為1-P0=效/，于是效=（1- P0）。例3 單人理發(fā)館有6個椅子，當6個椅子都坐滿時，后來到的顧客不進店就離開。顧客平均到達率為3人/h，理發(fā)平均需15min，試分析該服務系統(tǒng)。解 由題意知N=7，=3人/h，=4人/h，因此，某顧客一到達就能理發(fā)的概率為： P0=（1-3/4）（1-（3/4）8）=0.2778平均需要等待的顧客數(shù)量為： L系

17、 =2.11人 L隊= L系-(1-P0) =2.11-(1-0.2778)=1.39人 有效到達率為： 效=（1-P0）=4（1-0.2778）=2.89人/h顧客在理發(fā)館平均逗留時間為： W系= L系/效= 多通道等待制排隊問題多通道就是服務臺。對于這種排隊問題只討論標準模型，其特征與單通道標準模型特征完全相同。假定有m個服務臺，每個服務臺相互獨立工作，平均服務個數(shù)相同，則整個服務機構(gòu)的平均服務率為m，顯然只有當/m1時才不會排成無限長的隊列，下面不加證明的給出穩(wěn)定狀態(tài)概率Pn和系統(tǒng)指標。令，則 L系= L隊+m, L隊= W隊= L隊/, W系= W隊+=L系/例4 某火車站售票處有三個窗口，顧客的到達服從泊松分布，平均每分鐘