# A Heuristic Approach for Two-Dimensional Rectangular Cutting Stock Problem considering Balance for Material Utilization and Cutting Complexity

Authors: Dianjian Wu; Guangyou Yang
Journal: Advances in Materials Science and Engineering
 (2021)

---

## Abstract

The common staged patterns are always required during the cutting process for separating a set of rectangular items from rectangular plates in manufacturing industries. Two-staged patterns can reduce cutting complexity at the expense of material utilization; three-staged patterns do the opposite. Combining these two types of staged patterns may be a good balance for two contradictory objectives of material utilization and cutting complexity. A heuristic approach is proposed to solve the two-dimensional rectangular cutting stock problem with a combination of two-staged general patterns (2SGP) and three-staged homogenous patterns (3SHP). Firstly, the 2SGP and 3SHP are constructed by using recursive techniques. The pattern with the larger value is selected as the candidate pattern. Then, the value of each item is corrected according to the current candidate pattern. A cutting plan accurately satisfying all items demand is obtained by using the sequential heuristic algorithm. Finally, the cutting plan with a minimum number of used plates is achieved by applying the iterative algorithm. The computational results indicate that the proposed heuristic approach is more effective in material utilization and cutting complexity than the two published algorithms with staged patterns.


---

## Body

## 1. Introduction

The two-dimensional rectangular cutting stock problem (2DRCSP) is always encountered in many manufacturing industries, such as steel products, paper, wood, and glass. A set of rectangular items with specific demand need to be produced from cutting the same rectangular plates with the optimization objective of minimizing the number of used plates. This feature of the 2DRCSP is referred to as a two-dimensional rectangular single stock size cutting stock problem (2DRSSSCSP) in Wäscher et al. [1]. The solution of the 2DRSSSCSP is a cutting plan including a set of different patterns with their frequencies. Therefore, how to design patterns with optimization strategy becomes the most noteworthy problem.Some practical restrictions need to be observed while solving the 2DRSSSCSP. Lodi et al. [2] introduced two common application restrictions of “Guillotine cuts” and “Orientation.” Based on these two restrictions, the 2DRSSSCSP can be categorized as four variants, including 2DRSSSCSP-GO, 2DRSSSCSP-GR, 2DRSSSCSP-FO, and 2DRSSSCSP-FR, which are shown in Figure 1. G represents that the cutting style must be guillotine cuts, where each cut must be performed from edge-to-edge parallel to each side of the used rectangular plate. F represents that the cutting style can be free, namely, not considered guillotine cuts. O denotes that the items are oriented, that is, not rotated. R denotes that the items can be rotated by 90°.Figure 1
Four variants of the 2DRSSSCSP: (a) 2DRSSSCSP-GO. (b) 2DRSSSCSP-GR. (c) 2DRSSSCSP-FO. (d) 2DRSSSCSP-FR.
(a)(b)(c)(d)This paper mainly focuses on the research of the 2DRSSSCSP-GR, where the cutting style must be guillotine cuts, and each item is allowed to be rotated by 90°. The staged patterns are always constructed to satisfy guillotine cuts. The common staged patterns are two-staged patterns and three-staged patterns. In general, the two-staged patterns have simpler cutting complexity but less material utilization than the three-staged patterns. Two-staged patterns are welcomed to reduce cutting complexity when the material cost is relatively cheaper than the guillotine cuts cost. Three-staged patterns are selected to improve material utilization otherwise. It is difficult to consider two contradictory objectives of material utilization and cutting complexity during solving the 2DRSSSCSP-GR with only two-staged patterns or three-staged patterns. Therefore, combining two types of staged patterns for the 2DRSSSCSP-GR may be an effective approach to balance material utilization and cutting complexity.We firstly introduce two-staged patterns and three-staged patterns based on two types of strips in Figure2. Each homogenous strip in Figure 2(a) is only composed of multiple same items. Each general strip in Figure 2(b) is composed of multiple items of different sizes. Therefore, there are four common types of staged patterns, including two-staged homogenous patterns (2SHP), two-staged general patterns (2SGP), three-staged homogenous patterns (3SHP), and three-staged general patterns (3SGP) in Figure 3. The arrows denote the position of a guillotine cut. The numbers nearby the arrows denote the sequence of guillotine cut in Figure 3. For example, as shown in Figure 3(a), the first guillotine cut (GC_1) is horizontal to cut off the topside strip. The second guillotine cut (GC_2) is vertical to separate three items. Generally, the 2SHP have the lowest material utilization and simplest cutting complexity, and 3SGP have the opposite. The 2SGP and 3SHP can compromise material utilization and cutting complexity. Meanwhile, all items designed on the plate can be divided exactly with three guillotine cuts according to the 2SGP and 3SHP, which may be more suitable for a cutting machine during the cutting stock process. Therefore, we choose the 2SGP and 3SHP as candidate staged patterns for constructing a cutting plan in this paper.Figure 2
Two types of strips. (a) Homogenous strips. (b) General strips.
(a)(b)Figure 3
Four common types of staged patterns. (a) 2SHP. (b) 2SGP. (c) 3SHP. (d) 3SGP.
(a)(b)(c)(d)Staged patterns are necessary to satisfy guillotine cutting, which is restricted by cutting machines during the manufacturing process of cutting flat glass in the glass industry, rocks in the granite and marble industries, steel blocks in the metallurgical industry, and so on. For instance, the cutting process for steel plates is shown in Figure4, where a rectangular steel plate is cut into demanded items by three guillotine cuts. In the first guillotine cutting with single side crop shear, a rectangular steel plate is divided into segment 1 and segment 2. In the second guillotine cutting with double side crop shear, segment 1 is separated into strips 1, 2, and 3. Meanwhile, segment 2 is separated into strips 4, 5, and 6. In the final guillotine cutting with multiple side crop shear, strips 1, 2, and 3 are all cut into two pieces of item 1. Strip 4 is cut into three pieces of item 1 and one waste. Strip 5 is cut into two pieces of item 3 and another waste. Strip 6 is exactly cut into four pieces of item 2. Similar to the paper cutting problem and the glass cutting problem, the steel plate cutting problem has also been treated as the application of the 2DRCSP with staged patterns.Figure 4
Cutting process for steel plates.Based on the 2SGP and 3SHP, a heuristic approach is proposed to solve the 2DRSSSCSP-GR. Firstly, the 2SGP and 3SHP are built by using recursive techniques. The candidate pattern with the objective of a large pattern value can be chosen from the generated 2SGP and 3SHP. Then, the value of each item is corrected according to the current candidate pattern. A cutting plan including 2SGP and 3SHP is achieved with a sequential heuristic algorithm until all items demands are fulfilled. Finally, the cutting plan with the minimum number of used plates is achieved by applying the iterative algorithm.The remainder of the paper is organized as follows: the related literature is reviewed in Section2. The generation procedures for the 2SGP and 3SHP are introduced in Section 3. An iterative sequential heuristic procedure (ISHP) considering both 2SGP and 3SHP is proposed for solving the 2DRSSSCSP-GR in Section 4. The comparison results are reported in Section 5, followed by the conclusions in Section 6.


