Abstract: This paper discusses the problem of generating optimal cutting scheme for punch items. The cutting scheme also consists of several cutting patterns. First a knapsack algorithm generating four-block cutting patterns of punched strips is constructed, then the linear programming algorithm which based on column-generation is used to generate the cutting plans, it iteratively calls the above knapsack algorithm, improves the objective function based on the principle of minimum production cost and changes the current value of punched items, generates a new pattern according to the current value, in the end a set of optimal cutting patterns are chosen to form the cutting scheme. It makes this paper’s four-block generation algorithm compared with the literature’s multiple-segment generation algorithm through example testing, the experimental results show that, four-block generation algorithm can obtain a higher value pattern. Finally through the solving cutting scheme of an example, it can be seen that the proposed algorithm is effective in solving the practical problem.

Key words: punched items, shearing cutting stock, knapsack algorithm, column-generation, linear programming algorithm

摘要： 讨论冲裁件条料剪切下料方案的设计问题。下料方案由一组排样方式组成。首先构造一种生成条料最优四块排样方式的背包算法，然后采用基于列生成的线性规划算法迭代调用上述背包算法，每次都根据生产成本最小的原则改善目标函数并确定各种冲裁件的当前价值，按照当前价值生成一个新的排样方式，最后选择最优的一组排样方式组成下料方案。采用例题将该排样方式生成算法和文献中多段排样方式生成算法进行比较，实验计算结果表明，该算法得到的排样方式排样价值较高。最后通过文献中实例的下料方案求解，可以看出该算法解决实际下料问题是有效的。

关键词: 冲裁件, 剪切下料, 背包算法, 列生成, 线性规划算法