牛丹丹，董增壽

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

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

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

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

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

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

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

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

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

表1 員工技能等級(jí)Tab.1 Skill level of maintenance staff

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

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

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

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

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

(2)

其中：△jnci=rwi-ygki.

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

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

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

2 求解算法設(shè)計(jì)

2.1 遺傳算法

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

2.2 算法步驟

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

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

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

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

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

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

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

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

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

2.3 編碼方法

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

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

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

2.4 選擇

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

2.5 交叉算子

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

圖1 單點(diǎn)交叉運(yùn)算示意圖Fig.1 Single point crossover operation

2.6 變異

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

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

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

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

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

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

表3 員工技能等級(jí)信息表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時(shí)的技能匹配差值為0，表明此時(shí)選派方案與任務(wù)所需技能要求完全符合。其他組合雖然也滿足要求，但不是最理想組合。管理人員可根據(jù)實(shí)際情況選擇其中的任何一組去執(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時(shí)，團(tuán)隊(duì)技能匹配差值最小均為13，為最佳的選派方法。

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

4 結(jié)束語

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

參考文獻(xiàn)：

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

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

[3] 江俊杰，王麗亞.基于遺傳算法的多技能需求現(xiàn)場(chǎng)產(chǎn)品服務(wù)調(diào)度[J].計(jì)算機(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].中國機(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.