Intelligent Algorithm Based On The Two-dimensional Cutting Problem

The cutting stock problem layout a series of small parts with different shapes is to find the optimal arrangement of parts and producing the least waste. The problem belongs to the typical combination and optimization problem, which is the NP-complete problem with the high calculate complexity, for the large-scale cutting stock problem, conventional manual layout operation has many shortcoming such as inefficient low yield and long time consuming, even if use computer also have to exploder high efficiency arithmetic to achieve the relatively high efficiency optimum cutting.According to space division, the cutting stock problem divide into one-dimensional, two-dimensional, three-dimensional, in which two-dimensional cutting-stock is widely used.At present, rectangular cutting-stock combined with a variety of intelligent algorithms, has made a number of sophisticated algorithms. In the paper, for the rectangular cutting stock problem, use sheet with restricted in width but infinite in length to cut a group of triangles with known size, minimize the used area of sheet, the graphic scan conversion techinque can transforms the triangle into the discretizing geometrical information, which solves the problems caused by the complex profiles of triangles. The Heuristic Searching Algorithm based on graphic scan conversion method is introduced in the paper, which serves as the bottom, improved particle swarm optimization serves as the upper optimization Algorithm. The bottom Algorithm receive the optimization parameters from the upper optimization Algorithms.In the end, through simulating the experimental results show that the proposed heuristic particle swarm optimization algorithm has strong global search ability, the utilization of materials has been greatly improved and have a near optimize result in a relatively short time. In a word, the heuristic particle swarm optimization is an efficient, fast and accurate intelligence algorithm.