基于改进和声搜索算法的柔性作业车间调度研究
2018-10-23向双玲安友军刘秀凤
向双玲 安友军 刘秀凤
摘要：结合柔性作业车间调度问题，对和声搜索算法中新和声的产生方式及变异操作进行改进，提出了改进和声搜索算法。在改进算法中，对新和声的合成方式采用精英保留策略，保证新和声的较优性能；在迭代过程中引入变领域搜索算法，以提高算法的全局搜索能力。最后通过仿真实验对改进算法的求解性能进行检验，验证了改进算法在求解柔性作业车间问题上的可行性及有效性。
Abstract： Combined with the flexible job shop scheduling problem， the new harmony mode and the mutation operation in the harmony algorithm are improved， and an improved harmony search algorithm is proposed. In the improved algorithm， the elite harmony strategy is adopted for the synthesis of the new harmony to ensure the superior performance of the new harmony. The variable domain search operator is introduced in the iterative process to further improve the global search ability of the algorithm. Finally， the performance of the improved algorithm is tested by experimental simulation， and the feasibility and effectiveness of the algorithm in solving the flexible work shop problem are verified.
关键词：柔性作业车间调度；和声搜索算法；精英保留策略；变邻域搜索
Key words： flexible job shop scheduling；harmony algorithm；elite retention strategy；variable neighborhood search
中图分类号：TP181 文献标识码：A 文章编号：1006-4311（2018）31-0274-04
0 引言
柔性作业车间调度问题（Flexible Job-Shop Scheduling Problem，FJSP）是一个经典且复杂的组合优化问题，其中，求解该问题最常用的方法为元启发式算法，例如：遗传算法[1]，粒子群算法[2]，蚁群算法[3]等。和声搜索（Harmony Research，HS）算法是由韩国学者Geem Z W[4]等人在受到音乐创作的启发后，提出的一种全局搜索算法。王勇臻等[5]用和声搜索算法求解了旅行商问题；刘乐等[6]针对单机最大延迟重调度问题，设计了一种和声变邻域搜索算法。
与其他算法相比，和声搜索算法的结构设计简单、灵活通用，易与其他算法混合使用。针对FJSP的特点，借鉴变邻域较强的局部搜索能力，提出一种改进和声变邻域搜索算法。首先对新和声的产生方式进行改进，确保新调度解的有效性，然后对新解进行变邻域操作，最后利用仿真实验检验改进算法的有效性及最优解的质量。
1 柔性作业车间调度问题
柔性作业车间调度问题较传统作业车间调度问题更加复杂，其可用数学模型描述为：n个工件在m台机器上加工，工件集为J={J1，J2，…，Jn}，机器集为M={M1，M2，…，Mn}，每个工件包含一道或多道工序，工件i的工序集合为Oi={Oi1，Oi2，…，Oij}，工件i的第j道工序可供选择的机器的集合为Mij={Mij1，Mij2，…，Mijk}，工件i的第j道工序在机器k上的加工时间集合为pij={pij1，pij2，…，pijk}，所有集合中的数据均已知，结合生产要求，将所有待加工的工件安排在机器上加工，保证生产的稳定性和有序性。基于上述思路，以最大完工时间为优化目标，建立FJSP的调度模型如下：
2 基本和声搜索算法
2.1 初始化和声记忆库
选择用随机生成的方式产生和声记忆库HM，调度问题在初始化时，加工每道工序可供选择的机器有多台，因此每组和声解用双层编码方式产生。第一层为基于工件工序的编码，工件号在工序码中出现的次数表示该工件的工序数；第二层为机器编码，每个工序在可供选择的机器集内选择任意一台机器，机器序号作为该工序的机器编码。任一双层编码的和声解都能解码成一个初始调度方案，并能直观看出各工件选择加工的机器和各工序加工的先后次序。图1为一个工序和机器各有12个编码的双层初始和声。
图1中Oij表示工件代号，i表示工件号，j为工件i的第j道工序；机器链中的编码为对应工件工序的加工机器在机器集中的顺序号。例如：工序编码中的第八个数字“1”表示工件1的第二道工序，对应的机器码“2”表示选择该道工件工序在当前可选的机器集合中的第二台机器。
2.2 新和聲的产生
新和声的产生包括两个部分，第一个部分为工序的新和声，第二部分为机器的新和声。根据HS算法产生新和声的过程，当新和声来自于记忆库，直接从记忆库中分别获得工序码和机器码的新和声。用和声算法求解车间调度问题，产生工序码的新和声会遇到这样的问题：若HMS较小，当某一变量从对应列中随机取值时，所在列的值为[2 2 3 2 1 2 2 1 2 1 1 2 2 4 4 1 4 2 1 2]，变量取值为1，2，4，对应的工件的工序数都将超过该工件的最大工序数，只有取值为3时才能满足条件，因此变量无法取得满足要求的解或取得目标值的概率很低，且在迭代后期，较小的和声库将降慢最优解的更新速度。若HMS较大，和声库包含较多的大小不等的目标解，得到满意解的概率较大，但运算量大。
其传统的和声算法的新和声产生策略为：当变量在和声库中无法获得目标变量时，变量将从当前最优和声解中随机取得变量值，表达式如下。
3 改进和声搜索算法
3.1 新和声库的产生
基于原始新和声的产生都是随机的，无法在短时间内获得更优的解，本文将借鉴遗传算法中的精英保留策略，根据适应度的大小来决定新和声信息的构成。同时，将传统的从全部初始解中随机选择信息变为从种群中部分较好的个体中选择信息。同时，每次产生多个和声来更新和声库。表达式如下：
由于目标函数，即最短完工时间越短，解越优，则适应度fitness取每个个体完工时间ObjV的倒数。按照适应度从大到小的原则依次选取目标个体，该个体的信息保留比率rate取适应度与该目标个体完工时间在种群中的排序值order（按从小到大的顺序）的乘积。该目标个体的信息保留长度SLi取工件总长度tota ln umber与信息保留比率rate的乘积。保留策略分两种：
①所选信息在新和声中对应位置无信息，则直接复制给新和声。
②所选信息在新和声中对应位置有信息，则复制给新和声中无信息的其它位置上。（图2）
新和声产生的具体执行步骤如下：
Step1：计算每个个体的适应度值及信息保留比例rate。
Step2：找出初始解中的最优个体，计算该个体保留信息的长度SLi。随机选择信息复制给新和声new。
Step3：寻找下一个适应度值排序仅次于上一个被选个体的较优个体，若该个体的SLi和新和声已有信息长度SL大于等于小于工件总数，则更新SLi，其公式如下：
找出该目标个体中新和声中没有的其它信息，从中随机选择SLi个信息，根据上述保留策略将信息复制给新和声。
Step4：若新和聲的长度SL小于tota ln umber，则返回Step3；否则，将新和声放进新和声集合中。
3.2 变邻域搜索算法
在车间调度问题中，工件的加工满足工序约束和机器约束，目标值的好坏在很大程度上取决于关键路径的好坏，优化关键路径实质是尽可能找到问题的最优解。交换记忆库和新和声中相邻工序的次序能保证后续解的有效性和质量；即当产生一组新和声向量后，对工序码进行变邻域搜索，提高算法的局部搜索能力，两道工序顺序交换的过程如图3所示。具体步骤为：
Step1：交换除第一个和最后一个关键块外的其它关键块的块首和块尾。
Step2：若第一个人关键块包含两道以上关键工序，则只交换快首快尾相连的两道工序；如果最后一个关键快包含两道以上关键工序，则只交换快首；如果它们只包含两道关键工序，那么只交换此两道工序。
3.3 更新和声记忆库
在和声库的更新操作中，解码变邻域后新和声，如果新和声优于和声库的最劣解，用新和声替换最劣和声，否则算法进入下一次循环操作。
改进和声搜索算法的步骤如下：
Step1：设置算法参数和声记忆库大小HMS、记忆库选择概率HMCR、微调概率的最大值PARmax、最小值PARmin、创作次数NI；个体长度tota ln umber。
Step2：初始化和声记忆库HM，采用双层编码的方式分别产生工序和机器的初始和声库。
Step3：产生一组新和声集合，包括工序码的新和声和机器码的新和声。
Step4：进行变异操作。产生一个区间（0，1）内的随机数rand，若rand
Step5：对产生的新和声进行变领域操作。
Step6：计算新和声集合的目标函数值，用新和声替换和声记忆库中目标值差的和声。
Step7：判断算法是否终止。当创作次数达到设定的最大次数NI时跳出循环，并输出最优结果。否则，转至Step3。
改进和声搜索算法的流程图如图4所示。
4 实验验证与分析
为了验证本文提出的改进和声变邻域搜索算法对问题求解的有效性，选取的算法测试对象分别为，4×6，8×8，10×10，和Brandimarte提出的10个实例。改进和声算法采用MATLAB R2016编程，程序在环境为Interl（R） Core（TM）i-5200U CPU@2.20，主频2.20GHz，内存为4GB个人电脑上运行。设置和声记忆库大小HMS=100，和声记忆库微调概率PAR为0.3，迭代次数为200，连续运行10次。
表1给出了该算法与Chen[7]和Pezzella[8]以及和标准HS算法（未改进的HS算法）对比结果，在表1中第一栏是问题，第二栏中n为工件数，m为机器数，T0为工件的总工序数，Flex.表示工序可选择的加工机器的平均数，LB和UB分别为目前为止文献中求得的最优上限和最优下限。
从表1可以看出，对于15个测试结果，改进和声算法取得了较好的测试结果。改进和声算法与Chen的GA相比有10个问题取得了更优或相同的最优结果，与文献[8]相比有9个相同的最优结果，与标准和声算法相比有12个问题取得了更优解。从改进和声算法与其它算法比较，显示了改进的和声算法求解FJSP的有效性。
在测试实例中，改进和声算法对于总工序数较小的小规模的FJSP上，都能取得较优解，而在较大规模的FJSP上，所求最优解效果差一点，主要原因在于当规模变大时，优良信息难以稳定的保存下去，构造优良和声的能力变差。（图5）
5 总结与展望
本文对新和声的产生方式进行了改进，同时为了提高算法的局部搜索性能，对产生的新和声进行变邻域操作，提出了一种改进和声变邻域搜索算法来求解柔性作业车间调度问题。最后用不同规模的实验对改进算法进行了对比和验证，结果表明相比于标准和声搜索算法，改进算法的局部搜索效果得到了提升，且结果的整体性能优于对比算法的结果。将改进和声算法的结果与其他算法的结果相比可看出该改进算法在解决柔性作业车间调度问题方面具有可操作性。今后将进一步探究本文提出的改进和声变邻域搜索算法的求解效果，并将其运用于求解组合优化问题。
参考文献：
[1]张国辉，高亮，李培根，张超勇.改进遗传算法求解柔性作业车间调度问题[J].机械工程学报，2009，45（07）：145-151.
[2]孔飞，吴定会，纪志成.基于双层粒子群优化算法的柔性作业车间调度优化[J].计算机应用，2015，35（2）：476-480.
[3]张于贤，丁修坤，薛殿春，王晓婷，程书瑞.基于记忆曲线模型的蚁群算法在柔性作业车间的调度优化[J].现代制造工程，2017（11）：105-109.
[4]Geem ZW，Kim JH，Loganathan GV.A new heuristic optimization algorithm： harmony search.Simulation[J].2001，76（2）： 60-68.
[5]王勇臻，陈燕，张金松.用于求解旅行商问题的多策略离散型和声搜索算法[J].华南理工大学学报（自然科学版），2016，44（01）：131-138.
[6]刘乐.单机最大延迟重调度的和声变邻域搜索算法[J].计算机集成制造系统，2016，22（08）：1977-1991.
[7]Chen H ， Ihlow J ， Lehmann C .A Genetic Algorithm for Flexible Job-Shop Scheduling[R].IEEE International Conference on Robotics and Automation .Detr-oit ， 1999 ：1120-1125.
[8]Pezzella F，Morganti G，Ciaschetti G.A Hybrid Genetic and Variable Neighborhood Descent Algorithm for Flexible Job Shop Scheduling Problems[J].Computers & Operations Reseach，2008，35（9）：2892-2907.
