Research On A Typology Of Solution-algorithms Of Cutting And Packing Problem

Packing problem is a classic combinatorial optimistic problem, and is claimed to have double-hardness both in modeling and solving. Since the origination of this problem, it has been applied to many engineering fields, and attracted many researchers from engineering, mathmatics and computer science to do researching worked on the problem. Besides, numerous good methods have been proposed for the problem. Because of its NP-hardnes and the type variety, there are many algorithms appeared to solve it.The packing problem typology paper delivered by Dyckhoff in 1990 and the improved packing problem typology paper delivered by Gerhard W(a|¨)scher in 2007 were both classified and coded the packing problem. Organized and classified systemly the numerous and complicated packing problem to obtain a set of classified coding system. Both these codes are simple and clear which solved the lack of references ability among different C&P problems and their influences are fairly large.Based on the lately delivered papers on cutting and packing problems, this paper researches on the algorithms, proof approaches, achieved results etc, then classifies and summarizes different kinds of algorithms and establishes the typology coding system; at the same time, the properties and adaptable methods are studied, the development trend and the adaptable type of being solved problem are also obtained. Thus, when the new problem is coming out, we can solve it by using this system to recommend reasonable algorithm or to lead to the generation of the new algorithms for overcoming the disadvantages on manual designing.Firstly, research on the structure of literature papers about solving packing problem to find out the common points of different papers then proposes the general structure of the typology system. Secondly, proposes each criteria and refines the criteria, coding the codes based on the bit principle. thirdly, according to the different research depth, this paper grades the typology system and establishes the second type and gives the word expression; make codes for the typical algorithm typology examples to identify the validity and practicality. Then, bulids up a network for the codes and run it to make the researchers feel comfortable; at last, conclusions are drawn and the future research directions are suggested.In this paper, the author summarizes the system of algorithms for packing problems, and straightens out the complex relationships between different algorithms which both to supply the methods and tools. All of above has an important value.