Heuristics for the two-dimensional cutting stock problem with usable leftover

Abstract

Utilization of residue is a challenge in engineering practice, because unreasonable cutting causes excess materials wasted and increases the production cost. This work considers the residual two-dimensional cutting stock problem with usable leftover in which unused parts of cutting patterns can be used for future orders. We propose an algorithm that combines the iterative sequential value correction heuristic with the beam search heuristic, considering both the accumulation and the reusability of leftovers to reduce the material consumption. Cutting plans are constructed iteratively and the best one are chosen as the solution. Cutting patterns in the cutting plan are generated sequentially by recursive techniques, and potentially usable leftover are accumulated by beam search heuristic. Item values are corrected after each pattern to diversify cutting plans. Three sets of simulations under different number of periods, over medium and large instances from the literature, are used to demonstrate the effectiveness of the heuristics. Computational results show that the algorithm provides better solutions, which can save a considerable amount of plate in a long-term production period. The utilization of wastages can save a considerable amount of stock plate and contract the production cost of enterprises in the long-term production period.

Keywords

Cutting stock problem iterative sequential value correction beam search usable leftover residual sub-plate Cutting patterns Heuristics

1. Introduction

The heuristic is a technique used in the problem solving of the thing which is discovered by the man to optimal the approximation of the reaching intermediate of the optimal solution of the cognitive load to make the decision. The multi-dimensional cutting stock problem will help to set the items in the rectangular format for the objective of the number of materials for the manufacturing industries in the paper, wood etc. The ideal cutting design for substances with length & breadth variables can be found by solving the two-dimensional updated periodically sizing slicing supply issue (MSS2DCSP).

To maximize the fewest number of resources possible, the ideal slicing design is required. The restriction that contains the glass industry of the Dimond places which is the formulation the cutting of the different shapes to examine the stock rectangle of the transverse length. The very good property to slice the graph is the demand rectangular in shapes. The variation of the leftover will be able to cut the objects of the stock problems this will help in the CSPUL.

1.1 Literature review

The two-dimensional cutting stock problem (2DCSP) is one of the representative combinatorial optimization problems that has many applications in, such as industrial engineering, manufacturing and production process [15]. Given a set of small items and large stock plates, the 2DCSP consists of seeking a cutting plan in which small items of specific demands are completely arranged on the stock plates. The cutting plan is provided by a set of feasible cutting patterns and their frequencies, while the cutting pattern defines the layout of items on the plate.

Minimization of the plate cost is the main objective of the cutting plan of the 2DCSP, and minimizing trim loss is usually the main objective of a cutting pattern [19] In the field of optimization study, the trim loss issue (TLP) is among the trickiest issues. It attempts to satisfy the expectations of consumers so that the waste owing to trim erosion is avoided by selecting the best trimming plan of a variety of products of various heights from a supply of normal sized materials. Though trim loss reduction may save materials, the unused parts of the cutting pattern are not necessarily waste. The steps taken for the utilization of waste are incineration, waste compaction, composting besides vermicomposting. A grinding wheel is used as the milling cutter in the hard turning procedure termed as grinding. Accumulating unused fragments to larger leftovers that can be used for future orders may save a considerable amount of plates in a long-term production period. The period during which a person or investor enhances the worth of their contract or asset is known as the consolidation stage. It is the second stage of the investment decision. The layout of items on minimum plates is already a NP-hard problem, considering the reusability of leftovers increases the complexity of the problem. Within 2 hours of cooking, any remaining meal must be placed in the refrigerator or freezer. This will prevent the further dissemination of dangerous microorganisms. One could also conserve time, work, and expense by reusing the leftovers. Even this, a variety of factors can prevent us from utilising our leftovers, including uncertainty about their safety, forgetfulness, and a negative perception of leftovers.

Though the use of leftovers was first cited by Brown [5], and the first formula was presented by Gradišar et al. (1997), only the 1DCSP with usable leftover (1DCSPUL) has been well-studied recently. The integer linear programming in the wood-processing [13] where unused parts from previous process are selected to fulfil current orders [1] took both the standard objects and the retails as input, trying to minimize waste [7]. Heuristic methods used to find cutting patterns with desirable leftovers and [9] focused on minimizing the pseudo cost including bar cost and leftover profit [8]. The possibility of generating leftovers were considered, and proposed two residual heuristic to use retails. The implementation of a constructive heuristic to solve the 1DCSPUL, and got good solutions with less loss of material [14].

Literature concerned with the 2DCSP considering usable leftovers (2DCSPUL) is scarce and mainly suitable for small-scale problems. The two-dimensional cutting stock issue (2DCSP) calls for chopping all of the rectangle’s objects whilst reducing the wasted region of the utilized supplies provided a collection of rectangular objects as well as an unlimited amount of larger selection rectangle. Vanderbeck [23] offered an option for choosing the length of the used plate, and reserved the remaining sub-plate for future use [18]. [4] Multilevel mathematical programming models to deal with the non-guillotine 2DCSPUL where two leftovers are considered in a cutting pattern. Non-exact 2-staged 2DCSPUL where the cutting plans of minimum plate cost with the maximum area and minimum number of usable leftovers are chosen as the optimal solutions [3].

In this study, we deal with the special two-dimensional cutting stock problem with usable leftovers, in which both the generation and the prioritized utilization of leftovers are considered. According to the typology, this problem can be characterized as a residual cutting stock problem, as for that we call it the residual 2DCSPUL. We propose an algorithm that combines the iterative sequential value correction heuristic with the beam search heuristic to solve the residual 2DCSPUL, considering the accumulation and reusability of leftovers. Both stock plates and usable leftovers from previous periods are used as input material, but leftovers have higher priority [22].

The two-dimensional stock cutting problem leads in the well know optimization problem it has to manage the TDCSP of the complete problem in the polynomial factors of the electronic problems of the DNA molecules which makes the NP problems to solve in the stock cutting. This paper proposes that the DNA computing makes the sticker model which will make the TDCSP in the polynomial considering the formation of the main board [21]. The economic growth of the production cost may happen the formation of the major satisfactory problem in the stock cutting of the glasses. The proposed method needs to reduce the negative product cost for the companies in the reducing waste. The packing of the rectangle and the cutting will be able to find the relaxations, open problems and the exact method [20]. Recursion is a method for solving technical errors that involves writing a procedure that runs oneself again until the program yields the desired outcome.

1.2 Article contribution

Cutting patterns in the cutting plan are generated sequentially by recursive techniques.

ISVC-BS algorithm with the iterative sequential value correction heuristic with beam search heuristic is achieved.

The cutting plan of minimum used plates was used with usable leftovers effectively is obtained.

Pattern-procedure is used to obtain the cutting pattern of the stock plate.

