基于遗传算法的维修服务人员选派问题研究

牛丹丹，董增寿

(太原科技大学电子信息工程学院，太原 030024)

随着科学技术的不断发展，企业设备越来越复杂，功能越来越多样化，大幅度地增加了维修难度。但是由于每个维修人员所拥有的技能各不相同，维修能力存在差异。因此，选择合适的维修人员去高效的执行维修任务是极其重要的[1]。

维修人员选派问题[2-3]是指维修人员为客户提供维修服务，每个各户的服务任务需求各不相同，一个服务任务由多个不同技能的服务组成，每个维修人员所专注的维修技能是各不相同的，企业安排维修人员执行这些任务以正确匹配客户需求，快速提供服务，满足客户需求。

维修人员选派问题是一个典型的NP-Hard问题，国内外很多学者对服务调度进行了广泛研究。文献[4]假设只有两种类型的故障，而维修员工分为三类。故障类型少，这和实际情况是不相符的。文献[5]提出故障维修分配分两步实现，首先通过求解模型得到一个优化的维修人员首次分配方案，再用最大优先度原则进行再分配，直到全部的故障设备都得到维修。这种方法要求每次腾出的维修人员的信息必须及时，才能进行再分配。文献[6-7]提出了一种面向MRO服务的维修人员分派方法，采用遗传算法进行团队智能组合。但服务任务和服务团队的不匹配度模型复杂，计算量大。本文针对维修服务人员的选派问题进行了研究，建立了任务-团队技能不匹配度模型，采用一种基于遗传算法的智能选派方法进行求解。最后，通过仿真实验得出最优解，验证了模型和算法的有效性。

1 派工调度模型

当接到客户的维修请求后，企业首先要对同一时间段的维修服务进行汇总，生成任务表以及所需的技能表，随后选派维修人员执行任务。

一个故障可能需要一种或多种技能，则用向量来表示故障类型所需技能。假设服务任务需求的技能向量：

RWrequire=[rw1,rw2,…,rwn]，其中rw代表任务所需的某一项技能。

已有服务员工的技能向量表为YGskill=[ygk1,ygk2,…,ygkn]；其中ygk代表员工所拥有的技能及其对应的等级， 如表1所示， 其中表中的数字代表员工具有该项技能的等级， 0表示员工不具备该技能。

表1 员工技能等级Tab.1 Skill level of maintenance staff

例如，技能向量[0，3，0，5，0，2]表示维修员工具有技能序列中的第二项技能(水平为3级)，第四项技能(水平为5级)和第六项技能(水平为2级)。

团队技能向量和员工技能向量相似，对于同一项技能等级高的员工能代替等级低的员工，但等级低的员工不能代替等级高的员工。例如，员工1的技能向量为[5，0，2，0，1，3]，员工2的技能向量为[2，4，0，3，0，5]，那么，员工1和员工2组成的团队技能向量为[5，4，2，3，1，5].

服务任务和服务团队的不匹配度可以表示为：

其中，△jnc表示服务团队技能向量和服务任务技能向量之差，即：

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

(2)

其中：△jnci=rwi-ygki.

如果△jnci<0，说明团队组合中该项技能超出服务任务要求，表示团队技能虽然满足要求，但不是最理想的组合。

如果△jnci=0，说明该项技能完全符合要求，表示服务团队的技能水平恰好满足服务任务的技能需求，这是最理想、最匹配的组合。

如果△jnci>0，说明该项技能不符合要求，应舍去这种组合。

2 求解算法设计

2.1 遗传算法

遗传算法(Genetic Algorithm，GA)是由美国Michigan大学的Holland教授提出的[8]，其思想来自于达尔文的进化论和孟德尔的遗传学说，是求解最优化问题的有效工具。

2.2 算法步骤

针对上述任务-团队技能的不匹配度模型，采用如下步骤智能选派最佳的团队去执行维修任务。

Step1：汇总客户维修需求及其技能所需等级的信息，生成任务列表RenWu；

Step2：依据要服务的任务和等级选定员工，存入到该任务的待选员工档案RenWu_DXYG中；

Step3：设置种群个数POP，进化次数为gen，交叉率为0.85，变异概率为0.1；

Step4：初始化种群pop，依据编码规则生产第1代种群个体，并计算目标值；

Step5：适应度评估，选择目标值较小的个体作为适应度较大的个体执行单点交叉、变异进化操作；

Step6：计算目标值，依据公式(1)计算所派的一组员工技能等级与任务所需的等级差之和；

