基于混合遗传算法的柔性作业车间调度优化

文/段明跃，三明学院机电工程学院

基于混合遗传算法的柔性作业车间调度优化

文/段明跃，三明学院机电工程学院

本文摘要：针对传统作业车间调度问题的模糊性，结合实际生产流程，提出柔性作业车间调度模型，加入了随机选定原则，在遗传算法原有的基础上优化。通过随机选定，并进行交叉与变异，避免了局部最优问题同时是算法结果更加精确，收敛速度增强。最后通过实例仿真验证了算法的有效性。

混合遗传算法；多目标优化；柔性作业车间调度

就目前对调度问题的研究方法归纳来看，优化调度方法和启发式算法是目前最常见的方法。优化调度主要是从全局出发，考虑在各个调度约束条件下目标函数的最优解。这类方法由于模型的解析过于复杂，且实际计算中不一定能得到最优解，所以在调度问题上无法得到满意的答案。作业车间调度问题本质上是一个大范围的组合优化问题，而遗传算法本质上是一种并行的算法，与传统数学规划或算法相比搜索效率高，同时因为其采用的是随机搜索，能够克服局部最优问题，增大了算法的正确性。而且这类算法不需要很多的专业知识，所以实用范围广，可实现性高。

1 相关的问题假设

柔性作业车间调度主要是指在一个生产系统中，有一个需要加工完成的作业集，在这个加工集合中有个需要加工的零件，集合可以表示为。同时有一个加工机床集合,其中共有台机床可用，集合可以表示为,每一个需要加工的零件都需要经过若干加工工序才可以完成。目标函数为求得最大完工时间的最小值。

针对该模型进行相应的假设：

（1）每一台机床每次只能加工一个工件；

（2）每个工件在同一时刻只能在一台机床上加工；

（3）工件的加工过程是连续的，中途不能中断；

（4）在模型的初始时刻，所有工件都可以进行加工；

（5）工件的工艺流程是预先确定好的；

（6）每一种工序在机床上所需加工时间是确定好的；

2 模型变量定义

表1 模型变量定义表

3 基于混合遗传算法的FJSP优化

在加工过程中，工件的每一道工序都可以选择一台或多台机床进行加工，单一采用基于工序的遗传算法，在染色体的信息中无法表达出来，所以在原有算法的基础上进行优化，将工序信息与机床信息相融合，形成一个二维矩阵，增加了机床的信息。在这个二维矩阵中，第一行为加工工序信息，而第二行为加入机床序号的补充信息，工序与机床都用每个染色体上的基因进行编码。遗传算法存在过早收敛的问题，通过改进使其可以得到更加优秀的解。

将两种编码方式结合为一个二维矩阵，矩阵如下所示：

在矩阵(11)中，第一行表示所有加工工艺的序列，第二行表示每一道工序所对应的机床序号。

表2 一种柔性车间加工调度情况

表2是一个4个工件，3道工序，5台加工机床的加工调度情况，则以此为举例列写出相应的二维矩阵。假设（1,2,4,3,2,4,3,2,1,4,1）为该情况下的一种可行方案，根据上述编码方式可得到，

对应的操作和加工机床为：

步骤1 通过初始种群确定种群的规模大小，通过对时间取到将问题转化为求最大值问题，即适应度函数。构建一个概率模型，利用比例于个体的适应度概率决定子孙的遗传可行性。个体的概率选定后，产生随机数决定下一步操作。

步骤2 在概率P的作用下，随机的选择矩阵中第二行的机床中非空值，将其随机改变为0到工序范围的数。这样就可以得到同一工件同一步骤在不同机床上的信息。

步骤3 随机选取两个交叉点，然后将这两个基因的信息相互交换，搜索交叉完毕之后产生的新的基因序列，找出新增和遗失的工件号，并在染色体中随机筛选出多的基因，将其换为遗失的基因，则通过如此得到一个可行解。同时还需要保证原有染色体中的每道工序的相关信息不变。在变异过程中，在保证变异前后工件所可选择的机床是保持不变的，为了改进传统遗传算法，采用插入的变异方式，即在染色体中随机选择一个变异位置，然后将点插入在此位置之前。若本次最优解使得适应度函数大于历代值则替换最优解，继续下一个随机数组进行计算。

步骤4 输出最佳加工路线，算法结束。

[1]王万良, 赵澄, 熊婧,等. 基于改进蚁群算法的柔性作业车间调度问题的求解方法[J]. 系统仿真学报, 2008, 20(16):4326-4329.

[2]王小蓉, 李蓓智, 周亚勤,等. 基于混合遗传算法的柔性作业车间调度研究[J]. 现代制造工程, 2015(5):39-42.

[3]张腾飞, 马跃, 李力,等. 柔性作业车间调度问题的改进遗传算法[J].小型微型计算机系统, 2017, 38(1):129-132.