## 2. Literature Review

To review the gradual advancement of the literature for solving the 2DRCSP clearly, the related literature in the last two decades is reviewed according to chronological order. The critical analysis of the proposed methodology in each literature is also presented simultaneously.Hifi and Roucairol [3] presented an approximate algorithm and an exact algorithm for solving the 2DRCSP with restriction of two-staged guillotine cutting. Their approximate algorithm was constructed by using a dynamic programming procedure to solve multiple bounded knapsack problems. Their exact algorithm was built by a tailored branch-and-bound procedure, which determined lower and upper bounds by dynamic programming properties and branched based on the solution space. As their proposed algorithms mainly apply dynamic programming, which is a typical greedy algorithm. The solution by their proposed algorithms is easily trapped into local optimization. Therefore, the proposed algorithms can be improved to get a better solution.Vanderbeck [4] focused on the 2DRCSP with restriction of three-staged guillotine cutting. The optimization objective focused on minimizing waste and other production goals, including aging stock, optional orders, and fixed setup cost. Their solution approach is a repeated use of the column generation method to get an approximate solution for the 2DRCSP. This approach can get an optimal solution in acceptable computation time when the type number of order pieces is less. However, the solution space becomes huge when the type number of order pieces is large. It is hard to achieve an optimal solution.Alvarez-Valdes et al. [5] developed several heuristic approaches for solving the 2DRCSP based on the framework of the Gilmore–Gomory column generation scheme [6]. They use different heuristic algorithms, including the GRASP and tabu search, to generate each new cutting pattern by solving the subproblem. It can increase solution space at the expense of computation time. Their proposed method actually belongs to column generation techniques, which is suitable for 2DRCSP with less number of order piece type.Suliman [7] proposed a sequential heuristic procedure for the 2DRCSP to minimize the trim loss. The sequential heuristic procedure consisted of three steps. A width-cutting pattern with the minimum width trim loss was obtained in the first step. A cutting pattern was achieved when the length was determined with the minimum length trim loss. The frequency of the generated cutting pattern was confirmed based on the remaining number of each item. The proposed procedure is the simple sequential heuristic algorithm, which can get a solution in a short computation time. But it can trap into locally optimal solution and hard to get globally optimal solution.Belov and Scheithauer [8] solved the 2DRCSP with restriction of two-staged guillotine cutting by applying a branch-and-cut-and-price algorithm, which is a combination of the LP-based approach in [6] and branch-and-bound with column generation in the Chvatal–Gomory cutting planes. Based on their combination approach, all optimal solutions can be achieved for medium instances in acceptable computation time. However, there were still unsolved instances for larger instances because of the huge complexity of column generation with the large item type.Cintra et al. [9] focused on solving the 2DRCSP with the constraint of guillotine cutting. Their approach framework was also column generation. For generating each new cutting pattern, they used two dynamic programming-based algorithms for the Rectangular Knapsack problem. Their method also was not suitable for the instances with large item type.Cui [10] proposed exact and heuristic algorithms to solve the 2DRCSP with three-staged guillotine cutting. The exact algorithm was actually a branch-and-bound approach, where the lower and upper bounds were obtained by applying dynamic programming techniques to solve the knapsack problems. Meanwhile, one heuristic algorithm was used to get the initial lower bound for the main framework of the exact algorithm. The other heuristic algorithm underestimated the upper bounds of the blocks generated for the main framework of the exact algorithm. The proposed approach just only considered homogenous strips, which was the basic element of the cutting pattern. It can be capable of solving problems with large scale at the expense of reducing the solution space.Hifi et al. [11] solved the 2DRCSP with restriction of two-staged guillotine cutting and fixed-orientation item. The two-staged cutting patterns were generated by a strip-generation procedure. Their proposed beam search was a truncated branch-and-bound algorithm, which selected the elite nodes based on an evaluation operator. Their method can solve the problems with large scale. But the two-staged cutting pattern was a simple and special cutting pattern, whose material utilization was hard to be improved with iterative value correction. The approach was also to get approximate solution by reducing solution space.Silva et al. [12] introduced an integer programming model for the 2DRCSP with four restrictions: two-stage, three-stage, exact, and nonexact. They also addressed other constraints, such as the length of the cuts and the value of the remaining plate. Their proposed model was solved by a commercial solver (CPLEX). Their conclusion claimed that most instances with many item types could be solved in two hours. Several instances were dealt with over two hours. Obviously, it is a long computational time to get an optimal solution for the 2DRCSP occurring in the real enterprise application.Macedo et al. [13] presented an integer linear programming arc-flow model for the 2DRCSP with restriction of two-staged guillotine cutting. They solved the model with the commercial solver (CPLEX). The computational results showed that the proposed arc-flow model also could not solve all the instances. Meanwhile, some instances needed a long computational time to get their solutions.Cui and Huang [14] focused on the 2DRCSP with restriction of three-staged guillotine cutting. The optimization objective was minimizing the sum of used plate cost and cutting cost. The problem was solved by the classical column generation framework, where the new cutting patterns were generated by a pattern-generation procedure. They researched the 2DRCSP with multiple objectives in a different perspective.Cui [15] also addressed the 2DRCSP with three-staged patterns, which can be constructed in three steps. A set of rectangular items can be selected to generate strips in the first step. A set of generated strips can be chosen to build segments in the second step. A set of generated segments can be selected to achieve cutting patterns in the third step. Three large knapsack problems are constructed according to each step. The proposed dynamic programming algorithm was used to solve each knapsack problem to get an optimal pattern. The approach is simple and fast to get the solution. However, the greedy nature of dynamic programming may be influenced to get the optimal solution.Cui and Zhao [16] presented a heuristic algorithm to solve the 2DRCSP with two-staged patterns. The proposed algorithm was a special column generation method, which solved the residual problems repeatedly until all demands were satisfied. Each pattern was generated by using a procedure for the constrained single large object placement problem. They combined the column generation and heuristic algorithm. It is a new idea to solve the 2DRCSP.Cui et al. [17] focused on the 2DRCSP with the objective of plate minimization and pattern reduction. They proposed a sequential grouping heuristic based on the framework of the sequential heuristic procedure. It also applied a grouping technique to select the items, which generated the next pattern by using the dynamic programming algorithm. Meanwhile, the item value can be adjusted with the sequential value correction method. Their approach was actually an improved sequential heuristic procedure. It can be suitable for solving the 2DRCSP with multiple optimization objectives.Cui et al. [18] also addressed the 2DRCSP with three-staged patterns. They proposed a heuristic algorithm according to the construction process of the three-staged pattern. They used the dynamic programming algorithm three times to generate strips, segments, and patterns, respectively. Their approach can get a solution in a short computation time. But it was hard to get an optimal solution because of the greedy nature of the used algorithm.Chen et al. [19] proposed a sequential value correction heuristic for solving the 2DRCSP with constrained three-staged patterns. Their main method was similar to the sequential grouping heuristic proposed in Cui and Zhao [16]. The difference was that Chen et al. [19] used three-staged homogenous patterns as the element for the cutting plan. Cui and Zhao [16] applied simple block patterns, otherwise.Andrade et al. [20] solved the nonexact two-stage 2DRCSP with usable leftovers. They built two bilevel mathematical programming models, which can be reformulated as one-level MIP models. They solved the models by applying the branch-and-cut method of CPLEX.Cui et al. [21] proposed a heuristic algorithm for the 2DRCSP with guillotine cutting. Their algorithm included three procedures. A pattern-generation procedure was used to generate a set of triple-block patterns in the first procedure. A plan-generation procedure was applied to generate a solution in the second procedure. A plan-improvement procedure is also used to generate an improved solution. Their heuristic algorithm was also the same as the sequential value correction heuristic presented in Chen et al. [19].Nascimento et al. [22] presented the 2DRCSP with guillotine cutting. They considered the possibility of 2 and 3 cutting stages in a predefined sequence. A two-level iterative approach was used to solve integer linear programming and constraint programming models for the special 2DRCSP. The models that are in the approach were solved with the libraries of the CPLEX. They also cannot solve all instances in acceptable computation time.Velasco and Uchoa [23] considered the constrained two-dimensional guillotine cutting problem. They presented a weight adjusting algorithm based on integer programming, which was solved using a dynamic programming state-space relaxation. The solution can be obtained by using several iterations of a GRASP-based primal heuristic. The computation time of their approach is not short to get an optimal solution.Long et al. [24] solved the 2DRCSP with nonexact three-stage patterns. Two additional practical constraints had appeared in the cutting production line of steel mills. They were the length between any two adjacent guillotine cuts and the number of guillotine cuts in the second stage by one. Four heuristic algorithms based on column generation were introduced to solve the practical 2DRCSP. Their approach mainly included the column generation technique. Obviously, the computation time may be too long for some instances with larger item type.Martin et al. [25] proposed a top-down cutting approach to solve the mixed-integer linear programming models for the 2DRCSP with Guillotine cutting. Their approach was similar to the branch-and-bound algorithm. It used a binary tree to represent cutting patterns. The root node was the initial plate, and branches correspond to guillotine cuts. They also used a commercial solver (CPLEX) to solve the established model.We can give the summary based on all reviewed literature. There are mainly three optimization methods for solving the 2DRCSP. The first optimization method is based on the integer programming model, which is established according to the 2DRCSP with special constraints and solved with branch-and-bound or existing commercial solver such as CPLEX. Based on [3, 10, 13, 20, 22, 25], the computational complexity is too high with large item type. The runtime of solving several instances is even over two hours. The second optimization method is based on a linear programming model, which is built with special constraints, such as the staged pattern. It can often be solved with the framework of the column generation approach. Based on [4, 6, 8, 9, 14, 24], the computational complexity becomes high with item type increase. But the runtime of solving all instances is in two hours (acceptable computation time) at the expense of solution space, such as using staged patterns. The third optimization method is the heuristic procedure, whose main thought is to generate a cutting pattern using the remaining items with some pattern-generation algorithm repeatedly until all items demand is fulfilled. Based on [7, 15, 19, 21, 23], the computational complexity is moderate with large item type. The runtime of solving all instances is in a short time.According to the contrastive analysis, we select the third method to solve the 2DRCSP. Meanwhile, our method is different from other reviewed literature. We consider the combination of multiple staged patterns to solve the 2DRCSP. It is the first time to integrate two types of staged patterns to solve the 2DRSSSCSP-GR. Therefore, this paper aims to build two types of staged patterns (2SGP and 3SHP) and present the ISHP approach combined with the 2SGP and 3SHP in the remaining content.


