Optimal Two-Section Layouts for the Two-Dimensional Cutting Problem

1. Introduction

The cutting stock problem is common to production practice of many industries, problem. Solutions to the problem seek to make the highest use of material, in order to improve the usage of materials effectively and reduce production costs, which is an effective way to increase the efficiency of enterprises. In manufacturing, many parts are rectangular, so much research has taken place on the optimal layout of rectangular parts.

This paper discusses the two-dimensional guillotine-cutting stock (TDGCS) problem [1-5], cutting a given type and number of blanks from rectangular sheets. It is necessary to determine an optimal layout scheme in order to minimize the total value of the sheet consumed. The TDGCS problem belongs to a typical high-complexity NP problem. It has a significant influence on the industries such as manufacturing, ship-building, automobile industry. The unconstrained two-dimensional guillotine-cutting problem as the UTDGC problem [6-9], which describe cutting a sheet into rectangles of a variety of given sizes and values, where the number of times that each rectangle appears in the sheet is unconstrained, and the layout goal is to maximize the total area of the rectangles contained in the sheet. A solution to the TDGCS problem consists of several layouts, each of which may be constructed by an algorithm for the UTDGC problem. Gilmore and Gomory [10] proposed a linear programming (LP) method to solve the TDGCS problem, which has been widely used. The LP model is solved by iteration as each iteration needs to generate a new optimal layout.

At present, algorithms have been proposed by many researchers to the solve UTDGC problem. Gilmore and Gomory [10] proposed dynamic programming. Beasley [11] improved Gilmore’s method and applied the branch-and-bound method. Herz [12] has developed a tree search method. Hifi and Zissimopoulos [13] and Young-Gun et al. [14] proposed the exact algorithms that could optimally solve the small-scale UTDGC problem. Algorithms above could effectively solve the small-scale UTDGC problem. Because the UTDGC problem is an NP problem, the time spent by the above algorithms in solving such a large-scale problem is unacceptably long. Therefore, a common way to approach the problem is to adopt a specific layout, which can obtain a high material usage in a short time, meet the specific process requirements with simple cutting process and have good adaptability in industrial production. Many researchers have studied specific types of layout. Hifi [7] proposed the classic two-stage and three-stage layout methods. Beasley [11] introduced an exact algorithm to generate general layout methods. Cui [8] proposed a general T-shaped layout, and applied new restrictions in the general two-section layout method [9]. Although the material usage of these layouts may be slightly lower, the calculation time is short and the layout process is simple.

This paper proposes a new restriction on the cutting patterns. It simplifies the cutting process by only allowing blanks of the same size to appear in a block. An algorithm (referred to as the H-2SECTION_A) is proposed to generate the cutting layout scheme for the same-shape blocks to solve the TDGCS problem. In the algorithm, the blank of the same size in each size of the same-shape blocks on the sheet is limited, and the strips to which these blanks belong to are parallel or perpendicular to each other. The usage of sheet metal can be improved by determining the number of the optimal same-shape blocks. In this paper, the test problems in the literature are used to compare the layout algorithm with two types of layouts and a general T-shape layout scheme. The experimental results show that the algorithm in this study is effective in calculating time and sheet usage, and it is able to simplify the cutting process. It should be noted that the H-2SECTION_A algorithm presented could also be seen as an improved version of the algorithm of Cui et al. [9].

The remainder of this paper is organized as follows. Section 2 provides some definitions of the H-2SECTION layout, followed by the process to solve the TDGCS problem in Section 3. An exact algorithm is based on knapsack problems combined with dynamic programming techniques to generate the H-2SECTION layout in Section 4. A set of test problem instances and performance analysis of the proposed algorithms are then presented in Section 5. The results indicate that the H-2SECTION_A was indeed better than the optimal above three solutions. Section 6 concludes the paper. Fig. 1 shows a block diagram of overall the design this paper.

2. Layout and Layout Scheme

2.1 The General Two-Section Layout

