Research On The Problem Of Two Dimensional Layout Based On Block Structure

Two dimensional optimization problem of rectangular blanks refers to a layout problem, which needs to let a set of rectangular blanks lay in the limited area with no overlap to realize the optimized utilization of resource. It is mainly applied in the machinery manufacturing, clothing, wood, and other manufacturing areas. To solve the large scale cutting problem, we usually use linear programming to solve iteratively. During the each iteration, we need to call the algorithm of solving the unconstrained two-dimensional cutting problem to optimize the objective function, and to obtain the optimal solution of the problem. So a good layout algorithm directly determines the quality of the solution to the problem. Designing a reasonable and efficient optimization algorithm will have a very deep practical significance to the production practice.In this paper, we will study the unconstrained two-dimensional problem based on the block structure. Two kinds of the specific type layout patterns based on block structure are presented. Those are called Double-rows and Multi Segment pattern and Complex Uniform Block pattern, which are called DMS and CUB for short respectively in the passage. In this paper two algorithms of generating two layouts are introduced in detail, which are respectively called GenDMS and GenCUB for short.The algorithms were tested through three group benchmark problems. Through analyzing of the experimental results of the comparison, we can get the following conclusions. In the process of using the DMS pattern to deal with the cutting problem combined with shearing machine can simplify the cutting process, shorten the calculation time, and also improve the material utilization effectively. Compared with the DMS pattern, although the cutting process of CUB pattern is relatively complex, however it can also achieve higher material utilization within reasonable computation time. Combined the two kinds of solving algorithm of patterns in the paper with the linear programming algorithm to solve the problem of two-dimensional cutting problem can obtain the optimal cutting plan within reasonable computation time, which can play a realistic guidance during the actual production practice.