Open access peer-reviewed chapter - ONLINE FIRST

A Global Method for a Two-Dimensional Cutting Stock Problem in the Manufacturing Industry

By Yao-Huei Huang, Hao-Chun Lu, Yun-Cheng Wang, Yu-Fang Chang and Chun-Kai Gao

Submitted: May 3rd 2019Reviewed: August 27th 2019Published: January 20th 2020

DOI: 10.5772/intechopen.89376

Downloaded: 26

Abstract

A two-dimensional cutting stock problem (2DCSP) needs to cut a set of given rectangular items from standard-sized rectangular materials with the objective of minimizing the number of materials used. This problem frequently arises in different manufacturing industries such as glass, wood, paper, plastic, etc. However, the current literatures lack a deterministic method for solving the 2DCSP. However, this study proposes a global method to solve the 2DCSP. It aims to reduce the number of binary variables for the proposed model to speed up the solving time and obtain the optimal solution. Our experiments demonstrate that the proposed method is superior to current reference methods for solving the 2DCSP.

Keywords

  • two-dimensional cutting stock problem (2DCSP)
  • rectangular items
  • optimal solution
  • deterministic model

1. Introduction

Two-dimensional cutting stock problem (2DCSP) is a well-known problem in the fields of management science and operations research. The problem frequently arises in the manufacturing processes of different products such as wood, glass, paper, steel, etc. In the 2DCSP, a set of given rectangular items is cut from a set of rectangular materials with the aim of determining the minimum number of materials [1, 2]. These applications include sawing plates from wood stocks [3], reel and sheet cutting at a paper mill [4], cutting plates of thin-film-transistor liquid-crystal display (TFT-LCD) from glass substrate [5, 6], placing devices into a system-on-a-chip circuit [7], and container loading or calculation of containers [8, 9]. Minimizing the number of materials is normally the target in this type of the problem because it does not only reduce the overhead consumption but also enhances environmental protection. The problem in the literatures have been classified as one-dimensional, 1.5-dimensional, and 2DCSPs (Hinxman [10] and Lodi et al. [11]) and suggested two categories of approaches in solving the problems, namely, the heuristic and deterministic approaches (Belov [12], Burke et al. [13], Chen et al. [14], Hopper and Turton [15], Lin [16] and Martello et al. [17]).

Various heuristic approaches have been proposed and discussed in the literatures. The primary advantage of this approach is easier in solving the 2DCSP within an acceptable and economical timeframe [18, 19]. The feasible solution is obtained within a reasonable time, while the optimal solution cannot be guaranteed. Chazelle [20] first proposed a popular heuristic algorithm, called the bottom-left heuristic algorithm. Berkey and Wang [21] proposed a finite best strip heuristic algorithm to improve the original bottom-left method which packs the items directly into the bins with a best-fit policy. On the other hand, Lodi et al. [22] proposed an integrated heuristic approach that initiates the solution by paralleling the edges of the items and bins (i.e., materials) and utilizes a Tabu search [23, 24] to explore the neighborhood and refine the possible solution. In order to enhance the effectiveness of the algorithm used, Boschetti and Mingozzi [25, 26] consider empty bins in turn and fill the bins with items in a sequence defined by the prices attributed to the items and update them iteratively. Likewise, Monaci and Toth [27] initially used Lagrangian-based heuristic to generate a set of covering programming model to obtain a lower bound solution, in which the items cannot be rotated. They applied geometric analytical techniques and Dantzig-Wolfe decomposition to produce various lower bounds of the 2DCSP so that a better solution can be compared and obtained [28, 29, 30, 31].

Despite the development of heuristic approaches can obtain possible solution in a reasonable time, however there is a scarcity of literature attempting to ensure the achievement of an optimal solution. Moreover, the distance between one random feasible solution and the actual global optimal solution can be enlarged with an increasing problem size. Only a few studies attempted to develop deterministic approaches for an optimal solution. For example, Chen et al. [32] formed a mathematical model for packing a set of given rectangular items into a rectangular space in which the dimension of the rectangular space is minimized. The packing problem is equal to the cutting problem, and the problem can also be called as an assortment problem. Moreover, Williams [33] formulated a mathematical model considering the increased generalization of 2DCSP, to solve the problem with various sizes of bins. However, Williams’ model contains an excessive number of binary variables as indicated by Pisinger and Sigurd [31] who showed that Williams’ model has difficulty in solving a standard 2DCSP by their computational experiments. The subsequent studies by Li and Chang [34], Li et al. [35, 36], Hu et al. [37], and Tsai et al. [38] (these approaches are called Li’s approach in this study) enhanced Chen’s model with reformulation techniques based on reducing binary variables and piecewise linearization technique. The deterministic approaches can guarantee the achievement of global optimization with an acceptable tolerance; however, these approaches are only suitable for the assortment problem (i.e., cutting rectangular items from one material only), while many manufacturing situations require considering minimal number of materials.

