基于遗传算法的模具电极调度问题求解

2022-04-29夏琴香李凯马骏程秀全肖刚锋

华南理工大学学报（自然科学版） 2022年3期

夏琴香李凯马骏程秀全肖刚锋

(1.华南理工大学机械与汽车工程学院，广东广州 510640；2.珠海格力精密模具有限公司，广东珠海 519070； 3.广州民航职业技术学院飞机维修工程学院，广东广州 510403)

模具制造业广泛使用电火花(EDM)加工技术对型腔形状复杂的模具零件进行加工，电极经数控加工(CNC)后进入到EDM车间对模具零件进行放电加工，电极的生产将直接影响模具的制造周期[1]。由于模具属于典型的单件小批量产品，生产按照订单进行组织，模具零件到达EDM车间的时间并不具有连续性，且一套模具往往对应几十个电极，所需电极数量庞大，协作关系复杂，因此电极的生产调度任务复杂艰巨。

传统的模具电极调度人工参与度高，严重依赖个人经验，不可避免地出现电极未完成CNC加工，从而不能按时到达EDM单元耽误模具零件加工，以及模具零件还没有到达，而大量电极囤积在EDM车间的现象，严重影响模具零件的交货期，企业资源和生产能力也无法充分发挥和利用。因此，有效利用生产资源，制定电极生产调度方案，对保证模具按时交货和提高企业生产竞争力有重要意义。目前针对模具电极调度问题，孙吴胜等[2]将EDM阶段电极和内模的协同加工描述为后工序成组约束，以拖期量最小化为目标建立了成组约束下的模具电极调度模型，并提出了基于加工时间最长(LPT)和加工时间最短(SPT)优先规则的启发式调度算法进行求解；Li等[3]进一步归纳了后成组约束，且基于交货期最早(EDD)和LPT优先规则提出了一种名为EL算法。以上研究中的模具电极调度模型的CNC阶段仅限于单个电极加工，但目前模具企业为缩短电极加工时间，常在CNC阶段对电极进行批处理加工，上述算法难以适应现代化生产模式的要求。

文中针对以上问题，建立了批处理下的模具电极调度模型，根据相关性原则设计相关性优先分批算法以解决批处理问题，利用遗传算法求解批调度问题，并设计相关算例验证了该算法的有效性。

1 问题描述

1.1 模具电极生产流程

模具电极的生产流程包含CNC和EDM两个阶段[4]。接到模具订单后，根据模具零件的工艺设计产生电极生产任务，电极经过设计、编程并完成CNC工序后，进入到EDM车间作为模具零件加工的刀具进行放电加工。其中，CNC阶段多个电极随机组合，同时在批处理机上并行加工，具有批处理特征；EDM阶段与同一模具零件对应的所有电极在同一台机器上串行加工，即一次只能有一个电极放电，且为提高加工精度，模具零件在所有电极放电完成后才能下机。

针对模具电极在EDM阶段的生产特点，将多个电极加工一个模具零件的过程归纳为相关性特征：若模具零件在某一阶段需要若干个电极进行协同加工，称对应于同一个模具零件的电极具有相关性，具有相关性的电极需在同一台机器上加工，不相关的各电极组在加工过程中遵循不可抢占性。

模具电极调度问题即确定为电极在CNC和EMD阶段加工次序的优化问题。通过对加工次序的优化，使模具零件总拖期量最小；其中CNC阶段具有批处理特征、EDM阶段具有相关性特征，两阶段都具有多台并行机同时进行加工(如图1所示)。

图1 模具电极生产流程图

1.2 问题描述及数学模型

模具电极调度问题可视作柔性流水车间调度问题(HFSP)的扩展，HFSP最早由Johnson[5]在1954年发表的开创性论文里提出，在1978年被Garey等[6]证明为NP-hard问题，其特点是工件在流水线上进行多个阶段的加工，其中至少有一个阶段存在并行机。考虑到模具电极调度问题还存在批处理和相关性特征，将模具电极调度问题记为BCHFSP。

