Abstract:
This paper constructs an approximate algorithm for the two-dimensional layout of the rectangular pieces on the rectangular stocks.The problem belongs to NP-complete problem, so it is usually impossible to find its optimal solution. The main idea of the algorithm is to continuously produce some smaller rectangles on the stock by a local optimal principle, then allocate these rectangles with the rectangular pieces and delete the filled rectangles at the same time until all the rectangular pieces have been allocated.