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

基于汽車(chē)檢測(cè)設(shè)備共享的混合制動(dòng)態(tài)排隊(duì)論系統(tǒng)研究*

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

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

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

汽車(chē)檢測(cè)； 排隊(duì)論系統(tǒng)； 有效吞吐量； 混合制動(dòng)態(tài)配置算法

0 引 言

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

本文針對(duì)目前多數(shù)研究者僅僅做到對(duì)客戶(hù)分類(lèi)，并為考慮顧客流量隨時(shí)間變化而服務(wù)臺(tái)配置不變引起的配置不合理問(wèn)題，提出了一種基于顧客流量變化的服務(wù)臺(tái)混合制動(dòng)態(tài)配置算法(MDSWCA)。仿真結(jié)果表明，算法能有效解決顧客流量隨時(shí)間變化的汽車(chē)檢測(cè)問(wèn)題。

1 汽車(chē)檢測(cè)問(wèn)題描述與排隊(duì)模型

1.1 泊松分布與指數(shù)分布

1)泊松分布：排隊(duì)論中常用到的離散型的概率分布，設(shè)隨機(jī)變量X只能取非負(fù)整數(shù)，且其概率分布滿(mǎn)足

(1)

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

泊松分布[7，8]適合描述單位時(shí)間內(nèi)隨機(jī)事件發(fā)生的次數(shù)。另外泊松過(guò)程的分解和合成性質(zhì)也給系統(tǒng)分析提供了很大的便利。

2)指數(shù)分布：假如一個(gè)連續(xù)型的隨機(jī)變量X的分布密度函數(shù)為

(2)

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

(3)

式中e為常數(shù)，λ為單位時(shí)間內(nèi)隨機(jī)事件的平均發(fā)生率。則隨機(jī)變量X的分布可被認(rèn)為是指數(shù)分布，且方差為E(X)。

指數(shù)函數(shù)的一個(gè)重要特性是無(wú)記憶性,這種特性為分析帶來(lái)了非常大的便利。常用來(lái)表示元器件壽命，而服務(wù)時(shí)間也可被認(rèn)為類(lèi)似元器件壽命的變量。

1.2 問(wèn)題描述

雖然汽車(chē)檢測(cè)問(wèn)題某一時(shí)間段內(nèi)的到達(dá)率與服務(wù)率是確定的，但汽車(chē)到達(dá)檢測(cè)站的過(guò)程與其所用檢測(cè)時(shí)間都是隨機(jī)的。而檢測(cè)設(shè)備的數(shù)量(服務(wù)臺(tái)數(shù))是已知的，故檢測(cè)站的汽車(chē)檢測(cè)是一個(gè)典型的隨機(jī)服務(wù)系統(tǒng)(排隊(duì)論系統(tǒng))[9，10]。其排隊(duì)規(guī)則為部分顧客有優(yōu)先級(jí)，即顧客分為A類(lèi)和B類(lèi)，B類(lèi)顧客具有優(yōu)先級(jí)且部分服務(wù)臺(tái)只為B類(lèi)顧客服務(wù)。

1.3 排隊(duì)模型

本文建立并模擬的基本模型是多服務(wù)臺(tái)損失制，先到先服務(wù)排隊(duì)模型M/M/m1+m2/∞。解釋如下：

1)第一個(gè)M意為顧客到達(dá)的時(shí)間間隔滿(mǎn)足泊松分布，其參數(shù)設(shè)為λ，并對(duì)顧客進(jìn)行分類(lèi)，普通顧客A到達(dá)參數(shù)設(shè)為λ1，特殊顧客B到達(dá)參數(shù)設(shè)為λ2；

2)第二個(gè)M意為對(duì)顧客的服務(wù)時(shí)間滿(mǎn)足指數(shù)分布，其參數(shù)設(shè)為μ，普通顧客服務(wù)參數(shù)設(shè)為μ1，特殊顧客服務(wù)參數(shù)設(shè)為μ2；

