Research On Overlap Determination And Modeling Simplification Of Two-Dimensional Irregular Cutting Problems

The contradiction between the limited resources and infinite human demand for resources decides that human need to optimize the allocation of resources, fully and reasonably use the existing resources and reduce the costs. China’s economy is in the new normal with the economic structure needing optimization and upgrading. The extensive economic development model in the past which only pursues the quantity and speed of the economy needs to be improved. The goal of development should be focused more on the quality and efficiency. As the target of research on two-dimensional cutting and packing problem is maximize the utilization rate of material, it is necessary to study it further.Two-dimensional cutting and packing problem is a combination optimization problem with broad application value. Its NP-hard attribute determines that it has no polynomial time solution, and its dual complexity of modeling and solving makes it difficult to solve. This thesis focuses on the difficulty of two-dimensional cutting and packing problem including the overlap determination problem and modeling simplification on the general level. The algorithm proposed can effectively solve the large scale cutting problem, which is two-dimensional cutting and packing problem with irregular shape to be packed. The main work is as follows.(1) An algorithm is presented for generating two arbitrary polygons’no-fit polygon, which is used to determine overlap.(2) The common technology raster points in the two-dimensional cutting and packing problem is studied. From the perspective of mathematics, the model which is more suitable for cutting problem in this thesis is simplified in the general level.(3) Based on the basic idea of rolling horizon production planning method, rolling horizon strategy is put forward for solving the large scale two-dimensional cutting and packing problem.(4) Using the methods presented above, a model is built for large scale cutting problem. The new model is tested on a set of real world instances which come from sheet metal processing enterprise.