An Efficient Heuristic Algorithm For The Circle-cutting Problem

The cutting stock problems exist widely in the national productions, such as machine building industry, garment processing, furniture manufacturing, wood-processing industry, leather and leather product industries and so on. With the rapid development of information technology industry and computer technology, the advanced computer aided design techniques have been used more and more widely in the cutting process, and become the key factor for improving the cutting stock efficiency and material utilization.The two-dimensional cutting stock problem is to consider how to optimize the cutting plan to meet the blank demand when the sheet and the blanks are both two-dimensional. The purpose of the optimization is to maximize the material utilization and reduce the cutting losses. The two-dimensional cutting stock problem appears widely in daily productions. At preset, scholars in and abroad have given sufficient attention to this problem, especially about the rectangular and two-dimensional irregular packing problems. A lot of efficient algorithms have been proposed, such as dynamic programming, branch-and-bound algorithm, tabu search, simulated annealing algorithm, genetic algorithm, neural network algorithm and so on. However, another two-dimensional cutting stock problem that is widespread in the practical production ---- the circular cutting stock problem, is under a relatively less research, especially for the constrained circular cutting problem. The research on pattern generation algorithm has two branches: the algorithm for the unconstrained cutting problem and the algorithm for the constrained cutting problem. The former generates a pattern on a single sheet to maximize the total blank value, when the blank size and value has been given; it is often used jointly with the line programming technology to solve the cutting stock problem. The latter generates a pattern on a single sheet to maximize the total blank value, where there is an upper bound on the number of each blank type included in the pattern. It is often jointly with the sequential heuristic procedure to solve the cutting stock problem.In this paper, the constrained cutting algorithm and the cutting plan generation algorithm based on the sequential heuristic procedure are studied to solve the circular cutting stock problem. The purpose of the approach is to determine a solution based on the cutting and punching process. This pattern solution satisfies the following factors: (1) the solution is composed of one or more patterns; (2) the patterns must be feasible; (3) the demand of each blank type must be fulfilled exactly; (4) the solution must minimize the consumption of the sheet area. The cutting and punching process can be described as follows: there is a sheet with specified length and width; first cut the sheet into strips, with every strip containing blanks of the same diameter, then punch every strips into circles with a punching machine. Based on the research of the heuristic algorithm, we use the sequential value correction method to solve the circular cutting stock problem.The main work of this paper is as follows:Firstly, according to the studied question, the algorithm for the optimal cutting pattern on a single sheet is presented. Based on this algorithm and jointly with sequential heuristic procedure, the plan generation algorithm is designed. The purpose of this algorithm is to maximum the material utilization as much as possible and the demand of each blank type must be fulfilled exactly.Secondly, further refine and improve the cutting stock algorithm studied in this paper. Because of the greedy nature of the traditional sequential heuristic procedure, the solution generated by this method may easily lead to a local optimal solution but not a global optimal one. This paper uses a heuristic procedure based on the sequential value correction method and parameter optimization method to improve the material utilization. The sequential value correction method (SVC) first initializes every blank value as the blank area, and then updates the blank's value with the value correction formula and its previous value before generating the new pattern. The process is repeated several times to make the blank value more reasonable. The blank's value is adjusted appropriately to reflect their relative popularity. Give higher priority for the worse blanks to make them more popular. It will help to generate better patterns. Using the message of the previous pattern to guide the late layout process is helpful for the improvement of the material utilization.Thirdly, plan and design the basic functional modules of the cutting stock system. A circular cutting stock optimization system based on SVC is developed. The effectiveness of this approach is tested by the existed cutting stock system. The experimental results indicate that the approach of this paper can yield better material utilization and is an effective heuristic for the circular cutting stock problem.