## 3. Generation Procedures for 2SGP and 3SHP

In the 2DRSSSCSP-GR,m types of rectangular items need to be cut off exactly from plates of the same size L⊗W (length ⊗ width). The type-i item can be characterized by the size li⊗wi⊗vi⊗di (length ⊗ width ⊗ value ⊗ demand). To satisfy two restrictions (guillotine cuts and rotation) in the 2DRSSSCSP-GR, the 2SGP and 3SHP are used to meet the restriction of guillotine cuts (G). 2m types of strips are considered to satisfy the restriction of the item allowed to be rotated by 90° (R). We firstly introduce generation procedures for 2SGP and 3SHP. To simplify the presentation, only X-patterns are presented in this section. The Y-patterns are easy to be achieved by swapping the length and width of the used plates.The notations are used to denote the following related parameters:K: number of types of item allowed to be rotated by 90°, that is, K=2mlk: length of type-k item, lk=li when k=1,2,…,m; lk=wi when k=m+1,m+2,…,2m, i=1,2,…,mwk: width of type-k item, wk=wi when k=1,2,…,m; wk=li when k=m+1,m+2,...,2m, i=1,2,…,mri: remaining demand of type-i itemf2SGPk,x: value of type-k strip x⊗wk for 2SGP, k=1,2,…,mn2SGPk,x,i: number of type-i item in type-k strip x⊗wk for 2SGP, i=1,2,…,mF2SGPy: value of segmentL⊗y for 2SGP, y=1,2,…,WV2SGPk: total value of possible items in type-k strip L⊗wk for 2SGPN2SGPy,i: number of type-i item in segment L⊗y for 2SGP, y=1,2,…,WF3SHPx,y: value of segmentx⊗y for 3SHPV3SHPk,x: total value of possible existing items in type-k strip x⊗wk for 3SHPn3SHPk,x,i: number of only including type-i item in type-k strip x⊗wk for 3SHP, i=1,2,…,mN3SHPx,y,i: number of type-i item in segment x⊗y for 3SHPT3SHPx: value of 3SHP including segment x⊗W and segment L−x⊗W at the dividing position x


### 3.1. Generation Procedure for 2SGP

