改进的差分进化算法求解炼钢-连铸动态调度问题

金 焰，王秀英

(青岛科技大学 信息科学技术学院，山东 青岛 266061)

0 引言

钢铁的生产关系着制造业未来的发展方向，而炼钢-连铸是钢铁工业生产的关键过程，该过程的高效调度能够有效缩短生产周期、降低生产成本和能源消耗、提高钢铁质量和生产效率。炼钢-连铸生产过程中主要包括三大工艺过程：炼钢、精炼和连铸[1]。由于炼钢和精炼的生产过程是离散的，而连铸阶段为了提高产量需要连续生产，因此炼钢-连续生产过程是离散和连续相结合的复杂生产过程。

近年来，国内外研究者们对炼钢-连铸生产调度问题主要方向仍然是静态调度，动态调度的研究仍亟待求解。在炼钢-连铸实际的生产过程中，由于工艺复杂，多约束、多设备、多目标和随机性等特点[2]，常常会出现各种不确定的扰动事件，使得实际生产无法按原始的调度计划执行，如开工时间延迟、设备故障、紧急订单添加等扰动事件[3]。炼钢-连铸动态调度的任务，就是当生产过程中出现扰动时，实时调整调度计划表，保证连续生产的前提下，尽可能的减少能源消耗和等待时间，提高生产效率，降低生产成本[4]。罗小川[5]等针对炼钢-连铸中作业时间冲突引起的调度优化问题，提出了分部分求解的方案，先用线性规划法解决调度问题，再用极大值原理解决连铸机拉速变化问题，优化了炼钢-连铸生产过程中可能因时间扰动导致的调度过程出现时间冲突而导致断浇的问题。张春生[6]等针对故障下的炼钢-连铸动态调度问题，提出了基于动态约束满足技术建模机制，该机制灵活反映了实际生产车间中各种动态因素，能根据炼钢-连铸生产过程中出现的故障扰动程度实时制定不同的调度策略，保证了炼钢-连铸生产过程稳定进行。王柏琳[7]等针对炼钢-连铸生产过程中连铸机出现故障而引起的动态调度问题，建立了动态约束满足模型，提出了基于约束满足的优化方法，通过动态调整策略调整浇次计划，优化了炼钢-连铸两阶段故障引起的调度问题。Yu[8]等针对炼钢-连铸生产过程中转炉故障引起的动态调度问题，建立了多目标非线性规划模型，提出了两阶段动态最优调度方案，设计并开发了动态最优排产软件系统，优化了炼钢-连铸生产过程中的加工时间和排产调度，缩短了炉次在工序间的等待时间。Hou[9]等研究了当生产车间遇到各种实时扰动时对生产车间的影响问题，并提出当机器故障时，通过基本的识别和分析可得出对机器故障引起的问题的调度方案。Jiang[10]等针对炼钢-连铸生产过程中产生的扰动事件引起的调度问题，提出了一种基于改进差分进化的多阶段动态软调度算法，解决了因扰动事件引起的全局调度问题和局部调度问题。钱承星[11]针对炼钢-连铸的实际生产过程中出现的动态扰动因素引起的调度问题，开发了炼钢-连铸生产调度决策支持系统，加入自适应规则改进差分进化算法，应用动态优化思想并嵌入记忆种群形成动态差分进化算法，以某大型钢铁企业为研究对象，将差分进化算法与标准差分进化算法和人工模拟算法进行比较，改进后的动态差分进化算法在炼钢-连铸生产调度过程中更具有实用性。赵月[12]先以生产调度为研究背景，对生产过程中出现的动态因素因其的动态优化问题进行分析，提出了动态差分进化算法，再以炼钢-连铸生产调度为研究对象，提出了增量式动态差分进化算法，当动态扰动事件发生时，快速响应并生成新的调度方案。

