钢铁企业坯料设计问题模型及算法

[摘 要] 针对钢铁企业的坯料设计问题，建立了数学模型。针对模型特点，以标准粒子群算法为求解框架，通过线性加权法将多目标化为单一目标，引入基于三角函数的动态参数选择方法和邻域搜索以提升求解效率，设计了邻域搜索机制以提升求解效果。通过对比实验对算法的有效性进行了验证。

[关键词] 钢铁生产；坯料设计；粒子群算法；邻域搜索；动态参数选择

doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2012 . 23. 034

[中图分类号] TP27 [文献标识码] A [文章编号] 1673 - 0194（2012）23- 0053- 04

1 引 言

在市场需求日益多样化和钢铁生产工艺逐步柔性化的影响下，大规模定制生产已经成为钢铁企业的主要发展方向[1-3]。在大规模定制生产中，坯料设计处于连接客户需求和企业生产计划的核心地位。在钢铁企业的生产流程中，钢水通过精炼和连铸等工艺形成各类钢坯，钢坯通过轧制形成各类钢铁产品。所谓坯料设计就是针对需求各异的客户订单，在满足生产工艺要求的前提下，将基于量的产品需求转化为基于件次的坯料需求，以便于生产计划的编制，实现客户需求与生产组织的统一。

客户订单中对钢铁产品的要求主要有交货日期、钢种、重量、规格等，针对不同的订单要求，国内外学者提出了各自的问题模型以及求解方法。针对重量要求为固定值，客户订单分配过程中有最小重量限制的问题，张文学 等[4]建立了以最小化板坯数量为目标的约束满足模型，给出了变量选择策略和值选择策略，提出了基于约束满足技术的求解算法。针对重量要求为固定值，宽度和厚度要求为区间值的问题，Lee Kangbok等[5]将坯料设计问题归结为基于区间图的团划分问题，并提出了相应的算法进行求解。席阳 等[6]建立了最小化板坯数量和总盈余量的多目标板坯设计模型，并提出了一种两阶段算法对问题进行求解，其中第一阶段实现板坯数量最小的约束，第二阶段在满足第一阶段的基础上使板坯的盈余量最小；并在文献[7]中增加了最小加工重量的约束条件，并用粒子群算法对问题模型进行了求解。针对客户订单重量需求为固定值的问题，Antoine Gargani等[8]提出了基于全局和逻辑约束的，将具体的变量和值选择策略植入到深度搜索的问题求解模型，并通过使用大规模邻域搜索提升了求解速度。Hentenryck P. Van等[9]提出了一种打破对称性的搜索方法，此方法在不使用大规模邻域搜索的基础上，保证了求解方法的完整性和高效性。Dawand Milind等[10]建立了以板坯数量和总盈余量最小为优化目标的数学模型，并提出了一种基于匹配和装箱的启发式算法对问题进行求解。针对订单要求重量和宽度均为区间值的问题，张英杰 等[11]提出了基于合同—板坯矩阵的启发式算法。

本文考虑订单需求重量和规格为区间值，且具有最小加工重量限制的坯料设计问题，建立兼具一般性和特殊性的数学模型，采用改进的粒子群算法进行求解。

2 数学模型

对钢铁企业而言，客户订单对产品提出的要求有钢种、重量、最小加工重量、规格、交货日期等。对于不同类型的钢坯，其规格也有所不同，比如圆坯规格为直径，矩形坯则为宽度和厚度。坯料设计通常考虑钢坯与钢材之间的规格对应，钢种和交货日期等不在设计范围内，所以本文中客户订单对产品的约束主要包括订单需求重量、最小加工重量、订单规格3个方面，具体如下：

（1）客户订单的需求重量为区间值；

（2）最小加工重量为固定值，此值的设置是为了满足工艺要求；

（3）客户订单的规格要求为区间值。

坯料设计问题应追求以最少的坯料供应满足最多的订单需求，体现精益制造和精益管理的理念。

为了便于描述，对符号定义如下：

集合和索引

i：订单序号，i∈N+；j：坯料序号，j∈N+；O：订单集合，O={1，2，…，i，…，m}；S：坯料集合，S={1，2，…，j，…，n}。

参数

Gi：订单i的需求重量，为区间值，Gi=[ai，bi]，ai，bi∈Z+；Wi：订单i的需求规格，为区间值，Wi=[li，ri]，li，ri∈Z+；mi：订单i要求的最小加工重量，mi∈Z+；W：铸造临界值，即坯料的最大重量；Ωi：订单i的可容多元坯集合；Ω：所有订单的可容多元坯集合元素的集合。

变量

xij：坯料j中包含的订单i的重量，xij∈Z+；rwij：订单i在坯料j中的实际规格，rwij∈Z+。

2.3 模型建立

基于上述问题描述和符号说明，建立坯料设计问题的多目标优化模型[BD]如下：

maxF1=■■xij（1）

minF2=■（2）

s.t.

mi≤xij≤W，？坌i∈O，？坌j∈S（3）

0≤■xij≤W，？坌j∈S（4）

