考虑低碳排放的废钢铁生产调度模型和算法研究

陈伟达，王敬敬

（东南大学 经济管理学院，江苏 南京 211189）

国际钢铁协会研究报告表明，平均生产每吨钢会排放1.9吨二氧化碳.根据国际能源机构的数据，钢铁行业约占全球二氧化碳总排放量的4%～5%.降低钢铁行业生产中产生的碳排放问题越来越受到重视.废钢铁再熔炼过程是钢铁生产过程中非常重要的一个环节，也是重要的耗能单元，废钢铁再熔炼的优化调度，对于钢铁企业实现节能减排的目标有着非常重要的现实意义.

当前，钢铁工业生产调度方面的优化问题已经吸引了国内外的很多学者进行研究，李铁克等［1］将炼钢连铸生产过程抽象为混合流水车间，建立了0－1型混合整数线性规划调度模型，在对模型进行Benders分解的基础上，提出了将GA（genetic algorithm）与LP（linear programming）结合的两阶段遗传算法；谭园园等［2］将钢包调度问题归结为车辆路径问题，根据钢包服务钢水过程的约束建立了钢包调度问题的数学模型，针对模型特点提出了分散搜索算法；王刚等［3］建立了基于“炉机对应”原则的炼钢－连铸调度模型，求解不同生产模式下的调度方案；Tang等［4］针对炼钢－连铸生产订单批处理过程用拉格朗日松弛和列代组合方法进行求解，通过放松订单约束，获得拉格朗日松弛模型，利用拉格朗日松弛和列之间的关系，开发了一个两层嵌套循环的综合算法；王柏琳等［5］对等待时间受限的两阶段流水车间调度问题的基本性质进行了研究，为设计求解算法提供了理论基础；Mao等［6］首先把炼钢－连铸调度问题建模成把总加权延迟时间和等待时间最小化为目标的一种混合整数规划问题，然后再使用拉格朗日松弛算法放松约束去求解该混合整数规划问题；Luo等［7］研究了考虑机器电力消费成本的混合流水车间调度问题，提出一种新的蚁群优化启发式算法.

在节能减排方面同样已经有了一些研究成果，Fang等［8］建立了一个同时考虑工件总完工时间、能源消耗的多目标流水车间调度模型，通过对加工速度的改变来影响目标函数；Tan等［9］研究了可变电价下炼钢调度问题的两阶段数学规划模型，第一阶段的目标是最小化最大完工时间，第二阶段是能源消耗最优；Steffen等［10］研究了碳排放约束下随机水热调度问题，该问题给出碳排放配额，超过的部分就要进行罚款，并把配额作为约束条件.

分析以上研究成果可以发现：（1）目前对于钢铁工业生产调度问题的研究基本都是关注在多种算法对炼钢－连铸生产调度的优化，对废钢铁再熔炼生产调度问题的研究几乎没有；（2）研究大多把总完工时间最小和产量最大作为目标，虽然也有考虑到能耗的，但是不能完全使之与节能减排的目标统一起来.因此，论文把最小化二氧化碳排放量作为目标函数，研究废钢铁再熔炼生产调度问题，并使之与最小化最大完工时间为目标的调度结果进行比较，结合算例分析钢铁企业如何更好地实现节能减排，具有十分重要的现实意义.

1 问题描述及假设

废钢铁再熔炼从工序的角度可分为“长流程”和“短流程”.长流程一般指转炉炼钢，原料以生铁为主，废钢为辅；短流程一般指电炉炼钢，原料以废钢为主，生铁为辅.废钢铁的再熔炼工艺流程主要有4种，如图1所示.

图1 废钢铁再熔炼工艺流程图Fig.1 The process flow chart of iron and steel scrap remelting

论文研究的是从电炉开始的废钢铁再熔炼过程，其最主要的生产工序是电炉生产高温钢水和连铸机将液体钢水加工成固态铸坯，其生产过程的合理调度可以有效地提高企业的生产效率，降低企业的生产成本和减少二氧化碳排放.其他次要生产环节，一般来说不会成为主要生产瓶颈和生成能耗的主要环节.废钢铁再熔炼生产调度问题可以被抽象为混合流水车间调度问题，此类问题已被证明是NP难问题.

1.1 问题描述

废钢铁再熔炼生产调度各个工序都存在着多台生产设备，是多阶段并行多机的混合流水车间调度问题.这里，一个“工件”对应着一个炉次，每个工件都要顺序经过每道生产工序的加工处理，每个工序的所有生产机器是完全相同的.对于任一工件来说，在两道工序之间会存在等待时间，一方面工件本身会产生温降，另一方面会产生大量的碳排放.为了减少钢铁企业产生的碳排放量，论文将最小化碳排放量作为目标.废钢铁再熔炼生产调度过程中，会产生大量的碳排放.故从以下两个方面来考虑：（1）机器加工处理过程产生的碳排放；（2）炉次到达间隙机器空转产生的碳排放.为了更好地实现节能减排，建立了碳排放量最小作为目标函数的生产调度模型.

