基于改进蛙跳算法的离散制造车间调度模型研究

王 朝，潘顺发，方 博，周 林，张海涛，唐红涛

(武汉理工大学 机电工程学院，湖北 武汉 430070)

机械行业中铸件占机械产品总产量的80%，铸造行业是离散制造企业的基础行业[1]。铸造行业推动自身信息化进程，实现铸造行业整体的智能化、自动化、信息化水平是未来铸造行业发展面临的关键问题[2]。大部分铸件的生产模式是砂型铸造。砂型铸造分为混砂、造型、制芯、熔炼和清理5道工序。考虑铸件造型的复杂性，铸造企业普遍采用人工班组进行造型和制芯。混砂和熔炼工序是铸造的主要工序，某批次铸件订单任务确定投产后，混砂在造型之前加工，熔炼在限定时间段内独立加工。Dos等[3]探讨熔炼炉在单阶段内熔炼多少合金的问题，采用改进元启发算法求解，计算结果在自动化铸造企业中得到了应用和验证。对铸造工艺剖析，将其转变成经典柔性流水车间调度优化问题。柔性流水车间调度问题作为一种典型的优化组合问题，一般通过智能算法用于求解该类问题。张其亮等[4]采用一种混合粒子群算法解决不考虑工件运输条件约束的柔性流水车间调度问题，首先采用粒子群算法解决机器资源调度，然后确定工件加工顺序，最终通过平移计算差值算法求解目标函数值。毕孝儒等[5]采用一种新型人工蜂群算法，采用全局最优蜜源搜索策略强化改良算法的探索能力,避免算法出现陷入局部最优现象。笔者结合国内砂型铸造车间单件小批量模式下铸件的实际生产环境，针对砂型铸造的熔炼工序具有多约束的特征，提出熔炼工序弱化机制，建立以总完工时间最小为目标的柔性流水车间调度模型。采用改进蛙跳算法(suffled frog leaping algorithm-simulated annealing,SFLA-SA)求解模型，通过反向学习策略改善初始种群，改进的蛙跳算法中嵌入具有3种邻域结构的模拟退火搜索局部搜索以提高算法局部搜索能力。最后将模型应用于某铸造企业以检验模型的有效性，与蛙跳算法SFLA(suffled frog leaping algorithm)，遗传算法GA(genetic algorithm)和粒子种群算法PSO(particle swarm optimization)算法对比，表明改进蛙跳算法(SFLA-SA)的有效性和优越性。

1 问题描述

1.1 典型砂型铸造工艺流程分析

典型砂型铸造工艺包括铸型准备、铸造金属的熔化与浇注、铸件处理和检验3大部分。砂型铸造加工车工种大致可以分为2类，一类是机械加工，另一类是非机械加工。某典型砂铸企业生产流程如图 1所示。砂型铸造工艺路线分为6道主要工序，即造型、制芯、熔炼、浇注、落砂和清理。在砂型铸件的生产过程中，造型和制芯工序一般由人工班组进行操作，根据铸件实际生产特点，将造型和制芯作为一道工序。

图1 典型砂型铸件生产工艺流程图

1.2 熔炼工序弱化机制

熔炼工序不同于铸件其他工序，不存在对单个铸件单独熔炼铁水的操作，某批次铸件的熔炼工序作为同一道工序即公共工序。当某批次生产铸件数量确定时，根据铸件工艺出品率等相关参数可确定熔炼工序所需熔炼铁水的量，如式(1)所示。

(1)

式中：Mt为该批次生产中所需熔炼铁水的总重量；mr为第r个铸件的重量；kg为工艺出品率；s为该批次所需生产铸件的数量。