The generation procedure for 2SGP always includes generation of general strips and generation of 2SGP. The generation of general strips provides the candidate strips for 2SGP. Assume that all items are ordered by their width, that is,w1≤w2≤…≤w2m. 2m types of general strips can be generated for 2SGP in the plate L⊗W, where the type-k strip has the size L⊗wk, k=1,2,…,2m. The number of each item in type-k strip L⊗wk is determined by solving the following recursion:(1)f2SGPk,x=maxf2SGPk−1,x,vi+f2SGPk,x−lk|lk≤x,f2SGPk,x=∑i=1mvin2SGPk,x,i,n2SGPk,x,i≤ri.The recursion is initialized withf2SGP0,x=0 and n2SGP0,x,i=0. The value of type-k strip x⊗wk (x=1,2,…,L) can be selected from the maximum value between the value of strip x⊗wk−1 and the other one, which is the total value of one type-i item and strip x−lk⊗wk. Meanwhile, the number of each item in type-k strip L⊗wk can be determined by n2SGPk,x,i.All general strips can be determined by the decision variablen2SGPk,x,i, which is considered by k=1,2,…,2m, x=1,2,…,L,i=1,2,…,m. Therefore, the complexity of recursion (1) is O2m2L.The general strips have been generated through a horizontal combination of demanded items with the above recursion. The 2DGP for the plateL⊗W can be achieved through a vertical combination of generated strips with the following recursion:(2)F2SGPy=maxF2SGPy−1,V2SGPk+F2SGPy−wk|wk≤y,V2SGPk=∑i=1mviminn2SGPk,L,i,ri−N2SGPy−wk,i.This recursion is initialized withF2SGP0=0 and N2SGP0,i=0. The value of segment L⊗y(y=1,2,…,W) can be chosen from the maximum value between the value of segment L⊗y−1 and the other value, which is the total value of strip L⊗wk and segment L⊗y−wi. Considering the remaining demand of each item, the value of type-k strip L⊗wk can be computed by the sum of the price of each item multiplying the possible existing number of each item, which is determined with the minimum between the number of strip L⊗wk and the remaining number of each item excluding used for segment L⊗y−wi.The 2DGP can be achieved with the maximum valueF2SGPy, which is considered by y=1,2,…,W. Meanwhile, the total value of type-k strip V2SGPk is determined by n2SGPk,L,i, which is considered by k=1,2,…,2m, i=1,2,…,m. Therefore, the complexity of recursion (2) is O2m2W. Subsequently, the complexity of the generation procedure for 2SGP is O2m2L+W.


### 3.2. Generation Procedure for 3SHP

The generation procedure for 3SHP always includes the generation of homogenous strips, homogenous segments, and 3SHP. The generation of homogenous strips provides the candidate strips for homogenous segments. The homogenous segments are the basic element for 3SHP. Similar to the generation procedure for 2SGP, the homogenous strips are constructed along the length direction of the used plateL⊗W. Considering item rotation, 2m type of homogenous strips x⊗wk , including single item, are determined as follows:(3)n3SHPk,x,i=minxli,ri,k=1,2,…,m,n3SHPk,x,i=minxwi,ri,k=m+1,m+2,…,2m.The homogenous segments can be obtained with a vertical combination of generated homogenous strips. The combination of homogenous strips for the segmentx⊗W can be determined by solving the following recursion:(4)F3SHPx,y=maxF3SHPx,y−1,V3SHPk,x+F3SHPx,y−wk|wk≤y,V3SHPk,x=viminn3SHPk,x,i,ri−N3SHPx,y−wk,i.Recursion (4) is initialized with F3SHPx,0=0 and N3SHPx,0,i=0. The value of segment x⊗y can be computed with the maximum value between the value of segment x⊗y−1 and the other value, which is the total value of homogenous strip x⊗wk and segment x⊗y−wi. The value of homogenous strip x⊗wk is the total value of including type-i items, which are selected from minimum between the number of homogenous strip x⊗wk, and the remaining number of type-i item for the used segment x⊗y−wi.The generation of homogenous strips can be built with formula (3). Based on all generated homogenous strips, the homogenous segments can be generated by solving recursion (4). The decision variable is N3SHPx,y,i for x=1,2,…,L, y=1,2,…,W, i=1,2,…,m. The complexity of recursion (2) is OmLW.The 3SHP can be obtained with a horizontal combination of at least two segments. Although 3SHP including more segments can improve material utilization, the cutting complexity is also increased. We present the simplest 3SHP, including two segments, which can be extended to 3SHP, including more segments. The value of 3SHP is the total value of segmentx⊗W and segment L−x⊗W, shown in formula (5). The dividing position of plate L⊗W can be determined by selecting the maximum value of T3SHPx:(5)T3SHPx=maxF3SHPx,W+F3SHPL−x,W,L⊗wk.The formula is used to find the maximum value ofT3SHPx, L⊗wk. The complexity of formula (5) is OL. Considering that L≪mLW, subsequently, the complexity of the generation procedure for 3SHP is OmLW.


### 3.3. Normal Sizes for 2SGP and 3SHP

The staged patterns with recursive techniques commonly consider the normal sizes, which are the possible combination sizes of all demanded items. The variable is increased by one unit using general recursive techniques at each time, whereas only the positions of normal sizes are considered to generate staged patterns. Hence, considering normal sizes can reduce the computation time and cannot affect the solution quality. The normal sizes of strips, segments, and patterns for T-shape homogenous patterns are defined in Cui [26].Four sets of normal sizes are shown in formula (6). For the generation procedure for 2SGP, the normal sizes from set X1 can be considered to generate strips x⊗wk when recursion (1) is solved. The normal sizes from set Y1 can be considered to generate patterns L⊗y when recursion (2) is solved. For the generation procedure for 3SHP, the normal sizes from set X2 can be considered to generate strips x⊗wk when recursion (3) is solved. The normal patterns from set Y2 can be considered to generate segments x⊗y when recursion (4) is solved. The normal patterns from set X2 can be considered to generate segments x⊗W when formula (5) is solved:(6)X1=x|x=∑k=12meklk≤L,ek∈0,1,…,Llk,Y1=y|y=∑k=12mekwk≤|W,ek∈0,…,Wwk,X2=x|x=eklk,ek∈0,1,…,Llk,Y2=y|y=ekwk,ek∈0,1,…,Wwk.


### 3.4. Correction Value for Each Item

The recursive techniques are used repeatedly during the generation procedure for 2SGP and 3SHP. The solution may include good patterns in the early recursive stage and bad patterns in the later recursive stage because of the greedy nature. To avoid trapping into local optimization, the correction value is formula (7), where the new value of each item can be changed according to those items in the current pattern. Let ni be the number of type-i item in the current pattern and u the material utilization of the current pattern:(7)vi=g1vi+g2liwiu,i=1,2,…,m,g1=1−g2,g2=αnidi+ri,u=Σi=1mniliwiLW.The new value of each item is determined with a weighted combination of the existing valuevi and the other part liwiβ/u, which is called overproportional material consumption norm in [27]. Two weighted parameters g1 and g2 are computed by each computational formula. Parameter α is selected from interval 0.6,0.9. Parameter β is slightly bigger than 1 in [16]. The value of the items nonexistent in the current pattern will not be changed because g2=0 and g1=1 when ni=0.For overproportional material consumption normliwiβ/u, the numerator liwiβ denotes that the value of the item is overproportional to its area. These items with a large area have a big new value. The denominator u shows that the value of these items constructing the current pattern with bad material utilization has a big change. These items with hard combination possess a big new value. Therefore, the correction value for the item in the current pattern is aimed to select those items with large area and hard combination. They are applied to generate patterns in the early recursive stage. This approach can reduce the greedy nature of recursive techniques and improve solution quality.


