## Jun Ji* , Dun-hua Huang* , Fei-fei Xing* and Yao-dong Cui**## |

Parameter | Definition |
---|---|

L,W | Sheet length and width, L≥W |

𝑚 | Number of different blank sizes |

[TeX:] $$l_{i}, w_{i}, v_{i}, d_{i}$$ | Length, width, value and demand respectively of the ith blank, 1≤i≤m |

𝑫 | 𝐷=[𝑑1,𝑑2,⋯,𝑑𝑚]𝑇 , 𝑑𝑖 indicates the demand of the 𝑖th blank |

n | Number of cutting patterns considered |

X | X=[TeX:] $$\left[x_{1}, x_{2}, \cdots, x_{n}\right]^{T}$$，[TeX:] $$x_{j}$$ indicates the number of sheets by the jth layout, 1≤j≤n |

A | Matrix of m rows and n columns with the elements [TeX:] $$a_{i j}$$ representing the number of the ith blanks in each sheet for by the jth layout, 1≤j≤n |

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

V | Vector of the current blank values, V=[[TeX:] $$\left[v_{1}, v_{2}, \ldots, v_{m}\right]$$] |

P | P=[TeX:] $$\left[p_{1}, p_{2}, \cdots, p_{m}\right]^{T}$$, [TeX:] $$p_{i}$$ indicates the number of the ith blank size included, 1≤i≤m. |

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

s(x,y) | The value of the same-shape block x×y |

f1(x,y) | The maximum value of X segment x×y |

f2(x,y) | The maximum value of Y segment x×y |

g1(x,y) | The maximum value of X section x×y |

g2(x,y) | The maximum value of Y section x×y |

v1 | The maximum value of the HX-2SECTION layout |

v2 | The maximum value of the HY-2SECTION layout |

[TeX:] $$$$ | The maximum value of the H-2SECTION layout |

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.

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).

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.

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

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.

Table 1.

No. | v1 | v2 | v3 | v2/v1 (%) | v3/v1 (%) | t1 |
---|---|---|---|---|---|---|

P1 | 4492074 | 4490544 | 4480372 | 99.97 | 99.74 | 0.40 |

P2 | 4493050 | 4488944 | 4484676 | 99.91 | 99.81 | 0.34 |

P3 | 4497594 | 4489836 | 4489341 | 99.83 | 99.82 | 0.37 |

P4 | 4492558 | 4487967 | 4483009 | 99.90 | 99.79 | 0.36 |

P5 | 4493361 | 4485616 | 4482627 | 99.83 | 99.76 | 0.35 |

P6 | 4496824 | 4494340 | 4491008 | 99.94 | 99.87 | 0.35 |

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.

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].

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.

Table 3.

No. | Material usage (%) | Improvement (%) | Computation time (s)H-2SECTION_A | |
---|---|---|---|---|

H-2SECTION_A | TA | |||

1 | 98.44 | 98.06 | 0.38 | 0.35 |

2 | 98.52 | 98.07 | 0.45 | 1.76 |

3 | 99.37 | 98.60 | 0.77 | 9.23 |

4 | 98.86 | 97.79 | 10.7 | 1.77 |

5 | 99.44 | 98.89 | 0.55 | 16.67 |

6 | 96.62 | 96.58 | 0.04 | 0.20 |

7 | 99.14 | 99.11 | 0.03 | 53.02 |

8 | 99.18 | 98.45 | 0.73 | 11.72 |

9 | 98.94 | 98.20 | 0.74 | 8.19 |

10 | 99.62 | 99.07 | 0.55 | 33.87 |

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.

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.

She received B.S. degree in computer science from University of Jinan in 2003, M.S. degree in computer science from Guangxi Normal University in 2006, and Ph.D. degree in School of Mechanical Electronic and Control engineering from Beijing Jiaotong University in 2012. She is currently an associate professor in the School of Mechanical, Electronic Engineering, Beijing Polytechnic. Her research interests include optimization and computation techniques, computer added design.

He received B.S. degree in mechanical engineering and automation from Beijing Technology and Business University in 2002, M.S. degree in control engineering from Beihang University in 2009. He is with philosophy in organization development from Assumption University as a Ph.D. candidate. He is currently a professor in the School of Mechanical, Electronic Engineering, Beijing Polytechnic. His research interests include intelligent control.