在熔炼设备和熔炼工艺水平稳定的前提下，熔炼工序所需熔炼铁水量的确定，熔炼工序所需时间确定。砂型铸件生产中熔炼工序加工时间较长，熔炼炉耗电量占铸件生产能耗较大部分。为减少能耗，熔炼工序开始时间在晚上8点以后才符合实际生产。针对熔炼工序一般在限定时间段内独立进行，下芯合箱工序对熔炼工序不存在限制约束，熔炼工序对浇注工序存在限制约束的特点提出熔炼工序弱化机制，即将熔炼工序作为砂型铸造生产中工件的下芯合箱工序和浇注工序之间特定时间区间内的固定调整时间段。

2 柔性砂型铸造流水车间调度模型建立

经典柔性流水车间调度(flexible foow shop scheduling problem,FFSP)描述为：在m个资源和n个工件的生产环境下，所有的工件必须经过多道工序加工，各道工序可选加工资源设备集合已知，至少多于一道工序存在多个可选加工资源设备，这些资源的性能可相同也可不同。在传统的FFSP问题研究基础上，考虑砂型铸造实际生产状况后提出熔炼工序弱化机制。该砂型铸造车间调度模型存在以下假设：①初始时刻，所有资源均可用，所有铸件的第一道工序均可加工；②任意工序只能选定某一种资源进行加工，且加工过程连续不间断；③任意一种资源在某一时刻只能对铸件的某道工序单独加工，每种资源前可容纳无限量的待加工工件；④同一铸件不同工序间存在加工顺序限制，多个铸件之间不存在加工顺序限制机制；⑤铸件任意工序的加工时间包含有效加工时间和调整时间两部分；⑥工序移动时间忽略；⑦铸件不考虑成批运输情况。

柔性砂型铸造流水车间调度的数学模型描述和相关概念的定义为：n为待加工铸件数量；J为待加工铸件集合，J={Ji,1≤i≤n}；Ji为第i个加工铸件(i=1,2,3,…,n)；m为铸件加工资源总数；M为铸件加工资源集合，M={Mh,1≤h≤m}；Mh为第h个加工资源(h=1,2,3,…,m)；j为工序序号；Oij为第i个铸件的第j道工序；Oijh为工序Oij在加工资源h上加工；tijh为工序Oij在加工资源h上的有效加工时间；Biq为铸件i的下芯合箱工序的完工时间；Jiq为铸件i的下芯合箱工序的固定休整时间；Mend为该批次铸件的公共工序即熔炼工序完工时间；Aij为铸件i的第j道工序的起始加工时刻；Bij为铸件i的第j道工序的加工结束时刻；Bijh为工序Oij在机器h上最早完工时刻；Bi(j-1)l为工序Oi(j-1)在机器l上最早完工时刻；Bi′j′h为机器h上加工工序Oij的相邻上一道工序Oi′j′在机器h上最早完工时刻；Ci为第i个铸件的最后一道工序的完工时刻；Cmax为最大完工时间。该调度模型的决策变量如下，xijh为0-1变量，工序Oij在加工资源h上加工则xijh=1，否则为0。Rijgh为0-1变量，工序Oij先于工序Ogh在加工资源h上加工则Rijgh=1，否则为0。考虑最小化某批次铸件的最大完工时间，目标函数和约束限制条件如下：

minf1=max(Ci)i=1,2,…,n

(2)

(3)

(4)

(5)

Ai(j+1)≥Bi,j

(6)

(7)

Aijh≥Bi′j′h

(8)

(9)

其中式(2)为模型的目标函数，即最小铸件最大完工时间。式(3)中Ci为第i个铸件的完工时间。式(4)中Delijh为安排在加工资源h上的工序Iij因机器资源约束而延迟的时间。式(5)中TX为第i个铸件由于熔炼工序弱化机制而延迟的时间。式(6)为同一种铸件的不同工序的加工顺序约束限制机理，表明铸件的某道工序只能在前一道工序加工完成后才可开始加工。式(7)为工序的完工时间限制条件，在柔性流水车间调度中，工序的加工过程不可以被中断，也就是说工序完工时间应为工序的起始时间和其在所选择资源上加工时间的和。式(8) 限制了同一时刻内每个资源设备只能对铸件某道工序进行加工。式(9)为铸件的任意一道工序存在多个可选加工资源，但其任意一道工序只能被可选加工资源集中某个资源单独加工。

