基于汽車檢測設備共享的混合制動態排隊論系統研究*

趙培瑤， 向鳳紅， 毛劍琳， 郭 寧， 張傳龍

基于汽車檢測設備共享的混合制動態排隊論系統研究*

趙培瑤， 向鳳紅， 毛劍琳， 郭 寧， 張傳龍

(昆明理工大學 信息工程與自動化學院，云南 昆明 650500)

如何以有限的設備提供更好的檢測服務成為汽車檢測行業的首要問題。針對目前多數研究者僅僅做到對客戶分類，并未考慮顧客流量隨時間變化而服務臺配置不變引起的配置不合理問題，提出了一種基于顧客流量變化的服務臺混合制動態配置算法(MDSWCA)。仿真結果表明：該算法能有效增加系統的總服務時間和有效吞吐量，能很好地解決顧客流量隨時間變化的汽車檢測問題，明顯降低服務成本。

汽車檢測； 排隊論系統； 有效吞吐量； 混合制動態配置算法

0 引 言

排隊論是用來研究在不同顧客流輸入、各類服務時間分布、不同服務臺配置及不同排隊規則的情況下，排隊系統、排隊算法的工作性能[1]。排隊問題在實際生活中是很普遍的，且排隊的種類非常多，故排隊論中采取一種特定的標記方法標記所研究的排隊特征[2,3]：相鄰顧客到達時間間隔的分布、顧客服務時間分布、服務臺數目、系統排隊空間和顧客源數目。時間分布可為馬爾科夫型(M)、定長型(D)、r階愛爾蘭型(Er)、k階超指數(Hk)、一般分布(G)。服務臺數目、顧客源數目及系統排隊空間都以數字表明，合適的排隊論模型的建立非常重要。汽車數量在現代以驚人的速度在發展，導致汽車檢測行業面臨著如何以有限的設備提供更好的檢測服務的問題，這一類可以歸為排隊論問題。文獻[4]中針對類似問題提出了預留一部分服務臺給特殊顧客的排隊規則，但該排隊規則并未考慮到顧客流變化與服務臺配置的關系；文獻[5]中運用單通道、等待制、先到先服務的排隊規則判斷快速充電汽車快速充電站(服務臺)的需要增加的最優數目；文獻[6] 從先到先服務、后到先服務和有優先權的服務三種排隊規則研究對排隊論的訂單處理效率的影響。上述文獻都存在一些服務臺配置不合理的問題，當顧客流變化時，服務臺不能夠做出相應的改變。

本文針對目前多數研究者僅僅做到對客戶分類，并為考慮顧客流量隨時間變化而服務臺配置不變引起的配置不合理問題，提出了一種基于顧客流量變化的服務臺混合制動態配置算法(MDSWCA)。仿真結果表明，算法能有效解決顧客流量隨時間變化的汽車檢測問題。

1 汽車檢測問題描述與排隊模型

1.1 泊松分布與指數分布

1)泊松分布：排隊論中常用到的離散型的概率分布，設隨機變量X只能取非負整數，且其概率分布滿足

(1)

式中 e為常數，λ為單位時間內隨機事件的平均發生率。則隨機變量X的分布可被認為是泊松分布，并記為P(λ)，其中λ既是方差，也是均值。

泊松分布[7，8]適合描述單位時間內隨機事件發生的次數。另外泊松過程的分解和合成性質也給系統分析提供了很大的便利。

2)指數分布：假如一個連續型的隨機變量X的分布密度函數為

(2)

由上可知X服從參數是λ(常數)的負指數分布(exponential distribution)。該變量的分布函數為

(3)

式中e為常數，λ為單位時間內隨機事件的平均發生率。則隨機變量X的分布可被認為是指數分布，且方差為E(X)。

指數函數的一個重要特性是無記憶性,這種特性為分析帶來了非常大的便利。常用來表示元器件壽命，而服務時間也可被認為類似元器件壽命的變量。

1.2 問題描述

雖然汽車檢測問題某一時間段內的到達率與服務率是確定的，但汽車到達檢測站的過程與其所用檢測時間都是隨機的。而檢測設備的數量(服務臺數)是已知的，故檢測站的汽車檢測是一個典型的隨機服務系統(排隊論系統)[9，10]。其排隊規則為部分顧客有優先級，即顧客分為A類和B類，B類顧客具有優先級且部分服務臺只為B類顧客服務。

