An Exact Algorithm For Generating Optimal Three-block Patterns Of Rectangular Blanks

The rectangular cutting stock problem appears in many industries, such as the industries of mechanical manufacturing, furniture, leather, and so on. With manufacturing enterprise facing more intensive market competition, improving material usage may reduces the cost of production and it is an efficient way to increase the profit of the enterprises. The optimal patterns of rectangular blanks may not only improve material usage to reduce the cost of production but also simplify the cutting process to improve the efficiency of production. So the resolving of the rectangular cutting stock problems is of far-reaching theoretical and practical signification.The unconstrained two dimensional cutting of rectangular blanks refers to that the necessary rectangle blanks could be arranged as many as possible on a plate with given length and width for the purpose of reducing the amount of consumed plates as few as possible. It has been proved to be a rather difficult nondeterministic polynomial (NP) complete problem. It is difficult to find its exact global optimum because of the high computational complexity. Many scholars have proposed lots of algorithms, and a lot of papers have focused on it. Generally it is solved by exact algorithms or heuristic algorithms. Exact algorithms are usually used to solve small-scale instances, meanwhile, heuristic algorithms are used to solve large-scale instances in practice. The optimal patterns of rectangular blanks which is compact with the unconstrained two dimensional cutting of rectangular blanks demand maximizing the material usage, equivalently, minimizing the material usage consumed to meet the blank demands. It is solved by the linear programming (LP), the LP model is solved through iteration. During each cycle of the iteration by introducing an unconstrained pattern algorithm, a prominent cutting pattern must be generated. According to whether various-sized blanks could be arranged on the same plate, the corresponding cutting patterns are termed as rectangular object optimal embed placement or cutting patterns for rectangular blanks of a single size from a rectangular. The latter is accepted easily by the clients because of its simple technology and convenient management in the process of blanking, but the former is good for improving utilization ratio of materials. So the paper focuses on it.The optimal patterns of rectangular blanks are termed as rectangular object optimal embed placement. On the one hand, there are thousands of enterprises which have cutting stock problems in our country, but the majority of them use hand-generated cutting patterns in the cutting process. As a result, the material usage is low and the amount of waste is large. Improving material usage can save energy, reduce the pollution to the environment, and increase the profit of the enterprises, on the other, the shearing and punching process is often used to cut the metal plate into finished blanks in two stages in practice. The first stage is referred to as the shearing stage, at which a guillotine shear cuts the plate into strips. The second stage is referred to as the punching stage, at which a stamping press cuts the strips into finished blanks. To improve the efficiency of production, algorithms for generating every cutting pattern contain types of blanks at least. The paper presents an exact algorithm for generating optimal three-block patterns for rectangular blanks (TBPFRB) which divides the plate into three regions, each region contains a normal block consisting of blanks of the same type. The algorithm is based on knapsack problem and dynamic programming techniques. Applying the three techniques makes the TBPFRBLP much more efficient in time.The paper combines TBPFRB with LP to solve the large-scale rectangular layout. The LP model is solved by simplex method through iteration. During each cycle of the iteration by introducing TBPFRB which is an unconstrained pattern algorithm, a prominent cutting pattern must be generated. The problem of generating the prominent cutting pattern consists of cutting a rectangular sheet into a set of rectangular blanks of given sizes and values to maximize the total value of the blanks cut.Both benchmark and practical problems are used to test the algorithms. The computational results of the benchmark problems indicate that the algorithm for TBPFRBLP is efficient both in computational time and in simplifying the cutting process to compare with the algorithm for MPDD. To compare with the algorithms for tow-stage, T-shape and two-section, three-stage, the result indicate the algorithm for TBPFRBLP is less in material utilization, but may simplify the cutting process to some extent. It generates every cutting pattern containing three types of blanks at most. So it may improve the efficiency of production. The computational results of the practical problems indicate that the algorithm for TBPFRBLP is efficient both in material usage and in simplifying the cutting process. Therefore, the algorithm of this paper is promising in practical use.