# A Petri Net-Based Algorithm for Solving the One-Dimensional Cutting Stock Problem
## 1 Introduction  
Cutting stock problems are combinatorial problems involving the creation of small objects from large objects according to a cutting plan made of cutting patterns. The larger the number of small objects, the greater the number of possible cutting patterns, and hence these problems are classified as NP-hard optimization problems [1]. In this study, we focus on the single stock-size cutting problem according to [PERSON]'s classification [2] for the one-dimensional case, or one-dimensional cutting stock problem (1D-CSP), as it is best known in most of the literature. The 1D-CSP arises in industries manufacturing goods from paper, metal, glass, and wood, among others. The goal is the reduction in material usage and, therefore, the minimization of the related costs. Apart from cost reduction, industries such as the building industry are concerned with reducing gas emissions due to metal and concrete usage, as pointed out in [3]. Some other studies also address the problem by considering mathematical models that include the reuse of leftovers, as in [4]. Reference [5] presents some LP formulations proposed in the early stages of addressing the 1D-CSP. In the literature, most mathematical models for the 1D-CSP consider functions of only one term, either the total waste or the total number of stocks used. However, ref. [6] demonstrated the effectiveness of using a function that involves simultaneously the total waste and the total number of stocks used. In this study, we consider the objective function of the mathematical model (1)-(3) based on the one used in [7] for the 1D-CSP without contiguity. The objective function to be minimized accounts for both the minimization of waste and the minimization of the number of stocks with waste. \[\text{min}\quad W=\frac{1}{k+1}\left(\sum_{j=1}^{k}\sqrt{\frac{w_{j}}{L_{j}}}+ \sum_{j=1}^{k}\frac{V_{j}}{k}\right) \tag{1}\]  
subject to  
\[\sum_{j=1}^{k}x_{ij}=d_{i},\quad i=1,2,\ldots,m \tag{2}\]  
\[x_{ij}\geq 0\text{ and integer}. \tag{3}\]  
In model (1)-(3), \(L_{j}\) is the length of the stock, \(m\) is the number of different items, \(k\) is the total number of stocks used. \(d_{i}\) represents the demand or total number of orders of item \(i\), while \(l_{i}\) is the length of item \(i\), \(x_{ij}\) is the number of orders of item \(i\) in stock \(j\). \(w_{j}\) and \(V_{j}\) are defined in Equations (4) and (5), respectively, where \(w_{j}\) represents the wastage of stock \(j\). \[w_{j} =L_{j}-\sum_{i=1}^{m}x_{ij}l_{i},\quad j=1,2,\ldots,k \tag{4}\] \[V_{j} =\left\{ \begin{array}{ll}1&\text{if}\quad w_{j}>0,\qquad j=1,2,\ldots,k\\ 0&\text{otherwise}.\end{array} \right. \tag{5}\]  
Most approaches to solving the 1D-CSP are based on linear programming (LP) methods, with the column generation technique being one of the most outstanding ones. Column generation and other techniques focus on generating and reducing the number of cutting patterns. In the 1D-CSP, a cutting pattern is an ordered sequence of items cut from a large object or stock. One-cut models and arc-flow models are other paradigms used to address the 1D-CSP, as solutions to the 1D-CSP can be constructed as sequences of items. This sequential approach to constructing the 1D-CSP solutions motivates our proposal of using ordinary Petri nets (PN) to model the solution construction. We take advantage of the reachability tree to find the best solution through the implementation of a filtered beam search algorithm (FBS). Beam search algorithms are a type of any-time search algorithm, suitable for optimization problems where solutions can be constructed sequentially and represented as a tree structure. Unlike other any-time search methods, beam search algorithms do not perform backtracking. Only the most promising nodes at each level are retained to continue searching for the best path from the root node to a desired final node, while non-promising nodes are pruned permanently. The FBS is an improvement to the classical beam search algorithm.