将电极记为a类工件、模具零件记为b类工件，BCHFSP问题描述为：有p个a类工件和q个b类工件，a类工件ai在流水线上进行CNC和EDM两个阶段的加工，第1阶段(CNC阶段)有m1台机器，第2阶段(EDM阶段)有m2台机器。各阶段有且只有一道工序，可以在任意一台机器上加工；且第1阶段具有批处理特征，第2阶段具有相关性特征；a类工件在零时刻到达，b类工件分批等间隔到达。工件在加工过程中遵循不可抢占性，每个工件只能被一台机器所加工，在满足生产工艺约束条件下寻找一种调度策略，使所确定生产批量和相应加工顺序下的b类工件总拖期量最小。

BCHFSP的数学模型如下(模型相关参数及其定义见表1)：

(1)

(2)

(3)

(y=1,2,…,p)

(4)

(y=1,2,…,p)

(5)

Rai(d+1)=Faid=Said+Paid

(6)

(i=1,2,…，p;d=1,2)

Rbj2≥Aj,j=1,2,…,q

(7)

(8)

式(1)表示问题的目标函数，ξ为某一调度方案；约束(2)表示工件bj的拖期量等于最后一个与bj协同加工工件的完工时刻减去bj的交货期；约束(3)表示第1阶段为批处理加工；约束(4)表示第2阶段具有相关性的工件在同一机器上加工；约束(5)表示批处理加工时间为各电极加工时间之和；约束(6)表示同一阶段工件加工就绪时刻、完工时刻和开始加工时刻的关系；约束(7)表示工件bj的加工就绪时刻大于等于到达时刻；约束(8)表示同一批次工件占用的总空间不能超过最大批处理容量。

1.3 数学模型的理论分析

由于不相关的各电极组在加工过程中遵循不可抢占性，那么当相关电极在第2阶段的加工不连续时，将产生机器空闲等待时间，使当前工件以及后续工件的拖期量增加[3]。为获得模型中目标函数(1)的最优解，对如何实现加工连续性进行理论分析。假设一调度方案ξ已经确定a类工件的Rauj2，则有以下结论：

表1 模具电极调度模型参数及定义

①存在最小的b类工件Rbj2使具有相关性的a类工件在EDM阶段的加工连续;

②最小Rbj2可以被找到。

对于结论②，令Rbj2=Aj，通过Rauj2和Pauj2计算并判断加工过程是否中断，若中断则令Rbj2增加单位时间，因最小Rbj2存在且区间固定，只要重复以上判断必能找到最小Rbj2使加工连续，结论②得证。当加工连续时，b类工件的加工时间可按式(9)计算：

(9)

2 模具电极调度算法

2.1 算法总体框架

根据上述调度模型，将模具电极调度问题的求解分解为两个层次：第1层考虑CNC阶段的批处理特征，建立分批优先规则对a类工件进行分批，以及确定批次本身加工次序；第2层考虑EMD阶段的相关性特征，需要确定Rbj2使相关电极加工连续，并确定各相关电极组加工次序。

目前调度算法主要为启发式算法和智能优化算法[7]，Dios等[8]基于NEH法求解了最小完工时间下的可跳过HFSP；Tasgetiren等[9]提出一种迭代贪婪算法，求解最小拖期量的带阻塞HFSP；Engin等[10]基于交叉和变异机制的混合蚁群算法求解了无等待流水车间调度问题。由于启发式算法依赖于建立的优先规则，面对大规模的模具电极调度时规则匹配速度较慢，因此考虑使用智能优化方法。遗传算法(GA)是基于“适者生存”的一种高度并行、随机和自适应优化算法，自Davis[11]将其引入到FSP中，GA的隐含并行性和全局解空间搜索使其在大规模调度领域展现出了极强的适应性和生命力[12]。文中以GA算法框架为基础，配合分批策略以及GA改进策略完成模具电极两层调度，算法总体框架如图2所示。

图2 模具电极调度算法框架

2.2 电极分批算法

