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

Computer Aided Nesting (CAN) is a branch of computer aid techniques which is widely used in industrial production, such as mechanical manufacturing, apparel manufacturing, furniture manufacturing, equipment of traffic and transportation manufacturing and so on. The purpose of CAN is to find the optimal layout which makes the better material utilization, to reduce the cost and to simplify the cutting process. As a result, reduce the production cost and enhance enterprise competitiveness.The problem of rectangle packing is an important branch of CAN. The optimal patterns of rectangular blanks not only reduce the cost of production by improving material utilization but also improve the efficiency of production by simplifying the cutting process and shortening the computation time. So the research of the rectangular cutting stock problems has far-reaching theoretical and practical signification. Meanwhile, irregular layouts can be transformed into rectangular packing problems by computer graphics processing technology which puts one or several blanks into a rectangular enclosure. Then the enclosures can be treated as rectangles in generating the cutting patterns.Packing problem should consider three factors of material utilization, cutting techniques and computation time. This paper combines four-block patterns with Linear Programming to ensure higher material utilization. In addition, packing problem is a nondeterministic polynomial (NP) complete problem. If no necessary constrains are considered in generating the cutting patterns, not only the computation time is unacceptable but also the generated patterns are complicated. This paper uses four-block patterns. First, use a vertical or horizontal cutting line to divide the sheet into two blocks: the upper and the lower, or the left and the right. Then, use two lines which are perpendicular to the cutting line to divide the two blocks respectively. Each block contains homogeneous strips with uniform blanks. In other words, there are four types of blanks in the sheet at most. This paper presents an algorithm of four-block patterns for rectangular blanks (FBPFRB). The algorithm is based on knapsack problem and dynamic programming techniques. It can solve the unconstrained two-dimensional rectangular guillotine-cutting problem. Take twenty random examples for experiment. Then, this paper combines the FBPFRB algorithm with Linear Programming as FBPFRBLP algorithm according to the theory of Linear Programming. The FBPFRBLP is used to solve the cutting stock problem. One instance is used to demonstrate the effectiveness of the algorithm. As four-block patterns are composed of strips, they fit the guillotine-cutting techniques. It simplifies the cutting process and shortens the production cycle by using homogeneous blocks patterns solely. Combine with Linear Programming, it works more efficient. Each pattern generates four types of blanks at most. The pattern is simple, so it can simplify the cutting process to a certain extent. As a result, there is practical application of value which can improve the efficiency of production.This paper has two parts: The first part gives out four-block patterns for rectangular blanks (FBPFRB) which includes the following steps. The first step calculates the normal lengths. The second step determines the maximum number of each type of blanks in the different homogeneous blocks by the dynamic programming algorithm. The third step gets the maximum value in the four-block patterns and generates the patterns.The second part combines FBPFRB algorithm with Linear Programming as FBPFRBLP algorithm. The steps are as follows. First, initialize the basic feasible solution. Second, the blank values related to the current base matrix are obtained from the simplex method. Third, call FBPFRB algorithm to generate a four-block pattern according to the current blank values. Forth, if it can improve the result, consider to introduce the current pattern into the base matrix and go to the second step. Otherwise, go to the fifth step. Fifth, output the pattern.Two groups of instances reported in the literature are used to test the algorithm. The first group tests the unconstrained two-dimensional rectangular guillotine-cutting problem. In other words, it determines the patterns of the sheet with unlimited number of blanks to get the maximum value of the sheet. Use FBPFRB algorithm to generate the optimal four-block patterns for each example, and compare the patterns with two-stage and three-block patterns. The computational result indicates the four-block patterns have higher material utilization on average. The second group is rectangular cutting experiment. Cut out all required blanks so as to minimize the total cost of the sheets. The computational results indicate that when only homogeneous strips are allowed, using four-block patterns can get higher or equal material utilization than three-block, two-stage, T-shape and three-stage cutting patterns. When general strips are allowed, four-block patterns may get lower material utilization than T-shape, two-segment and three-stage cutting patterns, but they can simplify the cutting process efficiently. Also, the computational results indicate that the computation time of FBPFRBLP algorithm is reasonable for practical using.Four-block patterns is simple, also it can simplify the cutting process efficiently. The achieving material utilization is not far from the other cutting patterns. So, the algorithm of four-block patterns is a recommendable one.