## 3.1. Generation Procedure for 2SGP

The generation procedure for 2SGP always includes generation of general strips and generation of 2SGP. The generation of general strips provides the candidate strips for 2SGP. Assume that all items are ordered by their width, that is,w1≤w2≤…≤w2m. 2m types of general strips can be generated for 2SGP in the plate L⊗W, where the type-k strip has the size L⊗wk, k=1,2,…,2m. The number of each item in type-k strip L⊗wk is determined by solving the following recursion:(1)f2SGPk,x=maxf2SGPk−1,x,vi+f2SGPk,x−lk|lk≤x,f2SGPk,x=∑i=1mvin2SGPk,x,i,n2SGPk,x,i≤ri.The recursion is initialized withf2SGP0,x=0 and n2SGP0,x,i=0. The value of type-k strip x⊗wk (x=1,2,…,L) can be selected from the maximum value between the value of strip x⊗wk−1 and the other one, which is the total value of one type-i item and strip x−lk⊗wk. Meanwhile, the number of each item in type-k strip L⊗wk can be determined by n2SGPk,x,i.All general strips can be determined by the decision variablen2SGPk,x,i, which is considered by k=1,2,…,2m, x=1,2,…,L,i=1,2,…,m. Therefore, the complexity of recursion (1) is O2m2L.The general strips have been generated through a horizontal combination of demanded items with the above recursion. The 2DGP for the plateL⊗W can be achieved through a vertical combination of generated strips with the following recursion:(2)F2SGPy=maxF2SGPy−1,V2SGPk+F2SGPy−wk|wk≤y,V2SGPk=∑i=1mviminn2SGPk,L,i,ri−N2SGPy−wk,i.This recursion is initialized withF2SGP0=0 and N2SGP0,i=0. The value of segment L⊗y(y=1,2,…,W) can be chosen from the maximum value between the value of segment L⊗y−1 and the other value, which is the total value of strip L⊗wk and segment L⊗y−wi. Considering the remaining demand of each item, the value of type-k strip L⊗wk can be computed by the sum of the price of each item multiplying the possible existing number of each item, which is determined with the minimum between the number of strip L⊗wk and the remaining number of each item excluding used for segment L⊗y−wi.The 2DGP can be achieved with the maximum valueF2SGPy, which is considered by y=1,2,…,W. Meanwhile, the total value of type-k strip V2SGPk is determined by n2SGPk,L,i, which is considered by k=1,2,…,2m, i=1,2,…,m. Therefore, the complexity of recursion (2) is O2m2W. Subsequently, the complexity of the generation procedure for 2SGP is O2m2L+W.


## 3.2. Generation Procedure for 3SHP

The generation procedure for 3SHP always includes the generation of homogenous strips, homogenous segments, and 3SHP. The generation of homogenous strips provides the candidate strips for homogenous segments. The homogenous segments are the basic element for 3SHP. Similar to the generation procedure for 2SGP, the homogenous strips are constructed along the length direction of the used plateL⊗W. Considering item rotation, 2m type of homogenous strips x⊗wk , including single item, are determined as follows:(3)n3SHPk,x,i=minxli,ri,k=1,2,…,m,n3SHPk,x,i=minxwi,ri,k=m+1,m+2,…,2m.The homogenous segments can be obtained with a vertical combination of generated homogenous strips. The combination of homogenous strips for the segmentx⊗W can be determined by solving the following recursion:(4)F3SHPx,y=maxF3SHPx,y−1,V3SHPk,x+F3SHPx,y−wk|wk≤y,V3SHPk,x=viminn3SHPk,x,i,ri−N3SHPx,y−wk,i.Recursion (4) is initialized with F3SHPx,0=0 and N3SHPx,0,i=0. The value of segment x⊗y can be computed with the maximum value between the value of segment x⊗y−1 and the other value, which is the total value of homogenous strip x⊗wk and segment x⊗y−wi. The value of homogenous strip x⊗wk is the total value of including type-i items, which are selected from minimum between the number of homogenous strip x⊗wk, and the remaining number of type-i item for the used segment x⊗y−wi.The generation of homogenous strips can be built with formula (3). Based on all generated homogenous strips, the homogenous segments can be generated by solving recursion (4). The decision variable is N3SHPx,y,i for x=1,2,…,L, y=1,2,…,W, i=1,2,…,m. The complexity of recursion (2) is OmLW.The 3SHP can be obtained with a horizontal combination of at least two segments. Although 3SHP including more segments can improve material utilization, the cutting complexity is also increased. We present the simplest 3SHP, including two segments, which can be extended to 3SHP, including more segments. The value of 3SHP is the total value of segmentx⊗W and segment L−x⊗W, shown in formula (5). The dividing position of plate L⊗W can be determined by selecting the maximum value of T3SHPx:(5)T3SHPx=maxF3SHPx,W+F3SHPL−x,W,L⊗wk.The formula is used to find the maximum value ofT3SHPx, L⊗wk. The complexity of formula (5) is OL. Considering that L≪mLW, subsequently, the complexity of the generation procedure for 3SHP is OmLW.


## 3.3. Normal Sizes for 2SGP and 3SHP

The staged patterns with recursive techniques commonly consider the normal sizes, which are the possible combination sizes of all demanded items. The variable is increased by one unit using general recursive techniques at each time, whereas only the positions of normal sizes are considered to generate staged patterns. Hence, considering normal sizes can reduce the computation time and cannot affect the solution quality. The normal sizes of strips, segments, and patterns for T-shape homogenous patterns are defined in Cui [26].Four sets of normal sizes are shown in formula (6). For the generation procedure for 2SGP, the normal sizes from set X1 can be considered to generate strips x⊗wk when recursion (1) is solved. The normal sizes from set Y1 can be considered to generate patterns L⊗y when recursion (2) is solved. For the generation procedure for 3SHP, the normal sizes from set X2 can be considered to generate strips x⊗wk when recursion (3) is solved. The normal patterns from set Y2 can be considered to generate segments x⊗y when recursion (4) is solved. The normal patterns from set X2 can be considered to generate segments x⊗W when formula (5) is solved:(6)X1=x|x=∑k=12meklk≤L,ek∈0,1,…,Llk,Y1=y|y=∑k=12mekwk≤|W,ek∈0,…,Wwk,X2=x|x=eklk,ek∈0,1,…,Llk,Y2=y|y=ekwk,ek∈0,1,…,Wwk.


## 3.4. Correction Value for Each Item

