Research On Cutting Problem Of Two-dimensional Rectilinear Parts

ABSTRACT:Cutting problem belongs to a typical NP-hard combinatorial optimization problem. It has a very extensive application in practical engineering, such as machinery manufacturing, aerospace, transportation and other industries, so it has always been the focus of the research scholars. For two-dimensional cutting problems, most current publications are mainly for regular parts or completely irregular parts. But in the industrial enterprise many sheet metal parts are composed of lines and arcs, and some of these parts are rectilinear or can be converted into rectilinear parts. These rectilinear sheet metal parts cutting problem is known as rectilinear parts cutting problem. In order to solve this problem, two-dimensional rectilinear parts cutting problem is presented in this paper. The optimization objective is to find an arrangement for maximizing the material usage. The main contents of the study include:(1) Research on Neidlein2D rectangular problem generator, and improve the existing random jumping problem to ensure the repeatability of the problem generator(2) The dynamic programming method for guillotine cutting problem is presented. The principle of the dynamic programming method is analyzed. According to the recursion formula, its C++solution model is established, and finally the model is tested successfully by the instances.(3) The congruent rectangle problem is researched in this part. And the Beasley model of the PLP is analyzed as the example. The more important is that the Beasley model is solved by the CPLEX which is a kind of software applied to the large-scale linear programming optimization.(4) Based on the above Beasley model of the PLP, a new two dimensional mathematical model of rectilinear parts cutting problem is established by proposing a mapping matrix of the rectilinear parts. Furthermore, the article reforms the grid technology of the PLP and makes it can be used in the rectilinear parts cutting problem. And the model is solved by the software CPLEX, including single and hybrid methods.The research shows that this proposed method can solve medium-sized rectilinear parts cutting problem, and the result is exact. Fully considered the characteristics of two dimensional rectilinear parts, this algorithm gives a better result than the plant layout scheme.