3)m意為系統(tǒng)中有m個(gè)相互獨(dú)立的服務(wù)窗口；并對(duì)其進(jìn)行分類(lèi)，給特殊顧客預(yù)留的窗口數(shù)目為m2；

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

5)損失制意為顧客到達(dá)服務(wù)站時(shí)沒(méi)有空閑窗口便離去不等待，排隊(duì)長(zhǎng)度為0；

6)服務(wù)順序選擇為優(yōu)先級(jí)(B類(lèi)顧客具有優(yōu)先級(jí)，且有部分服務(wù)臺(tái)只允許B類(lèi)顧客接受服務(wù))。

2 MDSWCA改進(jìn)思想

本文應(yīng)用無(wú)線傳感器節(jié)點(diǎn)捕獲顧客流量[9]，經(jīng)檢測(cè)，所用的排隊(duì)系統(tǒng)中顧客流A的到達(dá)比較稀疏，而顧客流B的到達(dá)比較頻繁，因此,可以設(shè)定顧客流A的排隊(duì)規(guī)則為排隊(duì)隊(duì)長(zhǎng)為1的等待制，顧客流B的排隊(duì)規(guī)則可以判定為損失制。這樣的設(shè)定更加符合汽車(chē)檢測(cè)排隊(duì)系統(tǒng)的真實(shí)性，因?yàn)榕抨?duì)長(zhǎng)度大于1的話(huà)，顧客是不愿意等的，排隊(duì)長(zhǎng)度為1的時(shí)候顧客還是有等待直到排到自己被服務(wù)的耐心；而對(duì)于顧客流B來(lái)講，顧客到達(dá)非常頻繁，因此對(duì)于顧客流B的服務(wù)和排隊(duì)規(guī)則設(shè)定為損失制比較合理。綜合考慮這幾方面的因素，整個(gè)系統(tǒng)的服務(wù)規(guī)則為混合制排隊(duì)。

具體設(shè)定可以簡(jiǎn)單表示為系統(tǒng)的排隊(duì)規(guī)則：對(duì)于顧客種類(lèi)A, 顧客到達(dá)時(shí)刻允許每個(gè)窗口排隊(duì)1人；對(duì)于顧客種類(lèi)B，顧客到達(dá)時(shí)刻允許每個(gè)窗口排隊(duì)0人。

3 仿真與結(jié)果分析

3.1 數(shù)據(jù)參數(shù)

客戶(hù)到達(dá)率的隨機(jī)數(shù)據(jù)必須滿(mǎn)足λa≤λb，因?yàn)榭蛻?hù)到達(dá)率的數(shù)據(jù)參考是根據(jù)文獻(xiàn)[7]，在6～21之間產(chǎn)生(6≤λa+λb≤21)，這個(gè)數(shù)據(jù)區(qū)間是文獻(xiàn)[7]所采集的真實(shí)的數(shù)據(jù)區(qū)間。為了更加真實(shí)地模擬現(xiàn)實(shí)中的到達(dá)情況和服務(wù)情況，應(yīng)用信息采集系統(tǒng)[12]，將原來(lái)的15組數(shù)據(jù)增加到了30組，這樣一來(lái)就更加與現(xiàn)實(shí)情況相符合。本文在仿真軟件Matlab環(huán)境下，產(chǎn)生的30組顧客流A和顧客流B的泊松分布到達(dá)參數(shù)數(shù)據(jù)為λa,λb如表1。

3.2 仿真參數(shù)

1)總服務(wù)時(shí)間Τ：在仿真時(shí)間內(nèi)，系統(tǒng)為顧客提供的總服務(wù)時(shí)間即系統(tǒng)不空閑時(shí)間。故系統(tǒng)空閑時(shí)對(duì)總服務(wù)時(shí)間無(wú)貢獻(xiàn)

(4)

2)有效吞吐量Υ：仿真時(shí)間內(nèi)，所有服務(wù)臺(tái)所服務(wù)的顧客數(shù)目，到達(dá)服務(wù)臺(tái)但并沒(méi)有接受服務(wù)的顧客對(duì)有效吞吐量無(wú)貢獻(xiàn)。

