An Algorithm For Circle Cutting Stock Problem Based On Trapezoid And Parallelogram

The circular cutting stock problem is widely exists in electrical, mechanical manufacturing, aerospace and other fields. How to improve the material utilization during the cutting process has been a hot research for pattern experts. As mentioned the crafts of punching and shearing, the parallelogram strips are proposed to apply in the fixed size rectangle sheet. Trapezoid stripes are introduced at the same time to coordinate parallelogram strips when nesting for avoiding too much leftover. Then a schema for circle cutting stock problem based on trapezoid and parallelogram is formed. The main research works are as follows:(1) Referring whether parallelogram strips can achieve a higher material utilization in a fixed size sheet, recursive algorithm is applied in non-nested cutting stock problem of rectangle sheet and parallelogram sheet with the same area. Parallelogram stripes verified can achieve higher material usage than rectangle stripe by comparing the number of circular blanks layout in the sheet.(2) Referring how to apply parallelogram stripes in rectangle sheet without too much leftover, parallelogram strips and trapezoid stripes combined nesting is proposed. Plate with two parallel dividing lines will be divided into three segments when the nesting, two segments of right angle trapezoids and one parallelogram segment. The optimal combination of stripes in trapezoid segment is determined by recursive algorithm. Dynamic programming algorithm for one-dimensional knapsack problem is used to determine the optimal combination of stripes in parallelogram segment. Enumeration method and normal length are applied when seek the optimal cutting point. Thereby the whole plate’s optimal pattern is the combination of these two types segments.(3) To solve non-nested and nested cutting stock problem of rectangle sheet with the pattern proposed in (1). Liner programming algorithm is used to solve the problem of the two-dimensional nested cutting pattern problem, making material utilization maximum. Finally, the result of experiment of a large number of randomly generated problems and comparison with classic T-shape pattern show that pattern in (2) can layout more circle blanks into plate for non-nested cutting and less sheets will be used to meet the demand of blanks for nested cutting. Both of the computing time are in the acceptable range. This result indicates the effectiveness of improving material utilization and applicability of the algorithm.