第7期 杨业建等：钢还热轧加热炉区生产调度模型与算法 ·843· 提下，首先最小化钢坯温降时间，其次最小化同炉钢 3模型求解 坯离散度 根据以上描述，可以建立加热炉区调度问题的 根据给定时间域内的钢坯信息、轧制计划和铸 数学模型，首先定义如下参数：F={1,2,…m}为加 坯出坯计划，采用上述目标函数和约束条件，求解每 热炉序号集合，共有m座加热炉；Q=（9,92,…, 块钢坯分配的加热炉号、每块钢坯的入炉时间和出 q。)为待加工钢坯的轧制顺序，其中9：为钢坯号，共 炉时间.钢坯加热炉号的选择相对独立且对钢坯的 有n块钢坯；T,为钢坯q:的到达时刻；sg为钢坯q: 入炉时间和出炉时间有一定的决定作用，因此本文 的入炉时刻：e,为钢坯q:的出炉时刻：为所有钢 采用将求解加热炉区生产调度计划转换成求解钢坯 坯总的等待加热时间，min;D为同炉钢坯离散度的 的加热炉号的方式实现加热炉区生产调度，其优化 平均值；a、b和c为权值，且a+b+c=1;σ(T)、 求解过程为：首先确定每块钢坯分配的加热炉号，然 σ(V)和σ(G)分别为加热炉f所加工钢坯的温度 后按照约束条件生成钢坯的入出炉时间以及是否进 分布标准差、体积分布标准差和厚度分布标准差： 钢坯库，通过调整加热炉各段炉温和步进节奏实现 1板坯9：分配给加热炉f加工， 上述目标，最终生成完整的加热炉区调度方案.求 PF{0其他： 解流程如图1所示 h为最小轧制间隔时间，min;ta为钢坯最小加热时 (开始 间，min;tmx为钢坯最大加热时间，min;Ns为加热炉 产生钢还的 可同时加热最大钢坯数；M,为t时刻加热炉f内的 加热炉分配方案 钢坯数 按轧制顺序读取 加热炉调度问题的数学模型可以描述为： 轧制钢坯信总 m店=名 (s-T）, (1) 根据约束条件成 钢坯的入炉出炉时间 0时=ax月b(刀]+6x 判断板坯足否热送热装， 更新加热炉状态 盒（四]+ex月 o(G]. (2) 存人加热炉区调度计划 Subject toe.<eg,若i<j,Hg:g∈Q, (3) 否 是否轧制的 最后一块？ s<sg,若i<j,H9,g∈Q且P时=P时=1，f∈F, 是 生成加热炉区调度计划 (4) 名w 是否达到 (5) 停止条件？ 是 eu1-e≥h,Hg:g5∈Q, (6) 输出结果 tmin≤egu-Sgu≤tmm' (7) 图1调度模型的求解流程 Fig.1 Solving flowchart of the scheduling model My≤Nnx (8) 其中，式(1)表示所有钢坯温降总时间最短；式(2) 在求解过程中，以二进制表示每块钢坯分配的 表示钢坯入炉温度平均离散值、入炉钢坯体积平均 加热炉号，钢坯所分配的加热炉号按照轧制顺序排 离散值和入炉钢坯厚度平均离散值的加权平均值最 列可以组成一个二进制字符串.钢坯炉号选择的这 小；式(3)保证钢坯从加热炉区的出炉顺序与轧制 种二进制描述与逻辑学上的可满足性问题的描述形 顺序相符：式(4)保证在同一加热炉加工的钢坯先 式比较类似，该问题是历史上第一个被证明的NP- 热轧的先入炉；式(5)保证每块钢坯都被分配且只 complete问题.这类问题无法用精确算法求得最 被分配到一个加热炉加工；式(6)保证加热工序出 优解，只能通过启发式或者超启发式算法得到问题 钢的间隔符合热轧机组的要求：式(7)保证钢坯加 的满意解 热时间符合加热工艺要求：式(8)保证加热炉内钢 遗传算法是较早出现的超启发式算法，己被许 坯数不超过最大值. 多应用实例证明是求解组合优化难题的有效算法之第 7 期 杨业建等: 钢坯热轧加热炉区生产调度模型与算法 提下，首先最小化钢坯温降时间，其次最小化同炉钢 坯离散度． 根据以上描述，可以建立加热炉区调度问题的 数学模型，首先定义如下参数: F = { 1，2，…m} 为加 热炉序号集合，共有 m 座加热炉; Q = ( q1，q2，…， qn ) 为待加工钢坯的轧制顺序，其中 qi 为钢坯号，共 有 n 块钢坯; rqi 为钢坯 qi 的到达时刻; sqi 为钢坯 qi 的入炉时刻; eqi 为钢坯 qi 的出炉时刻; t Σ w 为所有钢 坯总的等待加热时间，min; DΣ d 为同炉钢坯离散度的 平均值; a、b 和 c 为权值，且 a + b + c = 1; σ( Tf ) 、 σ( Vf ) 和 σ( Gf ) 分别为加热炉 f 所加工钢坯的温度 分布标准差、体积分布标准差和厚度分布标准差; pqi f = 1 板坯 qi 分配给加热炉 f 加工， {0 其他; h 为最小轧制间隔时间，min; tmin为钢坯最小加热时 间，min; tmax为钢坯最大加热时间，min; Nmax为加热炉 可同时加热最大钢坯数; Mt，f为 t 时刻加热炉 f 内的 钢坯数． 加热炉调度问题的数学模型可以描述为: Min t Σ w = ∑i∈S ( sqi － rqi ) ， ( 1) Min DΣ d = a × ∑ m f = 1 ［σ( Tf ) ］+ b × ∑ m f = 1 ［σ( Vf ) ］+ c × ∑ m f = 1 ［σ( Gf ) ］． ( 2) Subject toeqi ＜ eqj ，若 i ＜ j，qi，qj∈Q， ( 3) sqi ＜ sqj ，若 i ＜ j，qi，qj∈Q 且 pqi f = pqj f = 1，f∈F， ( 4) ∑ f∈F qi∈Q pqi f = n， ( 5) eqi + 1 － eqi ≥h，qi，qj∈Q， ( 6) tmin≤eqi － sqi ≤tmax， ( 7) Mt，f≤Nmax ． ( 8) 其中，式( 1) 表示所有钢坯温降总时间最短; 式( 2) 表示钢坯入炉温度平均离散值、入炉钢坯体积平均 离散值和入炉钢坯厚度平均离散值的加权平均值最 小; 式( 3) 保证钢坯从加热炉区的出炉顺序与轧制 顺序相符; 式( 4) 保证在同一加热炉加工的钢坯先 热轧的先入炉; 式( 5) 保证每块钢坯都被分配且只 被分配到一个加热炉加工; 式( 6) 保证加热工序出 钢的间隔符合热轧机组的要求; 式( 7) 保证钢坯加 热时间符合加热工艺要求; 式( 8) 保证加热炉内钢 坯数不超过最大值． 3 模型求解 根据给定时间域内的钢坯信息、轧制计划和铸 坯出坯计划，采用上述目标函数和约束条件，求解每 块钢坯分配的加热炉号、每块钢坯的入炉时间和出 炉时间． 钢坯加热炉号的选择相对独立且对钢坯的 入炉时间和出炉时间有一定的决定作用，因此本文 采用将求解加热炉区生产调度计划转换成求解钢坯 的加热炉号的方式实现加热炉区生产调度，其优化 求解过程为: 首先确定每块钢坯分配的加热炉号，然 后按照约束条件生成钢坯的入出炉时间以及是否进 钢坯库，通过调整加热炉各段炉温和步进节奏实现 上述目标，最终生成完整的加热炉区调度方案． 求 解流程如图 1 所示． 图 1 调度模型的求解流程 Fig． 1 Solving flowchart of the scheduling model 在求解过程中，以二进制表示每块钢坯分配的 加热炉号，钢坯所分配的加热炉号按照轧制顺序排 列可以组成一个二进制字符串． 钢坯炉号选择的这 种二进制描述与逻辑学上的可满足性问题的描述形 式比较类似，该问题是历史上第一个被证明的 NP￾complete 问题［12］． 这类问题无法用精确算法求得最 优解，只能通过启发式或者超启发式算法得到问题 的满意解． 遗传算法是较早出现的超启发式算法，已被许 多应用实例证明是求解组合优化难题的有效算法之 ·843·