A Heuristics Algorithms Of One-dimensional Cutting Problem And Its Application

The one-demensional cutting problems consists of placing a given set of small rods on given set of large rods. It has important and extensive application in the enginnering technique and in the industry production. Whether in practice or in theory, the research with methods of one-demensional cutting problems still has certain importance.The one-demensional cutting problem belongs to the combination and optimization problem and NP-hard .Thus,only small size problems can be solved optimally.These problems are solved using either integer linear programming or dynamic programming,or branch-and-bound,depending on the type of problem.But most of the one-demensional cutting problems use heuristic algorithms. This paper designs a heuristic algorithm to solve a real-life one-demensional cutting problem in wheel and trye plant of maanshan iron & steel co.ltd..Firstly, we summize one-demensional cutting problems and present condition at home and abroad. Secondly,we introduce a few typical methods of one-demensional cutting problems and analyze the problems in the application. Thirdly,under the actual condition restriction of wheel and trye plant of maanshan iron & steel co.ltd.,we establish the mathematic model of the one-demensional cutting problem and design a heuristics algorithm to solve the problem.Finally,we carry on the algorithm with visual C++ 6.0 .We simulate the algorithm with the sequence four-week data from our partner company. Computational results show that our algorithms improve by 7% the performance of our partner company where the cutting plan had been carried experienced algorithms and the number of the table matching weight and length has fewer than experienced algorithms.