Research On Transmit Path About NP-Hardness Of Cutting And Packing Problems

As the typical representative of the study on NP, packing problems have been widely used in engineering practice. In the actual production, NP problems which are always encountered have become a bottleneck restricting the development of technology. In the 21st century, exploring NP-hard problems is an important challenge for computer scientists as well as engineering technicians. At present, although solving a problem is based on the complexity of the problem, the research on cutting and packing problems mainly focuses on solving methods and ignores the complexity. This article mainly studies on the proof transfer route of NP-Hardness of cutting and packing problems, the purpose is to clarify the transfer relationship based on the complexity between different packing problems. The main research contents are as follows:(1) The first one is the statistical classification of the three kinds of cutting and packing problems. On the basis of the study on the statement about the complexity of C&P, the author chooses the classification strategy, which is to classify different problems relying on the difficulty of the problem. And packing problems can be divided into three types of problems, which are the known NP-hard class, guessing NP-hard class and P class. For three kinds of problems, the paper implements different classification schemes, and finally obtains a reasonable classification result.(2) This article attempts to prove that the pallet loading problem can be transformed into an NP-hard problem. And it adopts the idea that transform the vertex cover problem into the pallet loading problem using a polynomial transformation. Because of the difficulty of proof process, it ends in failure. However, inspired by the proof process, the author finds the solving method (Using vertex cover problem to solve the pallet loading problem) is of great significance. The solving idea can be applied to the actual packing problems. The rectilinear part cutting problem is solved based on the method of vertex cover problem and achieves good results.(3) The research on the literature that explain the complexity of different problems is also involved. First the statistics of the literature which prove (claim) the complexity of different packing problems, namely, a total of literature show their complexity. The second is the literature of the last level problems. Thirdly, the literature of the next problems is researched.(4)The last content is clearing up the proof transfer route of NP-Hardness of cutting and packing Problems. This paper refers Wascher’s typology of C&P whose basic problem types divide packing problems into six kinds of problems. And then clarifies the transfer relationship based on the complexity between different packing problems. Finally, the sketch map on proof transfer route of NP-Hardness of C&P is built.(5) To establish the difficulty judging system of cutting and packing problems. The system includes two subsystems; one is the classification inquiring system and the other is complexity deciding system.The results of this paper can provide valuable support for the scholars who are determined to study packing problems in classification inquiring as well as complexity decision. At the same time, the results can give assistance for engineering technicians in the selection and design of the algorithms.