Study And Implementation Of The Method For Cutting Stock Problem Based On Genetic-ant Colony Algorithm

Cutting stock problem is coming from the production practice, this problem which is about how to save raw material and optimize resources in the product design and manufacture, widely exists in automobile manufacture, clothing, metal cutting, glass processing and furniture manufacturing industry. Facing the shortage of the resource, it has important practical significance to increase material utilization ratio, save raw material, reduce the cost.In this paper, the cutting stock problem in the fibre furniture manufacture is concerned with packing rectangular items onto a rectangular raw material sheet. Theoretically, this kind of problem in the calculation of the complexity belongs to NP complete problem, there is no precise method to solve this problem, but a wide range of applications exists in production. In recent years, with the development of intelligent optimization algorithms and computer technology, it provides a solid theoretical and technical foundation for the study of cutting stock problem.According to the merits of genetic algorithms and ant colony algorithm, this paper proposes a mixed algorithm, namely genetic ant colony algorithm (GAAC). The basic idea of GAAC is that, initially it adopts genetic algorithm to give information pheromone to distribute, in algorithm later it makes use of the ant algorithm to give the precision of the solution. According to the process characteristics of "guillotine cutting", this paper designs a binary tree to store the optimal solution method and proposes "object-oriented" coding method in genetic algorithm. Combination of rectangles is used to represent the nodes of the binary tree. This way reduces the number of layers in binary tree and improves binary tree search efficiency. Experimental results show that the integration of genetic algorithm and ant colony algorithm is very effective, algorithm performance is better than genetic algorithm and time cost is less than ant colony algorithm. This algorithm is applied to solve large-scale Rectangular in fibre furniture industry, get a good result of optimization.This paper developed the fibre furniture industry's large-scale rectangular cutting stock system, the operation of this system is very simple and practical, so it can avoid some inconvenience caused by artificial packing in the process of participation in the furniture industry. The result of experiment shows that this system can achieve optimization results for saving the raw material, reduce the cost of consumption, bring certain economic benefits for the furniture industry.