郝信烨 刘懋圻 张灿荣 郑力











摘 要:本文基于某家具厂实际生产场景,在大规模下料问题中考虑了成批供料等现实生产因素。我们建立了Kantorovich模型,其对应的算例具有规模大、解空间对称等特点,难以直接求解。为了解决计算困难,基于Dantzig-Wolfe框架将其分解,并通过列生成求解线性松弛主问题得到较紧的下界。通过对子问题的结构分析,将其分解为可独立求解的二级子问题。基于归并且还原设计了三种子问题求解方式,有效缩减了子问题求解规模,并克服了解空间对称性,进而加速列生成迭代。基于工厂实际数据进行数值实验,结果表明:本列生成启发式算法优于商用求解器CPLEX,其在较短计算时间内得到高质量的解。相比于工厂现行算法,本算法降低10.43%的下料浪费。
关键词:板材下料;成批供料;大规模混合整数规划;列生成;归并且还原
中图分类号:TB114.1 文献标识码:A 文章编号:2097-0145(2022)01-0009-08 doi:10.11847/fj.41.1.9
Abstract:This paper stems from a real production research. It studies a large-scale cutting stock problem considering batch feed and some other constraints based on the real production. We establish a Kantorovich model, the instances corresponding to which are hard to solve due to the large scale and symmetry in the solution space. To tackle the computational difficulty, we decompose it based on the Dantzig-Wolfe framework, and solve the linearly-relaxed master problem by column generation in order to generate tight lower bounds. Based on the analysis of the structure, we decompose the sub-problems into second-level sub-problems which can be solved independently. Based on the idea of merge and recover, we develop three methods to solve the sub-problems, which reduce the scale of sub-problems and overcome the symmetry in the solution space, leading to accelerating the column generation process. We conduct computational experiments based on the real data from the factory. The experimental results indicate that, our approach outperforms CPLEX, a commercial solver. It can generate high-quality solutions in short computation time. Compared with the algorithm presently used in the factory, our approach reduces the cutting waste by 10.43%.
Key words:cutting stock; batch feed; large-scale mixed integer programming; column generation; merge and recover
1 引言
下料问题(Cutting Stock Problem,CSP)是众多行业中(如造纸业[1]、造船业[2])面对的一个重要问题,其以最小化成本为目标,通过对库存板材的切割,来满足不同尺寸类型的需求[3~5]。合理的下料方案会为实际生产减少浪费,带来经济效益。基于同某家具厂合作的实际生产项目,本文对该厂CSP进行研究。该厂拼合板产品生产过程如下,盛有不同規格板材的托盘被挑选并从仓库中运到线上,工人将刀具预设为若干种标准宽度,并在板材宽度方向上进行水平切割(顺冲工序),产生短条;之后,在垂直方向上切去影响美观的木料疤痕(横截工序),产生横截小块,并将横截小块指接成长条;最终,用从长条上切下的拼合块进行产品拼合。……