The general two-section layout divides the sheet into two sections by a horizontal or vertical cutting line. As shown in Fig. 2, first, the vertical cutting line divides the sheet into left and right sections. Second, the horizontal cutting lines divide each of the section into strips. Finally, the punch divides the strips into blanks, where the number in the box indicates the item number of each size of blanks.

2.2 The Same-Shape Two-Section Layout

A same-shape block, that is, in a sheet, is only composed of blanks of the same size, and the strips that these blanks belong to are parallel or perpendicular to each other. Fig. 3 shows a same-shape block. The number of cuts is numbered in order according to the strip direction. When cutting, the first division cuts two horizontal stripes, the second division cuts five vertical stripes, the third dividing cuts two horizontal stripes, and the fourth dividing cuts two vertical stripes.

Fig. 1.

The Block-diagram of the design idea of this paper.

Fig. 2.

General two-section layout and its section cutting line.

Fig. 3.

A same-shape block.

A segment includes multiple same-shape blocks. If it is composed of a series of same-shape blocks arranged horizontally from left to right, it is called an X segment; if it consists of a series of same-shape blocks arranged vertically from top to bottom, it is called a Y segment.

A section consists of multiple segments. If it includes a series of X segments arranged vertically from top to bottom, it is called X section; if it is composed of Y segments arranged horizontally from left to right, it is Y direction section.

In this paper, a same-shape two-section layout (H-2SECTION) is proposed. The H-2SECTION layout means that the sheet is divided into two sections by a horizontal or vertical cutting line. When the cut line is vertical, it is called an HX-2SECTION layout (Fig. 4); when the cut line is horizontal, it is called an HY-2SECTION layout. As shown in Fig. 4, the number represents the cutting line. First, cutting line 1 divides the sheet into two sections. Second, cutting line 2 in each section divides the sections into segments. Finally, cutting lines 3 divides the segments into same-shape blocks.

Fig. 4.

HX-2SECTION layout and its cutting process.

In Fig. 4, the same-shape block with blank No. 1 in the upper right corner wireframe has just one blank. The H-2SECTION layout is a superset of the general two-section layout. It is made up of strips comprising the same size of blanks. In the stage of separating the strip into blanks, two connected feeding distances are called one step, and all steps are the same within each strip. It can be concluded that the cutting process of H-2SECTION layout is simple.

2.3 Layout Scheme

A layout scheme can have one or more layout modes, which indicates the number of sheets cut according to each layout mode. The “optimal layout scheme” is the layout scheme with the highest cutting usage; a “near optimal layout scheme” is one with the cutting usage close to the highest.

3. The Mathematical Model of TDGCS Problem

3.1 Symbol and Function

Table 1 lists some symbols and functions. Most of them will be re-introduced when they are used for the first time. It may be found that it is more convenient to look for the parameter definition in the table rather than in the text.

3.2 The Process to Solve the TDGCS Problem

The LP method is reasonable for solving the TDGCS problem if the blank demands are large. Fig. 5 shows the process of solving the problem. The solution includes multiple cutting layouts and indicates the number of sheets to be cut according to each cutting layout. To begin, an initial feasible solution must be constructed. To improve the solution, it is necessary to determine the current value of the blank according to the demand. An approach must be found to generate the current optimal layout P, which yields the maximum total value of blanks among all cutting layouts. If the value of the layout P is greater than previous sheet used, introduce it to form a new solution, and go to the next cycle. Otherwise, the current solution is the optimal one.

Fig. 5.

Process of solving the problem.

3.3 The Mathematical Model of the TDGCS Problem and Its Solution

The exact algorithm for generating the H-2SECTION layout and LP of column generation are combined to generate a layout scheme algorithm to solve the TDGCS problem. The following linear programming model was used.

C=[TeX:] $$\left[c_{1}, c_{2}, \ldots, c_{n},\right]$$, where n is the number of layout methods，and [TeX:] $$c_{j}$$ is the value of the sheet area for the sheet by the jth layout.

X=[TeX:] $$\left[x_{1}, x_{2}, \cdots, x_{n}\right]^{T}$$, where [TeX:] $$x_{j}$$ is the number of sheets for the jth layout, 1≤j≤n.