1.3 排隊模型

本文建立并模擬的基本模型是多服務臺損失制，先到先服務排隊模型M/M/m1+m2/∞。解釋如下：

1)第一個M意為顧客到達的時間間隔滿足泊松分布，其參數設為λ，并對顧客進行分類，普通顧客A到達參數設為λ1，特殊顧客B到達參數設為λ2；

2)第二個M意為對顧客的服務時間滿足指數分布，其參數設為μ，普通顧客服務參數設為μ1，特殊顧客服務參數設為μ2；

3)m意為系統中有m個相互獨立的服務窗口；并對其進行分類，給特殊顧客預留的窗口數目為m2；

4)∞意為顧客源是無限的；

5)損失制意為顧客到達服務站時沒有空閑窗口便離去不等待，排隊長度為0；

6)服務順序選擇為優先級(B類顧客具有優先級，且有部分服務臺只允許B類顧客接受服務)。

2 MDSWCA改進思想

本文應用無線傳感器節點捕獲顧客流量[9]，經檢測，所用的排隊系統中顧客流A的到達比較稀疏，而顧客流B的到達比較頻繁，因此,可以設定顧客流A的排隊規則為排隊隊長為1的等待制，顧客流B的排隊規則可以判定為損失制。這樣的設定更加符合汽車檢測排隊系統的真實性，因為排隊長度大于1的話，顧客是不愿意等的，排隊長度為1的時候顧客還是有等待直到排到自己被服務的耐心；而對于顧客流B來講，顧客到達非常頻繁，因此對于顧客流B的服務和排隊規則設定為損失制比較合理。綜合考慮這幾方面的因素，整個系統的服務規則為混合制排隊。

具體設定可以簡單表示為系統的排隊規則：對于顧客種類A, 顧客到達時刻允許每個窗口排隊1人；對于顧客種類B，顧客到達時刻允許每個窗口排隊0人。

3 仿真與結果分析

3.1 數據參數

客戶到達率的隨機數據必須滿足λa≤λb，因為客戶到達率的數據參考是根據文獻[7]，在6～21之間產生(6≤λa+λb≤21)，這個數據區間是文獻[7]所采集的真實的數據區間。為了更加真實地模擬現實中的到達情況和服務情況，應用信息采集系統[12]，將原來的15組數據增加到了30組，這樣一來就更加與現實情況相符合。本文在仿真軟件Matlab環境下，產生的30組顧客流A和顧客流B的泊松分布到達參數數據為λa,λb如表1。

3.2 仿真參數

1)總服務時間Τ：在仿真時間內，系統為顧客提供的總服務時間即系統不空閑時間。故系統空閑時對總服務時間無貢獻

(4)

2)有效吞吐量Υ：仿真時間內，所有服務臺所服務的顧客數目，到達服務臺但并沒有接受服務的顧客對有效吞吐量無貢獻。

3)成本C：在本文中，指系統所需要的人工成本。本文設定每臺機器需要2位工作人員，且每位工作人員的薪水為300/24h,系統使用的服務臺數n為

C=n×(300×2)

(5)

表1 顧客流輸入

組數λaλbλ組數λaλbλ組數λaλbλ11．88106．88408．7650111．57006．09807．6680211．76405．80107．565021．07106．61507．6860122．22309．767011．9900227．62307．778015．401032．693011．257013．9500130．18908．83909．0280234．446014．627019．073040．49808．74809．2460143．420013．772017．1920242．593013．006015．599054．232015．130019．3620156．76407．371014．1350255．88507．063012．948061．22905．18306．4120162．77607．931010．7070266．806010．176016．982073．58207．836011．4180175．870011．861017．7310272．318010．024012．342084．457011．571016．0280184．020013．463017．4830281．390014．665016．055093．699013．875017．5740195．09106．438011．5290299．08709．726018．8130106．386012．867019．2530201．532018．812020．3440300．544013．968014．5120

3.3 仿真分析

