On the one-dimensional stock cutting problem in the paper tube industry
On the one-dimensional stock cutting problem in the paper tube industry
复制标题
浅谈纸管行业的一维坯料切割问题
DOI：
10.1007/s10951-010-0164-2
复制
发表时间：
2012
影响因子：
2
通讯作者：
H.Nagamochi
中科院分区：
文献类型：
--
作者：
K.Matsumoto;S.Umetani;H.Nagamochi
一维下料问题（1D-CSP）是一类典型的组合优化问题。虽然1D-CSP的主要目标是最大限度地减少使用的库存卷的总长度，但近年来切割过程的效率变得更加重要。切割过程的关键瓶颈经常发生在半自动化制造商的处理操作中，例如纸管行业。为了减少纸管行业中处理操作的中断和错误，我们考虑了1D-CSP的变体，该变体最大限度地减少了所使用的储料卷的总长度，同时限制（C1）每种储料卷类型的设置数量，（C2）同时出现在开放堆叠中的件长度的组合，以及（C3）开放堆叠的数量。对于这个问题，我们提出了一个泛化的切割模式称为“切割组”，这是一个序列的切割模式，满足给定的上限设置的每个股票卷类型和开放堆栈。为了生成良好的切割组，我们分解的一维CSP到一些辅助装箱问题。提出了一种基于移位邻域的禁忌搜索算法，该算法采用首次拟合递减启发式算法求解辅助装箱问题。实验结果表明，我们的算法提高了解决方案的质量相比，现有的算法在纸管厂使用。
The one-dimensional cutting stock problem (1D-CSP) is one of the representative combinatorial optimization problems which arises in many industrial applications. Although the primary objective of 1D-CSP is to minimize the total length of used stock rolls, the efficiency of cutting processes has become more important in recent years. The crucial bottleneck of the cutting process often occurs at handling operations in semiautomated manufacturers such as those in the paper tube industry. To reduce interruptions and errors at handling operations in the paper tube industry, we consider a variant of 1D-CSP that minimizes the total length of used stock rolls while constraining (C1) the number of setups of each stock roll type, (C2) the combination of piece lengths occurring in open stacks simultaneously, and (C3) the number of open stacks. For this problem, we propose a generalization of the cutting pattern called the “cutting group,” which is a sequence of cutting patterns that satisfies the given upper bounds of setups of each stock roll type and open stacks. To generate good cutting groups, we decompose the 1D-CSP into a number of auxiliary bin packing problems. We develop a tabu search algorithm based on a shift neighborhood that solves the auxiliary bin packing problems by the first-fit decreasing heuristic algorithm. Experimental results show that our algorithm improves the quality of solutions compared to the existing algorithm used in a paper tube factory.