The recursive techniques are used repeatedly during the generation procedure for 2SGP and 3SHP. The solution may include good patterns in the early recursive stage and bad patterns in the later recursive stage because of the greedy nature. To avoid trapping into local optimization, the correction value is formula (7), where the new value of each item can be changed according to those items in the current pattern. Let ni be the number of type-i item in the current pattern and u the material utilization of the current pattern:(7)vi=g1vi+g2liwiu,i=1,2,…,m,g1=1−g2,g2=αnidi+ri,u=Σi=1mniliwiLW.The new value of each item is determined with a weighted combination of the existing valuevi and the other part liwiβ/u, which is called overproportional material consumption norm in [27]. Two weighted parameters g1 and g2 are computed by each computational formula. Parameter α is selected from interval 0.6,0.9. Parameter β is slightly bigger than 1 in [16]. The value of the items nonexistent in the current pattern will not be changed because g2=0 and g1=1 when ni=0.For overproportional material consumption normliwiβ/u, the numerator liwiβ denotes that the value of the item is overproportional to its area. These items with a large area have a big new value. The denominator u shows that the value of these items constructing the current pattern with bad material utilization has a big change. These items with hard combination possess a big new value. Therefore, the correction value for the item in the current pattern is aimed to select those items with large area and hard combination. They are applied to generate patterns in the early recursive stage. This approach can reduce the greedy nature of recursive techniques and improve solution quality.


## 4. An ISHP Approach

The proposed ISHP approach tries to achieve a cutting plan with the minimum number of plates for solving the 2DRSSSCSP-GR. The flowchart of the ISHP approach is shown in Figure5. Based on data information of the 2DRSSSCSP-GR, A 2SGP and a 3SHP are constructed with the generation procedure for 2SGP (Section 3.1) and generation procedure for 3SHP (Section 3.2) based on normal sizes for 2SGP and 3SHP (Section 3.3), respectively. The pattern with a larger value is selected as the candidate pattern. The frequency of the candidate pattern is determined according to the residual demand of each item. The information of the candidate pattern and its frequency is recorded. The residual demand of each item is updated based on the information of the candidate pattern. A new cutting plan is generated when the demand for each item is zero. Otherwise, the value of each item is corrected based on the current candidate pattern with a correction value for each item (Section 3.4). The newly generated cutting plan is used to replace the previous cutting plan when the newly generated cutting plan with the number of used plates is less than those in the previous cutting plan. Otherwise, the newly generated cutting plan is discarded. Another newly generated cutting plan is constructed repeatedly when the number of iterations is not reached. Otherwise, a cutting plan with a minimum number of used plates is achieved for solving the current 2DRSSSCSP-GR.Figure 5
Flowchart of the ISHP approach.The following notations are used to conveniently describe the procedure of the ISHP approach.G: number of iterations, G=1,2,…,GmaxGmax: maximum number of iterationsNpl_best: number of used plates for the best cutting planNpl_cur: number of used plates for the current cutting planP: set of patternspj: type-j patternF: set of frequency of patternsfj: frequency of type-j patternThe procedure of the ISHP approach mainly includes the following steps:Step 1: initialize the relevant parameters:G=1, Npl_best=+∞, and vi=liwi, i=1,2,…,m.Step 2: generate a cutting plan with a combination of 2SGP and 3SHP.Step 2.1: letP=, F=, and ri=di, i=1,2,…,mStep 2.2: for the remaining demandri of type-i item, use generation procedure for 2SHP and 3SHP to generate 2SHP and 3SHP based on normal sizesStep 2.3: select one with a large value from 2SHP and 3SHP in Step 2.2, and take it as the candidate patternpjStep 2.4: compute the frequency of the current candidate patternpj by the formulafj=min⌊ri/ni⌋,i=1,2,…,m. Put pj and fj into P and F, respectivelyStep 2.5: update the remaining demand by the formulari=ri−fjni,i=1,2,…,mStep 2.6: if∑i=1mri>0, correct value of each item vi, i=1,2,…,m. j=j+1 and go to Step 2.2; otherwise, record the number of used plate Npl_cur for the current cutting plan, and go to Step 3Step 3: ifNpl_cur<Npl_best, record the current cutting plan as the best cutting plan. Otherwise, ignore this current cutting plan. The number of iterations increased by one; that is, G=G+1.Step 4: ifG>Gmax, achieve the best cutting plan for the 2DRSSSCSP-GR. Otherwise, go to Step 2.The whole steps run throughG main iterations, each of which is the SHP in Step 2. Step 1 is used to initialize iterations, the number of used plates, and pattern types for the best cutting plan. The 2SGP and 3SHP are generated for constructing a cutting plan until all items demand is fulfilled in Step 2. Step 2 includes generating a 2SGP and a 3SHP, selecting the current candidate pattern, updating the items demand, and correcting the value for each item. Step 3 compares the number of used plates of the current cutting plan and the previous cutting plan. The iterations are run Gmax times and achieve the best cutting plan with the minimum number of used plates for solving the 2DRSSSCSP-GR.AS a new cutting plan can be generated by each iteration, and the ISHP approach is used to generateGmax cutting plans. Meanwhile, the number of patterns in a cutting plan can be estimated by H=∑i=1mliwidi/LW. The complexity of generation for 2SHP and 3SHP is O2m2L+W+OmLW=O2m2L+W+mLW according to Sections 3.1 and 3.2. Therefore, the complexity of the proposed ISHP approach is O2m2L+W+mLWHGmax.


## 5. Computational Results

This section is presented in two parts. The relevant parameters are set in the first part. The proposed ISHP approach is compared with one published algorithm with 2SGP in [16] and one published algorithm with 3SHP in [19] in the second part. Three types of heuristic algorithms are used to deal with two sets A and B, which are obtained from Silva et al. [12]. The ISHP runs on an Acer laptop with 2.30Gz Inter Core i5 and 8 GB RAM.


### 5.1. Parameter Setting

The solution quality and computational time are determined by main parametersα, β, and Gmax. Three parameters are considered with α∈0.6,0.9, β∈1.00,1.08, and Gmax∈1,100. The ISHP is applied to solve instances from set A. The computational results are shown in Table 1, where Ntot denotes the total used plates for all instances and t represents the average time in seconds for each instance.Table 1
Computational results of different parameter setting.
ConstantsVariablesNtottβ=1.02,Gmax=100α=0.62520.7α=0.72510.7α=0.82510.8α=0.92520.7α=0.7,Gmax=100β=1.002520.6β=1.022510.7β=1.042520.7β=1.062520.8α=0.7,β=1.02Gmax=12640.1Gmax=102580.1Gmax=302540.2Gmax=502510.3Gmax=802510.5Gmax=1002510.7It can be seen from the computational results of Table1 that (1) the two parameters α and β with the given intervals have little effect on the solution quality and computation time; (2) the solution quality tends to be stable when the maximum iterations Gmax is larger than 50; and (3) the computation time is very short for all instances from set B. Hence, we set the value of three parameters: α=0.7, β=1.02, and Gmax=100.


### 5.2. Comparing the ISHP with Two Published Algorithms

