排隊論

1.排隊論簡介

研究系統(tǒng)隨機聚散現(xiàn)象和隨機服務系統(tǒng)工作過程的數(shù)學理論和方法，又稱隨機服務系統(tǒng)理論，為運籌學的一個分支。

日常生活中存在大量有形和無形的排隊或擁擠現(xiàn)象，如旅客購票排隊，市內(nèi)電話占線等現(xiàn)象。排隊論的基本思想是1910年丹麥電話工程師A.K.埃爾朗在解決自動電話設計問題時開始形成的，當時稱為話務理論。他在熱力學統(tǒng)計平衡理論的啟發(fā)下，成功地建立了電話統(tǒng)計平衡模型，并由此得到一組遞推狀態(tài)方程，從而導出著名的埃爾朗電話損失率公式。自20世紀初以來，電話系統(tǒng)的設計一直在應用這個公式。30年代蘇聯(lián)數(shù)學家А.Я.欣欽把處于統(tǒng)計平衡的電話呼叫流稱為最簡單流。瑞典數(shù)學家巴爾姆又引入有限后效流等概念和定義。他們用數(shù)學方法深入地分析了電話呼叫的本征特性，促進了排隊論的研究。50年代初，美國數(shù)學家關于生滅過程的研究、英國數(shù)學家D.G.肯德爾提出嵌入馬爾可夫鏈理論，以及對排隊隊型的分類方法，為排隊論奠定了理論基礎。在這以后，L.塔卡奇等人又將組合方法引進排隊論，使它更能適應各種類型的排隊問題。70年代以來，人們開始研究排隊網(wǎng)絡和復雜排隊問題的漸近解等，成為研究現(xiàn)代排隊論的新趨勢。

2.排隊系統(tǒng)模型的基本組成部分

排隊系統(tǒng)又稱服務系統(tǒng)。服務系統(tǒng)由服務機構和服務對象（顧客）構成。服務對象到來的時刻和對他服務的時間（即占用服務系統(tǒng)的時間）都是隨機的。圖1為一最簡單的排隊系統(tǒng)模型。排隊系統(tǒng)包括三個組成部分：輸入過程、排隊規(guī)則和服務機構。

排隊論

輸入過程

　　輸入過程考察的是顧客到達服務系統(tǒng)的規(guī)律。它可以用一定時間內(nèi)顧客到達數(shù)或前后兩個顧客相繼到達的間隔時間來描述，一般分為確定型和隨機型兩種。例如，在生產(chǎn)線上加工的零件按規(guī)定的間隔時間依次到達加工地點，定期運行的班車、班機等都屬于確定型輸入。隨機型的輸入是指在時間t內(nèi)顧客到達數(shù) n（t）服從一定的隨機分布。如服從泊松分布,則在時間t內(nèi)到達n個顧客的概率為

　　或相繼到達的顧客的間隔時間T 服從負指數(shù)分布，即

　　式中λ為單位時間顧客期望到達數(shù)，稱為平均到達率；1/λ為平均間隔時間。在排隊論中，討論的輸入過程主要是隨機型的。

排隊規(guī)則

　　排隊規(guī)則分為等待制、損失制和混合制三種。當顧客到達時，所有服務機構都被占用，則顧客排隊等候，即為等待制。在等待制中，為顧客進行服務的次序可以是先到先服務，或后到先服務，或是隨機服務和有優(yōu)先權服務（如醫(yī)院接待急救病人）。如果顧客來到后看到服務機構沒有空閑立即離去，則為損失制。有些系統(tǒng)因留給顧客排隊等待的空間有限，因此超過所能容納人數(shù)的顧客必須離開系統(tǒng)，這種排隊規(guī)則就是混合制。

服務機構

　　可以是一個或多個服務臺。多個服務臺可以是平行排列的，也可以是串連排列的。服務時間一般也分成確定型和隨機型兩種。例如，自動沖洗汽車的裝置對每輛汽車沖洗（服務）時間是相同的，因而是確定型的。而隨機型服務時間v 則服從一定的隨機分布。如果服從負指數(shù)分布，則其分布函數(shù)是

　　式中μ為平均服務率，1/μ為平均服務時間。

3.排隊系統(tǒng)的分類