本文中選擇了Matlab作為仿真軟件，并對原始損失制排隊論模型算法、優先級排隊模型算法和本文中引入的混合制排隊模型算法進行排隊系統性能比較，在文中選擇：總服務時間(total service time)、有效服務顧客吞吐量(effective throughput)、系統成本分析(system cost)這三個算法性能評估指標來進行評價。

圖1為隨機產生的30個時間段內的30組數據進行仿真所得出的總服務時間高低比較，計算可得:本文所提出的引入混合制排隊模型算法比原始損失制排隊論模型算法高出519 h，比優先級算法高出230 h。這是由于引入混合制排隊模型之后，在排隊系統中的顧客流A在接受服務的時候，允許有1人在隊伍中等待，這就最大程度地減少了服務臺空閑情況，從而避免了服務臺在沒有顧客到達的時候產生的時間上的浪費。

圖2為隨機產生的30個時間段的30組顧客流A和顧客流B仿真結果可知：本文的引入混合制排隊模型比原始損失制排隊論模型算法的總的有效吞吐量增大了487人，且比優先級算法增多了352人。

圖2 有效顧客吞吐分析

圖3為三種算法所用的排隊系統成本比較。通過在排隊系統中減少使用的服務臺總數，起到了排隊系統的成本控制的作用。

圖3 系統成本的對比

4 結 論

仿真實驗表明：通過引入混合制排隊模型，整個排隊系統的性能有了較大的提升，在進一步降低成本使用的情況下，有效提高了總的服務時間和接受服務的總的顧客數目。

[1] Luo Chuanyi,Tang Yinghui,Lo Wei,et al.The recursive solution of queue length for geo/G/1 queue with N-policy[J].Journal of Systems Science and Complexity,2012(2):293-302.

[2] 何選森.隨機過程與排隊論[M].長沙：湖南大學出版社,2010.

[3] 任敏麗.排隊論在銀行服務系統中的若干應用研究[D].哈爾濱：哈爾濱工業大學,2010.

[4] 李仕鵬.基于排隊論的汽車共享優化設計[D].杭州:杭州電子科技大學,2012.

[5] 劉文霞,仇國兵.電動汽車快速充電站需求分析與設備優化方法[J].天津大學學報，2012,45(12)：1111-1115.

[6] 倪志偉.基于排隊論的訂單處理系統建模與仿真[D].北京:北京交通大學，2009.

[7] 李如琦，蘇浩益.基于排隊論的電動汽車充電設施優化配置[J].電力系統自動化,2011,35(14):58-61.

[8] 梅振宇,陳 峻,王 煒.城市路內停車設置規模非線性優化模型及其算法[J].交通運輸工程學報,2007,7(2):89-93.

[9] Guo P F,Paul Z.The effects of the availability of waiting-time information on a banking queue[J]．European Journal of Operational Research，2009，198(5):199-209.

[10] 蔡文婧,葛連升.基于排隊論的銀行業務窗口設置優化[J].山東大學學報：工學版,2013,43(3):24-29.

[11] 沙 超,王汝傳,張 悅.一種基于無線傳感器網絡的智能交通系統[J].傳感器與微系統,2012,31(10):81-83，87.

[12] 趙 敏,常 杰,孫棣華.基于ZigBee和ARM的分布式RFID信息采集系統的設計[J].傳感器與微系統,2011,30(9):105-108.

Study on mixing dynamic system based on car diagnosis equipment sharing*

ZHAO Pei-yao, XIANG Feng-hong, MAO Jian-lin, GUO Ning, ZHANG Chuan-long

(Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500,China)

How to provide better testing services using limited equipment becomes the primary issue of car diagnosis industry.In view of the present situation that most researchers just do classification to the customer while neglecting unreasonable configuration issue caused by ignoring the problem that serving window configuration remain unchanged while the customer flow is changing with time go on.Propose mixing dynamic serving window configuration algorithm(MDSWCA)based on varying customer flow.Simulation result shows that this algorithm can increase total serving time and effective throughput, it can solve problem of car diagnosis while customer flow change with time varing,besides the system cost is decreased as well.

car diagnosis; queuing theory; effective throughput; mixing dynamic service window configuration algorithm(MDSWCA)

2016—03—22

國家自然科學基金資助項目(61163051)

TP 273

A

1000—9787(2017)02—0025—03

趙培瑤(1990-)，女，碩士研究生，研究方向為智能控制算法。