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

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

摘   要：高效的生产调度策略是铸造企业提高生产效率、降低生產成本的重要手段. 目前，铸造生产优化调度的相关研究通常是针对熔炼浇铸加工与机加工两阶段分别进行的，制约了铸造生产线全流程优化调度的效果. 针对铸造生产线生产过程当中熔炼浇铸加工与机加工协同调度问题，建立了以最小化总完工时间为目标的铸造生产线全流程优化调度模型. 为了有效地解决该调度模型，提出一种混合并行混沌优化算法（HPCOA）. HPCOA中设计了并行混沌搜索用于高效的全局搜索，并引入基于关键路径的变邻域搜索用于增强算法的局部搜索能力. 通过在实际案例的对比试验，证明了HPCOA算法的有效性.

关键词：铸造生产线;协同调度;优化算法;变邻域搜索;交叉变异

中图分类号：TH186                               文献标志码：A

Two-stage Collaborative Scheduling of Casting Production Line

Based on Hybrid Parallel Chaotic Optimization Algorithm

YUAN Xiaofang YANG Yuhui TAN Weihua YIN Baixin

（1. College of Electrical and Information Engineering，Hunan University，Changsha  410082，China;

2. National Engineering Laboratory for Robot Visual Perception Control Technology，Hunan University，Changsha 410082，China）

Abstract：An efficient production scheduling strategy is an important means for foundry companies to improve production efficiency and reduce production costs. At present，the related research on the optimization scheduling of casting production is usually carried out separately for the two stages of smelting casting processing and machining，which restricts the effect of the optimization scheduling of the whole process of the casting production line. Aiming at the collaborative scheduling problem of smelting，casting and machining in the production process of the foundry production line，an optimized scheduling model for the whole process of the foundry production line with the goal of minimizing the total completion time was established. In order to effectively solve the change scheduling model，a hybrid parallel chaos optimization algorithm（HPCOA） is proposed. In HPCOA，parallel chaotic search is designed for efficient global search，and variable neighborhood search based on critical path is introduced to enhance the local search capability of the algorithm. Through comparative experiments in actual cases，the effectiveness of the HPCOA algorithm is proved.

Key words：casting production line;collaborative scheduling;optimization algorithm;variable neighborhood search;crossover mutation

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

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