本文针对炼钢-连铸动态调度问题，提出一种以炉次最小化总完工时间、最小化总断浇时间、最小化总等待时间和最小化总偏差量为优化目标，将拉格朗日插值算法与差分进化算法相融合，利用拉格朗日插值算法提高差分进化算法的局部搜索能力，通过自适应控制差分进化算法的进化参数，避免了算法陷入局部收敛的现象。最后，通过对国内某大型钢厂的实验数据进行仿真实验，验证了模型和算法的有效性。

1 问题描述

1.1 炼钢-连铸生产工艺过程

炼钢-连铸生产过程主要包含炼钢、精炼和连铸共3个环节。在同一个转炉里经过炼钢、精炼到连铸阶段结束统称为一个炉次，多个炉次组合成一个浇次，同一个浇次必须持续浇铸不能断浇。

1.1.1 炼钢

如图1中所示，高炉(图1中的BF)将生铁和废钢进行熔化，通过转炉(图1中的LD)将生铁和废钢按照钢种的要求进行氧化和脱硫处理，调整其成分的含量到一定的范围内且符合一定的出钢温度，即为铁水。将铁水通过高炉转运到转炉后，加入废钢，进行加热处理去除杂质调整钢水中的碳含量，将处理后的钢水倒入钢包中，通过吊车将其转移至精炼炉中进行精炼。

图1 炼钢-连铸生产工艺流程图

1.1.2 精炼

精炼阶段是为了进一步调整钢水中的成分含量，去除杂质，添加所需的合金成分，生产出特定级别的钢水。钢水温度需要保持在一定的范围内，若钢水的温度过高或过低，都将影响连铸阶段的效果。由于不同级别的钢种质量要求不同，钢水包需经过的精炼炉的种类和数量也不同，根据钢水包经过的精炼炉数量将精炼过程命名为一重精炼(例如一重精炼钢水包只需经过1#RH精炼设备)、二重精炼(二重精炼钢水包需经过2#RH和1#CAS两个精炼设备)和三重精炼(三重精炼钢水包需经过3#RH、2#CAS和1#KIP三个精炼设备进行处理)[13]。

1.1.3 连铸

高温钢水经过连铸机的处理，将熔融的金属不断浇入结晶器中，冷却后的铸件可通过结晶器的另一端拉出任意长度的铸件，即具有一定钢和规格的板坯。在连铸过程中，需要进行连续浇铸，若不能连续浇铸而产生断浇，会消耗过多的能源和时间。因此，为了提高生产效益、降低生产成本，连铸过程要保持连续浇铸。

1.2 炼钢连铸动态调度问题

炼钢-连铸动态调度问题可以归类为作业车间调度问题[14]。炼钢-连铸生产调度问题实际上是对生产工序中运输时间、生产工艺路径存在的回环和最后阶段是同一炉次连续加工的特殊生产问题[15]。而实际炼钢-连铸生产车间中，在满足生产约束的前提条件下，需实时调整并确定某一炉次在某工序的某台机器上进行加工及其开始时间和顺序，尽可能的缩短炉次在炼钢-连铸生产过程中的总完工时间、总断浇时间、总等待时间和时间偏差量，提高炼钢-连铸生产车间的生产效率，减少生产能耗。

1.3 数学模型

1.3.1 基本假设

炼钢-连铸生产过程是一个集离散和连续相混合的复杂过程。为了解决实际问题，通常使用数学模型对该问题进行描述。为确保生产过程的连续性，在正常的生产情况下，炉次依次在设备间传递且无重叠，连铸机的拉速是恒定的，当遇到不可预测的扰动时，可在合理范围内进行调节连铸机拉速，且有初始调度计划表。

1.3.2 符号定义

其中：

1.3.3 目标函数及约束条件

1)目标函数：

F=f1+f2+f3+f4

(1)

f1=minε1Cmax

(2)

(3)

(4)

(5)

2)约束条件：

(6)

(7)

(8)