The remainder is organized as follows. The definition of residual 2DCSPUL is described in Section 2. The method for solving the residual 2DCSPUL is described in Section 3. And computational results are reported in Section 4, followed by conclusions and future works in Section 5.

2. The residual 2DCSPUL

In this section, we introduce some of the definition of the residual 2DCSPUL, the main objective of the cutting plan and the detail of accumulation usable leftovers in cutting patterns.

Figure 1.

Residual reuse technique.

Figure 1 shows residual reuse technique plans set up in the article, and the plan shown good effects.

This is a waste reduction method is achieved by using the adequate leftovers from the process of previous cuttings, thus the problem found in the process of planning with the production of demanded items and leftovers by unknown future demands then to solve this problem a mathematical model has be used for analysing the uncertainty of demand in 2DCSPUL model. Something which lowers wastage by starting with less material is considered a waste reduction. To use both ends of a paperweight, purchasing things in quantity instead of separately packed, or utilising ceramics glasses rather than throwaway ones are all easy ways to reduce trash. Reducing it through better procedures & practises that decrease the quantity we produce is the recommended answer. The second-best option is to recuperate it by producing pet food or even other food items from it, giving excess food to people who need it, or both. Repurposing the outcomes of already training images as sources to a current design is the fundamental goal of the residual reuse method, which seeks to decrease the processing time as well as memory needs of machine learning systems.

Definition 1: the residual 2DCSPUL

On the residual 2DCSPUL, a set of items are produced by cutting a set of strongly heterogeneous large objects. In practice, these large objects are objects of standard size (stock plates bought from suppliers) or the unused parts of input materials (usable leftovers from previous cutting processes). Leftovers have different sizes, or, even if they are equal, treated as distinct types. Since things and garbage are the primary kinds of parts prepared after an operation or procedure, and since they reflect the resources that can be recycled or should be properly discarded since an event or procedure, designs of useable residues often only include things or wastes. The demand of items are given, the supply of each leftover type is 1, and the supply of the stock plates is sufficient. All the item demands must be met by cutting the available objects such that the quantity of used plates is small while the area of usable leftover is large.

Definition 2: the usable leftover

On the residual 2DCSPUL, a set of items are produced by cutting stock plates or usable leftovers. Usable leftovers are the unused parts of stock plates from previous cutting processes that are sufficiently large to be cut into at least one item. For simplicity, only the remaining sub-plates that have the same width as the stock plate are considered as potentially usable leftovers. Maintain a current stock, utilize the FIFO approach, identify as well as record things, meal planning round leftovers, become inventive with leftovers, give extra foodstuff, and other techniques can be used to streamline stock administration and enhance the utilisation of leftovers. Other residuals of the stock plate or previous leftovers are different and small in size, which are difficult to be reused, are treated as waste of the cutting process. Only one leftover is considered in one cutting pattern, which simplifies the inventory management and improves the reusability of leftovers.

Definition 3: the solution of a residual 2DCSPUL

The solution of the residual 2DCSPUL is defined as a cutting plan that contains a set of cutting patterns, including patterns of both the stock plate and usable leftovers. Patterns of stock plates may contain items, usable leftovers and waste. Patterns of usable leftovers contain only items and waste. The objective of a residual 2DCSPUL is to minimise the number of stock plates necessarily used to satisfy the demand of items and generate valuable usable leftovers.

2.1 Model of residual 2DCSPUL

Given $n+1$ types of input materials, including the stock plate and usable leftovers (initially only the stock plate), and a set of small rectangular items. All the demanded items must be cut from stock plates or usable leftovers, and newly generated usable leftovers cut from stock plates can be stocked for subsequent periods. The objective of the residual 2DCSPUL is to minimize the number of used plate.

To model the residual 2DCSPUL, we use the following constants and sets as shown in Table 1 and decision variables as shown in Table 2.

Table 1
Constants and sets

Notations	Definition
$n$	Number of item types
$m$	Number of input material types
$I$	Index set of item types, $I=\left\{{1,2,\ldots,n}\right\}$
$J$	Index set of input material types, $J=\left\{{0,1,\ldots,m}\right\}$ , consisting of stock plate ( $j=$ 0), and usable leftovers ( $j=$ 1, $\ldots$ , $m$ )
$L_{j}$	Length of input material, $j\in J$
$W$	Width of input material
$D_{j}$	Quantity of input material $j$ , $D_{j}=1$ , if $\left({j=1,\ldots,m}\right)$
$l_{i}$	Length of item type $i,i\in I$
$w_{i}$	Width of item type $i,i\in I$
$d_{i}$	Demand of item type $i,i\in I$
$K$	Index set of all feasible patterns that can be applied to the stock plate
$p_{k}$	Feasible pattern of stock plate, $k\in K$
$pl_{j}$	Pattern of usable leftover type $j,j=$ 1, $\ldots$ , $m$

Table 2

Decision variables

Variables	Definition
$x_{k}$	Frequency of plate pattern $p_{k}$ , $k\in K$
$a_{ik}$	Number of item type $i$ in plate pattern $p_{k},i\in I,k\in K$
$y_{j}$	Frequency of usable leftover pattern $pl_{j},j=1,\ldots,m$
$b_{ij}$	Number of item type $i$ in leftover pattern $pl_{j},i\in I$ , $j=1,\ldots,m$

Mathematical model for the residual 2DCSPUL:

$\displaystyle\mathop{\min}\limits_{k\in K}x_{k}$ (1)

Subject to:

$\displaystyle\mathop{\sum}\limits_{k\in K}a_{ik}x_{k}+\mathop{\sum}\limits_{j=% 1}^{m}b_{ij}y_{j}=d_{i},i\in I$ (2) $\displaystyle x_{k}\in\mathbb{N},k\in K$ (3) $\displaystyle y_{j}\in\left\{{0,1}\right\},j=1,\ldots,m$ (4)

The objective Eq. (2) minimizes the number of used stock plates. Constraints (2) ensure that the demands of items must be met by cutting from stock plates and usable leftovers. Constraints (3) are non-negative integrity constraints. Constraints (4) are binary constraints.

The solution of the residual 2DCSPUL is a cutting plan, which is the union of pattern set of stock plates and usable leftovers. For simplicity, we consider only the 3-staged patterns of homogenous strips (3H patterns). Relatively uniform strip 3-staged designs are a style of shape descriptors that comprises three phases or parts of a recurring motif. A 3H pattern can be divided into items in three stages: vertical cuts separate the input material into segments, then each segment is split into strips by horizontal cuts, finally strips are divided into items of the same type by another set of vertical cuts. In order to reduce the number of stock plate used in the cutting plan, cutting patterns should be placed more items and usable leftovers. In the next sub-section, we will discuss the cutting pattern of stock plate, patterns of usable leftovers, and the choice of the current pattern.