ai≤■xij≤bi，？坌i∈O（5）

li≤rwij≤ri，？坌i∈O，？坌i∈S（6）

rwuj=rwvj，？坌u，v∈O，Wu∩Wv≠？准（7）

上述数学模型中，目标函数（1）是最大化坯料中包含的所有订单的重量和；目标函数（2）是最小化坯料的数量；约束（3）是坯料j中包含的订单i的重量在订单i要求的最小加工重量和铸造临界值之间；约束（4）是每个坯料中包含的所有订单的分配重量之和小于铸造临界值；约束（5）是订单i分配到坯料j中的重量要在该订单的要求重量区间中；约束（6）是订单i中的设计规格必须在其要求的宽度区间内；约束（7）是分配到同一块坯料中的各个订单的规格应相同。

3 模型分析

根据坯料中包含订单的数目，将坯料划分成两类：单一坯和多元坯。单一坯是指此坯料中仅仅包含一个订单并且订单在此坯料中的重量恰恰为铸造临界值。多元坯是指此坯料中包含一个或是多个订单并且所包含订单要求的重量之和可以小于或是等于铸造临界值。通过定义可知，多元坯在满足订单的前提下，可能会产生盈余，此盈余可以作为库存。

多元坯的最大数目等于订单的数量，且每种多元坯的规格是固定的，即为将订单按照需求规格区间的上限排列后，相应序号订单上限的数值。很显然，一种坯料并不能包含全部的订单，一个订单也不能分配到任意的坯料中。本文定义订单可以分配到的多元坯的集合为订单的可容多元坯集合。令r0=l1，则订单i的可容多元坯集合Ωi可定义如下：

Ωi={Sj|li≤rj，ri≥rj-1，？坌i∈O，？坌j∈S}

模型[BD]为多目标优化模型，因此需要按照一定的规则将两个函数合二为一。通常，将多目标划一的方法有线性加权法、理想点法、功效系数法等，本文选择简单实用的线性加权法。其基本思想是根据各个分目标的重要程度和数量级给出一组加权因子，取经过无量纲化的分目标函数和相对应加权因子的线性组合，构成一个新的统一的目标函数。同时，由于一组订单的单一坯的数量是固定的，故目标函数F1化为最大化多元坯处理重量，F2转化为最小化多元坯数目。

目标函数F1=■■xij，进行无量纲化后转化为：

F1*=■■

目标函数F2=■ ，进行无量纲化为：

F2*=■

按照决策者的偏好和企业的实际情况给两个目标函数赋权重ω1和ω2，且ω1+ω2=1，因此原问题的目标函数可以转化为如下的单目标函数：

maxF=F1*ω1-F2*ω2，i∈O，j∈Ω（8）

4 求解算法

此问题是一个具有团划分问题NP完全性质的问题，因此本文选用粒子群算法（Particle Swarm Optimization， PSO）为求解方法的核心，以期在合理时间内获得满意解。粒子群算法源于对鸟群捕食行为的研究，其基本思想是通过群体中个体之间的协作和信息共享来寻找最优解。作为一类随机性较强的群体智能算法，粒子群算法的应用需要解决几个主要问题，即编码方案、初始化方案、种群更新机制和终止条件。此外，为了更有效地求解坯料设计问题，本文有针对性地设计了邻域搜索机制以提升求解效果，采用了动态参数选择机制以提升求解效率。

4.1 编码方案

编码方案是一种将问题空间映射到具有某种结构的表示方法，根据前述定义，可以将所有订单的多元坯集合中元素的顺序排列作为粒子的编码：（（x11…x1j）（x21…x2j）…（xm1…xmj））。

4.2 初始化粒子群

首先将订单中包含的单一坯的数量求解出来，并更新订单中的要求重量区间为Gi*=[ai*，bi*]，按照上述规则进行粒子编码，最后对粒子赋初始值（iter=0）。其中：

ai*=ai-W ■，ifai-W ■ >00，else（9）

bi*=bi-W ■（10）

速度的初始值为：

vhij0=rand（vmax）（rand表示[0，1]之间的随机数）（11）

4.3 种群更新

一般情况下适应度应为目标函数的值，但在本文讨论的问题中，粒子更新过程中产生的新的位置可能不满足约束条件，所以增加惩罚值punish，对不满足的粒子位置进行惩罚，惩罚值的计算公式如下：

punish=κ■xij-bi*（xhij-mi）+（12）

其中（x）+=max（x，0），κ为一个很大的实数。加上惩罚值的适应度计算函数为：

Fitness（xhij）=F1ω1-F2ω2+punish （ω1+ω2=1）（13）

本文中用pbesthiter表示第h个粒子在第iter代的最优位置；用gbestiter表示截止到第iter代，整个粒子群经历的最优位置。h∈[1，H]，h∈N，H为种群粒子数量。iter≤maxiter，maxiter为算法的最大迭代次数。其中：

pbesthiter=pbesthiter-1，if（Fitness（xhiter）

gbestiter=pbesthiter-1，if（Fitness（gbestiter-1）

4.4 邻域搜索

邻域的确定根据下面两个原则：