Aiming to close the knowledge gap, this study modifies the two programs of the assortment problem proposed by Chen et al. [32] and Li and Chang [34] to be two corresponding deterministic models for the 2DCSP. As an innovative approach, a global approach of the 2DCSP with a logarithmic number of binary variables and extra constraints is proposed and demonstrated.

The remainder of this study is organized as follows: Section 2 discusses the 2DCSP formulations. Section 3 proposes the 2DCSP models with logarithmic number of binary variables and extra constraints. Numerical examples are given in Section 4 to demonstrate the theoretical advances and advantages of the proposed global approach. Section 5 gives the concluding remarks.

2. Problem formulations

Given nsmall rectangular items, the 2DCSP is to cut all items within large rectangular materials with the objective of minimizing the number of materials used. Denote xand yas the width and the length of the enveloping rectangle. By referring to the method of Chen et al. [32], a mathematical program can be formed with the objective of minimizing the volume (i.e., Min xy) as discussed in Section 2.1. In the 2DCSP, the minimal number of materials can reduce the manufacturing costs. Thus Section 2.2 explains how to reformulate two new 2DCSP programs based on the original model in Section 2.1. Firstly, the terminologies, including decision variables and parameters, are introduced in Tables 1 and 2.

2.1 Cutting problem in one material

The cutting problem considering one material is also called the assortment problem, which considers cutting a set of given rectangular items within a rectangular material of minimum area. Avoiding the overlapping of items is the core requirements. Chen et al. [32] and Li and Chang [34] use four binary variables ai,jbi,jci,jdi,jand two binary variables ui,jvi,j, respectively, to handle the non-overlapping conditions, as shown in Table 3.

ParameterMeaning
nThe number of given rectangular items needed to be cut
mThe number of rectangular materials with the same size
piqiThe width and length of given rectangular item ifor i=1,,n
x¯y¯x¯and y¯are the upper bounds of xand y, respectively. These items also denote the width and length of a given rectangular material

Table 1.

Parameters in the 2DCSP.

VariableMeaning
xiyiThe bottom-left coordinate of rectangular item i
xyThe top-right coordinate of the rectangular material
ai,jbi,jci,jdi,jA set of binary variables expressing the non-overlapping conditions for a pair of rectangular items iand rectangular items jfor i<j, which are defined by Chen et al. [32]
ui,jvi,jA pair of binary variables expressing the non-overlapping conditions for a pair of rectangular items iand rectangular items jfor i<j, which are defined by Li and Chan [34]
siAn orientation indicator for a given rectangular item i. si=1if piis parallel to the x-axis; otherwise, si=0if piis parallel to the y-axis (siis a binary variable)
YThe accumulated length of all materials used.

Table 2.

Decision variables in the 2DCSP.

Table 3.

Four cases of non-overlapping conditions.

The following assortment program is proposed by Chen et al. [32]:

Original (a)

Minxy

s.t.xj+pjsj+qj1sjxi+x¯1ai,jfori,j=1,,nandi<j,E1
xi+pisi+qi1sixj+x¯1bi,jfori,j=1,,nandi<j,E2
yj+qjsj+pj1sjyi+y¯1ci,jfori,j=1,,nandi<j,E3
yi+qisi+pi1siyj+y¯1di,jfori,j=1,,nandi<j,E4
ai,j+bi,j+ci,j+di,j=1fori,j=1,,nandi<j,E5
xi+pisi+qi1sixx¯fori=1,,n,E6
yi+qisi+pi1siyy¯fori=1,,n,E7

where ai,j,bi,j,ci,j,di,j, and siare binary variables; xiand yiare nonnegative continuous variables; Constraints (1)(5) ensure that the rectangular items are non-overlapping, and Constraints (6) and (7) are to cut all of the rectangular items within an enveloping rectangular material x¯y¯.

