Research On The Optimal Cutting Of Circular Blanks

The computer aided optimal layout is an important branch of the computer aided design and manufacturing (CAD/CAM), whose purpose is to find out the optimal arrangement of blanks of different sizes, to maximize the material utilization and reduce its cost as long as the demand of all blanks are satisfied.In real production, cutting stock problems appear in many industries, such as machine building industry, garment processing industry, furniture manufacturing, wood-processing industry and leather and leather products industry. It's always been applied in the cutting and packing of wire rod, coiled material, plank stuff and three-dimensional material. Traditional works are completed by men, which leads to the waste of raw material and increased product cost because of long working hours and low material utilization. Accordingly, there is an importantly theoretic and actual purport for the research of cutting stock problems and the design of efficient algorithm.Academicians in and aboard have worked deeply on the research of cutting problem, especially on the rectangle and two-dimensional irregular packing problems, many advanced algorithms have been put forward, there are some deterministic ones like dynamic programming, polynomial time algorithm, continued fraction algorithm, branch-and-bound algorithm and so on, also some probabilistic algorithms such as tabu search algorithm, ant colony algorithm, genetic algorithms and neural networks algorithm have been used. However, there are a few algorithms for the circle cutting problem, as a branch of two-dimensional packing problem, it is frequently encountered in real production. Therefore, it is extremely necessary to do some research on the circle cutting stock problem.This paper focuses on the circle cutting problem, which can be described as follows: there are sheets with specified length and width, first the sheet is cut into horizontal or vertical strips by a guillotine shear, and each strip contains blanks with the same diameter; then the blanks demanded are cut from the strips by a stamping press. Provided the optimal design meets the demand of circular blanks, the quantity of raw material and the cost of production can be minimized.The thesis falls into two parts: Firstly, the algorithm for the unconstrained circle cutting problem has been designed and realized in order to generate the cutting pattern. Based on the exact algorithm, dynamic programming and knapsack algorithm combined, the subset of normal size is chosen to calculate the result in the unconstrained algorithm, which determines the optimal layout of the strip in the sheet to make the total value of circular blanks reach its maximum.Secondly, the unconstrained algorithm and the linear programming (LP) are combined to solve the large-scale two-dimensional circle cutting stock problem: the size of sheet, the diameter and demand of m circular blanks are known, the cutting plan must be determined to minimize the cost of sheet on the basis of satisfying the blank's demand. This paper adopts the simplex algorithm to solve the linear programming. In the procedure for solution, it calls the unconstrained algorithm again and again to generate a new pattern which can make the current solution better according to the current blank values, and establishes the best circle cutting stock plan at last.Because the unconstrained algorithm is called reiteratively in the linear programming by simplex algorithm, the efficiency of the unconstrained algorithm is extraordinarily important to the algorithm for generating the cutting stock plan. In the process of realizing the unconstrained algorithm, the paper has introduced the concept named normal size and the strategy of choosing its subset to optimize it to enhance its efficiency.A layout system is developed, and effectiveness of the presented algorithm is checked up by the benchmark in other literatures and production instance, the results of the benchmark for cutting pattern show that the material usage of my pattern is higher than part of those generated by the three-block pattern, and all of those generated by T-shape pattern; it is same as that generated by exact algorithm with less computation time; computing the instances of cutting solution, the results indicate that the material utilization of my solution is more desirable than all those cutting solutions generated by T-shape and uni-segment algorithm; the results of the practical instances demonstrate that the algorithm of this paper can not only fulfill the practical industrial need, but also work obviously better than those multi-segment and uni-segment in terms of generating cutting solution. To draw a conclusion, the algorithm presented in this paper is efficient in the practical manufacture.