（1）当前粒子附近可以使坯料处理总重量增加的粒子；

（2）当前粒子附近不增加坯料数目的粒子。

上述两个规则产生的粒子集合的交集即为当前粒子的邻域，邻域若不为空集，则从邻域中任取一个元素作为邻域粒子，用nxhiter表示第h个粒子在第iter代的邻域粒子，并将邻域粒子nxhiter的取值赋给当前粒子xhiter，然后进行全局和局部最优位置的更新。

4.5 参数选择

速度和位置的更新，按照如下公式：

vhij（t+1）=uvhij（t）+c1rand（pbesti-xhij（t））+c2rand（gbesti-xhij（t））（16）

xhij（t+1）=xhij（t）+vhij（t+1）（17）

其中，i∈O，j∈Ωi；u为惯性因子，是使粒子保持着运动惯性，具有搜索新的区域的能力；c1和c2是学习因子，分别代表将每个粒子推向自身最优位置pbesti和全局最优位置gbesti的加速权值；通过调整惯性因子和学习因子可以改变算法的全局和局部搜索能力。vmax为最大速度，当更新后的速度绝对值超过最大速度时，正数取最大速度，负数取最大速度的相反数。参数u、c1和c2取值参照参考文献[12]中提供的方法，即通过三角函数动态改变参数的值，使结果与实际搜索过程特点更加吻合。

4.6 终止条件

在进化类算法中，终止准则一般为预先设定一个最大迭代次数或是规定适应值稳定的代数。本文中，设置最大迭代次数maxiter，每更新一代粒子，都检查是否达到了终止条件，若iter=maxiter，则算法结束，输出gbestiter和Fitness（gbestiter），否则继续进行更新。

5 数据实验

算法参数设置为maxiter=200，H=150，vmax=20，ω1=0.7；订单数据源自文献[7]。算法程序由Eclipse Java EE IDE for Web Developers，Version： Helios Service Release 1实现，实验环境：CPU为AMD Turion（tm） X2 Dual-Core Mobile RM-72 （2 CPUs），2.1GHz，3.00G RAM。

本文算法（BD-PSO）实验结果与与文献[7]算法（SD-PSO）结果对比如表1所示，其中，处理百分比等于多元坯处理的重量除以订单要求重量上限减去单一坯重量。

从与文献[7]中算法的对比结果可以看出，本文的优化算法在处理单一坯和多元坯中都有明显优势，但多元坯存在剩余，这将是下一步研究的优化方向。

6 结 论

本文在考虑钢铁企业客户订单需求和工艺能力的基础上，建立了坯料设计问题的数学模型。针对模型特点，以标准粒子群算法为求解框架，通过线性加权法将多目标化为单一目标，并引入基于三角函数的动态参数选择方法和邻域搜索，提高算法的求解效率。最后的数据实验结果表明，本文提出的模型和求解方法可行、有效。

主要参考文献

[1]刘相华，王国栋，杜林秀，等. 钢材性能柔性化与柔性轧制技术[J]. 钢铁，2006，41（11）：32-36，62.

[2]A Balakrishnan，J Geunes. Production Planning with Flexible Product Specifications： An Application to Specialty Steel Manufacturing [J]. Operations Research， 2003， 51（1）： 94-112.

[3]周世春，丁建华，陈超，等.“大规模定制”生产模式在钢铁企业的应用实践[J]. 中国工程科学， 2006， 8（3）： 1-6.

[4]张文学，李铁克. 基于约束满足的板坯设计模型与求解方法[J]. 北京科技大学学报， 2011（5）：641-646.

[5]Lee Kangbok， Chang Soo Y， Hong Yushin. Continuous Slab Caster Scheduling and Interval Graphs[J]. Production Planning and Control， 2004， 15（5）：495-501.

[6]席阳， 李铁克. 针对固定重量板坯的板坯设计优化算法[J]. 北京科技大学学报，2008，30（10）：1179-1183.

[7]席阳， 李铁克. 基于粒子群算法求解区间值板坯设计优化问题[J]. 计算机工程与应用，2008（3）：205-209.

[8]Antoine Gargani， Philippe Refalo. An Efficient Model and Strategy for the Steel Mill Slab Design Problem[C]//Proceeding of the 13th International Conference on Principles and Practice of Constraint Programming. Springer-Verlag，2007：77-89.

[9]P V Hentenryck，L Michel. The Steel Mill Slab Design Problem Revisited[C]//Proceedings of CPAIOR，2008： 377-381.

[10]Dawande Milind， Kalagnanam Jayant， Lee Ho Soo， et al. The Slab-Design Problem in the Steel Industry [J]. Interfaces， 2004， 34（3）： 215-225.

[11]张英杰， 席阳， 李铁克. 考虑属性区域值的板坯设计模型与算法[J]. 铸造技术，2008，30（7）：945-948.

[12]Zhang Wenxue， Li Tieke， Shi Cantao. Dynamic Parameter Selection Based on Trigonometric[C]//Proceedings of the 2010 Third International Joint Conference on Computational Science and Optimization，2010.