如果按照排隊系統(tǒng)三個組成部分的特征的各種可能情形來分類，則排隊系統(tǒng)可分成無窮多種類型。因此只能按主要特征進行分類。一般是以相繼顧客到達系統(tǒng)的間隔時間分布、服務時間的分布和服務臺數(shù)目為分類標志?，F(xiàn)代常用的分類方法是英國數(shù)學家D.G.肯德爾提出的分類方法，即用肯德爾記號 X/Y/Z進行分類。

X處填寫相繼到達間隔時間的分布；

Y處填寫服務時間分布;

Z處填寫并列的服務臺數(shù)目。

各種分布符號有：M-負指數(shù)分布;D-確定型; Ek-k階埃爾朗分布；GI-一般相互獨立分布；G-一般隨機分布等。這里k階埃爾朗分布是指為相互獨立且服從相同指數(shù)分布的隨機變量時，服從自由度為 2k的χ2分布。例如,M/M/1表示顧客相繼到達的間隔時間為負指數(shù)分布、服務時間為負指數(shù)分布和單個服務臺的模型。D/M/C表示顧客按確定的間隔時間到達、服務時間為負指數(shù)分布和C個服務臺的模型。至于其他一些特征,如顧客為無限源或有限源等，可在基本分類的基礎上另加說明。

4.排隊系統(tǒng)問題的求解

　研究排隊系統(tǒng)問題的主要目的是研究其運行效率,考核服務質(zhì)量,以便據(jù)此提出改進措施。通常評價排隊系統(tǒng)優(yōu)劣有 6項數(shù)量指標。

①系統(tǒng)負荷水平ρ ：它是衡量服務臺在承擔服務和滿足需要方面能力的尺度；

②系統(tǒng)空閑概率P0：系統(tǒng)處于沒有顧客來到要求服務的概率；

③隊長：系統(tǒng)中排隊等待服務和正在服務的顧客總數(shù)，其平均值記為LS；

④隊列長：系統(tǒng)中排隊等待服務的顧客數(shù)，其平均值記為Lg；

⑤逗留時間：一個顧客在系統(tǒng)中停留時間，包括等待時間和服務時間，其平均值記為WS；

⑥等待時間：一個顧客在系統(tǒng)中排隊等待時間,其平均值記為Wg。M/M/1排隊系統(tǒng)是一種最簡單的排隊系統(tǒng)。系統(tǒng)的各項指標可由圖2中狀態(tài)轉移速度圖推算出來（表1）。其他類型的排隊系統(tǒng)的各種指標計算公式則復雜得多，可專門列出計算公式圖表備查?，F(xiàn)已開始應用計算機仿真來求解排隊系統(tǒng)問題。

排隊論

5.排隊論的應用

排隊論已廣泛應用于交通系統(tǒng)、港口泊位設計、機器維修、庫存控制和其他服務系統(tǒng)。表2中列出排隊論的應用。

排隊論

6.排隊論的案例分析

排隊論案例一：超市收銀臺^[1]

　　一、超市收銀臺

　　隨著市場經(jīng)濟的不斷發(fā)展，城鎮(zhèn)里的超市越來越多。在激烈的市場競爭中，如何提高經(jīng)營效益、吸引更多的顧客是超市經(jīng)營商最關心的問題。收銀臺是超市的服務窗口，不僅能夠反映超市的形象更與超市的服務質(zhì)量和經(jīng)營效率密切相關。收銀員的形象、服務態(tài)度、職業(yè)技能等固然重要，而收銀臺的管理與優(yōu)化也是不容忽視。顧客選擇超市的標準，不僅是價廉物美的商品，也有服務質(zhì)量。收銀臺前排隊成龍的超市顯然不是人們希望的購物環(huán)境，多數(shù)人寧愿放棄或者稍微走遠一點去購物也不愿意在擁擠中排隊等待。尤其是一些成功人士，他們寧愿多花點錢也不愿意排隊，對于他們來說時間就是金錢。在商品的質(zhì)量和價格基本相同的條件下，服務質(zhì)量才是競爭的焦點。前者可以通過采購環(huán)節(jié)加以控制，而后者只有通過收銀臺的增減與管理加以調(diào)節(jié)。就超市經(jīng)營者而言，增加收銀臺就意味著增加投資，有時還有可能發(fā)生資源空閑浪費的現(xiàn)象；而收銀臺太少，排隊現(xiàn)象就會嚴重，影響服務質(zhì)量，造成客源流失。

　　二、超市排隊系統(tǒng)的組成與特征

