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

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