2.2 Pattern of stock plate

Only the remaining sub-plate on the right side are considered as the potentially usable leftover. Figure 1 shows a cutting pattern of the stock plate, where the left side sub-plate is cut into demanded items and waste, and the residual sub-plate on right side with slash shadow is the potentially usable leftover. If the residual sub-plate is long enough to contain at least one item, it is called a usable leftover. To get exact items from the plate, we use the 3H cutting pattern with usable leftover where three stages of guillotine cuts are used. As shown in Fig. 1, the first-stage cuts separate the stock plate into some segments and a potentially usable leftover, then the second-stage cuts split each segment into homogenous strips and waste, and finally the third-stage cuts divide each strip into exact items and waste. by segmenting the plate stocks and the leftovers thus the segmented stocks and leftovers of plates were again separated into strips of homogeneous states then each strips will be separated into the exact item shown in Fig. 2.

Figure 2.

Pattern with leftover cut from stock plate.

The pattern value of the stock plate is the sum value of both the included items and the potentially usable leftover. To reduce the number of stock plate used in the cutting plan, the cutting pattern should make full use of the stock plate, maximize the sum value of both include items and the leftover:

$\displaystyle Z_{0}=\max\mathop{\sum}\nolimits_{i\in I}a_{i}v_{i}+V_{l};a_{i}% \leqslant r_{i},a_{i}\in\mathbb{N};$ (5)

Where $Z_{0}$ is the pattern value of the stock plate. $a_{i}$ is the number, $v_{i}$ is the value, and $r_{i}$ is the remaining demand of item type $i$ that included in the pattern, $i\in I$ . $V_{l}$ is the value of the potentially usable leftover, which is proportion to its length $l$ , and is defined as follows:

$\displaystyle V_{l}=\left\{\begin{array}[]{ll}\textit{clW},&\textit{if}\ l% \geqslant l_{\min}\\ 0,&\textit{otherwise}\\ \end{array}\right.$ (6)

Where $c$ is the value coefficient, and $l_{\min}=\mathop{\text{missing}}{min}\nolimits_{i\in I}\left\{{l_{i}}\right\}$ is the minimum length of items. If the length of the potentially usable leftover is longer than $l_{\min}$ , it is considered as a usable leftover, otherwise it is considered as a trim-loss of zero value. Usable leftovers return to stock may lose some of its value, so a value coefficient $c$ , $0<c\ll 1$ is multiplied to its original value.

2.3 Pattern of usable leftover

Compare with the stock plate, unused parts on patterns of usable leftovers from previous cutting process are generally small for use, and are considered as waste of the cutting process. As for that, the pattern value of the usable leftover, maximize the sum value of included items:

$\displaystyle Z_{j}=\max\mathop{\sum}\nolimits_{i\in I}{b}_{ij}v_{i}b_{ij}% \leqslant r_{i},b_{ij}\in\mathbb{N}$ (7)

Where $Z_{j}$ is the pattern value, and $b_{ij}$ is the number of item type $i$ included in the cutting pattern of usable leftover type $j$ .

2.4 The pattern to be chosen

The cutting plan is composed of cutting patterns, and patterns are generated sequentially one by one. Each pattern fulfills part of the demands and the solution process is terminated when all the item demands are met. The following are the main stages in a demand and marketplace assessment: Examination of the present condition & determination of goals, the gathering of quantitative information, conducting an analysis of the market. Usable leftovers from previous cutting processes are given priority-in-use compares with that of stock plates, because leftovers are not easy to preserve. The preferential use of leftovers can also reduce the use of stock plates. Here we attach a cost coefficient $C_{j}$ to the material cost, where $C_{j}=1$ if $j=0$ (stock plate), or $C_{j}<$ 1 if $j\neq 0$ (usable leftover). The pattern with maximum value-to-cost ratio is chosen as the pattern to construct the current cutting plan, where the maximum value-to-cost ratio is defined as follows:

$\displaystyle M_{R}=\mathop{\max}\nolimits_{j\in J,D_{j}>0}\left({Z_{j}/C_{j}L% _{j}W}\right)$ (8)

Small leftovers are more difficult to use, and should have higher priority than large leftovers, so $C_{j}$ is set to be negatively correlated with the length of the material.

3. Solving the residual 2DCSPUL

In this study, we solve the residual 2DCSPUL, considering both the generation and the prioritized utilization of leftovers. An algorithm that combines the iterative sequential value correction heuristic (ISVC) with the beam search (BS) heuristic (abbreviated to ISVC-BS) is proposed, both stock plates and usable leftovers from previous periods are used as input material and helps in providing the solution for the problem occurred in the cutting plan by the iterative cutting plan. A heuristic search method called beam search constantly increases the W value of the top vertices at every stage. It advances layer by stage, always starting from the top W terminals within every stage. It constructs its tree structure using breadth-first searching. A mathematical improvement method called the Iterative Sequential Value Correction (ISVC) heuristics is employed to increase the precision of importance attributed to objects on an inventory plate. To enables organizations more effectively allocate funds and streamline their processes, the concept is frequently utilised in stock control and supply chain optimization.

The sequential value correction heuristic constructs cutting plans iteratively and chooses the best one as the final solution. Cutting patterns that constitute the cutting plan are generated sequentially. To avoid accumulation of good patterns at the early stage of the iteration, the values of item types are corrected after each pattern, balance the combination of items in the whole iteration [17].

The sequential value correction heuristic is effective in input minimization, but without considering the generation and reuse of leftovers. We modify the iterative sequential value correction heuristic to give priority to leftovers, and use the BS heuristic to effectively accumulate fragments of unused parts into usable leftovers. Algorithm ISVC-BS considers both the accumulation and the reusability of leftovers to minimize the number of used stock plates in long-term period.

3.1 Algorithm ISVC-BS

A method for machine learning called ISVC-BS is employed to find and follow things in short videos. Background removal, adaptable training, numerous target tracking, durability, speed, etc. are a few of its key traits. Algorithm ISVC-BS generates a cutting plan in three phases: (1) Generate the first cutting pattern, where a Pattern-procedure is used to generate patterns of both leftovers and stock plates, and choose the pattern of maximum value-to-cost ratio as the first pattern. Consequently, the three steps of designing are style research, specification document layout, then template modelling. By breaking down fresh fashion developments into an intermediary form, they are evaluated. (2) Obtain the best pattern set of remaining demands by the iterative sequential value correction heuristic. The BS-procedure is used to recombine the low usage pattern in the residual pattern set. (3) Combine the first pattern and the best residual pattern set to form the cutting pattern set of the final solution. The Pattern-procedure used in Phase (1) is presented in Section 3.2. The BS-procedure used in Phase (2) is presented in Section 3.3. The value correction formula used in Phase (2) is described in Section 3.4.

The following notations are used as shown in Table 3.

Table 3
Notations

Notations	Definition
$G$	Current number of generation
$G_{\max}$	Maximum number of generation
Num	Number of used plates in the best cutting plan
$P$	Pattern set of the current cutting plan
Area	Area consumption of the current cutting plan.
$r_{i}$	Remaining demands
$P_{R}$	Current pattern set of the remaining demands
$P_{B}$	Best pattern set of the remaining demands
$r_{i}^{\prime}$	Residual demands
AreaR	Area consumption of $P_{R}$
AreaRm	Area consumption of $P_{B}$

Figure 3 shows the pseudo code of algorithm ISVC-BS. Initially, no cutting plan is available, so both Num. and Area in the best cutting plan are set to be infinite (Step 1). The current cutting plan contains no pattern, so the pattern set $P$ is initialized to be empty at the beginning and remaining demands are initialized to item demands.

Figure 3.

Pseudo code of algorithm ISVC-BS.

3.2 Pattern-procedure

Pattern-procedure is used to obtain the cutting pattern of stock plate and usable. The cutting method uses the angle grinder and the slicer wheel for cutting the thickest steel plates with the minimal amount of effort, it will helpful in making the straight and curve cuts safely. The ability to quickly arrange a cutting blade or angle grinders to cutting is their main benefit. 045 chopping wheel are thinner than piping wheels (called as Kerf) as well as sharpening discs (1/4) and thus are especially made for precision cutting. It’s suitable for performing modest tasks like precision cutting or timber up to 2–3 cm thick. It is not advised that it be utilized to cut cement and pebbles. The cutting pattern is obtained based on implicit enuting all homogenous strips of different items that are combined into segments that are combined into plates. The Pattern-procedure comprises two phases:

(1) solve backpack problem (9) for the value of segments $x\times W$ , $x\in Q$ :

$\displaystyle F(x)=\max\mathop{\sum}\nolimits_{i\in l_{x}}[v(x,i)\gamma_{i}]$ (9)

Subject to:

$\displaystyle\mathop{\sum}\limits_{i\in I_{x}}w_{i}\gamma_{i}\leqslant W$ (10) $\displaystyle e\left({x,i}\right)\gamma_{i}\leqslant r_{i},\gamma_{i}\in% \mathbb{N},x\in Q$ (11)

Where $Q=\{kl_{i}|0\leqslant k\leqslant\min\left({r_{i},\lfloor\frac{L}{l_{i}}\rfloor% }\right),k\in\mathbb{N},i\in I\}\cup\left\{L\right\}$ is the set of normal segment lengths, $I_{x}=\{i|l_{i}\leqslant x\}$ is the set of item types that can be packed, and $\gamma_{i}$ is the number of times strip $x\times w_{i}$ appears in segment $x\times W$ . And $e\left({x,i}\right)=\min\left({x/l_{i},r_{i}}\right)$ is the number of items, $v\left({x,i}\right)=e\left({x,i}\right)$ . $v_{i}$ is the value of strip $x\times w_{i}$ . The objective Eq. (9) maximizes the value of segment $x\times W$ . Constraint Eq. (10) ensures that strips arranged in the segment do not exceed the upper boundary of the segment. Constraints Eq. (11) ensure that items included in strips of the segment do not exceed the remaining demands.

The segment can be generated through vertical combination of horizontal strips or a sub-segment and a homogenous strip, and the segment value is the total value of the sub-segment and the strip.

Let $n(x,y,i)$ be the number of $\textit{type}-i$ items included, $F_{s}\left(y\right)$ be the value of the sub-segment $x\times y$ , $x\in Q$ , $i\in I$ . Initially $F_{s}\left(0\right)=0$ , $n(x,0,i)=0$ . The following recursion determines $F_{s}\left(y\right)$ :

$\displaystyle e_{i}=\min\left\{{\left\lfloor\frac{x}{l_{i}}\right\rfloor,r_{i}% -n\left({x,y-w_{i},i}\right)}\right\},i\in I_{xy}$ (12) $\displaystyle F_{s}\left(y\right)=\max\{F_{s}\left({y-1}\right),\mathop{\max}% \nolimits_{i\in I_{xy}}[F_{s}\left({y-w_{i}}\right)+e_{i}v_{i}],0<y\leqslant W$ (13)

Where $e_{i}$ is the number of $\textit{type}-i$ items in strip $x\times w_{i}$ . $I_{xy}=\left\{{i\left|{\left({l_{i},w_{i}}\right)\leqslant\left({x,y}\right)% \wedge r_{i}}\right\rangle 0}\right\}$ is the set of item types that can be fit into the sub-segment.

$F_{s}\left(y\right)$ is initially set to be the same as $F_{s}\left({y-1}\right)$ . If sub-segment $x\times y$ is obtained by placing strip $x\times w_{i}$ on the top of sub-segment $x\times\left({y-w_{i}}\right)$ , Eq. (12) ensures that the total number of $\textit{type}-i$ items in the sub-segment $x\times y$ does not exceed the remaining demand $r_{i}$ . Although strip $x\times w_{i}$ can contain $\left\lfloor{x/l_{i}}\right\rfloor$ $\textit{type}-i$ items, but the number of $\textit{type}-i$ items in sub-segment $x\times\left({y-w_{i}}\right)$ is $n(x,y-w_{i},i)$ , so only $e_{i}$ items are taken as effective. The number of $\textit{type}-i$ items in sub-segment $x\times y$ can be determined according to the following rules:

$\displaystyle\text{If}\ F_{s}\left(y\right)=F_{s}\left({y-1}\right),\text{then}$ $\displaystyle\quad n\left({x,y,i}\right)=n\left({x,y-1,i}\right).$ (14) $\displaystyle\text{Else if}\ F_{s}\left(y\right)=F_{s}\left({y-w_{k}}\right)+e% _{k}v_{k},\text{then}$ $\displaystyle\quad\text{for all}\ i\in I,\ \text{If}\ i=k\ \text{then}$ $\displaystyle n\left({x,y,i}\right)=n\left({x,y-w_{k},k}\right)+e_{k}$ (15) Else $\displaystyle\quad n\left({x,y,i}\right)=n\left({x,y-w_{k},i}\right)$ (16)

After solving recursion Eq. (13), the value of segment $x\times W$ is $F\left(x\right)=F_{s}\left(W\right)$ , and the number of $\textit{type}-i$ items in the segment is $n\left({x,W,i}\right)$ , $i\in I$ , $x\in Q$ .

(2) solve backpack problem Eq. (17) for the value of sub-plates $x\times W,x\leqslant L$ :

$\displaystyle f\left(x\right)=\max\mathop{\sum}\nolimits_{q_{k}\in Q}[f(q_{k})% t_{k}]$ (17)

Subject to:

$\displaystyle\quad\mathop{\sum}\limits_{q_{k}\in Q}q_{k}t_{k}\leqslant x$ (18) $\displaystyle\quad\mathop{\sum}\limits_{q_{k}\in Q}n\left({q_{k},W,i}\right)t_% {k}\leqslant r_{i},t_{k}\in\mathbb{N}$ (19)

Where $t_{k}$ is the number of times segment $q_{k}\times W$ included in the sub-plate $x\times W$ , $q_{k}\in{Q}$ . The objective function (17) maximizes the value of sub-plate $x\times W$ . Constraint (18) ensures that segments arranged in the sub-plate do not exceed the right boundary. Constraints (19) ensure that the number of items included in segments of the sub-plate does not exceed the remaining demands.

The cutting pattern can be generated through horizontal combination of segments or a segment and a sub-plate. Let $\eta(x,i)$ be the number of $\textit{type}-i$ items in sub-plate $x\times W$ , $x=0,\ldots,L$ . Initially let $f(0)=0$ , $\eta(0,i)=0$ , $i\in I$ . The following recursion determines $f(x)$ , the value of sub-plate $x\times W$ :

$\displaystyle h_{ki}=\min\left\{{n\left({q_{k},W,i}\right),r_{i}-\eta\left({x-% q_{k},i}\right)}\right\},i\in I,k\in K_{x}$ (20) $\displaystyle f\left(x\right)=\max\left\{f\left({x-1}\right),\mathop{\max}% \nolimits_{k\in K_{x}}\left[{f\left({x-q_{k}}\right)+\mathop{\sum}\nolimits_{i% \in I}h_{ki}v_{i}}\right]\right\},0<x\leqslant L$ (21)

Where $K_{x}=\{k|q_{k}\leqslant x\}$ is the set of segments that can be packed in sub-plate $x\times W$ , $h_{ki}$ is the number of $\textit{type}-i$ item in segment $q_{k}\times W$ . $f(x)$ is initially the same as $f(x-1)$ . If sub-plate $x\times W$ is obtained by placing segment $q_{k}\times W$ on the right of sub-plate $\left({x-q_{k}}\right)\times W$ , Eq. (20) ensures that items included in the sub-plate do not exceed the remaining demands. Although segment $q_{k}\times W$ can contain $n\left({q_{k},W,i}\right)$ $\textit{type}-i$ items, but the number of $\textit{type}-i$ items in sub-plate $\left({x-q_{k}}\right)\times W$ is $\eta(x-q_{k},i)$ , so only $h_{ki}$ items in segment $q_{k}\times W$ are taken as effective. Equation (21) maximizes the value of sub-plate $x\times W$ .

Figure 4.

Pseudo code of the Pattern-procedure.

The number of $\textit{type}-i$ items in sub-plate $x\times W$ can be determined by the following rules:

$\displaystyle\text{If}\ f(x)=f(x-1),\text{then}$ $\displaystyle\quad\eta(x,i)=\eta(x-1,i)$ (22) $\displaystyle\text{Else if}\ f\left(x\right)=f\left({x-q_{k}}\right)+\mathop{% \sum}\nolimits_{i\in I}h_{ki}v_{i},\text{then}$ $\displaystyle\quad\eta\left({x,i}\right)=\eta\left({x-q_{k},i}\right)+h_{ki}$ (23)

After solving backpack problem (21), the final result $f\left(L\right)$ is the sum value of items included in the pattern of plate $\times W$ , and the number of $\textit{type}-i$ items in the pattern is $\eta\left({L,i}\right)$ , $i\in I$ . Roll back from $f\left({L_{0}}\right)$ until the value of sub-plate $x\times W$ differ from that of $L_{0}\times W$ , then the length of the potentially usable leftover is $L_{N}=L_{0}-x+1$ . And the pattern value of the stock plate $L_{0}\times W$ is $Z_{0}=f\left({L_{0}}\right)+V_{L_{N}}$ . The value and the number of items of sub-plate $x\times W$ is $f\left(x\right)$ and $\eta\left({x,i}\right)$ . The value and the number of items of leftover $j$ is $Z_{L_{j}}=f\left({L_{j}}\right)$ and $\eta\left({L_{j},i}\right).$ . The value $f\left(x\right)$ is also used as the estimate of the unfilled sub-plate $x\times W$ in the BS-procedure( ). Figure 3 shows the pseudo code of the Pattern-procedure.

3.3 BS-procedure

Beam search heuristic is incomplete derivative of branch and bound algorithm where only elite nodes that have high potential are investigated. It is used to solve combinatorial optimization problems including cutting problems, beam search is a best-first search optimization algorithm that reduces its memory requirement this algorithm produces the graph by the promising nodes in the limited set of data. Hifi et al. [18] described the beam search (BS) heuristic in solving the two-staged cutting problems, Akeb et al. [19]used the BS heuristic in circular packing problems. The circular packaging issue is the task of determining the largest circumference of a certain quantity of identical rounds that may be arranged in a two-dimensional vessel with a stipulated diameter without overlapping. Hexagonal packing, the greatest effective way to package circular, achieves an effectiveness of about 91%. An algorithmic is a step-by-step process that takes a limited number of steps to resolve a specific issue. Using identical settings, an individual’s outcome is foreseeable & repeatable (input). Heuristics are rough estimates that act as a roadmap for further research. The problems are as many circles were packed into a single container the overlapping of the circle takes place and the circle goes out of the boundary this is solved by the beam search heuristics method, and both of them obtain good patterns in a short time. A search procedure called beam search is employed to select the top candidate from a group of solutions in a search process. It may be employed to locate a resolution that maintains the circular inside the bounds when dealing with the issue of a circular straying outside of the border. We use the beam search heuristic to accumulate residues into the large potentially usable. Typically, a beam search is employed in big systems with limited capability to hold the whole tree structure to ensure controllability. For instance, numerous automatic translation platforms have made use of it.

Three basic elements are required for a BS heuristic: node definition, evaluation operator and branching strategy. For a rectangle input material $L\times W$ , a node can defined as a pair of subrectangles: $\mu=((x\times W)$ , $((L-x)\times W))$ . Where ( $x\times WA$ ) is the sub-plate filled with segments of total length $x$ and total value $Z_{\mu}$ , and $((L-x)\times W)$ is the unfilled sub-plate with estimate $U_{\left({L-x}\right)}=f\left({L-x}\right)$ . The evaluation operator of a node $\mu$ is $\overline{Z_{\mu}}=Z_{\mu}+U_{\left({L-x}\right)}$ . To branch a node $\mu$ is to fill segments into the unfilled sub-plate, and create a set of children: $(((x+q_{k})\times W)$ , $((L-x-q_{k})\times W))$ , $(L-x-q_{k})\geqslant 0$ , $q_{k}\in Q$ . Only the top $\delta$ child nodes of high assessment are kept as the elite nodes for further branching, where $\delta$ is the beam width. Probabilistic beam search is the name given to this search method. Recovering beam searching or adaptable binary search are more variations. There are five types of strategies used for the beam search algorithms namely 1) small rectangular box selection strategy, 2) planning action selection strategy, 3) updating the corner areas, 4) line cutting strategy and 5) defect cutting strategy. The rectangular box selection is the begging of the process the finished small rectangular box is considered as the input to the stack and the output should be the same as the initial order in the stack, then the pattern is marked by the achieving the action in the placement are of the corners. The coroner updating strategy contains three set of rules with respect to the three types of corners they are rule 1 here the new one cut area will be temporarily considered, rule 2 when the box is placed in the bottom two cut areas then new one area should be considered and the last is rule 3 when the particular cut area cannot separate the small rectangular block selection then set any block for cutting. The line cutting strategy is used to divide the four cut lines, by developing the decision method for these four lines thus the positioning of the cut line determines three condition when there is an occurrence of cutting the defect from the product. Three groups can be made up of defect-finding methods: Static techniques: Tests performed without actually running an application or system. An illustration of a static measurement method is a code review. Dynamic methods of analysis: Defects detection through the physical execution of parts of the system. The cut defect strategy is the process of determining number of defects in the rectangular box in the pre-cutting actions in the corner area of the rectangular box, hence the operation of cutting down the defect is considered in this method then the piece of defect from the product will be removed.