1.2 基本假设

废钢铁再熔炼流程是一个准连续或间歇的复杂过程系统，通过对南京钢铁厂的实际调研发现，炼钢厂的生产周期会在一定范围波动，为了能更好地用数学模型对实际问题进行抽象描述，作如下假设：

（1）废钢铁再熔炼各设备运行正常无故障，生产稳定，即能保证充足的原材料供应和铁水顺行.

（2）工件数、机器数、在每台机器上的每个工件的处理时间以及能源消耗是已知的，且工件在同一工序的不同机器上的加工时间是相同的.

（3）一台机器在同一时刻只能处理一个工件，一个工件在一个工序中只能由一台机器处理.

（4）同一台机器，只有前一个工件处理完才能处理下一个工件.

（5）每一个工件都须经过所有的工序进行加工，且有序进行.

2 废钢铁再熔炼生产调度模型

2.1 符号定义

n：总工件数；i：工件的编号，i＝1，2，…，n；m：总工序数；j：工序的编号，j＝1，2，…，m；Nj：工序j的总机器数，j＝1，2，…，m；k：机器的编号；Mjk：在工序j的机器k上加工的总工件数；hjk：在工序j的机器k上加工的第h个工件，h＝1，2，…，Mjk；Tijk：工件i在工序j的机器k上的加工时间，i＝1，2，…，Mjk；Sijk：工件i在工序j的机器k上的开始加工时间；Fijk：工件i在工序j的机器k上的加工结束时间；Eijk：工件i在工序j的机器k上的加工能耗；EIjk：在工序j中机器k的空转能耗；TIjk：在工序j中机器k的空转时间；α：CO2排放当量，为264.5kg／（kWh）；Yijk：0，1变量，当工件i在工序j的机器k上加工时为1，否则为0.

2.2 碳排放计量

废钢铁再熔炼生产过程中，会产生大量的碳排放，碳排放主要由两部分组成：机器加工处理过程产生的碳排放、工件到达间隙机器空转产生的碳排放.

（1）每一道工序的每个机器加工处理时产生的碳排放，在总的碳排放量当中，这部分的碳排放占有较大的比重，表示为

（2）两个工件到达之间机器空转时产生的碳排放为

若CO2排放总量记为Ec，则

2.3 模型建立

基于以上问题描述及模型假设，建立如下废钢铁再熔炼生产调度模型：

（1）目标函数为

式（4）表示论文的目标函数是最小化碳排放量.

（2）模型构建所需要的约束条件

其中

式（6）表示一个工件在一道工序上只能由一台机器加工；式（7）表示每一道工序的总的机器处理的工件数为n；式（8）表示每一个工件只有在前一个工序加工结束才能进入下一道工序，前一工序加工结束时间不大于下一工序加工开始时间；式（9）表示任一工件，其每一工序的加工结束时间取决于加工开始时间和加工时间；式（10）表示对于同一台机器在同一时刻只能处理一个工件，只有前一个工件处理完才能处理下一个工件.

3 遗传算法及算例分析

废钢铁再熔炼生产调度问题属于NP难问题，解决这类问题多用遗传算法、粒子群算法、邻域搜索算法等智能算法进行求解，其中遗传算法是一种非常有效的智能优化算法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解.进化从完全随机个体的种群开始，之后一代一代发生.在每一代中，整个种群的适应度被评价，基于个体的适应度，从当前种群中随机地选择多个个体，通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群.遗传算法能够很好地解决全局优化问题和NP难问题，因此论文选择遗传算法对提出的废钢铁再熔炼生产调度模型进行求解.

根据对南京钢铁厂进行实地调研发现，不同钢种实际加工工艺以及加工周期的要求是有一些差别的，论文拟定废钢铁再熔炼生产过程有3道工序、共有8个工件需要经过加工处理，每个工件都必须经过这3道工序，每道工序的机器的数量分别是3，2，3台.

表1给出了每台机器对每个工件的加工处理时间，表2给出了每个工件在各机器上加工处理的能耗，以及机器空转时产生的能耗.

表1 各机器对各工件加工时间Tab.1 The time table min

表2 加工过程中的能耗Tab.2 The energy consumption table

采用遗传算法求解时，将遗传迭代次数设置为200，种群规模设置为30，变异概率设为0.1，下面分别讨论把最小化碳排放量作为目标函数的废钢铁再熔炼生产调度问题以及把最小化最大完工时间max｛Fimk，i＝1，2，…，Nmk；k＝1，2，…，Mm｝作为目标函数的废钢铁再熔炼生产调度问题，分析两个调度问题之间存在的碳排放量的变化以及完工时间的差别.

把最小化碳排放量作为目标函数时，通过对模型进行求解，得到如图2所示的生产调度甘特图.由图2可以看出，废钢铁再熔炼生产调度问题的最大完工时间是427，如图2的生产调度甘特图中，第一行表示工件J1在3道工序中分别由编号为“2”、“2”、“1”的机器加工，第二行表示工件J2在3道工序中分别由编号为“3”、“1”、“1”的机器加工，依次类推，第8行表示工件J8在3道工序中分别由编号为“1”、“2”、“2”的机器加工.