针对铸造生产线生产过程当中的批次生产调度问题，唐江涛等[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   问题模型

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

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

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对应铸件三的第一道工序O₃₁，O₃₁可选加工机器数为2，分别为机器一与机器二，基因值与机器数的乘积向上取整得1，代表O₃₁选择可选加工机器集中的第一台机器，即机器一. 其他亦然直到所有工序加工机器安排完毕. 编码方案详细过程如图2所示.

3.2   交叉變异策略

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

3.3   变邻域搜索策略

3.4   算法的实现

4   仿真研究

5   结   论

铸造生产线加工过程分为批次生产加工和单件

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

参考文献

[1]    林凯强. 铸造行业智能制造标准化的现状和发展[J]. 铸造工程，2019，43（5）：46—50.LIN K Q. Current situation and development of intelligent manufacturing standardization in foundry Industry[J]. Foundry Engineering，2019，43（5）：46—50. （In Chinese）

[2]    唐红涛，陈荣，秦红斌. 基于改进遗传算法的铸造造型任务批调度模型[J]. 工业工程与管理，2019，24（5）：112—119. TANG H T，CHEN R，QIN H B. A batch moulding scheduling model in foundry based on improved genetic algorithm[J]. Industrial Engineering and Management，2019，24（5）：112—119. （In Chinese）

[3]    胡常伟，陈新度，陈庆新，等. 含不一致任务重量的同型熔炼炉批调度优化[J].工业工程，2014，17（3）：73—78，85.HU C W，CHEN X D，CHEN Q X，et al. Optimization for scheduling identical parallel melting furnaces with non-identical job weights[J]. Industrial Engineering Journal，2014，17（3）：73—78，85. （In Chinese）

[4]    FRANCISCO B，MALLOR F，MATEO P M. Production scheduling in a market-driven foundry：a mathematical programing approach versus a project scheduling metaheuristic algorithm[J]. Optimization and Engineering，2012，13 （4）：663—687.

[5]    GAURI S K. Modeling product-mix planing for batches of meltunder multiple objectives in a small scale iron foundry[J]. Production Engineering，2009，3 （2）：189—196.

[6]    TANG L X，WANG X P. An improved particle swrm pptimization algorithm for the hybrid flowshop scheduling to minimize total weighted completion time in process industry[J]. Transactions on Control Systemstechnology，2010，18（6）：1303—1314.

[7]    LI X X，GUO S S，LIU Y，et al. A production planning model for make-to-order foundry flow shop with capacity constraint[J]. Mathematical Problems in Engineering，2017，2017：1—15.

[8]    QIN H B，FAN P F，TANG H T，et al. An effective multiobjective discrete grey wolf optimizer for a real-world scheduling problem in welding production [J]. Computers & Industrial Engineering，2019， 128：458—476.

[9]    陈荣.面向件批耦合铸造生产的两阶段协同车间调度研究[D]. 武汉：武汉理工大学，2019：8—12.CHEN R. Research on two-stage collaborative workshop scheduling for single piece and batch coupling casting production[D]. Wuhan：Wuhan University of Technology，2019：8—12. （In Chinese）

[10]  MAES J，MCCLAIN J O，WASSENHOVE L N V. Multilevel capacitated lotsizing complexity and LP based heuristic[J]. European Journal of Operational Reserarch，1991，53（2）：131—148.

[11]  刘蓉，周林，王朝，等. 带并行批处理机的柔性作业车间调度问题研究[J]. 武汉理工大学学报（信息与管理工程版），2020，42（1）：36—43.LIU R，ZHOU L，WANG C，et al. Research on flexible job shop scheduling problem with parallel batch processing machine[J]. Journal of  Wuhan University of Technology（Information & Management Engineering），2020，42（1）：36—43. （In Chinese）

[12]  YANG D X，LIU Z J，ZHOU J L. Chaos optimization algorithms based on chaotic maps with different probability distribution and search       speed for global optimization[J]. Communications in Nonlinear Science and Numerical Simulation，2014，19（4）：1229—1246.

[13]  袁小芳，刘晋伟，陈秋伊，等. 并行混沌与和声搜索的多目标混合优化算法[J]. 湖南大学学报（自然科学版），2018，45（4）：96—103.YUAN X F，LIU J W，CHEN Q Y，et al. A multi-objective hybird optimization algorithm based on parallel chaos and harmony search[J]. Journal of Hunan University（Natural Sciences），2018，45（4）：1229—1246. （In Chinese）

[14]  YUAN X F，ZHANG T，XIANG Y Z，et al. Parallel chaos optimization algorithm with migration and merging operation[J]. Applied Soft Computing，2015，35：591—604.

[15]  姚炯，杨根科，潘常春. 基于状态集分解的一类车间计划、调度算法[J]. 系统仿真学报，2009，21（8）：2314—2320.YAO J，YANG G K，PAN C C. Integration of planning and scheduling problem based on states decomposition[J]. Journal of System Simulation，2009，21（8）：2314—2320. （In Chinese）

[16]  高尚. 解旅行商问题的混沌蚁群算法[J]. 系统工程理论与实践，2005（9）：100—104，125.GAO S. Solving traveling salesman problem by chaos ant colony optimization algorithm[J]. Systems Engineering-Theory & Practice，2005（9）：100—104，125. （In Chinese）

[17]  ZHANG G H，GAO L，SHI Y. An effective genetic algorithm for the flexible job-shop scheduling prolem[J]. Expert Systems with Applications，2010，38（4）：3563—3573.

[18]  GAO J，SUN L Y，GEN M S. A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems[J]. Computersand Operations Research，2007，35（9）：2892—2907.

[19]  ZHANG B，PAN Q K，GAO L，et al. A hybrid variable neighborhood search algorithm for the hot rolling batch scheduling problem in compact strip production[J]. Computers & Industrial Engineering，2018，116：22—36.

[20]  ZHANG G H，ZHANG L J，SONG X H，et al. A variable neighborhood search based genetic algorithm for flexible job shop scheduling problem[J]. Cluster Computing，2019，22（5）：11561—11572.

[21]  NOWICKI E，SMUTNICKI C. A fast taboo search algorithm for the job shop problem[J]. Management Science，1996，42（6）：797—813.

[22]  SHA D Y，HSU C Y. A hybrid particle swarm optimization for job shop scheduling problem[J]. Computers & Industrial Engineering，2006，51（4）：791—808.

[23]  王磊，黃文奇. 求解工件车间调度问题的一种新的邻域搜索算法[J]. 计算机学报，2005（5）：809—816.WANG L，HUANG W Q. A new local search algorithm for job shop scheduling problem[J]. Chinese Journal of Computers，2005（5）：809—816. （In Chinese）