Figure 5.

Pseudo code of the BS-procedure.

Figure 5 provides the pseudo code of BS-procedure. The root node is $((0\times W),(L\times W))$ , where no segment has been packed. Initially, the elite set $B$ contains only the root node, no node is branched, so the children set $B_{C}$ is empty, the optimal pattern value $Z^{\ast}=f\left(L\right)$ comes from Pattern-procedure( ), $r_{\mu i}$ is item demands to be cut at this level. For each node in $B_{C}$ , if it is a terminal node, calculate the pattern value, otherwise, continue the branching, and insert the top $\min\left({\delta,\left|{B_{C}}\right|}\right)$ children into $B$ , where $\left|{B_{C}}\right|$ is the number of set $B_{C}$ .

3.4 Item value correction

The component price adjustment technique allows one to take wastage, depreciation, or expiry into consideration when modifying the valuations of specific objects in an inventory plate. In order to determine how to alter product prices, the process entails examining trends in the stock sheet, like how fast specific things are moving or how often items are all being refilled. A greedy algorithm is a method of problem-solving that chooses the best choice at the time. It is unconcerned about if the most awesome achievement at the moment will produce the final best outcome. The greedy algorithms uses the heuristics for problem solving methods to find the optimal solution at every stages, thus heuristic is the function used in the state of information search by analyzing the correct path. A heuristic algorithm is a process used in numerical methods to find answers to optimization problems that are close to optimum. Yet, this is accomplished by sacrificing quickness for effectiveness, thoroughness, correctness, or accuracy. Due to the combination of UCS with greedy best-first search capabilities, the issue is effectively solved. Applying the heuristic function, it locates the quickest route across the search process. This search method produces ideal outcomes quicker and grows less search trees. There are various methods that can be employed to lessen the influence of this heuristics. They include alternate heuristic algorithms, restrictions, diversity, randomness, and much more. The limits of the goals that traditional heuristic algorithms attempt to emulate frequently result in problems including storage inefficiency, getting stuck in locally global optimal, unpredictable results, and so on. Hence, to reduce the greedy impact heuristic algorithm, the item values are modified after each pattern of stock plate as follows (Chen et al. 2016):

