基于Q圖的M(t)/M/C服務臺配置優(yōu)化

高琦，宮麗芳，武艷華，戴洪帥

山東財經大學 統(tǒng)計學院，濟南 250000

排隊系統(tǒng)的研究大體可分為3個方面：① 性能分析； ② 統(tǒng)計推斷； ③ 資源配置[1]．在排隊模型的研究中，目前學者們通常假設顧客的到達率是不變的，具有平穩(wěn)性．但在很多情況下，如醫(yī)院急診室[2]，顧客的到達具有時變的特征，文獻[3]指出若到達率只是偶爾非平穩(wěn)，利用平穩(wěn)排隊模型分析系統(tǒng)的性能指標，得到的效果并不是最優(yōu)的．文獻[4]指出即使到達率只是適度的不平穩(wěn)，若利用平穩(wěn)排隊模型擬合系統(tǒng)，也會造成性能指標的嚴重低估，因此，逐段近似的方法成為研究非平穩(wěn)排隊模型的一類重要方法．最近幾十年，具有時變到達率的排隊模型的資源配置問題成為學者們的研究熱點之一．文獻[5]研究了非平穩(wěn)到達過程的一般模型，使用平方根公式建立了服務臺配置算法．文獻[6]根據改進的遺傳算法建立了有關立體車庫的排隊模型，該模型可以緩解城市交通的壓力，從而可以提升立體車庫的服務率．文獻[7]為了實現(xiàn)資源利用效率的最大化，提出了以能量最小化為基礎的虛擬機簇分配方法．

近年來，排隊模型的統(tǒng)計控制問題引起了學者們的廣泛關注．文獻[8]通過轉移概率，給出變點監(jiān)測的方法，并為M/G/1和GI/M/1模型系統(tǒng)利用率的監(jiān)測提供了控制限．文獻[9]通過CUSUM表監(jiān)控排隊系統(tǒng)M/M/1隊列的服務性能，并與幾種替代方法進行了對比．考慮到數據的自相關性，文獻[10]提出了一種基于加權似然比檢驗的WLRT控制圖，該控制圖能有效地監(jiān)控排隊系統(tǒng)的性能指標，尤其是對于M/M/1隊列系統(tǒng)利用率的監(jiān)控．

目前在排隊論的研究中，學者們通常把排隊系統(tǒng)的性能監(jiān)控和資源配置優(yōu)化問題分開考慮．另外，現(xiàn)實中很多排隊系統(tǒng)的服務效率主要與服務臺本身有關，如超市收銀臺的服務速率主要與收銀員的熟練程度有關[11]．基于以上考慮，本文將系統(tǒng)性能的監(jiān)控和服務臺配置綜合考慮，基于Q圖研究M(t)/M/C模型服務臺優(yōu)化配置的問題．

1 理論基礎

在M(t)/M/C模型中，到達過程服從Poisson分布，但此時到達率不再恒定而是關于時間t的函數．本文采用M/M/C模型和Q圖技術對動態(tài)M(t)/M/C排隊模型到達率的變化進行檢測，從而優(yōu)化服務臺的配置問題，下面對符號術語進行簡要的介紹．

1.1 M/M/C

本文采用逐段近似的方式優(yōu)化M(t)/M/C模型的服務臺配置問題，通過監(jiān)測變點對排隊系統(tǒng)進行合理的分段，每段近似服從平穩(wěn)的M/M/C模型，并利用該模型研究相關問題．在M/M/C模型中，顧客的到達速率服從參數為λ的泊松分布，服務時間服從參數為μ的指數分布，服務臺的數量為C，等待空間和客源數量為無窮大，服務規(guī)則是先到先服務[12]．其中，ρc=λ/(Cμ)表示系統(tǒng)的服務強度，一般來說只有當ρc<1時才能保證系統(tǒng)的平穩(wěn)運行．W是用來刻畫顧客等待時間的參數，其平均值為E(W|W>0)，概率為P(W≤T|W>0)．進一步有

E(W|W>0)=1/[Cμ(1-ρc)]

(1)

P(W≤T|W>0)=1-exp[-CμT(1-ρc)]，T>0

(2)

1.2 Q圖

傳統(tǒng)控制圖通常只能監(jiān)測服從標準正態(tài)分布的數據，對于服從泊松過程的數據其監(jiān)測性能較差．文獻[13]將Q統(tǒng)計量應用于自適應移動加權平均控制圖中，將參數值進行標準化處理，對常規(guī)控制方法進行了改進．文獻[14]也對Q圖進行了性能的改進，在繪制泊松屬性圖的工作中采用了近似標準化的控制圖，通過泊松分布進行變換，使數據近似標準化，并給出檢測泊松參數的Q圖技術．因此，本文采用改進后的Q圖來檢測排隊系統(tǒng)到達速率的變化．

2 模型

在M(t)/M/C模型中，顧客的到達服從強度為λ(t)的非齊次Poisson分布．為了對隊列的到達速率進行實時監(jiān)測，本文構建了基于Q控制圖的監(jiān)測方法，通過逐段平穩(wěn)的M(t)/M/C模型對其服務臺配置問題進行研究．

