基于遺傳算法的維修服務(wù)人員選派問題研究

牛丹丹，董增壽

(太原科技大學(xué)電子信息工程學(xué)院，太原 030024)

隨著科學(xué)技術(shù)的不斷發(fā)展，企業(yè)設(shè)備越來越復(fù)雜，功能越來越多樣化，大幅度地增加了維修難度。但是由于每個維修人員所擁有的技能各不相同，維修能力存在差異。因此，選擇合適的維修人員去高效的執(zhí)行維修任務(wù)是極其重要的[1]。

維修人員選派問題[2-3]是指維修人員為客戶提供維修服務(wù)，每個各戶的服務(wù)任務(wù)需求各不相同，一個服務(wù)任務(wù)由多個不同技能的服務(wù)組成，每個維修人員所專注的維修技能是各不相同的，企業(yè)安排維修人員執(zhí)行這些任務(wù)以正確匹配客戶需求，快速提供服務(wù)，滿足客戶需求。

維修人員選派問題是一個典型的NP-Hard問題，國內(nèi)外很多學(xué)者對服務(wù)調(diào)度進(jìn)行了廣泛研究。文獻(xiàn)[4]假設(shè)只有兩種類型的故障，而維修員工分為三類。故障類型少，這和實際情況是不相符的。文獻(xiàn)[5]提出故障維修分配分兩步實現(xiàn)，首先通過求解模型得到一個優(yōu)化的維修人員首次分配方案，再用最大優(yōu)先度原則進(jìn)行再分配，直到全部的故障設(shè)備都得到維修。這種方法要求每次騰出的維修人員的信息必須及時，才能進(jìn)行再分配。文獻(xiàn)[6-7]提出了一種面向MRO服務(wù)的維修人員分派方法，采用遺傳算法進(jìn)行團(tuán)隊智能組合。但服務(wù)任務(wù)和服務(wù)團(tuán)隊的不匹配度模型復(fù)雜，計算量大。本文針對維修服務(wù)人員的選派問題進(jìn)行了研究，建立了任務(wù)-團(tuán)隊技能不匹配度模型，采用一種基于遺傳算法的智能選派方法進(jìn)行求解。最后，通過仿真實驗得出最優(yōu)解，驗證了模型和算法的有效性。

1 派工調(diào)度模型

當(dāng)接到客戶的維修請求后，企業(yè)首先要對同一時間段的維修服務(wù)進(jìn)行匯總，生成任務(wù)表以及所需的技能表，隨后選派維修人員執(zhí)行任務(wù)。

一個故障可能需要一種或多種技能，則用向量來表示故障類型所需技能。假設(shè)服務(wù)任務(wù)需求的技能向量：

RWrequire=[rw1,rw2,…,rwn]，其中rw代表任務(wù)所需的某一項技能。

已有服務(wù)員工的技能向量表為YGskill=[ygk1,ygk2,…,ygkn]；其中ygk代表員工所擁有的技能及其對應(yīng)的等級， 如表1所示， 其中表中的數(shù)字代表員工具有該項技能的等級， 0表示員工不具備該技能。

表1 員工技能等級Tab.1 Skill level of maintenance staff

例如，技能向量[0，3，0，5，0，2]表示維修員工具有技能序列中的第二項技能(水平為3級)，第四項技能(水平為5級)和第六項技能(水平為2級)。

團(tuán)隊技能向量和員工技能向量相似，對于同一項技能等級高的員工能代替等級低的員工，但等級低的員工不能代替等級高的員工。例如，員工1的技能向量為[5，0，2，0，1，3]，員工2的技能向量為[2，4，0，3，0，5]，那么，員工1和員工2組成的團(tuán)隊技能向量為[5，4，2，3，1，5].

服務(wù)任務(wù)和服務(wù)團(tuán)隊的不匹配度可以表示為：

其中，△jnc表示服務(wù)團(tuán)隊技能向量和服務(wù)任務(wù)技能向量之差，即：

△jnc=RWrequire-YGskill=[△jnc1,△jnc2,…,△jncn]

(2)

其中：△jnci=rwi-ygki.

如果△jnci<0，說明團(tuán)隊組合中該項技能超出服務(wù)任務(wù)要求，表示團(tuán)隊技能雖然滿足要求，但不是最理想的組合。