$\displaystyle v_{i}\leftarrow g_{{}_{1}}v_{i}+g_{{}_{2}}(l_{i}w_{i})^{\beta}/u$ (24) $\displaystyle g_{2}=\raise 3.01pt\hbox{${\alpha a_{i}}$}\!\mathord{\left/{% \vphantom{{\alpha a_{i}}{d_{i}}}}\right.\kern-1.2pt}\!\lower 3.01pt\hbox{${d_{% i}}$}$ (25) $\displaystyle g_{1}=1-g_{2}$ (26) $\displaystyle{u}=\left.\left({\mathop{\sum}\limits_{i\in I}l_{i}w_{i}a_{i}}% \right)\right/L_{0}W$ (27)

Often a weighted mean seems to be more precise than a basic averaging. In a weighting factor, the allocated weighting is increased by every sample points number, and the results are added together and reduced with the total amount of datasets. Because of this, a weighting can increase the reliability of the information. Equation (24) expresses the new value which is the weighted average of the old value and the over-proportional material-per-item consumption in the current pattern, where $g_{1}$ and $g_{2}$ are the corresponding weights, $u$ is the material utilization of the current pattern. Parameter $\alpha\in[0.6,0.9]$ , and $\beta$ is slightly larger than 1, so that items of large area have a larger value increment. $u$ is used as the denominator,

Figure 6.

In order to, the item value in the worse pattern increases more. The major expense of inflation is the depreciation of actual earnings, which occurs when costs increase arbitrarily & causes certain customers’ disposable income to decline. As for that, large or odd-sized item types that cannot combine well with other types are considered in the early stage when more combinations can be chosen.

4. Computational results

4.1 Environment and parameter setting

Algorithm ISVC-BS was implemented in C#, and performed on a 2.53 GHz Intel core Duo processor with 2 GB of RAM memory. Twenty instances (ATP30-ATP49) are used for test. All the items, plates and leftovers are oriented [11].

Figure 7, reports the area consumption under different iteration $G$ , value coefficient $c$ and beam width $\delta$ . It seems that the area consumption is greatly influenced by the number of iteration and the value coefficient. The area consumption decreases as the number of iterations increase, and area consumption of $c=0.05$ is less than that of $c=0$ at the same number of iterations. When $c=0$ , the area is unchanged after $G=5$ , while when $c=0.05$ , it continues to decrease until $G=40$ . In the following sub-sections, we set $c=0.05$ , $G=50$ , $\delta=5$ and cost coefficient $C_{j}=0.99^{(L/L_{j})}$ .

Figure 7.

Area consumption under different coefficient.

4.2 Results of single period

Table 4 shows the results of one single period, compared with algorithms of Silva et al. [1] and Punchiger et al. (2007). Where ID refers to the instance number, $N_{\textit{Sa}}$ and $N_{\textit{Pr}}$ are the number of used plates of Silva and Punchiger, and the symbol “–” denotes that the algorithm cannot return a result in 7200s. $N_{\textit{IB}}$ , $L_{N}$ and $T_{\textit{IB}}$ are the number of used plates, the length of new usable leftover and the computational time of ISVC-BS, and the symbol “ $+$ ” separates different leftovers.