3 基于改进蛙跳算法的调度模型求解

基本蛙跳算法(suffled frog leaping algorithm，SFLA)是一种全新的生物进化算法，其受到自然界寻找食物的青蛙种群启示。SFLA参数简单，算法计算效率高、全局寻优能力强[6]。目前为止蛙跳算法已经被应用到很多优化问题中并取得了良好的效果。模拟退火算法(simulated annnealing,SA)是一种全局最优的串行结构的优化算法，其赋予搜索过程采用一种时变概率突跳性机制，可以有效的避免SFLA陷入局部最优[7]。笔者在基于基本蛙跳算法的基础上采用一种改进的蛙跳算法(SFLA-SA)用于求解柔性砂型铸造流水车间调度问题。

3.1 染色体编码与解码

参考文献[8]采用双层编码，一层基于加工工序，给铸件的所有工序确定加工顺序，一层基于可选机器，给工序选择可选加工机器。各层编码长度均为工序总数，编码取值范围为[0,1]。表1为3个铸件在3台机器上加工的柔性调度问题示例。3个铸件的总工序数为8，则两层编码的长度均为8。随机给定以下编码：工序层编码为[0.07,0.88,0.73,0.53,0.96,0.84,0.81,0.66]，机器层编码为[0.24,0.83,0.28,0.17,0.72,0.53,0.45,0.29]。相应的第一层解码过程如下：将第一层解码结果按其数值升序排列，令最小的3处数值为1，数值排在第4和5位处编码设置为2，令最大的3处数值为3，并按照各个工件的加工顺序来确定所有工序排列规则，工序层编码结果如图2所示。机器层编码依据工序层编码的解码结果采用基于轮盘赌选择算子的解码方法，在各个工序下面的第二层编码数值用于确定该工序对应的加工机器。例如，O1,1对应的编码数值为0.24，该数值表示确定进行工序O1,1加工的机器编号。加工机器的选择采用轮盘赌模型，由参数设置可知，O1,1工序可在机器1、机器2和机器3上进行加工，因而当编码数值在[0,1/3) 上时，O1,1由机器1加工，当编码数值在[1/3,2/3)上时，O1,1由机器2加工，当编码数值在[2/3,1]上时，O1,1由机器3加工。由于0.24在[0,1/3)上，因此O1,1由机器1加工。机器层编码解码结果见图3所示。图4为两层编码对应的解码结果的甘特图。

表1 示例铸件信息

图2 工序层编码解码示意图

图3 机器层编码解码示意图

图4 双层编码解码对应甘特示意图

3.2 种群初始化

笔者参考文献[9],改进蛙跳算法采用反向学习构造初始种群解。基本思路为：首先随机生成N个初始种群解。随后针对每个随机解构建其反向解得到N个反向解。最后在2N个初始解中选择较优的N个解组成初始种群。

3.3 基于模拟退火算法的局部搜索策略

标准SFLA算法种群的全局最优解和各子种群的最优解的优劣质量对种群进化具有重要影响。改进蛙跳算法采用模拟退火算法来对各子种群的群内最优解进局部搜索，以达到提高各子种群的群内最优解和全局最优解的质量。在SFLA-SA中，采用SA对子种群群内最优解局部搜索，由当前解生成变异解的过程采用交换、翻转和插入3种变异算子[10]。结合工序层编码示意图对3种变异叙述如下：

(1)交换变异。随机交换当前解上两处位置上的编码，如图5所示，选择待变异解编码的第3和第6位置交换。

图5 交换变异

(2)翻转变异。随机翻转当前解上的两处位置间的编码，如图6所示，选择待变异解第3和第7编码处位置，翻转变异。

图6 翻转变异

