# A Petri Net-Based Algorithm for Solving the One-Dimensional Cutting Stock Problem
## 6 Experiments  
Although we identified a wide variety of datasets in the literature, most studies do not use common datasets or performance measures to compare the algorithms. Additionally, implementing the published algorithms correctly can be challenging, and often, the code is not shared. Nevertheless, we identified two algorithms that share some similarities with our algorithm and are not based on populations. These algorithms were tested on five datasets that we found suitable for comparison with our algorithm. The first algorithm is the Least Lost Algorithm (LLA), introduced in [49], which uses a dataset of ten instances with a single stock size. We refer to this dataset as _hinterding_ because, to the best of our knowledge, it was first used in [67]. The LLA is executed in two phases. In the first one, the item lengths are arranged in decreasing order while in the second, the second half of the arrangement is put before the first half. In both phases, the items are taken from the arrangement to construct cutting patterns by beginning with those that have no waste. If no additional cutting patterns without waste can be found, the search continues with patterns that have one unit of waste. This process continues by increasing the allowed waste by one unit until all the item orders have been included in a cutting pattern. If the number of stocks used is above the optimal theoretical value by more than 5%, the algorithm performs the second phase. The feature of increasing the allowed waste by one unit is represented in our PN-CSP model with the pattern transitions. The LLA was compared to the EP algorithm shown in [7] over the same dataset and the LLA yielded better results. The other algorithm we compare to the FBS-PN-CSP is the Generate and Solve algorithm (G&S) presented in [50]. This algorithm is also executed in two phases. The first one reduces the problem size using a tree method that constructs all possible cutting patterns. Feasible cutting patterns are then selected and sent to the second phase, where an integer linear programming (ILP) method is implemented to obtain the best solution for the reduced set of solutions. In the first phase, a new reduced set of solutions is generated by considering an aging mechanism for previously used solutions, which can be re-selected as long as they have not reached a specified age limit. These new solutions are then sent to the second phase to determine the best solution among them, replacing the older solution if the new one is better. This process continues until a predefined time limit is reached, and the last solution found is returned as the best solution for the problem. The G&S algorithm was compared to the column generation technique. Both algorithms performed similarly for small instances, but the G&S algorithm was more effective for large instances. From the datasets used in [50], we selected the ones called _hard28_, _hard10_, and _wea_gau1_, available at [68]. Additionally, we included the dataset _falkenauer_U_ from the same repository, which consists of four groups named _binpack1_, _binpack2_, _binpack3_, and _binpack4_. Table 1 provides details about the datasets. The third column lists the minimum and maximum number of item types among the instances of each dataset, while the fourth column shows the number of different item types, along with the standard deviation in rounded brackets. Both the _hinterding_ dataset and the _hard10_ dataset have four different item types, but the variability in the former is greater than in the latter. Figure 7: Result of a structural analysis for a PN-CSP model of an instance of ten different items. The comparisons among the three algorithms were made with respect to the number of stocks used and their optimal theoretical value, which can be obtained using Equation (13). The experiments were conducted on a Quad-Core Intel(R) Core(TM) i5 computer with a 3.4 GHz processor and 8 GB RAM. All three algorithms were coded in Python 3.11.1.