考虑成批供料的大规模下料问题  

A Large-scale Cutting Stock Problem Considering Batch Feed

作　　者：郝信烨 刘懋圻 张灿荣[1,2] 郑力 HAO Xin-ye;LIU Mao-qi;ZHANG Can-rong;ZHENG Li(Department of Industrial Engineering,Tsinghua University,Beijing 100084,China;Logistics Engineering and Simulation Laboratory,Shenzhen International Graduate School,Tsinghua University,Shenzhen 518055,China)

机构地区：[1]清华大学工业工程系,北京100084 [2]清华大学深圳国际研究生院物流工程与仿真实验室,广东深圳518055

出　　处：《工程管理科技前沿》2022年第1期9-16,共8页Frontiers of Science and Technology of Engineering Management

基　　金：国家自然科学基金资助项目(72188101);国家重点研发计划资助项目(2018AAA0101700)。

摘　　要：本文基于某家具厂实际生产场景,在大规模下料问题中考虑了成批供料等现实生产因素。我们建立了Kantorovich模型,其对应的算例具有规模大、解空间对称等特点,难以直接求解。为了解决计算困难,基于Dantzig-Wolfe框架将其分解,并通过列生成求解线性松弛主问题得到较紧的下界。通过对子问题的结构分析,将其分解为可独立求解的二级子问题。基于归并且还原设计了三种子问题求解方式,有效缩减了子问题求解规模,并克服了解空间对称性,进而加速列生成迭代。基于工厂实际数据进行数值实验,结果表明:本列生成启发式算法优于商用求解器CPLEX,其在较短计算时间内得到高质量的解。相比于工厂现行算法,本算法降低10.43%的下料浪费。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%.

关 键 词：板材下料 成批供料 大规模混合整数规划 列生成 归并且还原 

分 类 号：TB114.1[理学—运筹学与控制论]