如果△jnci=0，說明該項技能完全符合要求，表示服務(wù)團(tuán)隊的技能水平恰好滿足服務(wù)任務(wù)的技能需求，這是最理想、最匹配的組合。

如果△jnci>0，說明該項技能不符合要求，應(yīng)舍去這種組合。

2 求解算法設(shè)計

2.1 遺傳算法

遺傳算法(Genetic Algorithm，GA)是由美國Michigan大學(xué)的Holland教授提出的[8]，其思想來自于達(dá)爾文的進(jìn)化論和孟德爾的遺傳學(xué)說，是求解最優(yōu)化問題的有效工具。

2.2 算法步驟

針對上述任務(wù)-團(tuán)隊技能的不匹配度模型，采用如下步驟智能選派最佳的團(tuán)隊去執(zhí)行維修任務(wù)。

Step1：匯總客戶維修需求及其技能所需等級的信息，生成任務(wù)列表RenWu；

Step2：依據(jù)要服務(wù)的任務(wù)和等級選定員工，存入到該任務(wù)的待選員工檔案RenWu_DXYG中；

Step3：設(shè)置種群個數(shù)POP，進(jìn)化次數(shù)為gen，交叉率為0.85，變異概率為0.1；

Step4：初始化種群pop，依據(jù)編碼規(guī)則生產(chǎn)第1代種群個體，并計算目標(biāo)值；

Step5：適應(yīng)度評估，選擇目標(biāo)值較小的個體作為適應(yīng)度較大的個體執(zhí)行單點交叉、變異進(jìn)化操作；

Step6：計算目標(biāo)值，依據(jù)公式(1)計算所派的一組員工技能等級與任務(wù)所需的等級差之和；

Step7：重復(fù)Step5-Step6，直到滿足終止條件；

Step8：結(jié)束，輸出最優(yōu)解。

2.3 編碼方法

設(shè)需求任務(wù)的技能及其等級構(gòu)成的矩陣為：

在上述矩陣中，10行表示有10個任務(wù)，第一列為該任務(wù)所需要的技能種類，第二列為該技能的等級要求。如第一行(1，2)表示第一項故障任務(wù)需要第1種技能，且等級至少為2.

編碼采用員工號直接編碼法，這種方法簡單有效，不需要解碼。假設(shè)種群產(chǎn)生的一個個體為：pop1=(10，5，9，3，8，16)，表示依次選派第10，5，9，3，8，16號員工去完成上述6個任務(wù)。

2.4 選擇

從種群中根據(jù)個體的適應(yīng)度值，按照某種準(zhǔn)則挑選出好的個體進(jìn)入下一代種群。此處采用輪盤賭選擇。每個個體進(jìn)入下一代的概率等于其適應(yīng)度值與整個種群中個體適應(yīng)度值和的比例，即適應(yīng)度值越高，被選中的概率越大，進(jìn)入下一代的可能性越大。

2.5 交叉算子

交叉運算是遺傳算法中產(chǎn)生新個體的基本操作，它以某一概率相互交換某兩個個體之間的部分染色體。本文采用單點交叉，隨機選擇1個交叉點，在該點互換交換兩個個體的部分染色體，產(chǎn)生2個新的子代個體，如圖1所示。

圖1 單點交叉運算示意圖Fig.1 Single point crossover operation

2.6 變異

某一位或某幾位“基因”上做突變運算，改變?nèi)痉N群中的個體按照變異概率在隨機指定的色體的元素，從而產(chǎn)生的新個體，維持解群體的多樣性。如對個體(10，5，9，3，8，16)進(jìn)行變異操作，則有可能變成(10，5，9，7，8，16).

3 應(yīng)用實例和結(jié)果分析

實驗假設(shè)企業(yè)復(fù)雜裝備可能出現(xiàn)的所有故障共有n種，解決這n種故障共需要10種技能，從1到10進(jìn)行編號。從大量任務(wù)中選取了兩組最具有代表性的任務(wù)，如表2所示：

其中任務(wù)1，需要技能Ⅰ(等級3)、Ⅴ(等級5)、Ⅶ(等級4)、Ⅷ(等級3)、Ⅸ(等級3)、Ⅹ(等級7)；任務(wù)2需要技能Ⅰ(等級2)、Ⅱ(等級3)、Ⅲ(等級1)、Ⅳ(等級5)、Ⅴ(等級4)、Ⅵ(等級3)、Ⅶ(等級3)、Ⅷ(等級2)、Ⅸ(等級3)、Ⅹ(等級4)。

