刘志宏 喻晓旭

摘要

切割问题因切割模式数量非常庞大，存在较多局部最优解，被看作一个NP-hard问题。本文所研究的两阶段切割问题是基于无缝钢管制造过程，将无缝钢管的热轧和冷轧过程抽象成一个两阶段切割问题，以对其进行数学建模。同时利用遗传算法求解非线性规划问题的优势，并使用MATLAB工具对遗传算法进行实验模拟仿真，从而得出实验结果数据，经研究显示遗传算法是一种很理想的求解两阶段切割问题的算法。

【关键词】遗传算法 两阶段 切割问题MATLAB

切割问题常见于我国制造业中，包括布料、造纸、玻璃、皮革机、钢铁等行业。根据Dyckhoff的分类方法，切割问题按维度数可划分为一维、二维和三维切割问题。国内就一维切割问题的研究进展较大，目前使用较为广泛的有启发式算法、单纯型算法等，都能取得较好的实验结果，但现有研究对余料控制问题尚有不足。

1两阶段切割问题数学模型

无缝钢管的制造包括两个加工流程：热轧和冷轧。钢管的热轧和冷轧过程非常复杂。在传统一维切割问题中，通常把原材料直接进行一次加工切割，这种方式会产生大量的余料。而两阶段切割是从订单合同交货长度出发，形成一定量的锯切长度管坯，再进行二次切割，从而减少余料的方法。为了便于研究，可把问题简单描述如下：在生产过程中，将原料管坯通过第一阶段热轧，切割成锯切长度;之后将第一阶段的锯切长度钢管进行第二阶段冷轧，从而变成订单合同交货长度钢管，如图1所示。订单合同可根据交货合同长度不同划分为两种，即定尺合同和非定尺合同。定尺合同对钢管的单根交货长度和总交货量进行了明确规定;非定尺只给出了单根管子的交货长度区间和总交货长度。

本文不考虑锯切损失的问题，同时，由于非定尺合同存在较大的不确定性，很难直接进行最优化求解，对此，本文提出一种将非定尺合同转为定尺合同的简单方法，从而将两阶段切割问题转化为直接针对定尺合同问题进行研究。非定尺合同转化为定尺合同的步骤如下.

（1）取出第一个合同，计算出符合交货区间长度的最小根数flmin和最大根数flmax。

（2）根据[flmin，flmax]区间，从小到大顺序依次计算出根数所对应的交货长度，如有符合的交货长度，则结束，若无，则取交货长度十分位最大者，将它作为新的定尺合同长度。

以下给出模型建立的变量定义：

Id，（d∈l…n）：定尺合同集合。If，（f∈1…n）：非定尺合同集合。

Id，（d∈1…n）：定尺合同集合。Li，（i∈Id）：定尺合同交货长度。

DNi，（i∈Id）：定尺合同交货数量。Y∈[Ymin，Ymax]：原料管坯长度。

SL∈[SLmin，SLmax]：锯切长度。

从而可得出两阶段切割问题数学模型：

阶段一：热轧切割模型。模型建立的过程如下：首先，从数据库中取出{Li，DN.}，两个参数以确定第一阶段的切割长度;其次，对数据进行预处理，这个过程对切割数量非常少的合同十分重要;第三，按照定尺合同的长度进行字典排序;第四，根据参数建立切割数学模型，求出SL长度，即第一次热轧的锯切长度。具体模型如下：

SL=∑ni=1aiβiLi，

（1）

具体参数说明如下，DN.表示第个合同的定尺长度，ai是调整系数的权重，ai∈（O，10），表示所占比重，计算公式如下ai=m*Pi，这里m取10，Pi表示第2个长度切割在所有合同占的比重，公式如下：

βi表示是否选择这个做为有效的长度，定义如下：

这个系数通过对于DN，的排序进行选择。

阶段二：冷轧切割模型。模型建立过程如下：从数据库中取出{Li，DNi）两个参数，根据上述计算出的锯切长度SL，以求解余料最少为最终问题。

min f（1，x），其中1表示SL，x是一组向量，表示定尺长度L.，表达式如下：

f（l，x）=∑i（l-∑，xi Li），

（3）

S.T. l-∑ixiLi>o，

（4）

实际上就是切割1分成定尺长度Li，属于带约束的线性规划问题，xi的确定方法同上。

2遗传算法

遗传算法通过模拟人类进化论的自然选择和遗传学机理的生物进化过程所建立的计算模型，并通过不断的自然进化搜索最优解的方法。遗传算法常用于求解线性规划方面的问题，其主要步骤如下：

（1）编码。

（2）初始化种群。

（3）评估个体适应度。评估种群中所对应个体的适应度。

（4）選择。参照适应度函数，遵照适应度越高，选择概率越大的原则，从种群中选择两个个体作为父方和母方。

（5）交叉。将父方和母方染色体进行交叉，产生新的子代。

（6）变异。对子代染色体进行变异。

（7）演化。重复3/4/5/6步骤，直至产生新的种群。

（8）结束。3实验仿真

由于两阶段问题可行性解数量较大，当合同数量达到50个时，切割模式数量可达到700多种，迭代次数3275次。原料管坯长度lOOOmm，本次仿真取3个合同集，具体参数如表l所示。

在实验仿真时，使用MATLAB进行实验仿真，该软件自带遗传工具箱，通过迭代不断逼近最优解。

上述最优解为：原料管坯共使用47根，锯切长度为500mm，一共需锯切94根锯切长度，余料为1650mm，余料比率为3.5106%。

4结论

两阶段切割问题是公认的NP-hard问题，存在大量的局部最优解，在第三部分的实验仿真阶段可以看出，遗传算法可以很好地解决两阶段切割问题中最优解问题，同时计算效率较高，余料控制比较理想。由于合同问题中的非定尺合同长度具有较大的不确定性，本文通过把非定尺合同定尺化的方法，将难点进行转移。这一做法在寻找最优解的过程中是非常关键的一步。

参考文献

[1] Dyckhoff， H.A typology of cuttinga packing problem[J]. EuropeanJournal of Operational Research，1939 （44）：145 -159.

[2]刘桂林，钢管生产短尺寸合同与非定尺合同组批优化算法[J].宝钢技术，2007 （02）： 42-44.

[3]王紫萍，线材下料问题

目标函数的一个注记[J]，中国科技信息，2008 （21）.