3)成本C：在本文中，指系統(tǒng)所需要的人工成本。本文設(shè)定每臺(tái)機(jī)器需要2位工作人員，且每位工作人員的薪水為300/24h,系統(tǒng)使用的服務(wù)臺(tái)數(shù)n為

C=n×(300×2)

(5)

表1 顧客流輸入

組數(shù)λaλbλ組數(shù)λaλbλ組數(shù)λ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作為仿真軟件，并對(duì)原始損失制排隊(duì)論模型算法、優(yōu)先級(jí)排隊(duì)模型算法和本文中引入的混合制排隊(duì)模型算法進(jìn)行排隊(duì)系統(tǒng)性能比較，在文中選擇：總服務(wù)時(shí)間(total service time)、有效服務(wù)顧客吞吐量(effective throughput)、系統(tǒng)成本分析(system cost)這三個(gè)算法性能評(píng)估指標(biāo)來(lái)進(jìn)行評(píng)價(jià)。

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

圖2為隨機(jī)產(chǎn)生的30個(gè)時(shí)間段的30組顧客流A和顧客流B仿真結(jié)果可知：本文的引入混合制排隊(duì)模型比原始損失制排隊(duì)論模型算法的總的有效吞吐量增大了487人，且比優(yōu)先級(jí)算法增多了352人。

圖2 有效顧客吞吐分析

圖3為三種算法所用的排隊(duì)系統(tǒng)成本比較。通過(guò)在排隊(duì)系統(tǒng)中減少使用的服務(wù)臺(tái)總數(shù)，起到了排隊(duì)系統(tǒng)的成本控制的作用。

圖3 系統(tǒng)成本的對(duì)比

4 結(jié) 論

仿真實(shí)驗(yàn)表明：通過(guò)引入混合制排隊(duì)模型，整個(gè)排隊(duì)系統(tǒng)的性能有了較大的提升，在進(jìn)一步降低成本使用的情況下，有效提高了總的服務(wù)時(shí)間和接受服務(wù)的總的顧客數(shù)目。

[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] 何選森.隨機(jī)過(guò)程與排隊(duì)論[M].長(zhǎng)沙：湖南大學(xué)出版社,2010.

[3] 任敏麗.排隊(duì)論在銀行服務(wù)系統(tǒng)中的若干應(yīng)用研究[D].哈爾濱：哈爾濱工業(yè)大學(xué),2010.

[4] 李仕鵬.基于排隊(duì)論的汽車(chē)共享優(yōu)化設(shè)計(jì)[D].杭州:杭州電子科技大學(xué),2012.

[5] 劉文霞,仇國(guó)兵.電動(dòng)汽車(chē)快速充電站需求分析與設(shè)備優(yōu)化方法[J].天津大學(xué)學(xué)報(bào)，2012,45(12)：1111-1115.

[6] 倪志偉.基于排隊(duì)論的訂單處理系統(tǒng)建模與仿真[D].北京:北京交通大學(xué)，2009.

[7] 李如琦，蘇浩益.基于排隊(duì)論的電動(dòng)汽車(chē)充電設(shè)施優(yōu)化配置[J].電力系統(tǒng)自動(dòng)化,2011,35(14):58-61.

[8] 梅振宇,陳 峻,王 煒.城市路內(nèi)停車(chē)設(shè)置規(guī)模非線性?xún)?yōu)化模型及其算法[J].交通運(yùn)輸工程學(xué)報(bào),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] 蔡文婧,葛連升.基于排隊(duì)論的銀行業(yè)務(wù)窗口設(shè)置優(yōu)化[J].山東大學(xué)學(xué)報(bào)：工學(xué)版,2013,43(3):24-29.

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

[12] 趙 敏,常 杰,孫棣華.基于ZigBee和ARM的分布式RFID信息采集系統(tǒng)的設(shè)計(jì)[J].傳感器與微系統(tǒng),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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61163051)

TP 273

A

1000—9787(2017)02—0025—03

趙培瑤(1990-)，女，碩士研究生，研究方向?yàn)橹悄芸刂扑惴ā?/p>