(3)插入变异。随机将某位置上的编码数值插入到另一位置之前，如图7所示，将待变异解第6位置处编码插到位置2之前。

图7 插入变异

3.4 改进蛙跳算法的基本流程

Step 1：SFLA算法与SA局部搜索算法的基本参数设置。初始种群规模为N；子种群数目为m；子种群个体数为n；种群迭代次数为Maxit；初始温度为T0；内循环次数为L；温度退化率为ps。

Step 2：随机生成N个个体，采用反向学习法得N个个体，计算全部个体适应度值，按降序排列选择较优的N个个体构建初始种群P0，令t=0; 随机选择个体作为全局最优解gbest。

Step 3：降序排序初始种群适应度值，将N个个体均匀分配在m个子种群中。

Step 4：若t

Step 5：采用SA算法对各个子种群中的最优解进行局部搜索，更新各个子种群的最优解。

Step 6：SFLA-SA算法采用均匀抽样选择子种群的子集并更新子集中最劣解。

Step 7：令t=t+1并更新种群的全局最优解gbest，转Step 5。

改进SFLA-SA算法的基本流程如图8所示。

图8 改进蛙跳算法基本流程图

4 案例应用与分析

4.1 案例描述

以某砂型铸造企业为例验证模型以及算法的有效性，该企业客户订单多为机床类零部件，铸件材质单一。对其某个周期内的订单进行调度研究,该批铸件开始加工时间为早8点，该周期铸件熔炼公共工序起始时刻为当天晚8点，所需时间为5 h。该周期内一共有6个铸件单件需要铸造生产且属于同一材质。该周期实际生产数据如表2所示，各工序的可调度资源一共有14个，表2中可用资源集是铸件该道工序可以加工的资源序号集合，加工时间集与可用资源集的顺序相对应。

4.2 案例求解与分析

算法在Windows 10系统、CPU主频四核2.3 GHz、运行内存8 GB的计算机中运行，软件为MATLAB R2016。选取标准蛙跳算法(SFLA)、传统遗传算法(GA)以及文献[11]中所提粒子群算法(PSO)进行对比, 验证SFLA-SA对模型求解的有效性及优越性。其中SFLA与SFLA-SA在参数上的选取均一致，SFLA采取随机种群初始化，且迭代过程未采取局部搜索，其他算子均与SFLA-SA一致。本文算法参数采用正交实验设计法进行选取，经过组合实验得最优参数：子种群数目为10，局部搜索次数为10，子种群数目为20，迭代次数MaxIt为400。GA染色体解码方案和PSO粒子解码方案及算法流程与文献[11]一致，种群大小与迭代次数均和SFLA-SA相同，其余参数采用文献[11]中建议参数。四种算法最优迭代曲线如图9所示，由于SFLA-SA采用了反向学习规则构建初始种群，初始种群质量相比PSO、GA和SFLA有较大提升，同时SA局部搜索算子使SFLA-SA能跳出局部陷阱。

表2 某铸造企业某周期生产铸件信息

图9 四种算法最优解迭代曲线对比

为验证SFLA-SA的稳定性，分别使用4种算法求解30次，算法稳定性如表3所示。根据分析可知，PSO表现最差。SFLA-SA表现最优，但迭代过程加入SA导致其运行速度稍慢，综合分析可知SFLA-SA寻优能力最强。图10为SFLA-SA对模型求解30次所得最优解36.05对应的甘特图，图10中矩形代表铸件工序，矩形长度表示工序加工时间，符号表示工序信息，例如符号为O4,1表示4号铸件的第一道工序。

表3 算法稳定性分析

图10 改进蛙跳算法(SFLA-SA)最优解甘特图

5 结论

笔者构建了以总完工时间最小为目标的柔性砂型铸造流水车间调度模型。通过对某企业案例分析，验证所采用SFLA-SA求解模型的有效性和优越性，求解结果对砂型铸件的实际生产具有现实意义。