Table 4
Results of single period

ID	$N_{\textit{Sa}}$	$N_{\textit{Pr}}$	$N_{\textit{IB}}$	$L_{N}$	Area	$T_{\textit{IB}}$	ID	$N_{\textit{Sa}}$	$N_{\textit{Pr}}$	$N_{\textit{IB}}$	$L_{N}$	Area	$T_{\textit{IB}}$
1	9	9	9	853	1138480	2.63	11	–	16	15	101	1399872	7.68
2	–	15	14	443	11125524	22.26	12	12	13	12	552	3483564	3.64
3	14	13	12	0	456816	3.79	13	17	16	15	73	707712	9.51
4	13	14	12	0	2842836	8.02	14	15	14	13	323	4019211	13.05
5	6	6	6	566	1917024	2.16	15	9	10	9	119	936448	4.06
6	8	8	8	766	4487186	3.37	16	8	9	8	95	814402	2.40
7	8	8	8	322	969656	1.62	17	12	12	11	0	2352064	6.07
8	15	12	11	34	4234086	9.31	18	14	14	13	303	2662524	5.93
9	12	12	10	0	2616980	5.05	19	9	9	8	190	1843532	2.47
10	12	12	12	37+427	3001992	3.11	20	6	6	5	65	1674770	1.53

Figure 8.

Result of single period.

Shown in Fig. 8, we compare only the number of used plates, because the other two literatures did not consider residual materials. The ISVC-BS uses fewer stock plate in 12 instances and the same in 8 instances (the bold italic font indicates the minimum number). If “–” are taken as the larger number, then the total number of used plate is 211 versus 230 versus 228. The average computational time of the ISVC-BS is 5.88s. Algorithm ISVC-BS used the same number of used plate as that of ISVC, but the area consumption of the stock plate is 52684679 versus 55230800, the plate area consumption is smaller because usable leftovers are saved to subsequent periods.

4.3 Results of adjacent period

Usable leftovers cut from the previous period are used in the subsequent period where item data are the same. Table 5 shows results of the second adjacent period, where $L_{j}$ denotes the lengths of leftovers from the previous period and $L_{N}$ is the lengths of unused or newly generated usable leftovers. The utilization of the usable leftovers saves 11 stock plates, and the total number of used plates is decreased to 200. The area consumption is 50192884, compares with the previous period, the area saved is 2491795. The number of leftovers in each instance is not more than two. The average computational time of the second adjacent is 5.31s, similar to that of the first single period.

Table 5
Results of the second adjacent periods

ID	$L_{j}$	$N_{\textit{IB}}$	$L_{N}$	Area	$T_{\textit{IB}}$	ID	$L_{j}$	$N_{\textit{IB}}$	$L_{N}$	Area	$T_{\textit{IB}}$
1	853	8	712	1019008	2.52	11	101	15	252	1379034	6.44
2	443	13	30	10698472	17.77	12	552	11	267	3280980	3.41
3	0	12	0	456816	3.59	13	73	15	127	691998	8.98
4	0	12	0	2842836	7.41	14	323	12	284	3723020	11.93
5	566	5	337	1658928	1.80	15	119	8	15	877424	3.90
6	766	7	572	3990052	3.67	16	95	7	0	760648	2.20
7	322	7	85	896456	1.49	17	0	11	0	2352064	5.67
8	34	11	34+34	4204132	8.36	18	303	12	213	2494662	5.80
9	0	10	0	2616980	4.60	19	190	8	331	1807718	2.37
10	37+427	11	37+352	2770029	2.78	20	65	5	72	1671627	1.58

Table 6

Results of multiple periods

PN	$N_{R}$	$L_{R}$	$T_{R}$	$N_{U}$	$L_{U}$	$T_{U}$	PN	$N_{R}$	$L_{R}$	$T_{R}$	$N_{U}$	$L_{U}$	$T_{U}$
1	2	521	3.61	2	521	3.04	11	2	746	9.7	2	114	21.0
2	12	345	3.86	13	748	2.67	12	4	686	2.05	4	151	1.95
3	1	741	2.50	1	240	3.36	13	1	773	5.89	2	883	10.6
4	3	632	99.2	4	841	34.3	14	4	334	49.2	5	559	78.8
5	2	449	2.94	3	702	1.64	15	1	112	8.15	2	812	30.1
6	5	482	1.56	5	0	1.12	16	1	29	3.71	2	11+853	35.4
7	1	329	0.91	2	750	6.90	17	3	301	78.1	3	295	47.4
8	5	671	11.1	5	352	33.1	18	3	282	62.6	4	833	17.1
9	3	742	4.02	3	79	3.92	19	2	156	2.01	3	771	2.11
10	3	455	5.65	4	637	5.32	20	2	11	3.60	2	87	1.81

Figure 9.

Results of second adjacent periods.

4.4 Results of multiple periods

In this set of experiments, we used 20 instances, one instance is cut in one period, and the total period is 20. The data of items are the same as previous sub-section, and the stock plate of each instance has the same size which is the longest length and the widest width of all the instances: 931 $\times$ 983. Table 6 compares the results of reuse and unused leftovers in multiple periods, where PN refers to the period number, $N_{R}$ is the number of used plates, $L_{R}$ is the lengths of new usable leftovers, $T_{R}$ is the computational time that usable leftovers are reused in subsequent periods. $N_{U}$ , $L_{U}$ and $T_{U}$ are the corresponding results of not considering usable leftovers.

Table 7
Cutting stock problem

Width	Quantity	Usage
20	5	120
25.56	16.9	40.79133
30	27.5	8.695652
35.67	31.2	13.36922
40.67	38.3	6.002279
45.815	41.5	9.883754
50.96	47.6	6.818182

Table 8

Iterative sequential value correction

Energy block	Temperature correction	Iteration
3.67	12.5	25.6
15.78	20.3	32.8
27.89	28.1	40
40	35.9	47.2
52.11	43.7	54.4
64.22	51.5	61.6
76.33	59.3	68.8

Figure 10.

Results of multiple periods.

Shown in Fig. 10, The total number of used plate is 71 vs 60, and 11 plates are saved when considering and reusing usable leftovers. The computational time of some instances is quite different, but the average time is similar, which is 18.03s vs 17.1s. Considering and reusing usable leftovers does not increase much time. Shown in Figs 11 and 12.

We show only the results of fixed parameters in all simulations. The results are similar when parameter $C_{j}$ is slightly less than 1 and negatively correlated with the length, and $c$ is slightly larger than zero. And a larger $\delta$ results in a little better solution but takes more time.

Table 7 shows, cutting stock problem, in this table based on, width, quantity and usage.

