0 引言

下料问题广泛存在于各类制造业中。在需要进行材料分割的情况, 企业为了降低成本, 提高自身竞争力, 需要高利用率的下料方案。一维下料问题(one-dimensional cutting stock problem, 1DCSP)是将长度已知的一维原材料(线材)切割成较小的长度和需求量已知的毛坯, 并最小化所需线材的数量或价值问题。一维下料问题主要有两种求解方法:列延迟生成法(Delayed Column Generation)为下料问题建立线性规划模型并求解^[1-5]; 顺序启发式算法(Sequential Heuristic Procedure, SHP)顺序地生成每个排样图并形成下料方案^[6-10]。SHP具有结构清晰、易于实现、容易针对次要优化目标进行改正等优点, 但其贪婪性导致存在局部最优问题。Belov和Scheithauer^[11]将顺序价值校正(sequential value correction, SVC)与SHP相结合, 通过在每次迭代后修改毛坯的价值, 增加下料方案的多样性, 以跳出局部最优。Cui等^[12]在生成下料方案过程中只选择剩余毛坯的一个子集来生成当前排样图。Cui和Tang^[13]将SVC用于求解多线材一维下料问题。启发式算法所用的启发式一般只适用于特定的问题, 无通用性, 有效的启发式对问题的求解是很有用的, 但是有时寻找一个有效的启发式比解决问题本身还要困难^[14]。此外, 近年来也有研究者将智能算法应用在一维下料问题求解中^[15-17]。

在实际生产中存在着特殊的一维下料问题, 有顺序依赖损耗的一维下料问题(1DCSP with sequence-dependent cut losses, 1D-CSP with SDCL)^[18]出现在木工行业, 其特殊性在于需要从一维线材上切出带有斜角的零件, 此时不同的毛坯顺序会导致切割损耗的不同。本研究根据有顺序依赖损耗的一维下料问题的特征, 采用SVC框架求解此问题, 可以加快排样图生成过程, 提高材料利用率与生产效率。试验结果表明:与其他算法相比, 本研究算法总体上能够生成利用率更高的下料方案。

1 数学模型

有顺序依赖损耗的一维下料问题, 指在一维的排样图内, 在每两个相邻的毛坯之间或毛坯与首尾两端之间可能会出现一种损耗, 这种损耗与排样图中毛坯排列的顺序相关。

设待切割的毛坯集合为I={1, …, m}, 每种毛坯i∈I具有长度l_i与需求d_i, 线材长度为L且I中任意l_i < L。每两种毛坯i与j之间存在切割损耗c_ij, 每种毛坯与线材开头之间有切割损耗c_0i, 与线材结尾之间有损耗c_i0。可行的排样图P为集合I的子集, 其中的毛坯长度加上损耗总和不大于线材长度L, 该子集可以包含重复的毛坯。设T为使用线材的总根数, n_ik为第k个排样图中含毛坯i的个数, f_k为第k个排样图重复次数(i∈I, k=1, …, K), 可以建立如下整数规划模型:

