基于MOMA 算法的分时电价下炼钢生产调度研究

薛明远，叶春明

（上海理工大学 管理学院，上海 200093）

0 引言

气候变暖、能源价格上涨等话题已成为社会热点，节能减排目标任务也随即摆在众多高耗能企业的面前。钢铁企业的钢铁生产具有高耗能、高排放的特点，一直是节能减排课题的重要研究对象。近年来，随着分时电价政策的推广适用，各企业纷纷应用分时电价政策来合理安排企业自身的生产计划，寻求降低能耗成本的有效途径。

Wang 等人针对传统的车间调度问题进行了分时电价下的混合流水车间的研究。并且分时电价政策的推出，促使钢铁企业也在考虑分时电价下的生产调度，如Li 等人针对基于混合流水车间的炼钢连铸生产调度问题，提出了一种高效的果蝇算法对问题进行求解。马文强等人也针对同一问题，提出了一种基于变邻域搜索的混合教与学优化算法。沈鹏针对分时电价下炼钢生产的浇次计划调度问题，提出了一种遗传算法来获得求解。Hadera 等人以优化电力成本为目标，构建了一个具有能量感知的连续时间模型，并提出了一种双层启发算法来求解问题。

在传统的混合流水车间调度及钢铁企业炼钢生产调度方面的研究较多，而对于分时电价下钢铁行业双目标炼钢生产研究较少。本文以分时电价下钢铁企业双目标炼钢生产调度为研究对象，在传统的炼钢生产基础上引入分时电价政策，在满足炼钢生产约束的前提下，以最小化最大完工时间和最小化电力成本为优化目标，建立分时电价下钢铁企业炼钢生产的调度模型。

1 钢铁生产调度问题描述及数学模型

1.1 问题描述

相比于“长流程”炼钢模式，以电弧炉为主要冶炼设备的“短流程”炼钢是较为节能环保的一种生产方式，但是也会加大用电负荷，增加电力成本。对于短流程炼钢模式可以描述为有个炉次，各炉次生产某种或者某些不同的钢铁产品，并将按照生产加工顺序依次经过：炼钢、精炼／多重精炼、连铸等多个加工阶段。具体而言，分别要经过电弧炉炼钢（Electric Arc Furnace Steelmaking，EAF）、氩氧脱碳精炼（Argon Oxygen Decarburization，AOD）、钢包精炼（Ladle Furnace，LF）、连铸（Continuous Casting，CC）四个生产阶段。各生产阶段有多台并行加工设备，各阶段每台设备的功率不同，对同一炉次的加工时长也不同。为保证钢铁产品的质量，要满足以下工艺约束：

（1）各个生产阶段有多台并行的加工设备，同一时刻、同一炉次最多在一台机器上被加工，同一时刻每台设备上最多只能加工一个炉次。

（2）每一炉次一旦开始加工便不可中断。

（3）所有炉次之间互不影响，各炉次之间的加工顺序没有先后，但是每个炉次在加工工序上有前后顺序约束，前一生产阶段结束后才能开始下一生产阶段的加工。

（4）同一浇次的炉次浇铸时不允许断浇。

1.2 数学模型

在分时电价政策的应用下，涉及到大量时间索引，本文提出了双目标的钢铁生产调度时间离散模型，为确保计算速度，本文将时间单位设置为1 h。

研究给出目标函数的数学公式可写为：

其中，表示最大完工时间；C表示炉次的完工时间；表示炉次序号，1，2，…，；表示加工过程中设备加工消耗的电力成本；PW表示加工设备的功率，表示设备序号；T表示设备所处的时间段区间的加工时间，1，2，…，；PR表示时间段区间的电价。

研究中要用到的约束条件可做阐释分述如下：

（1）保证同一炉次的前一加工阶段结束后才可以开始下一阶段，对此可表示为：

其中，b为炉次到达1 生产阶段并开始加工的时间； c为炉次在第生产阶段的完工时间；表示某一工序，表示所有工序的集合，｛1，2，…，｝，表示工序的总数，∈。

（2）保证每个炉次在各生产阶段上仅可以选择该阶段的某一台设备在某一时刻开始加工，对此可表示为：

其中，x为0-1 变量，若炉次在第时刻，选择第生产阶段的第台设备开始加工，则x＝1，否则，x＝0；为某一设备序号，M为工序中所有设备的集合，M＝｛1，2，…，｜M ｜｝；｜M ｜为工序中设备的总数，∈M，M∈。

（3）保证各阶段的任何一台设备在某一时刻最多只能加工一个炉次，对此可依次表示为：

其中，y为0-1 变量，若炉次在第时刻，生产阶段的第台设备上正在加工，则y＝1，否则y＝0。

（4）炉次在生产阶段上的加工开始时间、加工时间、加工结束时间，对此可分别表示为：

其中，p指炉次在第生产阶段的第台设备上加工所用的时间。

（5）保证炉次在生产阶段上的第台设备上的加工是连续的，对此可表示为：

其中，是一个足够大的正数。

（6）炉次的完工时间和所有炉次完工的最大完工时间定义，对此可表示为：

其中，C为炉次的完工时间，为所有炉次的最大完工时间。

2 改进的MOMA 算法