The published algorithm in [16] applied the repeated constrained CG (RCCG) to solve the 2DRSSSCSP-GR with 2SGP. The other published algorithm in [19] used sequential value correction heuristic (SVCH) to solve the 2DRSSSCSP-GR with 3SHP. The lower bound NLB of solution for each instance is copied from [19]. Notations NISHP, NRCCG, and NSVCH are the number of used plates using the ISHP, RCCG, and SVCH for solving two sets A and B, respectively. Notation Δ represents that the solution is equal to the lower bound for each instance.Three algorithms are applied to solve setA of 30 small-scale instances. The computational results for set A are displayed in Table 2. RCCG and SVCH solve 19 and 26 instances to their lower bounds, respectively. But the ISHP solves 28 instances to their lower bounds. Only the instances (CU2 and CW1) need one more plate. As one more plate is used for a staged pattern, three guillotine cuts are added for cutting complexity. Therefore, the comparison results indicate that the proposed ISHP can achieve a better solution (higher material utilization and less cutting complexity) than the other two published algorithms for solving small-scale instances.Table 2
Computational results for setA.
InstancesNLBNISHPNRCCGNSVCHA123ΔΔΔA212Δ13ΔA38ΔΔΔA45ΔΔΔA54Δ5ΔCHL16Δ7ΔCHL23ΔΔΔCHL53Δ44CHL65Δ66CHL76ΔΔΔCU112ΔΔΔCU214151515CW19101010CW212Δ13ΔCW316ΔΔΔHchl26ΔΔΔHchl3s3ΔΔΔHchl4s2Δ3ΔHchl6s5ΔΔΔHchl7s7ΔΔΔHchl8s2ΔΔΔHchl9s10ΔΔΔHH2ΔΔΔOF14ΔΔΔOF24Δ5ΔSTS212ΔΔΔSTS45ΔΔΔW24ΔΔΔ22ΔΔΔ323Δ24ΔMeanwhile, three algorithms are also used to solve the setB of 20 medium-scale instances. The computational results for set B are shown in Table 3. In the same comparison way, RCCG and SVCH solve 11 and 16 instances to their lower bounds, respectively. However, ISHP solves 18 instances to their lower bounds. Only the instances (APT39, APT47) need one more plate. In case of instance APT30, the ISHP can reach the lower bound. But the other two published algorithms cannot reach the lower bound. The data information of instance APT30 is generated in Table 4. The cutting plan figure for instance APT30 is shown in Figure 6. The comparison results also indicate that the proposed ISHP can achieve a better solution (higher material utilization and less cutting complexity) than the other two published algorithms for solving medium-scale instances.Table 3
Computational results for setB.
InstancesNLBNISHPNRCCGNSVCHAPT308Δ99APT3114ΔΔΔAPT3212Δ13ΔAPT3312Δ13ΔAPT346ΔΔΔAPT358ΔΔΔAPT368ΔΔΔAPT3711Δ12ΔAPT3810Δ11ΔAPT3911121212APT4015Δ16ΔAPT4112ΔΔΔAPT4215ΔΔΔAPT4312Δ1313APT449ΔΔΔAPT458ΔΔΔAPT4611ΔΔΔAPT4712131313APT488ΔΔΔAPT495ΔΔΔTable 4
Detailed data information of all demand items.
IDliwidi127344623027537723543042155216375667386712413581892649318246103203641186356123223651331817514189334152693241681125171691061830526619266456203191852122329522481562328436524311164252302642625534427251425281604542922328530901153123912532471663312440634511663567394362761543723544638136205Figure 6
A cutting plan figure for instance APT30 solved by the ISHP approach.The data information of instance APT30 is obtained as follows.The used plates have the same size927⊗152. The number of items types is 38, and the total number of all items is 192. The size and demand of each item are randomly selected from li∈57,371, wi∈7,47, and di∈4,6. The detailed data information of all demand items is shown in Table 4.The cutting plan figure for instance APT30 solved by the ISHP approach is shown in Figure6, where the number indexes from 1 to 38 in the filled blue box represents “ID” of each item in Table 4. The filled slash box represents useable leftovers.


### 5.3. Influence of Combining 2SGP and 3SHP

This section analyses the influence of combining 2SGP and 3SHP for the optimization objectives, including material utilization and cutting complexity. For generating a staged pattern, 2SGP and 3SHP are used in our proposed ISHP approach, simultaneously. The only 2SGP is applied by the RCCG presented in [16]. Only 3SHP is applied by the SVCH in [19]. Three methods are all used to solve all instances in set A and set B. The computational results of the three approaches are shown in Table 5.Table 5
Computational results of three approaches.
IDUISHP%URCCG%USVCH%NISHPNRCCGNSVCHSet A92.7989.5892.07535553Set B93.3389.6692.28143150145In Table5, let U and N denote the average material utilization and the average number of cuts, respectively. It is noted that the average number of cuts is upper rounding. For example, Notations UISHP% and NISHP represent the average material utilization and the average number of cuts for all instances in set A solved by the ISHP approach. Other parameters are the corresponding meaning.From a material utilization perspective, our proposed ISHP approach can get higher average material utilization than the RCCG and SVCH approaches for solving instances in both set A and set B. This verifies that our proposed ISHP approach is more effective in improving material utilization.From a cutting complexity perspective, our proposed ISHP approach can obtain the same average number of cuts as the SVCH approach, less than the RCCG approach for solving instances in set A. Or proposed ISHP approach can achieve less than the RCCG and SVCH approaches for solving instances in set B. This indicates that our proposed ISHP approach also can reduce cutting complexity without affecting material utilization.Therefore, our proposed ISHP approach considering the combination of 2SGP and 3SHP can get better solution quality than two other published approaches considering only 2SGP or 3SHP.


## 5.1. Parameter Setting

The solution quality and computational time are determined by main parametersα, β, and Gmax. Three parameters are considered with α∈0.6,0.9, β∈1.00,1.08, and Gmax∈1,100. The ISHP is applied to solve instances from set A. The computational results are shown in Table 1, where Ntot denotes the total used plates for all instances and t represents the average time in seconds for each instance.Table 1
Computational results of different parameter setting.
ConstantsVariablesNtottβ=1.02,Gmax=100α=0.62520.7α=0.72510.7α=0.82510.8α=0.92520.7α=0.7,Gmax=100β=1.002520.6β=1.022510.7β=1.042520.7β=1.062520.8α=0.7,β=1.02Gmax=12640.1Gmax=102580.1Gmax=302540.2Gmax=502510.3Gmax=802510.5Gmax=1002510.7It can be seen from the computational results of Table1 that (1) the two parameters α and β with the given intervals have little effect on the solution quality and computation time; (2) the solution quality tends to be stable when the maximum iterations Gmax is larger than 50; and (3) the computation time is very short for all instances from set B. Hence, we set the value of three parameters: α=0.7, β=1.02, and Gmax=100.


## 5.2. Comparing the ISHP with Two Published Algorithms