Remark 1. Original (a) uses 2n2nbinary variables (ai,j,bi,j,ci,j,di,j) and 2.5nn1+2nconstraints to formulate an assortment problem with nrectangular items.

By referring to Li and Chang [34], an alternative mathematical model can be expressed as follows:

Original (b)

Min xy

s.t. (6) and (7),

xj+pjsj+qj1sjxi+x¯ui,j+vi,jfori,j=1,,nandi<j,E8
xi+pisi+qi1sixj+x¯1ui,j+vi,jfori,j=1,,nandi<j,E9
yj+qjsj+pj1sjyi+y¯1+ui,jvi,jfori,j=1,,nandi<j,E10
yi+qisi+pi1siyj+y¯2ui,jvi,jfori,j=1,,nandi<j,E11

where ui,j,vi,j, and siare binary variables; xiand yiare nonnegative continuous variables; and Constraints (8)(11) ensure that the rectangular items are non-overlapping.

Remark 2. Original (b) uses n2binary variables (ui,j, vi,j) and 2n2constraints to formulate an assortment problem with nrectangular items.

However, these two models are inappropriate for directly solving the general 2DCSP because the objective of the 2DCSP must minimize the number of materials used for cutting all items. By referring to the two models above, two corresponding 2DCSP models are proposed in Section 2.2.

2.2 General deterministic models of 2DCSP

As mentioned above, we need to find out the minimal number of materials used for cutting all items. Original (a) is then reformulated as a general deterministic model of 2DCSP, where cutting nrectangular items from mmaterials, as shown in P1 (a):

P1 (a)

MinY

s.t. (1), (2) and (5) in Original (a),

yj+qjsj+pj1sjyi+my¯1ci,jfori,j=1,,nandi<j,E12
yi+qisi+pi1siyj+my¯1di,jfori,j=1,,nandi<j,E13
xi+pisi+qi1six¯fori=1,,n,E14
yi+qisi+pi1sik=1mky¯Qi,kfori=1,,n,E15
yik=1mk1y¯Qi,kfori=1,,n,E16
k=1mQi,k=1fori=1,,n,E17
yi+qisi+pi1siYfori=1,,n,E18

where si,ai,j,bi,j,ci,j,di,j, and Qi,kare binary variables; xi,yiand Yare nonnegative continuous variables; Constraints (1), (2), (5), (12) and (13) ensure that the rectangular items are non-overlapping; Constraints (15)(17) mean that each rectangular item is fitly cut from one of the mmaterials; Constraint (18) obtains the accumulated length of materials used; and the objective function minimizes the accumulated length of materials used.

There are nmnew binary variables (i.e., Qi,kfori=1,2,,nandk=1,2,,m) in Constraints (15)(17) of P1 (a) model. It aims to cut the ithrectangular item from the kthmaterial if Qi,k=1, and Constraint (17) forces any rectangular item to be cut from one of such materials. Supposing that rectangular item iis cut from the kthmaterial, then Qi,k=1and Qi,k=0for kkand k=1,2,,m. Constraints (15)(17) will force the y-axis position of rectangular item icut from the kthmaterial as shown below:

yi+qisi+pi1siky¯,E19
k1y¯yi.E20

Remark 3. P1 (a) requires 2n2n1mbinary variables and 5n2+3n/2constraints to form a 2DCSP program.

Referring to the Original (b), another corresponding 2DCSP program can be formulated as follows:

P1 (b)

Min Y

s.t. (8), (9), (14)(18),

yj+qjsj+pj1sjyi+my¯1+ui,jvi,jfori,j=1,,nandi<j,E21
yi+qisi+pi1siyj+my¯2ui,jvi,jfori,j=1,,nandi<j,E22

where si,ui,j,vi,j, and Qi,kare binary variables and xi,yi, and Yare nonnegative continuous variables.

Remark 4. P1 (b) requires n2+nmbinary variables and 2nn+1constraints to formulate a 2DCSP program.

Although both P1 (a) and P1 (b) can obtain a minimal number of materials used, there is mainly an issue needed to be addressed. That is, an excessive number of binary variables Qi,kis used to assign rectangular item iinto one of the materials; such that the computational load becomes a serious burden as the size of the problem grows.

As indicated by Li et al. [39], reducing the number of binary variables can accelerate the solving speed. Hence, we can roughly estimate the number of materials by the following remark.