A is a two-dimensional matrix whose elements [TeX:] $$a_{i j}$$ represent the number of blanks in each sheet for the jth layout, 1≤i≤m.

D=[TeX:] $$\left[d_{1}, d_{2}, \cdots, d_{m}\right]^{T}$$, where [TeX:] $$d_{i}$$ indicates the demand of the ith blank.

Using column generation to solve the above model, in each iteration cycle, it is necessary to call the generation algorithm of each of the above layout methods according to the current value of the blank to generate a layout scheme.

Model (1) is an LP model, which can be solved according to the following steps [15].

Step 1: Determine the initial feasible solution for model (1). Let A be the unit matrix, and the initial feasible solution is X=D. The ith method includes only one blank of the ith blank, 1≤i≤m.

Step 2: Determine the current blank value vector, [TeX:] $$V=C A^{-1}=\left[v_{1}, v_{2}, \ldots, v_{m}\right]$$, where [TeX:] $$v_{i}$$ indicates the value of the ith blank.

Step 3: Find a layout that may improve the objective function. Suppose the layout mode under investigation is [TeX:] $$P=\left[p_{1}, p_{2}, \cdots, p_{m}\right]^{T}$$, where [TeX:] $$p_{i}$$ is the number of the ith blank size included, 1≤i≤m. According to the theory of LP, if c-V∙P<0 , it is possible to improve the goal value by introducing layout P. Use a column P in the replacement matrix A, and then go to the second step. Otherwise, there is no layout that can improve the objective function of the model (1). The current solution is the optimal solution. P can be solved using model (2).

4. The Generation of H-2SECTION Layouts

This section describes the algorithm for generating the optimal layout H-2SECTION layout, where i is the number of the type of blank, 1≤i≤m, [TeX:] $$l_{i}$$ , [TeX:] $$w_{i}$$ and [TeX:] $$v_{i}$$ are the length, width and value of the ith blank size, respectively; 1≤i≤m; L and W are the length and width of the sheet, 0≤x,y≤L, x and y are the length and width of the same-shape block, segments and H-2SECTION layout, respectively.

Step 1: Determine the value s(x,y) of the same-shape block x×y

Denote [TeX:] $$n^{(i)}(x, y)$$ (x,y) as the maximum number of the ith blank in the same-shape block of dimensions x×y.

Step 2: Determine the optimal same-shape blocks layout of segments

f1(x,y) is referred to as the maximum value of X segment of dimensions x×y, and f2(x,y) is referred to as the maximum value of Y segment of dimensions x×y，where k_i is the number of the same-shape blocks.

Step 3: Determine the optimal segments layout of sections

g1(x,y) is referred to as the maximum value of X section of dimensions x×y, and g2(x,y) is referred to as the maximum value of Y section of dimensions x×y，where [TeX:] $$k_{i}$$ is the number of the segments.

Step 4: Determine the optimal H-2SECTION layout

When the sheet is divided into two sections by a vertical cutting line, v1 refers to the value of the HX-2SECTION layout. As shown in Fig. 6(a), the left and right sections can be either an X section or a Y section. There are three cases. When both sections are X sections, [TeX:] $$v 1_{X X}$$ is the layout value. When one is an X section and the other is a Y section, [TeX:] $$v 1_{X Y}$$ is the layout value. When both sections are Y sections, [TeX:] $$v 1_{Y Y}$$ is the layout value.

When the sheet is divided into two sections by a horizontal cutting line, v2 is the value of the HY-2SECTION layout. As shown in Fig. 6(b), the upper and lower sections can be either X-or Y-sections. There are three cases. When both sections are X sections, [TeX:] $$v 2_{X X}$$ is the layout value. When one is an X section and the other is a Y section, [TeX:] $$v 2_{X X}$$ is the layout value. When both sections are Y sections, [TeX:] $$v 2_{X X}$$ is the layout value.

Let [TeX:] $$\text { V }_{H-2 S E C T I O N}$$ be the maximum value of H-2SECTION layout.

Fig. 6.

The cutting line divides the sheet into two sections: (a) vertical cutting line and (b) horizontal cutting line.

5. The Computational Results