2.1 Q統(tǒng)計量

本文首先對到達率λ(ti)進行估計并檢測變點，根據檢測出的變點時刻將排隊隊列分為i(i=1，2，…，m)段，每段的時間記為ti，經過ni次觀測，顧客的到達速率為λ(ti)，到達速率隨著ni的變化記為niλ(ti)．當每段中顧客的到達速率和到達人數均相同時，ni和λ(ti)為常數，即ni=n，λ(ti)=λ0，計算可得每段顧客人數的均值為nλ0，方差為nλ0，利用傳統(tǒng)的3σ控制圖構造上下控制限，則

每段所需觀測的最小樣本數如下所示：

(3)

當λ(ti)隨時間ti變化時，上下控制限的誤差增大，控制圖的靈敏度降低．為了提高控制圖的檢測性能，本文將服從泊松分布的顧客數量的觀測值xi轉化為可以在標準化正態(tài)Q圖上繪制的值，Xi是不同時段所有顧客數量的觀測值xi的和，即Xi=x1+x2+…+xi，Ni是整個系統(tǒng)的總觀測次數，ni是該時段觀測的總次數，即Ni=n1+n2+…+ni．將x1，x2，…，xi轉化為Q統(tǒng)計量，通過下式給出相應的變換：

Qi=φ-1(γi)，其中γi=B(xi；Xi；ni/Ni)

(4)

2.2 服務臺配置優(yōu)化算法

本文利用逐段平穩(wěn)方法研究M(t)/M/C模型的服務臺配置優(yōu)化問題．利用Q圖檢測到達速率λ的變化，將發(fā)生變點的時刻記為t1，在t1處對到達過程進行分段處理，并分別估計出每段的到達速率λ1和λ2的值．若估計得到的λ2和λ1相等，則說明產生了誤報，此時是一個偽檢驗，不需要采取任何措施； 若得到的λ2與λ1相差較大，表明到達速率λ發(fā)生了變化，收到報警信號后，通過到達率λ2與λ1構造新的到達率λ的值，根據平穩(wěn)模型對服務臺的數量進行調整，從而優(yōu)化系統(tǒng)中顧客的擁堵程度和等待時間．

具體算法如下：

① 利用Q圖檢測整個排隊過程中到達率的變點，得到發(fā)生變點的時刻t1和到達率的估計值λ1；

② 基于到達率λ1和給定的延遲概率α，利用M/M/C模型的相關性質，計算服務臺的數量C，即

P(W≤T|W>0)=1-exp[-CμT(1-ρc)]≤α，T>0

(5)

通過上式可知，服務臺數量C滿足

C≤λ/μ-ln(1-α)/(μT)

(6)

③ 在時刻t1之后，基于到達率的估計值λ2，若λ1=λ2，則將檢測下一個變點，若λ1≠λ2，則重復步驟②計算該段服務臺的最優(yōu)配置；

④ 重復上面的步驟，直至周期結束．

3 模擬實驗

本節(jié)設計了隨機模擬實驗證明該模型的理論優(yōu)勢．首先選取i個樣本觀測值，對λ設定不同的參數來模擬Q圖的監(jiān)測過程．本文共選取了48個樣本點，即i=1，2，…，48．根據式(3)計算得到樣本的最小值為4，因此，可將前40個樣本觀測值每個節(jié)點的觀測次數ni=4，后8個樣本觀測值的每個節(jié)點的觀測次數ni=5．到達速率初始值設為λ1=1.7，λ2=3.4，服務速率設為μ1=μ2=1．假定i=39時，到達速率λ發(fā)生變化，即前39個觀測點服從λ1=1.7的泊松分布，后9個觀測點服從λ2=3.4的泊松分布．模擬得到系統(tǒng)中每個節(jié)點的觀測次數ni和人數xi的取值如表1所示．

表1 模擬數據

經計算可得

Xi=x1+x2+…+x48=420Ni=n1+n2+…+n48=200

通過式(4)，計算得到的Q分位數結果如表2所示．

表2 Q分位數

在Q控制圖中描繪出各模擬點的值，從圖1可以看出不同點對應的Q分位數的波動．其中，第39個點對應的分位數超出了控制限[-3，3]的范圍，系統(tǒng)發(fā)出警報，表明該控制圖檢測出了λ的變化．

圖1 模擬數據的Q控制圖

由于式(4)中的二項分布是泊松分布的最小方差無偏估計[14]，因此可以用二項分布的概率pi=ni/Ni來估計到達速率λi，得到λ1=1.756 998，λ2=3.358 514．其中，估計得到的λ1和λ2相差較大，說明沒有發(fā)生誤報．第39個樣本點是發(fā)生變化的點，根據逐段平穩(wěn)的性質對系統(tǒng)進行分段處理，將前38個樣本觀測點規(guī)劃到前一個節(jié)點內，后10個樣本觀測點規(guī)劃到后一個節(jié)點內，得到權重ω1和ω2的值．