　　一般的排隊服務系統(tǒng)(如圖）有三個基本的組成部分：輸入過程、排隊規(guī)則和服務機構。輸入過程是指顧客到達排隊系統(tǒng)；排隊規(guī)則是指顧客到達后按什么樣的規(guī)則排隊等待服務；服務機構是指為顧客提供服務的機構。本文所研究的排隊系統(tǒng)是指顧客在超市里挑選好商品后，在收銀臺前排隊等待付款的排隊系統(tǒng)。收銀臺是服務臺，顧客付款被認為是接受服務。輸入過程是指顧客挑選好商品后來到收銀臺前；排隊規(guī)則是指顧客按單隊單服務臺、多隊多服務臺或單隊多服務臺的方式排隊；服務機構是服務臺。

　　排隊服務系統(tǒng).jpg

　　一般認為在超市的排隊系統(tǒng)中，輸入過程服從泊松分布，服務時間服從指數(shù)分布。用λ表示單位時間內(nèi)平均到達的顧客數(shù)，用μ表示各個服務臺的平均服務速率(服務員的服務能力）。用Ρ表示平均每單位時間中系統(tǒng)可以為顧客服務的比例， $rho=frac{lambda}{mu}$ 即服務強度。W_s表示顧客在系統(tǒng)中的平均逗留時間（包括排隊等待時間和接受服務的時間），W_q表示顧客排隊等待的平均時間，可通過如下公式計算：

　　在單隊單服務臺的情況下:

　　　　 $W_s=frac{1}{mu-lambda}$ , $W_q=frac{rho}{mu-lambda}$

　　多隊多服務臺可看作是多個單隊單服務臺。在單隊k個服務臺的情況下:

　　 $W_s=frac{(krho)^krho}{k!(1-rho)^2lambda}P_0+frac{1}{mu}$ ， $W_q=frac{(krho)^krho}{k!(1-rho)^2lambda}P_0$

　　 $P_0=begin{bmatrix} sum^{k-1}_{n=0}frac{1}{n!}(frac{lambda}{mu})^n+frac{1}{k!(1-rho)}(frac{lambda}{mu})^kend{bmatrix}^{-1}$

　　三、超市收銀臺的優(yōu)化設計

　　作為顧客來說，超市收銀臺越多越好越方便，而就超市經(jīng)營者來說，增加收銀臺就要增加投資。所以應該合理的規(guī)劃收銀臺的數(shù)量，使得既不會因為收銀臺的數(shù)量過多而造成資源閑置浪費，也不會因為收銀臺的數(shù)量過少而造成嚴重的排隊現(xiàn)象。因此可對超市收銀臺進行管理和優(yōu)化設計。

　　1.對超市布局進行合理規(guī)劃，為顧客營造出溫馨，簡便的購物環(huán)境。讓顧客在盡量短的時間內(nèi)買到自己想買的商品，提高單位時間內(nèi)進出超市的客流量，這樣既節(jié)省了顧客的時間，也使超市增加了顧客的流量，從而使超市的經(jīng)營效率得到了提高。對于大型的超市在恰當?shù)奈恢迷黾訉з弳T是一種很好的方法。對于第一次來消費的顧客，導購員的指導就會大量的減少他們的漫無目的的逗留時間。收銀臺前的管理也是非常重要的，盡量讓等待的顧客按順序排隊，避免過分的擁擠和混亂。

　　2.加強培訓，提高收銀員的基本素質(zhì)。收銀臺是超市中顧客接觸最多的地方?？梢哉f是超市的窗口，收銀員的素質(zhì)和服務質(zhì)量直接影響超市的形象。如果超市位于社區(qū)內(nèi)，顧客都是些老客戶，他們知道哪個收銀員的收銀速度比較快，服務態(tài)度好，可能就會在她的通道內(nèi)排隊的顧客比較多，從而導致其他的收銀員暫時的資源閑置。這樣也不利于超市經(jīng)營者的管理。

　　所以招收收銀員時要適當考慮收銀員的資歷和形象，要對收銀員的愛崗敬業(yè)精神和職業(yè)技能加強培訓。要定期對收銀員進行考核或開展職業(yè)技能方面的競賽。要及時掌握收銀員的工作狀態(tài)、業(yè)務水平及相關資料，這不僅是對員工進行科學管理的需要，這些資料可以反映收銀員的工作強度，對于管理與優(yōu)化都是非常重要的數(shù)據(jù)資料。

　　3.盡量采用單隊多服務臺的排隊規(guī)則，提高工作效率。

　　在超市排隊系統(tǒng)中，輸入過程服從泊松分布，從理論來說，采用單隊多服務臺的排隊規(guī)則比采用多隊多服務臺的工作效率高。以有三個收銀臺的超市為例，設顧客的平均到達率為λ = 0.9(人)，平均服務率為μ = 0.4(人)，如果按多隊多服務臺的排隊規(guī)則進行排隊，則約有75%的顧客需要排隊等待付款，平均等待時間約為7分鐘。而按單隊多服務臺的排隊規(guī)則進行排隊，則只有約57%的顧客需要排隊，平均等待時間不到2分鐘。

　　4.誠信經(jīng)營。在現(xiàn)在的市場經(jīng)濟條件下，誰占有了消費者的購買信心，誰就占有了市場。所以，超市經(jīng)營者一定要誠信經(jīng)營，讓消費者在超市消費時，沒有后顧之憂。使消費者相信他選中的這個超市是可以長期合作的。這樣消費者和經(jīng)營者就達到了和諧。

排隊論案例二：汽車售后服務^[2]

　　當今排隊論研究的內(nèi)容包括3個方面：系統(tǒng)的性態(tài)、系統(tǒng)的優(yōu)化和統(tǒng)計推斷，根據(jù)資料的合理建立模型，其目的是正確設計和有效運行各個服務系統(tǒng)，使之發(fā)揮最佳效益。利用排隊論的知識來解決汽車售后服務中的排隊論問題。

　　1.排隊模型的建立

　　假設客戶平均到達率為λ，單個服務臺的平均服務率（表示單位時間被服務完的顧客數(shù)）為μ，整個服務機構的平均服務率為C^μ，系統(tǒng)的服務強度 $rho=frac{lambda}{C^mu}<1$ 時才不會排成無限的隊列，P_n(c)為C個服務臺任意時刻系統(tǒng)中有n個顧客的概率；當?shù)竭_率為lambda，服務率為C^μ的過程達到穩(wěn)態(tài)時，可得

