基于混合并行混沌优化算法的铸造生产线两阶段协同调度

袁小芳，杨育辉，谭伟华，尹柏鑫

（1.湖南大学 电气与信息工程学院，湖南 长沙 410082；2.湖南大学机器人视觉感知与控制技术国家工程实验室，湖南 长沙 410082）

铸造行业作为制造业的基础行业，其发展水平是衡量一个国家整体工业水平的重要因素.中国铸件制造总体以低端铸件为主，铸造企业多为小微企业，主要依靠个人经验确定生产计划，导致铸件生产效率较低[1].迫切需要更合理的生产调度策略以降低企业资源消耗、提高生产效率、增强企业竞争力.

按生产铸件方法分类，铸造可分为砂型铸造和特种铸造，典型的砂型铸造生产线生产流程如图1所示，计划生产系统从订单池获得订单之后给出生产计划，整个铸件生产过程分为两个阶段，第一阶段基于砂箱和熔炉对铸件进行批次加工，熔炼炉根据批次熔炼合金并注入造型机造好的模具当中，经过冷却，铸件从模具中取出，生产加工过程进入第二阶段进行柔性单件生产加工，铸件单件根据生产工艺进行后续加工.所有铸件以相同的工艺顺序通过第一阶段批次加工后进行各自第二阶段的生产加工操作.

图1 典型砂型铸造生产线生产流程Fig.1 Production flow of typical sand mold casting production line

针对铸造生产线生产过程当中的批次生产调度问题，唐江涛等[2]对铸造当中的批量造型计划进行了研究.胡常伟等[3]针对任务重量不一致的同型熔炼炉批调度问题进行了研究.Francisco 等[4]将中型铸造企业中的资源调度建模为项目调度问题并提出了一个元启发式算法进行求解.Gauri[5]对有不同材质的铸件进行了熔炼浇注的批次计划研究.针对铸造生产线全流程优化调度问题的研究，Tang[6]与Li[7]等将铸造生产线的加工流程视为混合流水车间调度问题进行了研究.QIN 等[8]针对实际生产当中的特殊约束条件，建立了忽略批调度过程的铸造生产线优化调度模型进行求解.陈荣[9]将铸造生产过程建立为两阶段的生产调度模型，并提出了相应的求解方法.然而，目前针对铸造生产线全流程优化调度问题的研究大都没有考虑批次加工与机加工协同调度的问题，忽略铸造生产两阶段耦合关系求得的解往往不是问题的最优解，因此，对铸造生产线全流程优化调度问题的研究具有重要意义.

Maes[10]与刘蓉[11]等的研究证明铸造生产线优化调度问题属于NP-hard 问题，传统求解方法如分支定界法等求解困难.混沌优化算法是一种利用混沌运动的遍历性来搜索最优解的启发式算法，具有优秀的全局寻优能力与跳出局部最优的能力[12-13].针对混沌优化算法对初始值敏感的问题，并行混沌优化算法（parallel chaos optimization algorithm，PCOA）采取多个混沌变量映射的措施，一个优化变量对应多个混沌变量，混沌变量独立搜索，并行变量的最优值为需要的优化解，提高了算法的搜索效率[14].

本文考虑实际铸件加工生产环境，建立了铸造生产线全流程优化调度模型，并设计了一种混合并行混沌优化算法（Hybrid parallel chaos optimization algorithm，HPCOA）对模型进行求解.算法设计了独特的编码解码机制和分批策略，并引入交叉变异操作，提高算法迭代过程中解集的多样性与算法的开发能力；然后引入变邻域搜索算法进行局部搜索，采用针对关键路径的四种邻域结构，避免了搜索的盲目性，提高了搜索效率.本文的创新在于对目前研究较少的铸造生产过程中批次加工与机加工协同调度问题建立了优化调度模型并进行了研究.算法创新上，并行混沌搜索与交叉变异算子的结合使算法具有较好的全局搜索性能.变邻域搜索算子的引入增强了算法的局部搜索能力.编码解码机制的设计使得算法适用于求解离散调度问题.最后通过对比实验验证了算法的有效性.

