Research And Development Of The Layout System For The Near Optimal Cutting Of Circular Blanks

The research on the cutting stock problems is to study how to generate cutting patterns to maximize material usage. Cutting stock problems appear in many industries, such as the industries of rag trade, leather, sports goods, mechanical manufacturing, and so on. There are thousands of enterprises which have cutting stock problems in our country, but the majority of them use hand-generated cutting patterns in the cutting process. As a result, the material usage is low and the amount of waste is large. Improving material usage may reduce the costs of production and it is an efficient way to increase the profits of the enterprises. Improving material usage is a systematic engineering. Many factors should be considered to get a good solution, such as production management, optimizing the cutting process, and decision support. The most direct method to improve material usage is to optimize the cutting scheme, and the key is to develop efficient algorithms. The two-dimensional cutting problems of rectangular and irregular blanks have been studied intensively, but the cutting problems of circular blanks have drawn little attention. So this paper focuses on the cutting problem of circular blanks, which is a branch of two-dimensional cutting problems. Hand-generated cutting patterns are often used in the cutting process of circular blanks in practice, which produce more waste. This paper presents an algorithm for the cutting problem of circular blanks. In theory, both conventional layout algorithms, such as dynamic programming, integer programming, linear programming, hill-climbing approach, branch and bound approach, and modern optimization algorithms such as tabu search, simulated annealing, genetic algorithms and neural networks, may be adopted. Conventional optimizing approaches can merely solve some simple problems in practice. As to the more complicated problems, heuristic algorithms should be adopted. The cutting problem of circular blanks (CPCB for short) discussed is to cut a roll into many demanded circular blanks, so as to minimize waste. The roll length is much larger than the sizes of the blanks. It may be taken as infinite in developing the algorithms. The blanks may be of different sizes, and the demand for each type must be meet exactly. This problem has been shown to be NP complete. This paper presents an algorithm (ASA for short) for the CPCB. It arranges the blanks one after the other according to a given order. A feasible position must be determined for each blank. The searching space consists of only discrete positions that form a subset of the space that should be searched. This searching space is larger than that used by the algorithms reported in the literature. This is helpful for improving the solution. The characteristics of the blank shape and the cutting pattern are analyzed to avoid considering some regions of the searching space that do not contain feasible positions. This may shorten the time required to solve a problem. ASA arranges the blanks in the roll according to a fixed order. Therefore, the material usage of the solution depends on the given order. A hybrid genetic algorithm (HGA for short) is used to generate different orders, each of which relates to a cutting pattern. The one of the highest material usage is selected from these patterns. The coding of the string is based on the integer indexes of the blanks. The initial population is generated both randomly and empirically. The best one of the strings considered so far is kept as the current best solution. The tournament selection process that chooses the strings considering their actual fitness values is used. The widely used sequencing cross operator and the swapping mutation operator are used. When the evaluation process is about to be terminated, the hill-climbing approach is used to consider new strings that are generated from the current best string, so as to improve the solution further. Both benchmark and random problems are used to test the algorithms. The computational results of the benchmark problems indicate that the algorithms can generate cutting patterns of higher material usage in shorter times, and are comparable to those presented by Hifi who is a famous French scholar in the domain of cutting and packing. The computational results of the random problems indicate that the algorithms of this paper can generate cutting patterns of higher material usage, and the computation time is reasonable for most practical cutting problems.