基于NEM的置换流水车间调度算法

摘要：对类电磁机制算法进行优化设计，提出基于NEM求解置换流水车间调度问题的算法。该算法将通过引入随机键的编码方式和对较差粒子进行变异的操作方式，以提高算法求解的精度和收敛的速度。最后将通过仿真实验验证该算法的有效性。

关键词：类电磁机制算法;NEM;调度;变异

中图分类号：TP3

文献标识码A

置换流水车间调度问题（Permutation Flow ShopScheduling Problem，PFSP）广泛存在于生产系统和服务系统中，是典型的组合优化问题，也是典型的NP难问题[1]。PFSP的求解方法很多：构造型启发式算法，能够快速地构造解，但解的质量和算法通用性通常较差;基于物理或仿生学原理的改进型调度算法，能以较大概率在可行时间范围内求得该问题的近似最优解，但其复杂度一般较大，并且算法的结构和参数都需要进行合适的设定才能达到预期的效果[2]。针对上述情况，提出基于NEM求解置换流水车间调度问题的算法。该算法在求解PFSP时，将提出对较差粒子进行变异操作这一思想，以提高算法的求解精度并加快算法的收敛速度。最后将通过实验仿真验证基于NEM求解PFSP算法的有效性。

1 NEM算法简介[3]

通过对EM算法的初始化、局部搜索、合力计算和粒子移动四个步骤分别进行改进，并在此基础上提出一种实用的类电磁机制算法——归一化类电磁机制算法（ Normalization Electromagnetism-likeMechanism，NEM）。对EM算法“复杂度较大”这一缺陷，采用归一化方法，使得目标函数值都在某个小范围内，这样就可以减少运算量。针对EM算法局部搜索和计算合力中的缺陷，采用去掉易产生溢出错误的分母部分‖x_j-x_i‖²，添加一个合力计算修

2 NEM算法的改进——变异操作

为了扩大有效搜索范围，增强算法的全局搜索能力，根据优胜劣汰原则，在不增加新粒子的情况下，将最差的几个粒子进行变异操作后，选择变异后的较优粒子替换原来的最差粒子，以便得到更优的解。当粒子数不小于30时，选择变异当前粒子群中最差的5个粒子，当粒子数小于30时，略过此步。这么做是由于当粒子数过少时，变异步骤会扰乱类电磁机制算法的收敛趋势，并且会降低算法的收敛速度。

实现这一步骤比较简单，首先按目标函数值的大小将粒子进行排序，目标函数值较大的排在后面，然后选择最后的5个粒子进行变异操作。变异操作方式分为交换变异、插入变异和反转变异，三种变异方式如图1所示。

对选出的5个最差粒子分别使用这三种方式进行变异操作，共产生15个新粒子。从中选取5个最优的粒子替换原粒子队列中最后的5个粒子，最后再计算目标函数值并进行重新排序，更新当前最优值。

3 随机键的引入

在一些离散型的优化问题中，为了方便对解直接进行数学操作，广泛采用了随机键的编码方式[4]。本文在基于NEM算法解决PFSP问题时，也借用随机键的编码方式模拟工件的排序。

随机键的编码方式就是将解转换表示为一串（0，1）之间的随机数，并将这串随机数用作解码时的分类键。例如一个9工件问题的调度方案：[0.82， 0.23， 0.45， 0.74， 0.87， 0.11，0.56， 0.69， 0.78]，其中，编码中的位置代表工件，处在位置的随机数代表工件的排列顺序。将这些随机数按照升序（工件的加工顺序）进行排列，可得下面的排序：8-2-3-6-9-1-4-5—7。这种编码方式可以消除NEM算法在求解过程中产生的不可行解。

随机键与工件排序的转换方式如图2所示。首先将搜索到的粒子进行随机键转换，然后计算其适应值，接着再进行粒子的合力计算和移动操作，最后将移动后得到的粒子再进行随机键转换，进入下一轮的循环。