1 问题描述与模型

1.1 问题描述

假设铸造生产线造型机的造型能力足够大，则可认为熔炼过程是生产瓶颈，假设企业的订单池足够大，每次计划生产系统获得具有相同材质的订单，从而使铸件生产线优化调度问题简化为考虑铸件质量约束的单机优化问题[3，15].由于技术要求，铸件不能在熔炼和浇注工序之间等待，因此本文将熔炼浇铸过程视为铸件的第一道工序.

本文考虑的优化问题定义为：针对以熔炼过程为生产瓶颈、只考虑铸件质量约束的铸造生产线加工过程，优化确定给定铸件的批次划分结果、铸件加工顺序以及铸件工序的加工机器，使整个加工过程的总完工时间最小.

1.2 问题模型

参数与符号表示

n：待加工铸件数量.

N：铸件集合，N={Ni，i=1，2，…，n}.

qi：铸件i 的工序数.

Oi：铸件i 的工序集合，Oi={O（i，j），j=1，2，…，qi}.

mij：铸件i 的第j 道工序的可用机器数量.

Mij：铸件i 的第j 道工序的可用机器集合.

Mij={Mijk，1 ≤k ≤mij}.

tijk：铸件i 的第j 道工序交给机器Mijk加工所需时间.

w：铸件质量集合，w={wi，i=1，2，…，n}.

m′：熔炉数.

M′：熔炉集合，M′={Md，d=1，2，…，m′}.

Q：熔炉熔炼速度，Q={Qd，d=1，2，…，m′}.

P：熔炉浇铸速度，P={Pd，d=1，2，…，m′}.

U：熔炉最大熔炼质量，U={Ud，d=1，2，…，m′}.

L：铸件批次划分结果.

NTd：第d 个熔炉的炉次数.

Fd：第d 个熔炉的炉次集合，Fd={1，2，…，NTd}，f∈Fd表示熔炉d 的第f 个炉次.

Ld：熔炉d 负责的铸件批次集合，d=1，2，…，m′，l∈Ld表示铸件批次l.

Cmax：最大完工时间.

A：足够大的正整数.

xijk：铸件i 的第j 道工序如果交给机器Mijk加工则xijk=1，否则为0.

yhgj：如果工序O（h，j）在O（g，j）之后加工或O（h，j）不存在或O（g，j）不存在则yhgj=1，否则为0.

Sigk：铸件i 的第j 道工序在机器Mijk上加工的开始时间.

目标函数：

式中：式（1）为本文模型的目标函数，最小化最大完工时间；式（2）表示一道工序只能由一台机器加工；式（3）表示熔炉每炉次只能生产一种铸件产品批次组合；式（4）表示只有熔炉当前炉次的熔炼浇铸工序完成之后才能进行下一炉次的熔炉浇铸工作；式（5）表示熔炉生产能力约束；式（6）表示每个铸件只能分配到一个批次当中；式（7）表示铸件的工序必须在其前一道工序完成之后才能开始加工；式（8）表示除熔炉外一台机器一次只能加工一道工序.

2 并行混沌优化算法（PCOA）

混沌优化算法的思想是产生与优化变量相同数目的混沌变量，用类似载波的方式将其引入优化变量使其呈现混沌状态，把混沌遍历范围放大到优化变量取值范围后，用混沌变量取代优化变量，直接利用混沌变量搜索[16]，并行混沌优化算法在混沌优化算法的基础上引入并行机制，每个优化变量由多个混沌变量映射，所有的混沌变量独立搜索，并行变量的最优值为需要的优化解，并行混沌优化算法的计算过程可以总结如下.

Step1.初始化，在这一步中，需要设置的参数包括总迭代次数k=1，2，…，S，一次载波迭代次数S1，并行个数P，全局最优目标函数值H*，以及混沌变量的随机初始，其中i=1，2，…，P，代表并行候选个体，j=1，2，…，D，代表优化问题的决策变量.