因此，根據優(yōu)化后模型的權重計算到達速率λ的值為

λ=ω1λ1+ω2λ2=2.090 647

通過算術平均計算得到的到達率λ′的值為

λ′=(λ1+λ2)/2=2.557 756

基于Green等標準的服務水平優(yōu)化目標[15]，本文設置延遲概率不超過80%，即α=0.8，可以得到等待時間小于T的概率，

P(W≤T|W>0)≤0.8

為了使顧客的等待時間相對較少，令T=10/60=1/6，由此計算出滿足此條件的服務臺數量為C≤11.74，這里服務臺個數取整為12．由式(1)可以得出排隊系統(tǒng)中每一位顧客的平均等待時間為W=0.100 9．同理根據λ′計算得出其服務臺數量和等待時間分別為C′≤12.21，W′=0.105 9，服務臺個數取整為12．為了能夠合理地分配總的服務臺個數，根據系統(tǒng)的逐段平穩(wěn)性質得到第一個節(jié)點和第二個節(jié)點所需要的服務臺數量為

通過模擬，根據C1和C2的取值，可以更加合理地安排不同時段的服務臺數量，第一段安排服務臺數量為11，等待時間W1=0.097 6，第二段安排服務臺數量為13，等待時間W2=0.093 9．

2種模型計算的結果如表3所示．

表3 模擬結果對比表

對比這2種模型所需服務臺的數量和顧客的等待時間，研究發(fā)現(xiàn)優(yōu)化之后的模型更加實用，主要體現(xiàn)在以下2個方面：

① 從顧客角度來說，優(yōu)化之后的模型可以減少每一位顧客的等待時間，進而可以提高顧客的滿意度．

② 從資源利用的角度來說，優(yōu)化后的模型能夠根據顧客到達率的變化合理安排服務臺的個數，可以更為有效地利用服務資源，完成資源的優(yōu)化配置．

4 實證分析

本文選取與現(xiàn)實生活密切相關的高速公路人工收費車道問題進行實證分析．隨著車輛的不斷增加，高速公路收費站處會出現(xiàn)到達車輛不能及時得到服務的狀況，為了解決車輛排隊的擁堵現(xiàn)象，文獻[16-17]分別采用M/M/N和M/G/K模型系統(tǒng)描述收費站的排隊情況．本文以山東省某收費站為例，利用上述模型對車流量進行監(jiān)測，并合理安排人工收費車道的數量．該收費站共有8個服務臺，3條ETC通道，5條人工通道，由于ETC通道全天候開放，故只對人工通道的車流量進行觀測并記錄，其中工作人員實行三班輪換制，即每8 h換班一次．由于每周的車流量數據具有一定的周期性，因此每周只選取一天進行觀測，連續(xù)觀測6周，于每周三6：00-21：00每15 min記錄一次觀測值，發(fā)現(xiàn)同一時段的觀測值相差不大，隨機選取收費站某天的車流量數據進行實證分析．

各時段車流量數據共計60個觀測值，其分布直方圖如圖2所示．為了對各時段車流量數據的分布進行研究，采用K-S檢驗法，由圖2可知P值為0.058，因此該數據近似服從泊松分布．其中前40個觀測值的ni=4，后20個觀測值的ni=5，μ≈50輛/h，T=1/6 h，車流量的Q圖如圖3所示．

利用Q圖對數據進行監(jiān)測，圖3表明當第1、第3和第36個點超出控制限時，系統(tǒng)發(fā)生報警．由于開始時系統(tǒng)的不平穩(wěn)特征[18]，我們排除第1和第3個點的干擾，即無需改變人工收費站的數量．因此以第36個點作為變點進行分段處理，由極大似然估計可得λ1=165輛/h，λ2=233輛/h，經計算可得，C=5，W≈0.018 h，λ=193輛/h，λ′=199輛/h，C1=4，C2=5．該模型的計算結果表明，在變點之前安排4個人工收費車道，在變點之后安排5個人工收費車道，相比較于收費站全天候開放5個人工收費車道，優(yōu)化之后的模型可以及時調整人工收費車道的開放個數，從而能夠降低人工費用等各項支出．

圖2 車流量分布與K-S檢驗圖

圖3 車流量的Q控制圖

5 結論

本文基于Q控制圖對到達速率λ的動態(tài)變化進行監(jiān)控，通過控制圖找到異常點，根據變點時刻分段，得到逐段平穩(wěn)的排隊列，利用M(t)/M/C模型的相關理論知識計算出服務臺的數量和等待時間，合理地安排服務臺數量．此方法的優(yōu)點是將變點檢測和逐段平穩(wěn)相結合，從而優(yōu)化了動態(tài)排隊模型的服務臺配置問題．本文利用收費站某天的車流量數據進行了實證分析，結果表明，Q控制圖能夠對動態(tài)的車流量數據進行實時監(jiān)測，檢測出車流量變化幅度較大的點．根據變點計算出各段的人工收費車道數量，進而實時調整服務資源，緩解收費站的擁堵情況，降低收費站人工成本等各類的支出，具有重要的現(xiàn)實意義．