Step7：重复Step5-Step6，直到满足终止条件；

Step8：结束，输出最优解。

2.3 编码方法

设需求任务的技能及其等级构成的矩阵为：

在上述矩阵中，10行表示有10个任务，第一列为该任务所需要的技能种类，第二列为该技能的等级要求。如第一行(1，2)表示第一项故障任务需要第1种技能，且等级至少为2.

编码采用员工号直接编码法，这种方法简单有效，不需要解码。假设种群产生的一个个体为：pop1=(10，5，9，3，8，16)，表示依次选派第10，5，9，3，8，16号员工去完成上述6个任务。

2.4 选择

从种群中根据个体的适应度值，按照某种准则挑选出好的个体进入下一代种群。此处采用轮盘赌选择。每个个体进入下一代的概率等于其适应度值与整个种群中个体适应度值和的比例，即适应度值越高，被选中的概率越大，进入下一代的可能性越大。

2.5 交叉算子

交叉运算是遗传算法中产生新个体的基本操作，它以某一概率相互交换某两个个体之间的部分染色体。本文采用单点交叉，随机选择1个交叉点，在该点互换交换两个个体的部分染色体，产生2个新的子代个体，如图1所示。

图1 单点交叉运算示意图Fig.1 Single point crossover operation

2.6 变异

某一位或某几位“基因”上做突变运算，改变染种群中的个体按照变异概率在随机指定的色体的元素，从而产生的新个体，维持解群体的多样性。如对个体(10，5，9，3，8，16)进行变异操作，则有可能变成(10，5，9，7，8，16).

3 应用实例和结果分析

实验假设企业复杂装备可能出现的所有故障共有n种，解决这n种故障共需要10种技能，从1到10进行编号。从大量任务中选取了两组最具有代表性的任务，如表2所示：

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

表2 任务所需技能及其等级Tab.2 The task required skills and level

若某企业共有20名维修员工，从1到20进行编号。技能等级分为7个等级，每名员工都有若干个技能，其等级如表3所示。采用上述所提的算法步骤分别对任务1和任务2进行求解，其中各参数依次为种群=200，交叉概率=0.85，变异概率=0.1 .经过300代选择、交叉和变异进化操作，结果分别如表4、表5所示，由于篇幅关系，这里只列出了部分解。

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

表4 任务1维修员工调度结果Tab.4 Maintenance staff scheduling results of task 1

表5 任务2维修员工调度结果Tab.5 Maintenance staff scheduling results of task 2

根据表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)执行任务1时的技能匹配差值为0，表明此时选派方案与任务所需技能要求完全符合。其他组合虽然也满足要求，但不是最理想组合。管理人员可根据实际情况选择其中的任何一组去执行任务。

同样表5中，加黑的员工组合(8，11，1，10，3，8，12，2，5，8)、(17，8，1，10，8，20，12，2，5，8，13)在执行任务2时，团队技能匹配差值最小均为13，为最佳的选派方法。

由表4和表5可知，任务所需要的技能越少，其完全符合其要求的员工组合越多；任务所需要的技能越多，完全符合其要求的员工组合越少。

4 结束语

引入技能向量的概念表示任务需求和员工的技能等级，提出选派员工的技能匹配模型，并采用基于遗传算法的选派方法求解了两个任务，结果表明模型和算法的可行性。目前大多数企业在进行派工调度时仍然采用人工调度的方法，调度人员大都依靠自身经验和生活经验来进行操作的。本文所提出的选派方法为调度人员提供了更多的选择，大大提高了调度人员的工作效率。实际生活中维修人员拥有的技能越多，被选派的概率越大，其工作量也越大，而本文的模型未考虑员工的工作量问题，这也是下一步需要研究的内容。

参考文献：

[1] 唐海波，叶春明.基于MRO服务提供商的设备预维修调度[J].系统管理学报，2012，21(3)：336-351.

[2] 江俊杰，王丽亚.基于遗传算法的带服务匹配的现场产品服务调度[J].计算机集成制造系统，2012，18(11)：2573-2577.

[3] 江俊杰，王丽亚.基于遗传算法的多技能需求现场产品服务调度[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] 厉红，钱省三.半导体制造设备的维修调度研究[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] 李旭，祁国宁.复杂装备MRO服务的若干关键技术研究[D].杭州：浙江大学，2012，3.

[8] 雷英杰，张善文，李续武，等.MATLAB遗传算法工具箱及应用[M].西安：西安电子科技大学出版社，2005.