根据模具电极加工的特点，CNC阶段的电极分批考虑两个原则[4]：第1个是同一批电极不能超过最大批处理容量；第2个考虑电极相关性特征，模具零件在EDM过程中遵循不可抢占性，即所有对应电极加工完才能进行下一模具零件的加工，若相关电极进入第2阶段时不连续，会不可避免地增加等待时间，因此将具有相关性的电极优先划分到同一批次，记为相关性优先(CF)。

CF分批策略为：①按相关性对所有参与调度的电极进行初步分组；②对于各组电极，选择第一个电极加入批次，并按顺序往批次中添加电极，若达到最大批处理容量，则下一电极添加到新的批次；③各组剩余电极任意组合，同样不能超过最大批处理容量。

2.3 电极批调度遗传算法

2.3.1 配种策略

传统GA尽管在一定条件下具有全局收敛性，但选择、交叉、变异等遗传操作是在概率意义下随机进行的，在一定程度上会出现退化及长时间陷入局部最优的情况，另一方面相较于GA强大的全局搜索能力，其局部搜索能力弱[13]。针对以上问题，文中从动物配种现象得到启发，提出一种优化策略。

动物配种是指挑选具有优秀基因的雄性，与其余雌性进行配种以期产生优秀个体的过程，以人工干预的方式增加了优秀个体出现的概率。文中将这一过程插入到遗传算法中，提出一种基于动物配种的策略(如图2中虚线框所示)，在此基础上，对传统遗传GA进行改进，改进后的遗传算法记为Breed-GA。

具体步骤如下：

步骤1按GA进行迭代，令停滞代数S=0，并设定临界停滞代数Smax和邻域搜索轮数k；

步骤2种群适应度计算，并判断进化停滞状态，即本次与上一轮迭代最优解值是否相同，若相同则S=S+1，否则继续迭代；

步骤3若S>Smax，则进行配种:取出当前最优解，按随机交换、中心对称、向前插入、向后插入4个邻域动作(如图3所示)为一轮进行k轮邻域搜索，选取适应度最高的染色体作为种染色体，将种染色体与种群中每一条染色体配种产生两个子代，比较该染色体与子代适应度，取最高者替代该染色体，S=0，返回步骤2，否则继续迭代；

图3 邻域搜索动作

步骤4每一次迭代完成都进行个体评价，若满足停止准则则输出最优解，否则重复以上步骤。

2.3.2 编码与解码

用所有批次的置换排列作为算法的染色体编码方式，染色体基因为批次编号，长度等于批次数量。批次编号在染色体中的位置表示该批次进入流水线的顺序,譬如，nB=5时，染色体[2 3 5 1 4]表示所有批次进入流水线的顺序为“批次2—批次3—批次5—批次1—批次4”。基于染色体转化后的有序操作表，通过一定的启发式方法进行解码，就可以产生调度方案。

解码过程分为两个阶段，第1阶段的解码步骤如下。

(10)

步骤2将染色体中最靠前的未分配批次分配给释放时刻最早的机器；

步骤3判断是否所有批次都完成了机器分配。若已完成，则结束循环，进入第2阶段解码，否则转到步骤1；

第2阶段的解码步骤为

步骤1第1阶段解码完成并获得a类工件的Rauj2，根据模型理论分析计算所有b类工件的加工就绪时刻Rbj2，按递增排序，按式(9)计算b类工件的加工时间；

步骤2根据下式更新第2阶段所有可用机器的释放时刻，按从早到晚排序：

(11)

步骤3将加工就绪时刻最早且未分配的b类工件对应的所有a类工件分配给释放时刻最早的机器，加工就绪时刻相同则选加工时间长的工件，仍不能确定则随机选取，即优先级为加工就绪时刻→加工时间→随机。由于保证了加工连续性，故a类工件可按任意顺序加工；

步骤4判断是否所有a类工件都完成了机器分配。若已完成，则结束循环，否则转到步骤2。

2.3.3 遗传操作

适应度函数取模型目标函数，适应度值越小适应度越高；选择采用轮盘赌方法，适应度值越小每条染色体被选取的概率越大；交叉操作采用POX交叉法；变异操作采用位置变异法。

