二维板材切割下料问题的一种确定性算法  

A Deterministic Algorithm for Solving the Problem of Two-Dimensional Sheet Cutting Stock

作　　者：曾兆敏[1] 王继红[2] 管卫利[3] Zeng Zhaomin;Wang Jihong;Guan Weili(Sichuan Institute of Information Technology, Guangyuan Sichuan 628017, China;School of Electrical Engineering, Zhengzhou University of Science&Technology, Zhengzhou Henan 450064, China;Information Engineering College, Nanning University, Nanning Guangxi 530200, China)

机构地区：[1]四川信息职业技术学院,四川广元628017 [2]郑州科技学院电气工程学院,河南郑州450064 [3]南宁学院信息工程学院,广西南宁530200

出　　处：《图学学报》2016年第4期471-475,共5页Journal of Graphics

基　　金：四川省教育厅科研项目(GZY15C45);广西科学研究与技术开发计划项目(12118017-10A)

摘　　要：研究二维板材切割下料问题,即使用最少板材切割出一定数量的若干种矩形件。提出一种结合背包算法和线性规划算法的确定性求解算法。首先构造生成均匀条带四块排样方式的背包算法;然后采用线性规划算法迭代调用上述背包算法,每次均根据生产成本最小原则改善目标函数并修正各种矩形件的当前价值,按照当前价值生成新的排样方式;最后选择最优的一组排样方式组成排样方案。采用基准测题,将该算法与著名的T型下料算法进行比较,实验结果表明,该算法比T型下料算法更能节省板材,计算时间能够满足实际应用需要。This paper discusses the two dimensional sheet cutting stock problem, that is, use the leastnumber of sheets to cut out a certain number of rectangular pieces. A deterministic algorithm isproposed which based on the combination of knapsack algorithm and linear programming algorithm.First, a knapsack algorithm is constructed to generates the four blocks uniform strip pattern, then thelinear programming algorithm is used to generate the cutting plans which iteratively calls the aboveknapsack algorithm to improve the objective function based on the principle of minimum productioncost and changes the current value of punched items to generate a new pattern according to thecurrent value. Lastly, a set of optimal cutting patterns is selected to form the cutting scheme. Thealgorithm was compared with the famous T-shape algorithm using some benchmark problem tests.The results show that the algorithm can save more sheets than the T-shape one, and the calculationtime is reasonable in practical application.

关 键 词：二维切割 矩形件下料 背包算法 线性规划算法 

分 类 号：TP399[自动化与计算机技术—计算机应用技术]