Research On The Optimal Nesting Problem Based On The Improvement Dynamic Programming Algorithm

This paper brings forward the technical thought of the nesting-problem at the background of the process of the raw material of the rectangle stock on the clipping-machine. The result of optimal placement of stock sheets is to improving the utilizing ratio of raw material and reducing the cost of the product which can improve the competition. Through investigation to a great range of article focused on nesting problem of two-dimensional parts, the author studied some defects of their algorithm in optimization nesting problem of same parts. Based on that, the paper put forward the thinking and algorithm to new auto-nesting methods: combining improvement dynamic programming algorithm with the heuristic strategies; and analysis the relation of the quantity of the production between the pictures of the layout results and the utilization of the stock sheet through three examples, based on the optimal algorithm offered in this paper, a set of software is developed to prove its validity with two computation examples.