Approximate Algorithm For The Stock Cutting Problem

Optimal layout is an urgent problem that is very difficult in?computation theory, but has been widely used in practice. With?the rapid development of the techniques of computer, CAD and?artificial intelligence, the computer aided optimal layout?becomes possible. Two classes of basic optimal layout problems are studied: one-dimensional stock-cutting problem and rectangular layout from the?aspects of mathematical model of optimization and its?adaptability and efficiency for the optimal layout problems. ?According to the natures of the optimal layout problems and?different needs of them in practice, several optimal layout?algorithms are presented.Based on the idea of k-opt algorithm for TSP, present a k-opt algorithm for the one-dimensional cutting-stock problem. The algorithm avoids the great complexity of deducing cutting-patterns and solving LP, result shows that the algorithm is valid to small-scale problem. And for the large-scale problem, the paper proposes an evolutionary approach, experiment shows it would be more effective. Ant colony algorithm is a new type of simulated evolutionary algorithm, the paper attempt to solve the stock cutting problem by using this algorithm.Based on actual banking technological requirement of rectangular pieces, this paper evaluated the remainder of the length or width of rectangular sheet material to that of rectangular pieces, and proposed an approximate algorithm for two-dimensional layout of the rectangular pieces on the rectangular sheet material according to the result of remainder. For improving unloading productivity, propose a T square approximate algorithm. First divided rectangular sheet into three blocks, then place a kind of rectangular pieces on each block. Experimental result shows that the algorithm is valid to the large-scale rectangular layout and ensures the productivity of unloading. Two-dimensional stock cutting problem can be settled by solving two one-dimensional knapsack problems, this paper presents a new algorithm based on the ant colony optimization idea.At last, all the works in this thesis are summarized and some?prospects are also proposed.