All experiments were carried out on a computer with a processor speed of 2.7 GHz of and 8 GB of RAM. Through the test problems in the literature, the algorithm in this paper was compared with two types of two-section layout algorithms and general T-shape layout scheme respectively. The following notations are used to denote the algorithms:

H-2SECTION_A The exact algorithm for the problem of H-2SECTION layout

BOPT Bealy’s exact algorithm [11] for the of general (non-staged) guillotine cutting problem

TA Cui’s exact algorithm [8] for the of T-shape layout problem

TSEC Cui’s exact algorithm [9] for the of two-section layout problem

5.1 The First Group Problems

Using the six test questions [9,Table 4], the sheet size (cm × cm) is 3000 × 1500. The blank size is evenly distributed in the range [200,700], and the blank value is equal to its area. For each test problem, this study generates an algorithm for the optimal two-section layout of the same-shape block. In [11], the general layout is generated by an exact algorithm, and a two-section layout was generated by the algorithm in [9]. where v1, v2, and v3 denote the values of the H-2SECTION_A, BOP and the TSEC, respectively, and t1 denotes the computation time of the H-2SECTION_A. Table 2 shows the experimental results.

Among the six test problems, the optimization results of the algorithm in this study are better than those of the two types of layout algorithms. Both the H-2SECTION_A and TSEC can will generate optimal two-section patterns. The H-2SECTION_A may be seen as an improved version of the TSEC. The algorithm in this paper took 2.17 seconds to solve the six test problems in total, with average calculation time of each test problem being 0.36 seconds, but TSEC took 0.01 seconds on a computer with processor speed of 1.9. Therefore, in future work, it will be necessary to simplify the structure of the same-shape block to further shorten the calculation time.

For the six test problems, the calculation time variance of H-2SECTION_A was 0.021. From the calculation time variance, the reliability of the H-2SECTION_A in this study is good.

Fig. 7 is a layout diagram of the six test problems generated by the algorithm of the optimal layout method in this study.

5.2 The Second Group Problems

Using the 10 test questions [8,Table 7], the H-2SECTION_A layout was compared with the TA. In [8], the sheet size was evenly distributed in the range [1500,3000], the blank type in the range [2,16], the blank size in the range [150,600], and the blank demand in the range [1000,20000].

Fig. 7.

Layout diagrams of six test problems: the layout of (a) P1, (b) P2, (c) P3, (d) P4, (e) P5, and (f) P6.

The calculation time for TA was not give calculation time in the literature, so the calculation time is not compared here, although the calculation time of the H-2SECTION_A is listed. Table 3 shows the experimental results. In the 10 test problems, the optimization results of the H-2SECTION_A were better than those of TA.

Among the 10 test problems, the material usage of the two algorithms was compared, and the fourth problem had the largest improvement. Fig. 8 shows a layout plan diagram for the fourth problem.

Fig. 8.

The layout scheme for the sixth problem (3374 pieces; usage of 98.86%): (a) 963 pieces, (b) 1324 pieces, (c) 315 pieces, (d) 101 pieces, (e) 14 pieces, (f) 426 pieces, and (g) 231 pieces.

6. Conclusion

The H-2SECTION_A can generate optimal two-section patterns for solving TDGCS problem, can improve the material usage, and have a good adaptability at the same time, which is especially suitable for the case of cutting and stamping processes. In this study, the test problems previously described in the literature were used. Compared with two types of layout algorithms and the general T-shape layout scheme algorithm, The H-2SECTION_A improved the material usage with a reasonable time, so it is worth recommending. There are two avenues of investigation for follow-up work. We will further simplify the structure of the same-shape block to improve the calculation speed. In addition, when applying the LP method combined with the layout algorithm to solve large-scale problems, the utilization rate of the plates can be further improved by increasing the number of plates so that better layout schemes can be selected on more plates.

Acknowledgement

This research was supported by the National Natural Science Foundation of China (No. 71371058, 61363026), Education Commission Scientific Foundation of Beijing (No. KM201910858004) and Natural Science Foundation of Beijing Polytechnic (No. 2019Z002-003-KXB).