Step2.利用式（9）将混沌变量映射到决策变量的搜索空间内，

式中：UBj，LBj分别代表第j 个决策变量的搜索空间上界与下界；表示全局最优解对应的解决方案；β为重要的局部搜索参数，用于调整决策变量的搜索范围.

Step4.利用Logistic 一维混沌序列更新混沌变量值，序列表达式：

Step5.迭代直至满足终止条件.

3 HPCOA 求解铸造生产线两阶段协同调度问题

3.1 编码与解码

染色体的编码与解码是解决调度问题的关键，考虑到铸造生产线优化调度问题的离散特性以及批次加工与机加工协同调度的问题，本文提出一种基于工件与机器的分层编码方式.编码由工件编码和机器编码两部分组成，分别对应工件的加工顺序和工序的加工机器.表1 为一个铸造生产线调度问题示例，本文只列出铸件部分工序用于显示编码过程.工件编码OS 由两层基因组成，第一层基因S1代表铸件批次加工过程中的熔炼浇铸工序，第二层基因S2代表铸件机加工过程中的工序.假设初始混沌向量X=[0.7，0.55，0.1，0.3，0.4|0.15，0.6，0.9，0.85，0.2，0.23，0.86，0.73]，利用整数序列φ 记录X 中各数的位置信息，铸件工序与φ 中数字一一对应，对X 排序 得X′=[0.1，0.3，0.4，0.55，0.7 |0.15，0.2，0.23，0.6，0.73，0.85，0.86，0.9]，整数序列作相应变化得新整数序列φ′.根据整数与工序的对应关系将φ′中数字替换为代表工件号的基因值即得到工件编码.最终得到的工件编码染色体中，每个基因值为工件号，在染色体中出现的次数等于相应工件的工序总数，是第几道工序取决于其位置顺序.机器编码MA 产生过程为，首先产生与加工铸件总工序数相等的混沌变量初始值，假设M=[0.1，0.85，0.67，0.45，0.92，0.31，0.62，0.23，0.18，0.24，0.78，0.05，0.71]，M中基因与基因对应的工序可选加工机器数的乘积向上取整即为选择的加工机器序号，序号对应的机器即为工序最终选择的加工机器.例如M 中第一个基因值0.1对应铸件三的第一道工序O31，O31可选加工机器数为2，分别为机器一与机器二，基因值与机器数的乘积向上取整得1，代表O31选择可选加工机器集中的第一台机器，即机器一.其他亦然直到所有工序加工机器安排完毕.编码方案详细过程如图2 所示.

图2 分层编码示意图Fig.2 Schematic of layered coding

表1 示例铸件信息Tab.1 Example casting information

对编码方案解码时，假设熔炉一、二的最大熔炼质量为8 和10，首先将工件编码中S1部分工序按照选择的熔炼炉进行分类，分类完成后根据熔炉的最大熔炼质量约束进行分批，铸件分批时，为了提高炉次利用率，尽可能将更多的铸件划分到同一批次当中.本例中选择炉二的铸件N1、N4、N5，N1、N4的总质量为10，N1、N4、N5的总质量为14 大于炉二的最大熔炼质量，因此将N1，N4组成一批，N5单独成为一批，详细分批过程如图3 所示.根据分批结果得出铸件熔炼浇铸工序的加工时间之后采取主动调度[17]的解码方式对编码方案进行解码.

图3 铸件分批示意图Fig.3 Block diagram of casting

3.2 交叉变异策略