钢铁企业炼钢生产调度问题与混合流水车间的调度问题相似，均属于NP 问题。多目标文化基因算法（MOMA）是一种基于种群的全局搜索和基于个体的局部搜索的结合体，常应用于解决具有多约束条件的0-1 问题，其优点是可以采用不同的搜索策略生成多种改进的MOMA 算法，NSGA-Ⅱ算法的编码规则是可以有效求解此类调度问题的处理策略，所以本文在MOMA 算法的基础上采用NSGA-Ⅱ的编码规则进行改进，在MOMA 算法框架下采用NSGA-Ⅱ的编码规则设计了交叉算子、变异算子以及局部搜索算子，提高了MOMA 算法的种群多样性以及局部搜索性能。改进后的MOMA 算法求解流程如图1 所示。

图1 改进的MOMA 算法求解流程图Fig.1 Improved MOMA algorithm solution flow chart

算法改进的相关操作可做重点表述如下：

（1）编码和解码。本文采用随机键升序的编码方式，构造出从个体位置到炉次排序的对应关系，通过解码过程将为各工件的每一生产阶段选择一台加工设备，同时确定各设备上需加工的各工件的加工顺序以及起始时间，根据求得的目标函数值及本文的各种约束条件生成最优调度方案。

（2）交叉、变异操作。考虑到交叉算子、变异算子影响着局部和全部的搜索能力，本文采用优先工序交叉的交叉策略和局部最优的变异策略。以一条5 个工件的工列排序染色体为例，进行优先工序交叉操作如图2 所示，具体操作为：

图2 优先工序交叉操作示意图Fig.2 Schematic diagram of priority process crossover operation

①随机选择2 个父代染色体和，并将所有工件的序号分配到2 个非空子集和中；

②将父代染色体中包含在中的工件复制到，将父代染色体中包含在中的工件复制到，并维持原有位置；

③将父代染色体中包含在中的工件复制到，将父代染色体中包含在中的工件复制到，原有顺序保持不变；

④得到经过交叉操作后的子代染色体和。

以一条5 个工件的工序排列染色体为例，进行局部最优变异操作，具体操作为：随机选择一个父代染色体，在中随机选择3 个工件｛1，3，5｝作为一个局部的算子，将局部算子中工件排序的所有可能列出｛1，3，5｝、｛1，5，3｝、｛3，1，5｝、｛3，5，1｝、｛5，1，3｝、｛5，3，1｝，然后对每种组合进行计算评估，根据支配关系选择最优的组合得到经过局部最优变异后的子代染色体。假设｛3，5，1｝是最优的组合，局部最优变异操作示意，如图3 所示。

图3 局部最优变异操作示意图Fig.3 Schematic diagram of local optimal mutation operation

（3）局部搜索算子。考虑到局部搜索性能和种群的多样性，本文采用了变邻域的方式，具体操作为：在个体中随机选择一个工件将工件的位置和其他工件的位置进行交换，分别计算每次交换后的目标函数值，记录每次的目标函数值，并根据支配关系选择最优的目标函数值，此时所对应的染色体序列就是最优的变邻域操作后的序列。

3 实验结果与分析

在钢铁企业中，假设炉次的冶炼路线分为4 个阶段，即：EAF 炉熔化废钢→AOD 炉氩氧脱碳精炼→LF 炉钢包精炼→CC 浇铸。

本文中选用一个具有15 个炉次规模的实例进行实验分析，仅考虑各生产阶段之间最大等待时间为0 的情况。每个生产阶段有2 台不同功率的加工设备，每台设备对同一炉次的加工时间不同。各阶段加工设备的功率及编号，见表1。各加工设备对每个炉次的加工时间，见表2。

表1 各阶段加工设备的功率及编号Tab.1 Power and number of processing equipments at each stage

表2 各加工设备对各炉次的加工时间Tab.2 Processing time of each processing equipment for each furnace h

以上海市非夏季时段一天内针对大工业用电的分时电价（单位：元／kWh）政策为例，如图4 所示。分时电价将一天24 h 分为峰时段（8～11 时、18～21时），平时段（6～8 时、11～18 时、21～22 时），谷时段（22 时～次日6 时）。根据具体的电价，一天24 h内的分时电价函数（单位：元／kWh）可表示为式（16）：

图4 上海市大工业用电24 h 分时电价图Fig.4 24 h time-of-use electricity prices for large-scale industries in Shanghai

运用改进的双目标文化基因算法可以得到求解结果，获得最优调度方案，最优解甘特图如图5 所示，计算排产计划的完工时间为169 h。在实际操作过程中，钢铁企业炼钢生产的各个阶段的排产计划大多由调度员用某种简单的启发式规则人工制定，考虑最多的就是完工时间，但是却很少会将电力成本因素考虑其中。在本文中引入分时电价政策前、最小化最大完工时间最优调度方案的电力成本为15 203.334元，在引入分时电价政策后、得到的电力成本结果为14 043.506 元。因此，在分时电价条件下使用改进的MOMA 算法，既保证了最小化最大完工时间，又使电力成本降低了7.63%，对于高耗能的钢铁企业来说，通过充分利用分时电价政策，能够有效地减少生产过程中的电力成本，证明了本文模型有着良好可行性。

图5 模型最优解甘特图Fig.5 Gantt chart of the optimal solution of the model

4 结束语

本文在分时电价政策背景下，以“短流程”炼钢生产为研究对象，分析了分时电价政策下钢铁企业炼钢生产的调度特点，建立了以最小化最大完工时间和最小化电力成本为目标的调度模型，并以一个15 炉次的实例进行实验。实验结果表明，在保证最小化最大完工时间的前提下，引入分时电价政策能够有效地降低自身约7.63%的电力成本，对钢铁企业实现成本节约以及维持整个电网负荷的平衡都具有重要意义。