　　 $p_0(c)=left[ sum^{c-1}_{k=0}frac{1}{k!}(frac{lambda}{mu})^k+frac{1}{c!}frac{1}{(1-rho)}(frac{lambda}{mu})^kright]^{-1}$ 　　(1)

　　 $p_n(c)=begin{cases} frac{1}{n}(frac{lambda}{mu})P_0(C) & n=1,2,cdots,C frac{1}{C!C^{n-c}}(frac{lambda}{mu})P_0(C) & n=C+1end{cases}$ 　　(2)

　　當系統(tǒng)達到平衡狀態(tài)時,每位顧客在系統(tǒng)中的等待時間w的均值為:

　　 $E(w)=frac{P_n(C)}{cmu(1-rho)^2}=frac{nmu}{n!(nmu-lambda)^2}(frac{lambda}{mu})^n p_0(c)$ 　　(3)

　　排隊逗留的人數(shù)：

　　 $L_s=L_q+crho=frac{1}{c!}frac{(crho)^crho}{(1-rho)^2}p_0+frac{lambda}{mu}$ 　　(4)

　　排隊系統(tǒng)的最優(yōu)化

　　在排隊系統(tǒng)中，顧客希望服務臺越多、服務效率越高、逗留時間越短越好，使自己的損失達到最小，為此4S店就要增加服務人員數(shù)，而4S店也不可能無限投入，因此就需要優(yōu)化設計，目的就是使顧客損失費用和公司運營成本最低。假設服務臺的個數(shù)為C，每個服務臺單位時間所需的成本費為C_s，每個顧客在系統(tǒng)中逗留單位時間的費用為C_w，總成本為Z(c)，則目標函數(shù)：

　　minZ(c) = C_sC + C_wL_s

　　其中L_s為逗留的人數(shù)公式（4），C只能取整數(shù)。

　　設C^*是使目標函數(shù)C取最小值的點C^*滿足。

　　 $Z(C^*-1)le Z(C^*)=CsC^*+C_w L_s(C^*)le Z(C^*+1)$ 　　L_s = L_s(C)

　　化簡得： $L_s(C^*)-L_s(C^*+1)le frac{C_s}{C_w}le L_s(C^*-1)-L_s(C^*)$ 　　(5)

