One-Dimensional Cutting Stock Problem with a Given Number of Setups: A Hybrid Approach of Metaheuristics and Linear Programming
One-Dimensional Cutting Stock Problem with a Given Number of Setups: A Hybrid Approach of Metaheuristics and Linear Programming
复制标题
DOI：
10.1007/s10852-005-9031-0
复制
发表时间：
2006-02
期刊：
影响因子：
--
通讯作者：
S. Umetani;M. Yagiura;T. Ibaraki
中科院分区：
文献类型：
--
作者：
S. Umetani;M. Yagiura;T. Ibaraki
一维下料问题是一类典型的组合优化问题，在工业应用中有着广泛的应用。由于切换不同的切割模式的设置成本在最近的切割行业中变得更加占主导地位，我们认为一维CSP的一个变种，称为模式限制问题（PRP），以尽量减少库存卷的数量，同时限制用户给定的范围内的不同切割模式的数量。对于这个问题，我们提出了一个局部搜索算法，交替使用两种类型的局部搜索过程与1-添加邻域和移位邻域，分别。为了提高局部搜索的性能，我们将其与线性规划（LP）技术，以减少在每个邻域中的解决方案的数量。灵敏度分析技术的引入，以解决大量的相关LP问题迅速。通过计算实验，我们观察到，新算法获得更好的质量比其他现有的方法获得的解决方案。
One-dimensional cutting stock problem (1D-CSP) is one of the representative combinatorial optimization problems, which arises in many industrial applications. Since the setup costs for switching different cutting patterns become more dominant in recent cutting industry, we consider a variant of 1D-CSP, called the pattern restricted problem (PRP), to minimize the number of stock rolls while constraining the number of different cutting patterns within a bound given by users. For this problem, we propose a local search algorithm that alternately uses two types of local search processes with the 1-add neighborhood and the shift neighborhood, respectively. To improve the performance of local search, we incorporate it with linear programming (LP) techniques, to reduce the number of solutions in each neighborhood. A sensitivity analysis technique is introduced to solve a large number of associated LP problems quickly. Through computational experiments, we observe that the new algorithm obtains solutions of better quality than those obtained by other existing approaches.