基于NSGA—II的炼钢—连铸调度多目标优化

朱朝月

摘要：为了多目标优化炼钢-连铸生产调度问题，引入了快速非支配排序遗传算法（NSGA-II）。以最小化浇次计划完工时间和最小化中间等待时间作为优化目标，依据炼钢-连铸工艺要求建立数学模型，通过NSGA-II在解空间搜索Pareto最优解集。仿真结果表明，该算法解决炼钢-连铸调度问题，能够迅速得到性能优越的Pareto前端，编排出高质量的生产计划，提高决策者的工作效率。

关键词：NSGA-II 炼钢-连铸 生产调度多目标优化

中图分类号：TP273 文献标识码：A 文章编号：1007-9416（2016）08-0061-02

炼钢和连铸工序的协调生产对改善钢厂的生产组织方式和提高系统的运行效率起着非常重要的作用[1]。该过程中各方面约束限制和不可控因素较多，炼钢-连铸调度计划的优化，对于提高企业生产效率，降低资源、人力消耗等具有重要意义。对炼钢-连铸调度的优化往往涉及多个优化目标。不同的优化目标可能相互制约，即某些目标的改善可能导致其它目标的恶化。NSGA-II是近年来兴起的一种多目标优化算法，它降低了非劣排序遗传算法（NSGA）的复杂性，具有运行速度快，解集的收敛性好等优点。本文引入NSGA-II对炼钢-连铸调度进行多目标优化，并通过仿真实验，验证了该方法的有效性。

1 炼钢-连铸调度模型

1.1 问题描述

炼钢-连铸主要包含冶炼、精炼和连铸三个主要环节，每个环节都存在多个并行机组。冶炼多为氧气顶吹转炉冶炼；精炼分为多种精炼工艺，如LF、RH、AOD等；连铸是将液态钢水连续浇铸成固态铸坯的过程。不同钢种所需的精炼工艺存在差别，有的只经过一道精炼工序，有的可能需要多重精炼。因此，炼钢-连铸调度问题属于多工件、多阶段和多并行机的，具有有限缓冲能力的混合流水车间调度问题[2]。通过炼钢-连铸调度计划编制，协调各工序各设备的生产节奏，在满足约束条件的前提下，尽可能缩短炉次的等待时间，缩短浇次计划的完工时间。

1.2 基本假设

考虑到钢铁生产流程的复杂性，为了便于炼钢-连铸调度问题的数学抽象，现根据实际情况做如下假设：（1）只考虑冶炼、精炼和连铸三个主要环节的工序及设备。（2）浇次计划已知，包括浇次总数、各浇次所包含的炉次数、炉次的加工流程及对应的目标铸机。（3）已知炉次在上下工序间的运输时间、最长等待时间以及同一连铸机上相邻浇次间的最短间隔时间。

1.3 符号和变量

符号：表示第j个浇次第i个炉次；表示第k种的第l个设备。变量：、分别表示在上加工的开始时间和结束时间；常数：N为炉次总数；P为浇次总数；R为设备种类总数（k=1为转炉，k=R为连铸机）；表示炉次在两设备间运输所需的时间，表示炉次在两设备间的最长运输时间。

1.4 数学模型

基于对模型的基本假设，构建炼钢-连铸调度的多目标优化模型如下：

式（1）是最小化完成整个浇次计划的时间；式（2）是最小化各炉次等待时间。根据实际炼钢-连铸过程，模型需满足以下约束条件：（1）每个炉次属于且仅属于一个浇次；（2）炉次在加工过程中，必须完成一个工序后，才能开始下一个工序；（3）每个炉次都有固定的工序顺序；（4）每个设备在同一时间加工的炉次数不超过其工位数；（5）每个工序加工时间不小于其必要加工时间；（6）钢包在工序间停留时间小于允许的最长等待时间；（7）同一铸机相邻浇次间隔时间，不小于其最小间隔时间。

2 NSGA-II算法

NSGA-II是在NSGA（非支配排序遗传算法）的基础上进行改进的算法，具有以下特点：（1）采用快速非支配排序，降低了算法的计算量；（2）提出了拥挤度比较算子，并在快速排序后作为衡量同级个体优劣的标准；（3）引入精英策略，将交叉变异操作前后的种群合并，共同竞争产生下一代种群[3]。

2.1 NSGA-II排序方法

对种群中任一个体x，都有支配x的个体数和x所支配的解集。首先，选出种群中所有=0的个体，构成集合；然后对于中的每个个体y，找出其所支配的解集中的每个个体z的，若=1，则将个体z存入另一个集合。继续对作上述分级操作，直到所有个体都被分级。最后，分别赋予每级个体非支配序号（=1，=2，=3…）。

2.2 比较算子

为了确保种群的多样性，NSGA-II提出了拥挤度的概念，即个体周围其他个体的密集程度。对于个体x，计算由个体x+1和x-1构成的最小长方形的平均边长，作为x的拥挤度距离。比较两个体优劣时，首先比较其所属非劣等级，等级需要越小越好；等级相同时，比较两个体的拥挤度距离，越大越好。

3 NSGA-II对炼钢-连铸调度的多目标优化

3.1 编码方式

3.2 求解步骤

Step1：确定种群规模，截止进化代数等算法相关参数。Step2：=0，随机生成足够多的个体，筛选符合约束条件的个，构成种群。Step3：交叉、变异，生成子代种群。将和合并，规模2。Step4：将混合后的种群进行非支配排序，同一等级的个体按照拥挤度距离排序。选出优良个体组成下一代种群。重复Step3和Step4，直到=。Step5：种群中非劣等级为1的个体构成Pareto最优解集，将其输出并结束运行[4]。

4 仿真实验

国内某钢厂，设有180 t转炉3座，LF炉2台，RH炉1台，板坯连铸机2台（CC1、CC2）。现以表1中的浇次计划进行仿真实验[5]。

仿真结果如图1所示，完成浇次计划总时间为605min，各炉次加工流程顺畅，没有长时间等待停留。通过NSGA-II编制的作业计划可以保证连续浇铸，且各工位作业时间没有冲突。

5 结语

综上所述，基于NSGA-II的炼钢-连铸调度多目标优化方法能够保证各炉次加工过程顺畅，缩短浇次计划完工时间，提高作业效率。该方法能够借助计算机运行，在短时间内编制出高质量的作业计划，降低决策者工作量，具有较高的现实意义和推广价值。

参考文献

[1]郑忠，朱道飞，高小强.基于蚁群算法的炼钢-连铸作业计划编制方法[J].北京科技大学学报，2009（4）：504-510.

[2]王刚，王彬，王宝，等.基于“炉机对应”原则的炼钢—连铸调度模型[J].北京科技大学学报，2013（8）.

[3]高媛.非支配排序遗传算法（NSGA）的研究与应用[D].浙江大学，2006.

[4]高振东，丁宇菁.基于遗传算法的加油车智能派工系统的设计与实现[J].数字技术与应用，2012（5）：111-112.

[5]龙建宇，郑忠，高小强，等.基于遗传算法的炼钢--连铸重计划方法[J].北京科技大学学报，2014（1）.