　　通過計算機模擬依次算出L_S(1),L_S(2),L_S(3)…相鄰兩項之差，看常數(shù)落在哪兩者之間，從而確定使顧客損失費用和公司服務成本之和達到最優(yōu)化服務臺個數(shù)C的最優(yōu)解C^*。

　　模型的求解

　　由已知易得：

$λ;$ （輛/h）	$μ;$ （輛/h）	$C s$ （元）	$C w$ （元）
15.05	3.7	30.512	143.189

$L S (1) − L S (2)$	-2.7113	$L S (4) − L S (5)$	-2.6241
$L S (2) − L S (3)$	-1.5813	$L S (5) − L S (6)$	0.0203
$L S (3) − L S (4)$	1.5020	$L S (6) − L S (7)$	0.0008

由上表知只有維修機組個數(shù)C^*= 4時滿足公式（5），從而使得每一位客戶來店等待維修時間最短，且公司成本最低的最優(yōu)維修機組個數(shù)為4。

　　模型的分析當顧客平均到達率上升引起服務強度增加致使平均隊長L太大，甚至由于服務強度ρ > 1使隊長趨向無限時，在平均服務率不變的情況下就只能增加服務臺。下面考慮有兩個服務臺且平均服務率相等的情況。

　　兩個服務臺的排隊有兩種形式分別由下面兩圖表示:左圖一個隊是一個M/M/2模型;右圖兩個隊，且入隊后不能換隊,是兩個M/M/1模型。

　　 M模型.jpg

　　可以知道，兩個服務臺的兩種服務形式平均隊長L,等待時間W之比為： $frac{2L_1}{L_2}=frac{W_1}{W_2}=1+rho_2(rho_2=frac{lambda}{2mu}<1)$

　　就人們最關心的等待時間而言有 $1<frac{W_1}{W_2}<2$ ,而當 $rho_2=frac{rho}{2}(rho=frac{lambda}{mu})$ 較大時，M/M/2模型的形式比2個M/M/1模型節(jié)省較多的等待時間。

　　同理可證：在有多個并列服務臺的排隊系統(tǒng)中,排成單隊比排成并列多隊的方案具有明顯的優(yōu)越性.對于設置多個服務臺的隨機過程，應該讓顧客排成一個隊。

　　接待、派工程序的設計

　　由上知，在設置4個并列維修機組的排隊系統(tǒng)中，排成單隊比排成并列4隊的方案具有明顯的優(yōu)越性.具體的接待、派工程序如下：

　　人員分配幾何示意圖.jpg

　　2.服務月工作安排

　　在最優(yōu)條件下，各維修機組基本上一直處于繁忙狀態(tài)，但該4S店4月份與9月份來店保養(yǎng)客戶比平均每天來店保養(yǎng)客戶多31%及43%，因此為了在不增加員工數(shù)量且遵守國家法定工作時間的條件下完成服務月活動，只能提高各維修機組的工作效率。

關系圖.jpg

　　由已知易得：4月份每小時客戶平均到達率λ = 18.77(輛/h)，設每個維修機組提高效率后每小時修理的汽車數(shù)量為μ,由MATLAB計算得當μ = 4.6時即可滿足條件,此時每個維修機組提高的效率為P=21.8%.同理9月份當μ = 5時即可滿足條件，此時每個維修機組提高的效率P=32.4%。

　　因此，該4S店的接待、派工流程為圖3，需提高的工作效率如下：

　　各維修機組在4月份、9月份需提高的工作效率

時間/月	$λ$ （輛/時）	$μ$ （輛/時）	P（%）
4	18.77	4.6	21.8
9	20.21	5	32.4

　　3.結論

　　應用排隊論一方面可以有效地解決售后服務系統(tǒng)中人員和設備的配置問題，為公司提供可靠的決策依據(jù)；另一方面通過系統(tǒng)優(yōu)化，找出客戶和公司兩者之間的平衡點，既減少排隊等待時間，又不浪費公司人力物力，從而使公司和客戶之間達到雙贏。排隊是一種司空見慣的現(xiàn)象，因此排隊論可以用來解決許多現(xiàn)實問題。

評論 | 0條評論

評論

經(jīng)理人分享

排隊論

目錄

1.排隊論簡介

2.排隊系統(tǒng)模型的基本組成部分