3 算例仿真及结果分析

3.1 仿真算例设计

采用分割试验思想[14]设计本文的仿真数据集，算例参数如下：b类工件交货期、b类工件数量、协作工件数量、a类工件占用批处理空间、最大批处理容量、工件加工时间、工件到达时间、机器数量，各参数设置如表2所示。

表2 算例参数

其中b类工件交货期采用TWK[15]方法：

(12)

式中:宽裕度系数取1和2，分别代表紧、松交货期。U代表取范围内均匀离散分布；Vi矩阵第1行为占用批处理空间，第2行为相应取值概率；工件到达时间指b类工件到达时间Aj，按起始时间/批次大小/间隔时间取10/5/5；(m1,m2)分别代表第1阶段和第2阶段的机器数量。

3.2 仿真实验及结果分析

按3.1算例设计方法，选取主要参数：b类工件数量、最大批处理容量、机器数量以及不同的交货期宽裕度系数得到参数配置四元组：{q,Vmax,(m1,m2),k}。通过四元组中每一个参数值的不同设置，得到24种仿真算例并对文中提出的Breed-GA和传统GA进行测试比较，目的包括：(1)验证算法针对不同规模问题的有效性；(2)验证配种策略能够有效解决传统GA进化停滞时间过长以及局部搜索能力弱的问题。所有算法的参数设置均为种群规模Psize=50，交叉概率Pc=0.6，变异概率Pm=0.001，停止准则为最大迭代次数imax=100，临界停滞代数5，邻域搜索轮数k=10，采用保优策略。仿真测试软件为Matlab2019a，处理器为Intel(R)Core(TM)i5-6300HQ，运存RAM8GB。

表3为按每种四元组配置下分别按Breed-GA和GA进行10次仿真试验得到的最优适应度平均值及其进化率。可以看出，文中提出的RF分批算法和Breed-GA对不同规模的BCHFSP均有效，且与传统GA相比，Breed-GA求解得到的拖期量进化率最高达到16.71%。在其它条件相同时，q=40的进化率相较于q=20明显提升，这说明随着问题规模的扩大，Breed-GA的优势也不断扩大。

表3 总拖期量

图4为算法进化迭代曲线，横坐标为迭代次数，纵坐标为总拖期量。图中总拖期量随着迭代次数的增加，从21 411降到17 162，即算法有效减小了模具总拖期量，虚线框表明GA在前期收敛时处于长时间的进化停滞状态，散状分布点则说明配种策略在长时间停滞时发挥了作用，增强了GA的局部搜索能力，跳出了局部最优状态，进而提高整体迭代速度和迭代质量。

图4 算法进化迭代曲线

图5为最优解分布图，相同条件下每种算法循环仿真10次，记录每一次循环下的最优解。各点的离散程度表明Breed-GA的解较GA的解稳定，这是由于配种策略加快了前期迭代速度，增加了相同最大迭代次数下算法收敛到最优解的概率。

图5 最优解分布图

图6对比了不同算例参数配置下的算法平均运行时间，右侧为对应配置信息，如“204331”表示{q=20,Vmax=4,(m1,m2)=(3,3),k=1}，以此类推。结果显示，由于配种操作影响，经配种策略改进的遗传算法运行时间比传统遗传算法长1～2 s，但所耗时间均在可接受范围内。q从20增加到40时，运行时间从10 s增加到24 s，其余参数影响不明显，说明算法运行时间主要和参与调度的工件数量有关。

图7为一组小规模案例下的最终调度方案甘特图，图中横轴为加工时间，纵轴为机器编号，“B”表示批次，“b”表示b类工件，“1，2，…，10”为各电极编号，具体案例信息见表4和表5，机器配置为(2,2)。甘特图显示，CNC阶段批次1和5在CNC1机床上加工，批次2、4、3依次在CNC2机床上加工，EDM阶段工件1、4和相关电极在EDM1机床上加工，工件2、3和相关电极在EDM2机床上加工。