表2 任務(wù)所需技能及其等級Tab.2 The task required skills and level

若某企業(yè)共有20名維修員工，從1到20進(jìn)行編號。技能等級分為7個等級，每名員工都有若干個技能，其等級如表3所示。采用上述所提的算法步驟分別對任務(wù)1和任務(wù)2進(jìn)行求解，其中各參數(shù)依次為種群=200，交叉概率=0.85，變異概率=0.1 .經(jīng)過300代選擇、交叉和變異進(jìn)化操作，結(jié)果分別如表4、表5所示，由于篇幅關(guān)系，這里只列出了部分解。

表3 員工技能等級信息表Tab.3 Skill level information of maintenance staff

表4 任務(wù)1維修員工調(diào)度結(jié)果Tab.4 Maintenance staff scheduling results of task 1

表5 任務(wù)2維修員工調(diào)度結(jié)果Tab.5 Maintenance staff scheduling results of task 2

根據(jù)表4，加黑的員工組合(8，3，12，13，5)、(8，12，20，5)、(17，3，12，13，5)、(17，8，12，13，5)、(17，8，12，20，5)執(zhí)行任務(wù)1時的技能匹配差值為0，表明此時選派方案與任務(wù)所需技能要求完全符合。其他組合雖然也滿足要求，但不是最理想組合。管理人員可根據(jù)實際情況選擇其中的任何一組去執(zhí)行任務(wù)。

同樣表5中，加黑的員工組合(8，11，1，10，3，8，12，2，5，8)、(17，8，1，10，8，20，12，2，5，8，13)在執(zhí)行任務(wù)2時，團(tuán)隊技能匹配差值最小均為13，為最佳的選派方法。

由表4和表5可知，任務(wù)所需要的技能越少，其完全符合其要求的員工組合越多；任務(wù)所需要的技能越多，完全符合其要求的員工組合越少。

4 結(jié)束語

引入技能向量的概念表示任務(wù)需求和員工的技能等級，提出選派員工的技能匹配模型，并采用基于遺傳算法的選派方法求解了兩個任務(wù)，結(jié)果表明模型和算法的可行性。目前大多數(shù)企業(yè)在進(jìn)行派工調(diào)度時仍然采用人工調(diào)度的方法，調(diào)度人員大都依靠自身經(jīng)驗和生活經(jīng)驗來進(jìn)行操作的。本文所提出的選派方法為調(diào)度人員提供了更多的選擇，大大提高了調(diào)度人員的工作效率。實際生活中維修人員擁有的技能越多，被選派的概率越大，其工作量也越大，而本文的模型未考慮員工的工作量問題，這也是下一步需要研究的內(nèi)容。

參考文獻(xiàn)：

[1] 唐海波，葉春明.基于MRO服務(wù)提供商的設(shè)備預(yù)維修調(diào)度[J].系統(tǒng)管理學(xué)報，2012，21(3)：336-351.

[2] 江俊杰，王麗亞.基于遺傳算法的帶服務(wù)匹配的現(xiàn)場產(chǎn)品服務(wù)調(diào)度[J].計算機集成制造系統(tǒng)，2012，18(11)：2573-2577.

[3] 江俊杰，王麗亞.基于遺傳算法的多技能需求現(xiàn)場產(chǎn)品服務(wù)調(diào)度[J].計算機工程，2012，38(18)：174-177.

[4] CAI X，LI K N.A genetic algorithm for scheduling staff of mixed skills under multi-criteria[J].European Journal of Operational Research，2000，125(2)：359-369.

[5] 厲紅，錢省三.半導(dǎo)體制造設(shè)備的維修調(diào)度研究[J].中國機械工程，2006，17(16)：1693-1697.

[6] KAI PAN，DONG ZHANG.A Three-Phase Approach to Service Staff Assignment for MRO Tasks[C]// Proceedings of IIE Asian Conference 2011，Shanghai，China：Shanghai Jiao Tong University Press，2011：612-622.

[7] 李旭，祁國寧.復(fù)雜裝備MRO服務(wù)的若干關(guān)鍵技術(shù)研究[D].杭州：浙江大學(xué)，2012，3.

[8] 雷英杰，張善文，李續(xù)武，等.MATLAB遺傳算法工具箱及應(yīng)用[M].西安：西安電子科技大學(xué)出版社，2005.