Remark 5. The number of materials can be reduced from mto fwhere fmby the following initial calculating:

fi=1nxiyix¯×y¯,E23

where if fvalue is not big enough, i.e., in solving P1(a) and P1(b) are infeasible, then we can accumulate f, i.e., f=f+1, until feasible solutions exist.

By referring to Remark 5, the number of binary variables in Constraints (15)(18) can be reduced from nmto nfwhere fm. Moreover, this study proposes a reformulation technique using logarithmic number of binary variables for the P1 (a) and P1 (b) models. The detail of technique is then discussed in Section 3.

3. Logarithmic reformulation technique of 2DCSP

After considering Remark 5, for a 2DCSP with nrectangular items and fmaterials, the P1 (a) and P1 (b) models will require nfbinary variables (Qi,k) to cut each rectangular item from one of the materials. The computational efficiency of the P1 (a) and P1 (b) models become a serious burden when an increasing size of the 2DCSP. For any rectangular item i, Constraint (17) (k=1fQi,k=1) is an SOS1 constraint [40], which is an ordered set of variables where only one variable may be one. An SOS1 constraint model with size fwill generally require fbinary variables. However, Vielma and Nemhauser [41] use SOS1 constraint with a logarithmic number of binary variables and constraints. This section utilizes the concept of Vielma and Nemhauser [41] and introduces the binary variables Qi,r(i=1,,nand r=1,,log2f) to replace the original binary variables (Qi,k) of the P1 (a) and P1 (b) models. Thus, the number of required binary variables can be reduced from nfto nlog2f. The following remarks and propositions discuss the logarithmic reformulation technique of the 2DCSP.

Remark 6. Let K=12f=2θ, θ=log2f, and kKbe the injective function for B:122θ01θ, which can be expressed as follows:

Bk=w1w2wθTandwr=1k2r1%2forr=1,,θ.E24

Proposition 1. Let K=1f, θ=log2fand kK; the original SOS1 Constraint in (25) which requires fbinary variables Qkcan be replaced by the Constraint set (26) and (27):

k=1fQk=1andQk01.E25

The Constraint set (25) and (26) only requires θbinary variables Qr, 2θadditional constraints, and fadditional continuous variables λk:

k=1fλk=1,E26
kS+rλk=Qrforr=1,,θ,E27

where

  1. Qr01.

  2. Bkis an injective function based on Remark 6 (i.e., Bk=w1w2wθTwith wr01for r=1,,θ).

  3. S+r=kKBkwherewr=1and Sr=kKBkwherewr=0.

Proof: Following Li et al. [39], Constraints (26) and (27) are used to construct the SOS1 property.

Following Proposition 1, we then have Proposition 2 that uses log2fbinary variables to determine whether rectangular item icould be exactly cut from one of the given materials.

Proposition 2. Let fbe the number of materials, y¯the length of material, and yithe y-axis position of rectangular item i. The original Constraint set (15)(17) of the P1 (a) and P1 (b) models will be re-expressed by the following linear system, which holds the rectangular item ito be cut from one of the given materials:

yi+qisi+pi1sik=1fky¯λi,kfori=1,,n,E28
yik=1fk1y¯λi,kfori=1,,n,E29
k=1fλi,k=1fori=1,,n,E30
kS+rλi,k=Qi,rfori=1,,nandr=1,,θ=log2f,E31

where S+rand Srare the same as the notations in Proposition 1 and si,Qi,r01.

Proof: According to Proposition 1, the continuous variables λi,kwith the Constraint set (30) and (31) have the characteristics of binary variables. Therefore, the Constraint set (28)(30) is equivalent to the Constraint set (15)(17).

Two types of 2DCSP models are formulated by utilizing Proposition 2 as the following P2 (a) and P2 (b), respectively:

P2 (a)

Min Y

s.t. (1), (2), (5), (12)(14), (18) and (28)(31),

where Y,xi,yi,λi,k0and ai,j,bi,j,ci,j,di,j,si,Qi,r01for i,j=1,,n, i<j, k=1,,f, and r=1,2,log2f.

Remark 7. P2 (a) requires n2n+log2f1binary variables and 5n2+10n+log2fconstraints to express a 2DCSP model.

P2 (b)

Min Y

s.t.(8), (9), (14), (18), (28)(31),