She received B.S. degree in applied mathematics from University of Jinan in 2004, M.S. degree in applied mathematics from Shandong Normal University in 2007, and Ph.D. degree in School of Mechanical Electronic and Control engineering from Beijing Jiaotong University in 2013. She is currently a lecturer in the School of Mechanical, Electronic Engineering, Beijing Polytechnic. Her research interests include optimiza-tion and computation techniques, computer added design.

He received B.S., M.S., and Ph.D. degree in computer science from Nanjing University of Aeronautics and Astronautics in 1982, 1985, and 2002, respectively. He is currently a professor in School of Computer, Electronics and Information, Guangxi University. His research interests include optimization and computation techniques, computer added design.

- 1 C. H. Cheng, B. R. Feiring, T. C. E. Cheng, "The cutting stock problem—a survey,"
*International Journal of Production Economics*, vol. 36, no. 3, pp. 291-305, 1994.custom:[[[-]]] - 2 P. E. Sweeney, E. R. Paternoster, "Cutting and packing problems: a categorized, application-orientated research bibliography,"
*Journal of the Operational Research Society*, vol. 43, no. 7, pp. 691-706, 1992.custom:[[[-]]] - 3 R. Alvarez-Valdes, F. Parreno, J. M. Tamarit, "A tabu search algorithm for a two-dimensional non-guillotine cutting problem,"
*European Journal of Operational Research*, vol. 183, no. 3, pp. 1167-1182, 2007.custom:[[[-]]] - 4 R. Baldacci, M. A. Boschetti, "A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem,"
*European Journal of Operational Research*, vol. 183, no. 3, pp. 1136-1149, 2007.custom:[[[-]]] - 5 P. C. Gilmore, R. E. Gomory, "Multistage cutting stock problems of two and more dimensions,"
*Operations Research*, vol. 13, no. 1, pp. 94-120, 1965.custom:[[[-]]] - 6 J. Ji, Y. P. Lu, J. Z. Cha, J. Q. Yu, Y. D. Cui, "An exact algorithm for large-scale unconstrained three staged cutting problems with same-size block requirement,"
*International Journal of Information and Management Sciences*, vol. 23, no. 1, pp. 59-78, 2012.custom:[[[-]]] - 7 M. Hifi, "Exact algorithms for large-scale unconstrained two and three staged cutting problems,"
*Computational Optimization and Applications*, vol. 18, no. 1, pp. 63-88, 2001.custom:[[[-]]] - 8 Y. Cui, "Generating optimal T-shape cutting patterns for rectangular blanks,"
*Proceedings of the Institution of Mechanical EngineersPart B: Journal of Engineering Manufacture*, vol. 218, no. 8, pp. 857-866, 2001.custom:[[[-]]] - 9 Y. Cui, D. He, X. Song, "Generating optimal two-section cutting patterns for rectangular blanks,"
*Computers & Operations Research*, vol. 33, no. 6, pp. 1505-1520, 2006.custom:[[[-]]] - 10 P. C. Gilmore, R. E. Gomory, "A linear programming approach to the cutting stock problem—Part II,"
*Operations Research*, vol. 11, no. 6, pp. 863-888, 1963.custom:[[[-]]] - 11 J. E. Beasley, "Algorithms for unconstrained two-dimensional guillotine cutting,"
*Journal of the Operational Research Society*, vol. 36, no. 4, pp. 297-306, 1985.custom:[[[-]]] - 12 J. C. Herz, "Recursive computational procedure for two-dimensional stock cutting,"
*IBM Journal of Research and Development*, vol. 16, no. 5, pp. 462-469, 1972.custom:[[[-]]] - 13 M. Hifi, V. Zissimopoulos, "A recursive exact algorithm for weighted two-dimensional cutting,"
*European Journal of Operational Research*, vol. 91, no. 3, pp. 553-564, 1996.custom:[[[-]]] - 14 G. Young-Gun, Y. J. Seong, M. K. Kang, "A best-first branch and bound algorithm for unconstrained two-dimensional cutting problems,"
*Operations Research Letters*, vol. 31, no. 4, pp. 301-307, 2003.custom:[[[-]]] - 15 J. V. De Carvalho, "LP models for bin packing and cutting stock problems,"
*European Journal of Operational Research*, vol. 141, no. 2, pp. 253-273, 2002.custom:[[[-]]]