Alogrithm For Three-Staged Two-Dimensional Cutting Problem

The development of economic is based on a variety of resource. The cutting problem is an optimizing utilization operation for materials and is widely applied in the file of material division, such as machinery manufacturing, leather clothing, architectural design, communications of transportation, aerospace and other fields. The goal of the cutting problem is to max total value of blank which lay out in the single sheet. This paper studies the cutting pattern generation algorithm.In actual industrial production, the material optimization step tends to have the following considerations:(a) the constraint demand of blank, the number of blank which lay out into sheet can’t exceed requirements, (b) patterns with the formation process of the sheet and cutting way are different.This dissertation presents two algorithms based on the number of blank if there is constrained to solve the three-pattern problem.The first algorithm based on unconstrained problem (UTDC). Because of unconstrained items, layout process is generated in advance directly to simplify stitching process. The algorithm solves three large knapsack problems to obtain the optimal pattern:One for the item layout the widest strip, one for the strip layout on the longest segment, and the third for segment layout on the plate. In order to improve the algorithm efficiency, optimize the general strips generated in advance. The one with large length will be discarded when both strips have same value and width. Like choosing the strip with smaller width, discarding the strip width is lager.The result shows that general strips can improve the utilization and optimize the amount of general strips comparing normal length. The calculation time is short. The value of pattern is in a reasonable range.A beam search algorithm is presented for the constrained three-staged cutting problem to obtain homogenous three-staged cutting patterns in a short time. Beam search is a kind of pruned branch and bound algorithm. Dynamic programming is used for determining the value of segments. The branch node is presented by the partial pattern and the unused leftover. On each level, only the elite nodes are allowed for further branching, other nodes are directly deleted, which is helpful to improve the efficiency of algorithm. The experimental results show that the beam search algorithm provides the cutting patterns of high value within reasonable computational time, and the cutting processing is simple.