where Y,xi,yi,λi,k0and si,ui,j,vi,j,Qi,r01for i,j=1,,n, i<j, k=1,,fand r=1,,log2f.

Remark 8. P2 (b) requires nn+log2fbinary variables and n2n+2log2f+3constraints to express another 2DCSP model.

Table 4 shows a comparison of the four ways of expressing the 2DCSP, and it clearly lists the number of binary variables, auxiliary continuous variables, and constraints.

ItemsP1(a)P1(b)P2(a)P2(b)
Concept of non-overlappingChen et al. [32]Li and Chang [34]Chen et al. [32]Li and Chang [34]
Constraints for assigning rectangular items into materialsk=1fQi,k=1k=1fQi,k=1Proposition 2Proposition 2
No. of binary variables2n2n1fn2+nfn2n+θ1nn+θ
No. of continuous variables2n+12n+12n+nf+12n+nf+1
No. of constraints5n2+5n/22n2+3nn5n+10+4θn2n+2θ+3
where θ=log2f

Table 4.

Comparison of the four ways of expressing the 2DCSP.

4. Numerical examples

There are two examples modified from Tsai et al. [38]. The detail sizes of rectangular items and materials are listed in Table 5. We implement a Java program, which embedded an optimization package GUROBI (2011) as an MIP solver for solving the two examples with the four proposed models (P1 (a), P1 (b), P2 (a), P2 (b)). The experimental tests were run on a PC equipped with an Intel® Core™ 2 Duo CPU, 4GB RAM, and 32 bit Windows 7 operating system.

ProblemSize of materialQty. of itemsfSize of items (pi, qi)
1(40, 69)82(25, 20), (16, 20), (15, 20), (14, 20), (20, 18), (15, 17), (30, 16), (30, 14)
2(25, 150)122(32, 24), (26, 20), (25, 20), (24, 20), (40, 18), (35, 17), (20, 16), (18, 16), (38, 15), (50, 15), (18, 4), (25, 5)

Table 5.

Sizes of rectangular items and materials.

The two problems with the number of materials firstly estimated to be 2 (i.e., f=2) are solved by using the four models including P1(a), P1(b), P2(a), and P2(b). Table 6 shows the experiment results of two problems. Both of Figures 1 and 2 depict the visualization solutions. In solving four models, we obtain the same objective values of (83) and (293) in Problem 1 and Problem 2, respectively. The results clearly indicate that solving P2(a) and P2(b) is much more computationally efficient than that of P1(a) and P1(b). By observing the four models, we know that both P2(a) and P2(b) use proposed approach to reduce the numbers of binary variables. The results demonstrate that the adoption of a smaller number of binary variables can enhance the solving efficiency in solving 2DCSP.

ItemsP1 (a)P1 (b)P2 (a)P2 (b)
Problem 2
Y = 83
No. of 0–1 variables1368012872
No. of cont. variables17173333
No. of constraints180152404168
Iterations621,821686,982263,296293,432
Nodes176,776211,56470,154111,173
Solving time18.818.07.59.1
Problem 2
Objective = 293
No. of 0–1 variables300168288156
No. of cont. variables25254949
No. of constraints390324844348
Iterations31,166,3571,017,9221,114,911805,136
Nodes9,766,654244,444266,672229,701
Solving time856.524.534.919.4

Table 6.

Experiment results of two problems.

Figure 1.

Visualization result of Example 1.

Figure 2.

Visualization result of Example 2.

5. Conclusions

This study develops a logarithmic reformulation technique for reducing the required binary variables of the mixed integer program for two-dimensional cutting stock problem in the manufacturing industry. A reformulated logarithmic technique in the deterministic method reduces the number of binary variables to speed up the solving time. The deterministic methods are guaranteed to find a global optimal solution, but the computational complexity grows rapidly by increasing the number of variables and constraints. Future studies are suggested to enhance the computational efficiency for globally solving large-scale 2DCSP, such as column generation, cloud computing and meta-heuristic algorithms.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Yao-Huei Huang, Hao-Chun Lu, Yun-Cheng Wang, Yu-Fang Chang and Chun-Kai Gao (January 20th 2020). A Global Method for a Two-Dimensional Cutting Stock Problem in the Manufacturing Industry [Online First], IntechOpen, DOI: 10.5772/intechopen.89376. Available from:

chapter statistics

26total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us