Your browser does not support the NLM PubReader view.
Go to this page to see a list of supporting browsers.

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

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

Article Information

Corresponding Author: Jun Ji* , ji_jun2000@sina.com

Jun Ji*, School of Mechanical, Electronic Engineering, Beijing Polytechnic, Beijing, China, ji_jun2000@sina.com

Dun-hua Huang*, School of Mechanical, Electronic Engineering, Beijing Polytechnic, Beijing, China, 1448402711@qq.com

Fei-fei Xing*, School of Mechanical, Electronic Engineering, Beijing Polytechnic, Beijing, China, xingfeifei@126.com

Yao-dong Cui**, School of Mechanical, Electronic Engineering, Beijing Polytechnic, Beijing, China, 08116293@bjtu.edu.cn

Received: April 10 2020

Revision received: October 7 2020

Accepted: November 8 2020

Published (Print): April 30 2021

Published (Electronic): April 30 2021

Abstract

Abstract: When generating layout schemes, both the material usage and practicality of the cutting process should be considered. This paper presents a two-section algorithm for generating guillotine-cutting schemes of rectangular blanks. It simplifies the cutting process by allowing only one size of blanks to appear in any rectangular block. The algorithm uses an implicit enumeration and a linear programming optimal cutting scheme to maximize the material usage. The algorithm was tested on some benchmark problems in the literature, and compared with the three types of layout scheme algorithm. The experimental results show that the algorithm is effective both in computation time and in material usage.

Keywords: Cutting Stock Problem , Layout , Optimization , Two-Dimensional Cutting

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.

Table 1.
Symbol and function
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.

(1)
[TeX:] $$\begin{array}{c} \min z_{1}=\boldsymbol{C} \cdot \boldsymbol{X} \\ \text { s. } t . \boldsymbol{A} \boldsymbol{X} \geq \boldsymbol{D} \\ \boldsymbol{X} \geq 0 \end{array}$$

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

(2)
[TeX:] $$$$ z_{2}=\max \left(\sum_{i=1}^{m} v_{i} p_{i}\right) $$ s.t. $\boldsymbol{P}$ is a feasible layout$$

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.

(3)
[TeX:] $$\begin{array}{c} n^{(i)}(x, y)=\max \left[n^{(i)}\left(x, y-l_{i}\right)+\operatorname{int}\left(\frac{x}{w_{i}}\right), n^{(i)}\left(x-l_{i}, y\right)+\operatorname{int}\left(\frac{y}{w_{i}}\right)\right] \\ s(x, y)=\max \left[n^{(i)}(x, y) \times v_{i}\right] \end{array}$$

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.

(4)
[TeX:] $$\begin{array}{l} f 1(x, y)=\left\{\max \left[\sum_{i=1}^{M} k_{i} s\left(x_{i}, y\right)\right] ; \sum_{i=1}^{M} k_{i} x_{i} \leq x ; \quad k_{i} \in N\right\} \\ f 2(x, y)=\left\{\max \left[\sum_{i=1}^{N} k_{i} s\left(x, y_{i}\right)\right] ; \sum_{i=1}^{N} k_{i} y_{i} \leq y ; \quad k_{i} \in N\right\} \end{array}$$

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.

(5)
[TeX:] $$\begin{array}{l} g 1(x, y)=\left\{\max \left[\sum_{i=1}^{N} k_{i} f 1\left(x, y_{i}\right)\right] ; \quad \sum_{i=1}^{N} k_{i} y_{i} \leq y ; \quad k_{i} \in N\right\} \\ g 2(x, y)=\left\{\max \left[\sum_{i=1}^{M} k_{i} f 2\left(x_{i}, y\right)\right] ; \quad \sum_{i=1}^{M} k_{i} x_{i} \leq x ; \quad k_{i} \in N\right\} \end{array}$$

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.

(6)
[TeX:] $$\begin{array}{c} v 1_{\mathrm{XX}}=\max [g 1(x, W)+g 1(L-x, W)] \\ v 1_{\mathrm{XY}}=\max [g 1(x, W)+g 2(L-x, W)] \\ v 1_{\mathrm{YY}}=\max [g 2(x, W)+g 2(L-x, W)] \\ v 1=\max \left(v 1_{\mathrm{XX}}, v 1_{\mathrm{XY}}, v 1_{\mathrm{YY}}\right) \end{array}$$

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.

(7)
[TeX:] $$\begin{array}{c} v 2_{\mathrm{XX}}=\max [g 1(L, y)+g 1(L, W-y)] \\ v 2_{\mathrm{XY}}=\max [g 1(L, y)+g 2(L, W-y)] \\ v 2_{\mathrm{YY}}=\max [g 2(L, y)+g 2(L, W-y)] \\ v 2=\max \left(v 2_{\mathrm{XX}}, v 2_{\mathrm{XY}}, v 2_{\mathrm{YY}}\right) \end{array}$$

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

(8)
[TeX:] $$v_{\mathrm{H}-2 \mathrm{SECTION}}=\max (v 1, v 2)$$

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.

Table 1.
Calculation results of six test problems

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.

Table 3.
Calculation results of 10 test problems

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

Biography

Jun Ji
https://orcid.org/0000-0002-8272-9908

bio1.png

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.

Biography

Dun-hua Huang
https://orcid.org/0000-0002-5537-2149

bio2.png

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.

Biography

Fei-fei Xing
https://orcid.org/0000-0002-3396-1823

bio3.png

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.

Biography

Yao-dong Cui
https://orcid.org/0000-0002-3472-1442

bio4.png

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.

References

  • 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:[[[-]]]

Table 1.

Symbol and function
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

Table 1.

Calculation results of six test problems
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

Table 3.

Calculation results of 10 test problems
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
The Block-diagram of the design idea of this paper.
General two-section layout and its section cutting line.
A same-shape block.
HX-2SECTION layout and its cutting process.
Process of solving the problem.
The cutting line divides the sheet into two sections: (a) vertical cutting line and (b) horizontal cutting line.
Layout diagrams of six test problems: the layout of (a) P1, (b) P2, (c) P3, (d) P4, (e) P5, and (f) P6.
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.