∀j∈Ji,k∈Mj,(i,i′)∈{(i,i′)|j∈Ji∩Ji′}

(9)

∀p≠P,m∈Mq

bp=adpq,∀p∈P

(10)

(11)

(12)

(13)

∀i∈I,j∈Jj,m∈Mj,m′∈Mδ(i,j)

(14)

∀i∈I,j∈Jj,m∈Mj

uijmaij≥uijmrm,∀i∈I,j∈Jj,m∈Mj

(15)

(16)

(17)

(18)

(19)

uijm∈{0,1}

(20)

vpm∈{0,1}

(21)

(22)

式(1)表示目标函数由式(2)～(5)组成，其中，式(2)表示最小化总完工时间，式(3)表示最小化总断浇时间，式(4)表示最小化总等待时间，式(5)表示最小化时间偏差量。式(6)表示在生产过程中炉次在各机器上仅可以被分配到一台机器上进行加工；式(7)表示连铸机上的一个浇次在同一时刻仅可以被分配到一台连铸机上浇铸；式(8)表示任意一台机器仅被允许一个炉次进行加工；式(9)表示表示连铸机在同一时刻仅允许一个浇次进行浇铸；式(10)表示连铸机的开浇时间等于该连铸机上第一个炉次开始浇铸的时间；式(11)表示连铸机的结束工作时间是该连铸机上最后一个炉次的浇铸结束时间；式(12)表示在同一个浇次中，后一炉次的浇铸开始时间等于前一炉次在该连铸机上的浇铸结束时间与两个炉次之间的断浇时间的和；式(13)表示某一炉次的下一工序的开始时间等于前一工序的结束时间与工序间的运输时间和等待时间之和；式(14)表示机器发生故障时该时间段内炉次不能在该机器上进行加工；式(15)表示炉次在各工序之间的加工开始时间不小于该机器上上一炉次的结束时间；式(16)表示炼钢-连铸生产调度的总完工时间；式(17)表示炉次在进行下一工序前的可等待时间范围；式(18)表示炉次的加工时间范围；式(19)表示连铸上断浇的时间范围；式(20)表示炉次在工序上可分配到的机器数；式(21)表示浇次可被分配的机器数；式(22)表示对工序的开始加工时间、浇次的开始浇铸时间和浇次的结束浇铸时间没有具体的限制。

2 改进差分进化算法的设计与求解

2.1 差分进化算法基本原理

差分进化算法(DEA，different evolution algorithm)由Storn和Price[16]于1995年提出的一种基于群体的全局优化算法[17]。差分进化算法通过模拟自然界生物种群的生存法则进化发展规律而形成的一种具有随机启发式的搜索算法。差分进化算法中，每个个体都有一个解向量，通过变异操作对种群个体进行差分，并将生成的差分向量与初始基向量进行交叉操作，通过选择操作选取最优个体，并将该最优个体保存至下一代，最终生成新的种群，通过不断的迭代，直到找到最优解。差分进化算法因结构简单、容易实现、鲁棒性强等特点，而被广泛应用于各个领域[18]。

2.2 差分进化算法的基本流程

差分算法的流程如下[19]：

1)设置参数；

2)随机产生初始种群；

3)对初始种群中个体计算适应度值；

4)判断是否达到最大迭代次数。若达到，则结束循环；否则，继续执行操作；

5)对未达到最大迭代次数的种群个体进行变异和交叉操作，将变异向量vi,g与父向基向量xi,g进行交叉操作，得到一个第j维的新个体，交叉操作公式如下：

(23)

其中：CR是交叉概率，jrand是维数[1,D]之间的均匀分布的随机数。

6)将得到的新个体向量与基向量进行选择操作，选取最优个体保留至下一代种群。选择操作的计算公式为：

(24)

7)迭代数加1，转至步骤4)。

2.3 拉格朗日插值