$ \left\{ \begin{array}{l} \min T = \sum\limits_{k = 1}^K {{f_k}} \\ {\rm{s}}{\rm{.t}}{\rm{.}}\;\;\sum\limits_{k = 1}^K {{n_{ik}}{f_k} \ge {d_i}, i = 1, \cdots, m} \end{array} \right.。$

(2)

将梯形毛坯去掉斜角之后的长度作为毛坯的标准长度l, 并将斜角与其他切割损耗一起视为损耗, 可以计算得出每种毛坯两端与任意毛坯或线材两端相邻时的切割损耗。若不计切割造成的损耗, 设毛坯两端的斜角分别为p_i和q_i, 则c_ij=max(q_i, p_j)。图 1说明带斜角毛坯进行一维排列产生的损耗。

问题的求解目标为生成一个下料方案(包含若干个排样图), 用所提供的线材生产出满足需求量的毛坯, 使所用的线材数量尽量少。

2 算法实现 2.1 算法思想

与列延迟生成法相比, 顺序启发式算法虽然不一定能求得最优解, 但是其结构简单、运算时间短, 更适用于较大规模的实际生产问题, 也更适合处理生产中出现的次要优化目标。经过优化后的顺序法运算结果已经能很好的逼近最优解, 结合以上优点, 使用顺序启发式算法更加符合本研究实际问题的需要, 故选用顺序启发式算法的框架求解有顺序依赖损耗的一维下料问题。

传统的SHP方法首先生成单个排样图, 顺序生成直至没有剩余毛坯为止, 即可得到下料方案。但由于总是先选取价值最高的排样图, 最后剩下的毛坯往往不易形成利用率高的排样图, 导致最后的排样图材料利用率偏低。为此引入价值校正, 令下料方案多元化, 有利于获得更加合适的下料方案。SVC框架的特点包括多代、顺序、价值修正^[19]。

由于继承了SHP简明易于实现的特点又规避了其缺陷, SVC框架在求解下料问题中得到广泛应用。

2.2 算法框架

定义G为当前迭代次数; G_max为最大迭代次数; m为毛坯种数; L为线材长度; l为毛坯长度集合, l={l₁, …, l_m}, 其中l_i为第i种毛坯的长度; V为毛坯价值集合, V={v₁, …, v_m}, 其中v_i为第i种毛坯的价值; D为毛坯总需求量集合, D={d₁, …, d_m}, 其中d_i为第i种毛坯的总需求量; R为毛坯剩余需求量集合, R={r₁, …, r_m}, 其中r_i为第i种毛坯的剩余需求量; N为毛坯数量集合, N={n₁, …, n_m}, 其中n_i为当前排样图中排入的第i种毛坯的数量; f为当前排样图的重复使用次数。

算法步骤如下:(1)令G=1, 并调用2.3节所述价值初始化函数初始化各毛坯的价值。(2)若G>G_max, 则转步骤(8);否则令R=D。(3)调用2.4节所述的排样图生成函数, 生成当前排样图, 并令$f = \min \left\{ {\lfloor {{r_i}/{n_i}}\rfloor|{n_i} > 0\Lambda i \in \left( {1, \cdots, m} \right)} \right\}$。(4)将当前排样图加入当前下料方案, 并更新剩余需求:令r_i=r_i-fn_i, (i=1, …, m)。(5)调用2.5节所述价值修正函数修正各毛坯价值。(6)如果存在i∈{1, …, m}, 使r_i>0, 则转步骤(3)。(7)若当前下料方案使用的线材数量小于目前最优方案, 则将当前下料方案作为最优下料方案。令$G \Leftarrow G + 1$, 转步骤(2)。(8)输出最优下料方案。

整个算法的时间复杂度由时间复杂度最高的排样图生成函数决定。

2.3 价值初始化函数

毛坯初始价值一般情况下可以取v_i=l_i, (i=1, …, m); 但是由于SHP的贪心特性, 这种初始化方法有所不足。在生成下料方案的后期, 容易出现还有较多剩余的长毛坯, 却缺乏短毛坯的情况, 导致最后剩下的毛坯难以组合成利用率高的排样图。此时适当增加长毛坯的价值, 提升其排入的优先级, 令较长毛坯的需求能够更早得到满足。

计算初始毛坯价值的公式^[20]为

$ {v_i} = \left\{ \begin{array}{l} \lambda {l_i}, \;{l_i} \ge 0.5L\\ \;\;\;\;\;\;{l_i} \end{array} \right., $

(3)

式中:λ为大毛坯价值增长参数, 令$\lambda \gg 1$使长毛坯价值明显增大。

2.4 排样图生成函数

定义F(x)是长为x的线材上所含毛坯的总价值; n_i(x)是长为x的线材上含第i种毛坯的个数; j是长为x的线材上排入的倒数第二个毛坯号; c_ij是毛坯i与j之间的切割损耗; c_i0是毛坯i在线材末尾时右端的切割损耗; x₀是从长为x的线材上去掉线材末尾的毛坯i后剩下的长度, x₀=x-c_ji-l_i-c_i0+c_j0, 计算示意图如图 2所示。

生成下料方案, 可以采用第1节所述整数规划模型求解。但考虑计算效率, 采用非精确的解法。有如下动态规划递推式

$ \left\{ \begin{array}{l} F\left( x \right) = 0, \;\left( {x = 0, \cdots, L} \right)\\ {n_i}\left( 0 \right) = 0, \left( {i = 1, \cdots, m} \right)\\ F\left( x \right) = \max \left\{ {F\left( {x- 1} \right), \max \left[{{v_i} + F\left( {{x_0}} \right)|} \right.} \right.\\ \;\;\;\;\;\;\;\;\;\;\;\left. {\left. {{x_0} \ge 0 \cap {n_i}\left( {{x_0}} \right) < {r_i}} \right]} \right\} \end{array} \right.。$

(4)

因其具有全容量特性, 一旦计算出F(x), 对于所有x∈[0, L], F(x)的值都可以确定。尝试每个长度每种可排入的毛坯, 选取价值最大的排样方式作为当前排样图, 算法时间复杂度为O(mL)。

2.5 价值校正函数

价值校正是SVC框架的精髓所在, 通过在每次生成排样图时改进毛坯价值, 使每次迭代生成的下料方案有所不同, 达到搜索更高质量解的目的。本研究采用如下价值修正公式^[20]:

$ {v'_i} = {g_1}{v_i} + {g_2}{\left( {{l_i}} \right)^p}/u, \left( {i = 1, \cdots, m} \right), $

(5)

$ {g_2} = \frac{{\mathit{\Omega} {n_i}}}{{{d_i} + {r_i}}}, {g_1} = 1-{g_2}, $

(6)

$ u = \left( {\sum\limits_{i = 1}^m {{l_i}{n_i}} } \right)/L, $

(7)

式中:p(p>1)与Ω为参数; u为当前排样图的材料利用率。根据式(5), 新的毛坯价值v′_i由两部分组成:第一部分由毛坯之前的价值决定, 系数为g₁; 第二部分由毛坯长度与当前排样图利用率决定, 系数为g₂。p表示毛坯长度在价值计算中的比例。越长的毛坯越难与其他毛坯结合形成利用率高的排样方式, 因此令p>1以增加长毛坯排入的优先级。g₁与g₂则决定了两部分价值的比例, 由毛坯的需求量、总需求量与出现次数和参数Ω决定。

3 试验结果 3.1 试验环境

采用Java语言进行编程, 试验用计算机配置为Intel Core i5-6500 CPU, 3.20 GHz主频, 8 GB内存, 系统为Windows 7旗舰版SP1, 64位。所有例题的试验参数中Ω=0.3, p=1.05, λ=10。

3.2 试验结果

采用文献[18]给出的例题, 例题由随机生成的线材长度L、各毛坯长度l={l₁, …, l_m}、各毛坯需求量D={d₁, …, d_m}、起始端切割损耗C_start={c₀₁, …, c_0m}、末端切割损耗C_end={c₁₀, …, c_m0}和损耗矩阵$\mathit{\boldsymbol{C}} = \left[{\begin{array}{*{20}{c}} {{c_{11}}}& \cdots &{{c_{1m}}}\\ \cdots&\cdots&\cdots \\ {{c_{m1}}}& \cdots &{{c_{mm}}} \end{array}} \right]$的数据组成, 分为两组。例题相关的参数如下:定义Q为生成例题时, 毛坯长度分布的期望值; N为单个例题中需要的毛坯数总和; C₁为例题组1中的损耗值区间, 其中G表示损耗值区间为15~45, D表示5~15, C₂为例题组2中的损耗值区间, x表示损耗值区间为1~1+x, x=0, 1, 2, 3, 4;L_LB为使用列生成法^[21]计算得出的该组例题的线材消耗根数均值下界^[18]; L_HSD为文献[18]提供的算法得出的线材消耗根数均值; L_SVC为本研究算法得出的线材消耗根数均值; t为本研究算法计算该组例题的平均时间。

例题分为两大组。第1组根据Q、N、C的不同分为30个小组, 每组5个例题, 共150个例题。第2组固定N=100, 毛坯长度为100~150, 根据C₁分为5个小组, 每组5个例题, 共25个例题。第2组例题的特点为损耗很小。

图 3为例题组1的一个例题(Q=80, N=25, C₁=D)计算结果的截图。该例题的具体数据为:L=1 000, l={71, 76, 76}, D={8, 9, 8}, C_start={10, 12, 10}, C_end={13, 14, 7}, $\mathit{\boldsymbol{C}} = \left[{\begin{array}{*{20}{c}} {11}&5&5\\ {14}&{11}&6\\ {14}&9&{14} \end{array}} \right] $。图中, 毛坯上的数字为该毛坯的序号。

试验数据见表 1~4, 其中L_LB列中“-”表示文献[21]的算法无法在规定时间内算出下界。表中L_SVC列数据与L_LB列持平者使用加粗文本, 低于L_HSD者使用斜体。

3.3 结果分析

在例题组1中, 当Q=80时, 本研究算法计算的线材消耗量在10组数据中有6组达到下界, 9组与L_HSD持平, 1组数量超过L_HSD; Q=125时, 有3组的线材消耗量达到下界, 7组与L_HSD持平, 3组少于L_HSD; Q=170时, 有4组的线材消耗量达到下界, 5组与L_HSD持平, 5组少于L_HSD。例题组2中, 本研究算法的线材消耗量全部达到下界, 5组中有4组少于L_HSD。两组例题合计35小组中, 本研究算法的线材消耗量有18组达到下界, 12组线材消耗量少于L_HSD, 1组超过L_HSD。

以上数据说明本研究算法总体来说可以较有效的节约材料。在Q相对较大以及损耗值较低时, 本研究算法比文献[18]中的算法更为有效。图 4对算法效果进行直观的说明。

由图 4可知:在毛坯长度分布期望值较大、损耗值低的情况下, 本研究所提方法在节省线材方面的优势。其中没有下界的情况以两种算法较低者作为下界。

4 结语

本研究提出一种采用SVC框架解决工业应用中的特殊下料问题——顺序依赖损耗的一维下料问题的算法, 通过与提出该问题的文献的算法进行对比, 说明应用本研究算法可以更有效降低材料消耗。针对毛坯长度分布期望值较小的情况作进一步优化、参数的调整、余料的利用以及排样图数目等次要优化目标可以作为今后的研究方向。