The published algorithm in [16] applied the repeated constrained CG (RCCG) to solve the 2DRSSSCSP-GR with 2SGP. The other published algorithm in [19] used sequential value correction heuristic (SVCH) to solve the 2DRSSSCSP-GR with 3SHP. The lower bound NLB of solution for each instance is copied from [19]. Notations NISHP, NRCCG, and NSVCH are the number of used plates using the ISHP, RCCG, and SVCH for solving two sets A and B, respectively. Notation Δ represents that the solution is equal to the lower bound for each instance.Three algorithms are applied to solve setA of 30 small-scale instances. The computational results for set A are displayed in Table 2. RCCG and SVCH solve 19 and 26 instances to their lower bounds, respectively. But the ISHP solves 28 instances to their lower bounds. Only the instances (CU2 and CW1) need one more plate. As one more plate is used for a staged pattern, three guillotine cuts are added for cutting complexity. Therefore, the comparison results indicate that the proposed ISHP can achieve a better solution (higher material utilization and less cutting complexity) than the other two published algorithms for solving small-scale instances.Table 2
Computational results for setA.
InstancesNLBNISHPNRCCGNSVCHA123ΔΔΔA212Δ13ΔA38ΔΔΔA45ΔΔΔA54Δ5ΔCHL16Δ7ΔCHL23ΔΔΔCHL53Δ44CHL65Δ66CHL76ΔΔΔCU112ΔΔΔCU214151515CW19101010CW212Δ13ΔCW316ΔΔΔHchl26ΔΔΔHchl3s3ΔΔΔHchl4s2Δ3ΔHchl6s5ΔΔΔHchl7s7ΔΔΔHchl8s2ΔΔΔHchl9s10ΔΔΔHH2ΔΔΔOF14ΔΔΔOF24Δ5ΔSTS212ΔΔΔSTS45ΔΔΔW24ΔΔΔ22ΔΔΔ323Δ24ΔMeanwhile, three algorithms are also used to solve the setB of 20 medium-scale instances. The computational results for set B are shown in Table 3. In the same comparison way, RCCG and SVCH solve 11 and 16 instances to their lower bounds, respectively. However, ISHP solves 18 instances to their lower bounds. Only the instances (APT39, APT47) need one more plate. In case of instance APT30, the ISHP can reach the lower bound. But the other two published algorithms cannot reach the lower bound. The data information of instance APT30 is generated in Table 4. The cutting plan figure for instance APT30 is shown in Figure 6. The comparison results also indicate that the proposed ISHP can achieve a better solution (higher material utilization and less cutting complexity) than the other two published algorithms for solving medium-scale instances.Table 3
Computational results for setB.
InstancesNLBNISHPNRCCGNSVCHAPT308Δ99APT3114ΔΔΔAPT3212Δ13ΔAPT3312Δ13ΔAPT346ΔΔΔAPT358ΔΔΔAPT368ΔΔΔAPT3711Δ12ΔAPT3810Δ11ΔAPT3911121212APT4015Δ16ΔAPT4112ΔΔΔAPT4215ΔΔΔAPT4312Δ1313APT449ΔΔΔAPT458ΔΔΔAPT4611ΔΔΔAPT4712131313APT488ΔΔΔAPT495ΔΔΔTable 4
Detailed data information of all demand items.
IDliwidi127344623027537723543042155216375667386712413581892649318246103203641186356123223651331817514189334152693241681125171691061830526619266456203191852122329522481562328436524311164252302642625534427251425281604542922328530901153123912532471663312440634511663567394362761543723544638136205Figure 6
A cutting plan figure for instance APT30 solved by the ISHP approach.The data information of instance APT30 is obtained as follows.The used plates have the same size927⊗152. The number of items types is 38, and the total number of all items is 192. The size and demand of each item are randomly selected from li∈57,371, wi∈7,47, and di∈4,6. The detailed data information of all demand items is shown in Table 4.The cutting plan figure for instance APT30 solved by the ISHP approach is shown in Figure6, where the number indexes from 1 to 38 in the filled blue box represents “ID” of each item in Table 4. The filled slash box represents useable leftovers.


## 5.3. Influence of Combining 2SGP and 3SHP

This section analyses the influence of combining 2SGP and 3SHP for the optimization objectives, including material utilization and cutting complexity. For generating a staged pattern, 2SGP and 3SHP are used in our proposed ISHP approach, simultaneously. The only 2SGP is applied by the RCCG presented in [16]. Only 3SHP is applied by the SVCH in [19]. Three methods are all used to solve all instances in set A and set B. The computational results of the three approaches are shown in Table 5.Table 5
Computational results of three approaches.
IDUISHP%URCCG%USVCH%NISHPNRCCGNSVCHSet A92.7989.5892.07535553Set B93.3389.6692.28143150145In Table5, let U and N denote the average material utilization and the average number of cuts, respectively. It is noted that the average number of cuts is upper rounding. For example, Notations UISHP% and NISHP represent the average material utilization and the average number of cuts for all instances in set A solved by the ISHP approach. Other parameters are the corresponding meaning.From a material utilization perspective, our proposed ISHP approach can get higher average material utilization than the RCCG and SVCH approaches for solving instances in both set A and set B. This verifies that our proposed ISHP approach is more effective in improving material utilization.From a cutting complexity perspective, our proposed ISHP approach can obtain the same average number of cuts as the SVCH approach, less than the RCCG approach for solving instances in set A. Or proposed ISHP approach can achieve less than the RCCG and SVCH approaches for solving instances in set B. This indicates that our proposed ISHP approach also can reduce cutting complexity without affecting material utilization.Therefore, our proposed ISHP approach considering the combination of 2SGP and 3SHP can get better solution quality than two other published approaches considering only 2SGP or 3SHP.


## 6. Conclusions

The ISHP approach in this paper is proposed to solve the 2DRSSSCSP-GR with the combination of 2SGP and 3SHP. The 2SGP and 3SHP are as candidate staged patterns. The SHP algorithm is used to select a candidate staged pattern with a larger value. A new cutting plan is generated until all items demand is fulfilled accurately. The ISHP approach tries to generate many cutting plans by the iterative algorithm. The cutting plan with the minimum number of used plates is selected as the best cutting plan for the current 2DRSSSCSP-GR. The computational results also indicate that the ISHP approach is more effective in material utilization and cutting complexity than the published algorithms with staged patterns.The common staged patterns are welcomed in the cutting process of the manufacturing industry, such as the production of steel products, paper, wood, glass, and other industries. 2SGP and 3SHP can be easily obtained with recursive techniques. The ISHP with the combination of 2SGP and 3SHP can get the most instances to their lower bounds, which verifies that combining 2SGP and 3SHP can balance material utilization and cutting complexity while solving the 2DRSSSCSP-GR.The ISHP in this paper considers the 2DRSSSCSP-GR with two contradictory objectives of material utilization and cutting complexity. Future research may consider other factors, such as setup cost or useable leftovers.



---

*Source: 3732720-2021-11-08.xml*