通过对同一物理量进行多个角度观察,可得多个不同的观测值,获得的多个观测值可由一个多项式表示,则该多项式称为拉格朗日插值多项式[20]。即拉格朗日插值是在已知多个坐标点的情况下，通过坐标点获得近似函数的一种建模方法[21]。

拉格朗日插值法基本原理：在需要插值的点附近随机选取若干个合适的点，构造一个简单的插值函数y=q(x)，且该构造的插值函数需通过随机选取的插值点。在所选的插值点区间内将插值函数值作为原函数f(x)的值，使函数f(xi)=p(xi),i=1,2,3,…,n成立。拉格朗日插值法的实质是根据已知的选取的插值点构造一个插值函数，并利用该插值函数快速获取原函数在该插值点上的位置，这种利用多个节点数据来构造插值基函数的方法称为拉格朗日插值法[22-23]。

在区间[a,b]上，有n+1个点x0,x1,…,xn，且过该n+1个点的函数值为y0,y1,…,yn，对这n+1个点，每个xi均可得到其对应的函数值yi，公式如下：

(25)

式(25)中，Ln(x)为拉格朗日多项式；为次数不超过n的多项式，即插值基函数。此时，拉格朗日插值阶数为n，满足如下公式：

(26)

具体计算公式为：

(27)

将式(26)代入式(27)得到n次拉格朗日多项式的计算式为：

(28)

2.4 拉格朗日插值改进差分进化算法

利用拉格朗日插值法构建的近似函数是一个恰好穿过二维平面上若干个已知点的多项式函数，该函数可以通过已知的信息来推测未知信息，获取更优解。已知坐标点(x0,y0),(x1,y1),…,(xD,yD),其中xi为种群个体，yi为种群个体的适应度值。通过已知的多个解建立近似函数，得到n次拉格朗日插值多项式：

(29)

本文取n∈{0,1,2}，代入式中得到抛物线式插值，将其简化成二次函数的数学模型如下：

fn(x)=ax2+bx+c

(30)

式(30)中：a、b及c为方程式的系数，其计算过程分别为:

(31)

(32)

c=c0+c1

(33)

其中：

n0=x0-x1

(34)

n1=x1-x2

(35)

n2=x2-x0

(36)

(37)

(38)

(39)

2.5 自适应调整差分进化算法搜索方向

将当前种群中各个个体进行适应度函数值大小排序，将适应度函数值小的个体放在前面，并将前m(m∈[1,2,…,NP])个个体定义为当前种群的优质解。通过随机选取的种群中的优质解来引导搜索方向，保证了前期种群的多样性，使得迭代后期寻优结果趋于最优解。变异策略DE/rand-to-best/1的具体计算公式如下所示：

(40)

(41)

式(41)中，g表示当前进化代数，gmax表示最大进化代数，s(x)表示大于x的最小整数。m在种群的前期搜索速率较慢，算法可在较大的范围内寻求最优解，增强了算法的局部搜索能力；而在种群后期搜索速率较快，通过优质解中的最优解得到位置分布。当m=1时，xmbest,g=xbest,g为当前种群最优解，算法更倾向于在全局最优解附近搜索，从而加快了算法的收敛速度。

为了利用拉格朗日插值优化差分进化算法搜索局部最优值，本文以当前变异的最优个体和最优个体附近的随机生成的两个个体从而得到3个点x0、x1、x2，其中，x0为最优个体，x1、x2由下列公式生成：

x1=x0-δ

(42)

x2=x0+δ

(43)

δ=a×(rand-0.5)

(44)

其中：a为极小系数，本文设置a=0.01。

利用二次拉格朗日插值可获得一条经过x0、x1、x2三点的二次函数，通过对二次函数的计算可获得全局最优解。为了平衡全局搜索和局部搜索，引入权重w加以控制，权重的计算表达式如下：

(45)

