Cutting Stock Problems And The Research On Their Algorithm

Cutting stock problem (CSP) has a wide range of application for production industry. In this paper, some special cutting stock problems have been studied.At first, a research has been done for circles'layout problem. In this section, farther optimization of using percentage has been discussed from two aspects which are multi-column choice and multi-angle choice, respectively. Then, in the second and third problems, this paper discusses two cutting stock problems in which items can be welded. The one is one-dimensional, the other is two-dimensional. For the one dimensional CSP, the focus is the characteristic that items can be welded. From the matrix of relationship between items and stocks, a mathematics model has been established, and on the basis of this model, a heuristic algorithm has been brought forth. In this heuristic algorithm, the thought of greedy has been used and the method of gaining the initial feasible matrix has been researched carefully. It also uses the stochastic analogy to optimize the using percentage. What's more, the algorithm discusses an important aspect of this problem: the optimization of the amount of welding points, and presents two methods by the improvement of the heuristic algorithm and multi-objective optimization, respectively. For the two dimensional siliconized plates'layout problem, the focus is multi-stages of its layout process. As the layout process is complex, the paper presents an improved genetic algorithm (GA) to solve it. This algorithm use the thought of messy GA to code for the feasible solution, and it also use elitist selection, partially matched crossover and simple mutation, and so on.During the second and the third problem, the paper also gives a summarization of genetic algorithm. It introduces the concept of genetic algorithm, especially the concept of evolutionary computation. Then, for the drawbacks of basic genetic algorithm, some improved genetic algorithms have been introduced. At last, some applications of genetic algorithm have also been presented.