图2 生产调度甘特图Fig.2 The gant graph of scheduling

同时得到如图3所示的各代最优个体适应值以及如图4所示的各代群体平均适应值.

图3 各代最优个体适应值Fig.3 The best individual adaptive value

图4 各代群体平均适应值Fig.4 The average individual fitness

由图3、4可以看出，使用该遗传算法进行计算求解时，二氧化碳排放量随着迭代次数的增加而逐渐收敛，在大约遗传到20代时，就可以达到比较好的收敛效果，这表明该算法在求解废钢铁再熔炼生产调度问题时是高效的，得到了较好的优化效果，二氧化碳排放量为5.444 2×105kg.

把最小化最大完工时间作为目标函数时，通过对模型进行求解，得到如图5所示的生产调度甘特图以及如图6所示的完工时间遗传迭代次数图.

由图5可以看出，把最小化最大完工时间作为目标函数的废钢铁再熔炼生产调度问题的最大完工时间是328，第一行表示工件J8在3道工序中分别由编号为“3”、“1”、“1”的机器加工，第二行表示工件J7在3道工序中分别由编号为“2”、“1”、“2”的机器加工，依次类推，第八行表示工件J1在3道工序中分别由编号为“2”、“2”、“2”的机器加工.

图6 遗传迭代次数图Fig.6 The graph of genetic iterations

由图6可以看出，在大约遗传到20代时，就可以达到比较好的收敛效果.通过计算得到此时的二氧化碳排放量为6.278 4×105kg.

表3给出了把最小化二氧化碳排放量作为目标函数时的废钢铁再熔炼生产调度模型求解结果以及把最小化最大完工时间作为目标函数的废钢铁再熔炼生产调度模型的碳排放量的求解结果.

表3 模型求解结果对比Tab.3 Comparison of results kg

由表3可以看出，把最小化二氧化碳排放量作为目标函数的废钢铁再熔炼生产调度模型较之与最小化最大完工时间的生产调度模型，二氧化碳的排放量减少了13.3%，这对于钢铁企业节能减排的有效实施具有很好的参考价值.

4 结束语

针对废钢铁再熔炼生产调度问题，论文分析了废钢铁再熔炼生产调度问题的特点，考虑到节能减排的目标，把最小化二氧化碳排放量作为废钢铁再熔炼生产调度问题的优化目标，并从两个方面来考虑二氧化碳的排放量：（1）机器加工处理过程产生的碳排放；（2）炉次到达间隙机器空转产生的碳排放.并设计遗传算法进行求解，使之与最小化最大完工时间的生产调度结果进行比较.结合算例进行分析可知，把最小化二氧化碳排放量作为优化目标较之与最小化最大完工时间的生产调度模型，虽然得到的最大完工时间不是最优的，但是二氧化碳的排放量减少了13.3%，废钢铁再熔炼的优化调度，对于钢铁企业实现节能减排的目标有着非常重要的现实意义.

［1］李铁克，苏志雄.炼钢连铸生产调度问题的两阶段遗传算法［J］.中国管理科学，2009，17（5）：69－74.

［2］谭园园，魏震，王森，等.基于 VRPTW－AT模型的钢包优化调度方法［J］.系统工程学报，2013，28（1）：94－100.

［3］王刚，王彬，王宝.基于“炉机对应”原则的炼钢－连铸调度模型［J］.北京科技大学学报，2013，35（8）：1081－1092.

［4］Tang L X，Wang G S，Liu J Y，et al.A combination of lagrangian relaxation and column generation for order batching in steelmaking and continuous－casting production［J］.Naval Research Logistics，2011，58（4）：370－388.

［5］王柏琳，李铁克.等待时间受限的流水车间调度问题的若干性质［J］.系统工程理论与实践，2012，32（6）：1346－1352.

［6］Mao K，Pan Q，Pang X F，et al.A novel lagrangian relaxation approach for a hybrid flowshop scheduling problem in the steelmaking－continuous casting process［J］.European Journal of Operational Research，2013，236（1）：51－60.

［7］Luo H，Du B，Huang G Q，et al.Hybrid flow shop scheduling considering machine electricity consumption cost［J］.International Journal of Production Economics，2013，146（2）：423－439.

［8］Fang K，Uhan N，Zhao F，et al.A new approach to scheduling in manufacturing for power consumption and carbon footprint reduction［J］.Manufacturing Systems，2011，30（4）：234－240.

［9］Tan Y Y，Huang Y L，Liu S X.Two－stage mathematical programming approach for steelmaking process scheduling under variable electricity price［J］.Journal of Iron and Steel Research，International，2013，20（7）：1－8.

［10］Steffen R，Bruno F，Mario V F，et al.Stochastic hydro－thermal scheduling under CO2emissions constraints［J］.IEEE Transactions on Power Systems，2012，27（1）：58－68.