在提出的HPCOA 算法中，通过交叉变异策略实现并行解决方案之间的信息交流，提高解的质量.交叉和变异策略的引入对于提高算法在每次迭代中解集的多样性、加快算法收敛速度有较大的作用.交叉方式本文采取优先操作交叉[18]，任意划分工件集合为2 个非空集合，保持一个集合的工件基因不变，交换另一集合的工件基因顺序.机器编码采取单点变异策略，随机选择一个位置，在此工序所对应的可选机器集中选择一个与当前机器号不同的机器，替换当前机器.工件编码采取逆序变异策略，将染色体中两不同随机位置间的基因序列逆序.需要注意的是，本文中的工件编码由两层基因组成，因此逆序变异策略在两层基因上单独进行且在执行交叉变异操作之后，混沌向量做相应改变.

3.3 变邻域搜索策略

由于混沌的随机性强、导致PCOA 算法在最优解邻域搜索时收敛速度变慢，算法的局部搜索能力较弱，为了提高算法的收敛速度，本文将PCOA 算法与变邻域搜索（variable neighborhood search，VNS）算法结合从而开发出更有效的混合优化算法.VNS 算法通过对当前最优解进行不同邻域的反复递进搜索，使当前最优解不断向全局最优解靠近.具有强大的局部搜索能力，在车间调度问题中展示出了优异的性能[19-20].邻域结构的选择对VNS 的求解质量和执行效率有很大的影响.研究表明，对关键路径上的工序块进行邻域搜索是改善解质量的最有效方式[21]且在一个关键块内交换内部操作不会减少最大完工时间[22].关键块的确定参考文献[23].假设一个关键块KB={KB1，KB2，…，KBn-1，KBn}，其中KB1，…，KBn，代表关键工序，首先定义三个函数：1）Swap（x，y）表示交换工序x 和y；2）Insertb（x，y）表示将x 插入y 的正后方；3）Insertf（x，y）表示将x 插入y 的正前方.本文给出如下四种有效邻域：

N1：选择关键块块内工序，将其插入块首工序之前或块尾工序之后，N1可表述如下：

N2：将关键块的前两道工序与关键块的后两道工序互相交换.N2可表述如下：

N3：将关键块块首工序插入关键块内部.N3可表述如下：

N4：将关键块块尾工序插入关键块内部.N4可表述如下：

变邻域搜索步骤如下所述：

Step1.给定初始解H，确定解的关键块，定义m个邻域，i=1.

Step2.使用邻域结构Ni进行搜索，如果在邻域内找到比H 更优的解H′，则令H=H′，i=1.

Step3.如果搜遍邻域结构Ni仍找不到比H 更好的解，则令i++.

Step4.if i≤m，转Step2.否则输出最优解H.

3.4 算法的实现

本文针对铸造生产线全流程优化调度问题，提出了结合并行混沌优化与变邻域搜索的混合算法.混合算法拥有良好的全局搜索与局部搜索能力，产生新解能力强，搜索精度高，对初始值不敏感，不易陷入局部最优解，在解决本文提出的铸造生产线全流程调度模型问题时表现出良好的性能.算法具体步骤如下，流程图如图4 所示.

图4 HPCHO 算法流程图Fig.4 Flowchart of HPCHO

Step1.确定算法参数.设置迭代次数k=1，指定最大迭代次数S、一次载波迭代次数S1、并行数P.

Step2.初始化.随机产生与种群数相等的混沌初始向量，一个初始向量中包含与工序个数相等的随机数.

Step3.确定当前迭代次数，利用式（9）与本文提出的编码解码规则将混沌向量映射到决策变量的搜索空间内.

Step4.采取交叉变异策略形成新解，如果新解的目标函数得以改进，则用新解替代原来的解.

Step5.对解进行变邻域搜索操作，直到解的工序块中所有关键工序都已移动完毕，不能继续改进，结束邻域搜索.

Step6.利用式（10）的混沌序列函数更新混沌向量中随机数的值，得到新的混沌向量.

Step7.if k≥S，则终止搜索，否则转Step3.

4 仿真研究

为便于分析算法性能，本文结合实际铸造生产线生产加工情况，参考文献[3]和[9]设计测试算例，数据按任务与资源的规模分为小、中、大三类算例.具体参数设置见表2.对于表中有范围限制的参数均采用随机的方式在指定范围内生成数据，其中，质量单位为t，时间单位为h，速度单位为t/h.