其中：分别设置wmax、wmin为0.9和0.4；t为种群迭代次数；maxDT为当前种群最大迭代次数。w的选取决定了种群的搜索能力，w越小时，其种群的全局搜索能力越强，反之局部搜索能力越强。在拉格朗日插值算法改进差分进化算法的过程中，权重系数w在种群前期的主要是为了扩大种群搜索范围，而在迭代后期，权重系数w的引入能够加快种群的局部搜索速度。

2.6 改进的差分进化算法流程

如图2所示，拉格朗日插值改进的差分进化算法具体步骤如下：

图2 LGDE算法流程图

1)设置算法的种群大小NP，最大进化代数为maxDT以及其他进化参数。初始化种群，计算各个个体的适应度，记录最优个体xbest以及f(xbest)；

2)判断结果是否达到maxDT，若是退出计算，否则，进入步骤3)；

3)计算当前权重w，若w≤0.75，则进入步骤4)，否则进入步骤5)；

4)取xbest和附近两点x1、x2，做拉格朗日插值计算，求得最小值min，计算min的适应度值并与xbest的适应度值相比较，当f(xbest)f(min)，用min替换xbest；

5)使用DE/rand-to-best/1策略进行变异操作；

6)进行交叉和选择操作，并计算种群中每个个体的适应度值，迭代次数加1；

7)判断是否满足结束条件，若是，则结束循环;否则，转至步骤3)。

3 实验结果与分析

表1是某大型钢厂的实际生产数据，包含3个浇次计划、10个炉次计划和两种精炼方式。以表1中的浇次计划进行仿真试验。

表1 浇次计划

将本文所提出的改进的差分进化算法与标准差分进化算法对上述问题求解，设置种群规模为50，变异算子为0.5，交叉概率为0.3，迭代次数为1 000，对数据进行50次独立实验，计算每一代目标函数值，获得折线如图3所示，改进后的差分进化算法的收敛曲线均优于标准差分进化算法的收敛曲线，证明了本文所提的改进后的差分进化算法有较好的收敛性。

图3 改进后的差分进化算法的收敛曲线

在实际的生产车间中，通过对该钢厂实际生产的相关数据的提取，当机器运行至7∶30分时，2#LD转炉突然出现故障，导致后面的炉次不能继续在该转炉上进行加工，需要分配新的转炉，如图4，2#LD转炉出现故障，导致在该转炉上还未开始加工的第7炉次和第4炉次开工延迟，从而导致第7炉次和第4炉次在连铸机上出现断浇，动态调整前的调度甘特图如图4所示。

图4 动态调度调整前的甘特图

通过改进的差分进化算法对原始调度计划进行调整，对故障下导致延迟的第7炉次和第4炉次重新分配新的转炉机器，调整后的甘特图如图5所示。

图5 动态调度调整后的甘特图

通过仿真实验结果显示，本文提出的改进的差分进化算法能够有效解决炼钢连铸生产过程中转炉出现故障的扰动事件，并生成新的较优的调度计划表。

4 结束语

1)针对炼钢-连铸生产动态调度问题，结合某大型钢厂的实际生产车间的数据，以炉次在炼钢-连铸生产过程中最小化总完工时间、最小化总断浇时间、最小化炉次间总等待时间和最小化总偏差量为优化目标，建立了炼钢-连铸动态调度数学模型。

2)在给定原始调度计划表的前提下，提出了以拉格朗日插值改进差分进化算法的方法来求解炼钢-连铸动态调度问题，并提出了自适应调整策略和权重系数的判断，来平衡全局搜索和局部搜索。

3)以某大型钢厂的实际生产数据为研究对象，建立数学模型并进行仿真实验，结果表明，所提出的算法能够有效地缩短炉次在炼钢-连铸生产过程中的总完工时间，当实际生产现场出现扰动事件时，及时响应并做出相应调整，确保了炼钢-连铸生产车间的顺利进行。本文所提的改进的差分进化算法未来可更多应用于多组合多约束优化问题。