The Research On Optimization Algorithms For One-dimensional Cutting Stock Problems

The one-dimensional cutting stock problem widely exists in manufacturing, construction,and other industries, The focus of attention of the relevant enterprises is to improve the stockmaterial usage and reduce the cost. The one-dimensional cutting stock problem consists ofcutting a set of stocks into smaller parts. The one-dimensional cutting stock problem is aclassic combinatorial optimization problem which belongs to the NP-hard problem. Therefore,The research on the one-dimensional cutting stock problem has important significance in boththeory and reality field.In this thesis, according to the specifications of the materials, the one-dimensionalcutting stock problem is divided into two kinds of circumstances: The single stock sizeproblem and multiple stock size problem. According to the situation that the length of stock islonger than the length of part, use different solutions to solve small-scale problem andlarge-scale problem. In addition, a new situation is considered: the lengths of stock is shorterthan the length of part, and make analysis and calculation.For the small-scale problem, a heuristic algorithm is proposed. First calculate all feasiblecutting patterns, then according to the constraints and search out effective cutting patterns,make sure that the final stock has the longest length, Finally the combination of theseeffective cutting patterns is the solution. For the large-scale problem using genetic algorithm.Based on the constant long real number coding, propose a punishment strategy for the illegalindividuals, make sure the feasibility of the solution.