表2 算例数据参数取值Tab.2 Numerical example data parameter value

为了验证本文提出的HPCOA 算法对模型求解的有效性，我们选取传统的并行混沌优化算法（PCOA）、经典的遗传优化算法（GA）与融合禁忌搜索的混合离散灰狼优化算法（HDMGWO）[8]在三类算例上与HPCOA 进行了对比实验，其中PCOA 与HPCOA 在参数的选取上保持一致，PCOA 在迭代过程中取消了交叉变异步骤与变邻域搜索步骤.算法均使用Matlab R2018 b 实现，在CPU2.2.GHz、4GB 内存的环境下运行.经过实验测试，设置小规模算例算法的运行时间为300 s，中等规模算例算法运行时间为600 s，大规模算例算法运行时间为900 s.PCOA与HPCOA 算法一次载波运行时间占总运行时间的1/3.并行数P=50，HDMGWO 算法的禁忌搜索次数在三类算例上分别取值为20、40、60.算法的交叉概率Pc=0.7，变异概率Pm=0.5，种群规模N=50.为了排除随机性的影响，每个算例求解15 次，计算结果如表3 所示，其中，Best 为算例15 次求解结果中，最大完工时间的最优值.Avg 为算例15 次求解结果的平均值，StDev 为算例15 次求解结果的标准差.Worst 代表算例15 次求解结果的最差值.

表3 不同任务规模下算法计算结果比较Tab.3 Comparison of computational results for different task sizes

图5 为按任务规模计算的算法性能比分析图，图6 为四种算法不同算例下Avg 值、Best 值与Worst值的对比分析图.图中可以看出，HPCOA 与GA、HDMGWO 及PCOA 相比，在不同任务规模下混合算法都能取得最优的结果，且任务规模越大算法性能越好，这是因为随着任务规模的扩大，问题的解空间急速扩张，而GA 与PCOA 缺乏强大的局部搜索能力，容易陷入局部最优解，从而影响算法整体的性能.HDMGWO 不如HPCOA 的原因在于HDMGWO每次交叉的父代之一来自于当前种群最优的三个解中的一个，这导致算法的全局搜索能力变弱，影响了算法最终的表现.

图5 按任务规模计算的算法性能比Fig.5 Algorithm performance ratio by task size

图6 算法在不同算例下Best、Avg与Worst值的对比分析Fig.6 Comparison and analysis of the Best、Avg and Worst value of the algorithm in different examples

算法稳定性方面，如图7 所示，随着算例规模扩大，StDev 值明显增加，但总体而言，PCOA 在不同算例规模上StDev 值都最小，但由于其每次求得的解质量都不高，导致其总体性能一般，而HPCOA 虽然StDev 值较大，但算法在大规模算例下15 次求解结果的最差解甚至要优于其他算法得到的最优解.因此，综合考虑算法的性能，本文提出的混合并行混沌优化算法能更有效地解决本文所提出的铸造生产线优化调度问题.

图7 算法不同算例下的StDev 值Fig.7 StDev values under different calculation examples of the algorithm

5 结论

铸造生产线加工过程分为批次生产加工和单件机加工两个阶段，针对铸造生产线生产加工过程当中熔炼浇铸加工与机加工协同调度问题，以总完工时间最小为目标函数，建立了以熔炼过程为生产瓶颈、只考虑铸件质量约束的铸造生产线全流程优化调度模型.为求解该模型，本文设计了一种HPCOA算法，算法设计独特的编码解码机制并在算法中引入变邻域搜索与交叉变异策略以避免算法陷入局部最最优值，提高了算法的局部搜索能力，增强了算法的开发效率.仿真实验表明HPCOA 算法在求解本文所提出的铸造生产线优化调度问题时具有比GA、PCOA、HDMGWO 算法更好的性能.