Figure 11.

Cutting stock problem.

Table 8 shows, iterative sequential value correction, in this table based on, energy block, temperature correction and iteration.

Figure 12.

Iterative sequential value correction.

5. Conclusions and future work

In this paper, we presented the model of the residual two-dimensional cutting stock problem with usable leftover. We designed an algorithm called ISVC-BS that combined the iterative sequential value correction heuristic with beam search heuristic to solve the problem, and obtains the cutting plan of minimum used plates with usable leftovers effectively. The ISVC-BS accumulated fragments into usable leftovers, and reused them as input material in subsequent periods. The utilization of leftovers can save a considerable amount of stock plate and reduce the production cost of enterprises in the long-term production period.

Leftovers should not be remained in stock for a long time. The longer the leftovers kept in stock, the greater the possibility of value loss. Therefore the cost coefficient should be reduced with period. Another interesting perspective for future research is to extend the algorithms to deal with the multi-period cutting processes, considering the benefits of advance cutting of some regular items for future used, instead of generating leftovers for future items.

Funding

This research is part of Project 71371058 supported by National Natural Science Foundation of China, Project 2020GXNSFAA159090 supported by Guangxi Natural Science Foundation and Project 20200371 supported by Guangxi University Foundation. The authors would like to thank for the financial support.

Data availability

All data generated or analysed during this study are included in the manuscript.

Code availability

Not applicable.

Author’s contributions

Qiulian Chen and Yan Chen. contributed to the design and methodology of this study, the assessment of the outcomes and the writing of the manuscript.

Footnotes

Conflict of interest

There is no conflict of interest among the authors.

References

Silva

Filipe

and Valério De Carvalho

J.M.

. An integer programming model for two-and three-stage two-dimensional cutting stock problems, European Journal of Operational Research 205(3) (2010), 699–708.

Octarina

Septimiranti

and Yuliza

, Implementation of arc flow model incapacitated multi-period cutting stock problem with the pattern set up cost to minimize the trim loss, In Journal of Physics: Conference Series 1940(1) (2021), 012018.

Brown

A.R.

, Optimum packing and depletion (1971).

Koch

Sebastian

and Gerhard

, Integer linear programming for a cutting problem in the wood-processing industry: a case study, International Transactions in Operational Research 16(6) (2009), 715–726.

Abuabara

and Reinaldo

, Cutting optimization of structural tubes to build agricultural light aircrafts, Annals of Operations Research 169(1) (2009), 149–165.

Cherri

A.C.

Arenales

M.N.

and Yanasse

H.H.

, The one-dimensional cutting stock problem with usable leftover–A heuristic approach, European Journal of Operational Research 196(3) (2009), 897–908.

Cui

and Yuli

, A heuristic for the one-dimensional cutting stock problem with usable leftover, European Journal of Operational Research 204(2) (2010), 245–250.

Coelho

K.R.

Cherri

A.C.

Baptista

E.C.

Chiappetta Jabbour

C.J.

, and Soler

E.M.

, Sustainable operations, The cutting stock problem with usable leftovers from a sustainable perspective, Journal of Cleaner Production 167 (2017), 545–552.

Ravelo

S.V.

Meneses

C.N.

and Santos

M.O.

, Meta-heuristics for the one-dimensional cutting stock problem with usable leftover, Journal of Heuristics 26(4) (2020), 585–618.

10.

Wäscher

Heike

and Holger

, An improved typology of cutting and packing problems, European Journal of Operational Research 183(3) (2007), 1109–1130.

11.

Andrade

Birgin

E.G.

Morabito

and Ronconi

D.P.

, MIP models for two-dimensional non-guillotine cutting problems with usable leftovers, Journal of the Operational Research Society 65(11) (2014), 1649–1663.

12.

Andrade

Birgin

E.G.

and Morabito

, Two-stage two-dimensional guillotine cutting stock problems with usable leftover, International Transactions in Operational Research 23(1-2) (2016), 121–145.

13.

Dun-hua

Fei-fei

and Yao-dong

, Optimal Two-Section Layouts for the Two-Dimensional Cutting Problem, Journal of Information Processing Systems 17(2) (2021), 271–283.

14.

Dechampai

Samerjit

Wuthichai

and Kittipong

, Applying material flow cost accounting and two-dimensional, irregularly shaped cutting stock problems in the lingerie manufacturing industry, Applied Sciences 11(7) (2021), 3142.

15.

Dodge

MirHassani

S.A.

and Hooshmand

, Solving two-dimensional cutting stock problem via a DNA computing algorithm, Natural Computing 20(1) (2021), 145–159.

16.

Cui

, Heuristic and exact algorithms for generating homogenous constrained three-staged cutting patterns, Computers & Operations Research 35(1) (2008), 212–225.

17.

Chen

Yaodong

and Yan

, Sequential value correction heuristic for the two-dimensional cutting stock problem with three-staged homogenous patterns, Optimization Methods and Software 31(1) (2016), 68–87.

18.

Hifi

Negre

Ouafi

and Saadi

, A Parallel Algorithm for Constrained Two-staged Two-dimensional Cutting Problems, Computers & Industrial Engineering 62 (2012), 177–189.

19.

Akeb

Mhand

and Rym

M.H.

, A beam search algorithm for the circular packing problem, Computers & Operations Research 36(5) (2009), 1513–1528.

20.

Cheng

M.Y.

Yi-Cho

and Chun-Yao

, Auto-tuning SOS algorithm for two-dimensional orthogonal cutting optimization, KSCE Journal of Civil Engineering 25(10) (2021), 3605–3619.

21.

Hifi

Rym

M.H.

and Toufik

, Algorithms for the constrained two-staged two-dimensional cutting problem, INFORMS Journal on Computing 20(2) (2008), 212–221.

22.

Puchinger

and Raidl

G.R.

, Models and algorithms for three-stage two-dimensional bin packing, European Journal of Operational Research 183(3) (2007), 1304–1327.

23.

Vanderbeck

, A nested decomposition approach to a three-stage, two-dimensional cutting-stock problem, Management Science 47(6) (2001), 864–879.

Heuristics for the two-dimensional cutting stock problem with usable leftover

Abstract

Keywords

1. Introduction

1.1 Literature review

1.2 Article contribution

2. The residual 2DCSPUL

Table 1 Constants and sets

3.1 Algorithm ISVC-BS

Table 3 Notations

4.1 Environment and parameter setting

Table 4 Results of single period

Table 5 Results of the second adjacent periods

Table 7 Cutting stock problem

Funding

Data availability

Code availability

Author’s contributions

Footnotes

Conflict of interest

References

Table 1
Constants and sets

Table 3
Notations

Table 4
Results of single period

Table 5
Results of the second adjacent periods

Table 7
Cutting stock problem