4 算法设计与实现

通过随机键编码方式的引入，将离散型工件排序编码转变成NEM算法可直接使用的连续型编码。将总的完工时间看作目标函数，其值越小，则解的适应度值就越高。使用随机方式初始化种群粒子，当算法迭代次数到达预先设定的某个值时自动停止。算法的局部搜索采用最简单的方式一仅对最优粒子采取局部搜索。在规定的最大迭代次数内，对当前最优粒子的每一维随机均匀地按照一定步长进行局部搜索。在此过程中，如果找到更优的解，则用其替换当前最优粒子。基于NEM的PFSP算法的流程如图3所示。

5 实验结果与分析

实验选取29个应用广泛的Benchmark问题进行性能测试，并与传统GA和NEH作比较。这29个Benchmark问题指Carlier（ 1978）提出的8个算例Carl，Car2，…，Car8和Tailland（ 1993）提出的21个算例Rec01，Rec03，…，Rec41。NEM和GA分别对每个算例独立运行20次，最大迭代次数均设为300，粒子数均设为30。实验仿真结果如表1所示。表中，m和n分别表示机器数和工件数，c*表示问题的最优解，RE表示与最优解c*的相对误差（c heu max- c*）xl00%，BRE为最优相对误差，ARE为平均相对误差。

从表1可以看出，加入变异操作改进后的NEM算法具有很好的优化质量。尤其对Carlier系列问题，均能得到已知最优解，ARE也都小于GA。对Tailland系列问题也能够得到良好的近似最优解，且质量明显优于方法GA和NEH，甚至NEM的最差结果都远远优于NEH方法。由此可见，经过改进的NEM算法在优化质量方面相对于方法NEH和GA具有很大的优越性。

6 实例

某SMT生产线由高速贴装机HS60和多功能贴装机80F5组成，产品设计为单面贴装。待贴装元器件共有42种，根据封装形式和组装精度分别将这些元器件分配给HS60和80F5。分配给HS60的元器件为1～16，17～23必须分配到80F5上组装，而24～42则两者皆可。现需对24～42共计19种元器件进行EM算法优化分配，要求总的贴装时间最小，并且两种贴装机的贴装时间差不大于0.35s。42种元器件的贴装机分配、貼装时间以及数量见表2-表4。

通过NEM算法的优化，所求得最优解为：（1，1，0，1，0，0，1，0，1，0，1，1，0，1，1，1，1，1，1）和（1，1，0，1，0，1，1，0，0，1，1，1，0，0，1，1，0，1，1），求解过程中获得了两个最优解。两个最优解的总贴装时间都是30.22s，T_HS60=15.26s，T_80ES=15.26s，实际贴装时间差为ξ= 0.30s，符合生产线平衡的要求。

7 结束语

针对EM算法不能直接被用来解决流水车间调度这类离散型优化问题的情况，通过引入随机键的编码方式将工序编码方式进行了转换，然后在NEM算法的基础上增添了变异操作从而对算法进行了改进，最后将改进后的NEM算法应用于解决离散型的流水车间调度问题。实验仿真结果表明，改进后的NEM算法成功地解决了流水车间调度问题。

参考文献

[1]刘敏，张超勇，张国军，等，基于混合粒子群优化算法的置换流水车间调度问题研究[J].中国机械工程，2011，22（17）： 2048-2053.

[2] CEN M，CHENG R.Cenetic algorithm and engineering design[M]. Beijing： Science Press， 2000.

[3]姜建国，王双记，刘永青，等，一种实用的类电磁机制算法[J].西安电子科技大学学报，2013（02）：48-53.

[4]KOLISCH R，HARTMANN S. Heuristic algorithms for solving theresource -constrained project scheduling problem： classificationand computational analysis [M]. WECIARZ J （editor）： ProjectScheduling-Recent Models， Algorithms and Applications， KluwerAcademic Publishers. Boston. 1999：147.